发布时间 : 星期五 文章数据结构考研复习题--第二章--线性表（带答案）更新完毕开始阅读51301d7bddccda38376baf2b
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->data
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