《JAVA数据结构第二章线性表A.ppt》由会员分享，可在线阅读，更多相关《JAVA数据结构第二章线性表A.ppt（34页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程的内容数据结构课程的内容逻辑结构唯一逻辑结构唯一存储结构不唯一存储结构不唯一运算的实现依赖运算的实现依赖于存储结构于存储结构线性表线性表逻辑结构逻辑结构存储结构存储结构基基本本概概念念抽象抽象数据数据类型类型定义定义线性表定义线性表定义逻辑特征逻辑特征ADTADT定义定义基本操作基本操作顺顺序序存存储储链链接接存存储储其其他他存存储储顺序表的特点顺序表的特点顺序表类定义顺序表类定义基基本本操操作作的的实实现及时间性能现及时间性能单链表的特点单链表的特点单链表类定义单链表类定义基基本本操操作作的的实实现及时间性能现及时间性能 比比 较较循环链表循环链表双链表双链表静态链表静态链表线性
2、表的应用线性表的应用 线性表的逻辑结构线性表的逻辑结构 线性表的顺序存储及实现线性表的顺序存储及实现 线性表的链接存储及实现线性表的链接存储及实现 顺序表和单链表的比较顺序表和单链表的比较 线性表的其他存储及实现线性表的其他存储及实现本章的基本内容是：本章的基本内容是：（a1, a2, ai-1，ai, ai1 ，, an）1. 线线性性表表的的定定义义：n(n0)个个相相同同类类型型数数据据元元素素的有限序列。的有限序列。n=0时称为时称为数据元素数据元素线性起点线性起点ai的直接前趋的直接前趋ai的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中
3、的位置n n为元素总个为元素总个数，即数，即表长表长空表空表线性终点线性终点2.1 2.1 线性表的逻辑结构线性表的逻辑结构 例例1 分析分析26 个英文字母组成的英文表个英文字母组成的英文表 （ A, B, C, D, , Z）学号学号姓名姓名性别性别年龄年龄班级班级2005011810205于春梅于春梅女女 182005级计信级计信016班班2005011810260何仕鹏何仕鹏男男 182005级计信级计信017班班2005011810284王王 爽爽女女 182005级通信级通信011班班2005011810360王亚武王亚武男男 182005级通信级通信012班班： ：例例2 分析学
4、生情况登记表分析学生情况登记表数据元素都是记录数据元素都是记录; 元素间关系是线性元素间关系是线性数据元素都是字母数据元素都是字母; 元素间关系是线性的。元素间关系是线性的。a1a3a4ana22、线性表的、线性表的特性特性1 1）. .有限性：有限性：线性表中数据元素的个数是有穷的。线性表中数据元素的个数是有穷的。2 2）. .相同性：相同性：线性表中数据元素的类型是同一的。线性表中数据元素的类型是同一的。3 3）. .顺序性：顺序性：线性表中相邻的数据元素线性表中相邻的数据元素a ai i-1-1和和a ai i之间存之间存在序偶关系在序偶关系 ，即，即a ai i-1-1是是a ai i
5、的前驱，的前驱， a ai i是是a ai i-1-1的后继；的后继；a a1 1 无前驱，无前驱，a an n无后继，其它每个元素有且仅无后继，其它每个元素有且仅有一个前驱和一个后继。有一个前驱和一个后继。 练：判断下列叙述的正误：练：判断下列叙述的正误：1. 数数据据的的逻逻辑辑结结构构是是指指数数据据元元素素之之间间的的逻逻辑辑关关系系，是用户按使用需要建立的。是用户按使用需要建立的。2. 线线性性表表的的逻逻辑辑结结构构定定义义是是唯唯一一的的，不不依依赖赖于于计计算机。算机。3. 线性结构反映结点间的逻辑关系是一对一的。线性结构反映结点间的逻辑关系是一对一的。4.一维向量是线性表，但
6、二维或一维向量是线性表，但二维或N维数组不是。维数组不是。5.“同同一一数数据据逻逻辑辑结结构构中中的的所所有有数数据据元元素素都都具具有有相相同同的的特特性性”是是指指数数据据元元素素所所包包含含的的数数据据项项的的个个数数都相等。都相等。3、线性表的操作、线性表的操作线性表接口线性表接口LList声明如下，描述线性表的取值、置声明如下，描述线性表的取值、置值、插入、删除等基本操作。值、插入、删除等基本操作。package dataStructure.linearList;/声明属于的包声明属于的包public interface LList/纯性表接口纯性表接口boolean isEmpt
7、y();/判断线性表是否为空，若空返回判断线性表是否为空，若空返回trueint length(); /返回线性表长度；返回线性表长度；E get(int index);/返回序号为返回序号为index的对象，的对象，index初值为初值为0BACKBACKE set(int index, E element);/设置序号为设置序号为indexindex对象为对象为elementelement，返回原对象，返回原对象boolean add(int index, E element);/插入插入elementelement对象，插入后对象序号为对象，插入后对象序号为indexindexboole
8、an add(E element);/插入插入elementelement对象，插入位置没有约定对象，插入位置没有约定E remove(int index);/移去序号为移去序号为index的对象，返回被移动对象的对象，返回被移动对象void clear();/清空线性表；清空线性表；进一步说明进一步说明: :（1 1）线性表的基本操作根据实际应用而定；）线性表的基本操作根据实际应用而定；（2 2）复杂的操作可以通过基本操作的组合来实现；）复杂的操作可以通过基本操作的组合来实现；（3 3）对不同的应用，操作的接口可能不同。）对不同的应用，操作的接口可能不同。BACK2.2 2.2 线性表的顺序
9、存储和实现线性表的顺序存储和实现2.2.1 顺序表的顺序存储表示顺序表的顺序存储表示2.2.2 顺序表的实现顺序表的实现2.2.3 顺序表的算法效率分析顺序表的算法效率分析本节小结本节小结2.2.1顺序表的顺序存储表示顺序表的顺序存储表示用用一一组组地地址址连连续续的的存存储储单单元元依依次次存存储储线线性性表表的的元元素素，可可通通过过静静态态数数组组VnVn 或动态数组或动态数组来实现。来实现。把逻辑上相邻的数据元素存储把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。在物理上相邻的存储单元中的存储结构。线性表的顺序表示又称为线性表的顺序表示又称为顺序存储结构顺序存储结构或或顺
10、序映像顺序映像。顺序存储定义：顺序存储定义：顺序存储方法顺序存储方法：简言之，逻辑上相邻，物理上也相邻简言之，逻辑上相邻，物理上也相邻“顺序表顺序表是一种是一种随机存取随机存取的的存储存储结构结构”的含义为：查的含义为：查找操作，其时间性能为找操作，其时间性能为O(1)。线性表顺序存储特点：线性表顺序存储特点：1. 逻辑上相邻的数据元素，其物理上也相邻；逻辑上相邻的数据元素，其物理上也相邻；2. 若已知表中首元素在存储器中的位置，则其他元若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（素存放位置亦可求出（利用数组下标利用数组下标）。计算方法）。计算方法是（是（参见存储结构示意图参
11、见存储结构示意图）：）：设首元素设首元素a1的存放地址为的存放地址为LOC(a0)（称为称为首地址首地址），），设每个元素占用存储空间（地址长度）为设每个元素占用存储空间（地址长度）为c字节，字节，则表中任一数据元素的则表中任一数据元素的存放地址存放地址为：为： LOC(ai) = LOC(a0) + i*c LOC(ai+1) = LOC(a0)+ (i+1)*c 注意：注意：JAVAJAVA语言中的数组的下标从语言中的数组的下标从0 0开始，开始， 即：即：VnVn 的有效范围是的有效范围是V0V0Vn-1Vn-1线性表的顺序存储结构示意图线性表的顺序存储结构示意图一个一维数组，下标的范围
12、是到，一个一维数组，下标的范围是到，每个数组元素用相邻的每个数组元素用相邻的个字节个字节存储。存储存储。存储器按字节编址，设存储数组元素器按字节编址，设存储数组元素 的第的第一个字节的地址是一个字节的地址是，则，则 的第一个的第一个字节的地址是字节的地址是 113例例3、因此：因此：LOC( M3 ) = 98 + 35=113解：解：地址计算通式为：地址计算通式为：2.2.2 顺序表的实现顺序表的实现1 1）顺序表的存储结构定义）顺序表的存储结构定义( (即顺序表类的声明即顺序表类的声明) )：package dataStructure.linearlist;import dataStruc
13、ture.linearlist.Llist;public class SeqList implements Llist/顺序表类顺序表类SeqList，实现线性表接口，实现线性表接口 private Object table; /对象数据，私有成员对象数据，私有成员 private int n; /顺序表的长度顺序表的长度 public SeqList( ); /指定空表的默认容量指定空表的默认容量 public SeqList(int capacity); /创建指定容量的空表创建指定容量的空表 public boolean isEmpty()；/判断顺序表是否为空判断顺序表是否为空 pub
14、lic int length(); /求顺序表的长度求顺序表的长度 public E get(int index) /返回返回index位置的对象位置的对象 public E set(int index, E element) /设置设置index位置的对象为位置的对象为element,若成功返回原对象，否则返回若成功返回原对象，否则返回null public boolean add(int index, E element); /在第在第index个位置个位置插入对象插入对象element public void clear(); /清空顺序表清空顺序表2 2）顺序表的操作实现）顺序表的操作
15、实现( (即顺序表类的定义实现即顺序表类的定义实现P37-40)P37-40)： public SeqList( ); /指定空表的默认容量指定空表的默认容量 public SeqList(int capacity); /创建指定容量创建指定容量的空表的空表 public boolean isEmpty()；/判断顺序表是否判断顺序表是否为空为空 public int length(); /求顺序表的长度求顺序表的长度 public E get(int index) /返回返回index位置的对象位置的对象 public E set(int index, E element) /设置设置ind
16、ex位位置的对象为置的对象为element,若成功返回原对象，否则返回若成功返回原对象，否则返回null操作接口操作接口public boolean add(int index, E element); /在第在第index个位置插入对象个位置插入对象element插入前：插入前：(a0, , ai-1, ai, , an-1)插入后：插入后：(a0, , ai-1, item , ai, , an-1)插入操作实现插入操作实现ai-1和和ai之间的逻辑关系发生了变化之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化存储位置要反映这个
17、变化插入操作图示33例如：（例如：（35，12，24，42），在），在index=2的位置上的位置上插入插入33。表满：表满：this.n=table.length合理的插入位置：合理的插入位置：0indextable.length-1 435122442a0a1a2a30 1 2 3 4422412335什么时候不能插入什么时候不能插入？注意边界条件注意边界条件插入：插入：在顺序表的第在顺序表的第indexindex个位置个位置插入插入一个元素一个元素实现步骤：实现步骤：将第将第n-1至第至第index位的元素向后移动一个位置；位的元素向后移动一个位置；将要插入的元素写到第将要插入的元素写到
18、第index个位置；个位置；表长加表长加1。注意：注意：事先应判断事先应判断: 1.插入位置插入位置index是否合法是否合法?2.表是否已满表是否已满? JAVA具体实现：具体实现：public boolean add(int index, E element) if (element=null) return false; /不能插入不能插入null if (this.n=table.length) /若数组满，则需要扩充顺序表容量若数组满，则需要扩充顺序表容量Object temp=this.table; this.table=new Objecttemp.length*2; for (
19、int i=0;itemp.length;i+)/复制数组元素复制数组元素this.tablei=tempi; if (indexthis.n) index=this.n; for (int j=this.n-1;j=index;j-)/元素后移元素后移this.tablej+1=this.tablej; this.tableindex=element; this.n+; return true;操作接口操作接口public E remove(int index x)删除前：删除前：(a1, , ai-1,ai,ai+1,an)删除后：删除后：(a1,ai-1,ai+1, ,an) ai-1和
20、和ai之间的逻辑关系发生了变化之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化存储位置要反映这个变化删除操作实现删除操作实现删除操作图示例：（例：（35, 33, 12, 24, 42），删除），删除index=2的数据元的数据元素。素。 535a1a2a3a40 1 2 3 4422412334a5122442表空：表空： this.n=0合理的删除位置：合理的删除位置：0indexthis.n什么时候不能删除什么时候不能删除？实现步骤：实现步骤：获得获得index位置上要删除的元素值位置上要删除的元素值;将位置为将位置为inde
21、x 至至this.n-1的元素向前移动一的元素向前移动一个位置；个位置；表长减表长减1。注意：注意：事先需要判断，事先需要判断，删除位置删除位置index是否合法是否合法?应当有应当有0index=0 & indexthis.n) E old=(E) this.tableindex; for (int j=index;j=0 & indexthis.n) return (E)this.tableindex; return null;时间复杂度时间复杂度？O(1)2.2.3顺序表的算法效率分析顺序表的算法效率分析插入、删除算法时间主要耗费在插入、删除算法时间主要耗费在移动元素移动元素的操作的操作
22、 T(n)= O (移动元素次数移动元素次数)移动元素的次数取决于插入或删除元素的位置。移动元素的次数取决于插入或删除元素的位置。讨论讨论1：若在长度为若在长度为 n 的线性表的第的线性表的第 i 位前位前 插入一元素，插入一元素，则向后移动元素的次数则向后移动元素的次数f(n)为为:f(n) =n i + 1时间效率分析时间效率分析:最好最好情况（情况（ i =n+1）：移动元素次数）：移动元素次数0次，时间复杂次，时间复杂度为度为O(1)。最坏最坏情况（情况（ i =1）：移动元素次数）：移动元素次数n次，时间复杂度为次，时间复杂度为O(n)。平均平均情况（情况（1in+1）：时间复杂度为
23、）：时间复杂度为O(n)。 + +- -+ += =11)=1(niiinp + +- -+ + += =11)=1(11niinn2nO(n) 讨论讨论2：若在长度为若在长度为n n的线性表上删除第的线性表上删除第i i位元素，向位元素，向前移动元素的次数前移动元素的次数f(nf(n) )为：为： f(nf(n) =) = n i讨论讨论3 3：顺序表的插入、删除操作算法顺序表的插入、删除操作算法空间空间复杂度复杂度S(nS(n)=O(1)=O(1)最好最好情况（情况（ i =n）：移动元素次数）：移动元素次数0次，时间复杂度为次，时间复杂度为O(1)。最坏最坏情况（情况（ i =1）：移动
24、元素次数）：移动元素次数n-1次，时间复杂度次，时间复杂度为为O(n)。平均平均情况（情况（1in）：时间复杂度为）：时间复杂度为O(n)。 - -= =1)=(niiinp - -= =1)=(1niinn2n-1O(n) 应用实例：应用实例：（上机练习题提示）（上机练习题提示）设有线性表设有线性表 LALA（3,5,8,113,5,8,11）和）和 LB=LB=（2,6,8,9,11,15,202,6,8,9,11,15,20）；）； 若若LALA和和LBLB分别表示两个集合分别表示两个集合A A和和B B，求新集合，求新集合 A AA U BA U B（并并操作，相同元素不保留）；操作，
25、相同元素不保留）；按规律插入按规律插入插入到尾部插入到尾部预测输出：预测输出：LA=LA=（3,5,8,11,2,6,9,15,203,5,8,11,2,6,9,15,20） 将将LALA与与LBLB表归并，要求仍有序（相同元素要保留）表归并，要求仍有序（相同元素要保留）预测输出：预测输出：LC=LC=（2,3,5,6,8,8,9,11,11,15,202,3,5,6,8,8,9,11,11,15,20）本本 节节 小小 结结线性表线性表顺序存储结构特点顺序存储结构特点：逻辑关系上相邻的两个元：逻辑关系上相邻的两个元素在物理存储位置上也相邻；素在物理存储位置上也相邻；优点：优点：可以随机存取表中任一元素；可以随机存取表中任一元素；缺点：缺点：(1)(1)在插入，删除某一元素时，平均要移动一半元素，在插入，删除某一元素时，平均要移动一半元素，平均时间复杂度平均时间复杂度O(nO(n) )。 表的容量难以确定，表的容量难以扩充；表的容量难以确定，表的容量难以扩充； 易造成存储空间的易造成存储空间的碎片碎片。为克服这些缺点，我们引入另一种存储形式：为克服这些缺点，我们引入另一种存储形式： 链式存储。链式存储。ThanksThanks！待续！待续！
