JAVA数据结构第二章线性表C.ppt
《JAVA数据结构第二章线性表C.ppt》由会员分享,可在线阅读,更多相关《JAVA数据结构第二章线性表C.ppt(22页珍藏版)》请在三一文库上搜索。
1、,第二章 线性表,(之三),上堂课要点回顾,链表的表示(包括有关术语、结构等) 链表的实现(建表、输出、修改、插入、删除),补充:其它链表形式,循环链表 双向链表 静态链表,提问: 怎样读取结点数据域中的信息? 链表的操作要用地址,如用p.data,仅两个动作:找位置和改地址!,线性表的逻辑结构 线性表的顺序存储及实现 线性表的链接存储及实现 顺序表和单链表的比较 线性表的其他存储及实现,本章的基本内容是:,2.4顺序表和单链表的比较,存储分配方式比较,顺序表采用顺序存储结构,即用一段地址连续的存储单元依次存储线性表的数据元素,数据元素之间的逻辑关系通过存储位置来实现。 单链表采用链式存储结构
2、,即用一组任意的存储单元存放线性表的元素。用地址来反映数据元素之间的逻辑关系。,时间性能比较,时间性能是指实现基于某种存储结构的基本操作(即算法)的时间复杂度。,按位查找: 顺序表的时间为(1),是随机存取; 单链表的时间为(n),是顺序存取。 插入和删除: 顺序表平均需移动表长一半的元素,时间为(n); 单链表不需要移动元素,在给出某个合适位置的指针后,插入和删除操作所需的时间仅为(1)。,空间性能比较,空间性能是指某种存储结构所占用的存储空间的大小。,定义结点的存储密度:,空间性能比较,结点的存储密度: 顺序表中每个结点的存储密度为1(只存储数据元素),没有浪费空间; 单链表的每个结点的存
3、储密度1(包括数据域和指针域),有指针的结构性开销。 整体结构: 顺序表需要预分配存储空间,如果预分配得过大,造成浪费,若估计得过小,又将发生上溢; 单链表不需要预分配空间,只要有内存空间可以分配,单链表中的元素个数就没有限制。,结论,若线性表需频繁查找却很少进行插入和删除操作,或其操作与位置密切相关时,宜采用顺序表作为存储结构;若线性表需频繁插入和删除时,则宜采用单链表做存储结构。 当线性表中元素个数变化较大或者未知时,最好使用单链表实现;而如果用户事先知道线性表的大致长度,使用顺序表的空间效率会更高。,总之,根据实际问题的具体需要,加以综合平衡,才能终选定比较适宜的实现方法。,2.5线性表
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- JAVA 数据结构 第二 线性
链接地址:https://www.31doc.com/p-2892970.html