## 問題描述 > 兩個整數序列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"); } ~~~