AI 助理
备案控制台
开发者社区 人工智能 文章 正文

C语言手撕实战代码_循环单链表和循环双链表

2024-09-09 352
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 本文档详细介绍了用C语言实现循环单链表和循环双链表的相关算法。包括循环单链表的建立、逆转、左移、拆分及合并等操作；以及双链表的建立、遍历、排序和循环双链表的重组。通过具体示例和代码片段，展示了每种算法的实现思路与步骤，帮助读者深入理解并掌握这些数据结构的基本操作方法。

C语言手撕实战代码_循环单链表和循环双链表

循环单链表习题
1.建立带头结点的循环链表
2.设计一个算法，将一个带有头结点的循环单链表中所有结点的链接方向逆转
3.设计一个算法,将一个循环单链表左移k个结点
4.设计一个算法将循环单链表中的结点p的直接前驱删除
5.设计算法将一个含有数字，字母和其他字符组成的循环链表拆分成为三个循环链表，每条链中只包含一种类型的字符。
6.设计一个算法，将单链表中从第 i 个节点到第 m 个节点之间的节点顺序逆置，并将逆置后的子链表变成一个循环链表
7.已知La和Lb分别为两个循环单链表的==头节点指针==，m和n分别为La和Lb中数据结点的个数，设计时间复杂度最小的算法将两个链表合并成一个带头的循环单链表
8.创建尾指针指向的循环单链表
9.请设计一种数据结构来存储带头结点指针，m和n分别为La和Lb中数据节点的个数，设计时间复杂度最小的算法将两个链表合并成一个带头的循环单链表。
双链表和循环双链表实践
1.双链表的建立
2.双链表的前趋遍历和后继遍历
3.实践双链表:请你设计一个算法，将带头双向链表中数据结点的原有顺序保存在每个结点的next域中，而prior域将所有结点按照其值从小到大的顺序链接起来
4.实践循环双链表:设以头结点得双向循环链表表示得线性表为L=(a~1~，a~2~,a~3~，...,a~n~)。试写一时间复杂度为o(n)的算法，将L改造为L(a~1~,a~3~,a~n~,a~4~,a~2~)

@[toc]

循环单链表实践

1.建立带头结点的循环链表

思路:在原有带头结点单链表的基础上，让尾部指向头结点，因为要操作尾部，所以使用尾插法建立。
其实就是用尾插法在结尾处让原本指向空的指针，指向头结点

void creat_cyclelinklist_byinserttail(LinkList &L,int enterArra[],int enterArraLength)
{
   
   
    //先定义头结点
    L=(LinkNode *)malloc(sizeof(LinkNode));
    L->next=NULL;

    //循环尾插结点
    int index=0; //第一个数组下标
    LinkList tail=L;
    while(index<enterArraLength)
    {
   
   
        LinkNode *p=(LinkNode *)malloc(sizeof(LinkNode));
        p->data= enterArra[index++];
        tail->next=p;
        tail=p;
    }
    tail->next=L;
}

就是把
tail->next=NULL;改成了tail->next=L;
验证建立带头结点的循环链表，循环12次，看看输出的链表

    int c[8]={
   
   1,2,3,4,5,6,7,8};
    LinkList Lc=NULL;
    creat_cyclelinklist_byinserttail(Lc, c, 8);
    int x=12;
    LinkNode *p=Lc;
    while (x--) {
   
   
        printf("%d->",p->next->data);
        p=p->next;
    }
    printf("NULL\n");

2.设计一个算法，将一个带有头结点的循环单链表中所有结点的链接方向逆转

思路:循环单链表的逆转其实和单链表的逆转并无差别，还是用pre和cur指针再配一个临时p指针，主要注意一下，最后反转完还是循环的就行。

总结:循环单链表反转=单链表反转+处理头结点反转

void reverse_cryleLinklist(LinkList &Lc)
{
   
   
    LinkNode *cur=Lc->next; //指向第一个元素
    LinkNode *pre=Lc; //指向头结点
    LinkNode *p=NULL;
    while(p!=Lc)
    {
   
   
        p=cur->next;
        cur->next=pre;
        pre=cur;
        cur=p;
    }     //这里结束，意味着除了头结点之外都反转过来了，即完成了单链表的反转操作
    Lc->next=pre; //最后一步，完成了头结点的反转
}

3.设计一个算法,将一个循环单链表左移k个结点

