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

p->next=la->next;/*将p结点前插入头结点后。*/ la->next=p;p=r; }

}∥结束算法

(3)本题要求倒排循环链表,与上面倒排单链表处理不同之处有二:一是初始化成循环链表而不是空链表;二是判断链表尾不用空指针而用是否是链表头指针。算法中语句片段如下:

p=la->next; ∥p为工作指针。

la->next=la; ∥初始化成空循环链表。 while(p!=la) ∥当p=la时循环结束。 {r=p->next; ∥暂存p的后继结点 p->next=la->next;∥逆置 la->next=p; p=r; }

(4)不带头结点的单链表逆置比较复杂,解决方法可以给加上头结点:

la=(LinkedList)malloc(sizeof(node)); la->next=L;

之后进行如上面(2)那样的逆置,最后再删去头结点: L=la->next; ∥L是不带头结点的链表的指针。 free(la); ∥释放头结点。

若不增加头结点,可用如下语句片段: p=L->next; ∥p为工作指针。

L->next=null;∥第一结点成为尾结点。 while(p!=null) {r=p->next;

p->next=L;∥将p结点插到L结点前面。

L=p; ∥L指向新的链表“第一”元素结点。 p=r; } (5)同(4),只是叙述有异。 (6)同(2),差别仅在于叙述不同。

22.[题目分析] 在无序的单链表上,查找最小值结点,要查遍整个链表,初始假定第一结点是最小值结点。当找到最小值结点后,判断数据域的值是否是奇数,若是,则“与其后继结点的值相交换”即仅仅交换数据域的值,用三个赋值语句即可交换。若与后继结点交换位置,则需交换指针,这时应知道最小值结点的前驱。至于删除后继结点,则通过修改最小值结点的指针域即可。

[算法设计]

void MiniValue(LinkedList la)

∥la是数据域为正整数且无序的单链表,本算法查找最小值结点且打印。若最小值结点的数值是奇数,则与后继结点值交换;否则,就删除其直接后继结点。

{p=la->next; ∥设la是头结点的头指针,p为工作指针。

pre=p; ∥pre指向最小值结点,初始假定首元结点值最小。 while(p->next!=null) ∥p->next是待比较的当前结点。 {if(p->next->datadata)pre=p->next;

p=p->next; ∥后移指针

}

printf(“最小值=%d\\n”,pre->data); if(pre->data%2!=0) ∥处理奇数

if(pre->next!=null)∥若该结点没有后继,则不必交换

{t= pre->data;pre->data=pre->next->data;pre->next->data=t;}∥交换完毕

else∥处理偶数情况

if(pre->next!=null)∥若最小值结点是最后一个结点,则无后继 {u=pre->next;pre->next=u->next;free(u);} ∥释放后继结点空间

23.[题目分析] 将一个结点数据域为字符的单链表,分解成含有字母字符、数字字符和其它字符的三个循环链表,首先要构造分别含有这三类字符的表头结点。然后从原链表第一个结点开始,根据结点数据域是字母字符、数字字符和其它字符而分别插入到三个链表之一的链表。注意不要因结点插入新建链表而使原链表断链。另外,题目并未要求链表有序,插入采用“前插法”,每次插入的结点均成为所插入链表的第一元素的结点即可。

void OneToThree(LinkedList L,la,ld,lo)

∥L是无头结点的单链表第一个结点的指针,链表中的数据域存放字符。本算法将链表L分解成含有英文字母字符、数字字符和其它字符的带头结点的三个循环链表。

{la=(LinkedList)malloc(sizeof(LNode)); ∥建立三个链表的头结点 ld=(LinkedList)malloc(sizeof(LNode));

lo=(LinkedList)malloc(sizeof(LNode));

la->next=la;ld->next=ld;lo->next=lo;∥置三个循环链表为空表 while(L!=null)∥分解原链表。

{r=L; L=L->next; ∥L指向待处理结点的后继

if(r->data>=‘a’&& r->data<=‘z’|| r->data>=‘A’&& r->data<=‘Z’) {r->next=la->next; la->next=r;} ∥处理字母字符。 else if(r->data>=‘0’&& r->data<=‘9’)

{r->next=ld->next;ld->next=r;} ∥处理数字字符 else {r->next=lo->next;lo->next=r;} ∥处理其它符号。

}∥结束while(L!=null)。

}∥算法结束

[算法讨论] 算法中对L链表中每个结点只处理一次,时间复杂度O(n),只增加了必须的三个表头结点,符合题目“用最少的时间和最少的空间”的要求。

24.[题目分析] 在递增有序的线性表中,删除数值相同的元素,要知道被删除元素结点的前驱结点。

LinkedList DelSame(LinkedList la)

∥la是递增有序的单链表,本算法去掉数值相同的元素,使表中不再有重复的元素。 {pre=la->next;∥pre是p所指向的前驱结点的指针。

p=pre->next;∥p是工作指针。设链表中至少有一个结点。 while(p!=null)

if(p->data==pre->data) ∥处理相同元素值的结点 {u=p;p=p->next;free(u);} ∥释放相同元素值的结点

else {pre->next=p;pre=p;p=p->next;} ∥处理前驱,后继元素值不同 pre->next=p;∥置链表尾。 }∥DelSame