第二章 线性表.ppt

《第二章 线性表.ppt》由会员分享，可在线阅读，更多相关《第二章 线性表.ppt（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章第二章 线性表线性表n n2.1 线性表的类型定义线性表的类型定义n n2.2 线性表的顺序表示与实现线性表的顺序表示与实现 n n2.3 线性表的链式表示与实现线性表的链式表示与实现n n2.3.1 2.3.1 线性链表线性链表n n2.3.2 2.3.2 循环链表循环链表n n2.3.3 2.3.3 双向链表双向链表第二章第二章 线性表线性表n n线性结构的特点是线性结构的特点是:n n存在唯一的存在唯一的存在唯一的存在唯一的第一个第一个第一个第一个数据元素数据元素数据元素数据元素;n n存在唯一的存在唯一的存在唯一的存在唯一的最后一个最后一个最后一个最后一个数据元素数据元素数据元素

2、数据元素;n n除第一个外除第一个外除第一个外除第一个外,每个数据元素均有且只有一个每个数据元素均有且只有一个每个数据元素均有且只有一个每个数据元素均有且只有一个前驱前驱前驱前驱元元元元素素素素;n n除最后一个外除最后一个外除最后一个外除最后一个外,每个数据元素均有且只有一个每个数据元素均有且只有一个每个数据元素均有且只有一个每个数据元素均有且只有一个后继后继后继后继元素。元素。元素。元素。2.1 2.1 线性表的类型定义线性表的类型定义n n线性表举例线性表举例:n n字母表字母表字母表字母表 (A,B,C,X,Y,Z)(A,B,C,X,Y,Z)n n数据序列数据序列数据序列数据序列 (6

3、,17,28,50,92,188)(6,17,28,50,92,188)n nn个元素的线性表个元素的线性表:n n（a1,a2,ai,ai+1,an）第一个元素第一个元素第一个元素第一个元素(没有前驱没有前驱没有前驱没有前驱)第第第第i i个元素个元素个元素个元素(有唯一的前驱有唯一的前驱有唯一的前驱有唯一的前驱和唯一的后继和唯一的后继和唯一的后继和唯一的后继)最后一个元素最后一个元素最后一个元素最后一个元素(没有后继没有后继没有后继没有后继)线性表的抽象数据类型线性表的抽象数据类型(ADT)(ADT)ADT List ADT List n n数据对象：数据对象：数据对象：数据对象：D=D=

