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=(a1,a2,a3,…,an)。试写一时间复杂度为o(n)的算法,将L改造为L(a1,a3,an,a4,a2)

文章目录

  • 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~)

循环单链表实践

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。
在这里插入图片描述

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结点之后的结点将无法被访问到。

给出图例:
在这里插入图片描述

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

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

注意和第9题联系起来

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

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

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

在这里插入图片描述
其中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=(a1,a2,a3,…,an)。试写一时间复杂度为o(n)的算法,将L改造为L(a1,a3,an,a4,a2)

首先,创建一个带头结点的循环双链表(采用尾插法方便)

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;  //头也连接好了
    
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/871836.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

游泳耳机品牌前十名哪个牌子好?如何选高配游泳耳机不花冤枉钱?

在快节奏的现代生活中&#xff0c;音乐已成为许多人放松和充电的重要方式之一。无论是晨跑、通勤还是健身&#xff0c;音乐总能陪伴我们度过每一个瞬间。而对于游泳爱好者来说&#xff0c;能够在水中享受音乐&#xff0c;更是将这一运动提升到了一个新的层次。然而&#xff0c;…

uniapp/uniapp x总结

uni-app组成和跨端原理 上图所诉 App的渲染引擎&#xff1a;同时提供了2套渲染引擎&#xff0c;.vue页面文件由webview渲染&#xff0c;原理与小程序相同&#xff1b;.nvue页面文件由原生渲染&#xff0c;原理与react native相同。开发者可以根据需要自主选择渲染引擎。 uniapp…

【unity小技巧】获取免费开源的人物模型,并为obj fbx人物模型绑定骨骼、动画——mixamo的使用介绍

文章目录 前言地址上传自己的3D角色下载单动画下载动作包角色模型导入Unity动画导入unity设置动画骨骼动画骨骼不配的问题参考完结 前言 其实前面我已经推荐了几种获取人物模型的方法&#xff1a; 1、【unity小技巧】下载原神模型&#xff0c;在Blender中PMX模型转FBX模型&…

多商户商品下单限购问题修复

