[数据结构从小白到大牛]第五篇:3分钟带你吃透双链表并用C语言模拟实现

目录

1->前言

2->链表的概念和结构

2.1链表概念

2.2->带头双向循环链表结构

3->模拟实现带头双向循环链表 

3.1定义链表结点 struct ListNode

3.2创建链表结点 CreateLTNode 函数

3.3链表初始化函数 ListInit函数

3.4链表打印函数 ListPrint函数

3.5链表判空函数 ListEmpty函数 

3.6链表增删改查之尾部插入 ListPushBack 函数

3.7链表增删改查之头部插入 ListPushFront 函数

3.8链表增删改查之尾部删除 ListPopBack 函数

3.9链表增删改查之头部删除 ListPopFront 函数

3.10链表增删改查之查找数据 ListFind 函数

3.11链表增删改查之在pos位置之前插入

3.12链表增删改查之删除pos位置的值

3.13链表增删改查之销毁链表

4->您的专属鼓励师


1->前言

        虽然有这么多的链表的结构,但是我们实际中最常用还是两种结构:
        1. 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

        2. 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了,后面我们代码实现了就知道了。

        上一个篇章我们讲解了无头单向非循环链表,这节我们讲解带头双向循环链表

2->链表的概念和结构

2.1链表概念

        概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的

2.2->带头双向循环链表结构

3->模拟实现带头双向循环链表 

3.1定义链表结点 struct ListNode

        数据域_data        指针域_prev指向前一个结点,_next指向后一个结点

#pragma once
//使用c语言模拟实现双向带头循环链表
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef struct ListNode
{struct ListNode* _prev;//指向前一个结点struct ListNode* _next;//指向后一个结点int _data;			   //存储数据
}LTNode;

3.2创建链表结点 CreateLTNode 函数

        注意:我们的结点动态申请内存在堆上,所以后边释放节点一定要free

//1.创建链表结点
LTNode* CreateLTNode(int num)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc failed");return NULL;}//到这里申请空间成功newnode->_prev = NULL;newnode->_next = NULL;newnode->_data = num;return newnode;
}

3.3链表初始化函数 ListInit函数

        个人总结:任何数据结构或变量在使用之前一定要初始化给予初始值,让他处于一个明确的状态,否则会带来很多未知的错误,会浪费很多时间

//2.链表初始化
LTNode* ListInit()
{LTNode* phead = CreateLTNode(-1);//创建头结点phead->_prev = phead; //让头结点指向自己phead->_next = phead; //让头结点指向自己return phead;
}

3.4链表打印函数 ListPrint函数

        因为我们有头结点,头结点里的数据不算作有效数据不要打印,并且用头结点作为while循环的判断条件

//3.链表打印
void ListPrint(LTNode* phead)
{assert(phead);printf("head<==>");LTNode* cur = phead->_next;//从头结点下一个节点开始有效数据打印while (cur != phead)//cur不是头结点才能进循环{printf("%d<==>", cur->_data);cur = cur->_next;}printf("head\n");
}

3.5链表判空函数 ListEmpty函数 

//4.判断链表是否为空
//为空返回 true,不为空返回 false
bool ListEmpty(LTNode* phead)
{assert(phead);return phead->_next == phead;
}

3.6链表增删改查之尾部插入 ListPushBack 函数

//5.链表尾部插入
void ListPushBack(LTNode* phead, int num)
{assert(phead);//创建新结点并且找到最后一个结点LTNode* newnode = CreateLTNode(num);LTNode* tail = phead->_prev;//修改指针达到尾部插入效果tail->_next = newnode;newnode->_prev = tail;newnode->_next = phead;phead->_prev = newnode;
}

我们写代码测试下是否正确: 

//1.测试双链表尾部插入
void test1()
{LTNode* plist = ListInit();ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);ListPushBack(plist, 4);ListPrint(plist);
}

 看控制台输出:结果正确:

3.7链表增删改查之头部插入 ListPushFront 函数

//6.链表头部插入
void ListPushFront(LTNode* phead, int num)
{assert(phead);//创建新结点并且找到第一个结点LTNode* newnode = CreateLTNode(num);LTNode* next = phead->_next;//修改指针达到插入数据效果phead->_next = newnode;next->_prev = newnode;newnode->_prev = phead;newnode->_next = next;
}

