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

,第二章线性表,(之一),数据结构课程的内容,逻辑结构唯一存储结构不唯一运算的实现依赖于存储结构,线性表的逻辑结构线性表的顺序存储及实现线性表的链接存储及实现顺序表和单链表的比较线性表的其他存储及实现,本章的基本内容是：,（a1,a2,ai-1，ai,ai1，,an）,1.线性表的定义：n(n0)个相同类型数据元素的有限序列。,n=0时称为,数据元素,线性起点,ai的直接前趋,ai的直接后继,下标，是元素的序号，表示元素在表中的位置,n为元素总个数，即表长,空表,线性终点,2.1线性表的逻辑结构,例1分析26个英文字母组成的英文表,（A,B,C,D,Z）,例2分析学生情况登记表,数据元素都是记录;元素间关系是线性,数据元素都是字母;元素间关系是线性的。,2、线性表的特性,1）.有限性：线性表中数据元素的个数是有穷的。,2）.相同性：线性表中数据元素的类型是同一的。,3）.顺序性：线性表中相邻的数据元素ai-1和ai之间存在序偶关系，即ai-1是ai的前驱，ai是ai-1的后继；a1无前驱，an无后继，其它每个元素有且仅有一个前驱和一个后继。,练：判断下列叙述的正误：,1.数据的逻辑结构是指数据元素之间的逻辑关系，是用户按使用需要建立的。2.线性表的逻辑结构定义是唯一的，不依赖于计算机。3.线性结构反映结点间的逻辑关系是一对一的。4.一维向量是线性表，但二维或N维数组不是。5.“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。,3、线性表的操作,线性表接口LList声明如下，描述线性表的取值、置值、插入、删除等基本操作。packagedataStructure.linearList;/声明属于的包publicinterfaceLList/纯性表接口booleanisEmpty();/判断线性表是否为空，若空返回trueintlength();/返回线性表长度；Eget(intindex);/返回序号为index的对象，index初值为0,BACK,BACK,Eset(intindex,Eelement);/设置序号为index对象为element，返回原对象booleanadd(intindex,Eelement);/插入element对象，插入后对象序号为indexbooleanadd(Eelement);/插入element对象，插入位置没有约定Eremove(intindex);/移去序号为index的对象，返回被移动对象voidclear();/清空线性表；,进一步说明:（1）线性表的基本操作根据实际应用而定；（2）复杂的操作可以通过基本操作的组合来实现；（3）对不同的应用，操作的接口可能不同。,BACK,2.2线性表的顺序存储和实现,2.2.1顺序表的顺序存储表示2.2.2顺序表的实现2.2.3顺序表的算法效率分析,本节小结,2.2.1顺序表的顺序存储表示,用一组地址连续的存储单元依次存储线性表的元素，可通过静态数组Vn或动态数组来实现。,把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。,线性表的顺序表示又称为顺序存储结构或顺序映像。,顺序存储定义：,顺序存储方法：,简言之，逻辑上相邻，物理上也相邻,“顺序表是一种随机存取的存储结构”的含义为：查找操作，其时间性能为O(1)。,线性表顺序存储特点：,1.逻辑上相邻的数据元素，其物理上也相邻；2.若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组下标）。计算方法是（参见存储结构示意图）：设首元素a1的存放地址为LOC(a0)（称为首地址），设每个元素占用存储空间（地址长度）为c字节，则表中任一数据元素的存放地址为：LOC(ai)=LOC(a0)+i*cLOC(ai+1)=LOC(a0)+(i+1)*c,注意：JAVA语言中的数组的下标从0开始，即：Vn的有效范围是V0Vn-1,线性表的顺序存储结构示意图,一个一维数组，下标的范围是到，每个数组元素用相邻的个字节存储。存储器按字节编址，设存储数组元素的第一个字节的地址是，则的第一个字节的地址是,113,例3、,因此：LOC(M3)=98+35=113,解：地址计算通式为：,2.2.2顺序表的实现,1）顺序表的存储结构定义(即顺序表类的声明)：packagedataStructure.linearlist;importdataStructure.linearlist.Llist;publicclassSeqListimplementsLlist/顺序表类SeqList，实现线性表接口privateObjecttable;/对象数据，私有成员privateintn;/顺序表的长度publicSeqList();/指定空表的默认容量publicSeqList(intcapacity);/创建指定容量的空表publicbooleanisEmpty()；/判断顺序表是否为空publicintlength();/求顺序表的长度publicEget(intindex)/返回index位置的对象publicEset(intindex,Eelement)/设置index位置的对象为element,若成功返回原对象，否则返回nullpublicbooleanadd(intindex,Eelement);/在第index个位置插入对象elementpublicvoidclear();/清空顺序表,2）顺序表的操作实现(即顺序表类的定义实现P37-40)：,publicSeqList();/指定空表的默认容量publicSeqList(intcapacity);/创建指定容量的空表publicbooleanisEmpty()；/判断顺序表是否为空publicintlength();/求顺序表的长度publicEget(intindex)/返回index位置的对象publicEset(intindex,Eelement)/设置index位置的对象为element,若成功返回原对象，否则返回null,操作接口publicbooleanadd(intindex,Eelement);/在第index个位置插入对象element插入前：(a0,ai-1,ai,an-1)插入后：(a0,ai-1,item,ai,an-1),插入操作实现,ai-1和ai之间的逻辑关系发生了变化,顺序存储要求存储位置反映逻辑关系,存储位置要反映这个变化,插入操作图示,例如：（35，12，24，42），在index=2的位置上插入33。,表满：this.n=table.length合理的插入位置：0indextable.length-1,4,35,12,24,42,a0,a1,a2,a3,01234,42,24,12,33,什么时候不能插入？,插入：在顺序表的第index个位置插入一个元素,实现步骤：将第n-1至第index位的元素向后移动一个位置；将要插入的元素写到第index个位置；表长加1。注意：事先应判断:插入位置index是否合法?表是否已满?,JAVA具体实现：publicbooleanadd(intindex,Eelement)if(element=null)returnfalse;/不能插入nullif(this.n=table.length)/若数组满，则需要扩充顺序表容量Objecttemp=this.table;this.table=newObjecttemp.length*2;for(inti=0;ithis.n)index=this.n;for(intj=this.n-1;j=index;j-)/元素后移this.tablej+1=this.tablej;this.tableindex=element;this.n+;returntrue;,操作接口publicEremove(intindexx)删除前：(a1,ai-1,ai,ai+1,an)删除后：(a1,ai-1,ai+1,an),ai-1和ai之间的逻辑关系发生了变化,顺序存储要求存储位置反映逻辑关系,存储位置要反映这个变化,删除操作实现,删除操作图示,例：（35,33,12,24,42），删除index=2的数据元素。,5,35,a1,a2,a3,a4,01234,42,24,12,33,a5,12,24,42,表空：this.n=0合理的删除位置：0indexthis.n,什么时候不能删除？,实现步骤：获得index位置上要删除的元素值;将位置为index至this.n-1的元素向前移动一个位置；表长减1。注意：事先需要判断，删除位置index是否合法?应当有0index=0,时间复杂度？,O(1),2.2.3顺序表的算法效率分析,插入、删除算法时间主要耗费在移动元素的操作T(n)=O(移动元素次数)移动元素的次数取决于插入或删除元素的位置。,讨论1：若在长度为n的线性表的第i位前插入一元素，则向后移动元素的次数f(n)为:f(n)=,ni+1,时间效率分析:,最好情况（i=n+1）：移动元素次数0次，时间复杂度为O(1)。最坏情况（i=1）：移动元素次数n次，时间复杂度为O(n)。平均情况（1in+1）：时间复杂度为O(n)。,讨论2：若在长度为n的线性表上删除第i位元素，向前移动元素的次数f(n)为：f(n)=,ni,讨论3：顺序表的插入、删除操作算法空间复杂度S(n)=O(1),最好情况（i=n）：移动元素次数0次，时间复杂度为O(1)。最坏情况（i=1）：移动元素次数n-1次，时间复杂度为O(n)。平均情况（1in）：时间复杂度为O(n)。,应用实例：（上机练习题提示）设有线性表LA（3,5,8,11）和LB=（2,6,8,9,11,15,20）；若LA和LB分别表示两个集合A和B，求新集合AAUB（并操作，相同元素不保留）；,按规律插入,插入到尾部,预测输出：LA=（3,5,8,11,2,6,9,15,20）将LA与L