《数据结构》复习笔记--线性表

本文主要是介绍《数据结构》复习笔记--线性表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给出线性表的顺序实现：

代码如下：

//线性表的顺序存储实现
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
typedef struct {
ElementType Data[MAXSIZE];
int Last;
}List;
List L,*Ptrl;
List *makeEmpty()//初始化
{List *ptrL;ptrL=(List *) malloc(sizeof(List));ptrL->Last=-1;return ptrL;
}
int find(ElementType x,List *ptrL)//查找
{int i=0;while(i<=ptrL->Last&&ptrL->Data[i]!=x){i++}if(i>ptrL->Last) return -1;else return i;
}
void insert(ElementType x,int i,List *ptrL)
{int j;if(ptrL->Last==<MAXSIZE-1){printf("表满");return ;}if(i<1||i>ptrL->Last+2){printf("位置不合法");return ;}for(j=ptrL->Last; j>=i-1; j--)ptrL->Data[j+1]=ptrL->Data[j];ptrL->Data[i+1]=X;ptrL->Last++;return;
}
void delete(int i,List *ptrL)
{int j;if(i<1||i>ptrL->Last+1){printf("元素不存在！");return;}for(j=i; j<=ptrL->Last; j++)ptrL->Data[j-1]=ptrL->Data[j];ptrL->Last--;return ;
}
int main()
{/* 如果把后移数组元素的循环for ( j = PtrL->Last; j >= i-1; j-- )PtrL->Data[j+1]=PtrL->Data[j];改为for ( j = i-1; j <= PtrL->Last; j++ )PtrL->Data[j+1]=PtrL->Data[j];那会是什么后果？结果：分量Data[i-1]到Data[Ptrl->Last+1]都是同一个值，即移之前Data[i-1]的值*/
}

代码如下：

//线性表的链式存储实现
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
typedef struct
{ElementType Data;struct Node *Next;
} List;
List L,*PtrL;
int Length(List *PtrL)/*采用循环遍历一遍的方法，当指向为空(null)，返回j,时间性能为o(n)*/
{List *p=PtrL;/*p指向表的第一个结点*/int j=0;while(p){p=p->Next;j++;/*当前p指向的是第j个结点*/}return j;
}
List *FindKth(int K,List *PtrL)/*按序号查找，时间性能为o(n)*/
{List *p=PtrL;int i=1;while(p!=NULL&&i<K){p=p->Next;i++;}if(i==K) return p;/*找到第K个，返回指针*/else return NULL;/*否则返回空*/
}
List *Find(ElementType X,List *Ptrl)/*按值查找，时间性能为o(n)*/
{List *p=Ptrl;while(p!=NULL&&p->Data!=X)p=p->Next;return p;
}
List *Insert(ElementType X,int i,List *Ptrl)//s->Next指向s,从而不能正确完成插入
{List *p,*s;if(i==1)/*新结点插入在表头*/{s=(List*)malloc(sizeof(List));/*申请，填充结点*/s->Data=X;s->Next=Ptrl;return s;/*返回新表头指针*/}p=FindKth(i-1,PtrL);/*查找第i-1个结点*/if(p==NULL)/*第i-1个不存在，不能插入*/{printf("参数i错");return NULL；}else{s=(List*)malloc(sizeof(List));/*申请，填充结点*/s->Data=X;s->Next=p->Next;/*新结点插入在第i-1个结点的后面*/p->Next=s;return Ptrl;}
}
List *Delete(int i,List *PtrL)/*平均查找次数n/2,时间性能o(n)*/
{List *p,*s;if(i==1)/*若要删除的是表的第一个结点*/{s=PtrL;/*指向第1个结点*/if(PtrL!=NULL) PtrL=PtrL->Next;else return NULL;free(s);/*释放被删除结点*/return PtrL;}P=FindKth(i-1,PtrL);/*查找第i-1个结点*/if(p==NULL){printf("第%d 个结点不存在",i-1);return NULL;}else if(p->Next==NULL){printf("第%d 个结点不存在",i);return NULL;}else {s=p->Next;/*指向第i个结点*/p->Next=s->Next/*从链表中删除*/free(s);/*释放被删除结点*/return PtrL;}
}

这篇关于《数据结构》复习笔记--线性表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---