[C/C++]数据结构 链表(单向链表,双向链表)

news/2024/4/19 16:43:42/

前言:

        上一文中我们介绍了顺序表的特点及实现,但是顺序表由于每次扩容都是呈二倍增长(扩容大小是自己定义的),可能会造成空间的大量浪费,但是链表却可以解决这个问题.

概念及结构:

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

注意:

  1. 链式结构在逻辑上是连续的,但是在物理上不一定连续
  2. 结点一般都是从堆上申请出来的
  3. 从堆上申请的空间是按照一定的策略来分配的,两次申请的空间可能连续也可能不连续

    分类:

  1. 单向或双向
  2. 带头或不带头
  3. 循环或不循环

    虽然链表有这么多种结构,但是在实际中最常用的还是两种结构:

  • 无头单向非循环链表:

          结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈       希桶、图的邻接表等等。       

  •  带头双向循环链表:

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

无头单向非循环链表

接口:

typedef int SLTDateType;
typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SListNode;// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode** pphead,SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode** pphead,SListNode* pos);
// 在pos的前面插入
SListNode* SListInsertFront(SListNode** pphead, SListNode* pos, SLTDateType x);
// 删除pos位置
void SLTErase(SListNode** pphead, SListNode* pos);
//单链表摧毁
void SLTDestroy(SLNode** pphead);

1.动态申请结点

SListNode* BuySListNode(SLTDateType x)
{SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (newnode == NULL){perror("malloc");return;}newnode->data = x;newnode->next = NULL;
}

2.单链表打印

void SListPrint(SListNode* plist)
{SListNode* cur = plist;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}

3.单链表尾插

void SListPushBack(SListNode** pplist, SLTDateType x)
{SListNode* newnode = BuySListNode(x);if (*pplist == NULL){*pplist = newnode;}else{SListNode* tail = *pplist;while (tail->next){tail = tail->next;}tail->next = newnode;}
}

4.单链表头插

void SListPushFront(SListNode** pplist, SLTDateType x)
{SListNode* newnode = BuySListNode(x);newnode->next = *pplist;*pplist = newnode;
}

5.单链表尾删

void SListPopBack(SListNode** pplist)
{assert(*pplist);SListNode* pre = NULL;SListNode* tail = *pplist;if ((*pplist)->next == NULL){*pplist = NULL;}else{/* while (tail->next){pre = tail; tail = tail->next;}free(tail);tail = NULL;pre->next = NULL;*/SListNode* tail = *pplist;while (tail->next->next){tail = tail->next;}free(tail->next);tail->next = NULL;} 
}

6.单链表头删

void SListPopFront(SListNode** pplist)
{assert(pplist);if ((*pplist)->next == NULL){*pplist = NULL;}else{SListNode* ret = ((*pplist)->next);free(*pplist);*pplist = ret;}
}

7.单链表查找

SListNode* SListFind(SListNode* plist, SLTDateType x)
{assert(plist);SListNode* ret = plist;while (ret->data != x&&ret->next){ret=ret->next;}if (ret->next == NULL && ret->data != x)return NULL;elsereturn ret; 
}

8.摧毁单链表

void SLTDestroy(SListNode** pphead)
{SListNode* cur = *pphead;SListNode* ret = NULL;while (cur){ret = cur->next;free(cur);cur = ret;}*pphead = NULL;
}

9.在pos位置之后插入x

// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode** pphead,SListNode* pos, SLTDateType x)
{assert(pphead);//检测插入位置是否存在assert(pos); assert(*pphead);SListNode* newnode=BuySListNode(x);newnode->next = pos->next;pos->next = newnode;
}

10.删除pos位置之后的值

// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode** pphead,SListNode* pos)
{assert(pphead);assert(pos);assert(pos->next);assert(*pphead);SListNode* tmp = pos->next;pos->next = pos->next->next;free(tmp);tmp = NULL;
}

11.在pos位置之前插入x

SListNode* SListInsertFront(SListNode** pphead, SListNode* pos, SLTDateType x)
{assert(pphead);assert(pos);assert(*pphead);SListNode* newnode = BuySListNode(x);SListNode* pre = *pphead;if (*pphead == pos){SListPushFront(pphead,x);}else{while (pre->next != pos){pre = pre->next;}newnode->next = pos;pre->next = newnode;}}

12.删除pos位置

void SLTErase(SListNode** pphead, SListNode* pos)
{assert(pphead);assert(pos);assert(*pphead);if (*pphead == pos){SListPopFront(pphead);}else{SListNode* pre = *pphead;while (pre->next != pos){pre = pre->next;}pre->next = pos->next;free(pos);pos = NULL;}}

 

带头双向循环链表

接口:

// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{LTDataType _data;struct ListNode* _next;struct ListNode* _prev;
}ListNode;// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* pHead);
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* pHead);
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* pHead);
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);

1.创建返回链表的头节点

ListNode* ListCreate(LTDataType x)
{ListNode* node = (ListNode*)malloc(sizeof(ListNode));if (node == NULL){perror("malloc");exit(-1);}node->_data = x;node->_next = NULL;node->_prev = NULL;return node;
}

