大学《数据结构》第二章：线性表-第四节-顺序表和链表的比较_第1页
大学《数据结构》第二章：线性表-第四节-顺序表和链表的比较_第2页
大学《数据结构》第二章：线性表-第四节-顺序表和链表的比较_第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、与线性表的顺序存储不相符的特性是（）AA.不便于插入和删除C.可随机访问E.存储容量固定A.不便于插入和删除C.可随机访问EA.不便于插入和删除C.可随机访问E.存储容量固定F.需另外开辟空间来保存元素间的关系隐藏答案【答案】F【解析】线性表的顺序存储是用一片地址连续的空间来存放数据元 素，其特点是逻辑上相邻的元素在物理位置上也相邻，数据元素之间 逻辑上的先后关系自动隐含在物理位置的相邻之中，因此不需要另外开辟空间来保存元素之间的关系。当前讲授本章小结本章着重介绍了线性表在顺序存储结构和链式存储结构上各种运算 实现的算法，并给出了算法的时间复杂度的分析。本章是整个数据结构的基础，也是考试的重点内容，尤其考试大纲 要求：利用顺序表和链表设计算法

人人文库> 全部分类> 办公材料 > 办公文档

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论