发布时间 : 星期一 文章数据结构考研复习题--第二章--线性表（带答案）更新完毕开始阅读51301d7bddccda38376baf2b
链入结果表。
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．[题目分析]本题实质上是一个排序问题，要求“不得使用除该链表结点以外的任何链结点空间”。链表上的排序采用直接插入排序比较方便，即首先假定第一个结点有序，然后，从第二个结点开始，依次插入到前面有序链表中，最终达到整个链表有序。 LinkedList LinkListSort(LinkedList list) ∥list是不带头结点的线性链表，链表结点构造为data和link两个域，data是数据 域，link是指针域。本算法将该链表按结点数据域的值的大小，从小到大重新链接。 {p=list->link; ∥p是工作指针，指向待排序的当前元素。 list->link=null;∥假定第一个元素有序，即链表中现只有一个结点。 while(p!=null) {r=p->link; ∥r是p的后继。 q=list; if(q->data>p->data)∥处理待排序结点p比第一个元素结点小的情况。 {p->link=list; list=p;∥链表指针指向最小元素。 } else∥查找元素值最小的结点。 {while(q->link!=null&&q->link->data p=r;∥p指向下个待排序结点。 } } [算法讨论]算法时间复杂度的分析与用顺序存储结构时的情况相同。但顺序存储结构将第i(i>1)个元素插入到前面第1至第i-1个元素的有序表时，是将第i个元素先与第i-1个元素比较。而在链表最佳情况均是和第一元素比较。两种存储结构下最佳和最差情况的比较次数相同，在链表情况下，不移动元素，而是修改结点指针。 另一说明是，本题中线性链表list不带头结点，而且要求“不得使用除该链表以外的任何链结点空间“，所以处理复杂，需要考虑当前结点元素值比有序链表第一结点的元素值还小的情况，这时要修改链表指针list。如果list是头结点的指针，则相应处理要简单些，其算法片段如下： p=list->link;∥p指向第一元素结点。 list->link=null;∥有序链表初始化为空 while(p!=null) {r=p->link;∥保存后继 q=list; while(q->link!=null && q->link->data q=r; } 6．[题目分析]本题明确指出单链表带头结点，其结点数据是正整数且不相同，要求利用直接插入原则把链表整理成递增有序链表。这就要求从第二结点开释，将各结点依次插入到有序链表中。 LinkedList LinkListInsertSort(LinkedList la) ∥la是带头结点的单链表，其数据域是正整数。本算法利用直接插入原则将链表整理成递增的有序链表。 {if(la->next!=null)∥链表不为空表。 {p=la->next->next;∥p指向第一结点的后继。 la->next->next=null;∥直接插入原则认为第一元素有序，然后从第二元素起依次插 入。 while(p!=null) {r=p->next;∥暂存p的后继。 q=la; while(q->next!=null&&q->next->data 与本题有类似叙述的题的解答： （1）本题也是链表排序问题，虽没象上题那样明确要求“利用直接插入的原则”来排序，仍可用上述算法求解，这里不再赘述。 7．[题目分析]本题要求将一个链表分解成两个链表，两个链表都要有序，两链表建立过程中不得使用NEW过程申请空间，这就是要利用原链表空间，随着原链表的分解，新建链表随之排序。 PROC discreat(VAR listhead,P,Q:linkedlist) ∥listhead是单链表的头指针，链表中每个结点由一个整数域DATA和指针域NEXT组成。本算法将链表listhead分解成奇数链表和偶数链表，分解由P和Q指向，且P和Q链表是有序的。 P:=NIL;Q:=NIL;∥P和Q链表初始化为空表。 s:=listhead; WHILE(s<>NIL)DO [r:=s^.NEXT; ∥暂存s的后继。 IF s^.DATA DIV 2=0 ∥处理偶数。 THEN IF P=NIL THEN[P:=s;P^.NEXT:=NIL;] ∥第一个偶数链结点。 ELSE[pre:=P; IF pre^.DATA>s^.DATA THEN[s^.NEXT:=pre;P:=s;∥插入当前最小值结 点修改头指针] ELSE[WHILE pre^.NEXT<>NIL DO IF pre^.NEXT^.DATA s^.NEXT:=pre^.NEXT; ∥链入此结点。 pre^.NEXT:=s; ] ] ELSE∥处理奇数链。 IF Q=NIL THEN[Q:=s;Q^.NEXT:=NIL;] ∥第一奇数链结点。 ELSE[pre:=Q; IF pre^.DATA>s^.DATA THEN[s^.NEXT:=pre; Q:=s; ]∥修改头指针。 ELSE[WHILE pre^.NEXT<>NIL DO ∥查找插入位置。