数据存储⽅式学习七(顺序表和链表的⽐较以及存储结构和存取
结构的区别)
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小时内删除。
发表评论