搜索
习题课－线性表顺序表应用例2．1将顺序表(a1，a2，...，an)重新排列为以a1为界的两部分：a1前面的值均比a1小，a1后面的值都比a1大。25302060103515...15102025306035...划分前划分后图2.5顺序表的划分调整前调整后基本思路：从第二个元素开始到最后一个元素，逐一向后扫描：（1）当前数据元素aI比a1大时，表明它已经在a1的后面，不必改变它与a1之间的位置，继续比较下一个。（2）当前结点若比a1小，说明它应该在a1的前面，此时将它上面的元素都依次向下移动一个位置，然后将它置入最上方。算法1算法如下：voidpart(SeqList*L){inti,j;datatypex,y;x=L-elem[0];/*将基准置入x中*/for(i=1;i=L-length;i++)if(L-elem[i]x)/*当前元素小于基准*/{y=L-elem[i];for(j=i-1;j=0;j--)/*移动*/L－elem[j+1]=L-elem[j];L-elem[0]=y;}}最坏情况下移动数据时间性能为Ｏ(ｎ２)。算法2intrearrange(seqList*L)//L是表长为n的线性表，采用顺序存储结构，实现排序，a[0]作为枢轴{i=0;j=L-length-1;t=L-elem[0];while(ij){while(ij&&L-elem[i]=t)j--;if(ij){L-elem[i]=L-elem[j];i++;}while(ij&&L-elem[i]0)i++;if(ij)L-elem[j--]=L-elem[i];}L-elem[i]=t;//将原第一个元素放到最终位置}时间性能为Ｏ(ｎ)。例2．2有顺序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也是从小到大的升序排列。voidmerge(SeqListA,SeqListB,SeqList*C){inti,j,k;i=0;j=0;k=0;m=A.length-1;n=B.length-1;while(i=m&&j=n)if(A.date[i]B.date[j])C-data[k++]=A.data[i++];elseC-data[k++]=B.data[j++];while(i=m)C-data[k++]=A.data[i++];while(j=n)C-data[k++]=B.data[j++];C-length=k-1;}例2.3试编写算法“比较”两个顺序表的大小intcompare(SqListA,SqListB){//若AB返回-1；若A=B返回0；若AB，则返回1j=0;while(jA.length&&jB.length)if(A.elem[j]B.elem[j])return(-1);elseif(A.elem[j]B.elem[j])return(1);elsej++;if(A.length==B.length)return(0);elseif(A.lengthB.length)return(-1);elsereturn(1);}//compare算法的时间性能是O(m+n)例2.4试设计一个算法，用尽可能少的辅助空间将顺序表中前m个元素和后n个元素进行互换，即将线性表(a1,…,am,b1,…,bn)改变成(b1,…,bn,a1,…,am)voidinvert(ElemType&R[],ints,intt){//本算法将数组R中下标自s到t的元素逆置，即//将（Rs,Rs+1,…,Rt-1,Rt）改变为(Rt,Rt-1，…,Rs+1,Rs）for(k=s;k=(s+t)/2;k++){w=R[k];R[k]=R[t-k+s];R[t-k+s]=w;}//for}//invertvoidexchange(SqList&A,intm){//本算法实现顺序表中前m个元素和后n个元素的互换if(m0&&mA.length){n=A.length-m;invert(A.elem,0,m+n-1);invert(A.elem,0,n-1);invert(A.elem,n,m+n-1);}}//exchange算法的时间性能是O(m+n)链表应用解题框架1）必要的初始化：各目标表的初始化，引入源表指示器、目标表指示器；对于仅对一源表进行分解删除的，该源表同时也是目标表，不需要初始化。•源表中是否含头结点，会影响源表指示器的初始化•目标表中是否含头结点，是否是循环链表，是否利用源表结点空间，会影响目标表的初始化•目标表的创建方法(头插法/尾插法)会影响到目标表指示器的定义与设置2）当各源表指示器未到表尾时，根据筛选条件，循环将满足条件的结点插入到目标表中(或根据题目要求释放掉)•源表是否是循环链表，会影响源表表尾的判断•对于选中的结点，其位置要暂存，便于插入到目标表中(或释放掉)；并且对应的源表指示器也要向后推进；•选中结点插入到特定目标表的方法，跟目标表的创建方法有关3）处理尚未到达表尾的源表中的剩余表项链表是否有序对执行时间的影响在这些合并、分解问题中，一些问题的筛选处理时间复杂度会因为源链表是否有序，而有不同的数量级。如：问题1：已知A,B,C三个表，要求对A表进行如下操作：删去那些既在B表中出现又在C表中出现的元素。问题2：已知A,B,C三个递增有序表，要求对A表进行如下操作：删去那些既在B表中出现又在C表中出现的元素。问题1：O(LengthA*max(LengthB,LengthC))问题2：O(LengthA+LengthB+LengthC))。对问题1和2进一步变形，若三表之一或若干有序，且序的方向不一致，这时问题的求解和问题1是类似的。链表的合并和分解1、问题描述:大量的链表应用可以归结为链表的合并、分解问题：1）已知若干个源链表，按一定条件合并成一个目标链表，该目标链表的结点空间可以是重新分配的空间，也可以是利用源表结点的空间；例2-1A=A∪B例2-2C=A∪B,其中A和B中的数据元素按值非递减有序排列，要求归并后的C也要按值非递减有序排列2)已知一个源链表，按一定条件分解成若干目标链表，该目标链表的结点空间可以是重新分配的空间，也可以是利用源表结点的空间；已知一线性链表中含有三类字符的数据元素，试将该链表分割为三个循环链表，其中每个循环链表中均只含一类字符。链表的合并和分解3)若干源链表按一定条件重新组成若干目标链表（1和2的复合）；将线性表L=(a1,a2,a3,……,an)调整为(a1,a3,……,an,……,a4,a2),线性表用带头结点的双向循环链表表示。4)将一个表中的部分元素删除，删除的条件或是简单的，或是根据其它源表中得来。删除数据元素按值非递减有序排列的单链表中所有值大于mink且小于maxk的元素，同时释放被删结点空间。已知A,B,C三个递增有序表，要求对A表进行如下操作：删去那些既在B表中出现又在C表中出现的元素。已知单链表H，写一算法将其倒置。(a)为倒置前，(b)为倒置后。25∧45187629H29∧76184525H(a)(b)算法思路：依次取原链表中的每个结点，将其作为第一个结点插入到新链表中去，指针p用来指向当前结点，p为空时结束。算法如下：voidreverse(LinklistH){LNode*p;p=H-next;/*p指向第一个数据结点*/H-next=NULL;/*将原链表置为空表H*/while(p){q=p;p=p-next;q-next=H-next;/*将当前结点插到头结点的后面*/H-next=q;}}已知单链表L，写一算法，删除其重复结点，(a)为删除前，(b)为删除后。10∧15181510H(a)18∧1510H(b)算法如下：voidpur_LinkList(LinkListH){LNode*p,*q,*r;p=H-next;/*p指向第一个结点*/if(p==NULL)return;while(p-next){q=p;while(q-next)/*从*p的后继开始找重复结点*/{if(q-next-data==p-data){r=q-next;/*找到重复结点，用r指向，删除*r*/q-next=r-next;free(r);}elseq=q-next;}/*while(q-next)*/p=p-next;/*p指向下一个，继续*/}/*while(p-next)*/}例2.5：已知递增有序的两个单链表A，B分别存储了一个集合。设计算法实现求两个集合的并集的运算A:=A∪BLinkListUnion（LinkListha，hb）{pa=ha-next;pb=hb-next;pc=ha;while(pa&&pb)if(pa-datapb-data){pc-next=pa;pc=pa;pa=pa-next;}elseif(pa-datapb-data){pc-next=pb;pc=pb;pb=pb-next;}else//处理pa-data=pb-data{pc-next=pa;pc=pa;pa=pa-next;u=pb;pb=pb-next;free(U);}if(pa)pc-next=pa;elsepa-next=pb;Free(hb);return(ha)}//Union例2：已知两个链表A和B分别表示两个集合，其元素递增排列。编一函数，求A与B的交集，并存放于A链表中。LinkListjoint（LinkListha，hb）{pa=ha-next;pb=hb-next;pc=ha;while(pa&&pb)if(pa-data=pb-data){pc-next=pa;pc=pa;pa=pa-next;u=pb;pb=pb-next;free(U);}elseif(pa-datapb-data){u=pa;pa=pa-next;free(u);}else{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(hb);return(ha)}//joint例3：已知递增有序的单链表A,B和C分别存储了一个集合，设计算法实现A=A∪（B∩C），并使求解结构A仍保持递增。LinkListUnion（LinkListha,hb,hc）{pa=ha-next;pb=hb-next;pc=hc-next;pre=ha;//ha,hb和hc均是代头节点的单链表实现A=A∪(B∩C)//确定表中的第一个元素，因为要求递增有序，删除重复元素合并//元素需要和前驱比较……………………//进行合并，先作（B∩C）找出共同元素，和A表比较插入……………………If(pa)pre-next=pa;//当BC无共同元素时，将A剩余部分链入}//算法Union结束if(pa-datapb-data||pa-datapc-data){pre-next=pa;pre=pa;pa=pa-next}else{while(pb&&pc)if(pb-datapc-data)pb=pb-next;elseif(pb-datapc-data)pc=pc-next;elsebreak;//找到B和C表共同元素if(pb&&pc)//因有共同元素而不是因为B或者C表为空而退出if(pa-datapb-data)//A表当前元素大于共同元素，将B元素链入{pre-next=pb;pre=pb;pb=pb-next;pc=pc-next;}}//结束结果表中第一个元素的确定while(pa&&pb&pc){while(pb&&p