您当前的位置:首页 > 计算机 > 编程开发 > C语言

两个整数序列A和B存放于两个单链表,判断B是否是A的连续子序列

时间:01-03来源:作者:点击数:

问题描述:

两个整数序列A=a1, a2, a3,…, am和B=b1, b2, b3,…,bn已经存入两个单链表中,设计一个算法,判断序列B是否是序列A的连续子序列。

问题解答:

算法思想:因为两个整数序列已存入两个链表中,操作从两个链表的第一个结点开始,若对应数据相等,则后移指针;若对应数据不等,则A链表从上次开始比较结点的后继开始,B链表仍从第一个结点开始比较,直到B链表到尾表示匹配成功。A链表到尾而B 链表未到尾表示失败。操作中应记住A链表每次的开始结点,以便下趟匹配时好从其后继开始。

int Pattern(LinkList A, LinkList B){
    //A和B分别是数据域为整数的单链表,本算法判断B是否是A的子序列
    LNode *p=A; //p为A链表的工作指针,本题假定A和B均无头结点
    LNode *pre = p;  //pre记住每趟比较中A链表的开始结点
    LNode *q=B;  //q是B链表的工作指针
    while (p&&q)
        if (p->data==q->data) { //结点值相同
            p=p->next;
            q=q->next;
        }else{
            pre=pre->next;
            p=pre;  //A链表新的开始比较结点
            q=B;  //q从B链表第一个结点开始
        }
    if (q==NULL)  //B已经比较结束
        return 1;  //说明B是A的子序列
    else
        return 0;  //B不是A的子序列
}

 

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门