第2章线性表答案

第2章线性表答案内容摘要：

数据不同时才并入链表。 其核心语句段如下。 pa=L1next。 pb=L2next。 ∥ pa、 pb是两链表的工作指针。 pc=L1。 ∥ L1作结果链表的头指针。 while(paamp。 amp。 pb) if(padatapbdata) {u=pa。 pa=panext。 free(u)。 }∥删除 L1表多余元素 else if (padatapbdata) pb=pbnext。 ∥ pb指针后移 else ∥处理交集元素 {if(pc==L1) {pcnext=pa。 pc=pa。 pa=panext。 } ∥处理第一个相等的元素。 else if(pcdata==padata){ u=pa。 pa=panext。 free(u)。 } ∥重复元素不进入 L1表。 else{ pcnext=pa。 pc=pa。 pa=panext。 } ∥交集元素并入结果表。 } ∥ while while(pa) {u=pa。 pa=panext。 free(u)。 } ∥ 删 L1表剩余元素 pcnext=null。 ∥置结果链表尾。 注： 本算法中对 L2表未作释放空间的处理。 （ 4） 本题与上面（ 3）算法相同，只是结果表要另辟空间。 （ 5） [题目分析 ]本题首先求 B和 C的交集，即求 B和 C中共有元素，再与 A求并集，同时删除重复元素，以保持结果 A递增。 LinkedList union(LinkedList A,B,C) ∥ A,B和 C均是带头结点的递增有序的单链表，本算法实现 A= A∪（ B∩ C），使求解结构保 持递增有序。 {pa=Anext。 pb=Bnext。 pc=Cnext。 ∥设置三个工作指针。 pre=A。 ∥ pre指向结果链表中当前待合并结点的前驱。 if(padatapbdata||padatapcdata)∥ A 中第一个元素为结果表的第一元素。 {prenext=pa。 pre=pa。 pa=panext。 } else{while(pbamp。 amp。 pc) ∥找 B表和 C表中第一个公共元素。 if(pbdatapcdata)pb=pbnext。 else if(pbdatapcdata)pc=pcnext。 else break。 ∥找到 B表和 C表的共同元素就退出 while 循环。 if(pbamp。 amp。 pc)∥ 因共同元素而非 B表或 C表空而退出上面 while 循环。 if(padatapbdata)∥ A表当前元素值大于 B表和 C表的公共元素，先将 B表元素链入。 {prenext=pb。 pre=pb。 pb=pbnext。 pc=pcnext。 }∥ B， C公共元素为结果表第一元素。 }∥结束了结果表中第一元素的确定 while(paamp。 amp。 pbamp。 amp。 pc) {while(pbamp。 amp。 pc) if(pbdatapcdata) pb=pbnext。 else if(pbdatapcdata) pc=pcnext。 else break。 ∥ B表和 C表有公共元素。 if(pbamp。 amp。 pc) {while(paamp。 amp。 padatapbdata) ∥先将 A中小于 B， C公共元素部分链入。 {prenext=pa。 pre=pa。 pa=panext。 } if(predata!=pbdata){prenext=pb。 pre=pb。 pb=pbnext。 pc=pcnext。 } else{pb=pbnext。 pc=pcnext。 }∥ 若 A中已有 B， C公共元素，则不再存入结果表。 } }∥ while(paamp。 amp。 pbamp。 amp。 pc) if(pa) prenext=pa。 ∥当 B， C无公共元素（即一个表已空），将 A中剩余链入。 }∥算法 Union结束 [算法讨论 ]本算法先找结果链表的第一个元素，这是因为题目要求结果表要递增有序（即删除重复元素）。 这就要求当前待合并到结果表的元素要与其前驱比较。 由于初始 pre=A（头结点的头指针），这时的 data域无意义，不能与后继比较元素大小，因此就需要确定第一个元素。 当然，不要这样作，而直接进入下面循环也可以，但在链入结点时，必须先判断pre是否等于 A，这占用了过多的时间。 因此先将第一结点链入是可取的。 算法中的 第二个问题是要求时间复杂度为 O（ |A|+|B|+|C|）。 这就要求各个表的工作指针只能后移（即不能每次都从头指针开始查找）。 本算法满足这一要求。 最后一个问题是，当 B， C有一表为空（即 B和 C已无公共元素时），要将 A的剩余部分链入结果表。 3． [题目分析 ]循环单链表 L1和 L2数据结点个数分别为 m和 n ，将二者合成一个循环单链表时，需要将一个循环链表的结点（从第一元素结点到最后一个结点）插入到另一循环链表的第一元素结点前即可。 题目要求“用最快速度将两表合并“，因此应找结点个数少的链表查其尾结点。 LinkedList Union(LinkedList L1,L2。 int m,n) ∥ L1和 L2分别是两循环单链表的头结点的指针， m和 n分别是 L1和 L2的长度。 ∥本算法用最快速度将 L1和 L2合并成一个循环单链表。 {if(m0||n0) {printf(“表长输入错误 \n” )； exit(0)。 } if(mn) ∥若 mn，则查 L1循环单链表的最后一个结点。 {if(m==0)return(L2)。 ∥ L1为空表。 else{p=L1。 while(pnext!=L1) p=pnext。 ∥查最后一个元素结点。 pnext=L2next。 ∥将 L1 循环单链表的元素结点插入到 L2 的第一元素结点前。 L2next=L1next。 free(L1)。 ∥释放无用头结点。 } }∥处理完 mn情况 else∥ 下面处理 L2长度小于等于 L1的情况 {if(n==0)return(L1)。 ∥ L2为空表。 else{p=L2。 while(pnext!=L2) p=pnext。 ∥查最后元素结点。 pnext=L1next。 ∥将 L2的元素结点插入到 L1 循环单链表的第一元素结点前。 L1next=L2next。 free(L2)。 ∥释放无用头结点。 } }∥算法结束。 类似本题叙述的其它题解答如下： （ 1） [题目分析 ]本题将线性表 la和 lb连接，要求时间复杂度为 O（ 1），且占用辅助空间尽量小。 应该使用只设尾指针的单循环链表。 LinkedList Union(LinkedList la,lb) ∥ la和 lb是两个无头结点的循环单链表的尾指针，本算法将 lb接在 la后，成为一个单循环链表。 { q=lanext。 ∥ q指向 la的第一个元素结点。 lanext=lbnext。 ∥将 lb的最后元素结点接到 lb 的第一元素。 lbnext=q。 ∥将 lb指向 la的第一元素结点，实现了 lb接在 la后。 return(lb)。 ∥返回结果单循环链表的尾指针 lb。 }∥算法结束。 [算法讨论 ]若循环单链表带有头结点，则相应算法片段如下： q=lbnext。 ∥ q指向 lb的头结点； lbnext=lanext。 ∥ lb的后继结点为 la的头结点。 lanext=qnext。 ∥ la的后继结点为 lb的第一元素结点。 free(q)。 ∥释放 lb的头结点 return(lb)。 ∥返回结果单循环链表的尾指针 lb。 （ 2） [题目分析 ]本题要求将单向链表 ha和单向循环链表 hb合 并成一个单向链表，要求算法所需时间与链表长度无关，只有使用带尾指针的循环单链表，这样最容易找到链表的首、尾结点，将该结点序列插入到单向链表第一元素之前即可。 其核心算法片段如下（设两链表均有头结点） q=hbnext。 ∥单向循环链表的表头指针 hbnext=hanext。 ∥将循环单链表最后元素结点接在 ha 第一元素前。 hanext=qnext。 ∥将指向原单链表第一元素的指针指向循环单链表第一结点 free(q)。 ∥释放循环链表头结点。 若两链表均不带头结点，则算法片段如下： q=hbnext。 ∥ q指向 hb首元结点。 hbnext=ha。 ∥ hb尾结点的后继是 ha第一元素结点。 ha=q。 ∥头指针指向 hb的首元结点。 4． [题目分析 ]顺序存储结构的线性表的插入，其时间复杂度为 O（ n），平均移动近一半的元素。 线性表 LA和 LB合并时，若从 第一个元素开始，一定会造成元素后移，这不符合本题“高效算法”的要求。 另外，题中叙述“线性表空间足够大”也暗示出另外合并方式，即应从线性表的最后一个元素开始比较，大者放到最终位置上。 设两线性表的长度各为 m和 n ，则结果表的最后一个元素应在 m+n位置上。 这样从后向前，直到第一个元素为止。 PROC Union(VAR LA:SeqList。 LB:SeqList) ∥ LA和 LB是顺序存储的非递减有序线性表，本算法将 LB合并到 LA中，元素仍非递减有序。 m:=。 n:=。 ∥ m， n分别为线性表 LA和 LB的长度。 k:=m+n。 ∥ k为结果线性表的工作指针（下标）。 i:=m。 j:=n。 ∥ i， j分别为线性表 LA和 LB的工作指针（下标）。 WHILE(i0)AND(j0)DO IF [i]=[j] THEN[[k]:=[i]。 k:=k1。 i:=i1。 ] ELSE[[k]:=[j]。 k:=k1。 j:=j1。 ] WHILE(j0) DO [[k]:=[j]。 k:=k1。 j:=j1。 ] :=m+n。 ENDP。 [算法讨论 ]算法中数据移动是主要操作。 在最佳情况下（ LB的最小元素大于 LA的最大元素），仅将 LB的 n个元素移（拷贝）到 LA中，时间复杂度为 O（ n），最差情况， LA的所有元素都要移动，时间复杂度为 O（ m+n）。 因数据合并到 LA 中，所以在退出第一个 WHILE循环后，只需要一 个 WHILE循环，处理 LB中剩余元素。 第二个循环只有在 LB有剩余元素时才执行，而在 LA有剩余元素时不执行。 本算法利用了题目中“线性表空间足够大”的条件，“最大限度的避免移动元素”，是“一种高效算法”。 5． [题目分析 ]本题实质上是一个排序问题，要求“不得使用除该链表结点以外的任何链结点空间”。 链表上的排序采用直接插入排序比较方便，即首先假定第一个结点有序，然后，从第二个结点开始，依次插入到前面有序链表中，最终达到整个链表有序。 LinkedList LinkListSort(LinkedList list) ∥ list是不带头结点的线性链表，链表结点构造为 data和 link两个域， data 是数据域， link是指针域。 本算法将该链表按结点数据域的值的大小，从小到大重新链接。 {p=listlink。 ∥ p是工作指针，指向待排序的当前元素。 listlink=null。 ∥假定第一个元素有序，即链表中现只有一个结点。 while(p!=null) {r=plink。 ∥ r是 p的后继。 q=list。 if(qdatapdata)∥处理待排序结点 p比第一个元素结点小的情况。 {plink=list。