4、a ai i|a|ai i属于属于属于属于Elemset,(iElemset,(i=1,2,n,n0)=1,2,n,n0)n n数数数数 据据据据 关关关关 系系系系：R1=R1=a ai-1i-1,a,ai i|a|ai-1i-1,a,ai i属属属属 于于于于D,(i=2,3,n)D,(i=2,3,n)n n基本操作：基本操作：基本操作：基本操作：n nInitList(&LInitList(&L););n nDestroyList(&LDestroyList(&L););n nListInsert(&L,i,eListInsert(&L,i,e););n nListDelete(&L,i

5、,&eListDelete(&L,i,&e););n n等等等等等等等等 ADT List ADT Listn nInitList(&L);DestroyList(&L);n nClearList(&L);ListEmpty(L);n nListLength(L);GetElem(L,i,&e);n nLocateElem(L,e,compare();n nPriorElem(L,cur_e,&pre_e);n nNextElem(L,cur_e,&next_e);n nListInsert(&L,i,e);ListDelete(&L,i,&e);n nListTraverse(&L,visi

6、ted()线性表线性表ADTADT的基本操作：的基本操作：n nInitList(&L)n n操作结果操作结果操作结果操作结果:构造一个空的线性表构造一个空的线性表构造一个空的线性表构造一个空的线性表L L。n nDestroyList(&L)n n初始初始初始初始条件条件条件条件:线性表线性表线性表线性表L L已经存在。已经存在。已经存在。已经存在。n n操作结果操作结果操作结果操作结果:销毁线性表销毁线性表销毁线性表销毁线性表L L。n nClearList(&L)n n初始条件初始条件初始条件初始条件:线性表线性表线性表线性表L L已经存在。已经存在。已经存在。已经存在。n n操作结果操

7、作结果操作结果操作结果:将线性表将线性表将线性表将线性表L L重置为空表。重置为空表。重置为空表。重置为空表。基本操作基本操作(一一)：n nListEmpty(L)n n初始条件初始条件初始条件初始条件:线性表线性表线性表线性表L L已经存在。已经存在。已经存在。已经存在。n n操操操操作作作作结结结结果果果果:若若若若线线线线性性性性表表表表L L为为为为空空空空表表表表，则则则则返返返返回回回回TURE;TURE;否否否否则返回则返回则返回则返回FALSEFALSE。n nListLength(L)n n初始条件初始条件初始条件初始条件:线性表线性表线性表线性表L L已经存在。已经存在。

8、已经存在。已经存在。n n操作结果操作结果操作结果操作结果:返回线性表返回线性表返回线性表返回线性表L L中的数据元素个数。中的数据元素个数。中的数据元素个数。中的数据元素个数。基本操作基本操作(二二)：n nGetElem(L,i,&e)n n初初初初 始始始始 条条条条 件件件件:线线线线 性性性性 表表表表 L L已已已已 经经经经 存存存存 在在在在，1=i=1=i=ListLength(LListLength(L)。n n操操操操作作作作结结结结果果果果:用用用用e e返返返返回回回回线线线线性性性性表表表表L L中中中中第第第第i i个个个个数数数数据据据据元元元元素素素素的的的的

9、值。值。值。值。n nLocateElem(L,e,compare()n n初始条件初始条件初始条件初始条件:线性表线性表线性表线性表L L已经存在，已经存在，已经存在，已经存在，compare()compare()是数是数是数是数据元素判定函数据元素判定函数据元素判定函数据元素判定函数。n n操作结果操作结果操作结果操作结果:返回返回返回返回L L中第中第中第中第1 1个与个与个与个与e e满足满足满足满足compare()compare()的的的的数据元素的位序。若这样的数据元素不存在则数据元素的位序。若这样的数据元素不存在则数据元素的位序。若这样的数据元素不存在则数据元素的位序。若这样的

10、数据元素不存在则返回值为返回值为返回值为返回值为0 0。基本操作基本操作(三三)：n nPriorElem(L,cur_e,&pre_e)n n初始条件初始条件初始条件初始条件:线性表线性表线性表线性表L L已经存在已经存在已经存在已经存在。n n操操操操作作作作结结结结果果果果:若若若若cur_ecur_e是是是是L L的的的的数数数数据据据据元元元元素素素素,且且且且不不不不是是是是第第第第一一一一个个个个,则则则则用用用用pre_epre_e返返返返回回回回它它它它的的的的前前前前驱驱驱驱,否否否否则则则则操操操操作作作作失失失失败败败败;pre_epre_e无无无无意义。意义。意义。意

11、义。n nNextElem(L,cur_e,&next_e)n n初始条件初始条件初始条件初始条件:线性表线性表线性表线性表L L已经存在。已经存在。已经存在。已经存在。n n操作结果操作结果操作结果操作结果:若若若若cur_ecur_e是是是是L L的数据元素的数据元素的数据元素的数据元素,且不是第最且不是第最且不是第最且不是第最后个后个后个后个,则用则用则用则用next_enext_e返回它的后继返回它的后继返回它的后继返回它的后继,否则操作失否则操作失否则操作失否则操作失 败败败败,next_enext_e无意义。无意义。无意义。无意义。基本操作基本操作(四四)：n nListInser

12、t(&L,i,e)n n初始条件初始条件初始条件初始条件:线性表线性表线性表线性表L L已经存在，已经存在，已经存在，已经存在，1=i=n 1=i=n ListLength(L)+1ListLength(L)+1。n n操作结果操作结果操作结果操作结果:在在在在L L的第的第的第的第i i个位置之前插入新的数据元个位置之前插入新的数据元个位置之前插入新的数据元个位置之前插入新的数据元素素素素e,Le,L的长度加一。的长度加一。的长度加一。的长度加一。插入前插入前(长度为长度为n):(a1,a2,ai-1,ai,an)插插 入入 后后(长长 度度 为为 n+1):(a1,a2,ai-1,e,ai

13、,an)基本操作基本操作(五五)：n nListDelete(&L,i,&e)n n初始条件初始条件初始条件初始条件:线性表线性表线性表线性表L L已经存在，已经存在，已经存在，已经存在，1=i=n 1=i=n ListLength(LListLength(L)。n n操作结果操作结果操作结果操作结果:删除删除删除删除L L的第的第的第的第i i个数据元素个数据元素个数据元素个数据元素,并用并用并用并用e e返回其返回其返回其返回其值值值值,L,L的长度减一。的长度减一。的长度减一。的长度减一。删除前删除前(长度为长度为n):(a1 1,a2 2,ai-1i-1,ai i,ai+1i+1,an

14、 n)删除后删除后(长度为长度为n-1):(a1 1,a2 2,ai-1i-1,ai+1i+1,an n)n nListTraverse(&L,visited()基本操作基本操作(六六)：例例2-1 2-1 线性表线性表La,LbLa,Lb的合并的合并.La=LaLb.(La=LaLb.(算法算法2.1)2.1)void union(List&La,List Lb)La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i=Lb_len;i+)GetElem(Lb,i,e);if(!LocateElem(La,e,equal)ListInsert

15、(La,+La_len,e);/union例例2-1 2-1 线性表线性表La,LbLa,Lb的合并的合并.La=(2,5,7,9)Lb=(4,5,6,7)合并结果合并结果:La=(2,5,7,9,4,6)由本节最后知，算法由本节最后知，算法2.12.1的时间复杂度为的时间复杂度为 O(ListLength(La)ListLength(Lb);例例2-2 2-2 非非递递减减线线性性表表La,LbLa,Lb的的合合并并.Lc=LaLb.(算法算法2.2)La=(3,5,8,11)Lb=(2,6,8,9,11,15,20)合并结果合并结果:Lc=(2,3,5,6,8,8,9,11,11,15,2

16、0)void void void void MergeList(ListMergeList(ListMergeList(ListMergeList(List La,List Lb,List&La,List Lb,List&La,List Lb,List&La,List Lb,List&LcLcLcLc)/已知非递减线性表已知非递减线性表已知非递减线性表已知非递减线性表La,LbLa,LbLa,LbLa,Lb /将所有将所有将所有将所有LaLaLaLa和和和和LbLbLbLb中的数据元素归并到中的数据元素归并到中的数据元素归并到中的数据元素归并到LcLcLcLc中中中中,/使使使使LcLcLcL

17、c的数据元素也是非递减的的数据元素也是非递减的的数据元素也是非递减的的数据元素也是非递减的./MergeListMergeListMergeListMergeList 时间复杂度为时间复杂度为时间复杂度为时间复杂度为:(:(ListLength(La)+ListLength(LbListLength(La)+ListLength(Lb););非递减线性表合并的非递减线性表合并的C C程序程序 InitListInitList(&Lc(&Lc);i=j=1;k=0;);i=j=1;k=0;La_lenLa_len=ListLengthListLength(La(La););Lb_lenLb_le

18、n=ListLengthListLength(Lb(Lb););While(i=While(i=La_lenLa_len)&(j=)&(j=Lb_lenLb_len)GetElemGetElem(La,i,ai(La,i,ai););GetElemGetElem(Lb,j,bj(Lb,j,bj););if(if(aiai=bjbj)ListInsertListInsert(LcLc,+k,+k,aiai);+i;);+i;else else ListInsertListInsert(LcLc,+k,+k,bjbj);+j;);+j;while(i=while(i=La_lenLa_len)Ge

19、tElemGetElem(La,i+,ai(La,i+,ai););ListInsertListInsert(Lc(Lc,+k,+k,aiai););while(j=while(j=Lb_lenLb_len)GetElemGetElem(Lb,j+,bj(Lb,j+,bj););ListInsertListInsert(Lc,+k(Lc,+k,bjbj););n n线性表线性表(a(a1 1,a,a2 2,a,ai i,a,ai+1i+1,a,an n)的顺序表示的顺序表示:用用一一组组地地址址连连续续的的存存贮贮单单元元依依次次存存贮贮线线性性表表的的数据元素数据元素.Loc(ai+1)=L

20、oc(ai)+Loc(ai)=Loc(a1)+(i-1)*设设为每个数据元素所需的存储大小为每个数据元素所需的存储大小2.2 2.2 线线性性表表的的顺顺序序表表示示与与实实现现 (物理结构物理结构)线性表的顺序表示线性表的顺序表示(图示图示)b-b-b-b-为为为为a1a1a1a1数据元素的存储地址数据元素的存储地址数据元素的存储地址数据元素的存储地址-为为为为为每个数据元素所需的存储大小为每个数据元素所需的存储大小为每个数据元素所需的存储大小为每个数据元素所需的存储大小typedeftypedef structstruct ElemTypeElemType *elemelem;intint

21、 length;length;intint listsizelistsize;SqListSqList;Status Status InitList_Sq(SqListInitList_Sq(SqList&L)&L)L.elemL.elem=(=(ElemTypeElemType*)*)mallocmalloc(LIST_INIT_SIZE(LIST_INIT_SIZE *sizeof(ElemTypesizeof(ElemType););if(!if(!L.elemL.elem)return(OVERFLOW);)return(OVERFLOW);L.lengthL.length=0;=0;

22、L.listsizeL.listsize=LIST_INIT_SIZE;=LIST_INIT_SIZE;return OK;return OK;/算法算法算法算法2.32.32.32.3Status Status Status Status ListInsert_Sq(SqlistListInsert_Sq(SqlistListInsert_Sq(SqlistListInsert_Sq(Sqlist&L,&L,&L,&L,intintintint i,i,i,i,ElemTypeElemTypeElemTypeElemType e)e)e)e)/在顺序线性表在顺序线性表在顺序线性表在顺序线性表

23、L L L L的第的第的第的第i i i i个位置之前插入新的元素个位置之前插入新的元素个位置之前插入新的元素个位置之前插入新的元素e e e e /i /i /i /i的合法值为的合法值为的合法值为的合法值为1=i=ListLength_Sq(L)+11=i=ListLength_Sq(L)+11=i=ListLength_Sq(L)+11=i=ListLength_Sq(L)+1 ElemTypeElemTypeElemTypeElemType*q,*p,*q,*p,*q,*p,*q,*p,*newbasenewbasenewbasenewbase;if(iL.length+1)retur

24、n ERROR;if(iL.length+1)return ERROR;if(iL.length+1)return ERROR;if(iL.length+1)return ERROR;/i/i/i/i值不合法值不合法值不合法值不合法 if(if(if(if(L.lengthL.lengthL.lengthL.length=L.listsizeL.listsizeL.listsizeL.listsize)/当前存储空间已满当前存储空间已满当前存储空间已满当前存储空间已满,增加分配增加分配增加分配增加分配newbasenewbasenewbasenewbase=(=(=(=(ElemTypeEle

25、mTypeElemTypeElemType*)*)*)*)reallocreallocreallocrealloc(L.elemL.elemL.elemL.elem,(L.listsize+LISTINCREMENTL.listsize+LISTINCREMENTL.listsize+LISTINCREMENTL.listsize+LISTINCREMENT)*)*)*)*sizeof(ElemTypesizeof(ElemTypesizeof(ElemTypesizeof(ElemType););););if(!if(!newbasenewbase)exit(OVERFLOWexit(OVE

26、RFLOW););/存储分配失败存储分配失败存储分配失败存储分配失败 L.elemL.elem=newbasenewbase;L.listsizeL.listsize+=LISTINCREMENT;+=LISTINCREMENT;/增加存储容量增加存储容量增加存储容量增加存储容量 q=&(L.elemi-1);q=&(L.elemi-1);/q/q为插入位置为插入位置为插入位置为插入位置 for(p=&(L.elemL.length-1);p=q;-p)for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;*(p+1)=*p;/插入位置及之后的元素后移插入位置及

27、之后的元素后移插入位置及之后的元素后移插入位置及之后的元素后移 *q=e;q=e;/插入插入插入插入e e +L.lengthL.length;/表长增表长增表长增表长增1 1 return OK;return OK;/算法算法算法算法2.42.42.42.4Status Status ListDelete_Sq(SqlistListDelete_Sq(Sqlist&L,intL,int i,ElemTypei,ElemType*e)*e)/在顺序线性表在顺序线性表在顺序线性表在顺序线性表L L中删除第中删除第中删除第中删除第i i个元素个元素个元素个元素,并用并用并用并用e e返回其值返回其

28、值返回其值返回其值 /i/i的合法值为的合法值为的合法值为的合法值为1=i=1=i=ListLength_Sq(LListLength_Sq(L)ElemTypeElemType*p,*q;*p,*q;if(iL.length)return ERROR;if(iL.length)return ERROR;/i/i值不合法值不合法值不合法值不合法 p=&(L.elemi-1);p=&(L.elemi-1);/p/p为被删除元素的位置为被删除元素的位置为被删除元素的位置为被删除元素的位置 *e=*p;e=*p;/被删除元素的值赋给被删除元素的值赋给被删除元素的值赋给被删除元素的值赋给e e q=(

29、L.elem+L.length-1);q=(L.elem+L.length-1);/表尾元素的位置表尾元素的位置表尾元素的位置表尾元素的位置 for(+p;p=q;+p)for(+p;pnext;j=1;p=L-next;j=1;while(p&ji)while(p&jnext;+j;p=p-next;+j;if(!p|jI)return ERROR;if(!p|jI)return ERROR;e=p-data;e=p-data;return OK;return OK;/GetElem_LGetElem_L插入结点：插入结点：指针指针p p所指的结点后插入所指的结点后插入指针指针s s所指的结

30、点所指的结点n ns-next=p-next;p-next=s;a1a1a2a2a3a3a1a1a3a3s-next=p-nexts-next=p-nexts-next=p-nexts-next=p-nexta2a2p pp ps ss sp-next=sp-next=sp-next=sp-next=s插入前：插入前：插入前：插入前：插入后：插入后：插入后：插入后：插入结点程序插入结点程序Status Status ListInsert_L(LinkListListInsert_L(LinkList&L,&L,intint i,i,ElemTypeElemType e)e)LinkListLi

31、nkList s,p;s,p;intint j;j;p=L;j=0;p=L;j=0;while(p&jnext;+j while(p&jnext;+j if(!p|ji-1)return ERROR;if(!p|ji-1)return ERROR;s=(s=(LnodeLnode*)*)malloc(sizeof(Lnodemalloc(sizeof(Lnode););if(!s)return OVERFLOW;if(!s)return OVERFLOW;s-data=e;s-data=e;s-next=p-next;s-next=p-next;p-next=s;p-next=s;return

32、 OK;return OK;删除结点：删除结点：删除指针删除指针p p所指的结点后的结点所指的结点后的结点n np-next=p-next-next;a a1 1a a3 3a a2 2p p删除前：删除前：删除前：删除前：删除后：删除后：删除后：删除后：a a1 1a a3 3a a2 2p pp-next=p-next-nextp-next=p-next-nexts ss=p-nexts=p-next释放结点后：释放结点后：释放结点后：释放结点后：a a1 1a a3 3p pfree(s)free(s)删除结点程序删除结点程序删除第删除第i i个元素，并由个元素，并由e e返回其返回其值

33、值Status Status ListDlete_L(LinkListListDlete_L(LinkList L,L,intint i,i,ElemTypeElemType&e)&e)LinkListLinkList s,p;s,p;intint j;j;p=L;j=0;p=L;j=0;while(p-next&jnext;+j while(p-next&jnext;+j if(!(p-next)|ji-1)return ERROR;if(!(p-next)|ji-1)return ERROR;s=p-next;s=p-next;p-next=s-next;p-next=s-next;e=s

34、-data;e=s-data;free(sfree(s););return OK;return OK;n循循环环链链表表的的特特点点:表表中中的的最最后后一一个个结结点点的的指指针域指向头结点针域指向头结点,整个链表形成一个环。整个链表形成一个环。n n从表的任意结点出发可以找到表中其它结点。从表的任意结点出发可以找到表中其它结点。2.3.2 2.3.2 循环链表循环链表a1a2a3Laian2.3.3 2.3.3 双向链表双向链表n n双双向向链链表表的的特特点点:表表中中的的每每个个结结点点有有两两个个指指针针域域，一一个个指指向向后后继继结结点点，一一个个指指向向前前趋趋结结点点,整个链

35、表形成两个环。整个链表形成两个环。n n从从表表的的任任意意结结点点出出发发可可以以通通过过正正向向环环（或或反反向环）找到表中其它结点。向环）找到表中其它结点。typedeftypedef structstruct DuLnodeDuLnode ElemTypeElemType data;data;StructStruct DuLnodeDuLnode *prior;*prior;StructStruct DuLnodeDuLnode *next;*next;DuLnodeDuLnode,*,*DuLinklistDuLinklist;priordatanext结点：结点：结点：结点：插入结

36、点：插入结点：指针指针p p所指的结点前插入所指的结点前插入指针指针s s所指的结点所指的结点n ns-prior=p-prior;s-prior=p-prior;p-prior-next=s;p-prior-next=s;n ns-next=p;s-next=p;p-prior=s;p-prior=s;a1a3a2ps插入前：ps插入后：a1a2a3插入结点程序插入结点程序Status Status ListInsert_DuL(DuLinklistListInsert_DuL(DuLinklist L,L,intint i,i,ElemTypeElemType e)e)DuLinklist

37、DuLinklist s,p;s,p;if (!(p=if (!(p=GetElemP_DuL(L,iGetElemP_DuL(L,i)/在在在在L L中确定第中确定第中确定第中确定第i i个元素的位置指针个元素的位置指针个元素的位置指针个元素的位置指针p p return ERROR;return ERROR;if(!(s=(if(!(s=(DuLinklist)malloc(sizeof(DuLNodeDuLinklist)malloc(sizeof(DuLNode)return ERROR;return ERROR;s-data=e;s-data=e;/构造数据为构造数据为构造数据为构造

38、数据为e e的结点的结点的结点的结点s s s-prior=p-prior;s-prior=p-prior;p-prior-next=s;p-prior-next=s;s-next=p;s-next=p;p-prior=s;p-prior=s;return OK;return OK;/ListInsert_DuLListInsert_DuL删除结点：删除结点：删除指针删除指针p p所指的结点所指的结点a1a1a2a2p p删除前：删除前：删除前：删除前：删除后：删除后：删除后：删除后：p-prior-next=p-nextp-prior-next=p-nexta3a3a1a1a2a2p pa3

39、a3p-next-p-next-proirproir=p-prior=p-prior释放结点：释放结点：释放结点：释放结点：free(pfree(p););删除结点程序删除结点程序删除第删除第i i个元素，并由个元素，并由e e返回其值返回其值Status Status ListDelete_DuL(DuLinklistListDelete_DuL(DuLinklist L,L,intint i,i,ElemTypeElemType&e)&e)DuLinklistDuLinklist p;p;if(!(p=if(!(p=GetElemP_DuL(L,iGetElemP_DuL(L,i)/在在L

40、 L中确定第中确定第i i个元素的位置指针个元素的位置指针p p return ERROR;return ERROR;e=p-data;e=p-data;/删除的结点的值存入删除的结点的值存入e e p-prior-next=p-next;p-prior-next=p-next;p-next-prior=p-prior;p-next-prior=p-prior;free(pfree(p););return OK;return OK;/ListDelete_DuLListDelete_DuL插入和删除的完整实例插入和删除的完整实例typedeftypedef intint ElemTypeEle

41、mType;typedeftypedef intint Status;Status;#define OK 1#define OK 1#define OVERFLOW-2#define OVERFLOW-2#define ERROR 0#define ERROR 0#define LIST_INIT_SIZE 100#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define LISTINCREMENT 10typedeftypedef structstruct ElemTypeElemType*elemelem;intint length;

42、length;intint listsizelistsize;SqlistSqlistmain()main()SqlistSqlist LstLst;intint i,n=101;i,n=101;ElemTypeElemType e;e;if(if(InitList_SqInitList_Sq(&Lst&Lst)=OK)=OK)/线性表线性表线性表线性表LstLst 初始化成功初始化成功初始化成功初始化成功 for(i=1;i=n;i+)for(i=1;i=n;i+)if(if(ListInsert_SqListInsert_Sq(&LstLst,i,i)!=OK)break;,i,i)!=O

43、K)break;/插入值插入值插入值插入值1 1到到到到n n printf(“nprintf(“n”);”);/换行换行换行换行 for(i=0;ifor(i=0;iLst.lengthLst.length;i+);i+)printfprintf(i,ei,e=%=%d,%dnd,%dn,i,i,Lst.elemiLst.elemi ););/打印值打印值打印值打印值1 1到到到到n n getchgetch();();/等待键盘响应等待键盘响应等待键盘响应等待键盘响应 if(if(ListDelete_SqListDelete_Sq(&Lst&Lst,5,&e)=OK),5,&e)=OK)

44、/删除第删除第删除第删除第5 5个元素个元素个元素个元素 printfprintf(delete_elemdelete_elem=%=%dndn,e);,e);/打印被删除的元素打印被删除的元素打印被删除的元素打印被删除的元素 getchgetch();();/等待键盘响应等待键盘响应等待键盘响应等待键盘响应 for(i=0;ifor(i=0;iL-elemelem=(=(ElemTypeElemType*)*)mallocmalloc(LIST_INIT_SIZE(LIST_INIT_SIZE *sizeof(ElemTypesizeof(ElemType););if(!L-if(!L-el

45、emelem)exit(OVERFLOWexit(OVERFLOW););/存储分配失败存储分配失败存储分配失败存储分配失败 L-length=0;L-length=0;/空表长度为空表长度为空表长度为空表长度为0 0 L-L-listsizelistsize=LIST_INIT_SIZE;=LIST_INIT_SIZE;/初始存储容量初始存储容量初始存储容量初始存储容量 return OK;return OK;/算法算法算法算法2.32.32.32.3Status Status ListInsert_Sq(SqlistListInsert_Sq(Sqlist*L,*L,intint i,i,

46、ElemTypeElemType e)e)/在顺序线性表在顺序线性表在顺序线性表在顺序线性表L L的第的第的第的第i i个位置之前插入新的元素个位置之前插入新的元素个位置之前插入新的元素个位置之前插入新的元素e e /i /i的合法值为的合法值为的合法值为的合法值为1=i=1=i=ListLength_Sq(LListLength_Sq(L)+1)+1 ElemTypeElemType*q,*p,*q,*p,*newbasenewbase;if(iL-length+1)return ERROR;if(iL-length+1)return ERROR;/i/i值不合法值不合法值不合法值不合法 i

47、f(L-length=L-if(L-length=L-listsizelistsize)/当前存储空间已满当前存储空间已满当前存储空间已满当前存储空间已满,增加分配增加分配增加分配增加分配 newbasenewbase=(=(ElemTypeElemType*)*)reallocrealloc(L-(L-elemelem,(L-,(L-listsizelistsize +LISTINCREMENT)*+LISTINCREMENT)*sizeof(ElemTypesizeof(ElemType););if(!if(!newbasenewbase)exit(OVERFLOW);)exit(OVER

48、FLOW);/存储分配失败存储分配失败存储分配失败存储分配失败 L-L-elemelem=newbasenewbase;L-L-listsizelistsize+=LISTINCREMENT;+=LISTINCREMENT;/增加存储容量增加存储容量增加存储容量增加存储容量 q=&(L-elemi-1);q=&(L-elemi-1);/q/q为插入位置为插入位置为插入位置为插入位置 for(p=&(L-for(p=&(L-elemLelemL-length-1);p=q;-p)-length-1);p=q;-p)*(p+1)=*p;*(p+1)=*p;/插入位置及之后的元素后移插入位置及之后的

49、元素后移插入位置及之后的元素后移插入位置及之后的元素后移 *q=e;q=e;/插入插入插入插入e e +L-length;+L-length;/表长增表长增表长增表长增1 1 return OK;return OK;/算法算法算法算法2.42.42.42.4Status Status ListDelete_Sq(SqlistListDelete_Sq(Sqlist*L,intL,int i,ElemTypei,ElemType*e)*e)/在顺序线性表在顺序线性表在顺序线性表在顺序线性表L L中删除第中删除第中删除第中删除第i i个元素个元素个元素个元素,并用并用并用并用e e返回其值返回其值

50、返回其值返回其值 /i/i的合法值为的合法值为的合法值为的合法值为1=i=1=i=ListLength_Sq(LListLength_Sq(L)ElemTypeElemType*p,*q;*p,*q;if(iL-length)return ERROR;if(iL-length)return ERROR;/i/i值不合法值不合法值不合法值不合法 p=&(L-elemi-1);p=&(L-elemi-1);/p/p为被删除元素的位置为被删除元素的位置为被删除元素的位置为被删除元素的位置 *e=*p;e=*p;/被删除元素的值赋给被删除元素的值赋给被删除元素的值赋给被删除元素的值赋给e e q=(L