2.双向链表销毁

void ListDestory(ListNode* pHead)
{assert(pHead);ListNode* cur = pHead->_next;while (cur != pHead){ListNode* next = cur->_next;free(cur);cur = next;}free(pHead);
}

3.双向链表打印

void ListPrint(ListNode* pHead)
{assert(pHead);ListNode* cur = pHead->_next;while (cur != pHead){printf("%d <-> ", cur->_data);cur = cur->_next;}
}

4.双向链表尾插

void ListPushBack(ListNode* pHead, LTDataType x)
{ListNode* newnode = ListCreate(x);ListNode* tail = pHead->_prev;     //尾指针tail->_next = newnode;newnode->_next = pHead;newnode->_prev = tail;pHead->_prev = newnode;
}

5.双向链表尾删

void ListPopBack(ListNode* pHead)
{assert(pHead);assert(pHead->_next!=pHead);ListNode* tail = pHead->_prev;pHead->_prev = tail->_prev;tail->_prev->_next = pHead;free(tail);tail = NULL;
}

6.双向链表头插

void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* newnode = ListCreate(x);newnode->_next = pHead->_next;pHead->_next->_prev = newnode;pHead->_next = newnode;newnode->_prev = pHead;
}

7.双向链表头删

void ListPopFront(ListNode* pHead)
{ListNode* pHeadNext = pHead->_next;pHeadNext->_next->_prev = pHead;pHead->_next = pHeadNext->_next;free(pHeadNext);pHeadNext = NULL;
}

8.双向链表查找


ListNode* ListFind(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* cur = pHead->_next;while (cur != pHead){if (cur->_data == x)return cur;cur = cur->_next;}return NULL;
}

9.双向链表在pos的前面进行插入

void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* posprev = pos->_prev;ListNode* newnode = ListCreate(x);newnode->_next = pos;pos->_prev = newnode;posprev->_next = newnode;newnode->_prev = pos->_prev;
}

10.双向链表删除pos位置的节点

void ListErase(ListNode* pos)
{assert(pos);ListNode* posprev = pos->_prev;ListNode* posnext = pos->_next;posprev->_next = posnext;posnext->_prev = posprev;free(pos);
}


http://www.ppmy.cn/news/1225161.html

相关文章

基于单片机音乐弹奏播放DS1302万年历显示及源程序

一、系统方案 1、本设计采用51单片机作为主控器。 2、DS1302计时显示年月日时分秒。 3、按键可以弹奏以及播放音乐&#xff0c;内置16首音乐。 二、硬件设计 原理图如下&#xff1a; 三、单片机软件设计 1、首先是系统初始化 /时钟显示**/ void init_1602_ds1302() { write…

策略模式在数据接收和发送场景的应用(升级版)

1.背景 在数据接收和发送场景打算使用了 if else 进行判断&#xff1a; if("A".equals(system)){ASystem.sync("向A同步数据"); } if("B".equals(system)){BSystem.sync("向B同步数据"); } ... 非常麻烦&#xff0c;需求多了很臃肿&…

Git企业开发级讲解(三)

&#x1f4d8;北尘_&#xff1a;个人主页 &#x1f30e;个人专栏:《Linux操作系统》《经典算法试题 》《C》 《数据结构与算法》 ☀️走在路上&#xff0c;不忘来时的初心 文章目录 一、版本回退1、内容2、演示 二、撤销修改1、情况⼀&#xff1a;对于⼯作区的代码&#xff0c…

DOA估计算法——Capon算法

1.波速形成基本思想 在理解Capon算法之前&#xff0c;我们有必要先了解波束形成的基本思想以及原理到底是什么。这有助于我们更好的理解Capon算法的思想。 图 1 如图1展示了均匀阵列波束导向的示意图。图中wm表示加权值&#xff0c;波速形成(DBF)的基本思想就是将各阵元输出进…

PS学习笔记——图层

文章目录 图层面板图层类型新建图层新建方式图层颜色 操作图层修改图层名称选中图层隐藏图层调整图层顺序复制图层 图层面板 按F7可打开/关闭图层面板 该面板就是图层面板了 对所有图层进行筛选的按钮&#xff0c;第一个搜索框可以选择按什么方式进行筛选&#xff0c;支持&am…

简单算法——回溯、贪心、动态规划

回溯法 回溯法深度优先剪枝&#xff0c;实质就是用递归代替for循环。 仍然是一种暴力遍历的手段&#xff0c;通常与递归配合使用&#xff0c;用于解决单纯for循环无法处理的问题&#xff0c;比如组合、切割、子集、排列等问题——比如求n个数里的长度为k的组合&#xff0c;需要…

JS 防抖封装方法

防抖封装方法&#xff1a; /*** param {Function} func* param {number} wait* param {boolean} immediate* return {*}*/ export function debounce(func, wait, immediate) {let timeout, args, context, timestamp, resultconst later function () {// 据上一次触发时间间隔…

Linux/麒麟系统上部署Vue+SpringBoot前后端分离项目

