数据结构Java版线性表顺序表ppt课件

线性表,1,主要内容,1何为线性表?2线性表的抽象数据类型3顺序表.何为顺序表?.顺序表的设计与使用.Java类库中的顺序表及其使用,2,线性表,线性表（LinearList）是一种可以在任意位置进行插入和删除数据元素操作的、由n(n=0）个相同类型数据元素a0，a1，ai，ai+1an-1组成的一个有限序列。线性表的逻辑结构是线性结构；线性表的存储结构可以有多种，最常用的两种是：顺序存储结构和链接存储结构。,3,线性表的抽象数据类型,抽象数据类型(ADT:abstractdatastructure)是一组数据以及定义在其上一组操作的集合.线性表的抽象数据类型主要包含两个方面：即:数据集合和该数据集合上操作的集合。,4,线性表的数据集合,线性表的数据元素集合可以表示为序列a0，a1，ai，ai+1an-1,每个数据元素可以是任意类型的。,在Java中，可以用类定义数据元素的数据类型。,5,线性表的操作集合,线性表的操作集合用来说明线性表所需要实现的功能，其基本操作大致如下：添加数据元素：在线性表的末尾添加一个数据元素。插入数据元素：在线性表第i个元素前插入一个数据元素。删除数据元素：删除线性表中第i个数据元素。获取数据元素：获取线性表中第i个数据元素。遍历线性表：从第一个元素开始，逐个访问线性表中的每个数据元素。获取当前线性表中的元素个数。求当前线性表中的元素个数。判断线性表是否为空。判断当前线性表中是否还有元素。,在Java中，可以用接口或抽象类来定义线性表的操作集合。,6,顺序表,使用顺序结构存储数据的线性表称为顺序表.,7,顺序表的设计与实现步骤,在确定了数据的存储结构以后,按下面步骤设计顺序表.数据元素定义-类数据操作定义-抽象类或接口实现顺序表-一个实现数据操作的类,8,使用顺序表,项目实践：例题2-1,用顺序表实现学生成绩信息管理程序.程序运行主界面见上图.该程序文件名为ArrStudent.java,包含下面3个类1个接口.StudScore类,定义数据元素(学生)StudOperation接口,定义数据操作ArrStudent类,顺序表ArrStudentUser类,完成学生成绩管理程序,9,修改完善例题2-1的学生成绩管理程序。修改接口StudOPeration，为程序添加操作如下：获取学生记录个数根据学生姓名查询学生信息根据学生姓名删除学生的信息在指定位置处插入学生的信息修改顺序表类ArrStudent，实现上述操作。修改类ArrStudentUser，完成上述功能的使用。,实战演练,10,Java类库中的顺序表,Java类库中的java.util.ArrayList类实现了顺序表的功能,其中常用的构造器和方法如下:publicArraylist(intinitialcapacity)/创建指定容量的顺序表publicbooleanadd(Objectobj)/在表尾添加一个元素publicbooleanremove(Objectobj)/删除表尾元素publicObjectremove(intindex)/删除指定位置的元素publicObjectget(intindex)/获取指定位置的元素publicintindexOf(Objectobj)/获取某个元素的位置,11,实战演练,使用java.util.ArrayList完成学生成绩管理程序.,12,使用java类库中顺序表java.util.ArrayList设计程序的步骤,导入顺序表类java.util.ArrayList定义数据元素使用顺序表,13,顺序表的效率分析,顺序表支持随机读取，顺序表读取数据元素操作的时间复杂度为O(1)。在顺序表中插入和删除一个数据元素的时间复杂度为O(n)。顺序表的主要优点是支持随机读