Chapter 2
Chapter 2
线性表
线性表
2.1 线性表的定义及基本运算
2.2 线性表的顺序表示和实现
2.3 线性表的链式表示和实现
2.4 应用实例
本章重点:
1. 线性表的逻辑结构定义、抽象数据类型定义。
2. 线性表的两种存储结构的不同特点及其适用场合。
3. 在线性表的两种存储结构（顺序和链式）上实现基本操作
的算法。尤其是链式存储结构中，要注意链表中的头结点、
头指针和首元结点（第一个元素结点）的区别及循环链表、
双向链表的特点等。
本章难点:
1. 对两类存储结构的描述方法的理解。
2. 在各种链表结构中线性表基本操作的实现算法，能在实际
应用中选用适当的链表结构。
2.1
2.1
线性表的定义及基本运算
线性表的定义及基本运算
一、什么是线性表(Linear List)？
例1. （0, 1, 2, 3, …, 9)
例2. (A, B, C, …, Z)
例3. 学生操行等级表
姓名 学号 性别 年龄
操行等级
张三
李四
王五
┇
01101
01102
01103
女
男
男
┇┇┇ ┇
19
20
20
优
良
优
◆ 定义
一个线性表是n(n≥0) 个数据元素a
0
,a
1
,…,a
n-1
的有限序列。
除第一个和最后一个元素外，表中每个元素都有且仅有一个
直接前趋和一个直接后继。
n为线性表的长度。
n＝0，为空表；
n＞0，非空表，可表示为：（a
0
,a
1
,…,a
n-1
）
其中，a
i
(0≤i≤n-1)是属于某个数据对象的元素。
◆ 特性
（1）所有数据元素的性质相同；
（2）数据元素在表中的位置只取决于它们的序号，元素之间
的相对位置是线性的。
二、线性表的运算
◆ 求表长
◆ 存取
◆ 插入：在线性表的指定位置上，插入一个新的数据元素。
◆ 删除：删除线性表中指定位置上的元素。
◆ 归并：将二个或二个以上的线性表合并为一个线性表。
◆ 分解：将一个线性表分拆成若干个线性表。
◆ 复制
◆ 查找
◆ 排序
