[数据结构从小白到大牛]第五篇: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.xdnf.cn/news/5168.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

心觉：如果做不到“道生一”，能做到“一生道”也不得了

心觉：如果做不到“道生一”，能做到“一生道”也不得了

Hi&#xff0c;我是心觉&#xff0c;带你用潜意识化解各种焦虑、内耗&#xff0c;建立无敌自信&#xff1b;教你财富精准显化的实操方法&#xff1b;关注我,伴你一路成长&#xff01; 每日一省写作222/1000天 想学的东西太多&#xff0c;想练的能力太多&#xff0c;想重塑的负…
阅读更多...
基于BP神经网络的手写体数字图像识别

基于BP神经网络的手写体数字图像识别

基于BP神经网络的手写体数字图像识别 摘要 在信息化飞速发展的时代&#xff0c;光学字符识别是一个重要的信息录入与信息转化的手段&#xff0c;其中手写体数字的识别有着广泛地应用&#xff0c;如&#xff1a;邮政编码、统计报表、银行票据等等&#xff0c;因其广泛地应用范围…
阅读更多...
SpringBoot项目中获取resources下静态文件时遇到的坑

SpringBoot项目中获取resources下静态文件时遇到的坑

文章目录 问题解决方法1. 上传到服务器指定的文件夹下2. 使用ClassPathResource读取 问题 在项目中需要使用到静态图片&#xff0c;将静态图片放在resources文件夹下。 本地使用this.getClass().getResource()读取静态图片一切正常&#xff0c;成功读取到静态图片。但是将项目…
阅读更多...
树莓派AI视觉小车——2.小车蜂鸣器控制实验

树莓派AI视觉小车——2.小车蜂鸣器控制实验

如下图所示&#xff0c;蜂鸣器为板载元器件&#xff0c;所以不需要外接其他设备。 将机器人打开电源开机&#xff0c;运行程序代码即可。 import RPi.GPIO as GPIO import timeBuzzer 11CL [0, 131, 147, 165, 175, 196, 211, 248] # Frequency of Low C notes CM [0, 262…
阅读更多...
【C++刷题注意事项】bfs？单源bfs？多源bfs？bfs解决拓扑排序？

【C++刷题注意事项】bfs？单源bfs？多源bfs？bfs解决拓扑排序？

一、bfs是个什么&#xff1f; 简单而言bfs就是个广度优先遍历&#xff0c;其根本就是我把与跟我当前点相邻的题目中所要求的点都统计出来并进行处理&#xff0c;再去遍历下一个满足的点的邻接的点的信息即可&#xff0c;最大的优势就是只需要不停的入队和出队即可。 那么我们就…
阅读更多...
三、Java并发 Java 线程池 ( Thread Pool )

三、Java并发 Java 线程池 ( Thread Pool )

一、前言 本文我们将讲解 Java 中的线程池 ( Thread Pool )&#xff0c;从 Java 标准库中的线程池的不同实现开始&#xff0c;到 Google 开发的 Guava 库的前世今生 注&#xff1a;本章节涉及到很多前几个章节中阐述的知识点。我们希望你是按照顺序阅读下来的&#xff0c;不然…
阅读更多...
string模拟实现迭代器

string模拟实现迭代器

个人主页&#xff1a;Jason_from_China-CSDN博客 所属栏目&#xff1a;C系统性学习_Jason_from_China的博客-CSDN博客 所属栏目&#xff1a;C知识点的补充_Jason_from_China的博客-CSDN博客 string模拟实现迭代器 迭代器的实现 主要实现的两种迭代器 这里我们实现迭代器我们主要…
阅读更多...
推荐一款C盘清理工具：360清理Pro

推荐一款C盘清理工具：360清理Pro

360清理Pro是一款专门用于解决电脑C盘空间不足问题的清理工具。它旨在简化C盘清理过程&#xff0c;让用户能够轻松释放磁盘空间&#xff0c;提高电脑性能。与其它版本不同&#xff0c;这个独立版的360清理Pro无需依赖360安全卫士&#xff0c;是一个独立运行的工具。 软件特点 …
阅读更多...
《scientific discovery in the age og artificial intelligence》文献阅读翻译

《scientific discovery in the age og artificial intelligence》文献阅读翻译

人工智能时代的科学发现 人工智能&#xff08;AI&#xff09;正日益被整合到科学发现中&#xff0c;以增强和加速研究&#xff0c;帮助科学家生成假设、设计实验、收集和解释大数据集&#xff0c;并获得使用传统科学方法可能无法获得的见解。在此&#xff0c;我们探讨了过去十…
阅读更多...
字节青训-小D的 abc 变换问题

字节青训-小D的 abc 变换问题

