JAVA数据结构第二章线性表.ppt

《JAVA数据结构第二章线性表.ppt》由会员分享，可在线阅读，更多相关《JAVA数据结构第二章线性表.ppt（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、上堂课要点回顾上堂课要点回顾1.1.链表的表示链表的表示(包括有关术语、包括有关术语、结构结构等）等）2.2.链表的实现（建表、输出、修改、插入、删除）链表的实现（建表、输出、修改、插入、删除）补充：其它链表形式补充：其它链表形式循环链表循环链表双向链表双向链表静态链表静态链表提问：提问：怎样读取结点数据域中的信息？怎样读取结点数据域中的信息？链表的操作要用链表的操作要用地址地址如用如用p.data仅两个动作：找位置仅两个动作：找位置和改地址！和改地址！线性表的逻辑结构线性表的逻辑结构 线性表的顺序存储及实现线性表的顺序存储及实现 线性表的链接存储及实现线性表的链接存储及实现 顺序表和单链表的

2、比较顺序表和单链表的比较 线性表的其他存储及实现线性表的其他存储及实现本章的基本内容是：本章的基本内容是：2.42.4顺序表和单链表的比较顺序表和单链表的比较存储分配方式比较存储分配方式比较顺序表顺序表采用采用顺序存储顺序存储结构，即用一段地址结构，即用一段地址连续连续的的存储单元存储单元依次依次存储线性表的数据元素，数据元素之存储线性表的数据元素，数据元素之间的逻辑关系通过间的逻辑关系通过存储位置存储位置来实现。来实现。单链表单链表采用采用链式存储链式存储结构，即用一组结构，即用一组任意任意的存储的存储单元存放线性表的元素。用单元存放线性表的元素。用地址地址来反映数据元素之来反映数据元素之间

3、的逻辑关系。间的逻辑关系。时间性能比较时间性能比较 时间性能时间性能是指实现基于某种存储结构的基本操作（即是指实现基于某种存储结构的基本操作（即算法）的时间复杂度。算法）的时间复杂度。按位查找：按位查找：顺序表的时间为顺序表的时间为(1)(1)，是随机存取；，是随机存取；单链表的时间为单链表的时间为(n n)，是顺序存取。，是顺序存取。插入和删除：插入和删除：顺序表平均需移动表长一半的元素，时间为顺序表平均需移动表长一半的元素，时间为(n n)；单链表不需要移动元素，在给出某个合适位置的指针单链表不需要移动元素，在给出某个合适位置的指针后，插入和删除操作所需的时间仅为后，插入和删除操作所需的时

4、间仅为(1)(1)。空间性能比较空间性能比较 空间性能空间性能是指某种存储结构所占用的存储空间的大小。是指某种存储结构所占用的存储空间的大小。定义结点的存储密度：定义结点的存储密度：数据域占用的存储量数据域占用的存储量整个结点占用的存储量整个结点占用的存储量存储密度存储密度空间性能比较空间性能比较 结点的存储密度：结点的存储密度：顺序表顺序表中每个结点的中每个结点的存储密度为存储密度为1 1（只存储数据元素）（只存储数据元素），没有浪费，没有浪费空间空间；单链表的每个结点的单链表的每个结点的存储密度存储密度11（包括数据域和指（包括数据域和指针域），有针域），有指针指针的结构性开销。的结构性开

5、销。整体结构：整体结构：顺序表需要预分配存储空间，如果预分配得过大，顺序表需要预分配存储空间，如果预分配得过大，造成浪费，若造成浪费，若估计得过小估计得过小，又将发生，又将发生上溢上溢；单链表不需要预分配空间，只要有内存空间可以分单链表不需要预分配空间，只要有内存空间可以分配，配，单链表中的元素个数就没有限制单链表中的元素个数就没有限制。结论结论若若线性表线性表需需频繁查找频繁查找却却很少进行插入和删除很少进行插入和删除操作，操作，或其操作或其操作与位置密切相关与位置密切相关时，宜采用顺序表作为存储时，宜采用顺序表作为存储结构；若线性表需结构；若线性表需频繁插入和删除频繁插入和删除时，则宜采用

6、单链时，则宜采用单链表做存储结构。表做存储结构。当线性表中元素当线性表中元素个数变化个数变化较大或者未知时，较大或者未知时，最好使最好使用单链表实现用单链表实现；而如果用户事先知道线性表的大致长；而如果用户事先知道线性表的大致长度，使用顺序表的空间效率会更高。度，使用顺序表的空间效率会更高。总之总之，根据实际问题的具体需要，根据实际问题的具体需要,加以综合平衡，才能加以综合平衡，才能终选定终选定比较适宜比较适宜的实现方法。的实现方法。2.52.5线性表的其他存储及实现线性表的其他存储及实现特点：特点：1 1、尾结点的地址域指向头结点。、尾结点的地址域指向头结点。、尾结点的地址域指向头结点。、尾

7、结点的地址域指向头结点。2 2、从任一结点出发均可找到表中其他结点。、从任一结点出发均可找到表中其他结点。、从任一结点出发均可找到表中其他结点。、从任一结点出发均可找到表中其他结点。3、操作时仅、操作时仅、操作时仅、操作时仅循环条件循环条件循环条件循环条件与单链表不同：（与单链表不同：（与单链表不同：（与单链表不同：（判表空判表空判表空判表空）单链表单链表单链表单链表 用用用用 p=NULL (p=NULL (不带头结点不带头结点不带头结点不带头结点)或或或或 p.next=NULL(p.next=NULL(带头结点带头结点带头结点带头结点)循环链表用循环链表用循环链表用循环链表用 p=hea

8、d(p=head(不带头结点不带头结点不带头结点不带头结点)或或或或 p.next=head(p.next=head(带头结点带头结点带头结点带头结点)从单链表中某结点从单链表中某结点p p出发如何找到其前驱？出发如何找到其前驱？heada1ai-1anaip讨论讨论1：如：带头结点的如：带头结点的空空循环链表样式循环链表样式head注：将单链表的首尾相接，将终端结点的地址域由空注：将单链表的首尾相接，将终端结点的地址域由空改为指向头结点，构成改为指向头结点，构成单循环链表单循环链表，简称，简称循环链表循环链表。data nextheada1ai-1anai循环链表循环链表循环链表循环链表插入

9、插入插入插入xspxspxsp核心算法描述：核心算法描述：Node s=new Node(element);s.next=p.next;p.next=s;循环链表循环链表循环链表循环链表插入实现插入实现插入实现插入实现与单链表的插入操作相比，差别是什么？与单链表的插入操作相比，差别是什么？循环链表中没有明显的尾端循环链表中没有明显的尾端 如何避免死循环如何避免死循环循环条件：循环条件：p!=NULLp!=headp.next!=NULLp.next!=headreara1ai-1anai开始结点：开始结点：开始结点：开始结点：rear.next.nextrear.next.next终端结点：终

10、端结点：终端结点：终端结点：rearrear其它形式的循环链表如：带尾指针的循环链表其它形式的循环链表如：带尾指针的循环链表 一个存储结构设计得是否合理，取决于基于该存一个存储结构设计得是否合理，取决于基于该存储结构的储结构的运算是否方便运算是否方便，时间性能是否提高时间性能是否提高。如何求结点如何求结点p p的直接前驱，时间性能？的直接前驱，时间性能？heada1ai-1anaip如何快速求得结点如何快速求得结点p p的后继？的后继？如何快速求得结点如何快速求得结点p p的前驱？的前驱？讨论讨论2：p.next 引入一个辅助指针变量引入一个辅助指针变量q,从首结点开始遍历，从首结点开始遍历，

11、至至q.next=p找到直接前驱结点找到直接前驱结点;双向链表：双向链表：在单链表的每个结点中再设置一个指在单链表的每个结点中再设置一个指向其前驱结点的向其前驱结点的地址地址域。域。priordatanext双向链表双向链表双向链表双向链表启示？启示？时空权衡时空权衡空间换取时间空间换取时间结点结构定义（结点结构定义（P59）：）：priordatanext常用双向循环链表，如空的双常用双向循环链表，如空的双向循环链表为：向循环链表为：双向链表的操作双向链表的操作插入实现插入实现ai-1aipxq注意指针修改的注意指针修改的相对相对顺序顺序q=new DLinkNode(x);q.prev=s

12、.prev;q.next=s;p.prev.next=q;s.prev=q;s双向链表的操作双向链表的操作删除实现删除实现ai-1aiqai+1结点结点q q的指针是否需要修改？的指针是否需要修改？p不需要！不需要！q.prev.next=q.next;if(q.next!=null)(q.next).prev=q.prev;2.5 2.5 应用举例应用举例1 1一元多项式的数学通式？一元多项式的数学通式？2.2.结点如何描述？结点如何描述？3 3如何编程实现两个一元多项式相加？如何编程实现两个一元多项式相加？一元多项式的计算一元多项式的计算1.一元多项式的数学通式？一元多项式的数学通式？一元

13、多项式的通式可表示为：一元多项式的通式可表示为：分析：分析：一元多项式在计算机内存储时，既可用一元多项式在计算机内存储时，既可用顺序表顺序表存储，存储，又可用又可用链表链表存储。但当多项式的存储。但当多项式的次数很高且零系数项很多次数很高且零系数项很多时，时，则更适于用链表存储（则更适于用链表存储（通常设计两个数据域和一个指针域通常设计两个数据域和一个指针域）。）。a0a1a2am-2am-1顺序表顺序表链表链表am-1 em-1am-2 em-2 a0 e0 或或0.0 -1 am-1 em-1 a0 e0.结点结构如何描述？结点结构如何描述？coefexpnextclass termpublic:float coef;/系数系数int exp;/指数指数;如结点如结点e为：为：Node e;e3.3.如何编程实现两个一元多项式相加？如何编程实现两个一元多项式相加？3 142 81 0a8 143 1010 6b例：例：运算规则：两多项式中运算规则：两多项式中指数相同的项指数相同的项对应对应系系数相加，数相加，若若和不为和不为0,则则构成多项式构成多项式c=(a+b)中中的一项；的一项；a和和b中所有指数不相同的项均应复中所有指数不相同的项均应复制到制到c中。（类似于归并操作）中。（类似于归并操作）ThanksThanks！待续！待续！