文档介绍：第2章线性表
1. 了解线性结构的特点。
2. 掌握顺序表的定义、查找、插入和删除。
3. 掌握链表的定义、查找、插入和删除。
4. 能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合。
教学目标
第2章线性表
2
线性表的定义和特点
线性表的类型定义
线性表的顺序表示和实现
线性表的链式表示和实现
线性表的应用
教学内容
第2章线性表
3
(a1, a2, … ai-1,ai, ai+1 ,…, an)
线性表的定义:由n(n≥0)个数据特征相同的元素构成的有限序列。
ai的直接前趋
ai的直接后继
4
线性表的定义和特点
第一个元素
最后一个元素
(a1, a2, … ai-1,ai, ai+1 ,…, an)
线性表的定义:由n(n≥0)个数据特征相同的元素构成的有限序列。
n=0时称为
下标,是数据元素的序号,表示元素在线性表中的位置
n为数据元素总个数,即线性表表长
空表
5
线性表的定义和特点
非空线性表或线性结构的特点
存在唯一的一个被称为“第一个”的数据元素;
存在唯一的一个被称为“最后一个”的数据元素;
除第一个元素之外,结构中的每个数据元素均只有一个直接前驱;
除最后一个元素之外,结构中的每个数据元素均只有一个直接后继。
6
线性表的定义和特点
例1 分析26个英文字母组成的英文表
( A, B, C, D, ……, Z)
根据线性表的定义和特点分析:
1. 根据定义:数据特征相同:数据元素都是字符并且都是字母;
2. 根据特点: 数据元素间关系是线性结构
7
线性表的定义和特点
学号
姓名
性别
年龄
班级
041810205
于春梅
女
18
04级计算机1班
041810260
何仕鹏
男
20
04级计算机2班
041810284
王爽
女
19
04级计算机3班
041810360
王亚武
男
18
04级计算机4班
:
:
:
:
:
例2 分析学生情况登记表
8
线性表的定义和特点
根据线性表的定义和特点分析:
1. 根据定义数据特征相同:数据元素都是记录;
2. 根据特点: 数据元素间关系是线性结构。
抽象数据类型(ADTs: Abstract Data Types)
更高层次的数据抽象
由用户定义,用以表示应用问题的数据模型
由基本的数据类型组成, 并包括一组相关的操作
9
线性表的类型定义
抽象数据类型(ADTs: Abstract Data Types)
定义部分: 线性表的类型定义
表示部分
实现部分
10
线性表的类型定义
线性表的顺序表示和实现
线性表的链式表示和实现