首页 > 其他 > 详细

链表 | 判断链表B是否为链表A的连续子序列

时间:2018-02-17 18:37:33      阅读:408      评论:0      收藏:0      [点我收藏+]

王道P38T16

代码:

bool common_subSequence(LinkList &A,LinkList &B){
    LNode *pA,*pB=B->next,*p=A->next;
    while(p!=NULL){
        if(p==NULL || pB==NULL) return false;
        if(p->data == pB->data){
            pA=p;
            while(pA!=NULL && pB!=NULL){
                if(pA->data != pB->data){
                    break;
                }
                pA=pA->next;
                pB=pB->next;
            }
            if(pB==NULL)
                return true;
            pB=B->next;
        }
        p=p->next;
    }
    return false;
} 

主代码:

技术分享图片
#include <cstdio>
#include <stdlib.h>

using namespace std;

typedef struct LNode{
    int data;
    struct LNode* next=NULL; 
    LNode(int x=0){    
        data=x;
    }
}LNode;

typedef LNode* LinkList;

LinkList  build_list(int * arr,int n){
    int i;
    LinkList L=new LNode;
    LinkList pre=L;
    for(i=0;i<n;i++){
        LinkList p=new LNode(arr[i]);
        pre->next=p;
        pre=p;
    }
    return L;
}

void show_list(LinkList& L){
    LinkList p=L->next;
    while(p){
        printf("%d ",p->data);
        p=p->next;
    }
    puts("");
}

bool common_subSequence(LinkList &A,LinkList &B){
    LNode *pA,*pB=B->next,*p=A->next;
    while(p!=NULL){
        if(p==NULL || pB==NULL) return false;
        if(p->data == pB->data){
            pA=p;
            while(pA!=NULL && pB!=NULL){
                if(pA->data != pB->data){
                    break;
                }
                pA=pA->next;
                pB=pB->next;
            }
            if(pB==NULL)
                return true;
            pB=B->next;
        }
        p=p->next;
    }
    return false;
} 

int main(){
    int A_arr[5]={0,0,2,2,2};
    int B_arr[3]={2,2,2};
    LinkList A=build_list(A_arr,5);
    LinkList B=build_list(B_arr,3);
    puts(common_subSequence(A,B)?"Yes":"No");
}
 
View Code

注意:

注意紫色代码处的工作指针p的滑动和橙色代码处的pB空指针判断。

 

链表 | 判断链表B是否为链表A的连续子序列

原文:https://www.cnblogs.com/TQCAI/p/8452056.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!