java数据结构第二章线性表c.pptVIP

上堂课要点回顾 链表的表示(包括有关术语、结构等） 链表的实现（建表、输出、修改、插入、删除） 补充：其它链表形式 循环链表 双向链表 静态链表 提问： ① 怎样读取结点数据域中的信息？ ② 链表的操作要用地址 如用p.data 仅两个动作：找位置和改地址！ 线性表的逻辑结构 线性表的顺序存储及实现 线性表的链接存储及实现 顺序表和单链表的比较 线性表的其他存储及实现 本章的基本内容是： 2.4顺序表和单链表的比较 存储分配方式比较 顺序表采用顺序存储结构，即用一段地址连续的存储单元依次存储线性表的数据元素，数据元素之间的逻辑关系通过存储位置来实现。 单链表采用链式存储结构，即用一组任意的存储单元存放线性表的元素。用地址来反映数据元素之间的逻辑关系。 时间性能比较 时间性能是指实现基于某种存储结构的基本操作（即算法）的时间复杂度。 按位查找： 顺序表的时间为Ｏ(1)，是随机存取； 单链表的时间为Ｏ(n)，是顺序存取。 插入和删除： 顺序表平均需移动表长一半的元素，时间为Ｏ(n)； 单链表不需要移动元素，在给出某个合适位置的指针后，插入和删除操作所需的时间仅为Ｏ(1)。 空间性能比较 空间性能是指某种存储结构所占用的存储空间的大小。 定义结点的存储密度： 数据域占用的存储量 整个结点占用的存储量 存储密度＝ 空间性能比较 结点的存储密度： 顺序表中每个结点的存储密度为1（只存储数据元素），没有浪费空间； 单链表的每个结点的存储密度1（包括数据域和指针域），有指针的结构性开销。 整体结构： 顺序表需要预分配存储空间，如果预分配得过大，造成浪费，若估计得过小，又将发生上溢； 单链表不需要预分配空间，只要有内存空间可以分配，单链表中的元素个数就没有限制。 结论 ⑴若线性表需频繁查找却很少进行插入和删除操作，或其操作与位置密切相关时，宜采用顺序表作为存储结构；若线性表需频繁插入和删除时，则宜采用单链表做存储结构。 ⑵当线性表中元素个数变化较大或者未知时，最好使用单链表实现；而如果用户事先知道线性表的大致长度，使用顺序表的空间效率会更高。 总之，根据实际问题的具体需要,加以综合平衡，才能终选定比较适宜的实现方法。 2.5线性表的其他存储及实现 特点： 1、尾结点的地址域指向头结点。 2、从任一结点出发均可找到表中其他结点。 3、操作时仅循环条件与单链表不同：（判表空） 单链表 用 p == NULL (不带头结点) 或 p .next ==NULL(带头结点) 循环链表用 p= =head(不带头结点) 或 p.next == head(带头结点) 从单链表中某结点p出发如何找到其前驱？ head a1 ai-1 an ai p 讨论1： 如：带头结点的空循环链表样式 head 注：将单链表的首尾相接，将终端结点的地址域由空改为指向头结点，构成单循环链表，简称循环链表。 data next head a1 ai-1 an ai 循环链表——插入 x s p x s p x s p 核心算法描述： NodeE s=new NodeE (element); s.next=p.next; p.next=s; 循环链表——插入实现 与单链表的插入操作相比，差别是什么？ 循环链表中没有明显的尾端 如何避免死循环 循环条件： p!=NULL?p!=head p.next!=NULL?p.next!=head rear a1 ai-1 an ai 开始结点：rear.next.next 终端结点：rear 其它形式的循环链表如：带尾指针的循环链表 一个存储结构设计得是否合理，取决于基于该存储结构的运算是否方便，时间性能是否提高。 如何求结点p的直接前驱，时间性能？ head a1 ai-1 an ai p 如何快速求得结点p的后继？ 如何快速求得结点p的前驱？ 讨论2： p.next 引入一个辅助指针变量q,从首结点开始遍历， 至q.next==p找到直接前驱结点; 双向链表：在单链表的每个结点中再设置一个指 向其前驱结点的地址域。 prior data next 双向链表 启示？ 时空权衡——空间换取时间 结点结构定义（P59）： prior data next 常用双向循环链表，如空的双向循环链表为： 双向链表的操作——插入实现 ai-1 ai p x q 注意指针修改的相对顺序 q = new DLinkNode(x); q.prev = s.prev;