第2章 线性表(java版)ppt课件.ppt

《第2章 线性表(java版)ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性表教学内容2.2线性表的顺序存储及其实现2.3线性表的链式存储及其实现2.4顺序表与链表的比较2.1线性表及其基本操作2.5线性表的应用举例教学重点与难点重点：顺序表与链表类的描述方法；在两种存储结构上实现线性表的基本操作的算法。难点：线性表在两种存储结构上的插入、删除算法及动态链表的创建算法。课前思考按数据元素之间的逻辑关系不同，数据结构有哪几类？你能举出几个你熟悉的“序列”的例子来吗？线性结构、树型结构、图型结构和集合四类。如："0，1，2，…，9","A，B，C，…，Z"。2.1.1线性表的基本概念1.线性表的定义：一个线

2、性表（LinearList）是由n(n≥0)个数据元素（结点）所构成的有限序列。线性表逻辑地表示为：（a0,a1,…,an-1)。其中，n为线性表的长度，n=0时为空表。称i为ai在线性表中的位序号。2.1.1线性表的基本概念2.线性表的结构（逻辑结构）特点：c.每个元素除第一个元素和最后一个元素之外,有且仅有一个前驱和一个后继。学号姓名大学英语高等数学计算机文化基础总分200853174101王一608178219200853174102刘二947682252200853174103张三907872240200853174104李四85

3、7371229………………开始结点终端结点a.它由n个同类型的元素组成；b.有且仅有一个第一个元素和最后一个元素；2.1.2线性表的抽象数据类型描述1.基本操作clear()1）线性表的置空操作：isEmpty()2）线性表判空操作：length()3）求线性表的长度：4）取元素操作：5）插入操作：get(i)insert(i,x)6）删除操作：remove(i)7）查找操作：indexOf(x)8）输出操作：display()2.1.2线性表的抽象数据类型描述2.线性表抽象数据类型的Java接口描述publicinterfaceILis

4、t{}publicvoidclear();publicbooleanisEmpty();publicintlength();publicObjectget(inti);publicvoidinsert(inti,Objectx);publicvoidremove(inti);publicintindexOf(Objectx);publicvoiddisplay();2.2.1线性表的顺序存储线性表的起始地址称作线性表的基地址a0a1…ai-2ai-1…an-11.概念(1)顺序存储：(2)顺序表：用顺序存储的线性表就称为顺序表n为表的长度

5、用一组地址连续的存储单元依次存放线性表中的数据元素的存储结构。01i-2i-1n-12.2.1线性表的顺序存储2.地址计算公式以“存储位置相邻”表示有序对即：LOC(ai)=LOC(ai-1)+C一个数据元素所占的存储量所有数据元素的存储位置均取决于第一个数据元素的存储位置↑LOC(ai)=LOC(a0)+i×C↑基地址2.2.1线性表的顺序存储存储地址内在状态元素在线性表的位序号a0a1aian-1………b(基地址）b+Cb+i*Cb+(n-1)*Cb+(maxSize-1)*C01in-1空闲……2.2.1线性表的顺

6、序存储3.特点(1)逻辑上相邻的数据元素，赋以相邻的存储位置；(2)存储密度高；存储密度：数据元素的值所需的存储空间d=该元素实际所需的存储空间(4)不便于插入、删除操作。（会引起大量结点的移动）(3)便于随机存取；2.2.1线性表的顺序存储4.顺序存储结构的描述publicclassSqListimplementsIList{}线性表的顺序存储结构在线性表Java接口的实现类中描述如下：listElemcurLen=6213211245744……012345maxSize-1线性表{21,32,11,24,57,44}顺序存储结构图pr

7、ivateObject[]listElem;//线性表存储空间privateintcurLen;//线性表的当前长度……2.2.1线性表的顺序存储5.顺序表类的描述（见书P33）publicclassSqListimplementsIList{privateObject[]listElem;privateintcurLen;}//构造一个容量为maxSize的空顺序表函数publicSqList(intmaxSize){}//顺序表置空函数publicvoidclear(){}……curLen=0;listElem=newObject[m

8、axSize];curLen=0;5.顺序表类的描述returncurLen;//判空函数publicbooleanisEmpty(){}//求顺序表长度函数publicintlength()