第1章第2节练习题14 判断子序列
最后更新于：2022-04-01 19:51:07
## 问题描述
> 两个整数序列A=a1,a2,a3,...,am和B=b1,b2,b3,...,bn已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的连续子序列。
## 算法思想
> 因为此题需要判断序列B是否为序列A的子序列，即单链表B中所有连续结点的数据域的值是否在A中能够找到同样连续的一部分。
既然如此，那么我们可以从两个链表的第一个结点开始，若对应的数据相等，则后移指针；
最后判断下单链表B是否彻底遍历完成，如果完成，则表示单链表B是单链表A的一个子序列；如果没有遍历完成，则表示单链表B不是单链表A的一个子序列。
## 算法描述
~~~
int FindSub(LNode* head1, LNode* head2)
{
LNode *pre=head1; //保存指针p所指结点的前驱结点
LNode *p=head1->next; //指向序列A中需要比较的结点
LNode *q=head2->next; //指向序列B中需要比较的结点
while(p&&q){ //如果p或q为空，表示单链表A或单链表B至少已经有一个遍历完成
if(p->data==q->data){
p=p->next;
q=q->next;
}
else{
pre=pre->next;
p=pre;
q=head2->next;
}
}
if(q==NULL){
return 0;
}
return -1;
}
~~~
具体代码见附件。
## 附件
~~~
#include
#include
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
LinkList CreatList(LNode*);
int FindSub(LNode*, LNode*);
void Print(LNode*);
int main(int argc, char* argv[])
{
LNode *head1;
head1=(LNode*)malloc(sizeof(LNode));
head1->next=NULL;
head1=CreatList(head1);
LNode *head2;
head2=(LNode*)malloc(sizeof(LNode));
head2->next=NULL;
head2=CreatList(head2);
Print(head1);
Print(head2);
int flag;
flag=FindSub(head1, head2);
if(flag==0){
printf("B is subsquence of A!\n");
}else{
printf("B isn't subsquence of A!\n");
}
return 0;
}
//头插法建立单链表
LinkList CreatList(LNode* head)
{
LNode *L;
ElemType x;
scanf("%d",&x);
while(x!=999){
L=(LNode*)malloc(sizeof(LNode));
L->data=x;
L->next=head->next;
head->next=L;
scanf("%d",&x);
}
return head;
}
//判断单链表B是否为单链表A的子序列。若是则返回0，若不是则返回-1；
int FindSub(LNode* head1, LNode* head2)
{
LNode *pre=head1;
LNode *p=head1->next;
LNode *q=head2->next;
while(p&&q){
if(p->data==q->data){
p=p->next;
q=q->next;
}
else{
pre=pre->next;
p=pre;
q=head2->next;
}
}
if(q==NULL){
return 0;
}
return -1;
}
//打印全部结点
void Print(LNode *head)
{
LNode *p=head->next;
while(p){
printf("%4d",p->data);
p=p->next;
}
printf("\n");
}
~~~
';