我们写代码测试下是否正确:  

//2.测试双链表头部插入
void test2()
{LTNode* plist = ListInit();ListPushFront(plist, 1);ListPushFront(plist, 2);ListPushFront(plist, 3);ListPushFront(plist, 4);ListPrint(plist);
}

看控制台输出:结果正确:

3.8链表增删改查之尾部删除 ListPopBack 函数

//7.链表尾部删除
void ListPopBack(LTNode* phead)
{//判断链表存在并且有数据才能删除assert(phead);assert(!ListEmpty(phead));//找到最后一个结点和最后一个结点的前一个结点LTNode* tail = phead->_prev;LTNode* prev_tail = tail->_prev;free(tail);//修改指针prev_tail->_next = phead;phead->_prev = prev_tail;
}

 我们写代码测试下是否正确:  

//3.测试双链表尾部删除
void test3()
{LTNode* plist = ListInit();ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);ListPushBack(plist, 4);ListPrint(plist);ListPopBack(plist);ListPopBack(plist);ListPrint(plist);}

 看控制台输出:结果正确:

3.9链表增删改查之头部删除 ListPopFront 函数

//8.链表头部删除
void ListPopFront(LTNode* phead)
{//判断链表存在并且有数据才能删除assert(phead);assert(!ListEmpty(phead));//找到第一个结点和第二个结点LTNode* next = phead->_next;LTNode* next_next = next->_next;//释放头部结点free(next);//修改指针phead->_next = next_next;next_next->_prev = phead;
}

我们写代码测试下是否正确:  

//4.测试双链表头部删除
void test4()
{LTNode* plist = ListInit();ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);ListPushBack(plist, 4);ListPrint(plist);ListPopFront(plist);ListPopFront(plist);ListPrint(plist);}

 看控制台输出:结果正确:

 

3.10链表增删改查之查找数据 ListFind 函数

//9.链表查找数据,简单遍历就行
LTNode* ListFind(LTNode* phead, int num)
{assert(phead);LTNode* cur = phead->_next;while (cur != phead){if (cur->_data == num)return cur;cur = cur->_next;}//到这里表示链表遍历一遍但是仍然没有找到数据,那就返回空return NULL;
}

 我们写代码测试下是否正确:  

//5.测试链表的查找数据
void test5()
{LTNode* plist = ListInit();ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);ListPushBack(plist, 4);ListPrint(plist);LTNode* ptr = ListFind(plist, 3);printf("我查找的数据 : %d",ptr->_data);
}

  看控制台输出:结果正确:

3.11链表增删改查之在pos位置之前插入

//10.在pos之前插入
void LTInsert(LTNode* pos, int x)
{assert(pos);LTNode* prev = pos->_prev;LTNode* newnode = CreateLTNode(x);// prev newnode posprev->_next = newnode;newnode->_prev = prev;newnode->_next = pos;pos->_prev = newnode;
}

3.12链表增删改查之删除pos位置的值

//11.删除pos位置的值
void LTErase(LTNode* pos)
{assert(pos);LTNode* posPrev = pos->_prev;LTNode* posNext = pos->_next;posPrev->_next = posNext;posNext->_prev = posPrev;free(pos);
}

3.13链表增删改查之销毁链表

//12.销毁链表
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->_next;while (cur != phead){LTNode* next = cur->_next;free(cur);//销毁存储有效数据结点cur = next;}//销毁头结点free(phead);
}

4->您的专属鼓励师

        有些事情,你永远都没有办法做到“顶尖”,因为智力跟不上.但是所有的事情,你都可以做到“高段”,因为它需要的是时间的累积和精力的打磨.不聪明与聪明之间的区别,是很微妙的.有时候我们只会通过一次两次的结果,来判断整个人、整件事,其实这是不明智的.从小,邻居和亲戚在谈论我的时候,都会觉得我很聪明。但是只有我自己知道,我从来没有聪明过,只是看上去比较聪明而已.

        修行之路确实枯燥,但是我们把问题搞懂以后就发现他是那样的美妙!一遍学不会没关系吖,多看几遍,我也是学了好多遍呢,小伙伴们肯定学的又快又好!!!最后希望写的内容对小伙伴们有所帮助,我写的如果有哪里不对的地方请在评论区或者私信指出来哦!让我们一起进步吖,任何疑问包括心情不好都可以找我聊聊,我很乐意当你的倾听者吖.     

   

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Rancher的安装

