数据结构及算法
? 课程名称,数据结构及算法
? 预修课程, C语言,高等数学
? 教材, 1.,数据结构, (C语言版 )清华大学出版社 1997
2.,数据结构题集, (C语言版 )清华大学出版社 1999
? 教师,徐镜春 xjcsj01@dlc.zju.edu.cn
关于习题与实验题
? 教材中习题放在每章结束,但学生在每周都应该完成与上
课内容相应的部分小题
? 有精力的同学应该思考《数据结构题集》中未列为必做
的练习,这会有助于理解课程内容
? 习题包括理论习题和上机实验题
? 实验题要求用 C语言编写,并在计算机上调试通过
? 实验报告至少应包括
? 题目
? 算法步骤
? 源程序 (不太多时写在作业本上 )
? 运算结果及分析
? 调试过程与体会
第一章 绪论
? 1,1 什么是数据结构
? 1,2 基本概念和术语
? 1,3 抽象数据类型的表示与实现
? 1,4 算法和算法分析
? 1,4,1 算法
? 1,4,2 算法设计的要求
? 1,4,3 算法效率的度量
? 1,4,4 算法的存储空间需求
1.1 什么是 数据结构
? 计算机解决问题的步骤
? 实际问题 --- 数学模型 ---算法 ---程序 --- 结果
? 工程师 数学家 程序员
? 计算机的用途
◆ 科学计算 (数值运算 ),解方程 (组 ),函数求
值,概率统计等
◆ 非数值运算, 字符,表格,图象,声音等
计算机的用途 ---数值运算
◆ 水库大坝的应力计算
◆ 预报人口增长
◆ 天气预报
计算机的用途 ---非数值运算
? 书目检索系统
001 高等数学 刘金明 S01 …
002 线性代数 华罗庚 X01 …
003 高等数学 徐汉洋 S01 …
004 普通物理 罗志高 W01 …
… … … … …
高等数学 001,003
线性代数 002
普通物理 004
… …
刘金明 001
华罗庚 002
罗志高 004
… …
X 002
S 001,003
… …
多叉路口的交通灯管理问题
? 有连线的节点用不
同的颜色标记,表
示不能同时通行,
? 要求使用的颜色数
尽可能少,以使减
少等待时间,
? 图论中的四色问题,
多叉路口的交通灯管理问题
? 不能同时通行的通路用连线把它们连起
来,它们有,
? A->B 通路, CA,BD,BC
? A->D 通路, CB,BC
? B->C 通路, AB,AD
? B->D 通路, AB,CB
? C->A 通路, AB
? C->B 通路, BD,AD
计算机的用途 ---非数值运算
? 计算机与人对奕问题
数据结构的定义
? 描述非数值计算问题的模型是 ---
? 如表、树、图之类的数据结构
? 数据结构 是 ---
? 研究计算机的 操作对象 (数据 )以及它们之间
的 关系和操作 等的学科,
学科《数据结构》在计算机科
学中所处的地位
? 综合性的专业基础课
1.2 基本概念和术语
? 数据,计算机程序处理的符号的总称 。
? 数据元素,数据的基本单位 。
? 通常作为一个整体进行处理 。
? 数据项,数据的不可分割的最小单位 。
? 一个数据元素可以由若干个数据项构成 。
? 数据对象,性质相同的数据元素的集合 。
? 数据结构,相互间存在一种或多种关系
的数据元素的集合 。
数据元素相互关系 -----
称为“结构”
? 四类基本结构
? 集合
? 线性结构
? 树型结构
? 图状结构（网状结构）
数据结构的数学定义
? 数据结构是一个二元组
? Data_Structure = (D,S)
D – 数据元素的有限集合
S – 定义在 D上的关系的有限集合
? 例如
? Complex = (C,R)
? C = {(c1,c2)| c1,c2是实数 }
? R = {P|P是定义在 C上的关系,<c1,c2>表示 c1是
实部,c2是 虚部 }
逻辑结构和物理结构
? 逻辑结构, 数据元素之间的逻辑关系
? 物理结构, 数据结构在计算机中的表示,
又称存储结构
? 算法的设计取决于选定的逻辑结构
? 算法的实现依赖于采用的存储结构
数据类型与抽象的数据类型
? 数据类型（ Data Type）：
? 值的集合以及定义在这个集合上的一组操作。
? 例如, C语言中的整数类型
? 抽象数据类型 (ADT)
? 数学模型以及定义在该模型上的一组操作 。
? 与其在计算机中的表示和实现无关 。
? ADT可用三元组表示,（ D,S,P）
? D – 数据对象 ; S – D上的关系 ; P – 对 D
的基本操作集
抽象数据类型的定义格式：
? ADT抽象数据类型名 {
数据对象：＜数据对象的定义＞
数据关系：＜数据关系的定义＞
基本操作：＜基本操作的定义＞
｝ ADT抽象的数据类型名
? 基本操作的定义格式为：
基本操作名（参数表）
初始条件：＜初始条件描述＞
操作结果：＜操作结果描述＞
抽象数据类型三元组的定义
? 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的值 。
抽象数据类型三元组的定义 (2)
– DestroyTriplet(&T)
– 初始条件, 三元组 T已经存在 。
– 操作结果, 销毁三元组 T。
– Get(T,i,&e)
– 初始条件, 三元组 T已经存在,1<=i<=3。
– 操作结果, 用 e返回三元组 T的第 i个元素 。
– Put(&T,i,e)
– 初始条件, 三元组 T已经存在,1<=i<=3。
– 操作结果, 用 e值取代三元组 T的第 i个元素 。
抽象数据类型三元组的定义 (3)
– IsAscending(T)
– 初始条件, 三元组 T已经存在 。
– 操作结果, 如果三元组 T的三个元素按升序排列,
则返回 TRUE; 否则返回 FALSE。
– IsDescending(T)
– 初始条件, 三元组 T已经存在 。
– 操作结果, 如果三元组 T的三个元素按降序排列,
则返回 TRUE; 否则返回 FALSE。
抽象数据类型三元组的定义 (4)
– Max(T,&e)
– 初始条件, 三元组 T已经存在,。
– 操作结果, 用 e返回三元组 T的最大值 。
– Min(T,&e)
– 初始条件, 三元组 T已经存在,。
– 操作结果, 用 e返回三元组 T的最小值 。
｝ ADT Triplet
1.3抽象数据类型的表示与实现
? 类 C语言 （ 作了扩充和修改 ） 的表示
? 如：预定义常量和类型
? ＃ define TRUE 1
＃ define FALSE 0
＃ define OK 1
＃ define ERROR 0
＃ define INFEASIBLE -1
＃ define OVERFLOW -2
typedef int Status
三元组基本操作实现 ---举例
Status Get(Triple T,int i,Elemtype *e)
// 初始条件, 三元组 T已经存在,1<=i<=3。
// 操作结果, 用 e返回三元组 T的第 i个元素 。
{
if (i<1 || i>3) return ERROR;
*e=T[i-1];
return OK;
}
1.4 算法和算法分析,1.4.1 算法
? 算法 （ Algorithm）,对特定问题求解步骤
的一种描述,
? 算法的五个重要特性：
（ 1） 有穷性
（ 2） 确定性
（ 3） 可行性
（ 4） 输入
（ 5） 输出
算法举例 ----气泡排序算法
? 初始条件,n个待排序的数 a[0]-a[n-1]
? 结果：排序后 a[0]-a[n-1]从小到大排列
（ 1） 置标记 change=TRUE;
（ 2） i 从 n-1直到 i=2做 （ 3） -（ 6） 步
（ 3） change = FALSE;
（ 4） j从 0直到 j=i-1做 （ 5）
（ 5） 若 a[j]>a[j+1]则交换它们并置 change=TRUE
（ 6) 若 change = FALSE则结束
（ 7） 算法结束
冒泡排序算法（ 1）
1） i 从 n-1直到 i=2做（ 2） -（ 3）步
2） j从 0直到 j=i-1做（ 3）
3）若 a[j]>a[j+1]则交换它们
4）算法结束
void bb_sort(int a[],int n){
for (i=n-1; i>1; --i) {
for (j= 0; j<i; ++j)
if(a[j] > a[j+1]){ a[j] ←→ a[j+1]; }
}
} //bb_sort
1.4.2 算法设计的要求
? 算法应达到的目标
（ 1） 正确性
（ 2） 可读性
（ 3） 健壮性
（ 4） 效率与低存贮量
1.4.3 算法效率的度量
（ 1) 事后统计法
（ 2） 事前分析估算法
? 算法的 时间复杂度, 基本操作重复执行的次
数 。
? 它是问题规模 n的某个函数 f(n)：
? T(n) = O(f(n))
例如：两个 nxn矩阵相乘
? 两个 nxn矩阵相乘的算法中乘法运算是基本操
作，其重复执行的次数为 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];
}
平均 时间复杂度 ---时间复杂度
与输入数据有关时采用
采用 平均时间复杂度 或 最坏时间复杂度
例如, (p.16 ) 气泡排序算法,
Void bubble_sort(int a[],int n){
for (i=n-1,change = TRUE; 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;}
} }//bubble_sort
渐近时间复杂度 (阶 )与 语句频
度
? 时间复杂度 只考虑对于问题规模的 增长率
? 在难以精确计算基本操作执行次数时,仅需
要求增长率 (或阶 )即可,
? 阶,for(i=2; i<=n;++i)
for(j=2; j<=i;++j){++x; a[i,j] = x;}
++x的执行次数关于 n 的增长率是 O(n2)
? 语句频度
? (n-1) + (n-2) + …… + 2 + 1 = (n -1)n/2
通常涉及的增长率（阶）
（从大到小）
? nn n!
? cn(c>1),2n,3n
? nc(c>1),n2,n3
? nlog(n),nlog2(n)
? nr(0<r<1.0)
? log(n),log2(n)
实验要求与习题
? 理论习题 1.1,1.2,1.5,1.6,1.8,
1.10,1.12
? 实验题, 1.9并通过上机验证结果,
1.16,1.18
? 课程名称,数据结构及算法
? 预修课程, C语言,高等数学
? 教材, 1.,数据结构, (C语言版 )清华大学出版社 1997
2.,数据结构题集, (C语言版 )清华大学出版社 1999
? 教师,徐镜春 xjcsj01@dlc.zju.edu.cn
关于习题与实验题
? 教材中习题放在每章结束,但学生在每周都应该完成与上
课内容相应的部分小题
? 有精力的同学应该思考《数据结构题集》中未列为必做
的练习,这会有助于理解课程内容
? 习题包括理论习题和上机实验题
? 实验题要求用 C语言编写,并在计算机上调试通过
? 实验报告至少应包括
? 题目
? 算法步骤
? 源程序 (不太多时写在作业本上 )
? 运算结果及分析
? 调试过程与体会
第一章 绪论
? 1,1 什么是数据结构
? 1,2 基本概念和术语
? 1,3 抽象数据类型的表示与实现
? 1,4 算法和算法分析
? 1,4,1 算法
? 1,4,2 算法设计的要求
? 1,4,3 算法效率的度量
? 1,4,4 算法的存储空间需求
1.1 什么是 数据结构
? 计算机解决问题的步骤
? 实际问题 --- 数学模型 ---算法 ---程序 --- 结果
? 工程师 数学家 程序员
? 计算机的用途
◆ 科学计算 (数值运算 ),解方程 (组 ),函数求
值,概率统计等
◆ 非数值运算, 字符,表格,图象,声音等
计算机的用途 ---数值运算
◆ 水库大坝的应力计算
◆ 预报人口增长
◆ 天气预报
计算机的用途 ---非数值运算
? 书目检索系统
001 高等数学 刘金明 S01 …
002 线性代数 华罗庚 X01 …
003 高等数学 徐汉洋 S01 …
004 普通物理 罗志高 W01 …
… … … … …
高等数学 001,003
线性代数 002
普通物理 004
… …
刘金明 001
华罗庚 002
罗志高 004
… …
X 002
S 001,003
… …
多叉路口的交通灯管理问题
? 有连线的节点用不
同的颜色标记,表
示不能同时通行,
? 要求使用的颜色数
尽可能少,以使减
少等待时间,
? 图论中的四色问题,
多叉路口的交通灯管理问题
? 不能同时通行的通路用连线把它们连起
来,它们有,
? A->B 通路, CA,BD,BC
? A->D 通路, CB,BC
? B->C 通路, AB,AD
? B->D 通路, AB,CB
? C->A 通路, AB
? C->B 通路, BD,AD
计算机的用途 ---非数值运算
? 计算机与人对奕问题
数据结构的定义
? 描述非数值计算问题的模型是 ---
? 如表、树、图之类的数据结构
? 数据结构 是 ---
? 研究计算机的 操作对象 (数据 )以及它们之间
的 关系和操作 等的学科,
学科《数据结构》在计算机科
学中所处的地位
? 综合性的专业基础课
1.2 基本概念和术语
? 数据,计算机程序处理的符号的总称 。
? 数据元素,数据的基本单位 。
? 通常作为一个整体进行处理 。
? 数据项,数据的不可分割的最小单位 。
? 一个数据元素可以由若干个数据项构成 。
? 数据对象,性质相同的数据元素的集合 。
? 数据结构,相互间存在一种或多种关系
的数据元素的集合 。
数据元素相互关系 -----
称为“结构”
? 四类基本结构
? 集合
? 线性结构
? 树型结构
? 图状结构（网状结构）
数据结构的数学定义
? 数据结构是一个二元组
? Data_Structure = (D,S)
D – 数据元素的有限集合
S – 定义在 D上的关系的有限集合
? 例如
? Complex = (C,R)
? C = {(c1,c2)| c1,c2是实数 }
? R = {P|P是定义在 C上的关系,<c1,c2>表示 c1是
实部,c2是 虚部 }
逻辑结构和物理结构
? 逻辑结构, 数据元素之间的逻辑关系
? 物理结构, 数据结构在计算机中的表示,
又称存储结构
? 算法的设计取决于选定的逻辑结构
? 算法的实现依赖于采用的存储结构
数据类型与抽象的数据类型
? 数据类型（ Data Type）：
? 值的集合以及定义在这个集合上的一组操作。
? 例如, C语言中的整数类型
? 抽象数据类型 (ADT)
? 数学模型以及定义在该模型上的一组操作 。
? 与其在计算机中的表示和实现无关 。
? ADT可用三元组表示,（ D,S,P）
? D – 数据对象 ; S – D上的关系 ; P – 对 D
的基本操作集
抽象数据类型的定义格式：
? ADT抽象数据类型名 {
数据对象：＜数据对象的定义＞
数据关系：＜数据关系的定义＞
基本操作：＜基本操作的定义＞
｝ ADT抽象的数据类型名
? 基本操作的定义格式为：
基本操作名（参数表）
初始条件：＜初始条件描述＞
操作结果：＜操作结果描述＞
抽象数据类型三元组的定义
? 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的值 。
抽象数据类型三元组的定义 (2)
– DestroyTriplet(&T)
– 初始条件, 三元组 T已经存在 。
– 操作结果, 销毁三元组 T。
– Get(T,i,&e)
– 初始条件, 三元组 T已经存在,1<=i<=3。
– 操作结果, 用 e返回三元组 T的第 i个元素 。
– Put(&T,i,e)
– 初始条件, 三元组 T已经存在,1<=i<=3。
– 操作结果, 用 e值取代三元组 T的第 i个元素 。
抽象数据类型三元组的定义 (3)
– IsAscending(T)
– 初始条件, 三元组 T已经存在 。
– 操作结果, 如果三元组 T的三个元素按升序排列,
则返回 TRUE; 否则返回 FALSE。
– IsDescending(T)
– 初始条件, 三元组 T已经存在 。
– 操作结果, 如果三元组 T的三个元素按降序排列,
则返回 TRUE; 否则返回 FALSE。
抽象数据类型三元组的定义 (4)
– Max(T,&e)
– 初始条件, 三元组 T已经存在,。
– 操作结果, 用 e返回三元组 T的最大值 。
– Min(T,&e)
– 初始条件, 三元组 T已经存在,。
– 操作结果, 用 e返回三元组 T的最小值 。
｝ ADT Triplet
1.3抽象数据类型的表示与实现
? 类 C语言 （ 作了扩充和修改 ） 的表示
? 如：预定义常量和类型
? ＃ define TRUE 1
＃ define FALSE 0
＃ define OK 1
＃ define ERROR 0
＃ define INFEASIBLE -1
＃ define OVERFLOW -2
typedef int Status
三元组基本操作实现 ---举例
Status Get(Triple T,int i,Elemtype *e)
// 初始条件, 三元组 T已经存在,1<=i<=3。
// 操作结果, 用 e返回三元组 T的第 i个元素 。
{
if (i<1 || i>3) return ERROR;
*e=T[i-1];
return OK;
}
1.4 算法和算法分析,1.4.1 算法
? 算法 （ Algorithm）,对特定问题求解步骤
的一种描述,
? 算法的五个重要特性：
（ 1） 有穷性
（ 2） 确定性
（ 3） 可行性
（ 4） 输入
（ 5） 输出
算法举例 ----气泡排序算法
? 初始条件,n个待排序的数 a[0]-a[n-1]
? 结果：排序后 a[0]-a[n-1]从小到大排列
（ 1） 置标记 change=TRUE;
（ 2） i 从 n-1直到 i=2做 （ 3） -（ 6） 步
（ 3） change = FALSE;
（ 4） j从 0直到 j=i-1做 （ 5）
（ 5） 若 a[j]>a[j+1]则交换它们并置 change=TRUE
（ 6) 若 change = FALSE则结束
（ 7） 算法结束
冒泡排序算法（ 1）
1） i 从 n-1直到 i=2做（ 2） -（ 3）步
2） j从 0直到 j=i-1做（ 3）
3）若 a[j]>a[j+1]则交换它们
4）算法结束
void bb_sort(int a[],int n){
for (i=n-1; i>1; --i) {
for (j= 0; j<i; ++j)
if(a[j] > a[j+1]){ a[j] ←→ a[j+1]; }
}
} //bb_sort
1.4.2 算法设计的要求
? 算法应达到的目标
（ 1） 正确性
（ 2） 可读性
（ 3） 健壮性
（ 4） 效率与低存贮量
1.4.3 算法效率的度量
（ 1) 事后统计法
（ 2） 事前分析估算法
? 算法的 时间复杂度, 基本操作重复执行的次
数 。
? 它是问题规模 n的某个函数 f(n)：
? T(n) = O(f(n))
例如：两个 nxn矩阵相乘
? 两个 nxn矩阵相乘的算法中乘法运算是基本操
作，其重复执行的次数为 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];
}
平均 时间复杂度 ---时间复杂度
与输入数据有关时采用
采用 平均时间复杂度 或 最坏时间复杂度
例如, (p.16 ) 气泡排序算法,
Void bubble_sort(int a[],int n){
for (i=n-1,change = TRUE; 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;}
} }//bubble_sort
渐近时间复杂度 (阶 )与 语句频
度
? 时间复杂度 只考虑对于问题规模的 增长率
? 在难以精确计算基本操作执行次数时,仅需
要求增长率 (或阶 )即可,
? 阶,for(i=2; i<=n;++i)
for(j=2; j<=i;++j){++x; a[i,j] = x;}
++x的执行次数关于 n 的增长率是 O(n2)
? 语句频度
? (n-1) + (n-2) + …… + 2 + 1 = (n -1)n/2
通常涉及的增长率（阶）
（从大到小）
? nn n!
? cn(c>1),2n,3n
? nc(c>1),n2,n3
? nlog(n),nlog2(n)
? nr(0<r<1.0)
? log(n),log2(n)
实验要求与习题
? 理论习题 1.1,1.2,1.5,1.6,1.8,
1.10,1.12
? 实验题, 1.9并通过上机验证结果,
1.16,1.18
