第 7章 数据结构
? 数据结构是计算机软件和计算机应用专业的
核心课程之一，对于学习计算机专业的其他
课程，如操作系统、编译原理、数据库管理
系统、软件工程、人工智能等都是十分有益
的。数据结构主要研究数据表示与存储的方
法、抽象的逻辑结构及其上定义的各种基本
操作。数据的逻辑结构常常采用数学描述的
抽象符号和有关的理论。如使用串、表、数
组、图等结构和理论来表示数据在存储时的
逻辑结构，研究这些结构上定义的各种操作 。
本章内容
? 7.1 数据结构的概念
? 7.2 几种典型的数据结构
? 7.3 查找
? 7.4 排序
7.1 数据结构的概念
? 在系统地学习数据结构知识之前, 先对
一些与数据结构相关的基本概念和术语
赋予确切的含义 。
? 数据 （ Data） 是信息的载体, 它能够被
计算机识别, 存储和加工处理 。 它是计
算机程序加工的原料, 应用程序处理各
种各样的数据 。
? 计算机科学中, 所谓数据就是计算机
加工处理的对象, 它可以是数值数据,
也可以是非数值数据 。 数值数据是指
整数, 实数或复数等, 主要用于工程
计算, 科学计算和商务处理等；非数
值数据包括字符, 文字, 图形, 图像,
语音等 。
? 数据元素（ Data Element）是数据的基
本单位。在不同的条件下，数据元素
又可称为元素、结点、顶点、记录等。
例如，学生信息检索系统中学生信息
表中的一个记录、八皇后问题中状态
树的一个状态、教学计划编排问题中
的一个顶点等，都被称为一个数据元
素。
? 一个数据元素可由若干个数据项（ Data
Item）组成，例如，学籍管理系统中学
生信息表的每一个数据元素就是一个学
生记录。它包括学生的学号、姓名、性
别、籍贯、出生年月、成绩等数据项。
这些数据项可以分为两种：一种叫做初
等项，如学生的性别、籍贯等，这些数
据项是在数据处理时不能再分割的最小
单位；
? 数据对象 （ Data Object ） 或数据元素类
（ Data Element Class） 是具有相同性质的数
据元素的集合 。 在某个具体问题中, 数据元
素都具有相同的性质 （ 元素值不一定相等 ）,
属于同一数据对象 （ 数据元素类 ）, 数据元
素是数据元素类的一个实例 。
在交通咨询系统的交通网中, 所有的顶点是
一个数据元素类, 顶点 A和顶点 B各自代表一
个城市, 是该数据元素类中的两个实例, 其
数据元素的值分别为 A和 B。
? 数据结构（ Data Structure，简称 DS）是指
互相之间存在着一种或多种关系的数据元
素的集合。在任何问题中，数据元素之间
都不会是孤立的，在它们之间都存在着这
样或那样的关系，这种数据元素之间的关
系称为结构。
? 数据结构是信息的一种组织方式，其目的
是为了提高算法的效率，它通常与一组算
法的集合相对应，通过这组算法集合可以
对数据结构中的数据进行某种操作。
根据数据元素间关系的不同特性, 通常有下列四类基本
的结构,
⑴ 集合结构 。 在集合结构中, 数据元素间的关系是, 属于
同一个集合, 。 集合是元素关系极为松散的一种结构 。
⑵ 线性结构 。 该结构的数据元素之间存在着一对一的关系 。
⑶ 树型结构 。 该结构的数据元素之间存在着一对多的关系 。
⑷ 图型结构 。 该结构的数据元素之间存在着多对多的关系,
图形结构也称作网状结构 。
（ a） 集合结构 （ b） 线性结构
（ c） 树型结构 （ d） 图形结构
图 7.1 四类基本结构的示意图
? 表和树是最常用的两种高效数据结构，许
多高效的算法可以用这两种数据结构来设
计实现。表是线性结构（全序关系），树
(偏序或层次关系 )和图（局部有序
(weak/local orders)）是非线性结构。
? 一个数据结构有两个要素 。 一个是数
据元素的集合, 另一个是关系的集合 。
因此, 在形式上, 数据结构通常可以
采用一个二元组来表示 。
? 数据结构的形式定义为：数据结构是
一个二元组 Data_Structure ＝ （ D,R）
其中, D是数据元素的有限集, R是 D
上关系的有限集 。
? 数据结构包括数据的逻辑结构和数据的物
理结构两部分。数据的逻辑结构是从具体
问题抽象出来的数学模型，它与数据的存
储无关。我们研究数据结构的目的是为了
在计算机中实现对它的操作，为此还需要
研究如何在计算机中表示一个数据结构。
数据结构在计算机中的标识（又称映像）
称为数据的物理结构，或称存储结构。
? 在计算机中信息表示的最小单位是二
进制的一位, 我们用若干位组合起来
形成的一个位串表示数据元素, 通常
这个位串称为元素 （ Element） 或结点
（ Node） 。 当数据元素由若干数据项
组成时, 位串中对应于各个数据项的
子位串称为数据域 （ Data Field） 。
? 元素或结点可看成数据元素在计算机中的映象。
即数据结构 DS 的物理结构 P 对应于从 DS 的
数据元素到存储区 M（维护着逻辑结构 S）的
一个映射,P,(DS) --> M。
? 数据结构主要研究以下三个方面的内容：数据
的逻辑结构；数据的物理存储结构；对数据的
操作（或算法）。通常，算法的设计取决于数
据的逻辑结构，算法的实现取决于数据的物理
存储结构。
? 数据的存储结构可采用顺序存储或链式
存储的方法 。
? 顺序存储方法是把逻辑上相邻的元素存
储在物理位置相邻的存储单元中, 由此
得到的存储表示称为顺序存储结构 。 顺
序存储结构是一种最基本的存储表示方
法, 通常借助于程序设计语言中的数组
来实现 。
? 链式存储方法对逻辑上相邻的元素不要求其
物理位置相邻, 元素间的逻辑关系通过附设
的指针字段来表示, 由此得到的存储表示称
为链式存储结构, 链式存储结构通常借助于
程序设计语言中的指针类型来实现 。
? 除了通常采用的顺序存储方法和链式存储方
法外, 有时为了查找的方便还采用索引存储
方法和散列存储方法 。
7.2 几种典型的数据结构
7.2.1 线性表
线性表是一种线性结构 。 线性结构的特点是
数据元素之间是一种线性关系, 数据元素
,一个接一个的排列, 。 在一个线性表中数
据元素的类型是相同的, 或者说线性表是由
同一类型的数据元素构成的线性结构 。 在实
际问题中线性表的例子是很多的, 如前面提
到的学生情况信息表就是一个线性表, 表中
每一个记录对应一名学生 。
? 线性表是具有相同数据类型的 n(n>=0)个数据
元素的有限序列，通常记为,
(a1,a2,… ai -1,ai,ai+1,…an),其中 n为
表长,n＝ 0 时称为空表。
表中相邻元素之间存在着顺序关系。将 ai-1
称为 ai 的直接前趋,ai+1 称为 ai 的直接后继。
就是说：对于 ai，当 i=2,...,n 时，有且仅
有一个直接前趋 ai-1.，当 i=1,2,...,n-1 时，
有且仅有一个直接后继 ai+1，而 a1 是表中第
一个元素，它没有前趋,an 是最后一个元素
无后继。
? 需要说明的是,ai为序号为 i 的数据元素
（ i=1,2,…,n）, 通常我们将它的数据类型
抽象为 datatype,datatype根据具体问题而
定, 如在学生情况信息表中, 它是用户自定
义的学生类型 。
? 线性表的存储方式共有两种：顺序存
储和链式存储。顺序存储是指在内存
中用地址连续的一块存储空间顺序存
放线性表的各元素，用这种存储形式
存储的线性表称其为顺序表。因为内
存中的地址空间是线性的，因此，用
物理上的相邻实现数据元素之间的逻
辑相邻关系是既简单，又自然的。
0 1 … i-1 i … n-1
a1 a2 … ai-1 ai ai+1 … an data
…maxaize1 -1,
…
last
? 这就是说只要知道顺序表首地址和每个数据
元素所占地址单元的个数就可求出第 i个数据
元素的地址来，这也是顺序表具有按数据元
素的序号随机存取的特点。
? 从表的定义不难看出表具有以下数学性质：
除了表头和表尾外，表中的每一个元素有且
仅有唯一的前驱和唯一的后继，表头有且只
有一个后继，表尾有且只有一个前驱。
7.2.2 堆栈
1,栈的定义
栈是一种特殊的线性表，这种表只在表头进
行插入和删除操作。因此，表头对于栈来说
具有特殊的意义，称为栈顶。相应地，表尾
称为栈底。不含任何元素的栈称为空栈。
2,栈的数学性质
假设一个栈 S中的元素为 an,an-1,..,a1，则
称 a1为栈底元素,an为栈顶元 素。栈中的
元素按 a,a2,..,an-1,an的次序进栈。在任何
时候，出栈的元素都是栈顶元素。换句话
说，栈的修改是按后进先出的原则进行的，
如图 1所示。因此，栈又称为后进先出
(Last In First Out)表，简称为 LIFO表。
所以，只要问题满足 LIFO原则，就可以
使用栈。
a1
a2
an-1 an …
栈底
栈顶
入栈 出栈
7.2.3 队列
1．队列的定义
队列也是一种特殊的线性表。对这种线性表，删
除操作只在表头 (称为队头 )进行，插入操作只在
表尾 (称为队尾 )进行。队列的修改是按先进先出
的原则进行的，所以队列又称为先进先出 (First
In First Out)表，简称 FIFO表。
2．队列的数学性质
假设队列为 a1,a2,..,an，那么 a1就是队头元
素,an为队尾元素。队列中的元素是按
a1,a2,..,an的顺序进入的，退出队列也只能
按照这个次序依次退出。也就是说，只有在 a1
离开队列之后,a2才能退出队列，只有在
a1,a2,..,an-1都离开队列之后,an才能退出
队列。
a1 a2 a3 … an 出队列 入队列
队头 队尾
7.2.4 树
? 线性结构的特点是逻辑结构简单，易于
进行查找、插入和删除等操作，其主要
用于对客观世界中具有单一的前驱和后
继的数据关系进行描述，而现实中的许
多事物的关系并非这样简单，如人类社
会的族谱、各种社会组织机构以及城市
交通、通讯等，这些事物中的联系都是
非线性的，采用非线性结构进行描绘会
更明确和便利。
? 所谓非线性结构是指在该结构中至少存在
一个数据元素，有两个或两个以上的直接
前驱（或直接后继）元素。树型结构和图
型结构就是其中十分重要的非线性结构，
可以用来描述客观世界中广泛存在的层次
结构和网状结构的关系，如前面提到的族
谱、城市交通等。
? 树（ Tree）是 n（ n≥0 ）个有限数据元素的集
合。当 n＝ 0时，称这棵树为空树。在一棵非空
树 T中,,
（ 1）有一个特殊的数据元素称为树的根结点，
根结点没有前驱结点。
（ 2）若 n>1，除根结点之外的其余数据元素被
分成 m（ m>0）个互不相交的集合 T1,T2,…,
Tm，其中每一个集合 Ti（ 1≤i≤m ）本身又是
一棵树。树 T1,T2,…, Tm称为这个根结点的
子树。
? 在树的定义中用了递归概念, 即用树来定义
树 。
? 树的定义还可形式化的描述为二元组的形式,
T＝ （ D,R） 其中 D为树 T中结点的集合, R
为树中结点之间关系的集合
? 树是很好的 DS—— 它有非常简单而高效的线
性化规则，因此可以利用树设计出许多非常
高效的算法。树的实现和使用都很简单，但
可以解决大量特殊的复杂问题，因此树是实
际编程中最重要和最有用的一种数据结构。
树的结构本质上有递归的性质 —— 每一个叶
节点可以被一棵子树所替代，反之亦然。实
际上，每一种递归的结构都可以被转化为
（或等价于）树形结构。
? 树具有下面两个特点,
（ 1） 树的根结点没有前驱结点, 除根结点之
外的所有结点有且只有一个前驱结点 。
（ 2） 树中所有结点可以有零个或多个后继结
点 。
G
A
D
B
C
F
E
F
A
H
E
D
B
C
E
D
C
B
A
E
F G F
G
D
C
B
A
(a) 一棵树结构 (b)一个非树结构 (c)一个非树结构 (d)一个非树结构
? 二叉树 （ Binary Tree） 是个有限元素的
集合, 该集合或者为空, 或者由一个称
为根 (root)的元素及两个不相交的, 被
分别称为左子树和右子树的二叉树组成 。
当集合为空时, 称该二叉树为空二叉树 。
在二叉树中, 一个元素也称作一个结点 。
? 二叉树是有序的，即若将其左、右子树颠
倒，就成为另一棵不同的二叉树。即使树
中结点只有一棵子树，也要区分它是左子
树还是右子树。因此二叉树具有五种基本
形态,
Φ
左子树 右子树 左子树 右子树
(a) (b) (c) (d) (e)
7.2.5 图
? 图状结构是一种比树形结构更复杂的非线
性结构。在树状结构中，结点间具有分支
层次关系，每一层上的结点只能和上一层
中的至多一个结点相关，但可能和下一层
的多个结点相关。而在图状结构中，任意
两个结点之间都可能相关，即结点之间的
邻接关系可以是任意的。因此，图状结构
被用于描述各种复杂的数据对象，在自然
科学、社会科学和人文科学等许多领域有
着非常广泛的应用。
1．图的定义
图 (Graph)是由非空的顶点集合和描述顶点
之间关系的边（或者弧）的集合组成，其
形式化定义为,
G＝（ V,E）
V＝ {vi| vi∈ dataobject}
E＝ {( vi,vj)| vi,vj ∈ V ∧ P(vi,vj)}
V1 V2
V3
V4 V5 V4 V3
V2 V1
2．图的相关术语
（ 1）无向图。在一个图中，如果任意两个
顶点构成的偶对（ vi,vj） ∈ E是无序的，即
顶点之间的连线是没有方向的，则称该图为
无向图。
（ 2）有向图。在一个图中，如果任意两个
顶点构成的偶对（ vi,vj） ∈ E是有序的，即
顶点之间的连线是有方向的，则称该图为有
向图。
（ 3）顶点、边、弧、弧头、弧尾。图中，数据元
素 vi称为顶点 (vertex )； P(vi,vj)表示在顶点
vi和顶点 vj之间有一条直接连线。如果是在无向
图中，则称这条连线为边；如果是在有向图中，
一般称这条连线为弧。边用顶点的无序偶对（ vi,
vj）来表示，称顶点 vi和顶点 vj互为邻接点，边
（ vi,vj）依附于顶点 vi与顶点 vj；
（ 4） 无向完全图 。 在一个无向图中, 如
果任意两顶点都有一条直接边相连接,
则称该图为无向完全图 。 可以证明, 在
一个含有 n个顶点的无向完全图中, 有
n(n-1)/2条边 。
（ 5） 有向完全图 。 在一个有向图中, 如果
任意两顶点之间都有方向互为相反的两条
弧相连接, 则称该图为有向完全图 。 在一
个含有 n个顶点的有向完全图中, 有 n(n-1)
条边 。
（ 6） 稠密图, 稀疏图 。 若一个图接近完全
图, 称为稠密图；称边数很少的图为稀疏
图 。
（ 7） 顶点的度, 入度, 出度 。 顶点的度
（ degree） 是指依附于某顶点 v的边数, 通
常记为 TD (v)。 在有向图中, 要区别顶点
的入度与出度的概念 。 顶点 v的入度是指以
顶点为终点的弧的数目 。 记为 ID (v)；顶
点 v出度是指以顶点 v为始点的弧的数目,
记为 OD (v)。 有 TD (v)=ID (v)＋ OD (v)。
? 可以证明，对于具有 n个顶点,e条边的
图，顶点 vi的度 TD (vi)与顶点的个数以
及边的数目满足关系：所有顶点度数之
和等于边数的两倍（握手定理）。即,
2e= ∑
n
i=1
TD(Vi)
（ 8）边的权、网图。与边有关的数据信息称为
权（ weight）。在实际应用中，权值可以有某
种含义。比如，在一个反映城市交通线路的图
中，边上的权值可以表示该条线路的长度或者
等级；对于一个电子线路图，边上的权值可以
表示两个端点之间的电阻、电流或电压值；对
于反映工程进度的图而言，边上的权值可以表
示从前一个工程到后一个工程所需要的时间等
等。边上带权的图称为网图或网络
（ network）。
V1
V3
V4 V5
V2
7.3 查找
? 计算机, 计算机网络使信息查询变得更快
捷, 方便, 准确 。 但要从计算机, 计算机
网络中查找特定的信息, 就需要在计算机
中存储包含该特定信息的表 。 如要从计算
机中查找英文单词的中文解释, 就需要存
储类似英汉字典这样的信息表, 以及对该
表进行的查找 （ Searching） 操作 。
学号 姓名 性
别
|
|
|
20010983
20010984
20010985
|
|
|
|
|
|
张三
李四
王五
|
|
|
|
|
|
男
男
女
|
|
|
来 源 总
分
录取
专业
|
|
|
包头一中
保定三中
易县中学
|
|
|
|
|
|
593
601
598
|
|
|
|
|
|
计算机
计算机
计算机
|
|
|
年 月 日
|
|
|
1982
1982
1983
|
|
|
|
|
|
11
09
01
|
|
|
|
|
|
05
12
25
|
|
|
出生年月
1,数据项 (也称项或字段 )
项是具有独立含义的标识单位，是数据不可分割
的最小单位。如表中“学号”、“姓名”,“年”
等。项有名和值之分，项名是一个项的标识，用
变量定义，而项值是它的一个可能取值，表中
,20010983”是项“学号”的一个取值。项具有
一定的类型，依项的取值类型而定。
2,组合项
由若干项, 组合项构成, 表中, 出生日期,
就是组合项, 它由, 年,,, 月,,, 日,
三项组成 。
3,数据元素 （ 记录 ）
数据元素是由若干项, 组合项构成的数据
单位, 是在某一问题中作为整体进行考虑
和处理的基本单位 。
4.关键字
关键字 (Key)是数据元素 （ 记录 ） 中某个
项或组合项的值, 用它可以标识一个数据
元素 （ 记录 ） 。 能唯一确定一个数据元素
（ 记录 ） 的关键字, 称为主关键字
(Primary Key)；
5.查找表
是由具有同一类型 （ 属性 ） 的数据元
素 （ 记录 ） 组成的集合 。 分为静态查
找表 (Static Search Table)和动态
查找表 (Dynamic Search Table)两类 。
6.查找
按给定的某个值 A,在查找表中查找关键字
为给定值 A的数据元素 （ 记录 ） 。
7.3.2 查找的方法
1 顺序查找
又称线性查找, 是最基本的查找方法之
一 。 其查找方法为：从表的一端开始,
向另一端逐个按给定值 kx与关键码进行
比较, 若找到, 查找成功, 并给出数据
元素在表中的位置；若整个表检测完,
仍未找到与 kx相同的关键字, 则查找失
败, 给出失败信息 。
2 折半查找
折半查找的思想为：在有序表 （ 表中的元素
按递增或递减的顺序排列 ） 中, 取中间元素
作为比较对象, 若给定值与中间元素的关键
字相等, 则查找成功；若给定值小于中间元
素的关键字, 则在中间元素的左半区继续查
找；若给定值大于中间元素的关键字, 则在
中间元素的右半区继续查找 。 不断重复上述
查找过程, 直到查找成功, 或所查找的区域
无数据元素, 查找失败 。
3 分块查找
又称索引顺序查找，是对顺序查找的一种
改进。分块查找要求将查找表分成若干个
子表，并对子表建立索引表，查找表的每
一个子表由索引表中的索引项确定。索引
项包括两个字段：关键字字段 (存放对应子
表中的最大关键字值 ) ；
7.4 排序
? 排序 (Sorting)是计算机程序设计中的一种重要操
作，其功能是对一个数据元素集合或序列重新排
列成一个按数据元素某个项值有序的序列。作为
排序依据的数据项称为“排序码”，也即数据元
素的关键字。为了便于查找，通常希望计算机中
的数据表是按关键字有序的。如有序表的折半查
找，查找效率较高。还有，二叉排序树,B-树和
B+树的构造过程就是一个排序过程。若关键字
是主关键字，则对于任意待排序序列，经排序后
得到的结果是唯一的；
? 若关键字是次关键字，排序结果可能不唯一，
这是因为具有相同关键字的数据元素，这些
元素在排序结果中，它们之间的的位置关系
与排序前不能保持一致。
? 若对任意的数据元素序列，使用某个排序方
法，对它按关键字进行排序：若相同关键字
元素间的位置关系，排序前与排序后保持一
致，称此排序方法是稳定的；而不能保持一
致的排序方法则称为不稳定的。
7.4.1 排序分类
? 排序分为两类：内排序和外排序 。
? 内排序：指待排序列完全存放在内存中
所进行的排序过程, 适合不太大的元素
序列 。
? 外排序：指待排序列的数量很大, 以致
内存一次不能容纳全部记录, 在排序过
程中还需访问外存储器 。
? 内排序的方法很多, 下面我们介绍一些
常用的内排序的方法 。
1 直接插入排序
直接插入排序 （ Straight Insertion Sort） 是一
种最简单的排序方法 。 它的基本操作是将
一个记录插入到已排好序的有序表中, 从
而得到一个新的, 记录数增 1的有序表 。
2 折半插入排序
直接插入排序的基本操作是向有序表中插入
一个记录, 插入位置的确定通过对有序表
中记录按关键字逐个比较得到的 。
3 表插入排序
直接插入排序, 折半插入排序均要大量移动
记录, 时间开销大 。 若要不移动记录完成排
序, 需要改变存储结构, 进行表插入排序 。
所谓表插入排序, 就是通过链接指针, 按关
键字的大小, 实现从小到大的链接过程, 为
此需增设一个指针项 。 操作方法与直接插入
排序类似, 所不同的是直接插入排序要移动
记录, 而表插入排序是修改链接指针 。
? 数据结构是计算机软件和计算机应用专业的
核心课程之一，对于学习计算机专业的其他
课程，如操作系统、编译原理、数据库管理
系统、软件工程、人工智能等都是十分有益
的。数据结构主要研究数据表示与存储的方
法、抽象的逻辑结构及其上定义的各种基本
操作。数据的逻辑结构常常采用数学描述的
抽象符号和有关的理论。如使用串、表、数
组、图等结构和理论来表示数据在存储时的
逻辑结构，研究这些结构上定义的各种操作 。
本章内容
? 7.1 数据结构的概念
? 7.2 几种典型的数据结构
? 7.3 查找
? 7.4 排序
7.1 数据结构的概念
? 在系统地学习数据结构知识之前, 先对
一些与数据结构相关的基本概念和术语
赋予确切的含义 。
? 数据 （ Data） 是信息的载体, 它能够被
计算机识别, 存储和加工处理 。 它是计
算机程序加工的原料, 应用程序处理各
种各样的数据 。
? 计算机科学中, 所谓数据就是计算机
加工处理的对象, 它可以是数值数据,
也可以是非数值数据 。 数值数据是指
整数, 实数或复数等, 主要用于工程
计算, 科学计算和商务处理等；非数
值数据包括字符, 文字, 图形, 图像,
语音等 。
? 数据元素（ Data Element）是数据的基
本单位。在不同的条件下，数据元素
又可称为元素、结点、顶点、记录等。
例如，学生信息检索系统中学生信息
表中的一个记录、八皇后问题中状态
树的一个状态、教学计划编排问题中
的一个顶点等，都被称为一个数据元
素。
? 一个数据元素可由若干个数据项（ Data
Item）组成，例如，学籍管理系统中学
生信息表的每一个数据元素就是一个学
生记录。它包括学生的学号、姓名、性
别、籍贯、出生年月、成绩等数据项。
这些数据项可以分为两种：一种叫做初
等项，如学生的性别、籍贯等，这些数
据项是在数据处理时不能再分割的最小
单位；
? 数据对象 （ Data Object ） 或数据元素类
（ Data Element Class） 是具有相同性质的数
据元素的集合 。 在某个具体问题中, 数据元
素都具有相同的性质 （ 元素值不一定相等 ）,
属于同一数据对象 （ 数据元素类 ）, 数据元
素是数据元素类的一个实例 。
在交通咨询系统的交通网中, 所有的顶点是
一个数据元素类, 顶点 A和顶点 B各自代表一
个城市, 是该数据元素类中的两个实例, 其
数据元素的值分别为 A和 B。
? 数据结构（ Data Structure，简称 DS）是指
互相之间存在着一种或多种关系的数据元
素的集合。在任何问题中，数据元素之间
都不会是孤立的，在它们之间都存在着这
样或那样的关系，这种数据元素之间的关
系称为结构。
? 数据结构是信息的一种组织方式，其目的
是为了提高算法的效率，它通常与一组算
法的集合相对应，通过这组算法集合可以
对数据结构中的数据进行某种操作。
根据数据元素间关系的不同特性, 通常有下列四类基本
的结构,
⑴ 集合结构 。 在集合结构中, 数据元素间的关系是, 属于
同一个集合, 。 集合是元素关系极为松散的一种结构 。
⑵ 线性结构 。 该结构的数据元素之间存在着一对一的关系 。
⑶ 树型结构 。 该结构的数据元素之间存在着一对多的关系 。
⑷ 图型结构 。 该结构的数据元素之间存在着多对多的关系,
图形结构也称作网状结构 。
（ a） 集合结构 （ b） 线性结构
（ c） 树型结构 （ d） 图形结构
图 7.1 四类基本结构的示意图
? 表和树是最常用的两种高效数据结构，许
多高效的算法可以用这两种数据结构来设
计实现。表是线性结构（全序关系），树
(偏序或层次关系 )和图（局部有序
(weak/local orders)）是非线性结构。
? 一个数据结构有两个要素 。 一个是数
据元素的集合, 另一个是关系的集合 。
因此, 在形式上, 数据结构通常可以
采用一个二元组来表示 。
? 数据结构的形式定义为：数据结构是
一个二元组 Data_Structure ＝ （ D,R）
其中, D是数据元素的有限集, R是 D
上关系的有限集 。
? 数据结构包括数据的逻辑结构和数据的物
理结构两部分。数据的逻辑结构是从具体
问题抽象出来的数学模型，它与数据的存
储无关。我们研究数据结构的目的是为了
在计算机中实现对它的操作，为此还需要
研究如何在计算机中表示一个数据结构。
数据结构在计算机中的标识（又称映像）
称为数据的物理结构，或称存储结构。
? 在计算机中信息表示的最小单位是二
进制的一位, 我们用若干位组合起来
形成的一个位串表示数据元素, 通常
这个位串称为元素 （ Element） 或结点
（ Node） 。 当数据元素由若干数据项
组成时, 位串中对应于各个数据项的
子位串称为数据域 （ Data Field） 。
? 元素或结点可看成数据元素在计算机中的映象。
即数据结构 DS 的物理结构 P 对应于从 DS 的
数据元素到存储区 M（维护着逻辑结构 S）的
一个映射,P,(DS) --> M。
? 数据结构主要研究以下三个方面的内容：数据
的逻辑结构；数据的物理存储结构；对数据的
操作（或算法）。通常，算法的设计取决于数
据的逻辑结构，算法的实现取决于数据的物理
存储结构。
? 数据的存储结构可采用顺序存储或链式
存储的方法 。
? 顺序存储方法是把逻辑上相邻的元素存
储在物理位置相邻的存储单元中, 由此
得到的存储表示称为顺序存储结构 。 顺
序存储结构是一种最基本的存储表示方
法, 通常借助于程序设计语言中的数组
来实现 。
? 链式存储方法对逻辑上相邻的元素不要求其
物理位置相邻, 元素间的逻辑关系通过附设
的指针字段来表示, 由此得到的存储表示称
为链式存储结构, 链式存储结构通常借助于
程序设计语言中的指针类型来实现 。
? 除了通常采用的顺序存储方法和链式存储方
法外, 有时为了查找的方便还采用索引存储
方法和散列存储方法 。
7.2 几种典型的数据结构
7.2.1 线性表
线性表是一种线性结构 。 线性结构的特点是
数据元素之间是一种线性关系, 数据元素
,一个接一个的排列, 。 在一个线性表中数
据元素的类型是相同的, 或者说线性表是由
同一类型的数据元素构成的线性结构 。 在实
际问题中线性表的例子是很多的, 如前面提
到的学生情况信息表就是一个线性表, 表中
每一个记录对应一名学生 。
? 线性表是具有相同数据类型的 n(n>=0)个数据
元素的有限序列，通常记为,
(a1,a2,… ai -1,ai,ai+1,…an),其中 n为
表长,n＝ 0 时称为空表。
表中相邻元素之间存在着顺序关系。将 ai-1
称为 ai 的直接前趋,ai+1 称为 ai 的直接后继。
就是说：对于 ai，当 i=2,...,n 时，有且仅
有一个直接前趋 ai-1.，当 i=1,2,...,n-1 时，
有且仅有一个直接后继 ai+1，而 a1 是表中第
一个元素，它没有前趋,an 是最后一个元素
无后继。
? 需要说明的是,ai为序号为 i 的数据元素
（ i=1,2,…,n）, 通常我们将它的数据类型
抽象为 datatype,datatype根据具体问题而
定, 如在学生情况信息表中, 它是用户自定
义的学生类型 。
? 线性表的存储方式共有两种：顺序存
储和链式存储。顺序存储是指在内存
中用地址连续的一块存储空间顺序存
放线性表的各元素，用这种存储形式
存储的线性表称其为顺序表。因为内
存中的地址空间是线性的，因此，用
物理上的相邻实现数据元素之间的逻
辑相邻关系是既简单，又自然的。
0 1 … i-1 i … n-1
a1 a2 … ai-1 ai ai+1 … an data
…maxaize1 -1,
…
last
? 这就是说只要知道顺序表首地址和每个数据
元素所占地址单元的个数就可求出第 i个数据
元素的地址来，这也是顺序表具有按数据元
素的序号随机存取的特点。
? 从表的定义不难看出表具有以下数学性质：
除了表头和表尾外，表中的每一个元素有且
仅有唯一的前驱和唯一的后继，表头有且只
有一个后继，表尾有且只有一个前驱。
7.2.2 堆栈
1,栈的定义
栈是一种特殊的线性表，这种表只在表头进
行插入和删除操作。因此，表头对于栈来说
具有特殊的意义，称为栈顶。相应地，表尾
称为栈底。不含任何元素的栈称为空栈。
2,栈的数学性质
假设一个栈 S中的元素为 an,an-1,..,a1，则
称 a1为栈底元素,an为栈顶元 素。栈中的
元素按 a,a2,..,an-1,an的次序进栈。在任何
时候，出栈的元素都是栈顶元素。换句话
说，栈的修改是按后进先出的原则进行的，
如图 1所示。因此，栈又称为后进先出
(Last In First Out)表，简称为 LIFO表。
所以，只要问题满足 LIFO原则，就可以
使用栈。
a1
a2
an-1 an …
栈底
栈顶
入栈 出栈
7.2.3 队列
1．队列的定义
队列也是一种特殊的线性表。对这种线性表，删
除操作只在表头 (称为队头 )进行，插入操作只在
表尾 (称为队尾 )进行。队列的修改是按先进先出
的原则进行的，所以队列又称为先进先出 (First
In First Out)表，简称 FIFO表。
2．队列的数学性质
假设队列为 a1,a2,..,an，那么 a1就是队头元
素,an为队尾元素。队列中的元素是按
a1,a2,..,an的顺序进入的，退出队列也只能
按照这个次序依次退出。也就是说，只有在 a1
离开队列之后,a2才能退出队列，只有在
a1,a2,..,an-1都离开队列之后,an才能退出
队列。
a1 a2 a3 … an 出队列 入队列
队头 队尾
7.2.4 树
? 线性结构的特点是逻辑结构简单，易于
进行查找、插入和删除等操作，其主要
用于对客观世界中具有单一的前驱和后
继的数据关系进行描述，而现实中的许
多事物的关系并非这样简单，如人类社
会的族谱、各种社会组织机构以及城市
交通、通讯等，这些事物中的联系都是
非线性的，采用非线性结构进行描绘会
更明确和便利。
? 所谓非线性结构是指在该结构中至少存在
一个数据元素，有两个或两个以上的直接
前驱（或直接后继）元素。树型结构和图
型结构就是其中十分重要的非线性结构，
可以用来描述客观世界中广泛存在的层次
结构和网状结构的关系，如前面提到的族
谱、城市交通等。
? 树（ Tree）是 n（ n≥0 ）个有限数据元素的集
合。当 n＝ 0时，称这棵树为空树。在一棵非空
树 T中,,
（ 1）有一个特殊的数据元素称为树的根结点，
根结点没有前驱结点。
（ 2）若 n>1，除根结点之外的其余数据元素被
分成 m（ m>0）个互不相交的集合 T1,T2,…,
Tm，其中每一个集合 Ti（ 1≤i≤m ）本身又是
一棵树。树 T1,T2,…, Tm称为这个根结点的
子树。
? 在树的定义中用了递归概念, 即用树来定义
树 。
? 树的定义还可形式化的描述为二元组的形式,
T＝ （ D,R） 其中 D为树 T中结点的集合, R
为树中结点之间关系的集合
? 树是很好的 DS—— 它有非常简单而高效的线
性化规则，因此可以利用树设计出许多非常
高效的算法。树的实现和使用都很简单，但
可以解决大量特殊的复杂问题，因此树是实
际编程中最重要和最有用的一种数据结构。
树的结构本质上有递归的性质 —— 每一个叶
节点可以被一棵子树所替代，反之亦然。实
际上，每一种递归的结构都可以被转化为
（或等价于）树形结构。
? 树具有下面两个特点,
（ 1） 树的根结点没有前驱结点, 除根结点之
外的所有结点有且只有一个前驱结点 。
（ 2） 树中所有结点可以有零个或多个后继结
点 。
G
A
D
B
C
F
E
F
A
H
E
D
B
C
E
D
C
B
A
E
F G F
G
D
C
B
A
(a) 一棵树结构 (b)一个非树结构 (c)一个非树结构 (d)一个非树结构
? 二叉树 （ Binary Tree） 是个有限元素的
集合, 该集合或者为空, 或者由一个称
为根 (root)的元素及两个不相交的, 被
分别称为左子树和右子树的二叉树组成 。
当集合为空时, 称该二叉树为空二叉树 。
在二叉树中, 一个元素也称作一个结点 。
? 二叉树是有序的，即若将其左、右子树颠
倒，就成为另一棵不同的二叉树。即使树
中结点只有一棵子树，也要区分它是左子
树还是右子树。因此二叉树具有五种基本
形态,
Φ
左子树 右子树 左子树 右子树
(a) (b) (c) (d) (e)
7.2.5 图
? 图状结构是一种比树形结构更复杂的非线
性结构。在树状结构中，结点间具有分支
层次关系，每一层上的结点只能和上一层
中的至多一个结点相关，但可能和下一层
的多个结点相关。而在图状结构中，任意
两个结点之间都可能相关，即结点之间的
邻接关系可以是任意的。因此，图状结构
被用于描述各种复杂的数据对象，在自然
科学、社会科学和人文科学等许多领域有
着非常广泛的应用。
1．图的定义
图 (Graph)是由非空的顶点集合和描述顶点
之间关系的边（或者弧）的集合组成，其
形式化定义为,
G＝（ V,E）
V＝ {vi| vi∈ dataobject}
E＝ {( vi,vj)| vi,vj ∈ V ∧ P(vi,vj)}
V1 V2
V3
V4 V5 V4 V3
V2 V1
2．图的相关术语
（ 1）无向图。在一个图中，如果任意两个
顶点构成的偶对（ vi,vj） ∈ E是无序的，即
顶点之间的连线是没有方向的，则称该图为
无向图。
（ 2）有向图。在一个图中，如果任意两个
顶点构成的偶对（ vi,vj） ∈ E是有序的，即
顶点之间的连线是有方向的，则称该图为有
向图。
（ 3）顶点、边、弧、弧头、弧尾。图中，数据元
素 vi称为顶点 (vertex )； P(vi,vj)表示在顶点
vi和顶点 vj之间有一条直接连线。如果是在无向
图中，则称这条连线为边；如果是在有向图中，
一般称这条连线为弧。边用顶点的无序偶对（ vi,
vj）来表示，称顶点 vi和顶点 vj互为邻接点，边
（ vi,vj）依附于顶点 vi与顶点 vj；
（ 4） 无向完全图 。 在一个无向图中, 如
果任意两顶点都有一条直接边相连接,
则称该图为无向完全图 。 可以证明, 在
一个含有 n个顶点的无向完全图中, 有
n(n-1)/2条边 。
（ 5） 有向完全图 。 在一个有向图中, 如果
任意两顶点之间都有方向互为相反的两条
弧相连接, 则称该图为有向完全图 。 在一
个含有 n个顶点的有向完全图中, 有 n(n-1)
条边 。
（ 6） 稠密图, 稀疏图 。 若一个图接近完全
图, 称为稠密图；称边数很少的图为稀疏
图 。
（ 7） 顶点的度, 入度, 出度 。 顶点的度
（ degree） 是指依附于某顶点 v的边数, 通
常记为 TD (v)。 在有向图中, 要区别顶点
的入度与出度的概念 。 顶点 v的入度是指以
顶点为终点的弧的数目 。 记为 ID (v)；顶
点 v出度是指以顶点 v为始点的弧的数目,
记为 OD (v)。 有 TD (v)=ID (v)＋ OD (v)。
? 可以证明，对于具有 n个顶点,e条边的
图，顶点 vi的度 TD (vi)与顶点的个数以
及边的数目满足关系：所有顶点度数之
和等于边数的两倍（握手定理）。即,
2e= ∑
n
i=1
TD(Vi)
（ 8）边的权、网图。与边有关的数据信息称为
权（ weight）。在实际应用中，权值可以有某
种含义。比如，在一个反映城市交通线路的图
中，边上的权值可以表示该条线路的长度或者
等级；对于一个电子线路图，边上的权值可以
表示两个端点之间的电阻、电流或电压值；对
于反映工程进度的图而言，边上的权值可以表
示从前一个工程到后一个工程所需要的时间等
等。边上带权的图称为网图或网络
（ network）。
V1
V3
V4 V5
V2
7.3 查找
? 计算机, 计算机网络使信息查询变得更快
捷, 方便, 准确 。 但要从计算机, 计算机
网络中查找特定的信息, 就需要在计算机
中存储包含该特定信息的表 。 如要从计算
机中查找英文单词的中文解释, 就需要存
储类似英汉字典这样的信息表, 以及对该
表进行的查找 （ Searching） 操作 。
学号 姓名 性
别
|
|
|
20010983
20010984
20010985
|
|
|
|
|
|
张三
李四
王五
|
|
|
|
|
|
男
男
女
|
|
|
来 源 总
分
录取
专业
|
|
|
包头一中
保定三中
易县中学
|
|
|
|
|
|
593
601
598
|
|
|
|
|
|
计算机
计算机
计算机
|
|
|
年 月 日
|
|
|
1982
1982
1983
|
|
|
|
|
|
11
09
01
|
|
|
|
|
|
05
12
25
|
|
|
出生年月
1,数据项 (也称项或字段 )
项是具有独立含义的标识单位，是数据不可分割
的最小单位。如表中“学号”、“姓名”,“年”
等。项有名和值之分，项名是一个项的标识，用
变量定义，而项值是它的一个可能取值，表中
,20010983”是项“学号”的一个取值。项具有
一定的类型，依项的取值类型而定。
2,组合项
由若干项, 组合项构成, 表中, 出生日期,
就是组合项, 它由, 年,,, 月,,, 日,
三项组成 。
3,数据元素 （ 记录 ）
数据元素是由若干项, 组合项构成的数据
单位, 是在某一问题中作为整体进行考虑
和处理的基本单位 。
4.关键字
关键字 (Key)是数据元素 （ 记录 ） 中某个
项或组合项的值, 用它可以标识一个数据
元素 （ 记录 ） 。 能唯一确定一个数据元素
（ 记录 ） 的关键字, 称为主关键字
(Primary Key)；
5.查找表
是由具有同一类型 （ 属性 ） 的数据元
素 （ 记录 ） 组成的集合 。 分为静态查
找表 (Static Search Table)和动态
查找表 (Dynamic Search Table)两类 。
6.查找
按给定的某个值 A,在查找表中查找关键字
为给定值 A的数据元素 （ 记录 ） 。
7.3.2 查找的方法
1 顺序查找
又称线性查找, 是最基本的查找方法之
一 。 其查找方法为：从表的一端开始,
向另一端逐个按给定值 kx与关键码进行
比较, 若找到, 查找成功, 并给出数据
元素在表中的位置；若整个表检测完,
仍未找到与 kx相同的关键字, 则查找失
败, 给出失败信息 。
2 折半查找
折半查找的思想为：在有序表 （ 表中的元素
按递增或递减的顺序排列 ） 中, 取中间元素
作为比较对象, 若给定值与中间元素的关键
字相等, 则查找成功；若给定值小于中间元
素的关键字, 则在中间元素的左半区继续查
找；若给定值大于中间元素的关键字, 则在
中间元素的右半区继续查找 。 不断重复上述
查找过程, 直到查找成功, 或所查找的区域
无数据元素, 查找失败 。
3 分块查找
又称索引顺序查找，是对顺序查找的一种
改进。分块查找要求将查找表分成若干个
子表，并对子表建立索引表，查找表的每
一个子表由索引表中的索引项确定。索引
项包括两个字段：关键字字段 (存放对应子
表中的最大关键字值 ) ；
7.4 排序
? 排序 (Sorting)是计算机程序设计中的一种重要操
作，其功能是对一个数据元素集合或序列重新排
列成一个按数据元素某个项值有序的序列。作为
排序依据的数据项称为“排序码”，也即数据元
素的关键字。为了便于查找，通常希望计算机中
的数据表是按关键字有序的。如有序表的折半查
找，查找效率较高。还有，二叉排序树,B-树和
B+树的构造过程就是一个排序过程。若关键字
是主关键字，则对于任意待排序序列，经排序后
得到的结果是唯一的；
? 若关键字是次关键字，排序结果可能不唯一，
这是因为具有相同关键字的数据元素，这些
元素在排序结果中，它们之间的的位置关系
与排序前不能保持一致。
? 若对任意的数据元素序列，使用某个排序方
法，对它按关键字进行排序：若相同关键字
元素间的位置关系，排序前与排序后保持一
致，称此排序方法是稳定的；而不能保持一
致的排序方法则称为不稳定的。
7.4.1 排序分类
? 排序分为两类：内排序和外排序 。
? 内排序：指待排序列完全存放在内存中
所进行的排序过程, 适合不太大的元素
序列 。
? 外排序：指待排序列的数量很大, 以致
内存一次不能容纳全部记录, 在排序过
程中还需访问外存储器 。
? 内排序的方法很多, 下面我们介绍一些
常用的内排序的方法 。
1 直接插入排序
直接插入排序 （ Straight Insertion Sort） 是一
种最简单的排序方法 。 它的基本操作是将
一个记录插入到已排好序的有序表中, 从
而得到一个新的, 记录数增 1的有序表 。
2 折半插入排序
直接插入排序的基本操作是向有序表中插入
一个记录, 插入位置的确定通过对有序表
中记录按关键字逐个比较得到的 。
3 表插入排序
直接插入排序, 折半插入排序均要大量移动
记录, 时间开销大 。 若要不移动记录完成排
序, 需要改变存储结构, 进行表插入排序 。
所谓表插入排序, 就是通过链接指针, 按关
键字的大小, 实现从小到大的链接过程, 为
此需增设一个指针项 。 操作方法与直接插入
排序类似, 所不同的是直接插入排序要移动
记录, 而表插入排序是修改链接指针 。
