【数据结构】线性表的链式存储结构

简介: 【数据结构】线性表的链式存储结构

顺序存储结构的不足的解决办法

从上一节我们对顺序表的讨论中可见,线性表的顺序存储结构的特点是:


逻辑关系上相邻的两个元素在物理位置(内存)上也相邻,因此可以随机存取表中任一位置元素,它的存储位置可用一个简单,直观的公式来表示.


然而,从另一方面来看,这个特点也铸成了这种存储结构的弱点:


  • 中间或头部位置进行插入/删除数据操作,需要挪动数据,效率低下
  • 空间不够就需要扩容.扩容有一定的消耗,其次还可能有一定空间浪费.

显然,这样的结构如果碰到数据量庞大并且需要频繁进行头插或中间插入的情况时的操作时间复杂度是极其庞大的.那么如何解决这个问题呢?我们先来思考一下导致这个问题的原因:


为什么当插入和删除时,就需要移动大量元素?仔细分析后,发现原因就在于相邻两元素的存储位置也具有邻居关系.它们编号是1,2,3,...,n,它们在内存中的位置也是挨着的,中间没有空隙,当然就无法快速介入,而删除后,当中就会留出空隙,自然需要弥补.问题就出在这里.


小A:既然问题在于元素之间没有空隙,那我们不如提前在元素之间留出一个空位方便其他元素插入,这样插入一个元素就不用挪动了.

小B:那假如我们要插入2个数据呢?

小A:那我们就留10个空位.

小B:我们要插入11个数据呢?

小A:那我们就留10000个空位!

小B:我们要插入10001个数据呢?

小A:那就不留空位了!大家随便存吧,哪有空位存哪吧!

小B:你说的对!

小A:??????

小B:就是物理上的相邻的特性导致了顺序存储的弱点,那么我们不让它们在物理上不相邻不就可以解决这个问题了.

小A:可是不在物理上相邻了,我们怎么知道下一个数据存在哪呢?

小B:你傻啊,我们存上一个数据的时候顺便存入一个下个结点的地址就可以了嘛.


上面这段对话中小A和小B交流讨论的结果就是我们接下来将要讨论线性表的另一种表示方法——链式存储结构,由于它不要求逻辑上相邻的元素在物理位置上也相邻,因此它没有顺序存储结构所具有的弱点,但同时也失去了顺序表可随机存取的优点.



线性表链式存储结构的定义

线性表的链式存储结构的特点是:

用一组任意的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的.

这就意味着,这些数据元素可以存在内存未被占用的任意位置.

以前在顺序结构中,每个数据元素只需要存储数据元素信息就可以了.现在链式结构中,除了要存储数据元素信息外,还要存储它的后继元素的存储地址.

因此,为了表示每个数据元素 与其直接后继数据元素 之间的逻辑关系,对数据元素 来说,除了存储其本身的信息外,还需存储一个指示其直接后继的信息(即直接后继的存储位置).我们把存储数据元素信息的域称为数据域,把存储直接后继位置的域称为指针域.指针域中存储的信息称作指针或链.这两部分信息组成数据元素 的存储映像,称为结点(Node).

结构图示如下:

n个结点( 的存储映像)链结成一个链表,即为线性表( )的链式存储结构,因为此链表的每个结点中只包含一个指针域,所以叫做单链表.单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起,如下图:

对于线性表来说,总得有个头有个尾,链表也不例外.我们把链表中第一个结点的存储位置叫做头指针,那么整个链表的存取就必须是从头指针开始进行了.之后的每一个结点,其实就是上一个的后继指针指向的位置.想象一下,最后一个结点,它的指针指向哪里?


最后一个,当然就意味着直接后继不存在了,所以我们规定,线性链表的最后一个结点指针为"空"(通常用NULL或"^"符号表示,如下图)



有时,我们为了更加方便地对链表进行操作,会在单链表的第一个结点前附设一个结点,称为头结点.


头结点的数据域可以不存储任何信息,也可以存储如线性表的长度等附加信息,头结点的指针域存储指向第一个结点的指针,如下图所示:


头指针与头结点的异同

头指针

  • 头指针是指链表指向第一个结点的指针,若链表有头结点,则是指向头结点的指针.
  • 头指针具有标识作用,所以常用头指针冠以链表的名字.
  • 无论链表是否为空,头指针均不为空.头指针是链表的必要元素.

无头结点单链表示意图:

无头结点空链表示意图:

头结点

  • 头结点是为了操作的统一和方便而设立的,放在第一元素的结点之前,其数据域一般无意义(也可存放链表的长度).
  • 有了头结点,对在第一元素结点前插入结点和删除第一结点,其操作与其他结点的操作就统一了.
  • 头结点不一定是链表必须要素.

带头结点单链表示意图:

带头结点空链表示意图:

链表的C语言实现

当我们搞明白了线性表的链式存储结构的理论知识后,接下来就需要依据这些理论知识来使用C语言实现单链表了,由于篇幅有限,我会另外再写一篇博客详细阐释用C语言实现单链表的各个步骤以及单链表的完整代码和运行效果都会包含在里面,感兴趣的朋友可以直接点击下方链接跳转到博客:

https://blog.csdn.net/weixin_72357342/article/details/133971550


结语

当我们搞清楚线性表的链式存储结构后,在数据结构线性表篇我们还将一起学习单链表的C语言实现,循环链表,双向链表等相关知识.希望这些内容能对大家有所帮助!欢迎大佬们留言或私信与我交流.学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!



数据结构线性表篇思维导图:


相关文章
|
14天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
57 16
|
1月前
|
存储 安全 数据库
除了 HashMap,还有哪些数据结构可以实现键值对存储?
【10月更文挑战第11天】 除了`HashMap`,其他常见支持键值对存储的数据结构包括:`TreeMap`(基于红黑树,键有序)、`LinkedHashMap`(保留插入顺序)、`HashTable`(线程安全)、`B-Tree`和`B+Tree`(高效存储大量数据)、`SkipList`(通过跳跃指针提高查找效率)及`UnorderedMap`(类似`HashMap`)。选择合适的数据结构需根据排序、并发、存储和查找性能等需求。
|
1月前
|
存储 Java
数据结构第二篇【关于java线性表(顺序表)的基本操作】
数据结构第二篇【关于java线性表(顺序表)的基本操作】
30 6
|
18天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
探索顺序结构:栈的实现方式
探索顺序结构:栈的实现方式
|
1月前
01(数据结构考研)线性表相关操作代码
01(数据结构考研)线性表相关操作代码
59 0
|
1月前
|
存储 算法
【数据结构】二叉树——顺序结构——堆及其实现
【数据结构】二叉树——顺序结构——堆及其实现
|
15天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
90 9
|
6天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
15 1
|
9天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。

热门文章

最新文章