JAVA数据结构第二章线性表C.ppt
,第二章 线性表,(之三),上堂课要点回顾,链表的表示(包括有关术语、结构等） 链表的实现（建表、输出、修改、插入、删除）,补充：其它链表形式,循环链表 双向链表 静态链表,提问： 怎样读取结点数据域中的信息？ 链表的操作要用地址,如用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,讨论1：,如：带头结点的空循环链表样式,注：将单链表的首尾相接，将终端结点的地址域由空改为指向头结点，构成单循环链表，简称循环链表。,head,a1,ai-1,an,ai,循环链表插入,核心算法描述： Node s=new Node (element); s.next=p.next; p.next=s;,循环链表插入实现,与单链表的插入操作相比，差别是什么？,循环条件： p!=NULLp!=head p.next!=NULLp.next!=head,开始结点：rear.next.next 终端结点：rear,其它形式的循环链表如：带尾指针的循环链表,一个存储结构设计得是否合理，取决于基于该存储结构的运算是否方便，时间性能是否提高。,如何求结点p的直接前驱，时间性能？,如何快速求得结点p的后继？,如何快速求得结点p的前驱？,讨论2：,p.next,引入一个辅助指针变量q,从首结点开始遍历， 至q.next=p找到直接前驱结点;,双向链表：在单链表的每个结点中再设置一个指 向其前驱结点的地址域。,双向链表,启示？,时空权衡空间换取时间,结点结构定义（P59）：,常用双向循环链表，如空的双向循环链表为：,双向链表的操作插入实现,ai-1,ai,注意指针修改的相对顺序,q = new DLinkNode(x); q.prev = s.prev; q.next = s; p.prev.next = q; s.prev = q;,双向链表的操作删除实现,ai-1,ai,ai+1,结点q的指针是否需要修改？,不需要！,q.prev.next = q.next; if (q.next!=null) (q.next).prev = q.prev;,2.5 应用举例,1一元多项式的数学通式？ 2. 结点如何描述？ 3如何编程实现两个一元多项式相加？,一元多项式的计算,1. 一元多项式的数学通式？,一元多项式的通式可表示为：,分析：一元多项式在计算机内存储时，既可用顺序表存储，又可用链表存储。但当多项式的次数很高且零系数项很多时，则更适于用链表存储（通常设计两个数据域和一个指针域）。,顺序表,链表,或,. 结点结构如何描述？,class term public: float coef;/系数 int exp;/指数 ; 如结点e为：Node e;,e,3. 如何编程实现两个一元多项式相加？,例：,运算规则：两多项式中指数相同的项对应系数相加，若和不为0,则构成多项式c=(a+b)中的一项；a和b中所有指数不相同的项均应复制到c中。（类似于归并操作）,Thanks！待续！,