左移简单理解就是，原先的循环一遍的顺序是12345,左移两位之后，循环的顺序就是34512.也就是头结点右移

不需要引入新的头结点的方式。
需要找到链表尾部，头结点插入的前一个位置，插入的后一个位置，

找到待插入结点和它的前一个结点。还有最后一个结点，然后将新的头结点插入，将最后一个结点指向第一个结点。

void left_crycle_linklist(LinkList &Lc,int k)
{
   
   
    //找到三个点 pre cur last,记录一个点 first,第一个结点的位置
    LinkNode *pre=Lc;
    LinkNode *cur=Lc->next;
    LinkNode *last=Lc;
    LinkNode *first=Lc->next;
    //第一个循环找pre和cur
    while (k--) {
   
   
        cur=cur->next;
        pre=pre->next;
    }
    //第二个循环找last
    while(last->next!=Lc)
    {
   
   
        last=last->next;
    }

    //将头结点插入
    Lc->next=cur;
    pre->next=Lc;
    //将最后一个结点连接第一个结点
    last->next=first;
}

思考:我记得单链表中还是使用反转链表做的，但是循环链表就不用那么复杂。

4.设计一个算法将循环单链表中的结点p的直接前驱删除

思路：给你一个指向p结点的指针P，设置一个寻找指针find，和新的指向p的指针new_p,find指向P的后继的后继。new_p和find构成双指针移动。find再次指向p的时候，new_p就指向了我们的目标，然后进行删除就ok。
image.png

5.设计算法将一个含有数字，字母和其他字符组成的循环链表拆分成为三个循环链表，每条链中只包含一种类型的字符。

思路:创建三个循环链表，采用头插法加入链表，重点在于判断三种类型。
数字0的asc码是48，数字0到9是连续的，故9的asc码是48+9=57
大写字母A的asc码是65，故大写字母Z的asc码是65+25=90
小写字母a是asc码是97，故小写字母z的asc码是97+25=122

6.设计一个算法，将单链表中从第 i 个节点到第 m 个节点之间的节点顺序逆置，并将逆置后的子链表变成一个循环链表

逻辑很清晰，先逆置，最后操作形成循环链表
值得注意的是，这个操作之后，m结点之后的结点将无法被访问到。

给出图例:
image.png

7.已知La和Lb分别为两个循环单链表的==头节点指针==，m和n分别为La和Lb中数据结点的个数，设计时间复杂度最小的算法将两个链表合并成一个带头的循环单链表

思路很简单，将较短的循环单链表插入较长的循环单链表中，采用头插法。

注意和第9题联系起来

8.创建尾指针指向的循环单链表

本质就是，尾插法建立循环单链表，记录好最后一个元素，处理好循环。
非常值得注意的是此时La和Lb 是指向最后一个结点，假如你要找到头结点
La->next才是头结点
image.png

9.请设计一种数据结构来存储带头结点指针，m和n分别为La和Lb中数据节点的个数，设计时间复杂度最小的算法将两个链表合并成一个带头的循环单链表。

image.png

其中pheadLa是这么定义的，pheadLa=Ta->next。

双链表和循环双链表实践

1.双链表的建立

使用头插法建立双链表，在插入过程中，先连接插入结点，再更新插入结点的前驱结点和后继结点。注意后继结点一定要判空，否则会访问出界。

typedef  int ElemType;
typedef struct DuLinkNode
{
   
   
    ElemType data;
    struct DuLinkNode* prior;
    struct DuLinkNode* next;
}DuLinkNode,*DuLinkList;

void creat_doubleLinklist(DuLinkList &DL, int a[4],int length) //双链表的建立
{
   
   
    //创建一个头结点
    DL=(DuLinkNode *)malloc(sizeof(DuLinkNode));
    DL->next=NULL;
    DL->prior=NULL;

    DuLinkNode * L=DL;
    //添加结点
    for(int i=0;i<length;i++)
    {
   
   
        DuLinkNode * p;
        p=(DuLinkNode *)malloc(sizeof(DuLinkNode));
        p->data=a[i];
        p->next=L->next;   //更新插入结点的后继指针域
        p->prior=L;   //更新插入结点的前驱指针域
        L->next=p;    //更新前驱结点的后继指针域
        if(p->next!=NULL)
        {
   
   
            p->next->prior=p; //更新后继结点的前驱指针域
        }

    }
}

