C语言链表详解 & 两类重要链表的实现

简介: 本文详细介绍了链表数据结构,包括链表的非连续、非顺序的物理存储和逻辑顺序通过指针链接的概念。文章以C语言实现链表,并计划更新两种链表(无头单向非循环链表和带头双向循环链表)的代码实现。目前提供了链表的逻辑和物理结构图解,帮助读者理解链表的工作原理,强调了画图在学习数据结构中的重要性。此外,文章指出链表的分类有多种组合形式,并预告将对常用类型的链表进行代码实现。

前言


本文详解对数据结构之链表的理解、链表的两种理解结构与分类以及两种重要链表的代码实现(由于这两类链表的代码实现部分篇幅较长,写在了新的博客文章里,通过链接的方式链入本文)。


本文采用C语言实现数据结构代码


本文将持续维护更新优化,笔者在后续学习种遇到更好的解读、易错点、OJ题讲解等链表相关知识点,也会贴在本贴。希望本文对诸位读者学习链表有所帮助。


提示:预计在3个工作日内更新完那两篇代码详解。更新完毕后这句提示会删除。


一、链表的概念及结构


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

中的 指针链接 次序实现的 。


1.单链表的逻辑结构



2.单链表的物理结构



逻辑结构相对而言比较抽象,一些初学者难以理解,是非常正常的,不必心急。当用逻辑结构想不通时,我们不妨从物理结构开始理解。


当然,在实际的存储中,根本不可能有像逻辑结构中的什么“箭头”指来指去,不同内存单元之间的联系肯定不是通过这些“箭头”产生的。事实上,逻辑结构中“箭头指向”的本质就是指针。你的箭头指向我,实际上是你的指针域中存放的是我的地址。两个原本毫不相干的内存单元,通过指针域中存放的内存地址互相串联起来,形成抽象意义上的链式结构。



思考了一下,想到一个绝妙的比方可以帮助大家理解:



这是网络上的一个“坑人小妙招”,当你看它时,顺着序号到处找。每次提起链表我就会想起这张图。


把上图中每一行文字想象成链表中不同的内存单元。当你从头开始在浏览这些文字时,你其实在做一件事情:遍历链表。然而,每一行文字中都包含了另外某一行的行号。如果没有这些行号,每一行之间毫无关系,看完一行,你会本能地按照顺序看下一行。但有了这些行号,你在看完一行后,不再从上到下看,而是顺着行末的“请看x”去寻找“第x行”。像穿针引线一般,你看完了全部文字(尽管作为一个整人小妙招,里面的文字毫无意义)。


总结一下:每一行文字,相当于内存中独立的内存单元,即链表中的节点;每行行末的“请看x”,相当于节点中的指针域;在跟着这些文字的思路进行阅读的你,即一个遍历链表用的指针(后面会提到)。


初学阶段,在阅读代码或做题时,如果一下子难以get到题意,可以画逻辑结构图或物理结构图。其中物理结构图更加清晰直观,适合我们初学时帮助理解。当熟练以后,就可以用逻辑结构图理解了。


注意:画图是学习数据结构非常重要的一个方法,就像做数学题要随手画图一样。一定要养成随手画图的好习惯!


二、链表的分类与代码实现


实际中链表的结构非常多样。以下情况组合起来有8种链表结构:


1. 单向、双向

2. 带头、不带头(头指哨兵位的头节点)

3. 循环、非循环



其中,最常用的两种是:



接下来,我们重点讲解一下这两类重要的链表结构:无(有)头单向非循环链表以及带头双向循环链表。


三、无头单向非循环链表


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

代码实现与详解另附文章,链接如下:


http://t.csdn.cn/JBt2W


四、带头双向循环链表


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


持续更新中……





                       

相关文章
|
1月前
|
C语言
对链表使用插入排序的C语言实现示例
对链表使用插入排序的C语言实现示例
|
11天前
|
存储
数据结构——双向链表(C语言版)
数据结构——双向链表(C语言版)
10 2
|
11天前
|
算法 C语言
数据结构——单向链表(C语言版)
数据结构——单向链表(C语言版)
13 2
|
17天前
|
存储 C语言 Python
|
18天前
|
存储 C语言
深入解析C语言的动态数据类型单项链表技术
深入解析C语言的动态数据类型单项链表技术
20 0
|
18天前
|
存储 C语言
C语言中处理动态数据类型链表节点冲突的技术探讨
C语言中处理动态数据类型链表节点冲突的技术探讨
22 0
|
23天前
|
测试技术 C语言
如何用C语言实现无头单向非循环链表Single List ?
这篇文档介绍了一个关于单链表数据结构的实现和相关操作。单链表是一种线性数据结构,每个元素(节点)包含数据和指向下一个节点的指针。文档中列出了单链表的图示,并提供了C语言实现单链表的代码,包括动态申请节点、打印链表、头插、尾插、头删、尾删、查找和在特定位置插入或删除节点等函数。 此外,文档还包含了三个测试用例(TestSList1至TestSList4),展示了如何使用这些函数创建、修改和操作单链表。这些测试用例涵盖了插入、删除、查找等基本操作,以及在链表中特定位置插入和删除节点的场景。
22 0
|
25天前
|
算法 C语言
Leetcode_203.移除链表元素—C语言
Leetcode_203.移除链表元素—C语言
|
1月前
|
C语言
链表的插入、删除和查询—C语言
链表的插入、删除和查询—C语言
|
1月前
|
存储 算法 C语言
C语言线性链表
【4月更文挑战第10天】C程序线性链表
25 0