数据结构
North China Electric Power University
Data Structure
华北电力大学计算机科学与工程系
Dept,of Computer Science&Engineering of North China Electric Power University
第一章 绪 论
★ 课程简介
★ 基本概念
★ 算法
★ 算法语言的说明
North China Electric Power University
开设本课程的必要性以及课程的特点：
1,计算机专业重要的专业基础课之一,
2,需要有关,程序设计语言,和,离散数学
”
的知识作为课程的基础,3,实践性较强,
North China Electric Power University
★ 课程简介算法 +数据结构 =程序 (Niklaus Wirth)
（ Algorithm+Data structure=Program)
程序设计：为计算机处理问题编写的一组指令。
算法：处理问题的策略。
数据结构：问题的数学模型。
程序设计的实质是数据的表示和数据处理,为此应提出问题的数学模型和设计相应的算法。
例如：桥梁结构的应力计算
（结构静力分析、线性代数方程）
例如：全球天气预报（环流模式方程）
North China Electric Power University
例如：预报人口增长率（微分方程）
例如：计算机对弈（对弈的规则和策略）
例如：酒店客房管理系统中的客房分配问题例如：铺设煤气管道问题
A
B
C
D
I
H
G
E
F
18.2
32.8
44.6
12.1 8.7
56.4
21.3 41.1
67.3
10.5
85.6
98.7
52.5 79.2
A
B
C
D
I
H
G
E
F
32.8 12.1 8.7
21.3 41.1 10.5
79.2
(a) 居民区示意图 (b) 铺设煤气管道设计图
North China Electric Power University
例如：图书馆的书目检索问题登录号 书名 作者 分类号 …
… … … … …
172832 离散数学 樊映川 S01 …
172833 理论力学 罗远祥 S01 …
172834 高等数学 华罗庚 S01 …
172835 线性代数 滦汝书 S02 …
… … … … …
书名 登录号
… …
高等数学 172832,
172834…
理论力学 172833…
线性代数 172835…
… …
作者 登录号
… …
樊映川 172832…
华罗庚 172834…
滦汝书 172835…
… …
类别 登录号
… …
L 172833…
S 172832,
172834…
… …
North China Electric Power University
★ 基本概念
1,数据,所有能输入到计算机中并为计算机程序处理的对象的集合。
2.数据元素,数据的基本单位，在程序中作为一个整体加以考虑和处理。
3.数据项,数据处理的最小单位。
980604 刘晔 女
1880 10
学号 姓名 性别年 月 日组合项 原子项出生日期
（学生情况）
North China Electric Power University
4.数据对象,性质相同的数据元素的集合。
5.数据的逻辑结构,对数据元素之间逻辑关系的描述。它可以用一个数据元素的集合和定义在这个集合上的若干关系来表示。
Data Structure=(D,S)
D:数据元素的集合 ; S:D上关系的集合
1）集合：集合中任何两个结点之间都没有逻辑关系，组织形式松散。
2）线性结构：元素之间存在着一对一的关系。依次排列形成一条,锁链,。
North China Electric Power University
3）树形结构：数据元素之间存在着一对多的关系，具有分支、层次特性。
4）图状结构：数据元素之间存在多对多的关系，元素之间互相缠绕，具有分支、
层次特性。
6.数据的存储结构,数据在计算机中的表示，包括数据元素的表示和关系的表示。
1）顺序存储方式（向量存储） 2）链式存储方式
3）索引存储方式 4）散列存储方式
North China Electric Power University
7.数据类型,一个值的集合和定义在这个值上的一组操作。
8.抽象数据类型,一个数学模型和定义在这个数学模型的一组操作。
特性数据抽象：用 ADT描述程序处理的实体时，强调的是其本质的特征，其完成的功能以及和外部的接口 。
数据封装：将实体的外部特性和其内部实现分离，并对外部用户隐藏其内部实现细节 。
ADT 抽象数据类型名 {
数据对象,<数据对象的定义 >
数据关系,<数据关系的定义 >
基本操作,<基本操作的定义 >
} ADT 抽象数据类型名
North China Electric Power University
例如,抽象数据类型复数的定义
ADT Complex {
数据对象,D={e1,e2|e1,e2∈Realset}
数据关系,R1={<e1,e2>|e1是复数的实数部分,e2是复数的虚数部分 }
基本操作,InitComplex(v1,v2)
DestroyComplex(Z)
GetReal(Z,realPart)
GetImag(Z,ImagPart)
Add(Z1,Z2,Sum)
Subtract(Z1,Z2,Difference)
Multiply(Z1,Z2,Product)
}
ADT Complex
注：对于数据成员完全相同的数据类型，如果给它们赋予不同的语义，
则可形成不同的抽象数据类型 。
North China Electric Power University
9.数据结构,按照某种逻辑结构组织的一组数据，
按一定的存储方式将它们映射到计算机的存储器中，并且在这些数据上定义了一个运算的集合，运算的结果保持原来的结构。
North China Electric Power University
1,研究数据元素之间的客观联系 。
2,研究具有某种逻辑关系的数据在计算机存储器内的存储方式。
3,研究如何在数据的各种结构 (逻辑的和物理的 )
的基础上对数据实施一系列有效的基本操作。
逻辑结构存储结构数据结构课程研究的主要内容算法
★ 算法算法,解决问题的方法和策略，指为解决一个或一类问题给出的一个确定的、有限长的操作序列。
分类：
1,程序设计语言描述的算法
2,伪语言算法
3,非形式算法（自然语言算法）
算法的特性,
1,有穷性
2,确定性
3,可行性
4,有输入
5,有输出
North China Electric Power University
算法设计的原则
1.正确性
a.程序中不含语法错误
b.程序对于几组给定的输入数据能得出满足要求的结果
c.程序对于精心选择的、典型的、苛刻的且带有刁难性的几组输入能得出满足要求的结果
d.程序对一切合法输入都能得出满足要求的结果
2.可读性,算法主要是为了人的阅读与交流，其次才是为了计算机执行，因此算法应该易于理解；另外，晦涩难懂的程序易于隐藏较多错误而难于调试
3.健壮性,当输入的数据非法时，算法应当恰当地做出反应或进行相应的处理，而不是产生莫名其妙的错误输出；并且处理错误的方法不应该始终段程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次进行处理
4.高效率和低存储量需求：
效率：指算法的执行时间存储量：算法执行过程中所需的最大存储空间两者都与问题的规模有关
North China Electric Power University
和算法执行时间相关的因素：
1.算法选用的策略
2.问题的规模
3.编写程序的语言
4.编译程序产生的机器代码的质量
5.计算机执行指令的速度一个特定算法的,运行工作量,的大小，只依赖于问题的规模（通常用整数量 n来表示），或者说它是问题规模的函数。
算法的复杂性复杂性,指实现或运行某一算法所需资源的多少。
时间复杂性空间复杂性人工复杂性 (指编程、调试等所需的人工 )
North China Electric Power University
算法的时间复杂性,假如随着问题规模 n的增长，
算法执行时间的增长率和 f(n)的增长率相同，则记作 T(n)=O(f(n))，称 T(n)为算法的时间复杂性。
算法时间复杂性的度量：
∵ 任何一个算法都是由一个控制结构和若干原子操作组成
∴ 算法的执行时间 =Σ 原操作 (i)的执行次数 *原操作 (i)的执行时间因为原操作的执行时间相对问题的规模 n而言是个常量，所以算法的执行时间与原操作执行次数之和成正比。
从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为时间复杂的依据。
这种衡量效率的办法所得出的不是时间量，而指一种增长趋势的度量，它与软、硬件无关，只揭示出算法本身执行效率的优劣。
North China Electric Power University
例如,k:=k+1 时间复杂度为 O(1)
例如,For i:=1 to n Do
k:=k+1 时间复杂度为 O(n)
例如,For i:=1 to n Do
For j:=1 to n Do
k:=k+1 时间复杂度为 O(n2)
例如,For i:=1 to n Do
For j:=1 to n Do
[ c[i,j]:=0;
For k:=1 to n Do
c[i,j]:=c[i,j]+a[i,k]*b[k,j];
] 时间复杂度为 O(n3)
North China Electric Power University
对于足够大的 n，存在下述关系：
O(log n)<O(n)<O(nlog n)<O(n2)<O(n3)<… <O(2n)<O(3n)<O(n!)
算法的空间复杂性,假如随着问题规模 n的增长，
算法执行所需存储量的增长率和 g(n)的增长率相同，则记作 S(n)=O(g(n))，称 S(n)为算法的空间复杂性。
算法的存储量：算法执行过程中所需的最大存储空间。
算法的存储空间
1.输入数据所占的空间
2.程序本身所占的空间
3.辅助变量所占的空间
North China Electric Power University
★ 类 Pascal语言说明类 Pascal语言来自对 Pascal语言的修改，它描述的算法是不能直接在机器上执行的程序过程。它与标准 Pascal的主要区别如下：
1,局部变量的说明可以省略 (但形参表中及函数类型的说明必须保留 )，重要的变量须在注解中说明其类型和作用。
2.算法可以写成过程或函数的形式。
Procedure 过程名 (参数表 )；
Begin
语句组；
End;
Function 过程名 (参数表 )；
Begin
语句组；
End;
注：除作为过程体和函数体标志之外的 Begin,End可用方括号代替
North China Electric Power University
3.分情形语句写成如下形式：
Case
<条件１ >,<语句组１ > ；
<条件２ >,<语句组２ > ；
<条件３ >,<语句组３ > ；
…,…
<条件ｎ >,<语句组ｎ > ；
else,<语句组ｎ +1 >
EndCase;
4.不含 goto 语句，增加以下两条语句,
1)出错处理语句,Error(字符串 )，其功能是终止它所在算法的执行，并回送表示出错信息的字符串。
2)返回语句,Return和 Return(表达式 )，其功能是终止过程的执行，在函数体中,Return(表达式 )终止函数的执行并将表达式的值回传给函数名。
5.在算法中任何处均可插入一对用花扩号扩起来的注释。
North China Electric Power University
North China Electric Power University
North China Electric Power University
Data Structure
华北电力大学计算机科学与工程系
Dept,of Computer Science&Engineering of North China Electric Power University
第一章 绪 论
★ 课程简介
★ 基本概念
★ 算法
★ 算法语言的说明
North China Electric Power University
开设本课程的必要性以及课程的特点：
1,计算机专业重要的专业基础课之一,
2,需要有关,程序设计语言,和,离散数学
”
的知识作为课程的基础,3,实践性较强,
North China Electric Power University
★ 课程简介算法 +数据结构 =程序 (Niklaus Wirth)
（ Algorithm+Data structure=Program)
程序设计：为计算机处理问题编写的一组指令。
算法：处理问题的策略。
数据结构：问题的数学模型。
程序设计的实质是数据的表示和数据处理,为此应提出问题的数学模型和设计相应的算法。
例如：桥梁结构的应力计算
（结构静力分析、线性代数方程）
例如：全球天气预报（环流模式方程）
North China Electric Power University
例如：预报人口增长率（微分方程）
例如：计算机对弈（对弈的规则和策略）
例如：酒店客房管理系统中的客房分配问题例如：铺设煤气管道问题
A
B
C
D
I
H
G
E
F
18.2
32.8
44.6
12.1 8.7
56.4
21.3 41.1
67.3
10.5
85.6
98.7
52.5 79.2
A
B
C
D
I
H
G
E
F
32.8 12.1 8.7
21.3 41.1 10.5
79.2
(a) 居民区示意图 (b) 铺设煤气管道设计图
North China Electric Power University
例如：图书馆的书目检索问题登录号 书名 作者 分类号 …
… … … … …
172832 离散数学 樊映川 S01 …
172833 理论力学 罗远祥 S01 …
172834 高等数学 华罗庚 S01 …
172835 线性代数 滦汝书 S02 …
… … … … …
书名 登录号
… …
高等数学 172832,
172834…
理论力学 172833…
线性代数 172835…
… …
作者 登录号
… …
樊映川 172832…
华罗庚 172834…
滦汝书 172835…
… …
类别 登录号
… …
L 172833…
S 172832,
172834…
… …
North China Electric Power University
★ 基本概念
1,数据,所有能输入到计算机中并为计算机程序处理的对象的集合。
2.数据元素,数据的基本单位，在程序中作为一个整体加以考虑和处理。
3.数据项,数据处理的最小单位。
980604 刘晔 女
1880 10
学号 姓名 性别年 月 日组合项 原子项出生日期
（学生情况）
North China Electric Power University
4.数据对象,性质相同的数据元素的集合。
5.数据的逻辑结构,对数据元素之间逻辑关系的描述。它可以用一个数据元素的集合和定义在这个集合上的若干关系来表示。
Data Structure=(D,S)
D:数据元素的集合 ; S:D上关系的集合
1）集合：集合中任何两个结点之间都没有逻辑关系，组织形式松散。
2）线性结构：元素之间存在着一对一的关系。依次排列形成一条,锁链,。
North China Electric Power University
3）树形结构：数据元素之间存在着一对多的关系，具有分支、层次特性。
4）图状结构：数据元素之间存在多对多的关系，元素之间互相缠绕，具有分支、
层次特性。
6.数据的存储结构,数据在计算机中的表示，包括数据元素的表示和关系的表示。
1）顺序存储方式（向量存储） 2）链式存储方式
3）索引存储方式 4）散列存储方式
North China Electric Power University
7.数据类型,一个值的集合和定义在这个值上的一组操作。
8.抽象数据类型,一个数学模型和定义在这个数学模型的一组操作。
特性数据抽象：用 ADT描述程序处理的实体时，强调的是其本质的特征，其完成的功能以及和外部的接口 。
数据封装：将实体的外部特性和其内部实现分离，并对外部用户隐藏其内部实现细节 。
ADT 抽象数据类型名 {
数据对象,<数据对象的定义 >
数据关系,<数据关系的定义 >
基本操作,<基本操作的定义 >
} ADT 抽象数据类型名
North China Electric Power University
例如,抽象数据类型复数的定义
ADT Complex {
数据对象,D={e1,e2|e1,e2∈Realset}
数据关系,R1={<e1,e2>|e1是复数的实数部分,e2是复数的虚数部分 }
基本操作,InitComplex(v1,v2)
DestroyComplex(Z)
GetReal(Z,realPart)
GetImag(Z,ImagPart)
Add(Z1,Z2,Sum)
Subtract(Z1,Z2,Difference)
Multiply(Z1,Z2,Product)
}
ADT Complex
注：对于数据成员完全相同的数据类型，如果给它们赋予不同的语义，
则可形成不同的抽象数据类型 。
North China Electric Power University
9.数据结构,按照某种逻辑结构组织的一组数据，
按一定的存储方式将它们映射到计算机的存储器中，并且在这些数据上定义了一个运算的集合，运算的结果保持原来的结构。
North China Electric Power University
1,研究数据元素之间的客观联系 。
2,研究具有某种逻辑关系的数据在计算机存储器内的存储方式。
3,研究如何在数据的各种结构 (逻辑的和物理的 )
的基础上对数据实施一系列有效的基本操作。
逻辑结构存储结构数据结构课程研究的主要内容算法
★ 算法算法,解决问题的方法和策略，指为解决一个或一类问题给出的一个确定的、有限长的操作序列。
分类：
1,程序设计语言描述的算法
2,伪语言算法
3,非形式算法（自然语言算法）
算法的特性,
1,有穷性
2,确定性
3,可行性
4,有输入
5,有输出
North China Electric Power University
算法设计的原则
1.正确性
a.程序中不含语法错误
b.程序对于几组给定的输入数据能得出满足要求的结果
c.程序对于精心选择的、典型的、苛刻的且带有刁难性的几组输入能得出满足要求的结果
d.程序对一切合法输入都能得出满足要求的结果
2.可读性,算法主要是为了人的阅读与交流，其次才是为了计算机执行，因此算法应该易于理解；另外，晦涩难懂的程序易于隐藏较多错误而难于调试
3.健壮性,当输入的数据非法时，算法应当恰当地做出反应或进行相应的处理，而不是产生莫名其妙的错误输出；并且处理错误的方法不应该始终段程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次进行处理
4.高效率和低存储量需求：
效率：指算法的执行时间存储量：算法执行过程中所需的最大存储空间两者都与问题的规模有关
North China Electric Power University
和算法执行时间相关的因素：
1.算法选用的策略
2.问题的规模
3.编写程序的语言
4.编译程序产生的机器代码的质量
5.计算机执行指令的速度一个特定算法的,运行工作量,的大小，只依赖于问题的规模（通常用整数量 n来表示），或者说它是问题规模的函数。
算法的复杂性复杂性,指实现或运行某一算法所需资源的多少。
时间复杂性空间复杂性人工复杂性 (指编程、调试等所需的人工 )
North China Electric Power University
算法的时间复杂性,假如随着问题规模 n的增长，
算法执行时间的增长率和 f(n)的增长率相同，则记作 T(n)=O(f(n))，称 T(n)为算法的时间复杂性。
算法时间复杂性的度量：
∵ 任何一个算法都是由一个控制结构和若干原子操作组成
∴ 算法的执行时间 =Σ 原操作 (i)的执行次数 *原操作 (i)的执行时间因为原操作的执行时间相对问题的规模 n而言是个常量，所以算法的执行时间与原操作执行次数之和成正比。
从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为时间复杂的依据。
这种衡量效率的办法所得出的不是时间量，而指一种增长趋势的度量，它与软、硬件无关，只揭示出算法本身执行效率的优劣。
North China Electric Power University
例如,k:=k+1 时间复杂度为 O(1)
例如,For i:=1 to n Do
k:=k+1 时间复杂度为 O(n)
例如,For i:=1 to n Do
For j:=1 to n Do
k:=k+1 时间复杂度为 O(n2)
例如,For i:=1 to n Do
For j:=1 to n Do
[ c[i,j]:=0;
For k:=1 to n Do
c[i,j]:=c[i,j]+a[i,k]*b[k,j];
] 时间复杂度为 O(n3)
North China Electric Power University
对于足够大的 n，存在下述关系：
O(log n)<O(n)<O(nlog n)<O(n2)<O(n3)<… <O(2n)<O(3n)<O(n!)
算法的空间复杂性,假如随着问题规模 n的增长，
算法执行所需存储量的增长率和 g(n)的增长率相同，则记作 S(n)=O(g(n))，称 S(n)为算法的空间复杂性。
算法的存储量：算法执行过程中所需的最大存储空间。
算法的存储空间
1.输入数据所占的空间
2.程序本身所占的空间
3.辅助变量所占的空间
North China Electric Power University
★ 类 Pascal语言说明类 Pascal语言来自对 Pascal语言的修改，它描述的算法是不能直接在机器上执行的程序过程。它与标准 Pascal的主要区别如下：
1,局部变量的说明可以省略 (但形参表中及函数类型的说明必须保留 )，重要的变量须在注解中说明其类型和作用。
2.算法可以写成过程或函数的形式。
Procedure 过程名 (参数表 )；
Begin
语句组；
End;
Function 过程名 (参数表 )；
Begin
语句组；
End;
注：除作为过程体和函数体标志之外的 Begin,End可用方括号代替
North China Electric Power University
3.分情形语句写成如下形式：
Case
<条件１ >,<语句组１ > ；
<条件２ >,<语句组２ > ；
<条件３ >,<语句组３ > ；
…,…
<条件ｎ >,<语句组ｎ > ；
else,<语句组ｎ +1 >
EndCase;
4.不含 goto 语句，增加以下两条语句,
1)出错处理语句,Error(字符串 )，其功能是终止它所在算法的执行，并回送表示出错信息的字符串。
2)返回语句,Return和 Return(表达式 )，其功能是终止过程的执行，在函数体中,Return(表达式 )终止函数的执行并将表达式的值回传给函数名。
5.在算法中任何处均可插入一对用花扩号扩起来的注释。
North China Electric Power University
North China Electric Power University