1. 概览 1.1 用户界面优势 Rancher 提供了一个直观的图形用户界面&#xff08;GUI&#xff09;。对于不熟悉 Kubernetes 复杂的命令行操作&#xff08;如使用kubectl&#xff09;的用户来说&#xff0c;通过 Rancher 的界面可以方便地进行资源管理。例如&#xff0c;用户可以在…

【办公类-04-04】华为助手导出照片视频分类(根据图片、视频的文件名日期导入“年-月-日”文件夹中,并转移到“年-月”文件中整理、转移到“年”文件夹中整理)

背景需求 最近带班&#xff0c;没有时间整理照片&#xff0c;偶尔导一次&#xff0c;几个月的照片。发现用电脑版“华为手机助手“中的WLAN连接”与华为手机的“华为手机助手”连接&#xff0c;速度更快、更稳定&#xff0c;不会出现数据线连接时碰碰就断网的问题 1、先打开电…

CDGP|企业数据治理流程全解析

在当今信息化时代&#xff0c;数据已成为企业最重要的资产之一。为了充分发挥数据的价值&#xff0c;企业需要对数据进行全面、系统的治理。企业数据治理流程是一套确保数据质量、安全性和合规性的规范化流程&#xff0c;涵盖了从数据采集到销毁的全过程。本文将详细介绍一般企…

学习threejs,将多个网格合并成一个网格

&#x1f468;‍⚕️ 主页&#xff1a; gis分享者 &#x1f468;‍⚕️ 感谢各位大佬 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍⚕️ 收录于专栏&#xff1a;threejs gis工程师 文章目录 一、&#x1f340;前言1.1 ☘️THREE.Geometry 几何体1.2 …

Linux 线程控制

一. 线程互斥 1.1 线程互斥相关概念 临界资源&#xff1a;多线程执行流共享的资源就叫做临界资源。临界区&#xff1a;每个线程内部&#xff0c;访问临界资源的代码&#xff0c;就叫做临界区。互斥&#xff1a;任何时刻&#xff0c;互斥保证有且只有一个执行流进入临界区&…

Centos安装ZooKeeper教程(单机版)

本章教程介绍,如何在Centos7中,安装ZooKeeper 3.9.3版本。 一、什么是ZooKeeper ? Apache ZooKeeper 是一个分布式协调服务,用于大型分布式系统中的管理和协调。它为分布式应用提供了一个高性能的通信框架,简化了开发人员在构建复杂分布式系统的任务。ZooKeeper 能够解决一…

企业CRM管理系统PHP源码/PHP客户关系CRM客户管理系统源码

系统功能实现 1、 公海管理:公海类型、客户公海。 2、 线索管理:我的线索、线索列表、线索状态、线索来源。 3、 客户管理:我的客户、客户列表、成交客户、行业类别、预查、地区列表、客户状态、客户级别。 4、 业绩订单:订单列表、我的订单。 5、 系统设置:系统设置…

设置JAVA以适配华为2288HV2服务器的KVM控制台

华为2288HV2服务器比较老旧了&#xff0c;其管理控制台登录java配置比较麻烦&#xff0c;华为的ibmc_kvm_client_windows客户端测试了几个版本&#xff0c;连接控制台也有问题&#xff0c;最终安装JDK解决。 一、测试环境 主机为WindowsServer2012R2,64位系统 二、Java软件包…

10大软件使用感受分享,数据恢复的得力助手!!

在找数据恢复软件&#xff1f;&#xff01;是不是存在误删重要文件或遭遇硬盘故障&#xff0c;想要找回丢失的数据&#xff1f;别担心&#xff0c;今天我就来给大家分享10款我亲自使用过的数据恢复软件&#xff0c;分别给你说说它们各自的优缺点&#xff0c;希望能帮你们在数据…

一周模电速成(3) 超详细!入门小白速成!!!

