数据结构cha2-1解读.pptx

第2章 线性表 1. 了解线性结构的特点。 2. 掌握顺序表的定义、查找、插入和删除。 3. 掌握链表的定义、查找、插入和删除。 4. 能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合。 教学目标 第2章　线性表 2 2.1 线性表的定义和特点 2.3 线性表的类型定义 2.4 线性表的顺序表示和实现 2.5 线性表的链式表示和实现 2.6 线性表的应用 教学内容 第2章　线性表 3 （a1, a2, … ai-1，ai, ai＋1 ，…, an） 线性表的定义：由n(n≥0)个数据特征相同的元素构成的有限序列。 ai的直接前趋 ai的直接后继 4 2.1 线性表的定义和特点 第一个元素 最后一个元素 （a1, a2, … ai-1，ai, ai＋1 ，…, an） 线性表的定义：由n(n≥0)个数据特征相同的元素构成的有限序列。 n=0时称为 下标，是数据元素的序号，表示元素在线性表中的位置 n为数据元素总个数，即线性表表长 空表 5 2.1 线性表的定义和特点 非空线性表或线性结构的特点 存在唯一的一个被称为“第一个”的数据元素； 存在唯一的一个被称为“最后一个”的数据元素； 除第一个元素之外，结构中的每个数据元素均只有一个直接前驱； 除最后一个元素之外，结构中的每个数据元素均只有一个直接后继。 6 2.1 线性表的定义和特点 例1 分析26个英文字母组成的英文表 （ A, B, C, D, …… , Z） 根据线性表的定义和特点分析： 1. 根据定义：数据特征相同：数据元素都是字符并且都是字母; 2. 根据特点： 数据元素间关系是线性结构 7 2.1 线性表的定义和特点 学号 姓名 性别 年龄 班级 041810205 于春梅 女 18 04级计算机1班 041810260 何仕鹏 男 20 04级计算机2班 041810284 王 爽 女 19 04级计算机3班 041810360 王亚武 男 18 04级计算机4班 ： ： ： ： ： 例2 分析学生情况登记表 8 2.1 线性表的定义和特点 根据线性表的定义和特点分析： 1. 根据定义数据特征相同：数据元素都是记录; 2. 根据特点： 数据元素间关系是线性结构。 抽象数据类型 (ADTs: Abstract Data Types) 更高层次的数据抽象 由用户定义，用以表示应用问题的数据模型 由基本的数据类型组成, 并包括一组相关的操作 9 2.3 线性表的类型定义 抽象数据类型 (ADTs: Abstract Data Types) 定义部分：2.3 线性表的类型定义 表示部分 实现部分 10 2.3 线性表的类型定义 2.4 线性表的顺序表示和实现 2.5 线性表的链式表示和实现 抽象数据类型定义 定义可以用以下的三元组来表示： ADT =（D，R，P） 数据对象 D上的关系集 D上的操作集 11 2.3 线性表的类型定义 ADT抽象数据类型名{ 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 } ADT抽象数据类型名 抽象数据类型定义 ADT常用定义格式 12 2.3 线性表的类型定义 ADT List { 数据对象：D ={ ai|ai∈ElemSet,i=1,2,… …,n,n≥0 } 数据关系：R ={ai-1 ,ai|ai-1 ,ai∈ D,i=2,… …,n} 基本操作： 13 2.3 线性表的类型定义 抽象数据类型定义 2.3 线性表的类型定义 1. 初始化线性表L InitList(L) 操作结果：构造一个空的线性表L 。 2. 销毁线性表L DestoryList(L) 初始条件：线性表L已存在。 操作结果：销毁线性表L。 3. 清空线性表L ClearList(L) 初始条件：线性表L已存在。 操作结果：将L重置为空表。 4. 求线性表L的长度 ListLength(L) 初始条件：线性表L已存在。 操作结果：返回L中数据元素个数。 基本操作： 14 5. 判断线性表L是否为空 IsEmpty(L) 初始条件：线性表L已存在。 操作结果：若L 为空表，则返回TRUE，否则返回 FALSE。 6. 获取线性表L中的某个数据元素内容 GetElem(L,i,e) 初始条件：线性表L已存在，1≤i≤ListLength(L) 操作结果：用e返回L中第i个数据元素的值。 7. 检索值