39-16

两个整数序列存放在单链表A，B 中，设计一个算法，判断B是否是A的连续子序列

算法思想类似于朴素匹配算法。

遇到不匹配的，A需要记录与B开始匹配的位置（pre指针的作用），从该位置的下一个结点开始匹配，B从头开始匹配。

#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    int data;
    struct node *next;
}LNode,*LinkList;

void TailCreate(LinkList &L)
{
    L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    LNode *p,*r=L;
    int x;
    scanf("%d",&x);
    while(x!=999)
    {
        p=(LNode*)malloc(sizeof(LNode));
        p->data=x;
        p->next=NULL;
        r->next=p;
        r=p;
        scanf("%d",&x);
    }
}

void displayList(LinkList L)
{
    LNode *p=L->next;
    while(p!=NULL)
    {
        printf("%d  ",p->data);
        p=p->next;
    }
}

void Judge(LinkList A,LinkList B)            
{
    LNode *pa=A->next,*pb=B->next,*pre=pa;
    while(pa && pb)
    {        
        if(pa->data==pb->data)
        {
            pa=pa->next;
            pb=pb->next;
        }
        else
        {
            pre=pre->next;
            pa=pre;
            pb=B->next;
        }
    }
    if(pb==NULL)
    {
        printf("yes");
        return;
    }
    else
    {
        printf("No");
        return;
    }
}

int main()
{
    LinkList A,B;
    TailCreate(A);
    displayList(A);
    printf("\n");
    TailCreate(B);
    displayList(B);
    printf("\n");
    Judge(A,B);
    return 0;
}