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

]∥结束奇数链结点

s:=r;∥s指向新的待排序结点。 ]∥结束“WHILE(s<>NIL)DO” ENDP;∥结束整个算法。 [算法讨论]由于算法要求“不得使用NEW过程申请空间,也没明确指出链表具有头结点,所以上述算法复杂些,它可能需要在第一个结点前插入新结点,即链表的头指针会发生变化。如有头结点,算法不必单独处理在第一个结点前插入结点情况,算法会规范统一,下面的(1)是处理带头结点的例子。算法中偶数链上结点是靠数据整除2等于0(DATA DIV 2=0)判断的。

类似本题的其它题解答如下:

(1)[题目分析]本题基本类似于上面第7题,不同之处有二。一是带头结点,二是分解后的两个链表,一个是数据值小于0,另一个是数据值大于0。由于没明确要求用类PASCAL书写算法,故用C书写如下。

void DisCreat1(LinkedList A)

∥A是带头结点的单链表,链表中结点的数据类型为整型。本算法将A分解成两个单链表B和C,B中结点的数据小于零,C中结点的数据大于零。 {B=A;

C=(LinkedList )malloc(sizeof(LNode));∥为C申请结点空间。 C->next=null ∥C初始化为空表。 p=A->next; ∥p为工作指针。 B->next=null; ∥B表初始化。 while(p!=null)

{r=p->next; ∥暂存p的后继。

if (p->data<0)∥小于0的放入B表。

{p->next=B->next; B->next=p; }∥将小于0的结点链入B表。 else {p->next=C->next; C->next=p; } p=r;∥p指向新的待处理结点。 }

}∥算法结束。

[算法讨论]因为本题并未要求链表中结点的数据值有序,所以算法中采取最简单方式:将新结点前插到头结点后面(即第一元素之前)。 (2) 本题同上面第7题,除个别叙述不同外,本质上完全相同,故不再另作解答。

(3)[题目分析]本题中的链表有头结点,分解成表A和表B,均带头结点。分解后的A表含有原表中序号为奇数的元素,B表含有原A表中序号为偶数的元素。由于要求分解后两表中元素结点的相对顺序不变,故采用在链表尾插入比较方便,这使用一指向表尾的指针即可方便实现。

void DisCreat3(LinkedList A)

∥A是带头结点的单链表,本算法将其分解成两个带头结点的单链表,A表中含原表中序号为奇数

