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

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

2、序存储结构,例二：删除有序表中相同的数据元素,void Delete_Equale(SqList La) i=0;j=1； while (jLa.length) if (La.elemi!=La.elemj) i=i+1; La.elemi=La.elemj; j=j+1; La.length=i+ ,分析:顺序表中每删除一个数据元素,被删元素后的元素都要依次向前移动一个位置, 浪费大量的时间. 可以每做一次删除,只做标记,最后一次将剩余元素移动到位 试做此算法懒惰删除 另给出一巧妙算法,2.链式存储结构,例二：删除有序表中相同的数据元素,void Delete_Equale(LinkList

3、 L) pre=L-next;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.elemi; LA.elemi= LA.elemj; LA.elemj=t; ,void reverse(SqList ,a1,a2,a3,L,p,

4、a1,a2,a3,思路一：,1）标志后继结点； 2）修改指针（将*p插入在头结点之后）； 3）重置结点*p（p重新指向原表中后继）；,2.链式存储结构,（1）带头结点单链表,void inverse(LinkList L) / 逆置带头结点的单链表 L p=L-next; 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-

5、next; / succ指向*p的后继 p-next=pre; pre=p; p = succ; L-next=pre; ,思考：不带头结点单链表逆置？带头结点单循环链表逆置,思路二:直接修改结点的指针域,指向原来链表上其直接前驱结点,1）void inverse(LinkList L) /思路直接逆置 / 逆置不带头结点的单链表 L p= NULL; /p记录刚逆置的结点 q=L;/q记录将要逆置的结点 while ( q!=NULL) L=L-next; q-next=p; p = q; q = L; L=p; ,（2）不带头结点单链表,2) p=L-next;L-next=NULL; w

