JAVA数据结构第二章线性表

,第二章线性表,(之三),上堂课要点回顾,链表的表示(包括有关术语、结构等）链表的实现（建表、输出、修改、插入、删除）,补充：其它链表形式,循环链表双向链表静态链表,提问：怎样读取结点数据域中的信息？链表的操作要用地址,如用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,循环链表插入,核心算法描述：Nodes=newNode(element);s.next=p.next;p.next=s;,循环链表插入实现,与单链表的插入操作相比，差别是什么？,循环条件：p!=NULLp!=headp.next!=NULLp.next!=head,开始结点：rear.next.next终端结点：rear,其它形式的循环链表如：带尾指针的循环链表,一个存储结构设计得是否合理，取决于基于该存储结构的运算是否方便，时间性能是否提高。,如何求结点p的直接前驱，时间性能？,如何快速求得结点p的后继？,如何快速求得结点p的前驱？,讨论2：,p.next,引入一个辅助指针变量q,从首结点开始遍历，至q.next=p找到直接前驱结点;,双向链表：在单链表的每个结点中再设置一个指向其前驱结点的地址域。,双向链表,启示？,时空权衡空间换取时间,结点结构定义（P59）：,常用双向循环链表，如空的双向循环链表为：,双向链表的操作插入实现,ai-1,ai,注意指针修改的相对顺序,q=newDLinkNode(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.一元多项式的数学通式？,一元多项式的通式可表示为：,分析：一元多项式在计算机内存储时，既可用顺序表存储，又可用链表存储。但当多项式的次数很高且零系数项很多时，则更适于用链表存储（通常设计两个数据域和一个指针域）。,顺序表,链表,或,.结点结构如何描述？,classtermpublic:floatcoef;/系数intexp;/指数;如结点e为：Nodee;,e,3.如何编程