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

news/2025/4/26 13:04:02/

前言:

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

概念及结构:

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

注意:

  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万年历显示及源程序

基于单片机音乐弹奏播放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企业开发级讲解（三）

Git企业开发级讲解（三）

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

DOA估计算法——Capon算法

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

PS学习笔记——图层

文章目录 图层面板图层类型新建图层新建方式图层颜色 操作图层修改图层名称选中图层隐藏图层调整图层顺序复制图层 图层面板 按F7可打开/关闭图层面板 该面板就是图层面板了 对所有图层进行筛选的按钮&#xff0c;第一个搜索框可以选择按什么方式进行筛选&#xff0c;支持&am…
阅读更多...
简单算法——回溯、贪心、动态规划

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

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

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前后端分离项目

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 前端项目部署…
阅读更多...
最新文章

Copyright @ 2022~2023