大学《数据结构》第二章：线性表-第四节-顺序表和链表的比较.docx

《大学《数据结构》第二章：线性表-第四节-顺序表和链表的比较.docx》由会员分享，可在线阅读，更多相关《大学《数据结构》第二章：线性表-第四节-顺序表和链表的比较.docx（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四节顺序表和链表的比拟一、顺序表的优缺点优点：空间利用率高。可以实现随机存取。缺点：插入、删除操作中要大量移动结点，时间性能差。需要事先确定顺序表的大小，估计小了会发生溢出现象，估计大了又将造成空间的浪费。二、链表的优缺点优点：插入、删除操作中无需移动结点，时间性能好。因为是动态分配存储空间，所以只要有空闲空间就不会 发生溢出现象。缺点：因为每个结点都要额外设置指针域，因此空间利用率低。三、顺序表和链表比拟通过上述比拟，可以看出算法的时间性能与空间性能往往是一对矛 盾，时间性能的改善要以牺牲空间性能为代价,反之亦然。因此在实 际中，要根据具体情况来确定采用哪种存储结构。对线性表的操作是经常性

2、的查找运算，以顺序表形式存储为宜。 因为顺序存储可以随机访问任一结点，访问每个结点的复杂度均为0 (l)o而链式存储结构必须从表头开始沿链逐一访问各结点，其时间复 杂度为0 (n)o如果经常进行的运算是插入和删除运算，以链式存储结构为宜。 因为顺序表作插入和删除操作需要移动大量结点，而链式结构只需要 修改相应的指针。对于线性表结点的存储密度问题，也是选择存储结构的一个重要 依据。所谓存储密度就是结点空间的利用率。它的计算公式为存储密度=（结点数据域所占空间）/（整个结点所占空间）结点存储密度越大，存储空间的利用率就越高。真题选解（例题填空题）1、链表结点定义如下：typedef struct

3、nodechar data 16 ;struct node *next; LinkStrNode ;如果每个字符占1个字节，指针占4个字节，那么该链表的存储密度是隐藏答案【答案】0.8【解析】存储密度=（结点数据域所占空间）/（整个结点所占空 间）=16/（16+4）=0.8。（例题单项选择题）2、与线性表的顺序存储不相符的特性是（）A.不便于插入和删除C.可随机访问E.存储容量固定A.不便于插入和删除C.可随机访问E.存储容量固定B.需连续的存储空间D.存储密度大F.需另外开辟空间来保存元素间的关系隐藏答案【答案】F【解析】线性表的顺序存储是用一片地址连续的空间来存放数据元 素，其特点是逻辑上相邻的元素在物理位置上也相邻，数据元素之间 逻辑上的先后关系自动隐含在物理位置的相邻之中，因此不需要另外开辟空间来保存元素之间的关系。当前讲授本章小结本章着重介绍了线性表在顺序存储结构和链式存储结构上各种运算 实现的算法，并给出了算法的时间复杂度的分析。本章是整个数据结构的基础，也是考试的重点内容，尤其考试大纲 要求：利用顺序表和链表设计算法解决应用问题，要求到达综合应用 层次。大多数情况下，试题的最后一道算法设计题目是线性表链式存 储结构的有关运算。