Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 1页第 1章 绪论
1,数据结构讨论的范畴
2．与数据结构相关的基本概念；
3．算法及其描述和分析。
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 2页
1.1 数据结构讨论的范畴
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 3页
1.1 数据结构讨论的范畴
程序设计,为计算机处理问题编制一组指令集的过程
算法,处理问题的策略
数据结构,问题的数学模型
计算机解决的问题分为
Niklaus Wirth：
Algorithm + Data Structures = Programs
数值计算问题
非数值计算问题算法 +数据结构 =程序
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 4页
1.1 数据结构讨论的范畴登录号：
书名：
作者名：
分类号：
出版单位：
出版时间：
价格：
书目卡片例 1 图书馆的书目检索问题
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,
…… ……
索引表线性表
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 5页
1.1 数据结构讨论的范畴例 1.3铺设煤气管道问题
A
DC
FE
B7
13
17
9
18
12
7 5
24
10
怎样铺设管道最省钱（图）
3
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 6页
1.1 数据结构讨论的范畴概括地说,数据结构 是一门讨论“描述现实世界实体的数学模型 (非数值计算 )
及其上的操作在计算机中如何表示和实现”的学科。
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 7页
1.2 与数据结构相关的基本概念
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 8页
1.2.1 基本概念和术语
数据（ data）,所有能被输入到计算机中，且能被计算机处理的符号的集合，是计算机操作的对象的总称，
是计算机处理的信息的某种特定的符号表示形式。
数据元素（ data element）,是数据（集合）中的一个
,个体,,是数据的基本单位。
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 9页
1.2.1 基本概念和术语
数据项 （ data item）,是数据结构中讨论的最小单位，数据元素可以是数据项的集合；
例如,描述一个运动员的数据元素可以是
关键码（ key）,是数据元素中能起标识作用的数据项。
关系（ relation）,是指集合中元素之间的某种相关性姓名 俱乐部名称 出生日期 参加日期 职务业绩年 月 日称之为组合项
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 10页
1.2.2 数据结构
数据结构 （ data structure)— 数据元素之间存在某种关系的集合，即 带结构的数据元素的集合
或者说,数据结构 是相互之间存在着某种逻辑关系的数据元素的集合
数据结构包括：
– 数据的逻辑结构 —只抽象反映数据元素的 逻辑关系
– 数据的存储（物理）结构 —数据的逻辑结构在计算机 存储器中的实现
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 11页数据结构（逻辑结构）形式定义：
数据结构是一个二元组
Data_Structures = (D,S)
其中,
D 是数据元素的有限集，
S 是 D上关系的有限集。
例如,在一维数组 {a1,a2,a3,a4,a5,a6} 的数据元素之间存在如下的次序关系,{<ai,ai+1 >| i=1,2,3,4,5}
D= {a1,a2,a3,a4,a5,a6}
S={<ai,ai+1 >| i=1,2,3,4,5}
不同的“关系”构成不同的“结构”
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 12页根据数据元素间关系的基本特性，有四种基本数据结构
（集合） —— 数据元素间除“同属于一个集合”
外，无其它关系
线性结构 —— 一个对一个，如线性表、栈、队列
树形结构 —— 一个对多个，如树
图状结构 —— 多个对多个，如图
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 13页数据的存储结构
逻辑结构在存储器中的映象
“数据元素”的映象
“关系”的映象
数据元素的映象方法：
例如：用二进制位 (bit)的位串表示数据元素
(321)10 = (501)8 = (101000001)2
A = (101)8 = (001000001)2
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 14页关系的映象方法：（表示?x,y?的方法）
顺序映象,
– 以相对的存储位置表示后继关系例如,令 y 的存储位置和 x 的存储位置之间差一个常量 C，而
C 是一个隐含值，整个存储结构中只含数据元素本身的信息
链式映象
– 以附加信息 (指针 )表示后继关系
– 需要用一个和 x 在一起的附加信息指示 y 的存储位置
x y
y x
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 15页
1.2.3 数据类型和抽象数据类型
数据类型 (Data Type ):一个值的集合和定义在此集合上操作的总称
抽象数据类型（ Abstract Data Type）,是指一个数学模型以及定义在此数学模型上的一组操作。
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 16页
ADT 有两个重要特征
数据抽象用 ADT描述程序处理的实体时，强调的是其本质的特征,其所能 完成的功能 以及 它和外部用户的接口 （即 外界使用它的方法 ）。
数据封装将实体的外部特性和其内部实现细节分离，
并且对外部用户隐藏 其内部实现细节 。
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 17页抽象数据类型的描述方法
抽象数据类型可用（ D,S,P）三元组表示其中,D 是数据对象；
S 是 D 上的关系集；
P 是对 D 的基本操作集。
其中基本操作的定义格式为,
基本操作名 （参数表）
初始条件,〈 初始条件描述 〉
操作结果,〈 操作结果描述 〉
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 18页
ADT 抽象数据类型名 {
数据对象,<数据对象的定义 >
数据关系,<数据关系的定义 >
基本操作,<基本操作定义 >
}
抽象数据类型的描述方法
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 19页例如，抽象数据类型复数的定义：
ADT Complex {
数据对象：
D＝ {e1,e2｜ e1,e2∈RealSet }
数据关系：
R1＝ {<e1,e2> | e1是实数部分,e2 是虚数部分 }
基本操作：
AssignComplex( &Z,v1,v2 )
操作结果：构造复数 Z,其实部和虚部分别被赋以参数 v1 和 v2 的值。
DestroyComplex( &Z)
初始条件：复数已存在。
操作结果：复数 Z被销毁。
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 20页
GetReal( Z,&realPart )
初始条件：复数已存在。
操作结果：用 realPart返回复数 Z的实部值。
GetImag( Z,&ImagPart )
初始条件：复数已存在。
操作结果：用 ImagPart返回复数 Z的虚部值。
Add( z1,z2,&sum )
初始条件,z1,z2是复数。
操作结果：用 sum返回两个复数 z1,z2 的和值。
} ADT Complex
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 21页抽象数据类型的实现
抽象数据类型需要通过固有数据类型 (高级编程语言中已实现的数据类型 )来实现。
例如，后面是对以上定义的复数使用类 C语言的实现
// -----存储结构的定义
typedef struct {
float realpart；
float imagpart；
}complex；
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 22页
// -----基本操作的函数原型说明
void Assign( complex &Z,float realval,float imagval )；
// 构造复数 Z,其实部和虚部分别被赋以参数
// realval 和 imagval 的值
float GetReal( cpmplex Z )；
// 返回复数 Z 的实部值
float Getimag( cpmplex Z )；
// 返回复数 Z 的虚部值
void add( complex z1,complex z2,complex &sum )；
// 以 sum 返回两个复数 z1,z2 的和
// -----基本操作的实现
void add( complex z1,complex z2,complex &sum ) {
// 以 sum 返回两个复数 z1,z2 的和
sum.realpart = z1.realpart + z2.realpart;
sum.imagpart = z1.imagpart + z2.imagpart;
}
{ 其它省略 }
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 23页
1.3 算法及其描述和分析
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 24页
1.3.1算法
算法 是为了解决某类问题而规定的一个有限长的 操作序列 。
一个算法必须满足以下 五个重要特性
（ 1） 有穷性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
（ 2） 确定性 算法中每一条指令必须有确切的含义。不存在二义性。
且算法只有一个入口和一个出口。
（ 3） 可行性 一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
（ 4） 输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。
（ 5） 输出 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 25页算法设计的原则
设计算法时，通常应考虑达到以下目标：
1．正确性
2,可读性
3．健壮性
4．高效率与低存储量需求
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 26页
1.3.2 算法的描述
采用类 C语言学好 C/C++语言是学习数据结构的关键
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 27页
1.3.3 算法效率的衡量方法和准则
算法的效率 指的是算法的执行时间随问题规模的增长而增长的趋势。
假如，随着问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同，则可记作：
T (n) = O(f(n))
称 T (n) 为 算法的 (渐近 )时间复杂度
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 28页
算法 = 控制结构 + 原操作
（固有数据类型的操作）
算法的执行时间 =∑ 原操作 (i)的执行次数
× 原操作 (i)的执行时间算法的执行时间 与 原操作执行次数之和 成正比
从算法中选取一种对于所研究的问题来说是 基本操作的原操作，以该基本操作 在算法中重复执行的次数作为算法运行时间的衡量准则。
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 29页算法 1.1 矩阵相乘
void mult(int a[],int b[],int& c[] ) {
// 以二维数组存储矩阵元素,c 为 a 和 b 的乘积
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];
} //for
} //mult
基本操作,乘法 操作时间复杂度,O(n3)
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 30页算法 1.2 选择排序
void select_sort(int& a[],int n) {
// 将 a 中整数序列重新排列成自小至大有序的整数序列 。
} // select_sort
基本操作,比较 (数据元素 )操作
j = i; // 选择第 i 个最小元素
for ( k = i+1; k < n; ++k )
if (a[k] < a[j] ) j = k;
for ( i = 0; i< n-1; ++i ) {
if ( j != i ) a[j] ←→ a[i]
}
时间复杂度,O(n2)
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 31页
1.3.4 算法的存储空间需求
算法的 空间复杂度定义为,
S(n) = O(g(n))
表示随着问题规模 n 的增大，算法运行所需存储量的增长率与 g(n) 的增长率相同。
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 32页算法的存储量包括
1,输入数据 所占空间
2,程序本身 所占空间
3,辅助变量 所占空间
若 输入数据 所占空间只取决于问题本身,和算法无关,
则只需要分析除 输入和程序之外的 辅助变量 所占 额外空间 。
若所需额外空间相对于输入数据量来说是常数，则称此算法为 原地工作 。
若所需存储量依赖于特定的输入，则通常按最坏情况考虑。
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 33页本章学习要点
1,熟悉各名词、术语的含义，掌握基本概念。
2,理解算法五个要素的确切含义。
3,掌握计算语句频度和估算算法时间复杂度的方法。
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 34页作业,
教材,P11
1.3
1.4
1.5(最后上机实现）
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 1页第 1章 绪论
1,数据结构讨论的范畴
2．与数据结构相关的基本概念；
3．算法及其描述和分析。
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 2页
1.1 数据结构讨论的范畴
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 3页
1.1 数据结构讨论的范畴
程序设计,为计算机处理问题编制一组指令集的过程
算法,处理问题的策略
数据结构,问题的数学模型
计算机解决的问题分为
Niklaus Wirth：
Algorithm + Data Structures = Programs
数值计算问题
非数值计算问题算法 +数据结构 =程序
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 4页
1.1 数据结构讨论的范畴登录号：
书名：
作者名：
分类号：
出版单位：
出版时间：
价格：
书目卡片例 1 图书馆的书目检索问题
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,
…… ……
索引表线性表
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 5页
1.1 数据结构讨论的范畴例 1.3铺设煤气管道问题
A
DC
FE
B7
13
17
9
18
12
7 5
24
10
怎样铺设管道最省钱（图）
3
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 6页
1.1 数据结构讨论的范畴概括地说,数据结构 是一门讨论“描述现实世界实体的数学模型 (非数值计算 )
及其上的操作在计算机中如何表示和实现”的学科。
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 7页
1.2 与数据结构相关的基本概念
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 8页
1.2.1 基本概念和术语
数据（ data）,所有能被输入到计算机中，且能被计算机处理的符号的集合，是计算机操作的对象的总称，
是计算机处理的信息的某种特定的符号表示形式。
数据元素（ data element）,是数据（集合）中的一个
,个体,,是数据的基本单位。
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 9页
1.2.1 基本概念和术语
数据项 （ data item）,是数据结构中讨论的最小单位，数据元素可以是数据项的集合；
例如,描述一个运动员的数据元素可以是
关键码（ key）,是数据元素中能起标识作用的数据项。
关系（ relation）,是指集合中元素之间的某种相关性姓名 俱乐部名称 出生日期 参加日期 职务业绩年 月 日称之为组合项
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 10页
1.2.2 数据结构
数据结构 （ data structure)— 数据元素之间存在某种关系的集合，即 带结构的数据元素的集合
或者说,数据结构 是相互之间存在着某种逻辑关系的数据元素的集合
数据结构包括：
– 数据的逻辑结构 —只抽象反映数据元素的 逻辑关系
– 数据的存储（物理）结构 —数据的逻辑结构在计算机 存储器中的实现
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 11页数据结构（逻辑结构）形式定义：
数据结构是一个二元组
Data_Structures = (D,S)
其中,
D 是数据元素的有限集，
S 是 D上关系的有限集。
例如,在一维数组 {a1,a2,a3,a4,a5,a6} 的数据元素之间存在如下的次序关系,{<ai,ai+1 >| i=1,2,3,4,5}
D= {a1,a2,a3,a4,a5,a6}
S={<ai,ai+1 >| i=1,2,3,4,5}
不同的“关系”构成不同的“结构”
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 12页根据数据元素间关系的基本特性，有四种基本数据结构
（集合） —— 数据元素间除“同属于一个集合”
外，无其它关系
线性结构 —— 一个对一个，如线性表、栈、队列
树形结构 —— 一个对多个，如树
图状结构 —— 多个对多个，如图
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 13页数据的存储结构
逻辑结构在存储器中的映象
“数据元素”的映象
“关系”的映象
数据元素的映象方法：
例如：用二进制位 (bit)的位串表示数据元素
(321)10 = (501)8 = (101000001)2
A = (101)8 = (001000001)2
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 14页关系的映象方法：（表示?x,y?的方法）
顺序映象,
– 以相对的存储位置表示后继关系例如,令 y 的存储位置和 x 的存储位置之间差一个常量 C，而
C 是一个隐含值，整个存储结构中只含数据元素本身的信息
链式映象
– 以附加信息 (指针 )表示后继关系
– 需要用一个和 x 在一起的附加信息指示 y 的存储位置
x y
y x
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 15页
1.2.3 数据类型和抽象数据类型
数据类型 (Data Type ):一个值的集合和定义在此集合上操作的总称
抽象数据类型（ Abstract Data Type）,是指一个数学模型以及定义在此数学模型上的一组操作。
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 16页
ADT 有两个重要特征
数据抽象用 ADT描述程序处理的实体时，强调的是其本质的特征,其所能 完成的功能 以及 它和外部用户的接口 （即 外界使用它的方法 ）。
数据封装将实体的外部特性和其内部实现细节分离，
并且对外部用户隐藏 其内部实现细节 。
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 17页抽象数据类型的描述方法
抽象数据类型可用（ D,S,P）三元组表示其中,D 是数据对象；
S 是 D 上的关系集；
P 是对 D 的基本操作集。
其中基本操作的定义格式为,
基本操作名 （参数表）
初始条件,〈 初始条件描述 〉
操作结果,〈 操作结果描述 〉
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 18页
ADT 抽象数据类型名 {
数据对象,<数据对象的定义 >
数据关系,<数据关系的定义 >
基本操作,<基本操作定义 >
}
抽象数据类型的描述方法
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 19页例如，抽象数据类型复数的定义：
ADT Complex {
数据对象：
D＝ {e1,e2｜ e1,e2∈RealSet }
数据关系：
R1＝ {<e1,e2> | e1是实数部分,e2 是虚数部分 }
基本操作：
AssignComplex( &Z,v1,v2 )
操作结果：构造复数 Z,其实部和虚部分别被赋以参数 v1 和 v2 的值。
DestroyComplex( &Z)
初始条件：复数已存在。
操作结果：复数 Z被销毁。
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 20页
GetReal( Z,&realPart )
初始条件：复数已存在。
操作结果：用 realPart返回复数 Z的实部值。
GetImag( Z,&ImagPart )
初始条件：复数已存在。
操作结果：用 ImagPart返回复数 Z的虚部值。
Add( z1,z2,&sum )
初始条件,z1,z2是复数。
操作结果：用 sum返回两个复数 z1,z2 的和值。
} ADT Complex
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 21页抽象数据类型的实现
抽象数据类型需要通过固有数据类型 (高级编程语言中已实现的数据类型 )来实现。
例如，后面是对以上定义的复数使用类 C语言的实现
// -----存储结构的定义
typedef struct {
float realpart；
float imagpart；
}complex；
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 22页
// -----基本操作的函数原型说明
void Assign( complex &Z,float realval,float imagval )；
// 构造复数 Z,其实部和虚部分别被赋以参数
// realval 和 imagval 的值
float GetReal( cpmplex Z )；
// 返回复数 Z 的实部值
float Getimag( cpmplex Z )；
// 返回复数 Z 的虚部值
void add( complex z1,complex z2,complex &sum )；
// 以 sum 返回两个复数 z1,z2 的和
// -----基本操作的实现
void add( complex z1,complex z2,complex &sum ) {
// 以 sum 返回两个复数 z1,z2 的和
sum.realpart = z1.realpart + z2.realpart;
sum.imagpart = z1.imagpart + z2.imagpart;
}
{ 其它省略 }
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 23页
1.3 算法及其描述和分析
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 24页
1.3.1算法
算法 是为了解决某类问题而规定的一个有限长的 操作序列 。
一个算法必须满足以下 五个重要特性
（ 1） 有穷性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
（ 2） 确定性 算法中每一条指令必须有确切的含义。不存在二义性。
且算法只有一个入口和一个出口。
（ 3） 可行性 一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
（ 4） 输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。
（ 5） 输出 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 25页算法设计的原则
设计算法时，通常应考虑达到以下目标：
1．正确性
2,可读性
3．健壮性
4．高效率与低存储量需求
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 26页
1.3.2 算法的描述
采用类 C语言学好 C/C++语言是学习数据结构的关键
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 27页
1.3.3 算法效率的衡量方法和准则
算法的效率 指的是算法的执行时间随问题规模的增长而增长的趋势。
假如，随着问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同，则可记作：
T (n) = O(f(n))
称 T (n) 为 算法的 (渐近 )时间复杂度
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 28页
算法 = 控制结构 + 原操作
（固有数据类型的操作）
算法的执行时间 =∑ 原操作 (i)的执行次数
× 原操作 (i)的执行时间算法的执行时间 与 原操作执行次数之和 成正比
从算法中选取一种对于所研究的问题来说是 基本操作的原操作，以该基本操作 在算法中重复执行的次数作为算法运行时间的衡量准则。
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 29页算法 1.1 矩阵相乘
void mult(int a[],int b[],int& c[] ) {
// 以二维数组存储矩阵元素,c 为 a 和 b 的乘积
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];
} //for
} //mult
基本操作,乘法 操作时间复杂度,O(n3)
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 30页算法 1.2 选择排序
void select_sort(int& a[],int n) {
// 将 a 中整数序列重新排列成自小至大有序的整数序列 。
} // select_sort
基本操作,比较 (数据元素 )操作
j = i; // 选择第 i 个最小元素
for ( k = i+1; k < n; ++k )
if (a[k] < a[j] ) j = k;
for ( i = 0; i< n-1; ++i ) {
if ( j != i ) a[j] ←→ a[i]
}
时间复杂度,O(n2)
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 31页
1.3.4 算法的存储空间需求
算法的 空间复杂度定义为,
S(n) = O(g(n))
表示随着问题规模 n 的增大，算法运行所需存储量的增长率与 g(n) 的增长率相同。
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 32页算法的存储量包括
1,输入数据 所占空间
2,程序本身 所占空间
3,辅助变量 所占空间
若 输入数据 所占空间只取决于问题本身,和算法无关,
则只需要分析除 输入和程序之外的 辅助变量 所占 额外空间 。
若所需额外空间相对于输入数据量来说是常数，则称此算法为 原地工作 。
若所需存储量依赖于特定的输入，则通常按最坏情况考虑。
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 33页本章学习要点
1,熟悉各名词、术语的含义，掌握基本概念。
2,理解算法五个要素的确切含义。
3,掌握计算语句频度和估算算法时间复杂度的方法。
Da
ta
Str
uc
tur
e
数据结构——
第
1
章绪论胡建华 2009-7-24计算机教研室第 34页作业,
教材,P11
1.3
1.4
1.5(最后上机实现）
