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

前言:

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

概念及结构:

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

注意:

  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.rhkb.cn/news/198988.html

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

相关文章

vue3之echarts区域折线图

vue3之echarts区域折线图

vue3之echarts区域折线图 效果&#xff1a; 核心代码&#xff1a; <template><div class"abnormal"><div class"per">单位&#xff1a;{{ obj.data?.unit }}</div><div class"chart" ref"chartsRef"&g…
阅读更多...
对话芯动科技 | 助力云游戏 4K级服务器显卡的探索与创新

对话芯动科技 | 助力云游戏 4K级服务器显卡的探索与创新

2021年芯动科技推出了基于IMG BXT GPU IP的风华1号显卡。单块风华1号显卡可在台式机和云游戏中实现4K级别的性能&#xff0c;渲染能力达到5 TFLOPS&#xff0c;如果在服务器中同时运行两块显卡&#xff0c;性能还可翻倍。该显卡是为不断扩大的安卓云游戏市场量身定制的&#xf…
阅读更多...
趣学python编程 (四、数据结构和算法介绍)

趣学python编程 (四、数据结构和算法介绍)

数据结构和算法在编程中非常重要。数据结构是组织和存储数据的方式&#xff0c;而算法是解决问题的方法和步骤。你要挑战的蓝桥杯&#xff0c;实际也是在设计算法解决问题。其实各种编程语言都只是工具&#xff0c;而程序的核心数据结构算法。犹如练武&#xff0c;数据结构和算…
阅读更多...
Qt HTTP 摘要认证(海康球机摄像机ISAPI开发)

Qt HTTP 摘要认证(海康球机摄像机ISAPI开发)

接到一个需求是开发下海康的球机,控制云台,给到我的是一个开发手册,当然了是海康的私有协议 ISAPI开发手册https://download.csdn.net/download/qq_37059136/88547425关于开发这块读文档就可以理解了,海康使用的是摘要认证,当然了海康已经给出使用范例 通过libcurl就可以直接连…
阅读更多...
SQL单表复杂查询where、group by、order by、limit

SQL单表复杂查询where、group by、order by、limit

1.1SQL查询代码如下&#xff1a; select job as 工作类别,count(job) as 人数 from tb_emp where entrydate <2015-01-01 group by job having count(job) > 2 order by count(job) limit 1,1where entrydate <‘2015-01-01’ 表示查询日期小于2015-01-01的记录…
阅读更多...
【Flink 问题集】The generic type parameters of ‘Collector‘ are missing

【Flink 问题集】The generic type parameters of ‘Collector‘ are missing

错误展示&#xff1a; Exception in thread "main" org.apache.flink.api.common.functions.InvalidTypesException: The return type of function main(CollectionDemo.java:33) could not be determined automatically, due to type erasure. You can give type in…
阅读更多...
第二证券：今日投资前瞻：小米汽车引关注 全球风光有望持续高速发展

第二证券：今日投资前瞻：小米汽车引关注 全球风光有望持续高速发展

昨日&#xff0c;两市股指盘中轰动上扬&#xff0c;深成指、创业板指一度涨超1%。到收盘&#xff0c;沪指涨0.55%报3072.83点&#xff0c;深成指涨0.72%报10077.96点&#xff0c;创业板指涨0.53%报2015.36点&#xff0c;北证50指数涨2.64%&#xff1b;两市算计成交9900亿元&…
阅读更多...
快速排序知识总结

快速排序知识总结

快速排序思维导图&#xff1a; 快速排序算法模版&#xff1a; #include <iostream>using namespace std;const int N 1e5 10;int n; int q[N];void quick_sort(int q[], int l, int r) {if (l > r) return;int x q[(l r) / 2], i l - 1, j r 1;while (i < …
阅读更多...
2023下半年软件设计师考试知识点大全思维导图

2023下半年软件设计师考试知识点大全思维导图

软件设计师考试知识点大全思维导图 2023年下半年第一次机考 复习资料 以上是我在学习过程中根据自己的知识结构的特点及刷到的考题 做的导图&#xff0c;有需要的可以留言发原版的 mmap格式文件 方便自己拓展. 软考资料 这是网上找的资料 汇总免费放在这里 吧![ 链接&#x…
阅读更多...
数据结构【DS】图的应用

数据结构【DS】图的应用

图的连通性问题 最少边数 最多边数 无向图非连通 &#x1d48e;&#x1d7ce; &#x1d48e;&#x1d48f;−&#x1d7d0;∗(&#x1d48f;−&#x1d7cf;)/&#x1d7d0; 无向图连通 &#x1d48e;&#x1d48f;−&#x1d7cf; &#x1d48e;&#x1d48f;∗(&#…
阅读更多...
springboot使用MongoTemplate根据正则表达式查询日期数据

