扫码获取更多资源

●线姓表两种存储表示的比较

线性表有两种存储表示：顺序存储结构和链式存储结构。在实际应用中究竟选用哪一 种存储结构合适呢？这要根据具体问题的要求和性质来决定。

●基于空间的比较

分配方式

顺序表采用静态分配方式。在程序运行之前必须明确规定存储规模。如果线性表的长 度变化较大，则存储规模难以预先确定：估计过大将造成空间浪费，估计太小又将使空间溢 出机会增多。

链式表采用动态分配方式。在程序运行之中只要内存尚有一个结点的空间可以分配， 就不会产生溢出。因此，当线性表的长度变化较大，难以事先估计其存储规模时，采用链式 存储结构为好。

存储密度

存储密度(Storage Density)是指结点数据本身所占用的存储量和整个结点结构所占用 的存储量之比。

顺序表的存储密度为lo当线性表长度变化不大，易于事先确定其大小时，为了节约存 储空间，宜采用顺序存储结构。

链式表的存储密度小于10链表中的结点除了数据域外，还需要额外设置指针域存储 逻辑上与其相邻接的下一结点的地址，从存储密度来讲是不经济的。

●基于空间的比较

存取方式点

顺序表是随机存取结构，对表中任一元素都可以在0(1)的时间内直接取得。当对线性 表主要进行查找操作，很少进行插入和删除操作时，采用顺序存储结构为宜。

链式表是顺序存取结构，对表中每个结点都必须从头指针开始顺链向后扫描才能进行 存取，时间复杂度为O(n)。

插入和删除操作

在顺序表中进行插入和删除操作时，平均要移动表中近一半的数据元素，尤其是当元素 个数较多、元素信息量较大时，移动元素所花费的时间开销相当大。

在链式表中进行插入和删除操作时，只需要修改指针。对于频繁进行插入和删除数据 元素的线性表，宜采用链表存储结构。

联系我们：