第1章第2节练习题14 判断子序列

问题描述

两个整数序列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!
");
    }else{
        printf("B isn"t subsquence of A!
");
    }

    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("
");
}