问题描述 小D拿到了一个仅由 "abc" 三种字母组成的字符串。她每次操作会对所有字符同时进行以下变换&#xff1a; 将 a 变成 bc将 b 变成 ca将 c 变成 ab 小D将重复该操作 k 次。你的任务是输出经过 k 次变换后&#xff0c;得到的最终字符串。 例如&#xff1a;对于初…
阅读更多...
Air780E基于LuatOS编程开发

Air780E基于LuatOS编程开发

Air780E基于LuatOS编程开发 Air780E开发板下载固件版本开发板刷机开发调试 Air780E开发板 合宙通信推出的 LTE Cat.1 bis通信模块&#xff0c;采用移芯EC618平台&#xff0c;支持4G全网通, 包括的模组有: Air780E – 4G Cat.1Air780EG – Air780EAir510U,支持GNSS/GPS卫星定位…
阅读更多...
Chrome与火狐哪个浏览器的移动版本更流畅

Chrome与火狐哪个浏览器的移动版本更流畅

在当今的数字化时代&#xff0c;移动设备已经成为我们生活中不可或缺的一部分。而浏览器作为我们访问互联网的重要工具&#xff0c;其性能和用户体验直接影响到我们的使用感受。本文将对比Chrome和火狐&#xff08;Firefox&#xff09;两款主流浏览器的移动版本&#xff0c;探讨…
阅读更多...
深度学习-pytorch安装与基本使用

深度学习-pytorch安装与基本使用

一. 基本介绍 Pytorch概念 PyTorch是一个开源机器学习和深度学习框架。PyTorch 允许您使用 Python 代码操作和处理数据并编写深度学习算法&#xff0c;能够在强大的GPU加速基础上实现张量和动态神经网络。 PyTorch是一个基于 Python 的科学计算包&#xff0c;使用 Tensor 作为…
阅读更多...
HCIP-HarmonyOS Application Developer V1.0 笔记（五）

HCIP-HarmonyOS Application Developer V1.0 笔记（五）

弹窗功能 prompt模块来调用系统弹窗API进行弹窗制作。 当前支持3种弹窗API&#xff0c;分别为&#xff1a; 文本弹窗&#xff0c;prompt.showToast&#xff1b;对话框&#xff0c;prompt.showDialog&#xff1b;操作菜单&#xff0c;prompt.showActionMenu。 要使用弹窗功能&…
阅读更多...
[极客大挑战 2019]EasySQL 1

[极客大挑战 2019]EasySQL 1

[极客大挑战 2019]EasySQL 1 观察题目&#xff0c;发现为登录界面&#xff0c;判断这道题的考点是SQL注入。 知识点 万能密码 知识点原理 当用户尝试登录时 网站后台会进行SQL查询&#xff0c;比如 【select * from table_name where username‘xxxx’ and password‘xxxx…
阅读更多...
42.第二阶段x86游戏实战2-lua寻找状态指针

42.第二阶段x86游戏实战2-lua寻找状态指针

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 本次游戏没法给 内容参考于&#xff1a;微尘网络安全 本人写的内容纯属胡编乱造&#xff0c;全都是合成造假&#xff0c;仅仅只是为了娱乐&#xff0c;请不要…
阅读更多...
leetcode：杨辉三角

leetcode：杨辉三角

题目链接 class Solution { public:vector<vector<int>> generate(int numRows) {vector<vector<int>> vv(numRows);//生成一个长度为5&#xff0c;元素为vector<int>的顺序表for (int i 0; i < numRows; i)//对生成的顺序表初始化&#xff…
阅读更多...
flutter 写个简单的界面

flutter 写个简单的界面

起因&#xff0c; 目的: 来源: 客户需求。 着急要&#xff0c;我随便写的&#xff0c;应付一下。 过程: 略&#xff0c;直接看代码&#xff0c;看注释。 代码 1 xxx import package:flutter/material.dart;void main() {runApp(const MyApp()); }// # class MyApp extends…
阅读更多...
030集——分组法——C# CAD二次开发

030集——分组法——C# CAD二次开发

重叠的图行进行分组&#xff0c;效果如下&#xff1a; 纵向投影重叠&#xff08;横向移动冲突&#xff09;可以分组: 纵向冲突也可以分组&#xff1a; 也可根据颜色不同分组&#xff1a; 部分代码如下&#xff0c;完整代码见文章下方名片 public class Class1{[CommandMethod(…
阅读更多...
java就近原则与this用法 C语言字符串与指针

java就近原则与this用法 C语言字符串与指针

1. &#xff08;1&#xff09; public class girlfriend{ String name; double high; String face; String age; //在方法里面是局部变量&#xff0c;在方法外面是成员变量public void setName(String name) {this.namename;}public String getName(){return name;}public vo…
阅读更多...
最新文章

Copyright @ 2022~2023