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

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

1、上堂课要点回顾上堂课要点回顾1.1.线性结构线性结构(包括表、栈、队、数组）的定义和特点：包括表、栈、队、数组）的定义和特点：仅一个首、尾结点，其余元素仅一个直接前驱和一个直仅一个首、尾结点，其余元素仅一个直接前驱和一个直接后继。接后继。2.2.线性表线性表逻辑结构逻辑结构：“一对一一对一”或或 1:11:1存储结构存储结构：顺序、链式：顺序、链式运运 算算 ：修改、插入、删除、查找：修改、插入、删除、查找3.3.顺序存储顺序存储特征：特征：逻辑上相邻，物理上也相邻；逻辑上相邻，物理上也相邻；优点：优点：随机查找快随机查找快 O(1)O(1)缺点：缺点：插入、删除慢插入、删除慢 O(n)O(n

2、)线性表的逻辑结构线性表的逻辑结构 线性表的顺序存储及实现线性表的顺序存储及实现 线性表的链接存储及实现线性表的链接存储及实现 顺序表和单链表的比较顺序表和单链表的比较 线性表的其他存储及实现线性表的其他存储及实现本章的基本内容是：本章的基本内容是：2.3 2.3 线性表的链式存储和实现线性表的链式存储和实现2.3.1 链表的存储表示链表的存储表示2.3.2 链表的操作实现链表的操作实现2.3.3 链表的算法效率分析链表的算法效率分析本节小结本节小结链表：链表：线性表的链接存储结构。线性表的链接存储结构。存储思想：存储思想：用一组用一组任意任意的存储单元存放线性表的元素。的存储单元存放线性表的

3、元素。2.3.1 链表的存储表示链表的存储表示静态存储分配静态存储分配 顺序表顺序表事先确定容量事先确定容量 链链 表表动态存储分配动态存储分配 运行时分配空间运行时分配空间 连续连续不连续不连续零散分布零散分布0200020803000325存储特点：存储特点：1.1.逻辑次序和物理次序逻辑次序和物理次序 不一定不一定相同。相同。2.2.元素之间的逻辑关系元素之间的逻辑关系 用用地址地址表示。表示。例：例：(a1,a2,a3,a4)的存储示意图的存储示意图1、链表的存储特点链表的存储特点 a10200 a20325 a30300 a4 链表是由若干结点构成的；每个结点结构有两个部链表是由若干

4、结点构成的；每个结点结构有两个部分组成：分组成：0200020803000325 a10200 a20325 a30300 a4 结点结点数据域数据域地址域地址域data：存储数据元素：存储数据元素next：存储指向后继结点的地址：存储指向后继结点的地址 data next如单链表的结点结构：如单链表的结点结构：数据域数据域地址域地址域2 2、有关的术语有关的术语1）结点：）结点：数据元素的存储映像。由数据域和地址域两数据元素的存储映像。由数据域和地址域两部分组成；部分组成；2）链表：）链表：n 个结点由个结点由地址地址链链组成一个链表。它是线组成一个链表。它是线性表的链式存储映像，称为线性表

5、的链式存储结构。性表的链式存储映像，称为线性表的链式存储结构。3）单链表、双链表、多链表、循环链表）单链表、双链表、多链表、循环链表：结点只有一个地址域的链表，称为结点只有一个地址域的链表，称为单链表单链表或或线性链线性链表表；有两个地址域的链表，称为有两个地址域的链表，称为双链表双链表；有多个地址域的链表，称为有多个地址域的链表，称为多链表多链表；首尾相接的链表称为首尾相接的链表称为循环链表循环链表。a1heada2anhead头指针头指针是是指向指向链表中链表中第一个结点第一个结点（或为（或为头结点头结点或或为首为首元结点元结点）的）的地址地址。头结点头结点是在链表的是在链表的首元结点之前

6、附设首元结点之前附设的一个结点；数的一个结点；数据域内只放空表标志或表长等信息据域内只放空表标志或表长等信息;首元结点首元结点是指链表中存储线性表第一个数据元素是指链表中存储线性表第一个数据元素a a1 1。头指针头指针头结点头结点 首结点首结点a14）头指针头指针、头结点头结点和和首结点首结点上例链表的逻辑结构示意图有以下上例链表的逻辑结构示意图有以下两种形式两种形式：a1a2/a4a3Ha1a2/a4a3H区别：区别：无头结点无头结点(链式队列、链栈常用链式队列、链栈常用)有头结点有头结点(链表常用链表常用)答：答：讨论讨论1 1.在链表中设置在链表中设置头结点头结点有什么好处？有什么好处

7、？讨论讨论2 2.如何表示如何表示空表空表？头结点头结点即在链表的首元结点之前附设的一个结点，该结即在链表的首元结点之前附设的一个结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对进行操作时，可以对空表、非空表空表、非空表的情况以及对的情况以及对首元结点首元结点进行进行统一处理，编程更方便统一处理，编程更方便,常用头结点。常用头结点。答：答：无头结点时，无头结点时，当头指针的值为空当头指针的值为空时表示空表；时表示空表；有头结点时，有头结点时，当头结点的地址域为空当头结点的地址域为空时表示空表。时表示空表。头

8、指针头指针头指针头指针头结点头结点无头结点无头结点有头结点有头结点hhh=NULLH.next=NULLpublic class Node /单链表结点类 public E data;/数据域，保存数据元素 public Node next;/地址域，引用后继结点3、单链表的存储结构定义单链表的存储结构定义 (重点及难点重点及难点)data next1)单链表结点类单链表结点类Node声明：声明：public Node（E data,Node next /构造结点 this.data=data;this.next=next;public Node(E data)this(data,null);