∥的结点,B表中含原表中序号为偶数的结点。链表中结点的相对顺序同原链表。 {i=0;∥i记链表中结点的序号。

B=(LinkedList)malloc(sizeof(LNode);∥创建B表表头。 B->next=null; ∥B表的初始化。

LinkedList ra,rb;∥ra和rb将分别指向将创建的A表和B表的尾结点。

ra=A;rb=B;

p=A->next; ∥p为链表工作指针,指向待分解的结点。 A->next=null; ∥置空新的A表 while(p!=null)

{r=p->next; ∥暂存p的后继。 i++;

if(i%2==0) ∥处理原序号为偶数的链表结点。

{p->next=rb->next;∥在B表尾插入新结点; rb->next=p; rb=p;∥rb指向新的尾结点; }

else∥处理原序号为奇数的结点。

{p->next=ra->next; ra->next=p; ra=p; }

p=r; ∥将p恢复为指向新的待处理结点。 }∥算法结束

8.[题目分析]题目要求重排n个元素且以顺序存储结构存储的线性表,使得所有值为负数的元素移到正数元素的前面。这可采用快速排序的思想来实现,只是提出暂存的第一个元素(枢轴)并不作为以后的比较标准,比较的标准是元素是否为负数。 int Rearrange(SeqList a; int n)

∥a是具有n个元素的线性表,以顺序存储结构存储,线性表的元素是整数。本算法重

排线性表a,

∥使所有值为负数的元素移到所有值为正数的数的前面。 {i=0; j=n-1; ∥ i,j为工作指针(下标),初始指向线性表a的第1个和第n个元

素。

t=a[0]; ∥暂存枢轴元素。 while(i

{while(i=0) j--; ∥ 若当前元素为大于等于零,则指针前移。 if(i

while(i

a[i]=t; ∥将原第一元素放到最终位置。 }

[算法讨论] 本算法时间复杂度为O(n)。算法只是按题目要求把正负数分开,如要求统计负数和大于等于零的个数,则最后以t来定。如t为负数,则0至i共i+1个负数,n-1-i个正数(包括零)。另外,题目并未提及零的问题,笔者将零放到正数一边。对此问题的扩充是若元素包含正数、负数和零,并要求按负数、零、正数的顺序重排线性表,统计负数、零、正数的个数。请读者利用上面解题思想自行解答。 类似本题的选了5 个题,其解答如下:

(1)与上面第8题不同的是,这里要求以an为参考元素,将线性表分成左右两部分。左半部分的元素都小于等于an,右半部分的元素都大于an,an位于分界位置上。其算法主要片段语句如下:

i=1;j=n;

t=a[n]; ∥暂存参考元素。 while(i

{while(i

while(it) j--; ∥当前元素大于参考元素时指针前移。 if(i

a[i]=t; ∥参考元素置于分界位置。

(2) [题目分析]本题要求将线性表A分成B和C两个表,表B和表C不另占空间,而是利用表A的空间,其算法与第8题相同。这里仅把表B和表C另设空间的算法解答如下: void Rearrange2(int A[],B[],C[])

∥线性表A有n个整型元素,顺序存储。本算法将A拆成B和C 两个表,B中存放

大于

∥等于零的元素,C中存放小于零的元素。

{i=0; ∥i,j,k是工作指针,分别指向A、B和C表的当前元素。 j=k=-1; ∥j,k初始化为-1。 while(i

{if(A[i]<0) C[++k]=A[i++]; ∥将小于零的元素放入C表。 else B[++j]=A[i++]; ∥将大于零的元素放入B表。

[算法讨论]本题用一维数组存储线性表,结果线性表B和C中分别有j+1和k+1个元素。若采用教材中的线性表,则元素的表示作相应改变,例如A.elem[i],而最后B和C表应置上表的长度,如B.length=j和C.length=k。

(3) 本题与第8题本质上相同,第8题要求分开正数和负数,这里要求分开奇数和偶数,判别方式是a[i]%2==0,满足时为偶数,反之为奇数。 (4) 本题与第8题相同,只是叙述不同。

(5) 本题与第8题基本相同,不同之处在于这里的分界元素是整数19(链表中并不要

求一定有19)。本题要求用标准pascal描述算法,如下所示。 TYPE arr=ARRAY[1..1000] OF integer; VAR a:arr;

PROCEDURE Rearrange5(VAR a:arr);

∥a是n(设n=1000)个整数组成的线性表,用一维数组存储。本算法将n个元素

中所有大于等于19的整数放在所有小于19的整数之后。

VAR i,j,t:integer; BEGIN

i:=1;j:=n;t:=a[1] ;∥i,j指示顺序表的首尾元素的下标,t暂存分界元素 WHILE(i

WHILE (i=19) DO j:=j-1;

IF(i

IF(i

[算法讨论] 分界元素t放入a[i],而不论它的值如何。算法中只用了一个t中间变量,符合空间复杂度O(1)的要求。算法也满足时间复杂度O(n)的要求。

9.[题目分析] 本题要求在单链表中删除最小值结点。单链表中删除结点,为使结点删除后不出现“断链”,应知道被删结点的前驱。而“最小值结点”是在遍历整个链表后才能知道。所以算法应首先遍历链表,求得最小值结点及其前驱。遍历结束后再执行删除操作。

LinkedList Delete(LinkedList L)

∥L是带头结点的单链表,本算法删除其最小值结点。

{p=L->next; ∥p为工作指针。指向待处理的结点。假定链表非空。 pre=L; ∥pre指向最小值结点的前驱。

q=p; ∥q指向最小值结点,初始假定第一元素结点是最小值结点。 while(p->next!=null)

{if(p->next->datadata){pre=p;q=p->next;} ∥查最小值结点 p=p->next; ∥指针后移。 }

pre->next=q->next;∥从链表上删除最小值结点 free(q); ∥释放最小值结点空间 }∥结束算法delete。

[算法讨论] 算法中函数头是按本教材类C描述语言书写的。原题中void delete(linklist &L),是按C++的“引用”来写的,目的是实现变量的“传址”,克服了C语言函数传递只是“值传递”的缺点。

10.[题目分析] 本题要求将链表中数据域值最小的结点移到链表的最前面。首先要查找最小值结点。将其移到链表最前面,实质上是将该结点从链表上摘下(不是删除并回收空间),再插入到链表的最前面。

LinkedList delinsert(LinkedList list)

∥list是非空线性链表,链结点结构是(data,link),data是数据域,link是链域。

∥本算法将链表中数据域值最小的那个结点移到链表的最前面。 {p=list->link;∥p是链表的工作指针

pre=list; ∥pre指向链表中数据域最小值结点的前驱。 q=p; ∥q指向数据域最小值结点,初始假定是第一结点 while (p->link!=null)

{if(p->link->datadata){pre=p;q=p->link;} ∥找到新的最小值结点; p=p->link; }

if (q!=list->link) ∥若最小值是第一元素结点,则不需再操作 {pre->link=q->link; ∥将最小值结点从链表上摘下; q->link= list->link;∥将q结点插到链表最前面。 list->link=q;

}

}∥算法结束

[算法讨论] 算法中假定list带有头结点,否则,插入操作变为q->link=list;list=q。 11.[题目分析] 知道双向循环链表中的一个结点,与前驱交换涉及到四个结点(p结点,前驱结点,前驱的前驱结点,后继结点)六条链。

void Exchange(LinkedList p)

∥p是双向循环链表中的一个结点,本算法将p所指结点与其前驱结点交换。 {q=p->llink;