发布时间 : 星期四 文章数据结构考研复习题--第二章--线性表（带答案）更新完毕开始阅读51301d7bddccda38376baf2b
∥A和B均是带头结点的递增有序的单链表，分别存储了一个集合，本算法求两集合的差集，存储于单链表A中，*n是结果集合中元素个数，调用时为0
{p=A->next； ∥p和q分别是链表A和B的工作指针。
q=B->next； pre=A； ∥pre为A中p所指结点的前驱结点的指针。 while（p!=null && q!=null）
if（p->data
else {pre->next=p->next； ∥处理A，B中元素值相同的结点，应删除。
u=p； p=p->next； free（u）；} ∥删除结点
18．[题目分析] 本题要求对单链表结点的元素值进行运算，判断元素值是否等于其序号的平方减去其前驱的值。这里主要技术问题是结点的序号和前驱及后继指针的正确指向。 int Judge（LinkedList la）
∥la是结点的元素为整数的单链表。本算法判断从第二结点开始，每个元素值是否等于其序号的平方减去其前驱的值，如是返回true；否则，返回false。 {p=la->next->next；∥p是工作指针，初始指向链表的第二项。 pre=la->next； ∥pre是p所指结点的前驱指针。
i=2； ∥i是la链表中结点的序号，初始值为2。 while（p!=null）
if（p->data==i*i-pre->data）{i++；pre=p；p=p->next；} ∥结点值间的关系符合题目要求
else break； ∥当前结点的值不等于其序号的平方减去前驱的值。
if（p!=null）return（false）； ∥未查到表尾就结束了。 else return（true）； ∥成功返回。 }∥算法结束。
[算法讨论]本题不设头结点也无影响。另外，算法中还可节省前驱指针pre，其算法片段如下：
p=la；∥假设无头结点，初始p指向第一元素结点。 i=2；
while（p->next!=null） ∥初始p->next指向第二项。 if（p->next->data= =i*i-p->data） {i++；p=p->next；}
if（p->next!=null）return（false）；∥失败 else return（true）； ∥成功 19．[题目分析] 本题实质上是一个模式匹配问题，这里匹配的元素是整数而不是字符。因两整数序列已存入两个链表中，操作从两链表的第一个结点开始，若对应数据相等，则后移指针；若对应数据不等，则A链表从上次开始比较结点的后继开始，B链表仍从第一结点开始比较，直到B链表到尾表示匹配成功。A链表到尾B链表未到尾表示失败。操作中应记住A链表每次的开始结点，以便下趟匹配时好从其后继开始。
int Pattern（LinkedList A，B）
∥A和B分别是数据域为整数的单链表，本算法判断B是否是A的子序列。如是，返回1；否则，返回0表示失败。
{p=A； ∥p为A链表的工作指针，本题假定A和B均无头结点。
pre=p； ∥pre记住每趟比较中A链表的开始结点。 q=B； ∥q是B链表的工作指针。 while（p && q）
if（p->data==q->data） {p=p->next；q=q->next；}
else{pre=pre->next；p=pre； ∥A链表新的开始比较结点。 q=B；} ∥q从B链表第一结点开始。 if（q==null）return（1）； ∥B是A的子序列。 else return（0）； ∥B不是A的子序列。 }∥算法结束。
20．[题目分析] 本题也是模式匹配问题，应先找出链表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中的工作指针。 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中下次比较的第一字母结点，读者可自行完善之。
类似本题的另外叙述题的解答：
（1）[题目分析] 本题应先查找第i个结点，记下第i个结点的指针。然后从第i+1个结点起，直至第m（1 ∥L是有m个结点的链表的头结点的指针。表中从第i（1 {if（i<1|| i>=m || m<4）{printf（“%d,%d参数错误\\n”,i，m）；exit（0）；} p=L->next->next； ∥p是工作指针，初始指向第二结点（已假定i>1）。 pre=L->next； ∥pre是前驱结点指针，最终指向第i-1个结点。 j=1； ∥计数器 while（j {j++；pre=p；p=p->next；}∥查找结束，p指向第i个结点。 q=p； ∥暂存第i个结点的指针。 p=p->next； ∥p指向第i+1个结点，准备逆置。 j+=2； ∥上面while循环结束时，j=i-1，现从第i+1结点开始逆置。 while（j<=m） {r=p->next； ∥暂存p的后继结点。 p->next=pre->next；∥逆置p结点。 pre->next=p； p=r； ∥p恢复为当前待逆置结点。 j++； ∥计数器增1。 } q->next=pre->next；∥将原第i个结点的后继指针指向原第m个结点。 [算法讨论] 算法中未深入讨论i，m，j的合法性，因题目的条件是m>3且1 21．[题目分析] 顺序存储结构的线性表的逆置，只需一个变量辅助空间。算法核心是选择循环控制变量的初值和终值。 void SeqInvert（ElemType a[ ]，int n） ∥a是具有n个元素用一维数组存储的线性表，本算法将其逆置。 {for（i=0；i<=（n-1）/2；i++） {t=a[i]；a[i]= a[n-1-i]；a[n-1-i]=t；} }∥算法结束 [算法讨论] 算法中循环控制变量的初值和终值是关键。C中数组从下标0开始，第n个元素的下标是n-1。因为首尾对称交换，所以控制变量的终值是线性表长度的一半。当n为偶数，“一半”恰好是线性表长度的二分之一；若n是奇数，“一半”是小于n/2的最大整数，这时取大于1/2的最小整数的位置上的元素，恰是线性表中间位置的元素，不需要逆置。另外，由于pascal数组通常从下标1开始，所以，上下界处理上略有不同。这点请读者注意。 类似本题的其它题的解答： 这一组又选了6个题，都是单链表（包括单循环链表）的逆置。链表逆置的通常作法是：将工作指针指向第一个元素结点，将头结点的指针域置空。然后将链表各结点从第一结点开始直至最后一个结点，依次前插至头结点后，使最后插入的结点成为链表的第一结点，第一个插入的结点成为链表的最后结点。 （1）要求编程实现带头结点的单链表的逆置。首先建立一单链表，然后逆置。 typedef struct node {int data；∥假定结点数据域为整型。 struct node *next； }node,*LinkedList； LinkedList creat（ ） {LinkedList head，p int x； head=（LinkedList）malloc（sizeof（node））； head->next=null； /*设置头结点*/ scanf（“%d”，&x）； while（x!=9999） /*约定输入9999时退出本函数*/ {p=（LinkedList）malloc（sizeof（node））； p->data=x； p->next=head->next；/* 将新结点链入链表*/ head->next=p； scanf（“%d”，&x）； } return（head）； }∥结束creat函数。 LinkedList invert1（LinkedList head） /*逆置单链表*/ {LinkedList p=head->next; /*p为工作指针*/ head->next=null； while（p!=null） {r=p->next； /*暂存p的后继*/ p->next=head->next； head->next=p； p=r； } return（head）； }/*结束invert1函数*/ main（） {LinkedList la； la=creat( ）； /*生成单链表*/ la=invert1（la）；/*逆置单链表*/ } （2）本题要求将数据项递减有序的单链表重新排序，使数据项递增有序，要求算法复杂度为O（n）。虽没说要求将链表逆置，这只是叙述不同，本质上是将单链表逆置，现编写如下： LinkedList invert2（LinkedList la） ∥la是带头结点且数据项递减有序的单链表，本算法将其排列成数据项递增有序的单链表。 {p=la->next； /*p为工作指针*/ la->next=null； while（p!=null） {r=p->next； /*暂存p的后继。*/