1北京邮电大学自动化学院
数据结构
北京邮电大学自动化学院
杨福兴
电话,13331090202
E-mail,yangfx@sina.com
2004年 9月 13日
2北京邮电大学自动化学院
? 使用教材：
?严蔚敏 吴伟民 编著,数据结构（ C语言
版），清华大学出版社
? 参考书：
?1、曹桂琴 编著，数据结构基础，大连理工大
学出版社。
?2、晋良颖 编，数据结构，人民邮电出版社
?3,Bruno R.Preiss，数据结构与算法，电子
工业出版社
使用教材及参考书
3北京邮电大学自动化学院
,数据结构, 辅导老师名单
辅导老师 负责班级 电 话 E-mail 地点
张志霞 0215301～ 2 13811789470 zhixia1223@eyou.com 4－ 129
李维成 03507～ 9 13366767286 lisyan@126.com 4－ 129
杜伟 03501~2 13810984903 dwzhx-1@163.com 4－ 314
王松月 03503~4 13311509032 wsy5228@sina.com 4－ 314
4北京邮电大学自动化学院
课程教学目的
? 在计算机及其应用的各个领域中，都会用到各种
各样的数据结构，通过本课程使学生学会分析和
研究计算机加工对象的特性，选择合适的数据结
构和存储表示，以及编制相应的实现算法．
? 课程教学基本要求,本课程介绍各种最常用的数据
结构，阐述各种数据结构内涵的逻辑关系，讨论
它们在计算机中的存储表示，以及在这些数据结
构上的运算和实际的执行算法，并对算法的效率
进行简要的分析和讨论。
5北京邮电大学自动化学院
? 数据结构的研究不仅涉及到
? 计算机硬件 （特别是编码理论、存储装置和存取
方法）的研究范围，
? 而且和 计算机软件 的研究有着密切的关系，无论
是编译程序还是操作系统，都涉及到数据元素在
存储器中的分配问题。
? 在研究 信息检索时 也必须考虑如何组织数据，以
便查找和存取数据元素更为方便。
课程介绍
6北京邮电大学自动化学院
? 因此，可以认为 数据结构 是介于 数学、计算机硬件
和计算机软件 三者之间的一门核心课程。
? 程序＝算法＋数据结构
? 目前在我国,,数据结构, 已经不仅仅是计算机专
业的教学计划中的核心课程之一，而且是其它非计
算机专业的主要选修课程之一。
? 通过对这门课程的学习可增强选择合适的数据结构
与编写高效的程序的能力。
课程介绍
7北京邮电大学自动化学院
教学安排及考试
? 讲课学时,34学时
? 上机时间,5次（每次 2学时）
? 考试成绩计算：
?平时成绩（考勤,作业及上机） 30分
?考试（ 70分）
? 考查课和考试课分别考试，考查课在第 17周考
试，考试课按学校安排时间考试。
8北京邮电大学自动化学院
目录
? 第 1章 绪论
? 第 2章 线性表
? 第 3章 栈和队列 第 4章 串
? 第 5章 数组和广义表
? 第 6章 树和二叉树
? 第 7章 图
? 第 8章 查找
? 第 9章 内部排序
? 第 10章 文件
9北京邮电大学自动化学院
? 计算机的应用已不再局限于科学计算，而更多地
用于控制、管理及数据处理等 非数值计算的处理
工作 。
? 与此对应，计算机加工处理的对象由纯粹的数值
发展到 字符、表格和图像 等各种具有一定结构的
数据。
? 为了编写出一个“好”的程序，必须分析 待处理
的对象的特征以及各对象之间存在的关系,这就
是“数据结构”这门学科形成和发展的背景。
第一章 绪 论
第一章 绪 论
10北京邮电大学自动化学院
? 一般来说，用计算机解决一个具体问题时，大致需要经多下
列几个步骤：
?首先要从具体问题抽象出一个适当的数学模型
?然后设计一个解此数学模型的算法，
?最后编出程序、进行测试、调整直至得到最终解答。
? 寻求数学模型的实质是分析问题，从中提取操作的对象，并
找出这些操作对象之间含有的关系，然后用数学的语言加以
描述。
? 然而，更多的非数值问题无法用数学方程描述。什么是数据
结构呢？先看以下几个例子。
1.1 什么是数据结构
11北京邮电大学自动化学院
0 0 1 高等数学 樊映川 S 0 1
0 0 2 理论力学 罗远祥 L 0 1
0 0 3 高等数学 华罗庚 S 0 1
0 0 4 线性代数 栾汝书 S 0 2
…… …… …… ……
书目文件
按书名 按作者名 按分类号
高等数学 001, 003 ……
理论力学 002, ……,.
线性代数 004, ……
…… ……,.
樊映川 001,…
华罗庚 002,…,
栾汝书,…,
……, ……,
L 002,…
S 0 0 1,0 0 3,
…… ……
索引表
线性表
例 1 书目自动检索系统
登录号：
书名：作者名：
分类号：出版单位：
出版时间：价格：
书目卡片
12北京邮电大学自动化学院
树
……..……..
…..,…..,…..,…...
例 2 人机对奕问题
13北京邮电大学自动化学院
? 对于一个多叉路口，设计一
个交通信号灯的管理系统。
? 首先需要分析一下所有车辆
的行驶路线的冲突问题。
? 这个问题可以归结为对车辆
的可能行驶方向作某种分
组，对分组的要求是使任一
个组中各个方向行驶的车辆
可以同时安全行驶而不发生
碰撞。
C
E
D
A
B
例 3 多叉路口交通灯管理问题
14北京邮电大学自动化学院
可通行方向
?A?B A?C A ?D
?B ?A B?C B?D
?D?A D?B D ?C
?E ?A E?B E?C E?D
C
E
D
A
B
例 3多叉路口交通灯管理问题
15北京邮电大学自动化学院
有些通行方向显然不能同时进行，相应的结点间画一条连线。
AB AC AD
BA BC BD
DA D B DC
EA EB EC ED
图 1.2 交叉路口的图示模型
C
E
D
A
B
图
16北京邮电大学自动化学院
? 把图 1.2中的结点进行分组，使得有结点相连的结点不
在同一个组里。
? 地图着色问题
? 如果把上图中的一个结点理解为一个国家,结点之间
的连线看作两国有共同边界，上述问题 就变成著名的
“着色问题”,即求出最少要几种颜色可将图中所有
国家着色，使得任意两个相邻的国家颜色都不相同。
? 通过上面的分析，我们就获得了该交通管系统的数学
模型。下面就可以着手进行算法的设计。
例 3多叉路口交通灯管理问题
17北京邮电大学自动化学院
算法设计
? 2.,贪心法”
? while 有结点未着色；
? { 选择一种新颜色；
? 在未着色的结点中,给尽可能多的彼此结点之间没有边
点着色；
? }
? 1,对 n个结点，逐个测试其所有组合；
例 3多叉路口交通灯管理问题
18北京邮电大学自动化学院
AB AC AD
BA BC BD
DA D B DC
EA EB EC ED
图 1.2 交叉路口的图示模型
图
AB AC AD
BA BC BD
DA DB DC
EA EB EC ED
C
E
D
A
B
着色结果
19北京邮电大学自动化学院
? 把上面方法应用于图 1.2，得到下面的分组：
? 绿色,AB,AC,AD,BA,DC,ED
? 蓝色,BC,BD,EA
? 红色,DA,DB
? 白色,EB,EC
例 3多叉路口交通灯管理问题
20北京邮电大学自动化学院
? 综上三个例子，描述这类非数值计算问题的数学模型
不再是数学方程，而是诸如 表、树和图 之类的数据结
构。
? 因此，简单说来，数据结构是一门 研究非数值计算的
程序设计问题中 计算机的操作对象以及它们之间的关
系和操作等等的学科 。
? 数据结构就是研究数据的逻辑结构和物理结构它们之
间相互关系，并对这种结构定义相应的运算，而且确
保经过这些运算后所得到的新结构仍然是原来的结构
类型。
第一章 绪 论
21北京邮电大学自动化学院
? 数据 (Data):是对客观事物的符号表示，在计算机科
学中是指 所有能输入到计算机中并被计算机程序处
理的符号的总称。
? 对计算机科学而言，数据的含义极为广泛，如图
像、声音等都可以通过编码而归之于数据的范畴。
? 数据元素 (Data Element):是数据的基本单位，在计
算机程序中通常作为一个整体进行考虑和处理。
? 例如，例 1－ 2中的“树”中的一个棋盘格局，例 1
－ 3中的“图”中的一个园圈都被称为一个数据元
素。
1.2 基本概念和术语
22北京邮电大学自动化学院
? 一个数据元素可由若干个数据项组成。例如，例 1－ 1中一
本书的书目信息为一个数据元素，而书目信息中的每一项
（如书名、作者名等）为一个数据项。
? 数据项是数据的不可分割的最小单位 。
? 数据对象 (Data Object),是性质相同的数据元素的集合，
是数据的一个子集。例如，整数数据对象是集合 N＝ {0，
± 1,± 2,… }，字母字符数据对象是集合 C＝ {A,B，
C,…} 。
? 数据结构 (Data Structure),是相互之间存在一种或多种
特定关系的数据元素的集合。
1.2 基本概念和术语
23北京邮电大学自动化学院
? 数据结构主要指逻辑结构和物理结构。 数据之间的相互关系称
为逻辑结构 。通常分为四类基本结构：
? 一、集合 结构中的数据元素除了同属于一种类型外，别无其
它关系。
? 二、线性结构 结构中的数据元素之间存在一对一的关系。
? 三、树型结构 结构中的数据元素之间存在一对多的关系。
? 四、图状结构或网状结构 结构中的数据元素之间存在多对多
的关系。
1.2 基本概念和术语
24北京邮电大学自动化学院
? 数据结构的形式定义为：数据结构是一个二元组：
? Data-Structure=(D,S)
? 其中,D是数据元素的有限集,S是 D上关系的有限
集。
? 例 复数的数据结构定义如下,Complex=(C,R)
? 其中,C是含两个实数的集合 ﹛ C1,C2﹜,分别表
示复数的实部和虚部。 R={P},P是定义在集合上的
一种关系 {〈 C1,C2〉 }。
1.2 基本概念和术语
25北京邮电大学自动化学院
? 数据结构在计算机中的表示称为数据的物理结构，又称为
存储结构。
? 数据结构在计算机中有两种不同的表示方法：
? 顺序表示和非顺序表示
? 由此得出两种不同的存储结构,顺序存储结构和链式存储
结构
? 顺序存储结构,用数据元素在存储器中的相对位置来表示
数据元素之间的逻辑关系。
? 链式存储结构,在每一个数据元素中增加一个存放地址的
指针,用此指针来表示数据元素之间的逻辑关系。
1.2 基本概念和术语
26北京邮电大学自动化学院
元素 n
……..
元素 i
……..
元素 2
元素 1L
o
Lo+m
Lo+(i-1)*m
Lo+（ n-1)*m
存储地址 存储内容
Loc(元素 i)=Lo+（ i-1)*m
顺序存储
27北京邮电大学自动化学院
1536元素 21400元素 1 1346元素 3 ∧元素 4
1345h
存储地址 存储内容 指针
1345 元素 1 1400
1346 元素 4 ∧
……, ……,,……,
1400 元素 2 1536
……, ……,,……,
1536 元素 3 1346
链式存储
h
28北京邮电大学自动化学院
数据的逻辑结构
数据的存储结构
数据的运算：检索、排序、插入、删除、修改等
线性结构
非线性结构
顺序存储
链式存储
线性表
栈
队
树形结构
图形结构
数据结构的三个方面：
1.2 基本概念和术语
29北京邮电大学自动化学院
? 数据类型,数据类型是一个值的集合和定义在这个值集范围
上的一组操作的总称。例如,C语言中的整型变量，其值集
为某个区间上的整数，定义在其上的操作为：加、减、乘、
除和取模等算术运算。
? 按“值”的不同特性，高级程序语言中的数据类型可分为：
? 一类是非结构的原子类型 。原子类型的值是不可分解的。
如,C语言中的基本类型（整型、实型、字符型和枚举类
型）、指针类型和空类型。
? 另一类是结构类型 。结构类型的值是由若干成分按某种结构
组成的。例如数组的值由若干分量组成。每个分量可以是整
数，也可以是数组等。
1.2 基本概念和术语
30北京邮电大学自动化学院
? 抽象数据类型：一个数学模型以及定义在该模型上的一组操
作。 抽象数据类型的定义仅取决于它的一组逻辑特性，而与
其在计算机内部如何表示和实现无关，即不论其内部结构如
何变化，只要它的数学特性不变，都不影响其外部的使用。
? 抽象数据类型实际上就是对该数据结构的定义。因为它定义
了一个数据的逻辑结构以及在此结构上的一组算法。
? 和数据结构的形式定义相对应，抽象数据类型可用三元组描
述如下,（Ｄ，Ｓ，Ｐ）
? D是数据对象,S是 D上的关系集,P是对 D的基本操作集。
1.2 基本概念和术语
31北京邮电大学自动化学院
? 本书采用以下格式定义抽象数据类型
? 抽象数据类型的定义：
ADT抽象数据类型名 {
数据对象,<数据对象的定义 >
数据关系,<数据逻辑关系的定义 >
基本操作,<基本操作的定义 >
? }ADT抽象数据类型名
? 基本操作的定义格式为：
基本操作名（参数表）
初始条件,<初始条件描述 >
? 操作结果,<操作结果描述 >
1.2 基本概念和术语
32北京邮电大学自动化学院
? 抽象数据类型三元组的定义：
? ADT Triplet{
? 数据对象,D={e1,e2,e3|e1,e2,e3?ElemSet}
? 数据关系,R1={<e1,e2>,<e2,e3>}
? 基本操作：
? InitTriplet(&T,v1,v2,v3)
? 操作结果,构造了三元组 T，元素 e1,e2和 e3分别赋以参数
v1,v2和 v3的值。
? } ADT Triplet
1.2 基本概念和术语
33北京邮电大学自动化学院
? ADT Triplet{
? 数据对象, D={e1,e2,e3|e1,e2,e3?ElemSet}
? 数据关系, R1={<e1,e2>,<e2,e3>}
? 基本操作,
? Get(T,i,&e)
? 初始条件,三元组 T已存在,1?i?3
? 操作结果,用 e返回 T的第 i元的值。
? } ADT Triplet
1.2 基本概念和术语
34北京邮电大学自动化学院
? 抽象数据类型 可通过固有数据类型来表示和实现，即利
用处理器中已存在的数据类型来说明新的结构，用已经
实现的操作来组合新的操作。
? 由于本书在高级程序设计语言的虚拟层次上讨论抽象数
据类型的表示和实现，并且讨论的数据结构及其算法主
要是面向读者，故采用 介于伪码和 C语言之间的类 C语
言作为描述工具,有时也用伪码描述一些只含抽象操作
的抽象算法。
? 这使得数据结构和算法的描述和讨论简明清晰，不拘泥
于 C语言的细节，又能容易转换成 C或者 C＋＋程序。
1.3 抽象数据类型的表示和实现
35北京邮电大学自动化学院
? 本书采用的类 C语言精选了 C语言的一个核心子集，同时作了
若干扩充，增强了语言的描述功能。以下对其作简要说明。
? （ 1）预定义常量和类型
? //函数结果状态代码
? #define TRUE 1 #define FLASE 0
? #define OK 1 #define ERROR 0
? #define INFEASIBLE -1 #define OVERFLOW -2
? // Status是函数的类型，其值是函数结果状态代码
? Typedef int Status;
1.3 抽象数据类型的表示和实现
36北京邮电大学自动化学院
? （ 2）数据结构的表示用类型定义（ typedef）描述。
数据元素类型约定为 Elemtype，由用户在使用该数据
类型时定义。
? （ 3）基本操作的算法都用以下形式的函数描述：
?函数类型 函数名 （函数参数表） {
?//算法说明
?语句序列
?}//函数名
1.3 抽象数据类型的表示和实现
37北京邮电大学自动化学院
? （ 4）赋值语句有
?简单赋值 变量名 =表达式；
?串值赋值 变量名 1=变量名 2=……= 表达式
?成组赋值 （变量名 1，。。。，） =（表达式
1，）
?交换赋值 变量名 ? 变量名
?条件赋值 变量名 =条件表达式？表达式 T：表
达式 F
1.3 抽象数据类型的表示和实现
38北京邮电大学自动化学院
? （ 5）选择语句有
? 条件语句 1 if（表达式）语句；
? 条件语句 2 if（表达式）语句； Else 语句
? 开关语句 1 switch(表达式 ) {
? case 值 1：语句序列 1； break;
? Default,语句序列 n+1;}
? 开关语句 2 switch{
? case 条件 1：语句序列 1； break;
? Default,语句序列 n+1;}
1.3 抽象数据类型的表示和实现
39北京邮电大学自动化学院
? （ 6）循环语句有
? For语句
? for（赋初值表达式；条件；修改表达式序列）语句；
? While 语句 while（条件）语句；
? do-while语句
? do {
? 语句序列 }while（条件）；
1.3 抽象数据类型的表示和实现
40北京邮电大学自动化学院
? （ 7）结束语句
?函数结束语句 return 表达式； return；
?Case结束语句 break;
?异常结束语句 exit(异常代码 )
? 8）输入和输出语句
? 输入语句 scanf([格式串 ]，变量 1，变量 n)；
? 输出语句 printf([格式串 ]，表达式 1，表达式 2)；
1.3 抽象数据类型的表示和实现
41北京邮电大学自动化学院
? （ 9）注释
? 单行注释 //文字序列
? （ 10）基本函数有
? 求最大值 max(表达式 1，表达式 n）
? 求最小值 min(表达式 1，表达式 n）
? 求绝对值 abs(表达式 )
? 求不足整数值 floor（表达式）
? 判定行结束 eoln（文件变量）或 eoln
1.3 抽象数据类型的表示和实现
42北京邮电大学自动化学院
? （ 11）逻辑运算约定
? 与运算 &&,对于 A &&B,当 A的值为 0时,不再对 B
求值。
? 或运算 ||,对于 A||B,当 A的值为非 0时,不再对 B
求值。
1.3 抽象数据类型的表示和实现
43北京邮电大学自动化学院
? 例题：抽象数据类型 Triplet的表示和实现
? //--------采用动态分配的顺序存储结构 ----------------
? Typedef ElemType *Triplet://initTriplet分配三个元素存
储空间
? //--------基本操作的函数原形说明 ----------------
? Status InitTriplet (Triplet &T,ElemType v1,ElemType
v2,ElemType v3）；
? //操作结果：构造了三元组 T，元素 e1,e2和 e3分别赋以参
数 v1,v2和 v3的值。
1.3 抽象数据类型的表示和实现
44北京邮电大学自动化学院
? Status DestroyTriplet (Triplet &T）；
?//操作结果：三元组 T被消除。
? Status Get (Triplet &T,int i,ElemType &e）；
?//初始条件：三元组 T已存在,1?i?3 。
? //操作结果：用 e返回 T的第 i元的值。
1.3 抽象数据类型的表示和实现
45北京邮电大学自动化学院
? //--------基本操作的实现 ----------------
? Status Get (Triplet &T,int i,ElemType &e） {
? // 1?i?3,用 e返回 T的第 i元的值。
? If (i<1||i>3) return ERROR;
? e=T [i-1] ；
? return OK;
? }//Get
? } ADT Triplet
1.3 抽象数据类型的表示和实现
46北京邮电大学自动化学院
? 算法是对特定问题求解步骤的一种描述，它是指令的有限序
列，每一条指令表示一个或多个操作。 1、算法有五个特性：
1.4 算法和算法分析
? （ 1）有穷性 一个算法必须总是在执行有穷步之后结束，且
每一步都在有穷时间内完成。
? （ 2）确定性 算法中每一条指令必须有确切的含义。不存在二
义性。且算法只有一个入口和一个出口。
? （ 3）可行性 一个算法是可行的。即算法描述的操作都是可以
通过已经实现的基本运算执行有限次来实现的。
? （ 4）输入 一个算法有零个或多个输入。
? （ 5）输出 一个算法有一个或多个输出。
47北京邮电大学自动化学院
? 评价一个好的算法有以下几个标准,
? （ 1） 正确性
? （ 2）可读性 算法应该好读。
? （ 3）健状性 算法应具有容错处理。当输入非法数据
时，算法应对其作出反应，而不是产生莫名其妙的输
出结果。
? （ 4）效率与存储量需求 效率是指算法执行的时
间；存储量需求指算法执行过程中所需要的最大存储
空间。
2,算法设计的要求
48北京邮电大学自动化学院
? 程序不含语法错误。
? 程序对于几组输入数据能够得出满足规格说
明的结果。
? 程序对于精心选择的典型、苛刻而带有刁难
性的几组输入数据能够得出满足规格说明的
结果。
? 程序对于一切合法的输入数据都能产生满足
规格说明的结果。
正确性（算法应满足具体问题的需求）
49北京邮电大学自动化学院
? 算法执行时间需要通过依据该算法编制的程序在计算机上运行时
所消耗的时间度量。度量一个程序的执行时间通常有两种方法。
? 事后统计的方法
?一是必须先运行依据算法编制的程序
?二是所得时间的统计量依赖于计算机的硬件、软件等环境
因素求出该算法的一个时间界限函数
? 事前分析估算的方法
?依据的算法选用何种策、问题的规模、书写的语言、编译
程序所产生的机器代码的质量、机器执行指令的速度。
? 所以，人们常常采用事前分析估算的方法。
3,算法效率的度量
50北京邮电大学自动化学院
? 使用绝对的时间单位衡量算法的效率是不合适的。 撇开这些
与计算机硬件软件有关的因素，可以认为一个特定算法的
“运行工作量”的大小，只依赖于 问题的规模 （通常用整数
量表示），或者说,它是问题规模的函数。
? 一个算法是由控制结构（顺序分支和循环三种）和原操作
（指固有数据类型的操作）构成的，则算法时间取决于两者
的综合效果。
? 为了便于比较同一问题的不同算法,通常的做法是，从算法
中选取一种对于研究问题（或算法类型）来说是基本操作的
原操作，以该基本操作重复执行的次数作为算法的时间量
度。
3,算法效率的度量
51北京邮电大学自动化学院
? 整个算法的执行时间与该基本操作（乘法）重复执行的次数
n3成正比，记为 T(n)=O(n3)
? for(i=1;i<=n;++i)
? for(j=1;j<=n;++j){ c[i][j]=0;
? for(k=1;k<=n;++k) c[i][j]+=a[i][k]*b[k][j];}
? 一般情况下，算法中基本操作重复执行的次数是问题规模 n
的某个函数 f(n),算法的时间度量记作 T(n)=O(f(n))
? 它表示随着问题规模 n的增加,算法执行时间的增长率和
f(n)的增长率相同,称作算法的渐进时间复杂度，简称时间
复杂度。
? 例 1，在如下所示的两个矩阵相乘的算法中，“乘法”运算是
“矩阵相乘问题”的基本操作。
52北京邮电大学自动化学院
? 显然，被称作问题的基本操作的原操作应是其重复执行次数
和算法的执行时间成正比的原操作，多数情况下它是最深层
循环内的语句中的原操作,它的执行次数和包含它的语句的
频度相同。
? 语句的频度是指的是该语句重复执行的次数。
? 例２ {++x;s=0;}
? 将 x自增看成是基本操作，则语句频度为 １,即 时间复杂度
为Ｏ (1)。
? 如果将 s=0也看成是基本操作，则语句频度为 ２,其 时间复
杂度仍为Ｏ (1)，即常量阶。
3,算法效率的度量
53北京邮电大学自动化学院
? 例３,for(i=1;i<=n;++i) {++x;s+=x;}
?语句频度为,2n
?其时间复杂度为,O(n)
?即时间复杂度为线性阶。
? 例４,for(i=1;i<=n;++i)
? for(j=1;j<=n;++j) {++x;s+=x;}
?语句频度为,2n2
?时间复杂度为,O(n2)
?即时间复杂度为平方阶。
3,算法效率的度量
54北京邮电大学自动化学院
? 定理：若 A(n)=amnm +am-1nm-1 +…+a 1n+a0是一个 m次多项
式，则 A(n)=O(nm)。证略。
? 例５ for(i=2;i<=n;++I)
? for(j=2;j<=i-1;++j) {++x;a[i,j]=x;}
? 语句频度为,1+2+3+…+n -2=(1+n-2) × (n-2)/2
? =(n-1)(n-2)/2 =n2-3n+2
?时间复杂度为 O(n2),
? 即此算法的时间复杂度为平方阶。
3,算法效率的度量
55北京邮电大学自动化学院
? 以下六种计算算法时间的多项式是最常用的。其关系为：
? O(1)<O(logn)<O(n)<O(nlogn) <O(n2)<O(n3)
? 指数时间的关系为：
? O(2n)<O(n!)<O(nn)
? 当 n取得很大时，指数时间算法
和多项式时间算法在所需时间上
非常悬殊。 因此，只要有人能将
现有指数时间算法中的任何一个
算法化简为多项式时间算法，那
就取得了一个伟大的成就。
3,算法效率的度量
56北京邮电大学自动化学院
? 有的情况下，算法中基本操作重复执行的次数还随问题
的输入数据集不同而不同。例如：
? Void bubble-sort(int a[],int n)
? for(I=n-1,change=TURE;I>1 && change;--I) {
? change=false; for(j=0;j<I;++j)
? if (a[j]>a[j+1]) { a[j] ←→a[j+1];change=TURE} }
? 最好情况,0次 最坏情况,1+2+3+…+n -1=n(n-1)/2
? 平均时间复杂度为,O(n2)
? 在本书以后各章节中讨论的时间复杂度，除特别指明
外，均指最坏情况下的时间复杂度。
3,算法效率的度量
57北京邮电大学自动化学院
? 类似于算法的时间复杂度，本书中以空间复杂
度作为算法所需存储空间的量度，记作,
? S(n)=O(f(n))
? 其中 n为问题的规模 (或大小 )。
? 一个上机执行的程序除了需要存储空间来寄存
本身所用指令、常数、变量和输入数据外，也
需要一些对数据进行操作的工作单元和存储一
些为实现计算所需信息的辅助空间。
4、算法的存储空间需求
58北京邮电大学自动化学院
4、复习提纲
? 1、理解数据、数据结构、存储结构
? 2、理解抽象数据类型及面向对象概念：数据类
型；数据抽象与抽象数据类型；用于描述数据结构
的语言
? 3、理解算法定义
? 4、掌握性能分析与度量（算法的性能标准；算法
的后期测试；算法的事前估计；空间复杂度度量；
时间复杂度度量；时间复杂度的渐进表示法；）
59北京邮电大学自动化学院
2、选择题。数据结构是一门研究非数值计算的程序设计问
题中，计算机的操作对象以及它们之间的（ 2 ）和运算
等等的学科。
①结构 ②关系 ③逻辑存储 ④算法 ④数据元素
1、填空题、算法的 5个重要特性是、有穷性,确定性,可
行性,输入和输出。
5、作业
3、分析下面程序段的时间复杂度。
For (i=0; i<n; i++) { y=y+1;
For (j=0;j<=2*n;j++)
x++;}
数据结构
北京邮电大学自动化学院
杨福兴
电话,13331090202
E-mail,yangfx@sina.com
2004年 9月 13日
2北京邮电大学自动化学院
? 使用教材：
?严蔚敏 吴伟民 编著,数据结构（ C语言
版），清华大学出版社
? 参考书：
?1、曹桂琴 编著，数据结构基础，大连理工大
学出版社。
?2、晋良颖 编，数据结构，人民邮电出版社
?3,Bruno R.Preiss，数据结构与算法，电子
工业出版社
使用教材及参考书
3北京邮电大学自动化学院
,数据结构, 辅导老师名单
辅导老师 负责班级 电 话 E-mail 地点
张志霞 0215301～ 2 13811789470 zhixia1223@eyou.com 4－ 129
李维成 03507～ 9 13366767286 lisyan@126.com 4－ 129
杜伟 03501~2 13810984903 dwzhx-1@163.com 4－ 314
王松月 03503~4 13311509032 wsy5228@sina.com 4－ 314
4北京邮电大学自动化学院
课程教学目的
? 在计算机及其应用的各个领域中，都会用到各种
各样的数据结构，通过本课程使学生学会分析和
研究计算机加工对象的特性，选择合适的数据结
构和存储表示，以及编制相应的实现算法．
? 课程教学基本要求,本课程介绍各种最常用的数据
结构，阐述各种数据结构内涵的逻辑关系，讨论
它们在计算机中的存储表示，以及在这些数据结
构上的运算和实际的执行算法，并对算法的效率
进行简要的分析和讨论。
5北京邮电大学自动化学院
? 数据结构的研究不仅涉及到
? 计算机硬件 （特别是编码理论、存储装置和存取
方法）的研究范围，
? 而且和 计算机软件 的研究有着密切的关系，无论
是编译程序还是操作系统，都涉及到数据元素在
存储器中的分配问题。
? 在研究 信息检索时 也必须考虑如何组织数据，以
便查找和存取数据元素更为方便。
课程介绍
6北京邮电大学自动化学院
? 因此，可以认为 数据结构 是介于 数学、计算机硬件
和计算机软件 三者之间的一门核心课程。
? 程序＝算法＋数据结构
? 目前在我国,,数据结构, 已经不仅仅是计算机专
业的教学计划中的核心课程之一，而且是其它非计
算机专业的主要选修课程之一。
? 通过对这门课程的学习可增强选择合适的数据结构
与编写高效的程序的能力。
课程介绍
7北京邮电大学自动化学院
教学安排及考试
? 讲课学时,34学时
? 上机时间,5次（每次 2学时）
? 考试成绩计算：
?平时成绩（考勤,作业及上机） 30分
?考试（ 70分）
? 考查课和考试课分别考试，考查课在第 17周考
试，考试课按学校安排时间考试。
8北京邮电大学自动化学院
目录
? 第 1章 绪论
? 第 2章 线性表
? 第 3章 栈和队列 第 4章 串
? 第 5章 数组和广义表
? 第 6章 树和二叉树
? 第 7章 图
? 第 8章 查找
? 第 9章 内部排序
? 第 10章 文件
9北京邮电大学自动化学院
? 计算机的应用已不再局限于科学计算，而更多地
用于控制、管理及数据处理等 非数值计算的处理
工作 。
? 与此对应，计算机加工处理的对象由纯粹的数值
发展到 字符、表格和图像 等各种具有一定结构的
数据。
? 为了编写出一个“好”的程序，必须分析 待处理
的对象的特征以及各对象之间存在的关系,这就
是“数据结构”这门学科形成和发展的背景。
第一章 绪 论
第一章 绪 论
10北京邮电大学自动化学院
? 一般来说，用计算机解决一个具体问题时，大致需要经多下
列几个步骤：
?首先要从具体问题抽象出一个适当的数学模型
?然后设计一个解此数学模型的算法，
?最后编出程序、进行测试、调整直至得到最终解答。
? 寻求数学模型的实质是分析问题，从中提取操作的对象，并
找出这些操作对象之间含有的关系，然后用数学的语言加以
描述。
? 然而，更多的非数值问题无法用数学方程描述。什么是数据
结构呢？先看以下几个例子。
1.1 什么是数据结构
11北京邮电大学自动化学院
0 0 1 高等数学 樊映川 S 0 1
0 0 2 理论力学 罗远祥 L 0 1
0 0 3 高等数学 华罗庚 S 0 1
0 0 4 线性代数 栾汝书 S 0 2
…… …… …… ……
书目文件
按书名 按作者名 按分类号
高等数学 001, 003 ……
理论力学 002, ……,.
线性代数 004, ……
…… ……,.
樊映川 001,…
华罗庚 002,…,
栾汝书,…,
……, ……,
L 002,…
S 0 0 1,0 0 3,
…… ……
索引表
线性表
例 1 书目自动检索系统
登录号：
书名：作者名：
分类号：出版单位：
出版时间：价格：
书目卡片
12北京邮电大学自动化学院
树
……..……..
…..,…..,…..,…...
例 2 人机对奕问题
13北京邮电大学自动化学院
? 对于一个多叉路口，设计一
个交通信号灯的管理系统。
? 首先需要分析一下所有车辆
的行驶路线的冲突问题。
? 这个问题可以归结为对车辆
的可能行驶方向作某种分
组，对分组的要求是使任一
个组中各个方向行驶的车辆
可以同时安全行驶而不发生
碰撞。
C
E
D
A
B
例 3 多叉路口交通灯管理问题
14北京邮电大学自动化学院
可通行方向
?A?B A?C A ?D
?B ?A B?C B?D
?D?A D?B D ?C
?E ?A E?B E?C E?D
C
E
D
A
B
例 3多叉路口交通灯管理问题
15北京邮电大学自动化学院
有些通行方向显然不能同时进行，相应的结点间画一条连线。
AB AC AD
BA BC BD
DA D B DC
EA EB EC ED
图 1.2 交叉路口的图示模型
C
E
D
A
B
图
16北京邮电大学自动化学院
? 把图 1.2中的结点进行分组，使得有结点相连的结点不
在同一个组里。
? 地图着色问题
? 如果把上图中的一个结点理解为一个国家,结点之间
的连线看作两国有共同边界，上述问题 就变成著名的
“着色问题”,即求出最少要几种颜色可将图中所有
国家着色，使得任意两个相邻的国家颜色都不相同。
? 通过上面的分析，我们就获得了该交通管系统的数学
模型。下面就可以着手进行算法的设计。
例 3多叉路口交通灯管理问题
17北京邮电大学自动化学院
算法设计
? 2.,贪心法”
? while 有结点未着色；
? { 选择一种新颜色；
? 在未着色的结点中,给尽可能多的彼此结点之间没有边
点着色；
? }
? 1,对 n个结点，逐个测试其所有组合；
例 3多叉路口交通灯管理问题
18北京邮电大学自动化学院
AB AC AD
BA BC BD
DA D B DC
EA EB EC ED
图 1.2 交叉路口的图示模型
图
AB AC AD
BA BC BD
DA DB DC
EA EB EC ED
C
E
D
A
B
着色结果
19北京邮电大学自动化学院
? 把上面方法应用于图 1.2，得到下面的分组：
? 绿色,AB,AC,AD,BA,DC,ED
? 蓝色,BC,BD,EA
? 红色,DA,DB
? 白色,EB,EC
例 3多叉路口交通灯管理问题
20北京邮电大学自动化学院
? 综上三个例子，描述这类非数值计算问题的数学模型
不再是数学方程，而是诸如 表、树和图 之类的数据结
构。
? 因此，简单说来，数据结构是一门 研究非数值计算的
程序设计问题中 计算机的操作对象以及它们之间的关
系和操作等等的学科 。
? 数据结构就是研究数据的逻辑结构和物理结构它们之
间相互关系，并对这种结构定义相应的运算，而且确
保经过这些运算后所得到的新结构仍然是原来的结构
类型。
第一章 绪 论
21北京邮电大学自动化学院
? 数据 (Data):是对客观事物的符号表示，在计算机科
学中是指 所有能输入到计算机中并被计算机程序处
理的符号的总称。
? 对计算机科学而言，数据的含义极为广泛，如图
像、声音等都可以通过编码而归之于数据的范畴。
? 数据元素 (Data Element):是数据的基本单位，在计
算机程序中通常作为一个整体进行考虑和处理。
? 例如，例 1－ 2中的“树”中的一个棋盘格局，例 1
－ 3中的“图”中的一个园圈都被称为一个数据元
素。
1.2 基本概念和术语
22北京邮电大学自动化学院
? 一个数据元素可由若干个数据项组成。例如，例 1－ 1中一
本书的书目信息为一个数据元素，而书目信息中的每一项
（如书名、作者名等）为一个数据项。
? 数据项是数据的不可分割的最小单位 。
? 数据对象 (Data Object),是性质相同的数据元素的集合，
是数据的一个子集。例如，整数数据对象是集合 N＝ {0，
± 1,± 2,… }，字母字符数据对象是集合 C＝ {A,B，
C,…} 。
? 数据结构 (Data Structure),是相互之间存在一种或多种
特定关系的数据元素的集合。
1.2 基本概念和术语
23北京邮电大学自动化学院
? 数据结构主要指逻辑结构和物理结构。 数据之间的相互关系称
为逻辑结构 。通常分为四类基本结构：
? 一、集合 结构中的数据元素除了同属于一种类型外，别无其
它关系。
? 二、线性结构 结构中的数据元素之间存在一对一的关系。
? 三、树型结构 结构中的数据元素之间存在一对多的关系。
? 四、图状结构或网状结构 结构中的数据元素之间存在多对多
的关系。
1.2 基本概念和术语
24北京邮电大学自动化学院
? 数据结构的形式定义为：数据结构是一个二元组：
? Data-Structure=(D,S)
? 其中,D是数据元素的有限集,S是 D上关系的有限
集。
? 例 复数的数据结构定义如下,Complex=(C,R)
? 其中,C是含两个实数的集合 ﹛ C1,C2﹜,分别表
示复数的实部和虚部。 R={P},P是定义在集合上的
一种关系 {〈 C1,C2〉 }。
1.2 基本概念和术语
25北京邮电大学自动化学院
? 数据结构在计算机中的表示称为数据的物理结构，又称为
存储结构。
? 数据结构在计算机中有两种不同的表示方法：
? 顺序表示和非顺序表示
? 由此得出两种不同的存储结构,顺序存储结构和链式存储
结构
? 顺序存储结构,用数据元素在存储器中的相对位置来表示
数据元素之间的逻辑关系。
? 链式存储结构,在每一个数据元素中增加一个存放地址的
指针,用此指针来表示数据元素之间的逻辑关系。
1.2 基本概念和术语
26北京邮电大学自动化学院
元素 n
……..
元素 i
……..
元素 2
元素 1L
o
Lo+m
Lo+(i-1)*m
Lo+（ n-1)*m
存储地址 存储内容
Loc(元素 i)=Lo+（ i-1)*m
顺序存储
27北京邮电大学自动化学院
1536元素 21400元素 1 1346元素 3 ∧元素 4
1345h
存储地址 存储内容 指针
1345 元素 1 1400
1346 元素 4 ∧
……, ……,,……,
1400 元素 2 1536
……, ……,,……,
1536 元素 3 1346
链式存储
h
28北京邮电大学自动化学院
数据的逻辑结构
数据的存储结构
数据的运算：检索、排序、插入、删除、修改等
线性结构
非线性结构
顺序存储
链式存储
线性表
栈
队
树形结构
图形结构
数据结构的三个方面：
1.2 基本概念和术语
29北京邮电大学自动化学院
? 数据类型,数据类型是一个值的集合和定义在这个值集范围
上的一组操作的总称。例如,C语言中的整型变量，其值集
为某个区间上的整数，定义在其上的操作为：加、减、乘、
除和取模等算术运算。
? 按“值”的不同特性，高级程序语言中的数据类型可分为：
? 一类是非结构的原子类型 。原子类型的值是不可分解的。
如,C语言中的基本类型（整型、实型、字符型和枚举类
型）、指针类型和空类型。
? 另一类是结构类型 。结构类型的值是由若干成分按某种结构
组成的。例如数组的值由若干分量组成。每个分量可以是整
数，也可以是数组等。
1.2 基本概念和术语
30北京邮电大学自动化学院
? 抽象数据类型：一个数学模型以及定义在该模型上的一组操
作。 抽象数据类型的定义仅取决于它的一组逻辑特性，而与
其在计算机内部如何表示和实现无关，即不论其内部结构如
何变化，只要它的数学特性不变，都不影响其外部的使用。
? 抽象数据类型实际上就是对该数据结构的定义。因为它定义
了一个数据的逻辑结构以及在此结构上的一组算法。
? 和数据结构的形式定义相对应，抽象数据类型可用三元组描
述如下,（Ｄ，Ｓ，Ｐ）
? D是数据对象,S是 D上的关系集,P是对 D的基本操作集。
1.2 基本概念和术语
31北京邮电大学自动化学院
? 本书采用以下格式定义抽象数据类型
? 抽象数据类型的定义：
ADT抽象数据类型名 {
数据对象,<数据对象的定义 >
数据关系,<数据逻辑关系的定义 >
基本操作,<基本操作的定义 >
? }ADT抽象数据类型名
? 基本操作的定义格式为：
基本操作名（参数表）
初始条件,<初始条件描述 >
? 操作结果,<操作结果描述 >
1.2 基本概念和术语
32北京邮电大学自动化学院
? 抽象数据类型三元组的定义：
? ADT Triplet{
? 数据对象,D={e1,e2,e3|e1,e2,e3?ElemSet}
? 数据关系,R1={<e1,e2>,<e2,e3>}
? 基本操作：
? InitTriplet(&T,v1,v2,v3)
? 操作结果,构造了三元组 T，元素 e1,e2和 e3分别赋以参数
v1,v2和 v3的值。
? } ADT Triplet
1.2 基本概念和术语
33北京邮电大学自动化学院
? ADT Triplet{
? 数据对象, D={e1,e2,e3|e1,e2,e3?ElemSet}
? 数据关系, R1={<e1,e2>,<e2,e3>}
? 基本操作,
? Get(T,i,&e)
? 初始条件,三元组 T已存在,1?i?3
? 操作结果,用 e返回 T的第 i元的值。
? } ADT Triplet
1.2 基本概念和术语
34北京邮电大学自动化学院
? 抽象数据类型 可通过固有数据类型来表示和实现，即利
用处理器中已存在的数据类型来说明新的结构，用已经
实现的操作来组合新的操作。
? 由于本书在高级程序设计语言的虚拟层次上讨论抽象数
据类型的表示和实现，并且讨论的数据结构及其算法主
要是面向读者，故采用 介于伪码和 C语言之间的类 C语
言作为描述工具,有时也用伪码描述一些只含抽象操作
的抽象算法。
? 这使得数据结构和算法的描述和讨论简明清晰，不拘泥
于 C语言的细节，又能容易转换成 C或者 C＋＋程序。
1.3 抽象数据类型的表示和实现
35北京邮电大学自动化学院
? 本书采用的类 C语言精选了 C语言的一个核心子集，同时作了
若干扩充，增强了语言的描述功能。以下对其作简要说明。
? （ 1）预定义常量和类型
? //函数结果状态代码
? #define TRUE 1 #define FLASE 0
? #define OK 1 #define ERROR 0
? #define INFEASIBLE -1 #define OVERFLOW -2
? // Status是函数的类型，其值是函数结果状态代码
? Typedef int Status;
1.3 抽象数据类型的表示和实现
36北京邮电大学自动化学院
? （ 2）数据结构的表示用类型定义（ typedef）描述。
数据元素类型约定为 Elemtype，由用户在使用该数据
类型时定义。
? （ 3）基本操作的算法都用以下形式的函数描述：
?函数类型 函数名 （函数参数表） {
?//算法说明
?语句序列
?}//函数名
1.3 抽象数据类型的表示和实现
37北京邮电大学自动化学院
? （ 4）赋值语句有
?简单赋值 变量名 =表达式；
?串值赋值 变量名 1=变量名 2=……= 表达式
?成组赋值 （变量名 1，。。。，） =（表达式
1，）
?交换赋值 变量名 ? 变量名
?条件赋值 变量名 =条件表达式？表达式 T：表
达式 F
1.3 抽象数据类型的表示和实现
38北京邮电大学自动化学院
? （ 5）选择语句有
? 条件语句 1 if（表达式）语句；
? 条件语句 2 if（表达式）语句； Else 语句
? 开关语句 1 switch(表达式 ) {
? case 值 1：语句序列 1； break;
? Default,语句序列 n+1;}
? 开关语句 2 switch{
? case 条件 1：语句序列 1； break;
? Default,语句序列 n+1;}
1.3 抽象数据类型的表示和实现
39北京邮电大学自动化学院
? （ 6）循环语句有
? For语句
? for（赋初值表达式；条件；修改表达式序列）语句；
? While 语句 while（条件）语句；
? do-while语句
? do {
? 语句序列 }while（条件）；
1.3 抽象数据类型的表示和实现
40北京邮电大学自动化学院
? （ 7）结束语句
?函数结束语句 return 表达式； return；
?Case结束语句 break;
?异常结束语句 exit(异常代码 )
? 8）输入和输出语句
? 输入语句 scanf([格式串 ]，变量 1，变量 n)；
? 输出语句 printf([格式串 ]，表达式 1，表达式 2)；
1.3 抽象数据类型的表示和实现
41北京邮电大学自动化学院
? （ 9）注释
? 单行注释 //文字序列
? （ 10）基本函数有
? 求最大值 max(表达式 1，表达式 n）
? 求最小值 min(表达式 1，表达式 n）
? 求绝对值 abs(表达式 )
? 求不足整数值 floor（表达式）
? 判定行结束 eoln（文件变量）或 eoln
1.3 抽象数据类型的表示和实现
42北京邮电大学自动化学院
? （ 11）逻辑运算约定
? 与运算 &&,对于 A &&B,当 A的值为 0时,不再对 B
求值。
? 或运算 ||,对于 A||B,当 A的值为非 0时,不再对 B
求值。
1.3 抽象数据类型的表示和实现
43北京邮电大学自动化学院
? 例题：抽象数据类型 Triplet的表示和实现
? //--------采用动态分配的顺序存储结构 ----------------
? Typedef ElemType *Triplet://initTriplet分配三个元素存
储空间
? //--------基本操作的函数原形说明 ----------------
? Status InitTriplet (Triplet &T,ElemType v1,ElemType
v2,ElemType v3）；
? //操作结果：构造了三元组 T，元素 e1,e2和 e3分别赋以参
数 v1,v2和 v3的值。
1.3 抽象数据类型的表示和实现
44北京邮电大学自动化学院
? Status DestroyTriplet (Triplet &T）；
?//操作结果：三元组 T被消除。
? Status Get (Triplet &T,int i,ElemType &e）；
?//初始条件：三元组 T已存在,1?i?3 。
? //操作结果：用 e返回 T的第 i元的值。
1.3 抽象数据类型的表示和实现
45北京邮电大学自动化学院
? //--------基本操作的实现 ----------------
? Status Get (Triplet &T,int i,ElemType &e） {
? // 1?i?3,用 e返回 T的第 i元的值。
? If (i<1||i>3) return ERROR;
? e=T [i-1] ；
? return OK;
? }//Get
? } ADT Triplet
1.3 抽象数据类型的表示和实现
46北京邮电大学自动化学院
? 算法是对特定问题求解步骤的一种描述，它是指令的有限序
列，每一条指令表示一个或多个操作。 1、算法有五个特性：
1.4 算法和算法分析
? （ 1）有穷性 一个算法必须总是在执行有穷步之后结束，且
每一步都在有穷时间内完成。
? （ 2）确定性 算法中每一条指令必须有确切的含义。不存在二
义性。且算法只有一个入口和一个出口。
? （ 3）可行性 一个算法是可行的。即算法描述的操作都是可以
通过已经实现的基本运算执行有限次来实现的。
? （ 4）输入 一个算法有零个或多个输入。
? （ 5）输出 一个算法有一个或多个输出。
47北京邮电大学自动化学院
? 评价一个好的算法有以下几个标准,
? （ 1） 正确性
? （ 2）可读性 算法应该好读。
? （ 3）健状性 算法应具有容错处理。当输入非法数据
时，算法应对其作出反应，而不是产生莫名其妙的输
出结果。
? （ 4）效率与存储量需求 效率是指算法执行的时
间；存储量需求指算法执行过程中所需要的最大存储
空间。
2,算法设计的要求
48北京邮电大学自动化学院
? 程序不含语法错误。
? 程序对于几组输入数据能够得出满足规格说
明的结果。
? 程序对于精心选择的典型、苛刻而带有刁难
性的几组输入数据能够得出满足规格说明的
结果。
? 程序对于一切合法的输入数据都能产生满足
规格说明的结果。
正确性（算法应满足具体问题的需求）
49北京邮电大学自动化学院
? 算法执行时间需要通过依据该算法编制的程序在计算机上运行时
所消耗的时间度量。度量一个程序的执行时间通常有两种方法。
? 事后统计的方法
?一是必须先运行依据算法编制的程序
?二是所得时间的统计量依赖于计算机的硬件、软件等环境
因素求出该算法的一个时间界限函数
? 事前分析估算的方法
?依据的算法选用何种策、问题的规模、书写的语言、编译
程序所产生的机器代码的质量、机器执行指令的速度。
? 所以，人们常常采用事前分析估算的方法。
3,算法效率的度量
50北京邮电大学自动化学院
? 使用绝对的时间单位衡量算法的效率是不合适的。 撇开这些
与计算机硬件软件有关的因素，可以认为一个特定算法的
“运行工作量”的大小，只依赖于 问题的规模 （通常用整数
量表示），或者说,它是问题规模的函数。
? 一个算法是由控制结构（顺序分支和循环三种）和原操作
（指固有数据类型的操作）构成的，则算法时间取决于两者
的综合效果。
? 为了便于比较同一问题的不同算法,通常的做法是，从算法
中选取一种对于研究问题（或算法类型）来说是基本操作的
原操作，以该基本操作重复执行的次数作为算法的时间量
度。
3,算法效率的度量
51北京邮电大学自动化学院
? 整个算法的执行时间与该基本操作（乘法）重复执行的次数
n3成正比，记为 T(n)=O(n3)
? for(i=1;i<=n;++i)
? for(j=1;j<=n;++j){ c[i][j]=0;
? for(k=1;k<=n;++k) c[i][j]+=a[i][k]*b[k][j];}
? 一般情况下，算法中基本操作重复执行的次数是问题规模 n
的某个函数 f(n),算法的时间度量记作 T(n)=O(f(n))
? 它表示随着问题规模 n的增加,算法执行时间的增长率和
f(n)的增长率相同,称作算法的渐进时间复杂度，简称时间
复杂度。
? 例 1，在如下所示的两个矩阵相乘的算法中，“乘法”运算是
“矩阵相乘问题”的基本操作。
52北京邮电大学自动化学院
? 显然，被称作问题的基本操作的原操作应是其重复执行次数
和算法的执行时间成正比的原操作，多数情况下它是最深层
循环内的语句中的原操作,它的执行次数和包含它的语句的
频度相同。
? 语句的频度是指的是该语句重复执行的次数。
? 例２ {++x;s=0;}
? 将 x自增看成是基本操作，则语句频度为 １,即 时间复杂度
为Ｏ (1)。
? 如果将 s=0也看成是基本操作，则语句频度为 ２,其 时间复
杂度仍为Ｏ (1)，即常量阶。
3,算法效率的度量
53北京邮电大学自动化学院
? 例３,for(i=1;i<=n;++i) {++x;s+=x;}
?语句频度为,2n
?其时间复杂度为,O(n)
?即时间复杂度为线性阶。
? 例４,for(i=1;i<=n;++i)
? for(j=1;j<=n;++j) {++x;s+=x;}
?语句频度为,2n2
?时间复杂度为,O(n2)
?即时间复杂度为平方阶。
3,算法效率的度量
54北京邮电大学自动化学院
? 定理：若 A(n)=amnm +am-1nm-1 +…+a 1n+a0是一个 m次多项
式，则 A(n)=O(nm)。证略。
? 例５ for(i=2;i<=n;++I)
? for(j=2;j<=i-1;++j) {++x;a[i,j]=x;}
? 语句频度为,1+2+3+…+n -2=(1+n-2) × (n-2)/2
? =(n-1)(n-2)/2 =n2-3n+2
?时间复杂度为 O(n2),
? 即此算法的时间复杂度为平方阶。
3,算法效率的度量
55北京邮电大学自动化学院
? 以下六种计算算法时间的多项式是最常用的。其关系为：
? O(1)<O(logn)<O(n)<O(nlogn) <O(n2)<O(n3)
? 指数时间的关系为：
? O(2n)<O(n!)<O(nn)
? 当 n取得很大时，指数时间算法
和多项式时间算法在所需时间上
非常悬殊。 因此，只要有人能将
现有指数时间算法中的任何一个
算法化简为多项式时间算法，那
就取得了一个伟大的成就。
3,算法效率的度量
56北京邮电大学自动化学院
? 有的情况下，算法中基本操作重复执行的次数还随问题
的输入数据集不同而不同。例如：
? Void bubble-sort(int a[],int n)
? for(I=n-1,change=TURE;I>1 && change;--I) {
? change=false; for(j=0;j<I;++j)
? if (a[j]>a[j+1]) { a[j] ←→a[j+1];change=TURE} }
? 最好情况,0次 最坏情况,1+2+3+…+n -1=n(n-1)/2
? 平均时间复杂度为,O(n2)
? 在本书以后各章节中讨论的时间复杂度，除特别指明
外，均指最坏情况下的时间复杂度。
3,算法效率的度量
57北京邮电大学自动化学院
? 类似于算法的时间复杂度，本书中以空间复杂
度作为算法所需存储空间的量度，记作,
? S(n)=O(f(n))
? 其中 n为问题的规模 (或大小 )。
? 一个上机执行的程序除了需要存储空间来寄存
本身所用指令、常数、变量和输入数据外，也
需要一些对数据进行操作的工作单元和存储一
些为实现计算所需信息的辅助空间。
4、算法的存储空间需求
58北京邮电大学自动化学院
4、复习提纲
? 1、理解数据、数据结构、存储结构
? 2、理解抽象数据类型及面向对象概念：数据类
型；数据抽象与抽象数据类型；用于描述数据结构
的语言
? 3、理解算法定义
? 4、掌握性能分析与度量（算法的性能标准；算法
的后期测试；算法的事前估计；空间复杂度度量；
时间复杂度度量；时间复杂度的渐进表示法；）
59北京邮电大学自动化学院
2、选择题。数据结构是一门研究非数值计算的程序设计问
题中，计算机的操作对象以及它们之间的（ 2 ）和运算
等等的学科。
①结构 ②关系 ③逻辑存储 ④算法 ④数据元素
1、填空题、算法的 5个重要特性是、有穷性,确定性,可
行性,输入和输出。
5、作业
3、分析下面程序段的时间复杂度。
For (i=0; i<n; i++) { y=y+1;
For (j=0;j<=2*n;j++)
x++;}
