1、单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,线性表,1,主要内容,1,何为线性表,?,2,线性表的抽象数据类型,3,顺序表,.,何为顺序表,?,.,顺序表的设计与使用,.Java,类库中的顺序表及其使用,2,线性表,线性表（,Linear List,）是一种可以在任意位置进行插入和删除数据元素操作的、由,n(n=0,）个相同类型数据元素,a0,，,a1,，,ai,，,ai+1,an-1,组成的一个有限序列。,线性表的逻辑结构是线性结构；,线性表的存储结构可以有多种，最常用的两种是：顺序存储结构 和 链接存储结构。,3,线性表的抽象数据类型,抽象数据
2、类型,(ADT:abstract data structure),是一组数据以及定义在其上一组操作的集合,.,线性表的抽象数据类型主要包含两个方面：,即,:,数据集合和该数据集合上操作的集合。,4,线性表的数据集合,线性表的数据元素集合可以表示为序列,a0,，,a1,，,ai,，,ai+1,an-1,每个数据元素可以是任意类型的。,在,Java,中，可以用类定义数据元素的数据类型。,5,线性表的操作集合,线性表的操作集合用来说明线性表所需要实现的功能，其基本操作大致如下：,添加数据元素：在线性表的末尾添加一个数据元素。,插入数据元素：在线性表第,i,个元素前插入一个数据元素。,删除数据元素：删
3、除线性表中第,i,个数据元素。,获取数据元素：获取线性表中第,i,个数据元素。,遍历线性表：从第一个元素开始，逐个访问线性表中的每个数据元素。,获取当前线性表中的元素个数。求当前线性表中的元素个数。,判断线性表是否为空。判断当前线性表中是否还有元素。,在,Java,中，可以用接口或抽象类来定义线性表的操作集合。,6,顺序表,使用顺序结构存储数据的线性表称为顺序表,.,7,顺序表的设计与实现步骤,在确定了数据的存储结构以后,按下面步骤设计顺序表,.,数据元素定义,-,类,数据操作定义,-,抽象类或接口,实现顺序表,-,一个实现,数据操作的类,8,使用顺序表,项目实践：,例题,2-1,用顺序表实现
4、学生成绩信息管理程序,.,程序运行主界面见上图,.,该程序文件名为,ArrStudent.java,包含下面,3,个类,1,个接口,.,StudScore,类,定义数据元素,(,学生,),StudOperation,接口,定义数据操作,ArrStudent,类,顺序表,ArrStudentUser,类,完成学生成绩管理程序,9,修改完善例题,2-1,的学生成绩管理程序。,修改接口,StudOPeration,，为程序添加操作如下：,获取学生记录个数,根据学生姓名查询学生信息,根据学生姓名删除学生的信息,在指定位置处插入学生的信息,修改顺序表类,ArrStudent,，实现上述操作。,修改类,A
5、rrStudentUser,，完成上述功能的使用。,实战演练,10,Java,类库中的顺序表,Java,类库中的,java.util.ArrayList,类实现了顺序表的功能,其中常用的构造器和方法如下,:,public Arraylist(int initialcapacity)/,创建指定容量的顺序表,public boolean add(Object obj)/,在表尾添加一个元素,public boolean remove(Object obj)/,删除表尾元素,public Object remove(int index)/,删除指定位置的元素,public Object get(i
6、nt index)/,获取指定位置的元素,public int indexOf(Object obj)/,获取某个元素的位置,11,实战演练,使用,java.util.ArrayList,完成学生成绩管理程序,.,12,使用,java,类库中顺序表,java.util.ArrayList,设计程序的步骤,导入顺序表类,java.util.ArrayList,定义数据元素,使用顺序表,13,顺序表的效率分析,顺序表支持随机读取，顺序表读取数据元素操作的时间复杂度为,O(1),。,在顺序表中插入和删除一个数据元素的时间复杂度为,O(n),。,顺序表的主要优点是支持随机读取，以及内存空间利用率高。,顺序表的主要缺点是需要预先给出表中数据元素的个数，而这个很难准确做到。另外，顺序表在进行插入和删除操作时，需要移动大量的数据元素。,14,
浙ICP备2021020529号-1 | 浙B2-20240490 