目录 稳压二极管 整流二极管 晶体三极管 三极管结构图 三极管的特点 1、如何让它工作在放大状态呢 2、如何工作在截止状态呢&#xff1f; 3、如何让三极管工作在饱和状态呢&#xff1f; 在电路中要如何实现呢&#xff1f;工作在各个状态有什么特点呢&#xff1f; 截止…

Python的条件语句if与match...case

一、定义 条件语句&#xff0c;也叫作选择语句、判断语句。根绝特定条件判断是否成立&#xff0c;执行不同的语句段。简单来说&#xff0c;满足条件执行&#xff0c;不满足不执行。 条件语句是使用关键字 if 做判断&#xff0c;根据不同情况结合不同的关键字else 或者 elif来…

SpringBoot基础系列学习(二):日志

文章目录 一丶日志控制台介绍二丶日志的用法三丶日志级别四丶配置文件参数及介绍五丶slf4j 一丶日志控制台介绍 只要引用了spring-boot-starter依赖,就无需引入日志依赖,里面自带了logging依赖,默认情况下,springBoot使用Logback来记录日志,并用INFO级别输出到控制台 二丶日…

Bert模型介绍

简介 BERT&#xff08;Bidirectional Encoder Representations from Transformers&#xff09;是一个基于Transformer的双向编码器表示模型&#xff0c;它通过预训练学习到了丰富的语言表示&#xff0c;并可以用于各种自然语言处理任务。 模型结构&#xff1a;BERT基于Transf…

AI驱动无人驾驶:安全与效率能否兼得?

内容概要 如今&#xff0c;人工智能正以其神奇的魔力驱动着无人驾驶的浪潮&#xff0c;带来了无数令人兴奋的可能性。这一领域的最新动态显示&#xff0c;AI技术在车辆的决策过程和实时数据分析中发挥着重要作用&#xff0c;帮助车辆更聪明地应对复杂的交通环境。通过实时监测…

Windows、Linux系统上进行CPU和内存压力测试

CPU和内存压力测试 1. Linux环境 Linux环境下&#xff0c;我们可以用 stress 工具进行内存、CPU等的压力测试。 【1】. stress工具说明 [kalamikysrv1 ~]$ stress --help stress imposes certain types of compute stress on your systemUsage: stress [OPTION [ARG]] ...-…

从零开始的c++之旅——多态

1. 多态的概念 通俗来说就是多种形态。 多态分为编译时多态&#xff08;静态多态&#xff09;和运行时多态&#xff08;动态多态&#xff09;。 编译时多态主要就是我们之前提过的函数重载和函数模板&#xff0c;同名提高传不同的参数就可以调 用不同的函数&#xff0c…

linux node vue3 部署手册

第一步&#xff1a;在linux 系统中安装node 1、在网址&#xff1a;https://nodejs.org/dist/ 下载对应版本的安装包。 2、解压缩下载的压缩包到任意位置&#xff0c;推荐home下。 样例路径为&#xff1a;/home/syl/node-v20.17.0-linux-x64.tar.xz 样例&#xff1a; tar -xv…

探索C/C++的奥秘之string类

string叫串&#xff0c;是一个管理字符数组的类&#xff0c;其实就是一个字符数组的顺序表&#xff0c;通过成员函数对字符串进行增、删、查、改。 C标准库里面的东西都在std这个命名空间中。 int main() { string s1; std:: string s2; std::string name("x…

【刷题】优选算法

优选算法 双指针 202. 快乐数 链接&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 【思路】 第一个实例是快乐数&#xff0c;因为会变为1且不断是1的循环 第二个实例不可能为1&#xff0c;因为会陷入一个没有1的循环 根据两个实例和鸽巢原理可以发现不断的平方和最…

openEuler的aarch64操作系统上安装k3s

1、需要安装docker容器引擎&#xff08;省略&#xff09; 2、安装ks3命令 curl -sfL https://rancher-mirror.rancher.cn/k3s/k3s-install.sh | INSTALL_K3S_MIRRORcn INSTALL_K3S_SKIP_SELINUX_RPMtrue INSTALL_K3S_SELINUX_WARNtrue sh -s -- --docker 其中&#xff1a…