## 问题描述 > 两个整数序列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<stdio.h> #include<stdlib.h> 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"); } ~~~