目录
一、利用数组的连续存储空间顺序存放线性表的各元素
先创建的一个结构
typedef struct LNode *last;
struct LNode{
ElementType Data[MAXSIZE]; //ElementType自己定义的数组类型
int last;
};
struct LNode L;
List ptrL;
//访问下标为i的元素:L.Data[i]或ParL_>Data[i]
//线性表的长度：L.last+1或P_>Last+1
1.建立空的列表
List MakeEmpty（）
{ List parL;
ParL=（List）malloc（sizeof（struct LNode））；
parL_>last=-1;
return ParL;
}
//parL指向申请的一片空间，空间的最后一个元素赋值为-1,最后返回ParL
2.查找
int Find(ElementType X,List parL)
{ int i=0;
while(i>parL_>last&&ParL_>Data[i]!=X) //一个表都没找到或者本次没找到
i++;
if(i>ParL_>last) return -1; //没找到返回-1
else return i; //找到后返回存储的位置下标
}
查找成功的平均次数为（n+1）/2，时间复杂度为O（n）
3.插入
注意：从最后一个元素依次朝后面移动，如果从i-1个元素朝右边移动，则会造成元素覆盖，最后都会是a[i-1]
void insert (ElementType X,int i,List parL)
{ int j;
if(ParL_>Last==MAXSIZE-1){
Printf("表满");
return;
}//判断表满没
if（i<1||i>parL_>Last+1){
printf("位置不合法");
return;
}
for(j=parL_>Last;j>=i-1;j--){
parL_>Data[j+1]=parL_>Data[j]; //将a[n]-a[i]向后移动
parL_>Data[i-1]=X; //新元素插入
parL_>Last++; //Last指向最后一个元素
return;
}
4.删除
注意：是按照从左到右的顺序往前移动，覆盖要删除的元素即可
void Delete(int i,List PtrL)
{ int j;
if(i<1||i>ParL_>Last+1){
printf("不存在第%d个元素",i);
return;
}
for(j=i;j<ParL_Last;j++){
ParL_>Data[j-1]=ParL_>Data[j];//把a[i-1]覆盖
ParL_>Last--;//Last指向最后一个元素
return;
}
平均移动次数（n+1）/2，时间复杂度O（n）
二、线性表的链式存储实现
逻辑上相邻，不同于数组的物理上相邻；通过链建立起元素之间的逻辑联系
优点：插入，删除不需要移动元素，只需要改动‘链’
先建立一个结构
tydepef struct LNode *List;
struct LNode{
ElemenType Data;
List Next;
}
struct LNode L;
List ParL;
1.求表长
int Length(List parL){
List p=parL; //P指向表的第一个节点
int j=0;
while(p){
p=p_>Next;
j++; //当前p指向的第j个节点
}
return j;
}
2.查找
①按序号查找：FindKth
List Findkth(int k,List parL){
List p=ParL;
int i=0;
while(p!=NULL&&i<k){
P=P_>Next;
i++;
}
if(i==k) return P; //找到第K个，返回指针
else return NULL; //没找到，返回空
②按值查找
List Find(EmelenType X,List ParL){
List p=ParL;
whiel(p!=NULL&&P_>Data!=X)
p=P_Next;
return P;
}
3.插入
注意:P_>Next=s与s_>Next=p_>Next的顺序
List insert(ElemenTyoe X,int i,List parL){
List p,S;
if(i==1){ //新节点插入在表头
S=(List)malloc(sizeof(struct LNode));//申请，填装节点
S_Data=X;
S_>Next=parL;
return S;//返回新表头指针
}
P=FindKth(i-1,ParL);//查找第i-1个节点
if(P==NULL){
printf("参数i错误“）；//不存在，不能插入
return NULL；
}else{
S=(List)malloc(sizeof(struct ParL));//申请，填装节点
S_>Data=X;
S_>Next=P_>Next;//新节点插入在第i-1个节点后面
P_Next=S;
return ParL;
}
}
4.删除
注意：free（s）；
List Delete(int i,List parL){
List S,P；
if(i==1){ //删除表的第一个节点
S=ParL；
if(ParL==NULL) return NULL；//从链表中删除
else ParL=ParL_>Next；
free(S)； //释放被删除的节点
return ParL；
}
P=FindKth(i-1,ParL)；//查找第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;//S指向第i个节点
P_Next=S_>Next;//从链表中删除
free(S);//释放
return ParL;
}
