数据结构考研复习题--第二章--线性表(带答案) 下载本文

链入结果表。

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->datadata)q=q->link; p->link=q->link;∥将当前排序结点链入有序链表中。 q->link=p; }

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->datadata)q=q->link; p->link=q->link; q->link=p;

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->datadata)q=q->next;∥查找插入位置。 p->next=q->next;∥将p结点链入链表。 q->next=p; p=r; }

与本题有类似叙述的题的解答:

(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 ∥查找插入位置。

IF pre^.NEXT^.DATA