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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章,线性表,(,之二,),上堂课要点回顾,线性结构,(,包括表、栈、队、数组）的定义和特点：,仅一个首、尾结点，其余元素仅一个直接前驱和一个直接后继。,2.,线性表,逻辑结构,：,“,一对一,”,或,1:1,存储结构,：顺序、链式,运 算,：修改、插入、删除、查找,3.,顺序存储,特征：,逻辑上相邻，物理上也相邻；,优点：,随机查找快,O(1),缺点：,插入、删除慢,O(n),线性表的逻辑结构,线性表的顺序存储及实现,线性表的链接存储及实现,顺序表和单链表的比较,线性表的其他存储及实现,本章的基本内容是2.3,线性表的链式存储和实现,2.3.1,链表的存储表示,2.3.2,链表的操作实现,2.3.3,链表的算法效率分析,本节小结,链表：,线性表的链接存储结构。,存储思想：,用一组,任意,的存储单元存放线性表的元素。,2.3.1,链表的存储表示,静态存储分配,顺序表,事先确定容量,链 表,动态存储分配,运行时分配空间,连续,不连续,零散分布,0200,0208,0300,0325,存储特点：,逻辑次序和物理次序,不一定,相同。,2.,元素之间的逻辑关系,用,地址,表示。,例：,(,a,1,a,2,a,3,a,4,),的存储示意图,1,、,链表的存储特点,a,1,0200,a,2,0325,a,3,0300,a,4,链表是由若干结点构成的；每个结点结构有两个部分组成：,0200,0208,0300,0325,a,1,0200,a,2,0325,a,3,0300,a,4,结点,数据域,地址域,data,：存储数据元素,next,：存储指向后继结点的地址,data next,如单链表的结点结构：,数据域,地址域,2,、,有关的术语,1,）结点：,数据元素的存储映像。由数据域和地址域两部分组成；,2,）链表：,n,个结点由,地址,链,组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。,3,）单链表、双链表、多链表、循环链表,：,结点只有一个地址域的链表，称为,单链表,或线性链表,；,有两个地址域的链表，称为,双链表,；,有多个地址域的链表，称为,多链表,；,首尾相接的链表称为,循环链表,。,a,1,head,a,2,a,n,head,头指针,是,指向,链表中,第一个结点,（或为,头结点,或,为首元结点,）的,地址,。,头结点,是在链表的,首元结点之前附设,的一个结点；数据域内只放空表标志或表长等信息,;,首元结点,是指链表中存储线性表第一个数据元素,a,1,。,头指针,头结点,首结点,a,1,4,）,头指针,、,头结点,和,首结点,上例链表的逻辑结构示意图有以下,两种形式,：,a1,a2,/,a4,a3,H,a1,a2,/,a4,a3,H,区别：,无头结点链式队列、链栈常用,),有头结点,(,链表常用,),答：,讨论,1,.,在链表中设置,头结点,有什么好处？,讨论,2,.,如何表示,空表,？,头结点,即在链表的首元结点之前附设的一个结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对,空表、非空表,的情况以及对,首元结点,进行统一处理，编程更方便,常用头结点。,答：,无头结点时，,当头指针的值为空,时表示空表；,有头结点时，,当头结点的地址域为空,时表示空表。,头指针,头指针,头结点,无头结点,有头结点,h,h,h=NULL,H.next=NULL,public class Node /,单链表结点类,public E data;/,数据域，保存数据元素,public Node next;/,地址域，引用后继结点,3,、,单链表的存储结构定义,(,重点及难点,),data next,1),单链表结点类,Node,声明：,public Node,（,E data,Node next /,构造结点,this.data=data;,this.next=next;,public Node(E data)this(data,null);,public Node()this(null,null);,head,Node,data,next,如何申请一个结点,？,Node p,q;,p=new Node(A);q=new Node(B);,p.next=q;,单链表的头指针,head,也是一个引用，声明如下：,Node head=null;,当,head=null,时，表示空单链表。,线性表接口,LList,public interface LList,/,纯性表接口,boolean isEmpty();,/,判断线性表是否为空，若空返回,true,int length();,/,返回线性表长度；,E get(int index);,/,返回序号为,index,的对象，,index,初值为,0,E set(int index,E element);,/,设置序号为,index,对象为,element,，返回原对象,boolean add(int index,E element);,/,插入,element,对象，插入后对象序号为,index,boolean add(E element);,/,插入,element,对象，插入位置没有约定,E remove(int index);,/,移去序号为,index,的对象，返回被移动对象,void clear();,/,清空线性表；,BACK,）单链表类声明（书,P48,）,public class SinglyLinkedList implements LList,/,单链表类，实现线性表接口,protected Node head;/,头指针,public SinglyLinkedList()/,构造空单链表,this.head=new Node();,2.3.2,单链表的操作实现,单链表的遍历,单链表的插入,3.,单链表的删除,4.,其它操作实现,5.,应用举例,1,、单链表的遍历,操作接口：,基本步骤：,从,首结点,开始，一个一个输出至,尾结点,。,算法实现,：,head,a,0,p,a,1,p,a,n,a,i,p,p,p,P=NULL,时结束,a,0,a,1,a,i,a,n,Node p=head;,while(p!=null),System.out.print(p.data.toString()+”);,p=p.nextp+,能否完成指针后移？,a,1,a,2,p,p,p.next,p+;,2,单链表的查找,(,按位查找,),操作接口：,（书,P49,）,public E get(int index),;,head,a,0,p,a,1,p,a,n,a,i,p,查找成功,p,in,查找失败,顺藤摸瓜,按位查找算法实现,：,public E get(int i),if(i=0),Node,p=this.head.next;,int j=0;,while(,p,&,j=1&i=,链表表长。,指针,p,初始化；累加器,j,清零；,（,2,）,修改,相应结点的,指针域,，实现删除。,注：先保护要删除的结点，将其值取出；再修改链表指针域。,删除算法实现（,P50,）,基本语句？时间复杂度？,5,单链表求表长函数的实现,基本思想：边遍历边计数。,操作接口：,public int length(),int i=0;,Node p=this.head;,while(p!=null),i+;,p=p.next;,return i;,带头结点的单链表,(,书,P48),单链表的逆转,(,书,P53),【,例,2.2】,采用单链表求解约瑟夫环问题。,5,、应用举例,6,、应用举例：两个链表的归并,算法要求：,已知：,线性表,A,、,B,，分别由,单链表,LA,LB,存储，其中数据元素按值,非递减有序,排列。,要求：,将,A,，,B,归并,为一个新的线性表,C,C,的数据元素仍按值非递减排列 。设线性表,C,由,单链表,LC,存储。,假设：,A=,（,3,，,5,，,8,，,11,），,B=,（,2,，,6,，,8,，,9,，,11,）,预测：,合并后,C=,（,2,3,5,6,8,8,9,11,，,11,）,用链表可表示为：,3,5,11,/,8,La,2,6,11,/,8,Lb,9,2,3,6,5,Lc,8,头结点,La,Lb,Lc,算法分析：,算法主要包括：,搜索、比较、插入,三个操作：,搜索：,需要,两个指针,遍历两个链表；,比较：,比较结点数据域中数据的大小；,插入：,将两个结点中数据,小的结点插入新链表,。,3,5,8,11,Lb,2,6,8,11,9,Pa,Pb,Pa,Pb,Pa,、,Pb,用于搜索,La,和,Lb,，,Pc,指向新链表当前结点,Lc,Pa,3,Pc,Pa,5,Pc,11,Pc,2,Pb,Pc,Pa,La,思考：,1,、不用,Lc,，直接把,La,表插到,Lb,表中；或者把,Lb,表,插到,La,表中，如何编程？,2,、要求不能有重复的数据元素，如何编程？,Thanks,！待续！,