发布时间 : 星期四 文章最完整的数据结构1800题含答案更新完毕开始阅读
pc=ha;∥pc为结果链表当前结点的前驱指针。 while(pa&&pb)
if(pa->data
{pc->next=pa;pc=pa;pa=pa->next;} else if(pa->data>pb->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;∥ 若ha表未空，则链入结果表。 else pc->next=pb;∥若hb表未空，则链入结果表。 free(hb); ∥释放hb头结点 return(ha);
}∥算法Union结束。
与本题类似的其它几个题解答如下： (1) 解答完全同上2。
(2) 本题是求交集，即只有同时出现在两集合中的元素才出现在结果表中。其核心语句段如下：
pa=la->next;pb=lb->next;∥设工作指针pa和pb； pc=la;∥结果表中当前合并结点的前驱的指针。 while(pa&&pb)
if(pa->data==pb->data)∥交集并入结果表中。 { pc->next=pa;pc=pa;pa=pa->next;
u=pb;pb=pb->next;free(u);}
else if(pa->data
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(lb); ∥注： 本算法中也可对B表不作释放空间的处理
（3）本题基本与（2）相同，但要求无重复元素，故在算法中，待合并结点数据要与其前驱比较，只有在与前驱数据不同时才并入链表。其核心语句段如下。 pa=L1->next;pb=L2->next;∥pa、pb是两链表的工作指针。 pc=L1;∥L1作结果链表的头指针。 while(pa&&pb)
if(pa->data
{if(pc==L1) {pc->next=pa;pc=pa;pa=pa->next;} ∥处理第一个相等的元
素。
else if(pc->data==pa->data){ u=pa;pa=pa->next;free(u);} ∥重复元
素不进入L1表。
else{ pc->next=pa;pc=pa;pa=pa->next;} ∥交集元素并入结果表。
} ∥while
while(pa) {u=pa;pa=pa->next;free(u);} ∥ 删L1表剩余元素
pc->next=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=A->next;pb=B->next;pc=C->next;∥设置三个工作指针。 pre=A; ∥pre指向结果链表中当前待合并结点的前驱。
if(pa->data
{pre->next=pa;pre=pa;pa=pa->next;}
else{while(pb&&pc) ∥找B表和C表中第一个公共元素。 if(pb->data
else if(pb->data>pc->data)pc=pc->next;
else break; ∥找到B表和C表的共同元素就退出while循环。 if(pb&&pc)∥ 因共同元素而非B表或C表空而退出上面while循环。 if(pa->data>pb->data)∥A表当前元素值大于B表和C表的公共元素，先将B
表元素链入。
{pre->next=pb;pre=pb;pb=pb->next;pc=pc->next;}∥ B，C公共元素为结果
表第一元素。
}∥结束了结果表中第一元素的确定 while(pa&&pb&&pc) {while(pb&&pc)
if(pb->data
else if(pb->data>pc->data) pc=pc->next; else break; ∥B表和C表有公共元素。 if(pb&&pc)
{while(pa&&pa->data
if(pre->data!=pb->data){pre->next=pb;pre=pb;pb=pb->next;pc=pc->next;} else{pb=pb->next;pc=pc->next;}∥ 若A中已有B，C公共元素，则不再存入结果表。 }
}∥ while(pa&&pb&&pc) if(pa) pre->next=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(m<0||n<0) {printf(“表长输入错误\\n”)；exit(0);}
if(m while(p->next!=L1) p=p->next;∥查最后一个元素结点。 p->next=L2->next;∥将L1循环单链表的元素结点插入到L2的第一元素结点前。 L2->next=L1->next; free(L1);∥释放无用头结点。 } }∥处理完m else∥ 下面处理L2长度小于等于L1的情况 {if(n==0)return(L1);∥L2为空表。 else{p=L2; while(p->next!=L2) p=p->next;∥查最后元素结点。 p->next=L1->next;∥将L2的元素结点插入到L1循环单链表的第一元素结点前。 L1->next=L2->next; free(L2);∥释放无用头结点。 } }∥算法结束。 类似本题叙述的其它题解答如下： （1）[题目分析]本题将线性表la和lb连接，要求时间复杂度为O（1），且占用辅助空间尽量小。应该使用只设尾指针的单循环链表。 LinkedList Union(LinkedList la,lb) ∥la和lb是两个无头结点的循环单链表的尾指针，本算法将lb接在la后，成为一 个单循环链表。 { q=la->next; ∥q指向la的第一个元素结点。 la->next=lb->next; ∥将lb的最后元素结点接到lb的第一元素。 lb->next=q; ∥将lb指向la的第一元素结点，实现了lb接在la后。 return(lb); ∥返回结果单循环链表的尾指针lb。 }∥算法结束。 [算法讨论]若循环单链表带有头结点，则相应算法片段如下： q=lb->next; ∥q指向lb的头结点； lb->next=la->next; ∥lb的后继结点为la的头结点。 la->next=q->next; ∥la的后继结点为lb的第一元素结点。 free(q); ∥释放lb的头结点 return(lb); ∥返回结果单循环链表的尾指针lb。 （2）[题目分析]本题要求将单向链表ha和单向循环链表hb合并成一个单向链表，要求算法所需时间与链表长度无关，只有使用带尾指针的循环单链表，这样最容易找到链表的首、尾结点，将该结点序列插入到单向链表第一元素之前即可。 其核心算法片段如下（设两链表均有头结点） q=hb->next; ∥单向循环链表的表头指针 hb->next=ha->next; ∥将循环单链表最后元素结点接在ha第一元素前。 ha->next=q->next; ∥将指向原单链表第一元素的指针指向循环单链表第一结 点 free(q); ∥释放循环链表头结点。 若两链表均不带头结点，则算法片段如下： q=hb->next; ∥q指向hb首元结点。 hb->next=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:=LA.last;n:=LB.last;∥m，n分别为线性表LA和LB的长度。 k:=m+n; ∥k为结果线性表的工作指针（下标）。 i:=m;j:=n; ∥i，j分别为线性表LA和LB的工作指针（下标）。 WHILE(i>0)AND(j>0)DO IF LA.elem[i]>=LB.elem[j] THEN[LA.elem[k]:=LA.elem[i];k:=k-1;i:=i-1;] ELSE[LA.elem[k]:=LB.elem[j];k:=k-1;j:=j-1;] WHILE(j>0) DO [LA.elem[k]:=LB.elem[j];k:=k-1;j:=j-1;] LA.last:=m+n; ENDP; [算法讨论]算法中数据移动是主要操作。在最佳情况下（LB的最小元素大于LA的最大元素），仅将LB的n个元素移（拷贝）到LA中，时间复杂度为O（n），最差情况，LA的所有元素都要移动，时间复杂度为O（m+n）。因数据合并到LA中，所以在退出第一个WHILE循环后，只需要一个WHILE循环，处理LB中剩余元素。第二个循环只有在LB有剩余元素时才执行，而在LA有剩余元素时不执行。本算法利用了题目中“线性表空间足够大”的条件，“最大限度的避免移动元素”，是“一种高效算法”。 5．[题目分析]本题实质上是一个排序问题，要求“不得使用除该链表结点以外的任何链