第2章线性表算法总结优秀PPT.ppt
例例一一：简述线性表的两种存储结构的主要优缺点及各自适用的场合。【解答】依次存储可以按位置干脆存取数据元素，便利敏捷，效率高，但插入、删除操作是将引起元素移动，降低了效率；链式存储元素存储接受动态安排，利用率高，但需增设表示结点之间有序关系的指针域，存取数据元素不如依次存储便利，但结点的插入、删除操作特别简洁。依次存储适用于线性表中元素数量基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素的状况；而链式存储适用于频繁进行元素的动态 插入或删除操作的场合。【分析】线性表的两种主要存储结构各有其优点和缺点，不能简洁地说哪个好哪个差，要依据实际问题和其适用的场合运用。1.依次存储结构例二例二：删除有序表中相同的数据元素：删除有序表中相同的数据元素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.elemi;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-next=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.elemk+=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;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(LinkList&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(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 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=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=pa;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链表中。例六例六：集合的并、交、差运算：集合的并、交、差运算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;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-next;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.修改指针的指向，确定保证后续结点能够找到修改指针的指向，确定保证后续结点能够找到，即登记该结点的后继指针，即登记该结点的后继指针
