1
数据结构
徐虹
http://jwc.cuit.edu.cn/Jxgl/
HomePage/Default.asp
数
据
结
构
之
绪
论
2
说明
? 总学时：
80(学时 )= 60（课时） +20（机时）
? 行课时间从第 1 周 开始，每周 4 学时
? 上机安排待定
? 考试时间：课程结束
? 第 8、 11、 12 章的内容为自学内容；
? 目录中标有 ** 的内容不作要求。
2
数
据
结
构
之
绪
论
3
教材与参考书
? 严蔚敏，《数据结构》，清华大学出版社
? Clifford A. Shaffer, 《数据结构与算法
分析》，电子工业出版社
? Sartaj Sahni, 《数据结构、算法与应用》 ,
机械工业出版社
? 严蔚敏，《数据结构题集》，清华大学出
版社
数
据
结
构
之
绪
论
4
目录
第一章：绪论
第二章：线性表
第三章：栈和队列
第四章：串
第五章：数组和广义表
第六章：树和二叉树
第七章：图
第八章：查找
第九章：内部排序
3
第一章 绪论
什么是数据结构
算法和算法分析
数
据
结
构
之
绪
论
6
1. 1 什么是数据结构
? 数据结构的引论
? 例1 图书馆的书目检索系统自动化问题
在书目自动检索系统中可以建立一张按等录顺序号
排列的书目文件和三张分别按书名、作者名和分类号
顺序排列的索引表，如下所示：
001
002
003
004
...
...
...
...
高等数学
理论力学
高等数学
线形代数
樊映川
罗远祥
华罗庚
栾汝书
S01
L01
S01
S02
.
.
.
.
.
..
.
4
数
据
结
构
之
绪
论
7
高等数学
理论力学
线形代数
001,003, …
002, …
004, …
...
.
.
.
L
S
002,
001, 003
...
...
.
.
.
.
.
.
特点： 计算机按某个特定的要
求进行查询.处理对象之间存在
一种简单的线形关系,这类模型
可以称为简单的线形数据结构.
按书名排列
樊映川
华罗庚
栾汝书
001,
003,
004,
...
...
...
.
.
.
.
.
.
按作者排列
按索引号排列
数
据
结
构
之
绪
论
8
? 例2: 计算机和人的对 弈 问题
对奕的过程是在一定的规则下随机进行的 ,因此 ,计算
机必须对对弈过程之中可能发生的情况以及相应
的对策都考虑周全 .这个关系不是线形的 ,从一个
棋盘可以派生出几个格局 ,如下图 :
“树根 ”是对奕开始之前的棋盘格局 ,而所有的 “叶子 ”是可能出现
的结局 ,对奕的过程就是从树根沿树叉到达某个叶子的过程 .
*
*
**
*
*
*
*
*
*
*
* ** * *
(a) 棋盘格式示例 (b)井字棋对弈树的局部
5
数
据
结
构
之
绪
论
9
? 例3: 多叉路口交通灯的管理问题
可以把这类交通 ,道路的问题当作一种 “图 ”的结构：一个顶点表
示一条通道 ,而通道之间的矛盾的关系以两个顶点之间的连
线表示 .如下图所示 :
A
E
D
C
B
(a) 五叉路口
数
据
结
构
之
绪
论
10
? 结论 ：综合上面三个例子 ,描述这类非数值计算性问
题的数学模型不再是数学方程 ,而是诸如表、树和图之
类的数据结构 .
? 数据结构定义 :
数据结构是一门非数值计算的程序设计问题中计
算机的操作对象以及它们之间的关系和操作等等的学
科 .
6
数
据
结
构
之
绪
论
11
? 数据结构的地位
《数据结构》是计算机科学中一门综合性的专业基础课。
数据结构的研究不仅涉及计算机的硬件的研究范围，
而且和计算机软件的研究有着更为密切的关系，无论
是编译程序还是操作系统，都涉及数据元素在存储器
中的分配问题。 可以认为数据结构是介于数学、计算
机硬件、计算机软件三者之间的一门核心课程。
数
据
结
构
之
绪
论
12
1. 2 基本概念
? 数据（ Data)
客观事物的符号表示 ，能输入到计算机中并被计算
机中程序处理的符号的总称。
? 数据元素 (Data element)
数据的基本单位 ，可由数据项组成。
? 数据类型 (Data Type)
是和数据结构密切相关的一个概念，在高级语言中，
用以刻画（程序）操作对象的特性。是一个值的集合
和定义在这个值集上的一组操作的总称。
7
数
据
结
构
之
绪
论
13
? 数据对象 (Data Object)
性质相同的数据元素的集合 ，是数据的子集。
? 数据结构 (Data Structure)
相互之间存在一种或多种特定关系的数据元素的集
合 。数据元素之间的相互关系称为结构。有下列四种
基本结构：
（ 1）集合（ 2）线形结构（ 3）树形结构（ 4）图状结构 (网状
结构）。
数
据
结
构
之
绪
论
14
集合 线
性
树
图
8
数
据
结
构
之
绪
论
15
? 数据结构类型
数据结构又可以分为两种：物理结构、逻辑结构
其基本类型用关系图描述如下：
? 数据结构的形式定义 ：
Data_Structure=[D,S]
其中： D是数据元素的有限集
S是上下关系的有限集
? 数据的存储结构 ：位、元素和数据域
? 数据结构的存储形式有 ：
?顺序存储
?链式存储
? 虚拟存储结构
数
据
结
构
之
绪
论
16
? 数据类型综述
数据类型可以分为：
原子类型 ——值不可以分解
结构类型 ——值由若干成分按某种结构组成。
抽象数据类型（ ADT） 是一个值的集合和定义
在这个值集上的一组操作的总称。 包括：
原子类型、固定聚合类型和可变聚合类型。
抽象数据类型可通过固有数据类型来表示和实现，
借助高级语言实现的三种情况：封装、继承、
多型。
9
数
据
结
构
之
绪
论
17
? 数据操作描述
? 数据的基本操作：
插入 ：在数据结构的指定位置添加新的数据元素。
拆除 ：去掉数据结构中某个指定的数据元素。
更新 ：改变数据结构中某个数据元素的值。
查找 ：在数据结构中寻找某个满足特定要求的数据元素。
排序 ：重新安排数据元素的逻辑顺序关系，使之值按从
小到大或从大到小的顺序排列。
数
据
结
构
之
绪
论
18
? 操作的分类操作的分类
?加工型操作 ——操作改变了（操作之前
的）结构的值。
?引用型操作 ——不改变值，只是查询或
求得结构的值。
? 操作的描述操作的描述
10
数
据
结
构
之
绪
论
19
1. 3 抽象数据类型的表示与实现
? 语言的描述
? 预定义常量和类型
# define TRUE 1
# define FALSE 0
# define OK 1
# define ERROR 0
Status是函数的类型，其值是函数结果状态代码
typedef int Status
? 数据结构的表示用类型定义（ typedef）描述，数
据元素类型约定为 ElemType，可以是 C语言中任
何数据类型。
数
据
结
构
之
绪
论
20
? 基本操作的算法用以下形式函数来描述
函数类型 函数名（函数参数表）
{
// 算法说明
语句序列
} //函数名
? C语言中操作的描述
? 赋值语句
? 循环语句
? 选择语句
? 注释
? 结束语句
? 输入和输出语句
? 逻辑运算约定
11
数
据
结
构
之
绪
论
21
1. 4 算法与算法分析
? 算法 ：是对特定问题求解步骤的一种描
述，是指令的有限序列。
一个算法就是一个有穷规则的集合，规
则规定了解决某特定问题的运算序列。
? 算法的特性 ：有穷性、确定性、可行性、
输入、输出。
数
据
结
构
之
绪
论
22
? 算法设计的两个目标标
? 易读、易编码和调试（软件工程）
? 充分利用计算机资源（算法和数据结构）
? 算法的设计要求
? 正确性：
?程序不含语法错误；
?程序对于几组输入数据能够得出满足要求的结果；
?程序对于精心选择的典型、苛刻的输入数据能够得出满足要
求的结果；
?程序对于一切合法的输入数据都能够得出满足要求的结果。
? 可读性
? 健壮性
? 效率与低存储量要求
12
数
据
结
构
之
绪
论
23
?最佳、最差、平均情况分析
? 对于不同的输入情况，算法的时间代
价
例如:在一个数组中查找元素 K
? 往往分为最佳、最差、平均情况分析
数
据
结
构
之
绪
论
24
?算法效率的度量
算法效率需通过该算法编制的程序在
计算机上运行所消耗的时间多少以及所
需辅助空间的大小来度量。
? 频度：某语句重复执行的次数。
? 时间复杂度：从算法中选取一个对于所研
究的问题来说是基本操作的源操作，以该
基本操作重复执行的次数作为算法的时间
量度。
T（ n） = O（ f（ n））。
它表示随着 n的增大，算法执行时间的增长
率和 f ( n ) 的增长率相同。
13
数
据
结
构
之
绪
论
25
? 空间复杂度： 一个上机执行的程序
除了需要存储空间来积存本身所用指
令，常数，变量和输入数据外，也需
要一些对数据进行操作的工作单元和
存储一些实现计算所需信息的辅助空
间。该辅助空间的大小及反映了该算
法的空间复杂性。
S（ n） = O（ f（ n））。
数
据
结
构
之
绪
论
26
? 大 O 表示法的运算规则
? 单位时间
?简单布尔或算术运算
?赋值
?简单 I/O
?函数返回
? 加法规则则 : f1(n)+f2(n)=(max(f1(n), f2(n)))
?If结构， switch结构
? 乘法规则则 : f1 (n)· f2(n) = (f1(n)·f2(n))
?for, while, do-while结构
14
数
据
结
构
之
绪
论
27
程序段一：
for(j=1;j<=n;++j)
for(k=1;k<=n;++k){
++x; s+=x;
}
程序段二：
{
++x;
s=0;
}
程序段三：
for(i=1;i<=n;++i) {
++x; s+=x;
}
例1：求下面程序的时间复杂度。
该程序中 “x增 1”是基本
操作语句，其频度为 n
2
，其
时间复杂度为 O(n
2
)，为平方
阶。
该程序中 “x增 1”是基本
操作语句，其频度为 1，其
时间复杂度为 O(1)，为常量
阶。
该程序中 “x增 1”是基本
操作语句，其频度为 n，其
时间复杂度为 O(n)，为线性
阶。
数
据
结
构
之
绪
论
28
课
堂
作
业
分
析
程
序
中
各
语
句
的
频
度
Ex( ) { int I , j , t ;
(1) for( I=1 ; I<10 ; I++)
(2) printf(“\n %d” , I );
(3) for(I=1; I<=2; I++)
(4) printf(“\n”);
(5) for(I=1; I<=9; I++){
(6) for(j=1; j <= I ; j++)
(7) { t = I * j ; printf(“%5d”,t); }
(8) for(j=1; j<3 ; j++)
(9) printf(“\n”); } }
15
数
据
结
构
之
绪
论
29
Ex( ) { int I , j , t ;
(1) for( I=1 ; I<10 ; I++) //n =10
(2) printf(“\n %d” , I ); //n =9
(3) for(I=1; I<=2; I++) //n =3
(4) printf(“\n”); //n =2
(5) for(I=1; I<=9; I++){ //n =10
(6) for(j=1; j <= I ; j++) //n =54
(7) { t = I * j ; printf(“%5d”,t); } //n =45
(8) for(j=1; j<3 ; j++) //n =27
(9) printf(“\n”); } } //n =18
数
据
结
构
之
绪
论
30
?运行时间估计
例：假设 CPU每秒处理 10
6
个指令，对于
输入规模为 = 10
8
的问题，时间代价为
T(n)=2n
2
的算法要运行多长时间？
操作次数为 T(n)=T(10
8
)=2× (10
8
)
2
=2× 10
16
运行时间为 2× 10
16
/10
6
= 2× 10
10
秒
每天有 86,400秒，因此需要 231,480 天 (634
年 )
16
数
据
结
构
之
绪
论
31
例：假设 CPU每秒处理 10
6
个指令，
对于输入规模为 n = 10
8
的问题，时
间代价为 T(n)=nlogn的算法要运行
多长时间？
操作次数为
T(n)=T(10
8
)= 10
8
× log10
8
=2.66× 10
9
运行时间为 2.66× 10
9
/106 = 2.66× 10
3
秒，即 44.33分钟
数
据
结
构
之
绪
论
32
17
数
据
结
构
之
绪
论
33
? 规定时间内能解决的问题规模
假设 CPU每秒处理 10
6
个指令，则每小时
能够解决的最大问题规模
T(n)/10
6
≤ 3600
对 T(n) = 2n
2
，，，，
即 2n
2
≤ 3600 × 10
6
n ≤ 42 , 426
T(n) = nlogn
即 nlogn ≤ 3600 × 10
6
n ≤ 133 , 000 , 000
