数据结构|总结线性表的几种存储结果

深藏阁楼爱情的钟 2022-06-07 05:16 244阅读 0赞

一、顺序存储结构——顺序表

顺序表是用一段地址连续的存储单元依次存储线性表的数据元素。所以通常用数组来存储线性表，用数组存放，这意味着我们要确定数组的长度，分配固定长度的数组空间。

①特点：内存中地址连续，支持随机查找，按位查找算法的时间复杂度为O（1），按值查找的平均时间性能是O（n），插入删除操作的平均时间性能是O（n），适用于需要大量访问元素，而没有或少量增添或删除元素的程序。

②优点：随机访问较快，创建简单。

③缺点：插入和删除需要移动大量的元素；表的容量难以确定；造成存储空间的“碎片”等。

二、链接存储结构

1.单链表

单链表是用一组任意的存储单元存放线性表的元素，无需事先分配存储空间。

①特点：每一个结点有着数据域和指针域，指针域指向下一个结点。单链表是顺序存放，所以查询时的的平均时间性能是O（n），插入删除操作的平均时间性能是O（n），试用于需要大量进行增添或删除元素，而对访问元素无要求的程序（以下的循环链表、双链表同，不一一详述）

②优点：结构简单，存储空间小，能动态存储分配，插入和删除也无需移动元素，效率高。

③缺点：只能向前访问节点，查找存取效率低。

2.循环链表

循环链表是在单链表的基础上，将终端结点的指针域由空指针改为指向头结点，使得整个单链表形成一个环，即为循环链表。

①特点：基本操作的实现与单链表类似，但从链表的任一结点出发，可扫描到其他结点，增加了链表操作的灵活性。

②优点：无须增加存储量，从循环链表中任一结点出发，就可扫描到其他结点，可使得表处理更加方便灵活。

③缺点：相比单链表，循环链表中没有明显的尾端，容易造成死循环，需要格外注意循环条件。

3.双向链表

双向链表它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。

①特点：从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

②优点：可以在当前结点前面或者后面插入，可以删除前驱和后继（包括结点自己），相比单链表，双联表能更快速确定表中任一结点的前驱结点。

③缺点：相比单链表，多了前驱指针域，加大了在结构上内存开销。

三、其他存储方法

1.静态链表

静态链表是用数组来表示单链表，用数组元素的下标来模拟单链表的指针。

①特点：每个数组元素由两个域组成：data域存放数据元素，next域存放该元素的后继元素所在的数组下标，即“模拟链表”

②优点：便于数据的插入和删除操作，只需要修改游标，不需要移动表中的元素，从而改进了插入和删除操作需要移动大量元素的缺点

③缺点：没有解决连续存储分配带来的表长难以确定的问题

2.间接寻址

间接寻址是将数组和指针结合起来的一种方法。

其特点是：将数组中存储数据元素的单元改为存储指向该元素的指针，它将数组中存储数据元素的单元改为存储指向该元素的指针。

①优点：保持了顺序表随机存取的优点，同时改进了插入和删除操作的时间性能

②缺点：没有解决连续存储分配带来的表长难以确定的问题

四、总结

本次实验内容总的来说有点多，与我而言在实验过程中也遇到了许多困难。从一开始的无从下手，到编译时遇到的一些bug，再到有时无法运行，许多难点都已经打击了我的自信心。俗话说“少少苦楚等于激励”，哪有不会遇到任何困难的事情？重要的是遇到挫折后重新出发。于是遇到bug会主动去网上搜索教程、查找错误，也会参考一些别人的代码，看看和自己的有何不同，再思考其中的道理。

整个实验完成后，我收获颇丰，往后我会投入更多精力在数据结构，努力学好这些知识点。

发表评论取消回复

表情：

评论列表（有 0 条评论，244人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构——线性表——散列存储结构——哈希表知识点总结

散列(hashing)是一种重要的存储方法，也是一种常见的查找方法。基本思想：以结点的关键字k为自变量，通过一个确定的函数关系f，计算出对应的函数值，吧这个函数值

Love The Way You Lie/ 2023年10月17日 13:02/ 0 赞/ 100 阅读

相关 [数据结构] 线性表的顺序存储方式

此篇博客主要对线性表的顺序存储方式进行解释，如果想了解链式存储点击此链接跳转: [线性表的链式存储结构][Link 1]。线性结构线性结构指的是每个元素都有

谁践踏了优雅/ 2023年01月18日 15:19/ 0 赞/ 14 阅读

相关线性表顺序存储结构

线性表顺序存储结构顺序存储结构：指的是用一段地址连续的存储单元一次存储线性表的数据元素。（理解成一维数组，既把第一个数据元素存到数组下表为0的位置中，接着把线性表相邻的元素

青旅半醒/ 2022年10月01日 04:56/ 0 赞/ 253 阅读

相关数据结构——线性表之顺序存储

数据结构——线性表之顺序存储 1、线性表的顺序存储结构特点 > 第i个元素和i+1个元素的存储位置满足：LOC(ai+1)=LOC(ai)+m (其中m是指每

以你之姓@/ 2022年06月16日 22:17/ 0 赞/ 353 阅读

相关数据结构|总结线性表的几种存储结果

一、顺序存储结构——顺序表顺序表是用一段地址连续的存储单元依次存储线性表的数据元素。所以通常用数组来存储线性表，用数组存放，这意味着我们要确定数组的长度，分配固定长度

深藏阁楼爱情的钟/ 2022年06月07日 05:16/ 0 赞/ 245 阅读

相关数据结构之线性表-顺序存储结构

线性表，顾名思义，所谓线性表就是零个或者多个数据元素的有序序列。今天我们一起来看一下线性表中的顺序存储结构。所谓的顺序存储结构其实是存储结构的一种，它的原理是把逻辑相邻的

分手后的思念是犯贱/ 2022年05月31日 08:55/ 0 赞/ 404 阅读

相关线性表的顺序存储结构

线性表的顺序存储结构记录本人学习数据结构的历程，现将分享总结出来的对线性表顺序存储结构的操作。

待我称王封你为后i/ 2022年05月29日 13:11/ 0 赞/ 269 阅读

相关【数据结构和算法】8 线性表：线性表的顺序存储结构

线性表的顺序存储结构线性表有两种物理存储结构：顺序存储结构和链式存储结构。物理上的存储方式事实上就是在内存中找个初始地址，然后通过占位的形式，把一定的内存空

柔光的暖阳◎/ 2022年04月21日 14:34/ 0 赞/ 274 阅读

相关【数据结构】线性表的顺序存储结构

线性表：由n(n≧0)个数据元素(结点)a1，a2， …an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n

青旅半醒/ 2022年04月04日 10:55/ 0 赞/ 367 阅读

相关数据结构总结---------线性表

数据结构总结---------线性表 1.顺序表（数组） 1.1 增加 1.2 删除 1.3 更改 1.4 查

ゝ一纸荒年。/ 2022年03月15日 05:28/ 0 赞/ 205 阅读