【趣学C语言和数据结构100例】

问题描述

51.在一个递增有序的单链表中，存在重复的元素。设计算法删除重复的元素，例如(7.10.10.21.30.42.42.42.51.70)将变为(7.10.21.30.42.51.70)。

52.设A 和 B 是两个单链表(带头结点)，其中元素递增有序。设计一个算法从 A 和B中的公共元素产生单链表 C，要求不破坏 A、B 的结点。

53.两个整数序列 A=a1,a2,a.....,a和 B=b,,b2,b.…,b已经存入两个单链表中，设计一个算去，判断序列 B是否是序列 A 的连续子序列。

54.设计一个算法用于判断带头结点的循环双链表是否对称

55.有两个循环单链表,链表头指针分别为 hl 和 h2,编写一个函数将链表 h2 链接到链表11 之后，要求链接后的链表仍保持循环链表形式。

代码分析

==51.有序的单链表，删除重复的元素==
分析：无返回值+对链表操作，故函数名为void 函数名(LiukLIist L)，定义节点p和q（p当前，即L->next开始，q找重复）如果单链表为空，则直接return 0;使用while(p->next)循环遍历，使q从p的下一个开始，如果2个的值相等，则p直接指向q的下一个，跳过当前q，并且释放free(q)，否则使p向后移动一位。

==52.A和B两个单链表(带头结点)的公共元素==
分析：返回链表+AB不操作，故函数名为LiukList 函数名(LiukLIist A,LiukLIist B)，创造C链表即（LiukList C=(LiukList)malloc(sizeof)(Lnode) ,C->next=NULL）,p、q 和 r，分别指向 A 链表、B 链表和新链表 C 的当前节点,使用while循环遍历，只要一个到达最后即可，使用&&，如果p的值>q的值,使q=q->next，如果q的值>p的值,使p=p->next(使小的移动，直到相等)，当值相等时，进行给C，即尾插法。创造一个s节点，用来存储值在赋值给C，值先交付，使r的下一个指向此时的p，更新r到达此时C的最后一位，尾插结束，使p和q同时向后移动一位，知道结束。在结束后，在C的最后加入r->next=NULL；然后返回链表C。

==53.判断序列 B是否是序列 A 的连续子序列==
分析：返回值为int,对AB不操作，故函数名为int 函数名(LiukLIist A,LiukLIist B)。三个指针 p、q 和 pre，分别指向 A 链表、B 链表和 A 链表的当前节点。使用while循环遍历，代码遍历两个链表，比较 p 和 q 指向的节点数据，如果相同，则继续遍历；否则，将 q 指针重置为 B 链表的头部，并将 p 指针指向 pre 的下一个节点。直到结束，如果此时的q为空，则说明可以到达最后，说明找到了，则返回1，否则返回0。

==54.判断带头结点的循环双链表是否对称==
分析：返回值为bool类型，对链表不操作，故函数名为bool 函数名(LiukLIist A)。定义p,q分别指向链表的头部和尾部，使用while循环遍历，只要p!=q或者p->next!=q，一直，if(p->data==q->data),则进行同时移动，如果不相等则return 0。在结束循环为进行返回，则返回return 1。

==55.链表的拆分==
分析：两个循环单链表的插入连接，初步思路为，h1的最后和h2的开头连接，h1的开头和h2的尾部连接即可。返回类型为链表，A会发生变化，故函数名为LiukList 函数名(LiukList &h1,LiukList &h2),在函数中使p和q分别先找到h1和h2的尾部。找到后令p的下一步指向h2,令q的下一步指向h1,然后返回h1。

//循环链表找尾部：
while(p->next!=头部){
   
    p=p->next;
}

代码实现