6、hile ( p!=NULL) r=p-next; p-next=L; L=p; p=r; /思路同上，细节不同,3)先加头结点，逆置后再删除,void inverse(LinkList L) / 逆置带头结点的单循环链表L p=L-next; L-next=L; while (p!=L) r=p-next; p-next=L-next; L-next=p; p=r; ,（3）带头结点单循环链表,void inverse(LinkList ,（4）不带头结点单循环链表,分析：应先找到第i-1个结点，记下第i个结点，然后从第i+1个结点开始直至第m个结点，依次插入到第i-1个结点之后，最后将暂存

7、的第i个结点的指针指向原第m个结点（即倒置后第i-1个结点的后继）。,（5）已知L为链表的头结点地址，表中共有m个结点(m3)，从表中第i个结点起到第m个结点构成一个循环部分链表，设计将这部分循环链表中所有结点顺序完全倒置的算法。,void ParrernInvert(LinkList /原第i个结点指向原第m个结点 ,分析：本题也是模式匹配问题，应先找出链表L2在链表L1中的出现位置，然后再将L1中的L2倒置。设L2在L1中出现时第一个字母结点的前驱的指针为p，最后一个字母结点在L1中为q所指结点的前驱，则在保存p后继结点指针s的情况下，执行p-next=q，之后再将s到q结点的前驱依次插入

8、到p结点之后。,（6）L1与L2分别为两单链表头结点地址指针，且两表中数据结点的数据域均为一个字母。设计把L1中与L2中数据相同的连续结点顺序完全逆置的算法。,void ParrernInvert(LinkList else printf(“L2并不存在于L1中”)； ,思考： 1）L2在L1中出现多次时？ 2）统计L2在L1中出现的次数,有序顺序表的合并 教材p26 另 void union(SqList LA, SqList LB, SqList LC) i=0; j=0; k=0; while(iLA.length ,1.顺序存储结构,例四：线性表的合并,1.顺序存储结构,例四：线性表的

9、合并,顺序结构线性表LA与LB的结点关键字为整数。 LA与LB的元素按非递减有序，线性表空间足够大。试给出一高效算法，将LB种元素合并到LA中，使新的LA的元素仍保持非递减有序。高效是指最大限度地避免移动元素。,分析：顺序存储结构的线性表的插入、删除，其时间复杂度为O(n)，平均移动近一半的元素。两表合并时，若从第一个元素开始，一定会造成元素后移，这不符合题目要求。题中叙述“线性表空间足够大”暗示出另外的合并方式，即应从线性表的最后一个元素开始比较，较大者放到最终位置上。,void union(SqList LA,SqList LB) m=LA.length; n=LB.length; k=m

10、+n; i=m-1; j=n-1; while(i=0 ,2.链式存储结构（1）,例四：线性表的合并,void MergeList_L(LinkList /MergeList_L,利用归并思想,该算法去掉if/else即可表示题集2.23交叉合并两线性表; 该题结合逆置思想即可表示2.24(合并为一个非递增有序链表),2.链式存储结构（2）,例四：线性表的合并,void MergeList_L(LinkList /MergeList_L,2.链式存储结构（3）,例四：线性表的合并,已知L1、L2分别为两单链表的头结点指针，m、n分别为L1、L2表中数据结点个数。要求设计一算法，用最快速度将两表

11、合并成一个带头结点的单链表。,LinkList Union(LinkList L1,LinkList L2) if (mnext=NULL) p=p-next; p-next=L2-next; L2-next=L1-next; free(L2);return(L1); elseif(n=0) return(L1); else p=L2; while(p-next!=NULL) p=p-next; p-next=L1-next; L1-next=L2-next; free(L1); return(L2); ,题目要求“用最快速度将两表合并”，因此应找结点个数少的链表查找其尾结点,2.链式存储结构

12、（4）,例四：线性表的合并,编写算法实现连接线性表la和lb（lb在后）的算法，要求其时间复杂度为O(1)，占用辅助空间尽量小。描述所用结构。,应使用只设尾指针的单循环链表 LinkList Union(LinkList la,LinkList lb) /不带头结点 q=la-next; la-next=lb-next; lb-next=q; return(lb); ,LinkList Union(LinkList la,LinkList lb) /带头结点 q=lb-next; lb-next=la-next; la-next=q-next; free(q); return(lb); ,2.

13、链式存储结构（5）,例四：线性表的合并,设有两个链表，ha为单链表，hb为单循环链表。编写算法，将两个链表合并成一个单链表，要求算法所需时间与链表长度无关。,应使用只设尾指针的单循环链表 LinkList Union(LinkList ha,LinkList hb) /不带头结点 q=hb-next; hb-next=ha; ha=q; return(ha); ,LinkList Union(LinkList ha,LinkList hb) /带头结点 q=hb-next; hb-next=ha-next; ha-next=q-next; free(q); return(hb); ,顺序存储的

14、线性表A，其数据元素为整型，试编写算法，将A拆成B和C两个表，使A中元素值大于等于0的元素放入B，小于0的元素放入C，要求：1）表B和C另外设置存储空间； 2）表B和C不另外设置存储空间； 山东大学 2001 九 1(12分),例五：线性表的拆分,1）void rearray(int A ,int ,1.顺序存储结构,int rearray(SqList A) i=0; j=A.length-1; t=a0; while(i=0) j-; if (ij) A.elemi= A.elemj;i+; while (ij A.elemi0 ? return (i+1) : return i ,2）表

15、B和C不另外设置存储空间； 分析:实现算法可以重排具有n个元的顺序表,使得所有值为负数的元素移动到正数元素的前面.采用快速排序的思想来实现,只是提出暂存的第一个元素(枢轴)并不作为比较标准,比较标准是 0,1）编写函数将一整数序列(顺序表)中的所有负数移到所有正数之前，要求时间复杂度为O(n)。【东北大学 1998 南航2001】 2）设有一元素为整数的线性表L=a1,a2,an 存放在一维数组AN中，设计一算法，以表中an为参考元素，将该表分为左右两部分，左部分小于等于an ，右部分大于an， an在分界线上。【北京理工大学 1999年 八（6分】 3）已知线性表a1,a2,an按顺序存储，

16、且每个元素都是不相等的整数，设计把所有奇数移到所有偶数前边的算法（时间最少，空间最小） 【东北大学 1997 】,类似描述：,设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B，C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B，C表利用A表的结点）。 【北京理工大学 2000】,例五：线性表的拆分,分析：题目中链表带头结点,分解后的两个链表不要求数值有序, 要求利用原表空间,采用方法: 将新结点插到头结点之后.,2.链式存储结构（1）,void DisCreat(LinkList A) B=A; C=(LNode *) m

17、alloc(sizeof(LNode); C-next=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=succ; ,例五：线性表的拆分,已知L为不带头结点的单链表中的一个结点的指针，每个结点数据域存放一个字符，该字符可能是英文字母或数字或其它字符，编写算法构造三个以带头结点的单循环链表表示的线

18、性表，使每个表中只含同一类字符（要求用最小的空间和最少的时间）,例五：线性表的拆分,分析：将一个表拆成三个带头结点的表，应先构造三个表头结点，然后从原链表第一个结点开始一个个结点进行判断和链接，注意不要因结点插入新链表而使原链表断链。,2.链式存储结构（2）,void onetothree(LinkList ,例五：线性表的拆分,else if (r-data=o ,例五：线性表的拆分,设计一算法，将不带头结点的单链表L中的结点分成一个奇数链和一个偶数链，分别由P、Q指向，每个链中的数据按由小到大排列，算法中不得申请新的结点空间。,例五：线性表的拆分,分析：将一个表拆成两个表，两个表都要有序，

19、不能申请空间，这就要利用原链表空间，随着原链表的分解，新建链表随之排序。,2.链式存储结构（3）,void split(LinkList /链入结点 ,例五：线性表的拆分,else if (Q=NULL) Q=s;Q-next=NULL;/第一个奇数结点 elsepre=Q; if (pre-datas-data) /比第一个小，修改头指针 s-next=pre;Q=s; else while(pre-next!=NULL)/查找插入位置 if (pre-next-datadata) pre=pre-next; s-next=pre-next; pre-next=s;/链入结点 s=r; ,例

20、五：线性表的拆分,将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A表中含有原表中序号为奇数的元素，而B表中含有原表中序号为偶数的元素，且保持其相对位置不变。,例五：线性表的拆分,分析：因为要将序号是奇数的元素和序号是偶数的元素分开，因此要有计数器用来区分序号的奇偶数；由于分解后两表中元素结点的相对位置不变，故采用在链表尾插入比较方便，这使用一指向表尾的指针即可方便实现。,2.链式存储结构（4）,void Discreat(LinkList ,例五：线性表的拆分,例六：集合的并、交、差运算,分析：本题实质上是两个链表的合并操作，与前面讲过的并运算不同的是递增有序，即不允许有相同元素，因此两表合并时，如有相等的元素，则应删除一个。,1.并 已知递增有序的两个单链表A、B分别存储了一个集合。设计算法实现两个集合的并运算,例六：集合的并、交、差运算,LinkList Union(Lin