第二章 线性表(15)

址”，克服了C语言函数传递只是“值传递”的缺点。

25．已知非空线性链表由list指出，链结点的构造为（data,link）.请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。

【北京航空航天大学 2001 四（10分）】

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

∥list是非空线性链表，链结点结构是（data，link），data是数据域，link是链域

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

pre=list； ∥pre指向链表中数据域最小值结点的前驱

q=p； ∥q指向数据域最小值结点，初始假定是第一结点 while （p->link）

{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。 26．已知两个单链表A和B,其头指针分别为heada和headb，编写一个过程从单链表A中删除自第i个元素起的共len个元素，然后将单链表A插入到单链表B的第j个元素之前。

【中国矿业大学 2000 三（10分）】

[题目分析] 在单链表中删除自第i个元素起的共len个元素，应从第1个元素起开始计数，记到第i个时开始数len个，然后将第i-1个元素的后继指针指向第i+len个结点，实现了在A链表中删除自第i个起的len个结点。这时应继续查到A的尾结点，得到删除元素后的A链表。再查B链表的第j个元素，将A链表插入之。插入和删除中应注意前驱后继关系，不能使链表“断链”。另外，算法中应判断i，len和j的合法性。

LinkedList DelInsert（LinkedList heada，headb，int i，j，len）

∥本算法删除heada链表自第i个元素起len个元素，再将heada插入到headb的第j个元素之前

{if（i<1 || len<0 || j<1）{printf（“参数错误\\n”）；exit（0）；}∥参数错，退出算法。

p=heada；∥p为链表A的工作指针，初始为A的头指针，查到第i个元素时，p

46

指向第i-1个元素 k=0；∥计数

while（p!=null && knext；}

if（p==null）{printf（“给的%d太大\\n”,i）；exit（0）；} ∥i太大，退出算法

q=p->next；∥q为工作指针，初始指向A链表第一个被删结点 k=0；

while（q!=null && knext；free（u）；} ∥删除结点，后移指针

if（knext=q；∥A链表删除了len个元素，但未释放空间

if(heada->next!=null) ∥heada->next==null说明链表中结点均已删除，无需往B表插入

{while（p->next!=null）p=p->next；∥找A的尾结点 q=headb；∥q为链表B的工作指针 k=0； ∥计数

while（q!=null && k

{k++；q=q->next；} ∥查找成功时，q指向第j-1个结点 if（q==null）{printf（“给的%d太大\\n”,j）；exit（0）；} p->next=q->next； ∥将A链表链入

q->next=heada->next； ∥A的第一元素结点链在B的第j-1个结点之后 }∥if

free（heada）；∥释放A表头结点 }∥算法结束

27．L1与L2分别为两单链表头结点地址指针，且两表中数据结点的数据域均为一个字母。设计把L1中与L2中数据相同的连续结点顺序完全倒置的算法。【东北大学1997四(15分)】

[题目分析] 本题也是模式匹配问题，应先找出链表L2在链表L1中的出现，然后将L1中的L2倒置过来。设L2在L1中出现时第一个字母结点的前驱的指针为p，最后一个字母结点在L1中为q所指结点的前驱，则在保存p后继结点指针(s)的情况下，执行p->next=q。之后将s到q结点的前驱依次插入到p结点之后，实现了L2在L1中的倒置。

LinkedList PatternInvert（LinkedList L1，L2）

∥L1和L2均是带头结点的单链表，本算法将L1中与L2中数据域相同的连续结点的顺序倒置过来

{p=L1； ∥p是每趟匹配时L1中的起始结点前驱的指针 q=L1->next； ∥q是L1中的工作指针

47

s=L2->next； ∥s是L2中的工作指针 while（p!=null && s!=null）

if（q->data==s->data）{q=q->next;s=s->next;} ∥对应字母相等，指针后移 else {p=p->next；q=p->next；s=L2->next；} ∥失配时,L1起始结点后移,L2从首结点开始

if（s==null）∥匹配成功，这时p为L1中与L2中首字母结点相同数据域结点的前驱

∥q为L1中与L2最后一个结点相同数据域结点的后继

{r=p->next； ∥r为L1的工作指针，初始指向匹配的首字母结点

p->next=q； ∥将p与q结点的链接 while（r!=q）； ∥逐结点倒置 {s=r->next； ∥暂存r的后继

r->next=p->next；∥将r所指结点倒置 p->next=r；r=s； ∥恢复r为当前结点 } }

else printf（“L2并未在L1中出现”）； } ∥算法结束。

[算法讨论] 本算法只讨论了L2在L1至多出现一次（可能没出现），没考虑在L1中多次出现的情况。若考虑多次出现，可在上面算法找到第一次出现后的q结点作L1中下次比较的第一字母结点，读者可自行完善之。 28．请设计算法将不带头结点的单链表就地逆置。【北方交通大学 2001 三（12分）】

[题目分析]不带头结点的单链表逆置比较复杂，解决方法可以给加上头结点： head=（LinkedList）malloc（sizeof（node））； head->next=la；∥设无头结点的单链表是la 之后进行如上面那样的逆置，最后再删去头结点： la=head->next； ∥la是不带头结点的链表的指针 free（head）； ∥释放头结点 若不增加头结点，可用如下算法：

LinkedList invertcycl(LinkedList la） ∥将无头结点的单链表la逆置 {p=la->next； ∥p为工作指针,设单链表非空 la->next=null；∥第一结点成为尾结点 while（p!=null） {r=p->next；

p->next=la；∥将p结点插到L结点前面

la=p； ∥L指向新的链表“第一”元素结点 p=r； }

return la; }

29．设有一个由正整数组成的无序（向后）单链表，编写完成下列功能的算法： 找出最小值结点，且打印该数值； …… 此处隐藏：1383字，全部文档内容请下载后查看。喜欢就下载吧 ……