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链表的存储表示,存储特点：逻辑次序和物理次序不一定相同。2.元素之间的逻辑关系用地址表示。,例：(a1,a2,a3,a4)的存储示意图,1、链表的存储特点,a10200,a20325,a30300,a4,链表是由若干结点构成的；每个结点结构有两个部分组成：,数据域,地址域,data：存储数据元素next：存储指向后继结点的地址,2、有关的术语,1）结点：数据元素的存储映像。由数据域和地址域两部分组成；2）链表：n个结点由地址链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。3）单链表、双链表、多链表、循环链表：结点只有一个地址域的链表，称为单链表或线性链表；有两个地址域的链表，称为双链表；有多个地址域的链表，称为多链表；首尾相接的链表称为循环链表。,头指针是指向链表中第一个结点（或为头结点或为首元结点）的地址。头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志或表长等信息;首元结点是指链表中存储线性表第一个数据元素a1。,4）头指针、头结点和首结点,上例链表的逻辑结构示意图有以下两种形式：,a1,a2,/,a4,a3,H,a1,a2,/,a4,a3,H,区别：无头结点(链式队列、链栈常用)有头结点(链表常用),答：,讨论1.在链表中设置头结点有什么好处？,讨论2.如何表示空表？,头结点即在链表的首元结点之前附设的一个结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便,常用头结点。,答：,无头结点时，当头指针的值为空时表示空表；有头结点时，当头结点的地址域为空时表示空表。,h=NULL,H.next=NULL,publicclassNode/单链表结点类publicEdata;/数据域，保存数据元素publicNodenext;/地址域，引用后继结点,3、单链表的存储结构定义(重点及难点),1)单链表结点类Node声明：,publicNode（Edata,Nodenext/构造结点this.data=data;this.next=next;publicNode(Edata)this(data,null);publicNode()this(null,null);,head,data,next,如何申请一个结点？,Nodep,q;p=newNode(A);q=newNode(B);p.next=q;,单链表的头指针head也是一个引用，声明如下：Nodehead=null;,当head=null时，表示空单链表。,线性表接口LList,publicinterfaceLList/纯性表接口booleanisEmpty();/判断线性表是否为空，若空返回trueintlength();/返回线性表长度；Eget(intindex);/返回序号为index的对象，index初值为0Eset(intindex,Eelement);/设置序号为index对象为element，返回原对象booleanadd(intindex,Eelement);/插入element对象，插入后对象序号为indexbooleanadd(Eelement);/插入element对象，插入位置没有约定Eremove(intindex);/移去序号为index的对象，返回被移动对象voidclear();/清空线性表；,BACK,）单链表类声明（书P48）,publicclassSinglyLinkedListimplementsLList/单链表类，实现线性表接口protectedNodehead;/头指针publicSinglyLinkedList()/构造空单链表this.head=newNode();,2.3.2单链表的操作实现,单链表的遍历单链表的插入3.单链表的删除4.其它操作实现5.应用举例,1、单链表的遍历操作接口：基本步骤：从首结点开始，一个一个输出至尾结点。算法实现：,head,a0,a1,an,ai,P=NULL时结束,a0,a1,ai,an,Nodep=head;while(p!=null)System.out.print(p.data.toString()+”);p=p.next;,a1,a2,p.next,p+;,2单链表的查找(按位查找),操作接口：（书P49）publicEget(intindex);,head,a0,a1,an,ai,顺藤摸瓜,按位查找算法实现：publicEget(inti)if(i=0)Nodep=this.head.next;intj=0;while(p,核心操作（关键操作）：P指针后移。从首结点出发，通过指针的反复后移而将整个单链表“审视”一遍的方法称为扫描（或遍历）。思考：按值查找如何实现。（略）,3、单链表插入,操作接口：publicbooleanadd(intindex,Eelement),(1)空表插入/头插入,if(head=null)head=newNode(x);elseNodeq=newNode(x);q.next=head;head=q;,如何实现结点ai-1、x和ai之间逻辑关系的变化？,Nodeq=newNode(x);Step1:q.next=p.next;Step2:p.next=q;,插入步骤（即核心语句）：,思考：步骤1和2能互换么？,不能互换！,(2)中间插入/尾插入,算法：在单链表L中第i个位置之前插入元素x。基本思想：（1）找到插入点（p将指向第i-1个结点）；平均时间复杂度为O(n)；（2）新建插入结点；（3）修改相应结点的地址域，实现插入，其时间复杂度为O(1)。注：先修改新结点的地址域，再修改链表的地址域。,插入算法实现（P50）,基本语句？时间复杂度？,4、单链表的删除,操作接口：publicEremove(intindex),头删除head=head.next;中间/尾删除if(p.next!=null)p.next=p.next.next;,算法：在带头结点的单链表L中删除第i个结点，并返回该结点的值。基本思想：（1）找到删除点（指针p将指向第i-1个结点）；/平均查找时间复杂度为O(n)判i的合法性：i=1Nodep=this.head;while(p!=null)i+;p=p.next;returni;,带头结点的单链表(书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）,用链表可表示为：,头结点,La,Lb,Lc,算法分析：,算法主要包括：搜索、