9、public Node()this(null,null);headNodedatanext如何申请一个结点如何申请一个结点？Node p,q;p=new Node(A);q=new Node(B);p.next=q;单链表的头指针head也是一个引用，声明如下：Node head=null;当head=null时，表示空单链表。线性表接口线性表接口LListpublic interface LList/纯性表接口纯性表接口boolean isEmpty();/判断线性表是否为空，若空返回判断线性表是否为空，若空返回trueint length();/返回线性表长度；返回线性表长度；E get(

10、int index);/返回序号为返回序号为index的对象，的对象，index初值为初值为0E set(int index,E element);/设置序号为设置序号为index对象为对象为element，返回原对象，返回原对象boolean add(int index,E element);/插入插入element对象，插入对象，插入后对象序号为后对象序号为indexboolean add(E element);/插入插入element对象，插入位置没有约对象，插入位置没有约定定E remove(int index);/移去序号为移去序号为index的对象，返回被移动对的对象，返回被移动对

11、象象void clear();/清空线性表；清空线性表；BACK）单链表类声明（书）单链表类声明（书P48）public class SinglyLinkedList implements LList /单链表类，实现线性表接口 protected Node head;/头指针 public SinglyLinkedList()/构造空单链表 this.head=new Node();2.3.2 单链表的操作实现单链表的操作实现1.1.单链表的遍历单链表的遍历2.2.单链表的插入单链表的插入3.3.单链表的删除单链表的删除4.4.其它操作实现其它操作实现5.5.应用举例应用举例1、单链表的遍历

12、、单链表的遍历操作接口：操作接口：基本步骤：基本步骤：从从首结点首结点开始，一个一个输出至开始，一个一个输出至尾结点尾结点。算法实现算法实现：heada0pa1panaipppP=NULL时结束时结束a0a1aianNode p=head;while(p!=null)System.out.print(p.data.toString()+”);p=p.next;p+能否完成指针后移？能否完成指针后移？a1a2ppp.nextp+;2单链表的查找单链表的查找(按位查找按位查找)操作接口：操作接口：（书（书P49P49）public E get(int index);heada0pa1panaip查

13、找成功查找成功pin查找失败查找失败顺藤摸瓜顺藤摸瓜按位查找算法实现按位查找算法实现：public E get(int i)if(i=0)Node p=this.head.next;int j=0;while(p&ji)p=p.next;/工作指针工作指针p后移后移 j+;if(p)return p.data;else return null;v核心操作（关键操作）：核心操作（关键操作）：P指针后移指针后移。从首结点出发，通过指针的反复。从首结点出发，通过指针的反复后移而将整个单链表后移而将整个单链表“审视审视”一遍的方法称为一遍的方法称为扫描扫描（或遍历）。（或遍历）。v思考：按值查找如何实

14、现。（略）思考：按值查找如何实现。（略）3 3、单链表插入、单链表插入操作接口：操作接口：public boolean add(int index,E element)(1)空表插入空表插入/头插入头插入if(head=null)head=new Node(x);elseNode q=new Node(x);q.next=head;head=q;如何实现结点如何实现结点ai-1、x和和ai之间逻辑关系的变化？之间逻辑关系的变化？pxqheada1ai-1anaiNode q=new Node(x);Step1:q.next=p.next;Step2:p.next=q;插入步骤（即核心语句）：插