2.双链表的前趋遍历和后继遍历


void print_next(DuLinkList DL,int length)  //双链表的后继遍历
{
   
   
    while(length--)
    {
   
   
        printf("%d->",DL->next->data);
        DL=DL->next;
    }
    printf("NULL\n");
}

void print_prior(DuLinkList DL,int length)  //双链表的前趋遍历
{
   
   
    while(DL->next!=NULL)
    {
   
   
        DL=DL->next;
    }
    while(length--)
    {
   
   
        printf("%d->",DL->data);
        DL=DL->prior;
    }
    printf("NULL\n");
}

3.实践双链表:请你设计一个算法，将带头双向链表中数据结点的原有顺序保存在每个结点的next域中，而prior域将所有结点按照其值从小到大的顺序链接起来

next储存原先顺序，prior储存排序顺序，反向使用单链表的插入排序

关于单链表的插入排序

struct ListNode* insertionSortList(struct ListNode* head) {
   
   
    if (head == NULL) return NULL;  // 检查链表是否为空

    struct ListNode* L = (struct ListNode*)malloc(sizeof(struct ListNode));
    L->next = head;

    struct ListNode* ordermove;             // ordermove起点是头结点
    struct ListNode* disordermove = head->next; // disordermove起点是第二个元素，因为第一个元素默认有序
    head->next = NULL;  // 断开链表，只保留第一个元素作为初始有序链表

    while (disordermove != NULL) {
   
     // 当disordermove遍历完之后循环结束
        ordermove = L;  // 重置 ordermove 为哑结点 L

        // 寻找插入点
        while (ordermove->next != NULL && ordermove->next->val < disordermove->val) {
   
   
            ordermove = ordermove->next;
        }

        // 插入 disordermove 到 ordermove 之后
        struct ListNode* nextDisorder = disordermove->next;  // 记录下一个待排序结点
        disordermove->next = ordermove->next;
        ordermove->next = disordermove;

        // 移动到下一个待排序结点
        disordermove = nextDisorder;
    }

    struct ListNode* sortedHead = L->next;  // 排序后的链表头部
    free(L);  // 释放哑结点
    return sortedHead;
}

4.实践循环双链表:设以头结点得双向循环链表表示得线性表为L=(a~1~，a~2~,a~3~，...,a~n~)。试写一时间复杂度为o(n)的算法，将L改造为L(a~1~,a~3~,a~n~,a~4~,a~2~)

首先，创建一个带头结点的循环双链表（采用尾插法方便）

void creat_doublecycleLinklist(DuLinkList &DL, int a[8],int length) //双链表的建立
{
   
   
    //创建一个头结点
    DL=(DuLinkNode *)malloc(sizeof(DuLinkNode));
    DL->next=DL;
    DL->prior=DL;

    DuLinkNode * cur=DL;
    //添加结点
    for(int i=0;i<length;i++)
    {
   
   
        DuLinkNode * p;
        p=(DuLinkNode *)malloc(sizeof(DuLinkNode));
        p->data=a[i];
        p->next=DL;   //更新插入结点的后继指针域
        p->prior=cur;   //更新插入结点的前驱指针域
        cur->next=p;    //更新前驱结点的后继指针域
        DL->prior=p;   //头结点的前驱指针
        cur=p; //更新L指针

    }
}

本题思路:

思路:遍历一遍双向循环链表，将偶数列拿出来，采用头插法建立一个新的链，最后再拼接起来。

本题代码，千万别忘了双向循环链表该考虑的都要考虑到

给出测试版代码和简化版代码

==测试版代码==

