数据结构 B
总学时, 48 理论学时,36 上机学时,12
采用 教材,
,数据结构 ----使用 C语言,
陈一华等编
电子科技大学出版社
第 一 章 绪 论
1, 1 数据结构课程的形成和发展
什么是数据结构?
当前, 计算机的应用已渗透到社会活动的各个领
域 。 在使用计算机的初期, 其应用还局限于科学计算,
也就是大量用于数值计算 。 如果计算机仅只能用于数
值计算, 恐怕其普及程度不会象今天这样广泛, 计算
机应用领域的不断扩大, 以至进入普通的百姓家庭,
是因为随着 计算机硬件和软件技术的不断提高, 而更
多地 用于控制, 管理及数据处理等非数值计算的领域,
与此相应, 计算机加工处理的对象由纯粹的数值发展
到字符, 表格, 图象, 声音等各种具有一定 结构 的 数
据。为编出一个, 好, 的程序，必须分析待处理对象的
特性及各待处理对象之间存在的关系。在这种背景下，就
形成了, 数据 结构, 这门学科。
当用 计算机解决一个具体问题时,一般要经过下面
几个步骤：
1,根据需 解决 的 具体问题抽象出一个适当的 数学模
型，也称建 模。
2,设计 一个适合于计算机执行的解此 数学模 型的算
法 。
3,根据 算法,编写程序,并对所编程序进行调试
直至获得最终解答。
其实质是分析问题，从中提取操作的对象，并找出这些
操作对象之间含有的关系，然后用数学语言加以描述。
在此，数学模 型的 这一 含义已被扩充,所为数学模
型并非一定要用 数学方程如线性方程组,微分 方程等数
学解析式来表达，更多的非数值计算问题无法用数学方
程式来描述，需用其它方式加以描述，统称为数学模 型
在数据 结构 这一学科中，常采用表, 树, 图等数学
模 型 来 抽象 需 解决 的 具体问题,下面用三个例子加以说
明。
例 1,图书馆的书目检索系统自动化问题。
在上述三个步骤中,建 模是首要的也是关键的一步
001 高等数学 樊映川 S01 ┅
002 理论力学 罗远祥 L01 ┅
003 高等数学 华罗庚 S01 ┅
004 线性代数 栾汝书 S02 ┅
￤ ￤ ￤ ￤ ￤
高等数学 001, 003, ┅
理论力学 002, ┅
线性代数 004, ┅
￤ ￤
樊 映川 001, ┅
华罗庚 003, ┅
栾汝书 004, ┅
￤ ￤
L 002, ┅
S 001, 003, ┅
￤ ￤
在例 1中，有四张二维表构成的文件是图书馆书目检索
系统自动化问题的数学模型，在这类问题中计算机处
理的对象之间通常存在着的是一种最简单的线性关系
这类数学模型可称作为线性的 数据 结构。
例 2,大学的行政 结构 问题。
某大学
学院 1 学院 2 ┅ ┅ 学院 N
￤
系 11 系 12 ┅ 系 21 ┅ ┅ 系 N1 ┅
专业 A 专业 B ┅
1班 ┅
例 2的行政 结构 可用树型 结构来表示，类似于 例 2的非
数值计算问题均可用称作为“树”的数学模型来表示，
“树”也是一种数据结构。
例 3,若干个地点间的交通 问题
B C D
A E F G H
I J K
是一种称作为“图”的数据结构。
可见，描述上面三例的 非数值计算问题的 数学模
型不再是我们通常所熟悉的数学方程，而是诸如表,
树, 图之类的数据结构。因此，
数据结构是一门研究非数值计算的程序设计问题
中计算机的 操作对象 以及它们之间的 关系 和 操作 等等
的学科。
1, 2 数据结构与算法
数据结构与算法是两个互相关联的问题，为了解
两者间的关系，必须先了解一些基本概念。
1, 2, 1 基本概念和术语
例 3表示的若干个地点间的交通 问题所对应的数学模型
数据 (data),是客观事物的符号表示,在计算机科学
中是指所有能被计算机所接受并被计算机程序所处理的
符号的总称,
数据的含义极为广泛, 例如,一个用数值分析方法
解代数方程的程序,其处理的对像是实数 ; 一个编译程
序或文字处理程序的处理对像是字符串 ; 而图像,声音
等都可通过编码而归于 数据的范畴,
数据元素 (data element),是组成数据的基本单位,
数据元素在计算机程序中通常作为一个整体进行考
虑和处理, 例如,一本书的书目信息作为一个数据元素
在数据库语言中,常被当作一条记录进行考虑和处理,
一个数据元素可由若干个 数据项 (data item)组成,
例如,书目信息中的每一项如书名,作者 名,出版社等
均为一个数据项,
数据项 (data item),是数据的不可分割的最小单位,
数据对像 (data object),是同一种数据类型 (或称性质相
同 )的数据元素的集合,是数据的一个子集,
例如,整数数据对像是整数类型数据的集合,即
? ??,2,1,0 ???N 字母字符的 数据对像是集合 C={‘A’,
‘B’,…,’Z’}.
数据结构 (data structure),数据元素之间存在的相互关系,
根据数据元素之间关系的不同特性,通常有下列四种基本
结构,
(1)集合, 结构中的数据元素之间除了“同属于一个集合”的
关系外,无其它关系, 和数学中的集合概念一致,
(2)线性结构, 结构中的数据元素之间存在一个对一个的关
系,
(3)树型结构, 结构中的数据元素之间存在一对多的关系,
(4)图状结构或网状结构,结构中的数据元素之间存在
多对多的关系,
上述数据结构的定义仅是对操作对象的一种数学描
述,是从操作对象抽象出来的数学模型,
数据的逻辑结构 (logic structure), 数据元素之间抽
象化的相互关系,
除了在形式上定义出数据的逻辑结构外,在设计算
法和程序时,尚需研究这些数据在计算机存储器中的存
储方式,
数据的物理结构, 数据结构在计算机中的存储方式
叫做数据结构在计算机中的映像,而这一映像叫数据的
物理结构,也叫 存储结构,
在计算机中表示信息的最小单位是二进制数的一位,
叫做位 (bit),在计算机中可用若干位组合成位串表示一个
数据元素,例如,用一个字长 (8位 )的位串表示一个有限范
围的整数,用一个字长表示一个字符等,从而称这个位
串 (bit string)为 元素 (element)或结点 (node),当数据元素
有若干数据项组成时,位串中对应于各个数据项的子串叫
数据域 (data field),显然,元素或结点就是数据元素在计
算机中的映像,
数据元素之间的关系在计算机中有两种不同的表示
方法, 顺序映像及相应的顺序存储结构和非顺序映像及
相应的链式存储结构,
顺序存储结构的特点是用一组地址连续的存储单元
来表示数据元素之间的逻辑关系,
链式存储结构的特点是用指示存储单元地址的指针来
表示数据元素之间的逻辑关系,而这些存储单元的地址可
以连续也可以不连续,
1, 2, 2 算法的概念和特性
算法 (algorithm),是对特定问题求解步骤的一种描述,
在计算机科学中,它是指令的有限序列,其中的每一条指
令表示一个或多个操作,
算法有下列五个重要特性,
(1)有穷性, 一个算法必须总是对任何合法的输入值在
执行有穷步之后结束,且每一步都可在有穷时间内完成,
(2)确定性, 算法中每一条指令必须有确切的含义,不
能有二义性, 且在任何条件下,算法只有唯一的一条执行
路经,即对于相同的输入只能得到相同的输出,
(3)可行性, 算法中描述的操作都可通过已经实现的基
本运算执行有限次来完成,
(4)数据输入, 一个算法有零个或多个输入,这些输入
取自特定的数据对象的集合,
(5)信息输出, 一个算法必须有一个或多个有效信息的
输出,它是同输入有某种特定关系的信息,
1, 4 算法的描述和分析
一,算法的描述
根据不同的需要,一个算法可用不同的形式进行描述
如用文字框图,程序流程图或用 计算机能执行的语言,
二, 算法设计的要求
(1)正确性 (correctness),分以下几个层次,
a,程序不含语法错误 ;
b,程序对于几组输入数据能够得出满足要求的结果 ;
c,程序对于精心选择的典型,苛刻而有刁难性的 几组
输入数据都能够得出满足要求的结果 ;
d,程序对于一切合法的输入数据能够得出满足要求
的结果,
(2)可读性 (readability)
(3)健壮性 (robustness),指当输入非法数据时,算法能作出
反应,
(4)效率与低存储需求, 效率指算法执行时间,而存储需求
指算法执行过程中所需要的最大存
储空间, 这两者与算法所解决问题
的规模有关,
二, 算法效率的度量
1.算法的时间效率
算法执行时间需通过依据该算法编制的程序在计算机
上运行时所消耗的时间来度量,有两种方法,
1)事后统计法 ; 2)事先分析估算法,
但上述两种方法的缺点是,所得时间效率与计算机的硬件
和软件有关,缺少可比性, 如撇开与计算机有关的因素,
可认为一个特定算法,运行工作量” 的大小,仅与问题
的
规模 (用整数 n表示 )有关,即是问题规模的函数,
为便于比较同一问题的不同算法的时间效率,通常的
做法是,从算法中选取一种对于所研究的问题来说是基本
运算的原操作,以该 操作 (即程序中 执行 该 操作的指令 )重复执
行的次数 (也就是语句的频度 )作为 算法的 时间的度量, 例如,
两个 N*N矩阵相乘的算法,可用 C语言的程序描述如下,
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]= c[i][j]+a[i][k]*b [k] [j]
}
};
其中每一条语句的频度为
? ?1?n
? ?)1( ?nn
? ?2n
? ?)1(2 ?nn
? ?3n
将 算法所耗费的时间定义为该算法中每条语句的频度之和
则上述算法的时间耗费为,
1232)( 23 ???? nnnnT显然它是矩阵的阶 n的函数,且当
??n 时 2)(
3 ?n
nT 即 n充分
大时,)(nT 和 3n 是同阶的,引入, O”记号 (读作大, O”),
可记,一般情况下,算法中基本操作重复执行的)()( 3nOnT ?
次数是问题规模的 n的某个函数 )(nf,算法的时间复杂度记
作 )).(()( nfOnT ? 它表示随问题规模 n的增大,算法执行时间
的增长率和 )(nf 的增长率相同,称作 算法的渐进时间复杂度
简称 时间复杂度, 由上例可得对程序的分析法则为,
(1)执行一条读或赋值语句用 O(1)时间 ;
(2)依次执行一系列语句所用时间用求和准则 ;
(3)if语句的耗时主要是执行语句所用的时间,检验语句
还需用 O(1)时间 ;
(4)循环语句的运行时间为多次迭代中执行循环以及检验
循环条件耗时,常用乘法计算,
对于较复杂的算法,可将它分成几个容易估算的部分,
然后利用,O”的求和准则和乘法准则计算整个算法的时间复
杂度,
大, O”下的求和准则, 若算法的两个部分的时间复杂度
为
和 ))(()(
1 nfOnT ? ))(()(2 ngOnT ?,则 ) ) )(),(( m ax (21 ngnfOTT ??
又若 ))(()()),(()(
21 ngOnTmfOmT ??,则 )).()((21 ngmfOTT ???
大, O”下的乘法准则, 若算法的两个部分的时间复杂度为
))(()(1 nfOnT ? 和 ))(()(2 ngOnT ?,则 )).()((21 ngnfOTT ???
例, 下面程序段为
(1) s=0;
(2) for(i=1;i<=n;i++)
(3) {for(j=1;j<=n;j++)
(4) s++; }
执行一条赋值语句与 n无关,时间复杂度为 )1()(),1()(
41 OnTOnT ??
对于第三条语句,)()(
3 nOnT ?
,因此 )()()(
34 nOnTnT ??
,第二条语
句 )()(
2 nOnT ?,而第 (2)与 (3),(4)是 循环嵌套,故有
)())()(()( 2432 nOnTnTnT ???,对于第一条语句 )1()(1 OnT ?,与其它
语句之间的关系是顺序 执行,故有 )())()(()()( 2
4321 nOnTnTnTnT ????
常见的 时间复杂度有常数阶,对 数阶)1(O )(log 2 nO,线性 阶
)(nO,线性对 数阶 )log( 2 nnO,平方 阶 )( 2nO,立方 阶 )( 3nO
、指 数阶 ).2( nO
2.算法的存储空间需求
算法所需存储空间可用空间复杂度 (space complexity)
来度量,记作
)).(()( nfOnS ?
其中 n为问题的规模 (或大小 ).
课外习题
教材,P.8第 4题
学习数据结构的意义
数据结构是计算机软件和应用专业的核心课程,也
是一门独立的课程, 随着计算机技术的发展,计算机应
用的普及,仅掌握计算机语言和程序设计的技巧与方法
而缺乏有关数据结构的知识,就难以应付众多复杂的课
题,不能有效地使用计算机,
数据结构在计算机科学有着十分重要的地位,它与
计算机软件 ﹑ 硬件以及数学有着密切的关系,是操作系
统 ﹑ 编译原理 ﹑ 数据库和人工智能等课程的基础,广泛
应用于信息科学 ﹑ 系统工程 ﹑ 应用数学以及各种工程技
术领域,
当今,计算机解决非数值性问题越来越多,数据元
素之间由简单联系变为往往无法用数学方程进行描述的
复杂结构, 人们认识到程序设计的实质是对确定的问题
选择一种好的结构从而设计出一种好的算法, 曾有学者
指出, 算法 +数据结构 =程序,这里,算法指的是对数据
运算的描述,数据结构指数据的逻辑结构和存储结构, 可
见程序设计的实质是对实际问题选择一种好的数据结构
从而设计出一个好的算法有效地解决问题,
在数据结构着门课程中,有些内容需用到 C语言中
的指针的概念, 因此,要求同学们务必认真地复习和深
入地掌握 C语言中有关指针的基本概念 ﹑ 相关的语句及
其应用, 否则,将给本门课程的学习 ﹑ 完成课外习题 ﹑
上机实习及最后的考试带来很大的困难,
总学时, 48 理论学时,36 上机学时,12
采用 教材,
,数据结构 ----使用 C语言,
陈一华等编
电子科技大学出版社
第 一 章 绪 论
1, 1 数据结构课程的形成和发展
什么是数据结构?
当前, 计算机的应用已渗透到社会活动的各个领
域 。 在使用计算机的初期, 其应用还局限于科学计算,
也就是大量用于数值计算 。 如果计算机仅只能用于数
值计算, 恐怕其普及程度不会象今天这样广泛, 计算
机应用领域的不断扩大, 以至进入普通的百姓家庭,
是因为随着 计算机硬件和软件技术的不断提高, 而更
多地 用于控制, 管理及数据处理等非数值计算的领域,
与此相应, 计算机加工处理的对象由纯粹的数值发展
到字符, 表格, 图象, 声音等各种具有一定 结构 的 数
据。为编出一个, 好, 的程序，必须分析待处理对象的
特性及各待处理对象之间存在的关系。在这种背景下，就
形成了, 数据 结构, 这门学科。
当用 计算机解决一个具体问题时,一般要经过下面
几个步骤：
1,根据需 解决 的 具体问题抽象出一个适当的 数学模
型，也称建 模。
2,设计 一个适合于计算机执行的解此 数学模 型的算
法 。
3,根据 算法,编写程序,并对所编程序进行调试
直至获得最终解答。
其实质是分析问题，从中提取操作的对象，并找出这些
操作对象之间含有的关系，然后用数学语言加以描述。
在此，数学模 型的 这一 含义已被扩充,所为数学模
型并非一定要用 数学方程如线性方程组,微分 方程等数
学解析式来表达，更多的非数值计算问题无法用数学方
程式来描述，需用其它方式加以描述，统称为数学模 型
在数据 结构 这一学科中，常采用表, 树, 图等数学
模 型 来 抽象 需 解决 的 具体问题,下面用三个例子加以说
明。
例 1,图书馆的书目检索系统自动化问题。
在上述三个步骤中,建 模是首要的也是关键的一步
001 高等数学 樊映川 S01 ┅
002 理论力学 罗远祥 L01 ┅
003 高等数学 华罗庚 S01 ┅
004 线性代数 栾汝书 S02 ┅
￤ ￤ ￤ ￤ ￤
高等数学 001, 003, ┅
理论力学 002, ┅
线性代数 004, ┅
￤ ￤
樊 映川 001, ┅
华罗庚 003, ┅
栾汝书 004, ┅
￤ ￤
L 002, ┅
S 001, 003, ┅
￤ ￤
在例 1中，有四张二维表构成的文件是图书馆书目检索
系统自动化问题的数学模型，在这类问题中计算机处
理的对象之间通常存在着的是一种最简单的线性关系
这类数学模型可称作为线性的 数据 结构。
例 2,大学的行政 结构 问题。
某大学
学院 1 学院 2 ┅ ┅ 学院 N
￤
系 11 系 12 ┅ 系 21 ┅ ┅ 系 N1 ┅
专业 A 专业 B ┅
1班 ┅
例 2的行政 结构 可用树型 结构来表示，类似于 例 2的非
数值计算问题均可用称作为“树”的数学模型来表示，
“树”也是一种数据结构。
例 3,若干个地点间的交通 问题
B C D
A E F G H
I J K
是一种称作为“图”的数据结构。
可见，描述上面三例的 非数值计算问题的 数学模
型不再是我们通常所熟悉的数学方程，而是诸如表,
树, 图之类的数据结构。因此，
数据结构是一门研究非数值计算的程序设计问题
中计算机的 操作对象 以及它们之间的 关系 和 操作 等等
的学科。
1, 2 数据结构与算法
数据结构与算法是两个互相关联的问题，为了解
两者间的关系，必须先了解一些基本概念。
1, 2, 1 基本概念和术语
例 3表示的若干个地点间的交通 问题所对应的数学模型
数据 (data),是客观事物的符号表示,在计算机科学
中是指所有能被计算机所接受并被计算机程序所处理的
符号的总称,
数据的含义极为广泛, 例如,一个用数值分析方法
解代数方程的程序,其处理的对像是实数 ; 一个编译程
序或文字处理程序的处理对像是字符串 ; 而图像,声音
等都可通过编码而归于 数据的范畴,
数据元素 (data element),是组成数据的基本单位,
数据元素在计算机程序中通常作为一个整体进行考
虑和处理, 例如,一本书的书目信息作为一个数据元素
在数据库语言中,常被当作一条记录进行考虑和处理,
一个数据元素可由若干个 数据项 (data item)组成,
例如,书目信息中的每一项如书名,作者 名,出版社等
均为一个数据项,
数据项 (data item),是数据的不可分割的最小单位,
数据对像 (data object),是同一种数据类型 (或称性质相
同 )的数据元素的集合,是数据的一个子集,
例如,整数数据对像是整数类型数据的集合,即
? ??,2,1,0 ???N 字母字符的 数据对像是集合 C={‘A’,
‘B’,…,’Z’}.
数据结构 (data structure),数据元素之间存在的相互关系,
根据数据元素之间关系的不同特性,通常有下列四种基本
结构,
(1)集合, 结构中的数据元素之间除了“同属于一个集合”的
关系外,无其它关系, 和数学中的集合概念一致,
(2)线性结构, 结构中的数据元素之间存在一个对一个的关
系,
(3)树型结构, 结构中的数据元素之间存在一对多的关系,
(4)图状结构或网状结构,结构中的数据元素之间存在
多对多的关系,
上述数据结构的定义仅是对操作对象的一种数学描
述,是从操作对象抽象出来的数学模型,
数据的逻辑结构 (logic structure), 数据元素之间抽
象化的相互关系,
除了在形式上定义出数据的逻辑结构外,在设计算
法和程序时,尚需研究这些数据在计算机存储器中的存
储方式,
数据的物理结构, 数据结构在计算机中的存储方式
叫做数据结构在计算机中的映像,而这一映像叫数据的
物理结构,也叫 存储结构,
在计算机中表示信息的最小单位是二进制数的一位,
叫做位 (bit),在计算机中可用若干位组合成位串表示一个
数据元素,例如,用一个字长 (8位 )的位串表示一个有限范
围的整数,用一个字长表示一个字符等,从而称这个位
串 (bit string)为 元素 (element)或结点 (node),当数据元素
有若干数据项组成时,位串中对应于各个数据项的子串叫
数据域 (data field),显然,元素或结点就是数据元素在计
算机中的映像,
数据元素之间的关系在计算机中有两种不同的表示
方法, 顺序映像及相应的顺序存储结构和非顺序映像及
相应的链式存储结构,
顺序存储结构的特点是用一组地址连续的存储单元
来表示数据元素之间的逻辑关系,
链式存储结构的特点是用指示存储单元地址的指针来
表示数据元素之间的逻辑关系,而这些存储单元的地址可
以连续也可以不连续,
1, 2, 2 算法的概念和特性
算法 (algorithm),是对特定问题求解步骤的一种描述,
在计算机科学中,它是指令的有限序列,其中的每一条指
令表示一个或多个操作,
算法有下列五个重要特性,
(1)有穷性, 一个算法必须总是对任何合法的输入值在
执行有穷步之后结束,且每一步都可在有穷时间内完成,
(2)确定性, 算法中每一条指令必须有确切的含义,不
能有二义性, 且在任何条件下,算法只有唯一的一条执行
路经,即对于相同的输入只能得到相同的输出,
(3)可行性, 算法中描述的操作都可通过已经实现的基
本运算执行有限次来完成,
(4)数据输入, 一个算法有零个或多个输入,这些输入
取自特定的数据对象的集合,
(5)信息输出, 一个算法必须有一个或多个有效信息的
输出,它是同输入有某种特定关系的信息,
1, 4 算法的描述和分析
一,算法的描述
根据不同的需要,一个算法可用不同的形式进行描述
如用文字框图,程序流程图或用 计算机能执行的语言,
二, 算法设计的要求
(1)正确性 (correctness),分以下几个层次,
a,程序不含语法错误 ;
b,程序对于几组输入数据能够得出满足要求的结果 ;
c,程序对于精心选择的典型,苛刻而有刁难性的 几组
输入数据都能够得出满足要求的结果 ;
d,程序对于一切合法的输入数据能够得出满足要求
的结果,
(2)可读性 (readability)
(3)健壮性 (robustness),指当输入非法数据时,算法能作出
反应,
(4)效率与低存储需求, 效率指算法执行时间,而存储需求
指算法执行过程中所需要的最大存
储空间, 这两者与算法所解决问题
的规模有关,
二, 算法效率的度量
1.算法的时间效率
算法执行时间需通过依据该算法编制的程序在计算机
上运行时所消耗的时间来度量,有两种方法,
1)事后统计法 ; 2)事先分析估算法,
但上述两种方法的缺点是,所得时间效率与计算机的硬件
和软件有关,缺少可比性, 如撇开与计算机有关的因素,
可认为一个特定算法,运行工作量” 的大小,仅与问题
的
规模 (用整数 n表示 )有关,即是问题规模的函数,
为便于比较同一问题的不同算法的时间效率,通常的
做法是,从算法中选取一种对于所研究的问题来说是基本
运算的原操作,以该 操作 (即程序中 执行 该 操作的指令 )重复执
行的次数 (也就是语句的频度 )作为 算法的 时间的度量, 例如,
两个 N*N矩阵相乘的算法,可用 C语言的程序描述如下,
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]= c[i][j]+a[i][k]*b [k] [j]
}
};
其中每一条语句的频度为
? ?1?n
? ?)1( ?nn
? ?2n
? ?)1(2 ?nn
? ?3n
将 算法所耗费的时间定义为该算法中每条语句的频度之和
则上述算法的时间耗费为,
1232)( 23 ???? nnnnT显然它是矩阵的阶 n的函数,且当
??n 时 2)(
3 ?n
nT 即 n充分
大时,)(nT 和 3n 是同阶的,引入, O”记号 (读作大, O”),
可记,一般情况下,算法中基本操作重复执行的)()( 3nOnT ?
次数是问题规模的 n的某个函数 )(nf,算法的时间复杂度记
作 )).(()( nfOnT ? 它表示随问题规模 n的增大,算法执行时间
的增长率和 )(nf 的增长率相同,称作 算法的渐进时间复杂度
简称 时间复杂度, 由上例可得对程序的分析法则为,
(1)执行一条读或赋值语句用 O(1)时间 ;
(2)依次执行一系列语句所用时间用求和准则 ;
(3)if语句的耗时主要是执行语句所用的时间,检验语句
还需用 O(1)时间 ;
(4)循环语句的运行时间为多次迭代中执行循环以及检验
循环条件耗时,常用乘法计算,
对于较复杂的算法,可将它分成几个容易估算的部分,
然后利用,O”的求和准则和乘法准则计算整个算法的时间复
杂度,
大, O”下的求和准则, 若算法的两个部分的时间复杂度
为
和 ))(()(
1 nfOnT ? ))(()(2 ngOnT ?,则 ) ) )(),(( m ax (21 ngnfOTT ??
又若 ))(()()),(()(
21 ngOnTmfOmT ??,则 )).()((21 ngmfOTT ???
大, O”下的乘法准则, 若算法的两个部分的时间复杂度为
))(()(1 nfOnT ? 和 ))(()(2 ngOnT ?,则 )).()((21 ngnfOTT ???
例, 下面程序段为
(1) s=0;
(2) for(i=1;i<=n;i++)
(3) {for(j=1;j<=n;j++)
(4) s++; }
执行一条赋值语句与 n无关,时间复杂度为 )1()(),1()(
41 OnTOnT ??
对于第三条语句,)()(
3 nOnT ?
,因此 )()()(
34 nOnTnT ??
,第二条语
句 )()(
2 nOnT ?,而第 (2)与 (3),(4)是 循环嵌套,故有
)())()(()( 2432 nOnTnTnT ???,对于第一条语句 )1()(1 OnT ?,与其它
语句之间的关系是顺序 执行,故有 )())()(()()( 2
4321 nOnTnTnTnT ????
常见的 时间复杂度有常数阶,对 数阶)1(O )(log 2 nO,线性 阶
)(nO,线性对 数阶 )log( 2 nnO,平方 阶 )( 2nO,立方 阶 )( 3nO
、指 数阶 ).2( nO
2.算法的存储空间需求
算法所需存储空间可用空间复杂度 (space complexity)
来度量,记作
)).(()( nfOnS ?
其中 n为问题的规模 (或大小 ).
课外习题
教材,P.8第 4题
学习数据结构的意义
数据结构是计算机软件和应用专业的核心课程,也
是一门独立的课程, 随着计算机技术的发展,计算机应
用的普及,仅掌握计算机语言和程序设计的技巧与方法
而缺乏有关数据结构的知识,就难以应付众多复杂的课
题,不能有效地使用计算机,
数据结构在计算机科学有着十分重要的地位,它与
计算机软件 ﹑ 硬件以及数学有着密切的关系,是操作系
统 ﹑ 编译原理 ﹑ 数据库和人工智能等课程的基础,广泛
应用于信息科学 ﹑ 系统工程 ﹑ 应用数学以及各种工程技
术领域,
当今,计算机解决非数值性问题越来越多,数据元
素之间由简单联系变为往往无法用数学方程进行描述的
复杂结构, 人们认识到程序设计的实质是对确定的问题
选择一种好的结构从而设计出一种好的算法, 曾有学者
指出, 算法 +数据结构 =程序,这里,算法指的是对数据
运算的描述,数据结构指数据的逻辑结构和存储结构, 可
见程序设计的实质是对实际问题选择一种好的数据结构
从而设计出一个好的算法有效地解决问题,
在数据结构着门课程中,有些内容需用到 C语言中
的指针的概念, 因此,要求同学们务必认真地复习和深
入地掌握 C语言中有关指针的基本概念 ﹑ 相关的语句及
其应用, 否则,将给本门课程的学习 ﹑ 完成课外习题 ﹑
上机实习及最后的考试带来很大的困难,
