算法与数据结构主讲人 樊希平教材
数据结构－ C语言描述? 耿国华等编著,西安电子科技大学出版社参考书
数据结构?(C语言版） 严蔚敏等编著,清华大学出版社网络资源教学网站：
http://web.nuist.edu.cn/courses/jsj/GD_jsj_
002b/
学习目标
学会分析数据对象特征，掌握数据组织方法和计算机的表示方法，以便为应用所涉及的数据选择适当的逻辑结构、存储结构及相应算法，初步掌握算法时间、
控件分析的技巧，培养良好的程序设计技能。
什么是数据结构（定义）
数据结构的内容
算法
算法描述的工具
对算法性能评价
关于学习数据结构第一章 绪论课题提出
计算机的处理对象多样化学生成绩表格学 号 姓 名 数据结构 系统结构 数学
1 20001 刘扬 89 69 67
2 20002 李平 70 83 89
3 20003 王方 86 81 78
4 20004 张策 69 69 78
5 20005 董立 79 89 68
6 20006 谢平 80 88 79
7 20007 高月 81 81 80
8 20008 刘平 89 85 87
9 20009 好园 86 80 84
选课单学号 课程号 时间 成绩
20001 DS2000
SX2000
2001,2
2000,9
78
87
20002 ART2000
DS2000
2002,2
2001,2
68
90
20003 SX2000
DS2000
2000,9
2001,2
87
78
20004 SX2000
ART2000
2000,9
2002,2
89
76
UNIX文件系统结构图
/ root
bin lib user etc
math ds sw yin tao xie
Stack.cppQueue.cpp Tree.cpp
在应用程序中涉及到各种各样的数据，
如何在计算机中组织、存储、传递数据，
需要讨论它们的归类及它们之间的关系，
从而建立相应的数据结构，依此实现软件功能。
综上,描述这类非数值计算问题的数学模型不是数学方程,而是树、表和图之类的数据结构。
因此从广义上讲,数据结构描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现,
1.1 什么是数据结构
数据
数据元素
数据对象
数据结构
数据类型
数据抽象与抽象数据类型基本概念和术语数据（ Data）
是信息的载体，是描述客观事物的数、
字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。
数值性数据
非数值性数据数据元素 （ Data Element）
数据的 基本单位 。在计算机程序中常作为一个整体进行考虑和处理。
有时一个 数据元素 可以由若干 数据项 (Data Item)组成。 数据项 是具有独立含义的 最小标识单位 。
数据元素又称为元素、结点、记录数据项 (Data Item)
姓名俱乐部名称出生日期年 月 日入队日期职位业绩数据对象 (data object)
具有相同性质的数据元素的集合。
整数数据对象
N = { 0,?1,?2,… }
字母字符数据对象
C={ ‘A’,‘B’,‘C’,… ‘F’ }
数据 数据对象 数据元素 数据项子集 其一 子项数据结构 （ Data Structure）
形式定义：
某一 数据对象 的所有数据成员及成员之间的关系。记为：
Data_Structure = {D,S}
其中,D 是某一数据对象,S
是该对象中所有数据成员之间的关系的有限集合。
数据类型 （ Data Type）
一组性质相同的值集合以及定义在这个集合上的一组操作的总称。
高级语言中的数据类型。
C语言中的整型
（ 1）取值范围；
（ 2）可进行的运算原子类型结构类型整型、字符型、浮点型等数组、结构体、自定义类型等抽象数据类型 ( Abstract Data Type)
是指一个数学模型以及定义在此数学模型上的一组操作
数据结构 +定义在此数据结构上的一组操作 = 抽象数据类型
例如：矩阵 +（ 求转置,加,乘,
求逆,求本征值 ）
构成一个矩阵的抽象数据类型面向对象程序设计观念 类，包含数据和操作栈、队列、树、图字符串、窗口、列表框抽象数据类型的描述
抽象数据类型可用（ D,S,P）三元组表示其中,D是数据对象,S是 D上的关系集,P是对 D的基本操作集 。
ADT 抽象数据类型名 {
数据对象,〈 数据对象的定义 〉
数据关系,〈 数据关系的定义 〉
基本操作,〈 基本操作的定义 〉
} ADT 抽象数据类型名其中,数据对象,数据关系用伪码描述；基本操作定义格式为基本操作名 （ 参数表 ）
初始条件,〈 初始条件描述 〉
操作结果,〈 操作结果描述 〉
基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以 &打头,除可提供输入值外,还将返回操作结果 。
,初始条件,描述了操作执行之前数据结构和参数应满足的条件,若不满足,则操作失败,
并返回相应出错信息 。
,操作结果,说明了操作正常完成之后,数据结构的变化状况和应返回的结果 。 若初始条件为空,则省略之 。
抽象数据类型的表示和实现
抽象数据类型可以通过固有数据类型 (高级编程语言中已实现的数据类型 )来实现
抽象数据类型 类 class
数据对象 数据成员
基本操作 成员函数 (方法 )
在 C++中,类的成分 (数据成员和成员函数 )可以有三种访问级别
Private 私有成分 （ 只允许类的成员函数进行访问 ）
protected 保护成分 （ 只允许类的成员函数及其子孙类进行访问 ）
public 公有成分 （ 允许类的成员函数,类的实例及其子孙类,子孙类的实例进行访问 ）
1.2 数据结构的内容
逻辑结构
存储结构
运算集合数据的逻辑结构
从逻辑关系上描述数据，与数据的存储无关；
从具体问题抽象出来的数据模型；
与数据元素本身的形式、内容无关；
与数据元素的相对位置无关。
四个基本结构
集合
线性结构
树形结构
网状结构数据的逻辑结构分类
线性结构
线性表、栈、队、字符串、数组、
广义表
非线性结构
树
图（或网络）
bin dev etc lib user
2
1
14131211
2
3 4
6 7 8 9 10 3
1 5
8
7
10
11
9
987
4 5 6
62 3 13
1
5
线性结构树形结构树 二叉树 二叉排序树堆结构
12
3 5 4 8
7
11
10
2
9
16
1 2
5
6
4
3
1 2
5 4
3611
33
18
14
6
6
519 21
图结构 网络结构数据的存储结构（物理结构）
数据结构在计算机中的表示。
数据的存储结构依赖于计算机语言。
顺序存储表示
链接存储表示
索引存储表示
散列存储表示运算集合
定义在一定数据集上的操作。
例：职工工资表
逻辑结构－线性表
存储结构－顺序存储
操作（运算）集合－增加、修改、
删除、查找、统计等运算集合依赖于数据集、逻辑结构、存储结构和操作需求。
1.3 算法
定义,为了解决某类问题而规定的一个有限长的操作序列 。
特性：
有穷性 算法在执行有穷步后能结束
确定性 每步定义都是确切、无歧义
可行性 每一条运算应足够基本
输入 有 0个或多个输入
输出 有一个或多个输出算法设计要求：正确性、可读性、健壮性、高效性
例子,选择排序
问题,递增排序
解决方案,逐个选择最小数据
算法框架：
for ( int i = 0; i < n-1; i++ ) {//n-1趟从 a[i]检查到 a[n-1];
若最小整数在 a[k],交换 a[i]与 a[k];
}
细化,Select Sort
void selectSort ( int a[ ],int n ) {
//对 n个整数 a[0],a[1],…,a[n -1]按递增顺序排序
for ( int i = 0; i < n-1; i++ ) {
int k = i;
//从 a[i]查到 a[n-1],找最小整数,在 a[k]
for ( int j = i+1; j < n; j++ )
if ( a[j] < a[k] ) k = j;
int temp = a[i]; a[i] = a[k]; a[k] = temp;
}
}
1.4 算法描述的工具
算法、语言和程序的关系
设计实现算法的步骤
类描述算法的语言选择程序是算法在计算机中的实现（与所用计算机及所用语言有关）
· 找出与求解有关的数据元素之间的关系（建立结构关系）。
· 确定在某一数据对象上所施加的运算。
·
·
· 设计实现求解的算法,并用程序语言加以描述。
预定义常量和类型
＃ define TRUE 1
＃ define FALSE 0
＃ define MAXSIZE 100
＃ define OK 1
＃ define ERROR 0
提高程序的可读性算法的函数形式表示
［数据类型］ 函数名（［形式参数及说明］）
{ 内部数据说明；
执行语句组；
} /*函数名 */
成组赋值
(<变量 1>,<变量 2>,<变量 3>,…,< 变量 k>) =
(<表达式 1>,<表达式 2>,<表达式 3>,…,< 表达式 k>);
<数组名 1>[下标 1][下标 2] = <数组名 2>[下标 1][下标 2];
简化表达
1.5 性能分析与度量算法的性能标准
正确性
可使用性
可读性
效率
健壮性算法的后期测试在算法中的某些部位插装时间函数 time ( ),
测定算法完成某一功能所花费时间
double start,stop;
time (&start);
int k = seqsearch (a,n,x);
time (&stop);
double runTime = stop - start;
printf (,%d%d\n ",n,runTime );
int seqsearch ( int a[ ],int n,int x ) {
//在 a[0],…,a[n -1]中搜索 x
int i = 0;
while ( i < n && a[i] != x )
i++;
if ( i == n ) return -1;
return i;
}
算法的事前估计
空间复杂度度量
存储空间的固定部分程序指令代码的空间，常数、简单变量、定长成分 (如数组元素、结构成分、对象的数据成员等 )变量所占空间
可变部分尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用空间、通过 new
和 delete命令动态使用空间时间复杂度度量
运行时间 = 算法中每条语句执行时间之和。
每条语句执行时间 = 该语句的执行次数（频度）
* 语句执行一次所需时间。
语句执行一次所需时间取决于机器的指令性能和速度和编译所产生的代码质量，很难确定。
设每条语句执行一次所需时间为单位时间，则一个算法的运行时间就是该算法中所有语句的频度之和。
作业
1.1 (1),(3),(4),(5),(10)；
1.3
数据结构－ C语言描述? 耿国华等编著,西安电子科技大学出版社参考书
数据结构?(C语言版） 严蔚敏等编著,清华大学出版社网络资源教学网站：
http://web.nuist.edu.cn/courses/jsj/GD_jsj_
002b/
学习目标
学会分析数据对象特征，掌握数据组织方法和计算机的表示方法，以便为应用所涉及的数据选择适当的逻辑结构、存储结构及相应算法，初步掌握算法时间、
控件分析的技巧，培养良好的程序设计技能。
什么是数据结构（定义）
数据结构的内容
算法
算法描述的工具
对算法性能评价
关于学习数据结构第一章 绪论课题提出
计算机的处理对象多样化学生成绩表格学 号 姓 名 数据结构 系统结构 数学
1 20001 刘扬 89 69 67
2 20002 李平 70 83 89
3 20003 王方 86 81 78
4 20004 张策 69 69 78
5 20005 董立 79 89 68
6 20006 谢平 80 88 79
7 20007 高月 81 81 80
8 20008 刘平 89 85 87
9 20009 好园 86 80 84
选课单学号 课程号 时间 成绩
20001 DS2000
SX2000
2001,2
2000,9
78
87
20002 ART2000
DS2000
2002,2
2001,2
68
90
20003 SX2000
DS2000
2000,9
2001,2
87
78
20004 SX2000
ART2000
2000,9
2002,2
89
76
UNIX文件系统结构图
/ root
bin lib user etc
math ds sw yin tao xie
Stack.cppQueue.cpp Tree.cpp
在应用程序中涉及到各种各样的数据，
如何在计算机中组织、存储、传递数据，
需要讨论它们的归类及它们之间的关系，
从而建立相应的数据结构，依此实现软件功能。
综上,描述这类非数值计算问题的数学模型不是数学方程,而是树、表和图之类的数据结构。
因此从广义上讲,数据结构描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现,
1.1 什么是数据结构
数据
数据元素
数据对象
数据结构
数据类型
数据抽象与抽象数据类型基本概念和术语数据（ Data）
是信息的载体，是描述客观事物的数、
字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。
数值性数据
非数值性数据数据元素 （ Data Element）
数据的 基本单位 。在计算机程序中常作为一个整体进行考虑和处理。
有时一个 数据元素 可以由若干 数据项 (Data Item)组成。 数据项 是具有独立含义的 最小标识单位 。
数据元素又称为元素、结点、记录数据项 (Data Item)
姓名俱乐部名称出生日期年 月 日入队日期职位业绩数据对象 (data object)
具有相同性质的数据元素的集合。
整数数据对象
N = { 0,?1,?2,… }
字母字符数据对象
C={ ‘A’,‘B’,‘C’,… ‘F’ }
数据 数据对象 数据元素 数据项子集 其一 子项数据结构 （ Data Structure）
形式定义：
某一 数据对象 的所有数据成员及成员之间的关系。记为：
Data_Structure = {D,S}
其中,D 是某一数据对象,S
是该对象中所有数据成员之间的关系的有限集合。
数据类型 （ Data Type）
一组性质相同的值集合以及定义在这个集合上的一组操作的总称。
高级语言中的数据类型。
C语言中的整型
（ 1）取值范围；
（ 2）可进行的运算原子类型结构类型整型、字符型、浮点型等数组、结构体、自定义类型等抽象数据类型 ( Abstract Data Type)
是指一个数学模型以及定义在此数学模型上的一组操作
数据结构 +定义在此数据结构上的一组操作 = 抽象数据类型
例如：矩阵 +（ 求转置,加,乘,
求逆,求本征值 ）
构成一个矩阵的抽象数据类型面向对象程序设计观念 类，包含数据和操作栈、队列、树、图字符串、窗口、列表框抽象数据类型的描述
抽象数据类型可用（ D,S,P）三元组表示其中,D是数据对象,S是 D上的关系集,P是对 D的基本操作集 。
ADT 抽象数据类型名 {
数据对象,〈 数据对象的定义 〉
数据关系,〈 数据关系的定义 〉
基本操作,〈 基本操作的定义 〉
} ADT 抽象数据类型名其中,数据对象,数据关系用伪码描述；基本操作定义格式为基本操作名 （ 参数表 ）
初始条件,〈 初始条件描述 〉
操作结果,〈 操作结果描述 〉
基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以 &打头,除可提供输入值外,还将返回操作结果 。
,初始条件,描述了操作执行之前数据结构和参数应满足的条件,若不满足,则操作失败,
并返回相应出错信息 。
,操作结果,说明了操作正常完成之后,数据结构的变化状况和应返回的结果 。 若初始条件为空,则省略之 。
抽象数据类型的表示和实现
抽象数据类型可以通过固有数据类型 (高级编程语言中已实现的数据类型 )来实现
抽象数据类型 类 class
数据对象 数据成员
基本操作 成员函数 (方法 )
在 C++中,类的成分 (数据成员和成员函数 )可以有三种访问级别
Private 私有成分 （ 只允许类的成员函数进行访问 ）
protected 保护成分 （ 只允许类的成员函数及其子孙类进行访问 ）
public 公有成分 （ 允许类的成员函数,类的实例及其子孙类,子孙类的实例进行访问 ）
1.2 数据结构的内容
逻辑结构
存储结构
运算集合数据的逻辑结构
从逻辑关系上描述数据，与数据的存储无关；
从具体问题抽象出来的数据模型；
与数据元素本身的形式、内容无关；
与数据元素的相对位置无关。
四个基本结构
集合
线性结构
树形结构
网状结构数据的逻辑结构分类
线性结构
线性表、栈、队、字符串、数组、
广义表
非线性结构
树
图（或网络）
bin dev etc lib user
2
1
14131211
2
3 4
6 7 8 9 10 3
1 5
8
7
10
11
9
987
4 5 6
62 3 13
1
5
线性结构树形结构树 二叉树 二叉排序树堆结构
12
3 5 4 8
7
11
10
2
9
16
1 2
5
6
4
3
1 2
5 4
3611
33
18
14
6
6
519 21
图结构 网络结构数据的存储结构（物理结构）
数据结构在计算机中的表示。
数据的存储结构依赖于计算机语言。
顺序存储表示
链接存储表示
索引存储表示
散列存储表示运算集合
定义在一定数据集上的操作。
例：职工工资表
逻辑结构－线性表
存储结构－顺序存储
操作（运算）集合－增加、修改、
删除、查找、统计等运算集合依赖于数据集、逻辑结构、存储结构和操作需求。
1.3 算法
定义,为了解决某类问题而规定的一个有限长的操作序列 。
特性：
有穷性 算法在执行有穷步后能结束
确定性 每步定义都是确切、无歧义
可行性 每一条运算应足够基本
输入 有 0个或多个输入
输出 有一个或多个输出算法设计要求：正确性、可读性、健壮性、高效性
例子,选择排序
问题,递增排序
解决方案,逐个选择最小数据
算法框架：
for ( int i = 0; i < n-1; i++ ) {//n-1趟从 a[i]检查到 a[n-1];
若最小整数在 a[k],交换 a[i]与 a[k];
}
细化,Select Sort
void selectSort ( int a[ ],int n ) {
//对 n个整数 a[0],a[1],…,a[n -1]按递增顺序排序
for ( int i = 0; i < n-1; i++ ) {
int k = i;
//从 a[i]查到 a[n-1],找最小整数,在 a[k]
for ( int j = i+1; j < n; j++ )
if ( a[j] < a[k] ) k = j;
int temp = a[i]; a[i] = a[k]; a[k] = temp;
}
}
1.4 算法描述的工具
算法、语言和程序的关系
设计实现算法的步骤
类描述算法的语言选择程序是算法在计算机中的实现（与所用计算机及所用语言有关）
· 找出与求解有关的数据元素之间的关系（建立结构关系）。
· 确定在某一数据对象上所施加的运算。
·
·
· 设计实现求解的算法,并用程序语言加以描述。
预定义常量和类型
＃ define TRUE 1
＃ define FALSE 0
＃ define MAXSIZE 100
＃ define OK 1
＃ define ERROR 0
提高程序的可读性算法的函数形式表示
［数据类型］ 函数名（［形式参数及说明］）
{ 内部数据说明；
执行语句组；
} /*函数名 */
成组赋值
(<变量 1>,<变量 2>,<变量 3>,…,< 变量 k>) =
(<表达式 1>,<表达式 2>,<表达式 3>,…,< 表达式 k>);
<数组名 1>[下标 1][下标 2] = <数组名 2>[下标 1][下标 2];
简化表达
1.5 性能分析与度量算法的性能标准
正确性
可使用性
可读性
效率
健壮性算法的后期测试在算法中的某些部位插装时间函数 time ( ),
测定算法完成某一功能所花费时间
double start,stop;
time (&start);
int k = seqsearch (a,n,x);
time (&stop);
double runTime = stop - start;
printf (,%d%d\n ",n,runTime );
int seqsearch ( int a[ ],int n,int x ) {
//在 a[0],…,a[n -1]中搜索 x
int i = 0;
while ( i < n && a[i] != x )
i++;
if ( i == n ) return -1;
return i;
}
算法的事前估计
空间复杂度度量
存储空间的固定部分程序指令代码的空间，常数、简单变量、定长成分 (如数组元素、结构成分、对象的数据成员等 )变量所占空间
可变部分尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用空间、通过 new
和 delete命令动态使用空间时间复杂度度量
运行时间 = 算法中每条语句执行时间之和。
每条语句执行时间 = 该语句的执行次数（频度）
* 语句执行一次所需时间。
语句执行一次所需时间取决于机器的指令性能和速度和编译所产生的代码质量，很难确定。
设每条语句执行一次所需时间为单位时间，则一个算法的运行时间就是该算法中所有语句的频度之和。
作业
1.1 (1),(3),(4),(5),(10)；
1.3