#include <stdio.h>
#include <cstring>
#include <ctype.h>
#include <math.h>
int main() {
   

//    51.在一个递增有序的单链表中，存在重复的元素。设计算法删除重复的元素，例如(7.10.10.21.30.42.42.42.51.70)将变为(7.10.21.30.42.51.70)。
void Del_same(LiukList &L){
   
    Lnode *p=L->next,*q;    //p当前，q找重复
    if(p==NULL){
   
        return 0;
    }
    while(p->next != NULL){
   
        q=p->next;
        if(p->data=q->data){
   
            p->next=q->next;
            free(q);

        }
        else{
   
            p=p->next;    
        }
    }

}     

//    52.设A和B是两个单链表(带头结点)，其中元素递增有序。设计一个算法从 A 和B中的公共元素产生单链表 C，要求不破坏 A、B 的结点。
LiukList Find_same(LiukList A, LiukList B) {
   
    Lnode *p = A->next, *q = B->next, *s;
    LiukList C = (LiukList)malloc(sizeof(Lnode));
    C->next = NULL;
    Lnode *r = C->next;
    // p、q 和 r，分别指向 A 链表、B 链表和新链表 C 的当前节点
    while (p != NULL && q != NULL) {
   
        if (p->data < q->data) {
   
            p = p->next;
        } else if (p->data > q->data) {
   
            q = q->next;
        } else {
   
            // 到 p->data == q->data 时 
            s = (Lnode *)malloc(sizeof(Lnode));
            s->data = p->data;
            s->next = NULL;
            //在C尾插 
            if (C->head == NULL) {
   
                C->head = s;
                r = s;
            } else {
   
                r->next = s;
                r = s;
            }
            p = p->next;
            q = q->next;
        }
    }
    r->next=NULL;
    return C;
}


//    53.两个整数序列 A=a1,a2,a.....,a和 B=b,,b2,b.…,b已经存入两个单链表中，设计一个算去，判断序列 B是否是序列 A 的连续子序列。
//三个指针 p、q 和 pre，分别指向 A 链表、B 链表和 A 链表的当前节点。
//代码遍历两个链表，比较 p 和 q 指向的节点数据，如果相同，则继续遍历；
//否则，将 q 指针重置为 B 链表的头部，并将 p 指针指向 pre 的下一个节点。
int  Find_x(LiukList A,LiukList B){
   
    Lnode *p=A,*q=B,*pre=A;
    while(p && q){
   
        if(p->data == p->data){
   
            p=p->next;
            q=q->next;
        }
        else{
   
            //重置q从头 
            q=B;
            p=pre->next;
            pre=p;    
        }
    }
    if(q==NULL){
   
        return 1;
    }else{
   
        return 0;
    }
}     

//    54.设计一个算法用于判断带头结点的循环双链表是否对称
//双向循环链表： 同时拥有 next 和 prior 指针。 由于双向循环链表可以从任意节点开始，沿着 next 或 prior 指针遍历，因此可以使用 L->prior 来访问前一个节点。
bool func(DLiukList L){
   
    DLiukList *p=L->next,*q=L->prior;  //p,q分别指向链表的头部和尾部
    while(p!= q && p->next!=q){
   
        if(p->data==q->data){
   
            p=p->next;
            q=q->prior;
        }else{
   
            return 0;
        }
    }
    return 1;
} 

//    55.有两个循环单链表,链表头指针分别为 hl 和 h2,编写一个函数将链表 h2 链接到链表11 之后，要求链接后的链表仍保持循环链表形式。
LiukList func(LiukList &h1,LiukList h2){
   
    Lnode *p=h1,*q=h2;
    //找到h1 链表和 h2 链表的尾部
    while(p->next!=h1){
   
        p=p->next;
    }
    while(q->next!=h2){
   
        q=q->next;
    }
    //h1 链表的尾部节点的p-> next 指针指向 h2 链表的头部节点，并将 h2 链表的尾部节点的q-> next 指针指向 h1 链表的头部节点
    p->next=h2;
    q->next=h1;
    return h1;
}

    return 0;
}

总结

本文介绍了五个链表操作的问题及其C语言实现，这些问题涉及删除重复元素、查找公共元素、判断子序列、检查对称性以及链表的合并。这些算法问题覆盖了链表操作的多个方面，展示了数据结构在解决实际问题中的应用。

删除重复元素的问题要求我们在保持链表有序的前提下删除重复的元素。这个问题的解决关键在于使用两个指针遍历链表，当发现重复元素时，跳过这些元素并释放内存。

查找公共元素的问题要求我们从两个有序的单链表中找出公共元素，并生成一个新的链表。这个问题的解决需要我们使用两个指针分别遍历两个链表，找到公共元素后，使用尾插法将它们添加到新链表中。

判断子序列的问题要求我们判断一个链表是否是另一个链表的连续子序列。这个问题的解决可以通过两个指针分别遍历两个链表，如果当前元素相等，则继续向后遍历，否则重置一个指针并继续比较。

检查对称性的问题要求我们判断一个带头结点的循环双链表是否对称。这个问题的解决需要我们使用两个指针分别从头部和尾部向中间遍历，如果发现元素不相等，则链表不对称。

链表合并的问题要求我们将两个循环单链表合并为一个，并保持循环链表的性质。这个问题的解决需要我们找到两个链表的尾部，并将它们连接起来，形成一个更大的循环链表。

这些算法的实现不仅展示了C语言在处理链表时的能力，也体现了算法设计的基本思想，如指针操作、条件判断和循环控制。通过这些算法的学习，我们可以更好地理解数据结构和算法的基本概念，提高解决实际问题的能力。

总的来说，这些算法问题不仅锻炼了编程能力，也加深了对数据结构和算法的理解。通过这些问题的解决，我们可以逐步提高自己的编程技能，为将来的学习和工作做好准备。这些算法的掌握对于计算机专业的学生和软件开发人员来说都是非常重要的。通过这些练习，我们可以逐步提高自己的编程技能，为将来的学习和工作做好准备。同时，这些问题的解决也体现了算法在处理链表时的灵活性和效率，为我们在实际开发中遇到类似问题提供了解决思路。