Question

试比较顺序存储结构和链式储蓄结构的优缺点,在什么情况下用顺序表比链表好?

试比较顺序存储结构和链式储蓄结构的优缺点,在什么情况下用顺序表比链表好?

Answer 1

顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。
优点：存储密度大（＝1？），存储空间利用率高。缺点：插入或删除元素时不方便。
②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1），存储空间利用率低。
顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。
若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；
若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。

Answer 2

链式存储结构:
(1)占用额外的空间以存储指针(浪费空间)
(2)存取某个元素速度慢
(3)插入元素和删除元素速度快
(4)没有空间限制,存储元素的个数无上限,基本只与内存空间大小有关.

顺序存储结构:
(1)空间利用率高
(2)存取某个元素速度快
(3)插入元素和删除元素存在元素移动,速度慢,耗时
(4)有空间限制,当需要存取的元素个数可能多于顺序表的元素个数时,会出现"溢出"问题.当元素个数远少于预先分配的空间时,空间浪费巨大.

在存取元素频繁,但删除或插入操作较少的情况宜用顺序表.堆排序,二分查找适宜用顺序表.