数据存储⽅式学习七（顺序表和链表的⽐较以及存储结构和存取
结构的区别）
1.顺序表和链表的优缺点（区别、特点）
概述：
通过系统地学习顺序表和链表我们知道，虽然它们同属于，
但数据的存储结构有本质的不同：
(1)顺序表存储数据，需预先申请⼀整块⾜够⼤的存储空间，
然后将数据按照次序逐⼀存储，数据之间紧密贴合，
不留⼀丝空隙，如图 1a) 所⽰；
(2)链表的存储⽅式与顺序表截然相反，什么时候存储数据，
什么时候才申请存储空间，数据之间的逻辑关系依靠
每个数据元素携带的指针维持，如图 1b) 所⽰；
基于不同的存储结构，顺序表和链表有以下⼏种不同：
（1）开辟空间的⽅式
顺序表存储数据实⾏的是 "⼀次开辟，永久使⽤"，
即存储数据之前先开辟好⾜够的存储空间，
空间⼀旦开辟后期⽆法改变⼤⼩（使⽤动态的情况除外）。
⽽链表则不同，链表存储数据时⼀次只开辟存储⼀个节点的物理空间，
如果后期需要还可以再申请。
因此，若只从开辟空间⽅式的⾓度去考虑，当存储数据的个数⽆法提前确定，
⼜或是物理空间使⽤紧张以致⽆法⼀次性申请到⾜够⼤⼩的空间时，
使⽤链表更有助于问题的解决。
（2）空间利⽤率
从空间利⽤率的⾓度上看，顺序表的空间利⽤率显然要⽐链表⾼。
这是因为，链表在存储数据时，每次只申请⼀个节点的空间，
且空间的位置是随机的，如图2所⽰：
这种申请存储空间的⽅式会产⽣很多空间碎⽚，⼀定程序上造成了空间浪费。
不仅如此，由于链表中每个数据元素都必须携带⾄少⼀个指针，
因此，链表对所申请空间的利⽤率也没有顺序表⾼。
ps：空间碎⽚，指的是某些容量很⼩（1KB 甚⾄更⼩）以致⽆法得到有效利⽤的物理空间。
(3)时间复杂度
解决不同类型的问题，顺序表和链表对应的时间复杂度也不同。
根据顺序表和链表在存储结构上的差异，问题类型主要分为以下 2 类：
数组和链表
（1）问题中主要涉及访问元素的操作，元素的插⼊、删除和移动操作极少；
（2）问题中主要涉及元素的插⼊、删除和移动，访问元素的需求很少；
概括：第1类问题适合使⽤顺序表。
这是因为，顺序表中存储的元素可以使⽤数组下标直接访问，
⽆需遍历整个表，因此使⽤顺序表访问元素的时间复杂度为O(1)；
⽽在链表中访问数据元素，需要从表头依次遍历，
直到到指定节点，花费的时间复杂度为O(n);
第2类问题则适合使⽤链表。
链表中数据元素之间的逻辑关系靠的是节点之间的指针，
当需要在链表中某处插⼊或删除节点时，
只需改变相应节点的指针指向即可，
⽆需⼤量移动元素，因此链表中插⼊、
删除或移动数据所耗费的时间复杂度为O(1)；
⽽顺序表中，插⼊、删除和移动数据可能会牵涉到⼤量元素的整体移动，
因此时间复杂度⾄少为O(n);
总结：综上所述，不同类型的场景，选择合适的存储结构会使解决问题效率成倍数地提⾼。
2.存储结构和存取结构的区别
1.⼀个是数据的存储状态⼀种是数据的存储⽅式：
所谓存储结构，指的是数据在内存中真实的存储状态，
具体可分为2类，即顺序存储结构和链式存储结构。
⽽存取结构，指的是存取数据的⽅式，
具体也可以分为2类，分别为顺序存取结构和随机存取结构。
2.例⼦：
描述:
线性表的顺序存储结构是随机存取结构，⽽不是顺序存取结构；
线性表的链式存储结构，⼜可以称为顺序存取结构，⽽不是随机存取结构。
分析：
我们知道，线性表的顺序存储结构，
本质就是采⽤⼀块连续的存储空间将所有数据集中存储起来。
不仅仅是C语⾔，很多种编程语⾔中，
都在使⽤数组这种数据类型来表⽰顺序存储结构。
顺序存储结构最⼤的特点是，我们可以随机存或者取数据。
例如，现有⼀个数组a，其初始存储状态为：
在此基础上，如果想取出元素1，由于其位于数组下标为1的位置
（数组下标通常由0开始计数），因此借助a[1]，就可以轻松实现⽬的；
反之，如果想将元素2改存为元素5，可以这样实现：
a[2] = 5;
显然借助顺序存储结构的特点，我们可以随机存或者取存储的各个元素。
这也就解释了“线性表的顺序存储结构，⼜可以称为随机存取结构”。
和随机存取结构相对的，是顺序存取结构。
通过前⾯的学习我们知道，采⽤链表存储的数据，它们所在的物理空间并不紧挨着，⽽是分散在内存中的各个位置。仍以存储 0、1、2、和3这4个元素为例，
如果采⽤链式存储结构，则各个元素的存储状态可能为：
如图2所⽰，如果我们想在链表中存或者取数据，
就只能从链表头H开始，逐个遍历链表中的每个元素，
直⾄到⽬标元素。也就是说，从链表中存和取数据，
必须从遵循各个元素在链表中存储的逻辑顺序，⽆法随机存取。
总之，线性表的顺序存储结构，⼜可以称为随机存取结构；
⽽线性表的链式存储结构（以及栈结构和队列结构），⼜可以称为顺序存取结构。学习来源：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。