给定两个子序列，存入两个单链表中，判断B是否为A的子序列(C语言)

待我称王封你为后i 2022-12-24 14:56 79阅读 0赞

#### 思想 ####

1.  使用两个指针p和q，分别指向需要匹配的两个单链表A和B的第一个数据结点。
2.  使用一个pre指针保存p和q匹配的初始位置
3.  两两比对，如果相同继续一起往后走，如果不同，则q回到B，p回到pre，也就是开始匹配的地方。再进行比对。

例如

> 1 2 3 4 5  
> 3 4 5

注意：以下实现基于带表头结点的链表

#### C语言代码实现 ####

/**
        判断是否是子序列
    **/
    int judgeIsChildOrder(ListNode *A,ListNode *B)
    {
        
        ListNode *p = A->next;
        ListNode *q = B->next;
        ListNode *pre=p;//pre记录A中与B开始比较的位置
        while(p && q)
        {
        
            if(p->data==q->data)
            {
        
                p=p->next;
                q=q->next;
            }
            else
            {
        
                q=B->next;//B链表回到最初位置，注意这里必须是next,因为本题带表头结点
                pre=pre->next;
                p=pre;//A从标记点重新开始
            }
        }
        return q==NULL?  1:0;
    
    }

#### 运行结果测试 ####

这里我们先使用尾插法创建链表

ListNode *createLinkedList(int a[],int n)
    {
        
    
        ListNode *L = (ListNode*)malloc(sizeof(ListNode));//创建表头结点
        int i;
        ListNode *r=L;//尾指针
        for(i=0; i<n; i++)
        {
        
            ListNode *s=(ListNode*)malloc(sizeof(ListNode));
            s->data=a[i];
            r->next=s;
            r=s;
        }
    
        r->next=NULL;// 表尾设置为null
        return L;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70]  
测试代码

int main()
    {
        
        int a[5]={
        1,2,3,4,5};
        int b[5]={
        2,3};
        ListNode *resultA=createLinkedList(a,5);
        ListNode *resultB=createLinkedList(b,2);
        printLinkedList(resultA);
        printLinkedList(resultB);
        int isChildOrder = judgeIsChildOrder(resultA,resultB);
        printf("是否是子序列%d",isChildOrder);
        return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70]: /images/20221120/88684876f6ab4b308dc48f0d71f252d2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg4OTg0MQ_size_16_color_FFFFFF_t_70 1]: /images/20221120/78977bfa6d6240bd947a60f31c3adc24.png