springboot使用MongoTemplate根据正则表达式查询日期数据

一、日期正则表达式测试 匹配HH:mm:ss正则表达式写法有很多列举两个 .(点)代表任意匹配 ^必须以xxx开头, 如^[a-z],必须以a-z的字母开头 : 精确匹配,必须是: ([0-1]?[0-9]|2[0-3]).([0-5][0-9]).([0-5][0-9]) ^([0-1]?[0-9]|2[0-3]).([0-5][0-9]).([0-5][0-9])$ ([0-1]?…
阅读更多...
小程序游戏、App游戏与H5游戏：三种不同的游戏开发与体验方式

小程序游戏、App游戏与H5游戏：三种不同的游戏开发与体验方式

在当今数字化的时代&#xff0c;游戏开发者面临着多种选择&#xff0c;以满足不同用户群体的需求。小程序游戏、App游戏和H5游戏是三种流行的游戏开发和发布方式&#xff0c;它们各自具有独特的特点和适用场景。 小程序游戏&#xff1a;轻巧便捷的社交体验 小程序游戏是近年来…
阅读更多...
从硬件到软件：揭秘磁盘结构和文件系统组织

从硬件到软件：揭秘磁盘结构和文件系统组织

&#x1f4df;作者主页&#xff1a;慢热的陕西人 &#x1f334;专栏链接&#xff1a;Linux &#x1f4e3;欢迎各位大佬&#x1f44d;点赞&#x1f525;关注&#x1f693;收藏&#xff0c;&#x1f349;留言 本博客主要内容讲解了从磁盘的硬件结构&#xff0c;再到操作系统内部是…
阅读更多...
C语言之深入指针及qsort函数（五）（详解介绍）

C语言之深入指针及qsort函数（五）（详解介绍）

C语言之深入指针 在这篇博客看不懂的可以看看这篇C语言之深入指针&#xff08;四&#xff09;在上篇博客中介绍了&#xff1a; 函数指针变量函数指针数组简易计算器的实现\ 文章目录 C语言之深入指针1 回调函数2 qsort函数的使用2.1 使用冒泡排序排序整型数组2.2 使用qsort函数…
阅读更多...
使用Sqoop命令从Oracle同步数据到Hive，修复数据乱码 %0A的问题

使用Sqoop命令从Oracle同步数据到Hive，修复数据乱码 %0A的问题

一、创建一张Hive测试表 create table test_oracle_hive(id_code string,phone_code string,status string,create_time string ) partitioned by(partition_date string) ROW FORMAT DELIMITED FIELDS TERMINATED BY ,; 创建分区字段partition_date&#xff0c…
阅读更多...
mysqlbinlog使用记录

mysqlbinlog使用记录

首先要确认mysql启用了binlog功能。一般默认启用。 mysql> select log_bin; ----------- | log_bin | ----------- | 1 | ----------- 然后确认binlog目录 mysql> select log_bin_basename; ---------------------------- | log_bin_basename | -----…
阅读更多...
xlua源码分析（三）C#访问lua的映射

xlua源码分析（三）C#访问lua的映射

xlua源码分析&#xff08;三&#xff09;C#访问lua的映射 上一节我们主要分析了lua call C#的无wrap实现。同时我们在第一节里提到过&#xff0c;C#使用LuaTable类持有lua层的table&#xff0c;以及使用Action委托持有lua层的function。而在xlua的官方文档中&#xff0c;推荐使…
阅读更多...
＜b＞＜strong＞,＜i＞＜em＞标签的区别

＜b＞＜strong＞,＜i＞＜em＞标签的区别

1. b标签和strong标签 b标签&#xff1a;仅仅是UI层面的加粗样式&#xff0c;并不具备HTML语义 strong标签&#xff1a;不仅是在UI层面的加粗样式&#xff0c;具备HTML语义&#xff0c;表示强调 2. i标签和em标签 i 标签&#xff1a;仅仅是UI层面的斜体样式&#xff0c;并不…
阅读更多...
Django学习日志08

Django学习日志08

如何开启事务 事务的目的&#xff1a;为了保证多个SQL语句执行成功&#xff0c;执行失败&#xff0c;前后保持一致&#xff0c;保证数据安全 ACID属性&#xff1a; A&#xff1a;原子性&#xff08;Atomicity&#xff09;&#xff1a;指事务是原子的&#xff0c;对事务中的操…
阅读更多...
系统设计之通讯协议

系统设计之通讯协议

一、通讯协议 架构风格定义了应用程序编程接口 (API) 的不同组件如何相互交互。因此&#xff0c;它们通过提供设计和构建 API 的标准方法来确保效率、可靠性以及与其他系统集成的便捷性。以下是最常用的样式&#xff1a; 1. SOAP 成熟、全面、基于XML 最适合于企业应用 可扩展…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023