目录 1. 前端准备工作 1.1 在项目根目录创建两份环境配置文件 1.2 环境配置 2. 后端准备工作 2.1 在项目resources目录创建两份环境配置文件 2.2 环境配置 3. 前后端打包 3.1 前端打包 3.2 后端打包 4、服务器前后端配置及部署 4.1 下载、安装、启动Nginx 4.2 前端项目部署…

Ubuntu搭建FTP服务

在Ubuntu上配置FTP服务通常使用vsftpd&#xff08;Very Secure FTP Daemon&#xff09;是一种常见的选择。以下是在Ubuntu上配置vsftpd的基本步骤&#xff1a; 步骤 1&#xff1a;安装vsftpd 打开终端&#xff0c;并运行以下命令以安装vsftpd&#xff1a; sudo apt-get upda…

IEEE Standard for SystemVerilog Chapter 22. Compiler directives

22.1 General 此子句描述以下编译器指令&#xff08;按字母顺序列出&#xff09;&#xff1a; __FILE__ [22.13] __LINE__ [22.13] begin_keywords [22.14] celldefine [22.10] default_net…

PTP软硬件时间戳

软硬件时间戳 抄袭来源&#xff1a;http://www.bdtime.com.cn/pinlv/4296.html PTP 是一种网络协议&#xff0c;用于在计算机网络中进行时钟校准和时间同步。硬件时间戳和软件时间戳是在实现 PTP 时常见的两种方式&#xff0c;它们在精度、可靠性、实时性以及资源消耗等方面存…

C++标准模板库(STL)-list介绍

C标准模板库&#xff08;STL&#xff09;中的list是一个双向链表&#xff0c;它提供了高效的插入、删除和反转操作。list支持随机访问&#xff0c;这意味着我们可以直接访问任何元素&#xff0c;而不需要从头开始遍历链表。此外&#xff0c;list还支持反向迭代&#xff0c;即可…

face_recognition:高准确率、简单易用的人脸识别库 | 开源日报 No.79

ageitgey/face_recognition Stars: 49.8k License: MIT 这个项目是一个使用 Python 编写的人脸识别库&#xff0c;可以从图片中识别和操作人脸。它基于 dlib 开发&#xff0c;并采用深度学习技术构建了最先进的人脸识别模型&#xff0c;在 Labeled Faces in the Wild 数据集上…

java类型属性set方法无法被赋值

前言 遇到一个基础的问题 方法设置属性值 失败 问题代码 有个内部类的User对象 分别使用 方式一和 方式二 设置User的属性值 发现方式一的属性并不能被设置成功 可以自行测试下 public class Test{public static void main(String[] args) {#方式一 User user new User();u…

echarts 实现tooltip提示框样式自定义

实现echarts图提示框自定义样式&#xff0c;最重要的是给tooltip加一个自定义class&#xff0c;下面是我写的例子&#xff1a; tooltip: {trigger: "axis",axisPointer: {type: "line",},className: "custom-tooltip-box",formatter: function …

数据库迁移(DBeaver版本)

最近需要做一个数据库迁移&#xff0c; 测试环境开发的差不多了&#xff0c;需要将脚本迁移到生产。 中间了试了一些工具&#xff0c;比如Jetbrain出品的datagrip&#xff0c;这个数据库工具平时还是很好用的&#xff0c;但是数据迁移感觉不是那么好用&#xff0c;所以还是用到…

【深度学习实验】网络优化与正则化(六):逐层归一化方法——批量归一化、层归一化、权重归一化、局部响应归一化

文章目录 一、实验介绍二、实验环境1. 配置虚拟环境2. 库版本介绍 三、优化算法0. 导入必要的库1. 随机梯度下降SGD算法a. PyTorch中的SGD优化器b. 使用SGD优化器的前馈神经网络 2.随机梯度下降的改进方法a. 学习率调整b. 梯度估计修正 3. 梯度估计修正&#xff1a;动量法Momen…

【SA8295P 源码分析 (三)】129 - GMSL2 协议分析 之 Video Frame 帧数据结构分析 PCLK 计算公式

【SA8295P 源码分析】129 - GMSL2 协议分析 之 Video Frame 帧数据结构分析 & PCLK 计算公式 一、GMSL2 Video Frame 数据分析1.1 视频帧数据结构组成1.2 PCLK 计算公式系列文章汇总见:《【SA8295P 源码分析 (三)】Camera 模块 文章链接汇总 - 持续更新中》 本文链接:《【…

测试开发环境下centos7.9下安装docker的minio

按照以下方法进行 1、安装docker&#xff0c;要是生产等还是要安装docker-ce yum install docker 2、启动docker service docker start 3、 查看docker信息 docker info 4、加到启动里 systemctl enable docker.service 5、开始docker pull minio/minio 但报错&#x…

直播间停留人气的10种方法

**一、背景介绍** 随着互联网的发展&#xff0c;直播已经成为一种重要的社交和营销方式。直播间的人气是影响直播效果的重要因素之一&#xff0c;直接影响观众的参与度和转化率。本文将介绍如何通过10种方法提高直播间停留人气。 **二、方法与技巧** 1. **优质内容**&#x…