void reverse_doublecycleLink(DuLinkList &DL)
{
   
   
    //设置一个偶数表头(循环双链表)
    DuLinkList el=NULL;
    el=(DuLinkNode*)malloc(sizeof(DuLinkNode));
    el->next=el;
    el->prior=el;


    // 遍历一遍循环双链表
    DuLinkNode *p=DL->next; //定义一个指针控制循环
    DuLinkNode *pre=DL; //定义一个指针控制循环
    int jiou=0; //奇偶开头
    while(p!=DL)  //循环一遍
    {
   
   
        DuLinkNode *last=p->next;
        if(jiou==0)jiou=1;
        else jiou=0;  //奇偶标志

        if(jiou==0)  //偶数操作，
        {
   
   
            //将当前偶数头插进入el表
            p->next=el->next;
            el->next->prior=p;
            el->next=p;
            p->prior=el;

            //在原表中删掉这个偶数结点，删除结点时前趋后继都要修改
            pre->next=last;
            last->prior=pre;
            p=last;  //pre此时不变

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

    //检验一下，当前DL的打印
    p=DL->next;
    while(p!=DL)
    {
   
   
        printf("%d->",p->data);
        p=p->next;
    }
    printf("\n");

    //检验一下，当前el的打印
    p=el->next;
    while(p!=el)
    {
   
   
        printf("%d->",p->data);
        p=p->next;
    }
    printf("\n");

    //检验成功，进行合并操作，需要el的尾指针和pl的尾指针,因为是循环链表直接能拿到
//    DuLinkNode *tail_dl=DL;
//    DuLinkNode *tail_el=el;
//    while(tail_dl->next!=DL)
//    {
   
   
//        tail_dl=tail_dl->next;
//    }
//    while(tail_el->next!=el)
//    {
   
   
//        tail_el=tail_el->next;
//    }
//    printf("el的尾指针%d\n",el->prior->data);

    printf("连接前的DL某尾的后继是%d\n",DL->prior->next->data);
    DL->prior->next=el->next;
    printf("连接后的DL某尾的后继是%d\n",DL->prior->next->data);
    el->next->prior=DL->prior;  //屁股连好了

    el->prior->next=DL;
    DL->prior=el->prior;  //头也连接好了

   // 终极检测

    //检验一下，当前DL的打印
    p=DL->next;
    while(p!=DL)
    {
   
   
        printf("%d->",p->data);
        p=p->next;
    }
    printf("\n");


}

==简化版代码==

void reverse_doublecycleLink(DuLinkList &DL)
{
   
   
    //设置一个偶数表头(循环双链表)
    DuLinkList el=NULL;
    el=(DuLinkNode*)malloc(sizeof(DuLinkNode));
    el->next=el;
    el->prior=el;


    // 遍历一遍循环双链表
    DuLinkNode *p=DL->next; //定义一个指针控制循环
    DuLinkNode *pre=DL; //定义一个指针控制循环
    int jiou=0; //奇偶开头
    while(p!=DL)  //循环一遍
    {
   
   
        DuLinkNode *last=p->next;
        if(jiou==0)jiou=1;
        else jiou=0;  //奇偶标志

        if(jiou==0)  //偶数操作，
        {
   
   
            //将当前偶数头插进入el表
            p->next=el->next;
            el->next->prior=p;
            el->next=p;
            p->prior=el;

            //在原表中删掉这个偶数结点，删除结点时前趋后继都要修改
            pre->next=last;
            last->prior=pre;
            p=last;  //pre此时不变

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

    DL->prior->next=el->next;
    el->next->prior=DL->prior;  //屁股连好了
    el->prior->next=DL;
    DL->prior=el->prior;  //头也连接好了

}
文章标签：
算法
C语言
存储
关键词：
C语言循环
C语言链表
C语言代码
C语言单链表
C语言实战
小徐在进步
目录
相关文章
程序员Feri
|
10月前
|
人工智能 Java 程序员
一文彻底搞清楚C语言的循环语句
本文介绍了C语言中的三种循环语句：`while`、`do-while`和`for`，并详细解释了它们的语法格式、执行流程及应用场景。此外，还讲解了循环控制语句`break`和`continue`的使用方法。希望这些内容能帮助你在编程道路上不断进步，共同成长！
程序员Feri
863 0
一文彻底搞清楚C语言的循环语句
RossyYan
|
11月前
|
C语言
【C语言程序设计——循环程序设计】枚举法换硬币（头歌实践教学平台习题）【合集】
本文档介绍了编程任务的详细内容，旨在运用枚举法求解硬币等额 - 循环控制语句（`for`、`while`）及跳转语句（`break`、`continue`）的使用。 - 循环嵌套语句的基本概念和应用，如双重`for`循环、`while`嵌套等。 3. **编程要求**：根据提示在指定区域内补充代码。 4. **测试说明**：平台将对编写的代码进行测试，并给出预期输出结果。 5. **通关代码**：提供完整的代码示例，帮助理解并完成任务。 6. **测试结果**：展示代码运行后的实际输出，验证正确性。 文档结构清晰，逐步引导读者掌握循环结构与嵌套的应用，最终实现硬币兑换的程序设计。
RossyYan
162 19
RossyYan
|
11月前
|
算法 C语言
【C语言程序设计——循环程序设计】求解最大公约数（头歌实践教学平台习题）【合集】
采用欧几里得算法（EuclideanAlgorithm）求解两个正整数的最大公约数。的最大公约数，然后检查最大公约数是否大于1。如果是，就返回1，表示。根据提示，在右侧编辑器Begin--End之间的区域内补充必要的代码。作为新的参数传递进去。这个递归过程会不断进行，直到。有除1以外的公约数；变为0，此时就找到了最大公约数。开始你的任务吧，祝你成功！是否为0，如果是，那么。就是最大公约数，直接返回。
RossyYan
291 18
RossyYan
|
11月前
|
Serverless C语言
【C语言程序设计——循环程序设计】利用循环求数值 x 的平方根（头歌实践教学平台习题）【合集】
根据提示在右侧编辑器Begin--End之间的区域内补充必要的代码，求解出数值x的平方根；运用迭代公式，编写一个循环程序，求解出数值x的平方根。注意：不能直接用平方根公式/函数求解本题！开始你的任务吧，祝你成功！​ 相关知识 求平方根的迭代公式 绝对值函数fabs() 循环语句 一、求平方根的迭代公式 1.原理 在C语言中，求一个数的平方根可以使用牛顿迭代法。对于方程（为要求平方根的数），设是的第n次近似值，牛顿迭代公式为。 其基本思想是从一个初始近似值开始，通过不断迭代这个公式，使得越来越接近。
RossyYan
294 18
RossyYan
|
11月前
|
C语言
【C语言程序设计——循环程序设计】统计海军鸣放礼炮声数量（头歌实践教学平台习题）【合集】
有A、B、C三艘军舰同时开始鸣放礼炮各21响。已知A舰每隔5秒1次，B舰每隔6秒放1次，C舰每隔7秒放1次。编程计算观众总共听到几次礼炮声。根据提示，在右侧编辑器Begin--End之间的区域内补充必要的代码。开始你的任务吧，祝你成功！
RossyYan
236 13
RossyYan
|
11月前
|
存储 C语言
【C语言程序设计——循环程序设计】利用数列的累加和求 sinx（头歌实践教学平台习题）【合集】
项的累加和，一般会使用循环结构，在每次循环中计算出当前项的值（可能基于通项公式或者递推关系），然后累加到一个用于存储累加和的变量中。在C语言中推导数列中的某一项，通常需要依据数列给定的通项公式或者前后项之间的递推关系来实现。例如，对于一个简单的等差数列，其通项公式为。的级数，其每一项之间存在特定的递推关系（后项的分子是其前项的分子乘上。，计算sinx的值，直到最后一项的绝对值小于。为项数），就可以通过代码来计算出指定项的值。对于更复杂的数列，像题目中涉及的用于近似计算。开始你的任务吧，祝你成功！
RossyYan
271 6
RossyYan
|
11月前
|
C语言
【C语言程序设计——循环程序设计】鸡兔同笼问题（头歌实践教学平台习题）【合集】
本教程介绍了循环控制和跳转语句的使用，包括 `for`、`while` 和 `do-while` 循环，以及 `break` 和 `continue` 语句。通过示例代码详细讲解了这些语句的应用场景，并展示了如何使用循环嵌套解决复杂问题，如计算最大公因数和模拟游戏关卡选择。最后，通过鸡兔同笼问题演示了穷举法编程的实际应用。文中还提供了编程要求、测试说明及通关代码，帮助读者掌握相关知识并完成任务。 任务描述：根据给定条件，编写程序计算鸡和兔的数量。鸡有1个头2只脚，兔子有1个头4只脚。
RossyYan
579 5
LuckiBit
|
存储 算法 C语言
【C语言】深入浅出：C语言链表的全面解析
链表是一种重要的基础数据结构，适用于频繁的插入和删除操作。通过本篇详细讲解了单链表、双向链表和循环链表的概念和实现，以及各类常用操作的示例代码。掌握链表的使用对于理解更复杂的数据结构和算法具有重要意义。
LuckiBit
3432 6
龙大吉
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
355 5
ephemerals__
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
1162 4