1
第一章 概述
? 数据结构的兴起与发展
? 数据结构的研究对象
? 数据结构的概念
? 数据结构的图示
? 数据结构的分类
? 数据结构的存储
? 数据的基本操作
? 算法的基本概念
? 面向对象方法
? 面向对象与数据结构
2
§ 1.1 数据结构的兴起与发展
? 数据结构问题起源于程序设计的发展 。
? 程序设计现在已经历了三个阶段：
–无结构阶段
–结构化程序设计阶段
– 面向对象阶段
3
§ 1.2 数据结构的研究对象
? 计算机应用系统中的两个关键问题：
– 表示 ----- 对象 /实体及其关系在计算机中的表
示 。 只有对象及其相互关系已存储 （ 表示 ） 在计算
机中, 才能被进一步处理；
– 操作 ------ 对对象 /实体进行处理, 访问 。
4
§ 1.2 数据结构的研究对象
? 例 1,解一元二次方程 ax2+bx+c=0.
问题：如何在计算机中表示该方程？
? 用三个系数的线性排列在来表示
–3x2-x+1=0表示为 （ 3,-1,1）
–x2-3=0表示为 (1,0,-3)
? 一元二次方程 ax2+bx+c=0在计算机中表示为 线性表
（ a,b,c）
? 解方程实质上是对线性表 (a,b,c)进行操作 。
5
§ 1.2 数据结构的研究对象
? 例 2,计算机管理家谱, 主要实现家庭成员的登记, 查询及变
更处理等
? 在数据结构中, 该层次结构称为 树 。
W1
W12
W121 W122W111
W11
W131 W132 W133
W13
W1112 W1221W1111
图 - 一个家族结构的树表示
6
§ 1.2 数据结构的研究对象
? 除了确定表示方式外, 数据结构的任务还有对这棵
树的计算机物理存储, 操作的抽象化 。
? 数据结构的研究内容为：
数据的组织方式
相应的抽象操作
7
§ 1.3 数据结构的概念
? 数据,描述客观事物的信息的符号化, 是计算机系
统可加工处理的对象
? 数据类型, 一个值的集合和定义在这个值集上的一
组操作的总称 。
– 原子类型
– 复合类型 （ 或导出类型或结构类型 ）
8
§ 1.3 数据结构的概念
? 数据元素, 数据项,
能独立, 完整地描述问题世界中的实体的最小数据
单位称为 数据元素 （ 也称记录 ） 。 构成数据元素的不
可分割的数据单位, 称为 数据项
? 数据对象, 同类数据元素的集合称为 数据对象,
9
§ 1.3 数据结构的概念
? 数据结构,
相互之间存在着一定关系的数据元素的集合及定义在其上的操
作 （ 运算 ） 为 数据结构,
如果不考虑定义在数据结构上的操作, 则称数据结构为 数据的
逻辑结构,
? 数据的逻辑结构也可借助集合论述语定义：
数据逻辑结构是一个二元组 （ D,S）, 其中 D是数据元素的有限
集, S是 D上的关系的有限集 。
型为 <d1,d2>的二元关系中, 称 d1为关系的 前件, d2为 后件 。
称 d2为 d1的 后继, 而 d1为 d2的 前驱 。
10
§ 1.4 数据结构的图示
? 若 d1和 d2表示两个数据元素, 它们具有关系＜ d1,d2＞,
则表示为
d1 d2
数据元素 数据元素之间的关系
11
§ 1.5.1 集合
?如果数据结构中, 数据元素之间不考虑关
系问题 （ 无前驱 /后继之分 ）, 则称这种结
构为 集合 。
?在集合中, 各元素是, 平等, 的, 它们的
共同关系是,都属于同一个集合 。
12
§ 1.5.2 线性结构
?如果数据结构中, 数据元素之间只存在前后顺
序关系, 则称这种结构为 线性结构 。
?每个元素都有唯一前趋和后继, 第一个元素可
以没有前驱, 最后一个可以没有后继
?线性结构是一种最常见的数据结构 。 线性表,
栈, 队列, 串等均为线性结构 。
13
§ 1.5.2 线性结构
上图表示的数据结构为：
DS=(D,S)
D={d1,d2,…,dn}
S={ r }
r={<d1,d2>,<d2,d3>,…,<dn-1,dn>}
d1 d2 dn
14
§ 1.5.3 树形结构
如果除一个特殊元素没有前驱外, 其他每个元素都有
唯一的前驱 （ 后继个数不限 ）, 则称该结构为 树型结
构 （ 简称 树 ） 。 其中, 将无前驱的元素称为 树根 。
W1
W12
W121 W122W111
W11
W131 W132 W133
W13
W1112 W1221W1111
图 - 一个家族结构的树表示
它代表的结构的形式描述为：
DS= ( D,S)
D = {W1,W11,W12,W13,W111,W121,W122,
W131,W132,W133,W1111,W1112,W1221}
S = {r}
r = {<W1,W11>,<W1,W12>,<W1,W13>,
<W11,W111>,<W12,W121>,<W12,W122>,
<W13,W131>,<W13,W132,>,<W13,W133>,
<W111,W1111>,<W111,W1112>,<W122,W1221> }
15
§ 1.5.3 树形结构
? 树形结构中的数据元素 （ 结点 ） 可分为三种,
? 根, 每个树结构只有一个根 （ 空树无根 ）, 根无前趋,
但可有若干个后继；
? 叶子, 叶子无后继, 但只有且必有一个前趋,
? 普通结点, 有且必有一个前趋, 后继有若干个 。
? 树型结构的应用
? 常用来表达层次关系
? 另一个重要应用是快速检索：为了提高数据检索速度,
可将数据按树结构组织, 如二叉排序树, 平衡二叉树, B树
等 。
16
§ 1.5.4 图状结构
? 图状结构：
任一数据元素, 均可有多个前趋和多个后继 。 该种结构
也称网状结构 。
? 例如, 交通图
树形结构
图状结构 非线性结构
17
§ 1.6 数据结构的存储 ----存储结构
? 计算机的存贮器
? 内部存储器 （ 简称内存, 也称主存 ）
? 外部存储器 （ 简称外存, 也称辅存 ）
? 本课程的几点说明：
? 数据结构的存储问题, 除最后一章外, 都针对内存,
? 用高级语言中的数组模拟计算机存贮器
? C/C++中的指针的概念
§ 1.6.1 存贮器表示问题
18
§ 1.6.2 存贮映象 (存储结构 )问题
? 数据结构的存贮映象, 是指数据结构在计算机中的存储
方式 /方法
? 将一个逻辑上的数据结构存储在计算机中, 必需满足下
列两点：
?内容存储,数据结构中的各数据元素的内容 （ 数据 ）, 都
分别存贮在一个独立的可访问的存贮区中 ;
?关系存储, 数据元素的存放方式方法, 必须能显示地或隐
式地体现数据元素间的逻辑关系 。
? 存贮映象还应考虑存贮使用效率 （ 空间复杂度 ） 及数据
结构的操作的实现的方便性等 。
19
§ 1.6.3 基本存储方法
顺序方法
数据元素的逻辑次序与它们在存贮器中
的存放次序一致 。
? 主要面向线性结构
? 若某结构中存在一种线性关系, 而通过此线性关系就
可以确定元素关系, 也可使用这种方法 。
如多维数组, 顺序二叉树等结构的存贮 。
? 在存贮器中, 任意相邻两数据元素之间的存贮单元数
目应相等 。
20
§ 1.6.3 基本存储方法
? 例：设有数据结构 DS=（ D,S）, 其中,
D={d1,d2,d3,d4},S={r}，
r={<d1,d2>,<d2,d3>,<d3,d4>}
D中每个元素需占用两个存贮单元, 则该结构的顺
序存贮结构如下图
d1 d2 d3 d4 … …
21
§ 1.6.3 基本存储方法
链式存储
每个数据元素的存储区分两大部分
数据区 指针区
?数据元素的存贮区之间, 可以是连续的, 也可不连续
?链式方法具有很大的灵活性
?存储空间开销较大
?对内存空闲区分布的要求不高, 很适合动态存贮管理
22
§ 1.6.3 基本存储方法
? 例 [1.4]：设有数据结构 DS=（ D,S）, 其中,
D={d1,d2,d3,d4},S={r}，
r={<d1,d2>,<d2,d3>,<d3,d4>}
表 1-1
地址 数据 关系指示
a + 0
2 d3 8
4 d1 10
6
8 d4 0
10 d2 2
… … …
每个元素占 2个
存储单元
23
§ 1.6.3 基本存储方法
? [例 1.5] 设数据结构为 DS=（ D,S）, 其中,
D={d1,d2,d3,d4,d5,d6}，
S={r1,r2}，
r1={<d1,d3>,<d3,d4>,<d2,d6>}
r2={<d1,d2>,<d3,d5>}
表 1-2
地址 数据 关系 1 关系 2
a+ 0
4 d2 28
8
12 d1 24 4
16 d5
20
24 d3 32 16
28 d6
32 d4
… … … …
每个元素占 4个存
储单元
24
§ 1.6.3 基本存储方法
索引存储
在数据结构的存储区 （ 称数据区 ） 外, 增加
一个 （ 或若干个 ） 索引区 。
? 主要针对集合和线性表, 面向检索 （ 查找 ） 操作
? 索引区本身也是个线性表或其他数据结构, 结构中每个
元素用于记录数据区中一个 （ 对稠密索引 ） 或一组 （ 对
非稠密索引 ） 元素的存储位置 （ 起始位置 ） 。
? 索引存储并不强调对关系的存储, 而主要针对数据内容,
所以, 一般只适合集合结构或线性结构
25
§ 1.6.3 基本存储方法
散列存储
? 其基本思想是：
设置一个函数, 称为散列函数,元素内容 ?地址；
规定元素内容到存储地址的映射；
? 存储时, 通过散列函数求出元素的应存储的地址, 按
此地址存储；
? 读取时, 通过散列函数求出元素的存储地址, 按此地
址读取；
? 与索引存储类似, 散列存储也是面向内容存储, 不适
合存储复杂数据结构 。
26
§ 1.7 数据的基本操作
对每种数据结构, 如何设置一些操作, 使得各种应用都能
只通过这些操作就能实现对数据结构的各种操作, 我们把
这类操作称为数据结构的 基本操作 或 运算 ；
?基本操作有下列关键点：
– 抽象性
– 基本性
– 完备性
– 支撑性
§ 1.7.1 基本操作的概念
27
? 抽象数据类型实质上是指数据结构及定义在其上的一
组操作
? 一个数据结构应设立那些操作的问题, 由数据结构本
身及数据结构的应用目标有关
? 操作的实现与数据结构的存贮映射方法相关
§ 1.7.2 基本操作的种类
28
? 基本操作类型
– 属性读取 (Get)
– 属性设置 (Set)
– 查找
– 插入
– 删除
– 关系访问
– 遍历
§ 1.7.2 基本操作的种类
29
? 操作的实体是计算机程序, 因此, 基本操作的实现,
是个针对相应的数据结构编程的问题 。 由于程序是算法的
实现, 所以可以讲操作也是算法问题 。
§ 1.7.3 基本操作的实现
30
? 算法
一个算法是规则的有穷集合, 这些规则为解决某一
特定类型问题规定了一个运算序列 。
? 算法的特性：
有穷性
确定性
可行性
输入
输出
§ 1.8 算法的基本概念
§ 1.8.1 算法的概念
31
? 算法的描述方法可以是任意的, 可以用自然语言描述,
也可用数学方法描述, 也可用某种计算机语言 。
? 若用计算机语言描述, 就成了 程序 。
? 衡量算法的优劣的标准
正确性
可读性
健壮性 （ 鲁棒性 ）
时间复杂度与空间复杂度
§ 1.8.1 算法的概念
32
? 相关因素
? 问题性质
? 问题规模
? 算法性质
? 算法的时间复杂度 是指算法的运行速度,
? 算法的速度与时间复杂度, 常指算法自身的抽象运行速
度, 与运行算法的目标计算机及描述算法的工具无关 。
? 一个算法的时间复杂度可以描述为输入规模的函数 f(n)
§ 1.8.2 算法时间复杂度与空间复杂度
33
? [例 1.6] 考虑计算三次多项式
ax3 + bx2 + cx + d
§ 1.8.2 算法时间复杂度与空间复杂度
?一种 直接的计算方法 是：
s=a*x*x*x + b*x*x + c*x + d;
? 该算法共执行 6次乘法,3次加法。
?考察另一种解法：
s=a;
s=s*x+b;
s=s*x+c;
s=s*x+d;
该算法共进行 3次乘法,3次加法
?该算法基于的原理是逐步提取
共因子：
a*x*x*x + b*x*x + c*x + d
= (ax+b)x2 + cx + d
=((ax+b)x + c)x + d
34
? 复杂度的渐近表示
? 许多算法的时间复杂度函数难以给出解析形式
? 通常用某些种简单函数近似表示
? 数学分析中的大 O的定义
设 T(n)和 f(n)均为正整数 n的函数, 则
T(n) = O(f(n))
表示存在一个正整数 M和 n0,使得当 n>= n0 时, 有
| T(n) | <= M | f(n) |
§ 1.8.2 算法时间复杂度与空间复杂度
35
? 几种常见的渐进函数的数量比较关系：即当 n充分大时, 各函
数的大 O的比较 。
O(a) < O(log n) < O(n) < O(n.log n) < O(n2) <,.,< O(nm) < O(an) <
O(n!) < O(nn)
这里, n为自变量, a和 m为常数 。
? 有相当多的一些算法, 它们的时间复杂度可以表示为一个输入
量的高次多项式, 为此, 给出一个相关的定理：
[定理 1.1] 若 A(n) = amnm + … +a1n + a0 是关于 n的一个 m次多项
式, 则
A(n) = O(nm)
§ 1.8.2 算法时间复杂度与空间复杂度
36
(三 ) 算法的时间复杂度的分类
? 通常, 将算法按时间复杂度分为两在类：
? 多项式时间复杂度算法,渐近函数为多项式, 或变
化率不超过多项式；
? 指数时间复杂度算法,渐近函数变化率超过多项式；
§ 1.8.2 算法时间复杂度与空间复杂度
37
? 语句频度 是指语句被重复执行的次数 。
? 算法的时间复杂度：
? 用算法中的各语句的语句频度之和来表示
? 某些语句频度是随机量, 需用概率论方法解决
最好性态, 最差性态和平均性态
? 有些算法是用递归方法描述的, 这类算法的时间复杂度
一般较容易用递归方程表示
§ 1.8.3 算法时间复杂度的度量
38
? 例 1.8] 考虑下列子程序, 它的功能是求出数组 a中各数的大小
次序号, 存在数组 b中的对应位置 。
a[]={4,2,3,9,6,8,7} 则 b[]={3,1,2,7,4,6,5}
void rderNumber(int *a,int n,int *b)
{ int i,j;
for (i=0; i<n; i++) b[i]= 1;
for (i=0 ; i<n-1; i++)
for (j=i+1; j<n ; j++)
if (a[i] < a[j])
b[j]++;
return ;
}
§ 1.8.3 算法时间复杂度的度量
n
n-1
(n-i-1)??
?
1
0
n
i
(n-i-1)??
?
1
0
n
i
最多为 (n-i-1)??
?
1
0
n
i
39
? 总的语句频度最大为：
n + (n-1) + 3(n-i-1)
= 2n-1 + (n+1)n/2
= n2/2 + 5n/2 – 1
= O(n2)
§ 1.8.3 算法时间复杂度的度量
40
? 对象, 实体的抽象
? 属性 或 数据成员, 实体的状态
? 方法 或 操作 或 服务, 实体的行为
对象 = 属性 + 操作
? 类, 一批属性和结构相同且操作相同的对象的抽象 。
§ 1.9.1 对象与类
§ 1.9 面向对象方法
41
封装 （ Encapsulation）
继承 （ Inheritance）
多态性 （ Polymorphism）
消息传递
§ 1.9.2 面向对象方法要素
42
(一 ) 封装（ Encapsulation）
? 封装是指将数据与相应的操作作为一个整体看待
? 操作一般只改变相应的数据，不改变封装体（对象）外部
的目标
? 使用者使用封装体时，只需知道访问操作，而无需顾及内
部实现方法
? 封装与具有数据隐蔽性的功能模块有本质差别
§ 1.9.2 面向对象方法要素
43
(二 ) 继承（ Inheritance）
? 继承主要是为支持实体之间的一般 /特殊关
系
?继承支持一般到特殊（简单到复杂）的构造方
法
?软件复用机制
? [例 1.6]
§ 1.9.2 面向对象方法要素
出版物
书 期刊
44
(三 )多态性（ Polymorphism）
? 一个名字，多种语义；或相同界面，多种实现
? 汽车的刹车器
? 高级程序设计语言中的算术运算
? 多态性是更高级别的信息隐蔽，它不仅隐蔽内部数据与内部
实现，而且隐蔽入口数据的细节
? 在 C++中，多态性通过, 覆盖, （重定义）基类中的虚函数实
现
§ 1.9.2 面向对象方法要素
45
(四 )消息传递
? 驱动状态的转化就称为 消息
? 对象状态的改变是消息传递的结果 --- 事件驱
动
? 企业职工工资管理
? 消息传递与功能模块调用有本质区别
§ 1.9.2 面向对象方法要素
46
? 面向对象方法是客观世界的自然体现
? 面向对象方法支持从一般到特殊的演绎方法
? 面向对象的方法中的继承机制支持演绎方法
? 面向对象方法是一种以数据结构为中心的自底向上增值式
的开发方法
? 面向对象的方法抓住了, 数据, 这个纲
? 面向对象方法支持软件 IC概念
§ 1.9.3 面向对象方法的若干述评
47
? Simula,
§ 1.9.4 面向对象程序设计语言
? 最早正式地将面向对象概念做为语言成份
的是 Simula67
? 由 Ole Dahl和 Krisrten Nygaaard等人于 1967
年设计
? 本意是用于编写模拟系统
? 基于 ALGOL60，首次引入了类、对象、
继承和共行子程序等新概念
48
? Smalltalk
§ 1.9.4 面向对象程序设计语言
? 集成化的程序设计语言和程序设计环境
? Xerox 公司 PARC研究中心所属软件概念
组 的成果
? Smalltak同时也是一个很好的集成化开发
环境
? Smalltalk还有许多贡献，如目前的高分辨
率图形工作站,图符式用户界面及个人
用计算机等都直接来源于 Smalltalk-80系
统
49
? Eiffel
§ 1.9.4 面向对象程序设计语言
? 强类型 OOP语言，由 Betrand Meyer开发
? Eiffel程序由包括方法在内的类说明集合
组成
? 支持参数化类、多重继承、内存管理
? 提供小容量的类库
? 目前最好的商用 OOP语言
50
? C++
§ 1.9.4 面向对象程序设计语言
? AT&T贝尔实验室的 Bjarne stroustrup于
80年代初设计
? 强类型语言
? 开发 C++ 的目的是为了编写一些大型的系
统模拟程序
? 具备了目前公认的面向对象的全部特征
? 支持 C++的环境 /工具 /编译器很多
51
? Java
§ 1.9.4 面向对象程序设计语言
? 1993诞生于 Sun公司的一个名为 Green的项
目的开发
? Java几乎是 C++的精简品
? 定义了大量的标准类库
? 跨平台、可移动
52
§ 1.10 面向对象与数据结构
§ 1.10.1 面向对象与数据结构的关系
? 数据结构主要强调两个方面的内容
– 同类数据元素间的依赖关系；
– 针对这些依赖关系的基本操作
? 对象与数据结构具有下列对应关系：
–对象 ——数据结构
–属性 ——数据元素间的关系的描述
–方法 ——基本操作
–事件 ——无
53
§ 1.10.1 面向对象与数据结构的关系
? 抽象数据类型（ Abstract Data Type — ADT）
是指一个数学模型与定义在该模型上的一组操作
? 数学模型
实质上指用符号化操作定义的数据对象（数
据集）
? 数学模型的概念，对应于面向对象中的数据封装
54
§ 1.10.2 面向对象数据结构
? 面向对象数据结构从下列几个方面改造传统的数据结构：
a) 将基本元素视为对象；
b) 将数据结构视为对象；
c) 对, 相似, 数据结构应用继承
d) 用继承机制扩展基本数据结构
e) 用面向对象的形式描述数据结构。
55
§ 1.10.2 面向对象数据结构
? 数据结构的狭义定义：
– 数据结构可视为二元组（ D,S），其中 D为同类数据元素集
合,S为定义在该集合上的关系的集合
? 广义的数据结构还涉及的另外两点 ——基本操作定义
与 存贮实现
? 面向对象的继承的优点可体现到数据结构上面
线性表
栈 队 字符串
第一章 概述
? 数据结构的兴起与发展
? 数据结构的研究对象
? 数据结构的概念
? 数据结构的图示
? 数据结构的分类
? 数据结构的存储
? 数据的基本操作
? 算法的基本概念
? 面向对象方法
? 面向对象与数据结构
2
§ 1.1 数据结构的兴起与发展
? 数据结构问题起源于程序设计的发展 。
? 程序设计现在已经历了三个阶段：
–无结构阶段
–结构化程序设计阶段
– 面向对象阶段
3
§ 1.2 数据结构的研究对象
? 计算机应用系统中的两个关键问题：
– 表示 ----- 对象 /实体及其关系在计算机中的表
示 。 只有对象及其相互关系已存储 （ 表示 ） 在计算
机中, 才能被进一步处理；
– 操作 ------ 对对象 /实体进行处理, 访问 。
4
§ 1.2 数据结构的研究对象
? 例 1,解一元二次方程 ax2+bx+c=0.
问题：如何在计算机中表示该方程？
? 用三个系数的线性排列在来表示
–3x2-x+1=0表示为 （ 3,-1,1）
–x2-3=0表示为 (1,0,-3)
? 一元二次方程 ax2+bx+c=0在计算机中表示为 线性表
（ a,b,c）
? 解方程实质上是对线性表 (a,b,c)进行操作 。
5
§ 1.2 数据结构的研究对象
? 例 2,计算机管理家谱, 主要实现家庭成员的登记, 查询及变
更处理等
? 在数据结构中, 该层次结构称为 树 。
W1
W12
W121 W122W111
W11
W131 W132 W133
W13
W1112 W1221W1111
图 - 一个家族结构的树表示
6
§ 1.2 数据结构的研究对象
? 除了确定表示方式外, 数据结构的任务还有对这棵
树的计算机物理存储, 操作的抽象化 。
? 数据结构的研究内容为：
数据的组织方式
相应的抽象操作
7
§ 1.3 数据结构的概念
? 数据,描述客观事物的信息的符号化, 是计算机系
统可加工处理的对象
? 数据类型, 一个值的集合和定义在这个值集上的一
组操作的总称 。
– 原子类型
– 复合类型 （ 或导出类型或结构类型 ）
8
§ 1.3 数据结构的概念
? 数据元素, 数据项,
能独立, 完整地描述问题世界中的实体的最小数据
单位称为 数据元素 （ 也称记录 ） 。 构成数据元素的不
可分割的数据单位, 称为 数据项
? 数据对象, 同类数据元素的集合称为 数据对象,
9
§ 1.3 数据结构的概念
? 数据结构,
相互之间存在着一定关系的数据元素的集合及定义在其上的操
作 （ 运算 ） 为 数据结构,
如果不考虑定义在数据结构上的操作, 则称数据结构为 数据的
逻辑结构,
? 数据的逻辑结构也可借助集合论述语定义：
数据逻辑结构是一个二元组 （ D,S）, 其中 D是数据元素的有限
集, S是 D上的关系的有限集 。
型为 <d1,d2>的二元关系中, 称 d1为关系的 前件, d2为 后件 。
称 d2为 d1的 后继, 而 d1为 d2的 前驱 。
10
§ 1.4 数据结构的图示
? 若 d1和 d2表示两个数据元素, 它们具有关系＜ d1,d2＞,
则表示为
d1 d2
数据元素 数据元素之间的关系
11
§ 1.5.1 集合
?如果数据结构中, 数据元素之间不考虑关
系问题 （ 无前驱 /后继之分 ）, 则称这种结
构为 集合 。
?在集合中, 各元素是, 平等, 的, 它们的
共同关系是,都属于同一个集合 。
12
§ 1.5.2 线性结构
?如果数据结构中, 数据元素之间只存在前后顺
序关系, 则称这种结构为 线性结构 。
?每个元素都有唯一前趋和后继, 第一个元素可
以没有前驱, 最后一个可以没有后继
?线性结构是一种最常见的数据结构 。 线性表,
栈, 队列, 串等均为线性结构 。
13
§ 1.5.2 线性结构
上图表示的数据结构为：
DS=(D,S)
D={d1,d2,…,dn}
S={ r }
r={<d1,d2>,<d2,d3>,…,<dn-1,dn>}
d1 d2 dn
14
§ 1.5.3 树形结构
如果除一个特殊元素没有前驱外, 其他每个元素都有
唯一的前驱 （ 后继个数不限 ）, 则称该结构为 树型结
构 （ 简称 树 ） 。 其中, 将无前驱的元素称为 树根 。
W1
W12
W121 W122W111
W11
W131 W132 W133
W13
W1112 W1221W1111
图 - 一个家族结构的树表示
它代表的结构的形式描述为：
DS= ( D,S)
D = {W1,W11,W12,W13,W111,W121,W122,
W131,W132,W133,W1111,W1112,W1221}
S = {r}
r = {<W1,W11>,<W1,W12>,<W1,W13>,
<W11,W111>,<W12,W121>,<W12,W122>,
<W13,W131>,<W13,W132,>,<W13,W133>,
<W111,W1111>,<W111,W1112>,<W122,W1221> }
15
§ 1.5.3 树形结构
? 树形结构中的数据元素 （ 结点 ） 可分为三种,
? 根, 每个树结构只有一个根 （ 空树无根 ）, 根无前趋,
但可有若干个后继；
? 叶子, 叶子无后继, 但只有且必有一个前趋,
? 普通结点, 有且必有一个前趋, 后继有若干个 。
? 树型结构的应用
? 常用来表达层次关系
? 另一个重要应用是快速检索：为了提高数据检索速度,
可将数据按树结构组织, 如二叉排序树, 平衡二叉树, B树
等 。
16
§ 1.5.4 图状结构
? 图状结构：
任一数据元素, 均可有多个前趋和多个后继 。 该种结构
也称网状结构 。
? 例如, 交通图
树形结构
图状结构 非线性结构
17
§ 1.6 数据结构的存储 ----存储结构
? 计算机的存贮器
? 内部存储器 （ 简称内存, 也称主存 ）
? 外部存储器 （ 简称外存, 也称辅存 ）
? 本课程的几点说明：
? 数据结构的存储问题, 除最后一章外, 都针对内存,
? 用高级语言中的数组模拟计算机存贮器
? C/C++中的指针的概念
§ 1.6.1 存贮器表示问题
18
§ 1.6.2 存贮映象 (存储结构 )问题
? 数据结构的存贮映象, 是指数据结构在计算机中的存储
方式 /方法
? 将一个逻辑上的数据结构存储在计算机中, 必需满足下
列两点：
?内容存储,数据结构中的各数据元素的内容 （ 数据 ）, 都
分别存贮在一个独立的可访问的存贮区中 ;
?关系存储, 数据元素的存放方式方法, 必须能显示地或隐
式地体现数据元素间的逻辑关系 。
? 存贮映象还应考虑存贮使用效率 （ 空间复杂度 ） 及数据
结构的操作的实现的方便性等 。
19
§ 1.6.3 基本存储方法
顺序方法
数据元素的逻辑次序与它们在存贮器中
的存放次序一致 。
? 主要面向线性结构
? 若某结构中存在一种线性关系, 而通过此线性关系就
可以确定元素关系, 也可使用这种方法 。
如多维数组, 顺序二叉树等结构的存贮 。
? 在存贮器中, 任意相邻两数据元素之间的存贮单元数
目应相等 。
20
§ 1.6.3 基本存储方法
? 例：设有数据结构 DS=（ D,S）, 其中,
D={d1,d2,d3,d4},S={r}，
r={<d1,d2>,<d2,d3>,<d3,d4>}
D中每个元素需占用两个存贮单元, 则该结构的顺
序存贮结构如下图
d1 d2 d3 d4 … …
21
§ 1.6.3 基本存储方法
链式存储
每个数据元素的存储区分两大部分
数据区 指针区
?数据元素的存贮区之间, 可以是连续的, 也可不连续
?链式方法具有很大的灵活性
?存储空间开销较大
?对内存空闲区分布的要求不高, 很适合动态存贮管理
22
§ 1.6.3 基本存储方法
? 例 [1.4]：设有数据结构 DS=（ D,S）, 其中,
D={d1,d2,d3,d4},S={r}，
r={<d1,d2>,<d2,d3>,<d3,d4>}
表 1-1
地址 数据 关系指示
a + 0
2 d3 8
4 d1 10
6
8 d4 0
10 d2 2
… … …
每个元素占 2个
存储单元
23
§ 1.6.3 基本存储方法
? [例 1.5] 设数据结构为 DS=（ D,S）, 其中,
D={d1,d2,d3,d4,d5,d6}，
S={r1,r2}，
r1={<d1,d3>,<d3,d4>,<d2,d6>}
r2={<d1,d2>,<d3,d5>}
表 1-2
地址 数据 关系 1 关系 2
a+ 0
4 d2 28
8
12 d1 24 4
16 d5
20
24 d3 32 16
28 d6
32 d4
… … … …
每个元素占 4个存
储单元
24
§ 1.6.3 基本存储方法
索引存储
在数据结构的存储区 （ 称数据区 ） 外, 增加
一个 （ 或若干个 ） 索引区 。
? 主要针对集合和线性表, 面向检索 （ 查找 ） 操作
? 索引区本身也是个线性表或其他数据结构, 结构中每个
元素用于记录数据区中一个 （ 对稠密索引 ） 或一组 （ 对
非稠密索引 ） 元素的存储位置 （ 起始位置 ） 。
? 索引存储并不强调对关系的存储, 而主要针对数据内容,
所以, 一般只适合集合结构或线性结构
25
§ 1.6.3 基本存储方法
散列存储
? 其基本思想是：
设置一个函数, 称为散列函数,元素内容 ?地址；
规定元素内容到存储地址的映射；
? 存储时, 通过散列函数求出元素的应存储的地址, 按
此地址存储；
? 读取时, 通过散列函数求出元素的存储地址, 按此地
址读取；
? 与索引存储类似, 散列存储也是面向内容存储, 不适
合存储复杂数据结构 。
26
§ 1.7 数据的基本操作
对每种数据结构, 如何设置一些操作, 使得各种应用都能
只通过这些操作就能实现对数据结构的各种操作, 我们把
这类操作称为数据结构的 基本操作 或 运算 ；
?基本操作有下列关键点：
– 抽象性
– 基本性
– 完备性
– 支撑性
§ 1.7.1 基本操作的概念
27
? 抽象数据类型实质上是指数据结构及定义在其上的一
组操作
? 一个数据结构应设立那些操作的问题, 由数据结构本
身及数据结构的应用目标有关
? 操作的实现与数据结构的存贮映射方法相关
§ 1.7.2 基本操作的种类
28
? 基本操作类型
– 属性读取 (Get)
– 属性设置 (Set)
– 查找
– 插入
– 删除
– 关系访问
– 遍历
§ 1.7.2 基本操作的种类
29
? 操作的实体是计算机程序, 因此, 基本操作的实现,
是个针对相应的数据结构编程的问题 。 由于程序是算法的
实现, 所以可以讲操作也是算法问题 。
§ 1.7.3 基本操作的实现
30
? 算法
一个算法是规则的有穷集合, 这些规则为解决某一
特定类型问题规定了一个运算序列 。
? 算法的特性：
有穷性
确定性
可行性
输入
输出
§ 1.8 算法的基本概念
§ 1.8.1 算法的概念
31
? 算法的描述方法可以是任意的, 可以用自然语言描述,
也可用数学方法描述, 也可用某种计算机语言 。
? 若用计算机语言描述, 就成了 程序 。
? 衡量算法的优劣的标准
正确性
可读性
健壮性 （ 鲁棒性 ）
时间复杂度与空间复杂度
§ 1.8.1 算法的概念
32
? 相关因素
? 问题性质
? 问题规模
? 算法性质
? 算法的时间复杂度 是指算法的运行速度,
? 算法的速度与时间复杂度, 常指算法自身的抽象运行速
度, 与运行算法的目标计算机及描述算法的工具无关 。
? 一个算法的时间复杂度可以描述为输入规模的函数 f(n)
§ 1.8.2 算法时间复杂度与空间复杂度
33
? [例 1.6] 考虑计算三次多项式
ax3 + bx2 + cx + d
§ 1.8.2 算法时间复杂度与空间复杂度
?一种 直接的计算方法 是：
s=a*x*x*x + b*x*x + c*x + d;
? 该算法共执行 6次乘法,3次加法。
?考察另一种解法：
s=a;
s=s*x+b;
s=s*x+c;
s=s*x+d;
该算法共进行 3次乘法,3次加法
?该算法基于的原理是逐步提取
共因子：
a*x*x*x + b*x*x + c*x + d
= (ax+b)x2 + cx + d
=((ax+b)x + c)x + d
34
? 复杂度的渐近表示
? 许多算法的时间复杂度函数难以给出解析形式
? 通常用某些种简单函数近似表示
? 数学分析中的大 O的定义
设 T(n)和 f(n)均为正整数 n的函数, 则
T(n) = O(f(n))
表示存在一个正整数 M和 n0,使得当 n>= n0 时, 有
| T(n) | <= M | f(n) |
§ 1.8.2 算法时间复杂度与空间复杂度
35
? 几种常见的渐进函数的数量比较关系：即当 n充分大时, 各函
数的大 O的比较 。
O(a) < O(log n) < O(n) < O(n.log n) < O(n2) <,.,< O(nm) < O(an) <
O(n!) < O(nn)
这里, n为自变量, a和 m为常数 。
? 有相当多的一些算法, 它们的时间复杂度可以表示为一个输入
量的高次多项式, 为此, 给出一个相关的定理：
[定理 1.1] 若 A(n) = amnm + … +a1n + a0 是关于 n的一个 m次多项
式, 则
A(n) = O(nm)
§ 1.8.2 算法时间复杂度与空间复杂度
36
(三 ) 算法的时间复杂度的分类
? 通常, 将算法按时间复杂度分为两在类：
? 多项式时间复杂度算法,渐近函数为多项式, 或变
化率不超过多项式；
? 指数时间复杂度算法,渐近函数变化率超过多项式；
§ 1.8.2 算法时间复杂度与空间复杂度
37
? 语句频度 是指语句被重复执行的次数 。
? 算法的时间复杂度：
? 用算法中的各语句的语句频度之和来表示
? 某些语句频度是随机量, 需用概率论方法解决
最好性态, 最差性态和平均性态
? 有些算法是用递归方法描述的, 这类算法的时间复杂度
一般较容易用递归方程表示
§ 1.8.3 算法时间复杂度的度量
38
? 例 1.8] 考虑下列子程序, 它的功能是求出数组 a中各数的大小
次序号, 存在数组 b中的对应位置 。
a[]={4,2,3,9,6,8,7} 则 b[]={3,1,2,7,4,6,5}
void rderNumber(int *a,int n,int *b)
{ int i,j;
for (i=0; i<n; i++) b[i]= 1;
for (i=0 ; i<n-1; i++)
for (j=i+1; j<n ; j++)
if (a[i] < a[j])
b[j]++;
return ;
}
§ 1.8.3 算法时间复杂度的度量
n
n-1
(n-i-1)??
?
1
0
n
i
(n-i-1)??
?
1
0
n
i
最多为 (n-i-1)??
?
1
0
n
i
39
? 总的语句频度最大为：
n + (n-1) + 3(n-i-1)
= 2n-1 + (n+1)n/2
= n2/2 + 5n/2 – 1
= O(n2)
§ 1.8.3 算法时间复杂度的度量
40
? 对象, 实体的抽象
? 属性 或 数据成员, 实体的状态
? 方法 或 操作 或 服务, 实体的行为
对象 = 属性 + 操作
? 类, 一批属性和结构相同且操作相同的对象的抽象 。
§ 1.9.1 对象与类
§ 1.9 面向对象方法
41
封装 （ Encapsulation）
继承 （ Inheritance）
多态性 （ Polymorphism）
消息传递
§ 1.9.2 面向对象方法要素
42
(一 ) 封装（ Encapsulation）
? 封装是指将数据与相应的操作作为一个整体看待
? 操作一般只改变相应的数据，不改变封装体（对象）外部
的目标
? 使用者使用封装体时，只需知道访问操作，而无需顾及内
部实现方法
? 封装与具有数据隐蔽性的功能模块有本质差别
§ 1.9.2 面向对象方法要素
43
(二 ) 继承（ Inheritance）
? 继承主要是为支持实体之间的一般 /特殊关
系
?继承支持一般到特殊（简单到复杂）的构造方
法
?软件复用机制
? [例 1.6]
§ 1.9.2 面向对象方法要素
出版物
书 期刊
44
(三 )多态性（ Polymorphism）
? 一个名字，多种语义；或相同界面，多种实现
? 汽车的刹车器
? 高级程序设计语言中的算术运算
? 多态性是更高级别的信息隐蔽，它不仅隐蔽内部数据与内部
实现，而且隐蔽入口数据的细节
? 在 C++中，多态性通过, 覆盖, （重定义）基类中的虚函数实
现
§ 1.9.2 面向对象方法要素
45
(四 )消息传递
? 驱动状态的转化就称为 消息
? 对象状态的改变是消息传递的结果 --- 事件驱
动
? 企业职工工资管理
? 消息传递与功能模块调用有本质区别
§ 1.9.2 面向对象方法要素
46
? 面向对象方法是客观世界的自然体现
? 面向对象方法支持从一般到特殊的演绎方法
? 面向对象的方法中的继承机制支持演绎方法
? 面向对象方法是一种以数据结构为中心的自底向上增值式
的开发方法
? 面向对象的方法抓住了, 数据, 这个纲
? 面向对象方法支持软件 IC概念
§ 1.9.3 面向对象方法的若干述评
47
? Simula,
§ 1.9.4 面向对象程序设计语言
? 最早正式地将面向对象概念做为语言成份
的是 Simula67
? 由 Ole Dahl和 Krisrten Nygaaard等人于 1967
年设计
? 本意是用于编写模拟系统
? 基于 ALGOL60，首次引入了类、对象、
继承和共行子程序等新概念
48
? Smalltalk
§ 1.9.4 面向对象程序设计语言
? 集成化的程序设计语言和程序设计环境
? Xerox 公司 PARC研究中心所属软件概念
组 的成果
? Smalltak同时也是一个很好的集成化开发
环境
? Smalltalk还有许多贡献，如目前的高分辨
率图形工作站,图符式用户界面及个人
用计算机等都直接来源于 Smalltalk-80系
统
49
? Eiffel
§ 1.9.4 面向对象程序设计语言
? 强类型 OOP语言，由 Betrand Meyer开发
? Eiffel程序由包括方法在内的类说明集合
组成
? 支持参数化类、多重继承、内存管理
? 提供小容量的类库
? 目前最好的商用 OOP语言
50
? C++
§ 1.9.4 面向对象程序设计语言
? AT&T贝尔实验室的 Bjarne stroustrup于
80年代初设计
? 强类型语言
? 开发 C++ 的目的是为了编写一些大型的系
统模拟程序
? 具备了目前公认的面向对象的全部特征
? 支持 C++的环境 /工具 /编译器很多
51
? Java
§ 1.9.4 面向对象程序设计语言
? 1993诞生于 Sun公司的一个名为 Green的项
目的开发
? Java几乎是 C++的精简品
? 定义了大量的标准类库
? 跨平台、可移动
52
§ 1.10 面向对象与数据结构
§ 1.10.1 面向对象与数据结构的关系
? 数据结构主要强调两个方面的内容
– 同类数据元素间的依赖关系；
– 针对这些依赖关系的基本操作
? 对象与数据结构具有下列对应关系：
–对象 ——数据结构
–属性 ——数据元素间的关系的描述
–方法 ——基本操作
–事件 ——无
53
§ 1.10.1 面向对象与数据结构的关系
? 抽象数据类型（ Abstract Data Type — ADT）
是指一个数学模型与定义在该模型上的一组操作
? 数学模型
实质上指用符号化操作定义的数据对象（数
据集）
? 数学模型的概念，对应于面向对象中的数据封装
54
§ 1.10.2 面向对象数据结构
? 面向对象数据结构从下列几个方面改造传统的数据结构：
a) 将基本元素视为对象；
b) 将数据结构视为对象；
c) 对, 相似, 数据结构应用继承
d) 用继承机制扩展基本数据结构
e) 用面向对象的形式描述数据结构。
55
§ 1.10.2 面向对象数据结构
? 数据结构的狭义定义：
– 数据结构可视为二元组（ D,S），其中 D为同类数据元素集
合,S为定义在该集合上的关系的集合
? 广义的数据结构还涉及的另外两点 ——基本操作定义
与 存贮实现
? 面向对象的继承的优点可体现到数据结构上面
线性表
栈 队 字符串
