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

∥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->datadata){pre=p;p=p->next;*n++;} ∥ A链表中当前结点指针后移。 else if(p->data>q->data)q=q->next; ∥B链表中当前结点指针后移。

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且1next=pre->next,实现了从原第i个结点到原第m个结点的循环。最后pre->next正是指向原第m个结点,不可用p->next代替pre->next。

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的后继。*/