java数据结构第二章线性表a.ppt

《java数据结构第二章线性表a.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性表(之一)数据结构课程的内容逻辑结构唯一存储结构不唯一运算的实现依赖于存储结构线性表逻辑结构存储结构基本概念抽象数据类型定义⑴线性表定义⑵逻辑特征⑴ADT定义⑵基本操作顺序存储链接存储其他存储⑴顺序表的特点⑵顺序表类定义⑶基本操作的实现及时间性能⑴单链表的特点⑵单链表类定义⑶基本操作的实现及时间性能比较⑴循环链表⑵双链表⑶静态链表线性表的应用线性表的逻辑结构线性表的顺序存储及实现线性表的链接存储及实现顺序表和单链表的比较线性表的其他存储及实现本章的基本内容是：（a1,a2,…ai-1，ai,ai＋1，…,

2、an）1.线性表的定义：n(n≥0)个相同类型数据元素的有限序列。n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长空表线性终点2.1线性表的逻辑结构例1分析26个英文字母组成的英文表（A,B,C,D,……,Z）学号姓名性别年龄班级2005011810205于春梅女182005级计信016班2005011810260何仕鹏男182005级计信017班2005011810284王爽女182005级通信011班2005011810360王亚武男1820

3、05级通信012班：：：：：例2分析学生情况登记表数据元素都是记录;元素间关系是线性数据元素都是字母;元素间关系是线性的。a1a3a4ana22、线性表的特性1）.有限性：线性表中数据元素的个数是有穷的。2）.相同性：线性表中数据元素的类型是同一的。3）.顺序性：线性表中相邻的数据元素ai-1和ai之间存在序偶关系，即ai-1是ai的前驱，ai是ai-1的后继；a1无前驱，an无后继，其它每个元素有且仅有一个前驱和一个后继。练：判断下列叙述的正误：1.数据的逻辑结构是指数据元素之间的逻辑关系，是用

4、户按使用需要建立的。2.线性表的逻辑结构定义是唯一的，不依赖于计算机。3.线性结构反映结点间的逻辑关系是一对一的。4.一维向量是线性表，但二维或N维数组不是。5.“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。√×√√×3、线性表的操作线性表接口LList声明如下，描述线性表的取值、置值、插入、删除等基本操作。packagedataStructure.linearList;//声明属于的包publicinterfaceLList{//纯性表接口booleanisEm

5、pty();//判断线性表是否为空，若空返回trueintlength();//返回线性表长度；Eget(intindex);//返回序号为index的对象，index初值为0BACKBACKEset(intindex,Eelement);//设置序号为index对象为element，返回原对象booleanadd(intindex,Eelement);//插入element对象，插入后对象序号为indexbooleanadd(Eelement);//插入element对象，插入位置没有约定Eremove(inti

6、ndex);//移去序号为index的对象，返回被移动对象voidclear();//清空线性表；}进一步说明:（1）线性表的基本操作根据实际应用而定；（2）复杂的操作可以通过基本操作的组合来实现；（3）对不同的应用，操作的接口可能不同。BACK2.2线性表的顺序存储和实现2.2.1顺序表的顺序存储表示2.2.2顺序表的实现2.2.3顺序表的算法效率分析本节小结2.2.1顺序表的顺序存储表示用一组地址连续的存储单元依次存储线性表的元素，可通过静态数组V[n]或动态数组来实现。把逻辑上相邻的数据元素存储在物理上相邻的

7、存储单元中的存储结构。线性表的顺序表示又称为顺序存储结构或顺序映像。顺序存储定义：顺序存储方法：简言之，逻辑上相邻，物理上也相邻“顺序表是一种随机存取的存储结构”的含义为：查找操作，其时间性能为O(1)。线性表顺序存储特点：1.逻辑上相邻的数据元素，其物理上也相邻；2.若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组下标）。计算方法是（参见存储结构示意图）：设首元素a1的存放地址为LOC(a0)（称为首地址），设每个元素占用存储空间（地址长度）为c字节，则表中任一数据元素的存放地址为：LOC(

8、ai)=LOC(a0)+i*cLOC(ai+1)=LOC(a0)+(i+1)*c注意：JAVA语言中的数组的下标从0开始，即：V[n]的有效范围是V[0]～V[n-1]线性表的顺序存储结构示意图一个一维数组Ｍ，下标的范围是０到９，每个数组元素用相邻的５个字节存储。存储器按字节编址，设存储数组元素Ｍ[０]的第一个字节的地址是９８，则Ｍ[３]的第一个字节的地址是