15、入步骤（即核心语句）：思考：步骤思考：步骤1 1和和2 2能互换么？能互换么？不能互换！不能互换！(2)中间插入中间插入/尾插入尾插入算法：在单链表算法：在单链表L L中第中第i个位置之前插入元素个位置之前插入元素x。基本思想：基本思想：（1 1）找到插入点找到插入点（p p将指向第将指向第i-1-1个结点）；平个结点）；平均时间复杂度为均时间复杂度为O(n)；（2 2）新建插入结点；）新建插入结点；（3 3）修改相应结点的地址域，实现）修改相应结点的地址域，实现插入插入，其时，其时间复杂度为间复杂度为O(1)(1)。注：注：先修改新结点的地址域，再修改链表的地先修改新结点的地址域，再修改链表

16、的地址域。址域。插入算法实现（插入算法实现（P50）基本语句？时间复杂度？基本语句？时间复杂度？4、单链表的删除、单链表的删除操作接口：操作接口：public E remove(int index)头删除head=head.next;中间/尾删除if(p.next!=null)p.next=p.next.next;算法：在带头结点的单链表算法：在带头结点的单链表L L中删除第中删除第i i个结点，并返个结点，并返回该结点的值。回该结点的值。基本思想：基本思想：（1 1）找到删除点找到删除点（指针（指针p p将指向第将指向第i-1i-1个结点）；个结点）；/平平均查找时间复杂度为均查找时间复杂度

17、为O(n)O(n)判判i i的合法性：的合法性：i=1&i=1&i=链表表长。链表表长。指针指针p p初始化；累加器初始化；累加器j j清零；清零；（2 2）修改修改相应结点的相应结点的指针域指针域，实现删除。，实现删除。注：先保护要删除的结点，将其值取出；再修改链表注：先保护要删除的结点，将其值取出；再修改链表指针域。指针域。删除算法实现（删除算法实现（P50）基本语句？时间复杂度？基本语句？时间复杂度？5 5单链表求表长函数的实现单链表求表长函数的实现基本思想：边遍历边计数。基本思想：边遍历边计数。操作接口：操作接口：public int length()int i=0;Node p=th

18、is.head;while(p!=null)i+;p=p.next;return i;带头结点的单链表带头结点的单链表(书书P48)单链表的逆转单链表的逆转(书书P53)【例2.2】采用单链表求解约瑟夫环问题。5 5、应用举例、应用举例6 6、应用举例：两个链表的归并、应用举例：两个链表的归并算法要求：算法要求：已知：已知：线性表线性表 A、B，分别由，分别由单链表单链表 LA,LB 存储，其存储，其中数据元素按值中数据元素按值非递减有序非递减有序排列。排列。要求：要求：将将 A，B 归并归并为一个新的线性表为一个新的线性表C,C 的数据元的数据元素仍按值非递减排列素仍按值非递减排列 。设线性

19、表。设线性表 C 由由单链表单链表 LC 存存储。储。假设：假设：A=（3，5，8，11），），B=（2，6，8，9，11）预测：预测：合并后合并后 C=（2,3,5,6,8,8,9,11，11）用链表可表示为：用链表可表示为：3 511/8 LaLa 2 611/8 LbLb 9 2 3 6 5 LcLc 8头结点头结点LaLaLbLbLcLc算法分析：算法分析：算法主要包括：算法主要包括：搜索、比较、插入搜索、比较、插入三个操作：三个操作：搜索：搜索：需要需要两个指针两个指针遍历两个链表；遍历两个链表；比较：比较：比较结点数据域中数据的大小；比较结点数据域中数据的大小；插入：插入：将两个结点中数据将两个结点中数据小的结点插入新链表小的结点插入新链表。3 5 8 11 Lb2 6 8 119 PaPbPaPbPa、Pb用于搜索用于搜索La和和Lb，Pc指向新链表当前结点指向新链表当前结点Lc Pa3 PcPa5 Pc11Pc2 PbPcPaLa思考：思考：1、不用、不用Lc，直接把，直接把La表插到表插到Lb表中；或者把表中；或者把Lb表表 插到插到La表中，如何编程？表中，如何编程？2、要求不能有重复的数据元素，如何编程？、要求不能有重复的数据元素，如何编程？ThanksThanks！待续！待续！