第2章线性表算法总结.ppt

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

1、例例一一：简述线性表的两种存储结构的主要优缺点及各自适用的场合。【解答】顺序存储可以按位置直接存取数据元素，方便灵活，效率高，但插入、删除操作是将引起元素移动，降低了效率；链式存储元素存储采用动态分配，利用率高，但需增设表示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作十分简单。顺序存储适用于线性表中元素数量基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素的情况；而链式存储适用于频繁进行元素的动态 插入或删除操作的场合。【分析】线性表的两种主要存储结构各有其优点和缺点，不能简单地说哪个好哪个差，要根据实际问题和其适用的场合使用。1.顺序存储结

2、构例二例二：删除有序表中相同的数据元素：删除有序表中相同的数据元素void Delete_Equale(SqList La)i=0;j=1；while(jnext;p=pre-next；while(p!=NULL)if (pre-data!=p-data)pre=p;p=p-next;else u=p;p=p-next;pre-next=p;free(u);1.顺序存储结构例三例三：线性表的就地逆置：线性表的就地逆置void reverse(SqList LA)/使用两个控制变量使用两个控制变量 ElemType t;for(i=0,j=LA.length-1;ij;i+,j-)t=LA.el

3、emi;LA.elemi=LA.elemj;LA.elemj=t;void reverse(SqList&LA)/使用一个控制变量使用一个控制变量 ElemType t;n=LA.length;for(i=0;inext;L-next=NULL;while(p)succ=p-next;/succ指向*p的后继 p-next=L-next;L-next=p;/*p插入在头结点之后 p=succ;void inverse(LinkList L)p=L-next;pre=NULL;while(p)succ=p-next;/succ指向*p的后继 p-next=pre;pre=p;p=succ;L-n

4、ext=pre;思考：不带头结点单链表思考：不带头结点单链表逆置？带头结点单循环链逆置？带头结点单循环链表逆置表逆置思路二思路二:直接修改结点的指针域直接修改结点的指针域,指向原来指向原来链表上其直接前驱结点链表上其直接前驱结点有序顺序表的合并 教材p26 另void union(SqList LA,SqList LB,SqList LC)i=0;j=0;k=0;while(iLA.length&j LB.length)if(LA.elemi=LB.elemj)LC.elemk+=LA.elemi+;else LC.elemk+=LB.elemj+;while(i LA.length)LC.e

5、lemk+=LA.elemi+;while(j=0&j=0)if(LA.elemi=LB.elemj)LA.elem-k=LA.elemi-;else LA.elem-k=LB.elemj-;while(j=0)LA.elem-k=LB.elemj-;2.链式存储结构（1）例四例四：线性表的合并：线性表的合并void MergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc)/将两个非递减有序链表合并为一个将两个非递减有序链表合并为一个非递减非递减有序链表，有序链表，利用原表空间，带头结点利用原表空间，带头结点 pa=La-next;pb=Lb-next;

6、Lc=pc=La;while(pa&pb)if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;else pc-next=pb;pc=pb;pb=pb-next;pc-next=pa?pa:pb;free(Lb);/MergeList_L利用归并思想利用归并思想,该算该算法去掉法去掉if/else即可表即可表示题集示题集2.23交叉合并交叉合并两线性表两线性表;该题结合该题结合逆置思想即可表示逆置思想即可表示2.24(合并为一个合并为一个非非递增递增有序链表有序链表)2.链式存储结构（2）例四例四：线性表的合并：线性表的合并void MergeList_L(Li

7、nkList&La,LinkList&Lb)/将两个非递减有序链表合并为一个将两个非递减有序链表合并为一个非递增非递增有序链表，利用原表有序链表，利用原表空间，带头结点空间，带头结点 pa=La-next;pb=Lb-next;La-next=NULL;while(pa&pb)if(pa-datadata)r=pa-next;pa-next=La-next;La-next=pa;pa=r;else r=pb-next;pb-next=La-next;La-next=pb;pb=r;while(pa)r=pa-next;pa-next=La-next;La-next=pa;pa=r;while(

8、pb)r=pb-next;pb-next=La-next;La-next=pb;pb=r;/MergeList_L顺序存储的线性表A，其数据元素为整型，试编写算法，将A拆成B和C两个表，使A中元素值大于等于0的元素放入B，小于0的元素放入C，要求：1）表B和C另外设置存储空间；2）表B和C不另外设置存储空间；山东大学 2001 九 1(12分)例五例五：线性表的拆分：线性表的拆分1）void rearray(int A,int&B,int&C)i=0;j=k=-1;while(in)if(Ai0)C+k=Ai+;else B+j=Ai+;1.顺序存储结构 int rearray(SqList

9、A)i=0;j=A.length-1;t=a0;while(ij)while(i=0)j-;if(ij)A.elemi=A.elemj;i+;while(ij&ai0)i+;if(ij)A.elemj=A.elemi;j-;A.elemi=t;A.eleminext=NULL;p=A-next;/p为工作指针 B-next=NULL;while(p!=NULL)succ=p-next;/暂存p的后继 if (p-datanext=B-next;B-next=p;else if (p-data0)p-next=C-next;C-next=p;elseu=p;p=p-next;free(u);p=

10、succ;例五例五：线性表的拆分：线性表的拆分例六例六：集合的并、交、差运算：集合的并、交、差运算分析：分析：本题实质上是两个链表的合并操作，与前面讲过的并运算不同的是递增有序，即不允许有相同元素，因此两表合并时，如有相等的元素，则应删除一个。1.并 已知递增有序的两个单链表A、B分别存储了一个集合。设计算法实现两个集合的并运算例六例六：集合的并、交、差运算：集合的并、交、差运算LinkList Union(LinkList ha,LinkList hb)pa=ha-next;pb=hb-next;pc=ha;while(pa&pb)if(pa-datadata)pc-next=pa;pc=p

11、a;pa=pa-next;else if(pa-datapb-data)pc-next=pb;pc=pb;pb=pb-next;else pc-next=pa;pc=pa;pa=pa-next;/处理相等 u=pb;pb=pb-next;free(u);if(pa)pc-next=pa;else pc-next=pb;free(hb);return(ha);例六例六：集合的并、交、差运算：集合的并、交、差运算分析：分析：求交集，即同时出现在两集合中的元素才出现在结果表中。2.交 已知两个单链表A、B分别表示一个集合，其元素递增排列。设计算法实现两个集合的交运算，并存放于A链表中。例六例六：集合

12、的并、交、差运算：集合的并、交、差运算void Same(LinkList&La,LinkList Lb)pa=La-next;pb=Lb-next;pc=La;while(pa&pb)if(pa-datadata)u=pa;pa=pa-next;free(u);else if(pa-datapb-data)u=pb;pb=pb-next;free(u);else pc-next=pa;pc=pa;pa=pa-next;/处理相等 u=pb;pb=pb-next;free(u);while(pa)u=pa;pa=pa-next;free(u);while(pb)u=pb;pb=pb-next;

13、free(u);pc-next=NULL;free(Lb);例六例六：集合的并、交、差运算：集合的并、交、差运算分析：分析：求两个集合的差A-B（A中出现B中不出现的元素构成的集合），即在A中删除A和B中共有的元素。由于集合用单链表存储，问题变成删除链表中的结点操作，因此要记住被删除结点的前驱，防止“断链”。3.差 已知递增有序的单链表A、B分别存储了一个集合，请设计算法以求出两个集合的差A-B，并以同样的形式存储，同时返回该集合的元素个数。例六例六：集合的并、交、差运算：集合的并、交、差运算int Defrence(LinkList&A,LinkList B)p=A-next;q=B-nex

14、t;pre=A;n=0;while(q!=NULL&q!=NULL)if(p-datadata)pre=p;p=p-next;n+;else if(p-dataq-data)q=q-next;else pre-next=p-next;u=p;p=p-next;free(u);return(n);例六例六：集合的并、交、差运算：集合的并、交、差运算分析：分析：本题先求和的交集，即求和中共有元素，再与求并集，同时删除重复元素，以保持结果递增。4.混合 已知递增有序的单链表A、B和分别存储了一个集合，请设计算法实现（），使求解结果仍保持递增。要求算法的时间复杂度为(|A|+|B|+|C|)。单链表编程注意1.掌握通过画出结点图来进行链表的生成、插入、掌握通过画出结点图来进行链表的生成、插入、删除、遍历等操作删除、遍历等操作2.对链表的操作，都要从头结点开始对链表的操作，都要从头结点开始3.若在某结点前插入或删除某元素，必须知道该元若在某结点前插入或删除某元素，必须知道该元素的前驱结点的指针素的前驱结点的指针4.修改指针的指向，一定保证后续结点能够找到修改指针的指向，一定保证后续结点能够找到，即记下该结点的后继指针，即记下该结点的后继指针