问题: 当商品设置限购为 1 时,够买数量未超过限购,但是还是提示超出限购数量 修复方法: 修改代码路径: app\common\repositories\store\order\StoreOrderCreateRepository.php 修改代码一: i s p a y s a r r a y u n i q u e ( a r r a y c o l u m n ( is_pays array_un…

Python 设置Excel工作表页边距、纸张大小/方向、打印区域、缩放比例

在使用Excel进行数据分析或报告制作时&#xff0c;页面设置是确保最终输出效果专业、美观的关键步骤。合理的页面设置不仅能够优化打印效果&#xff0c;还能提升数据的可读性。本文将详细介绍如何使用Python操作Excel中的各项页面设置功能。 目录 Python 设置Excel工作表页边…

AutosarMCAL开发——基于EB FEE驱动

这目录 1. FEE原理2.EB配置以及接口应用3.总结 1. FEE原理 在Fls解析文章中介绍了Flash与EEPROM储存器的区别&#xff0c;本文将介绍FEE具体实现原理。 FEE模块&#xff0c;全称Flash EEPROM Emulation Module&#xff0c;旨在使用Flash模拟EEPROM以增加使用寿命。 术语解释 p…

CTFHUB | web进阶 | JSON Web Token | 无签名

一些JWT库也支持none算法&#xff0c;即不使用签名算法。当alg字段为空时&#xff0c;后端将不执行签名验证 开启题目 账号密码随便输&#xff0c;登录之后显示只有 admin 可以获得 flag 在此页面抓包发到 repeater&#xff0c;这里我们需要用到一个 Burp 插件&#xff0c;按图…

瑞吉外卖-登录时报错:接口404异常

一、错误描述 出现“系统接口404异常”的弹窗&#xff0c;同时一直显示登录中&#xff0c;而无法跳转到后台页面。 二、解决方法 1. 检查浏览器的网址 确保为localhost:8080/backend/page/login/login.html&#xff0c;而不是idea自动生成的&#xff0c;修改过来即可。 2.确…

Unity XR Interaction Toolkit 通过两个手柄控制物体放大缩小

1&#xff1a;给物体添加 XR General Grab Transformer 脚本 2&#xff1a;XR Grab Interactable 的 select mode 选择 Multiple

SpringIoCDI

前言&#x1f440;~ 上一章我们介绍了Spring MVC&#xff0c;今天介绍Spring核心功能之一IoC Spring到底是什么&#xff1f; Spring IoC 什么是 IoC 容器&#xff1f; IoC 介绍 DI 介绍 IoC详解 获取Bean对象的其他方式 Bean的存储 方法注解 Bean 扫描路径 DI详解 …

拼图游戏02

文章目录 概要整体架构流程代码过程小结 概要 现在需要将图片添加界面中 关键点在于它如何动态地根据游戏状态更新用户界面。它使用了Swing的布局管理器来定位组件&#xff0c;并且通过ImageIcon和JLabel来显示图像。注意&#xff0c;路径字符串中的反斜杠在Java中是转义字符…

选择排序(直接选择排序和堆排序)

一、直接选择排序 1.基本思想 每一次从待排序的数据元素中选出最小&#xff08;或最大&#xff09;的一个元素&#xff0c;存放在序列的起始位置&#xff0c;直到全部待排序的数据元素排完。 2.动图展示 3.思路讲解 ①在元素集合array[i]—array[n-1]中选择关键码最大&…

以简单的例子从头开始建spring boot web多模块项目(一)

目的&#xff1a;从头梳理&#xff0c;如何手工从头建立多模块项目。 步骤&#xff1a; 1、建立maven项目,类型&#xff1a;maven Archetype&#xff0c;Name:ParentDemo 选择JDK版本&#xff0c;Archetype&#xff1a;org.apache.maven.archetypes:maven-archetype-quickstart…

网络UDP报文详细解析

目录 一、简介二、详细介绍三、其他相关链接1、TCP报文段的详细图总结2、TCP三次握手和四次挥手详解3、socket通信原理及相关函数详细总结4、网络包IP首部详细解析 一、简介 本文主要介绍UDP报文格式。 二、详细介绍 UDP是一种无连接、不可靠的用户数据报协议&#xff0c;其…

《图解设计模式》笔记(四)分开考虑

九、Bridge模式&#xff1a;将类的功能层次结构与实现层次结构分离 类的两个层次结构和作用 类的功能层次结构&#xff1a;希望增加新功能时 父类有基本功能&#xff0c;在子类中增加新功能 Something父类 …├─SomethingGood子类 想要再增加新功能 Something父类 …├─So…

Windows All download

前言 微软家族产品下载HEU_KMS_Activator download Windows PC desktop download 微软官网all 地址&#xff0c;地址1国内镜像地址&#xff0c;地址1 Windows 常规使用&#xff0c;运维&#xff0c;部署csdn 专栏 &#xff0c;付费专栏 参考 版本微软官网Windows 7,8,10,…

hyperf 协程作用和相关的方法

什么是协程 协程是一种轻量级的线程&#xff0c;由用户代码来调度和管理&#xff0c;而不是由操作系统内核来进行调度&#xff0c;也就是在用户态进行 判断当前是否处于协程环境内 在一些情况下我们希望判断一些当前是否运行于协程环境内&#xff0c; 对于一些兼容协程环境与…

使用html-docx-js + fileSaver实现前端导出word

因为html-docx-js是16年的老库了&#xff0c;它代码里面用到的with语法现在严格模式不允许&#xff0c;用npm直接引入会报错&#xff0c;所以我们需要用其它方式引入 首先要将html-docx-js的代码放到项目中 html-docx-js/dist/html-docx.js at master evidenceprime/html-do…

modbus协议与RS-485协议的区别

在工业自动化领域&#xff0c;Modbus协议和RS-485通信协议都是常见且重要的技术标准。Modbus协议是一种通信协议&#xff0c;而RS-485则是一种物理层通信标准。 1.Modbus协议 Modbus协议是一种串行通信协议&#xff0c;最初由Modicon&#xff08;现为施耐德电气公司&#xff0…

智能猫砂盆真的能代替双手铲屎吗?热门前三的智能猫砂盆推荐!

养猫的上班族最大的烦恼应该就是无法时刻为猫咪铲屎了吧&#xff0c;猫砂盆中的便便残留过久会发散臭味&#xff0c;甚至可能滋生细菌&#xff0c;招惹小飞虫&#xff0c;对家庭环境造成困扰&#xff0c;但是上班或出差又无法待在家中&#xff0c;时刻为猫咪待命&#xff0c;以…