线性表链式存储结构的由来与基本概念

开始学习链表
服务器君一共花费了223.102 ms进行了7次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议
  • 在前面《线性表顺序存储的优缺点》里面我们谈到了线性表的一些不足,最大的缺点就是插入和删除时需要移动大量元素,在线性表比较大的时候采用顺序存储很是不方便,效率低。
  • 那么有什么办法可以解决线性表在插入与删除操作中效率低的问题呢?先思考下效率低的原因。

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

知道了原因,就有了一些解决的思路。

思路一:让当中毎个元素之间都留有一个空位置,这样要插入时,就不至于移动。可一个空位置如何解决多个相同位置插入数据的问题呢?所以这个想法显然不行。

思路二:那就让当中每个元素之间都留足够多的位置,根据实际情况制定空隙大小,比如10个,这样插入时,就不需要移动了。万一 10个空位用完了,再考虑 移动使得每个位置之间都有10个空位置。如果删除,就直接删掉,把位置留空即可。这样似乎暂时解决了插入和删除的移动数据问题,可这对于超过10个同位置数 据的插入,效率上还是存在问题。对于数据的遍历,也会因为空位置太多而造成判断时间上的浪费。而且显然这里空间复杂度还增加了,因为毎个元素之间都有若干个空位置。

思路三:我们反正也是要让相邻元素间留有足够余地,那干脆所有的元素都不要考虑相邻位置了,哪有空位就到哪里,而只是让每个元素知道它下一个元素的位 置在哪里,这样,我们可以在第一个元素时,就知道第二个元素的位置(内存地址), 而找到它;在第二个元素时,再找到第三个元素的位置(内存地址)这样所有的元素我们就都可以通过遍历而找到。

思路三,正是线性表链式存储结构的产生思路。

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的。这就意味着,这些数据元素可以存在内存未被占用的任意位置,比如下图:

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

链表的一些基本概念

为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系,对数据元素ai来说,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息(即直接后继的存储位置)。

  • 数据域:我们把存储数据元素信息的域称为数据域。
  • 指针域:存储直接后继位置的域称为指针域。
  • 指针/链:指针域中存储的信息称做指针或链。
  • 结点(Node):数据域与指针域这两部分信息组成数据元素ai的存储映像,称为结点(Node)
  • 我明白单链表名字的由来了。n个结点(ai的存储映像)链结成一个链表,即为线性表(ai, a2…,an)的链式存储结构,因为此链表的每个结点中只包含一个指针域。因为指针域中存储的信息称做链,而且这个链每个结点都只有一个,所以叫做单链表吧。

延伸阅读

此文章所在专题列表如下:

  1. 第01话:线性表的概念与定义
  2. 第02话:线性表的抽象数据类型ADT定义
  3. 第03话:线性表的顺序存储结构
  4. 第04话:线性表的初始化
  5. 第05话:线性表的遍历、插入操作
  6. 第06话:判断线性表是否为空与置空操作
  7. 第07话:线性表的查找操作
  8. 第08话:线性表删除某个元素
  9. 线性表顺序存储的优缺点
  10. 线性表链式存储结构的由来与基本概念
  11. 单链表的头指针、头结点与首元结点
  12. 单链表的结构体定义与声明
  13. 单链表的初始化
  14. 单链表的插入与遍历操作
  15. 单链表的删除某个元素的操作
  16. 获取单链表中的指定位置的元素
  17. 查找某数在单链表中的位置
  18. 用头插法实现单链表整表创建
  19. 用尾插法实现单链表整表创建
  20. 将单链表重置为空表
  21. 单链表反转/逆序的两种方法
  22. 单链表反转/逆序的第三种方法
  23. 求单链表倒数第N个数
  24. 用标尺法快速找到单链表的中间结点
  25. 如何判断链表是否有环的存在
  26. 单链表建环,无环链表变有环
  27. 删除单链表中的重复元素

本文地址:http://www.nowamagic.net/librarys/veda/detail/2219,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/2219

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《PHP经典实例(第2版)》 斯克拉(David Sklar) (作者), 切贝特伯格(Adam Tracbtenberg) (作者), 李松峰 (译者), 秦绪文 (译者), 李丽 (译者)

PHP经典实例(第2版)能够为您节省宝贵的Web开发时间。有了这些针对真实问题的解决方案放在手边,大多数编程难题都会迎刃而解。《PHP经典实例(第2版)》将PHP的特性与经典实例丛书的独特形式组合到一起,足以帮您成功地构建跨浏览器的Web应用程序。在这个修订版中,您可以更加方便地找到各种编程问题的解决方案,《PHP经典实例(第2版)》中内容涵盖了:表单处理;Session管理;数据库交互;使用Web服务。

更多计算机宝库...