上章回顾
数据指针、函数指针和数组间的运算操作
注意讲述const 、define、enum、static等C关键词特点和区别 static几个重要的用法和特性
讲述C语言编程常见的几个错误 重点提示C语言编程的调试方案
第三章
第三章
数据结构与算法概述
数据结构与算法概述
本章结构
数据结构与算法
数据结构与算法
什么是数据结构
什么是数据结构
基本概念和术语
基本概念和术语
抽象数据类型的表示与实现
抽象数据类型的表示与实现
算法和算法分析
算法和算法分析
预习检查
什么是数据结构
常见的数据结构的形式有哪些
算法的时间复杂度是什么
算法的空间复杂度是什么
课程目标
了解数据结构的基本概念
理解常用术语
了解算法时间复杂度的分析与评价
了解算空间复杂度的分析与评价
2011-11-13 5
git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
3.1 什么是数据结构 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象
以及它们之间的关系和操作的学科。数据结构主要有三个方面的内容: 数据的逻辑结构、数据的存储结构和对数据的算法。
逻辑结构:反映数据之间的逻辑关系,是对数据之间关系的描述,主 要有集合、线性表、树、图等四种结构。
物理结构:反映数据在计算机内部的存储安排,是数据结构在计算机 中的实现方法。
主要有顺序、链接、散列、索引等四种基本存储结构,并可以根据需 要组合成其它更复杂的结构。
算法:数据进行处理的方法。
2011-11-13 6
3.1.1 数据结构示例 【例3-1】图书目录表
由于表中每条记录(表示每一本书)的登录号各不相 同,所以可用登录号来唯一地标识每条记录(一本图书)。 在计算机的数据管理中,能唯一地标识一条记录的数据项被 称为关键字。因为每本图书的登录排列位置有先后次序,所 以在表中会按登录号形成一种次序关系,即整个二维表就是 图书数据的一个线性序列。这种关系被称为线性结构。
git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
2011-11-13 7
git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
3.1.1 数据结构示例图表
表 3-1 图书目录表
登录号 书号 书名 作者 出版社 定价
1 ISBN 7-302-02368-9 / TP.1185 数据结构
严蔚敏 清华大学 22 谭浩强 清华大学 17.3
2 ISBN 7-302-00860-4 / TP.312
3 ISBN 7-5053-9279-4 / TP.311
C 程序设计 数据结构
徐孝凯 电子工业 29 张基温 电子工业 25 庞丽萍 华中科技大学 22.8
4 ISBN 7-5053-8168-7 / TP.4757
5 ISBN 7-5609-2351-8 / TP.316
计算机系统原理
操作系统原理
6 ISBN 7-304-01404-0 / TP.68
7 ISBN 7-5084-1648-1 / TP.706
数据库基础与应用 王 利
中央电大 23.3
中国水利水电 20 ..................
网页制作实例教程 齐建玲
git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
返回
2011-11-13 8
git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
3.1.1 磁盘目录结构和文件管理系统
bin
lib user etc zhao jiang shao li
math ds sw
queue stack tree
graph
这种关系很像自然界中的 树,所以称为目录树。如左图所 示。
root
描述磁盘目录和文件结构 时,假设每个磁盘包括一个根目 录(root)和若干个一级子目 录,每个一级子目录中又包含若 干个二级子目录....
在这种结构中,目录和目录以及目录和文件之间呈现出一对多 的非线性关系。即根root有多个下属(也称为后代),每一后代又
有属于自己的后代;而任一个子目录或文件都只有一个唯一的上级 git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
(也称为双亲)。称这种数学模型为树型数据结构。
2011-11-13 9
git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
3.1.1 教学计划编排问题
课程编号 课程名称 先修课程 C1 计算机导论 无
C2 数据结构
C3 汇编语言 C1
C4 C 程序设计 C1
C5 计算机图形学 C2,C3,C4
C6 接口技术
C7 数据库原理
C8 编译原理
C9 操作系统
C3 C2,C9 C4
C2
C4
C2 C8
C9 C7
C1,C4
C3 C1
C6
假如一个教学计划中包含许多课程。在课程之间,有些必须 按规定的先后次序排课,如:学C6课程必须先学C3课,学C3课程 必须先学C1课。这些课程之间存在先修和后续的关系。
在这种结构中,表示课程的数据之间呈现多对多的非线性关 git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
系,称这类数学模型为图形结构。
2011-11-13 10
git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
C5
3.1.1 图案例总结 图结构还有:多岔路口交通灯的控制和管理、煤气管道的铺
设造价等。
通过以上几例可以认为:数据结构就是研究数据的逻辑结构 和物理结构以及它们之间相互关系,并对这种结构定义相应的运 算,而且确保经过这些运算后所得到的新结构仍然是原来的结构 类型。
git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
2011-11-13 11
git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
3.1.2 基本概念和术语 1.数据(Data)
数据(Data):是对信息的一种符号表示。在计算机科学中是指所 有能输入到计算机中并被计算机程序处理的符号的总称。包括文
字、表格、图象等。 例如,一个图书管理程序所要处理的数据可能是一张表格。如表
1-1所示。
2.数据元素(DataElement)
数据元素(Data Element):是数据的基本单位,在计算机程序 中通常作为一个整体进行考虑和处理。
一个数据元素可由若干个数据项组成。数据项是数据的不可分 割的最小单位。git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
2011-11-13 12
git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
3.1.2 基本概念和术语 例如,在表3-1所示的图书目录表中,为了便于处理,把其中的每一行
(代表一本书)作为一个基本单位来考虑,故该数据由7个结点构成。 一般情况下,一个结点中含有若干个字段(也叫数据项)。字段是构
成数据的最小单位。
3.数据对象(Data Object)
数据对象(Data Object):是性质相同的数据元素的集合。是数据的一个
子集。
4.数据类型(Data Type)
数据结构(Data Structure):是相互之间存在一种或多种特定关系的数
据元素的集合。
git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
2011-11-13 13
git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
3.1.2 基本概念和术语 例如,整型、字符型、浮点型、双精度型等数据类型,分别是
一组相同结构的值以及在这些值上允许进行操作的总称。 5.抽象数据类型(Abstruct Data Type,简称
ADT) ADT是指一个数学模型以及定义在该模型上的一组的操作。可以
看作是数据的逻辑结构及其在逻辑结构上定义的操作。 抽象数据类型的定义仅取决于它的一组逻辑特性,而与其在计算
机内部如何表示和实现无关。
git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
2011-11-13 14
git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
3.1.3 数据结构
数据结构是研究数据元素(DataElement)之间抽象化的相互关系(逻辑结构)和
这种关系在计算机中的存储表示(物理结构),并对这种结构定义相适应的运算,设计 出相应的算法。
数据结构主要指逻辑结构和物理结构。
1.逻辑结构:
数据之间的相互关系称为逻辑结构。通常分为 4类基本结构:
集合 结构中的数据元素除了同属于一种类型外,别无其它关系。 线性结构 结构中的数据元素之间存在一对一的关系。
树型结构 结构中的数据元素之间存在一对多的关系。 图状结构或网状结构 结构中的数据元素之间存在多对多的关系。
git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git2011-11-13
15
3.1.3 数据结构
在表3-1所示的表格中,由7个结点 (数据元素)组成,每个数 据元素又包括6个数据项(字段)。各结点之间在逻辑上有一种线性 关系,它指出了7个结点在表中的排列顺序。
这张表的逻辑结构就是数据元素(或是结点、记录)之间的关 系。对于表中的任一个结点(记录),都只有一个前驱结点,也只
有一个后继结点,整个表只有一个开始结点和一个终端结点。 此表的逻辑结构是线性的。
git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
2011-11-13 16
git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
3.1.3 数据结构 四类数据基本结构的示意图:
(a)集合结构(b)线性结构(c)树型结构(d)图形结构
由以上例子可见,描述这类非数值计算问题的数学模型 和方法不再是数学方程,而是诸如线性表、树和图之类的数 据结构。
git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
2011-11-13 17
git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
3.1.3 数据结构 数据对象可以是有限的,也可以是无限的。
数据结构不同于数据类型,也不同于数据对象,它不仅要
描述数据类型的数据对象,而且要描述数据对象各元素之间的 相互关系。
git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
2011-11-13 18
git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
3.1.3 存储结构
2.存储结构: 数据结构在计算机中的存储表示称为数据的存储结构。它包括数据元
素的表示和关系的表示。 表3-1所示的表格数据在计算机中可以有多种存储表示:
数据既可以存放在一块连续的内存单元中,通过元素在存储器中的位置 来表示它们之间的逻辑关系(顺序);
也可以随机分布在内存中的不同位置,通过指针元素表示数据元素之间 的逻辑关系(链式)。这两种不同的表示方法对应有四种不同的存储结构 (亦称方式):
顺序存储结构、链式存储结构、索引存储结构和散列存储结构。 git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
2011-11-13 19
git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
3.1.3 存储结构
(1)顺序存储结构是把逻辑上相邻的结点存储在物理上相邻 的存储单元里,结点之间的逻辑关系由存储单元位置的邻接关 系来体现。
优点:占用较少的存储空间; 缺点:由于只能使用相邻的一整块存储单元,因此可能产生较
多的碎片现象。 顺序存储结构通常借助程序语言中的数组来描述。
顺序存储结构主要应用于线性的数据结构。 git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
2011-11-13 20
git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
3.1.3 存储结构
(2) 链式存储结构将结点所占的存储单元分为两部分,一部分存放结点 本身的信息,另一部分存放结点的后继结点地址,结点间的逻辑关系由附 加的指针字段表示。
链式存储结构常借助于程序语言的指针类型描述。 优点:不会出现碎片现象,充分利用所有的存储单元; 缺点:每个结点占用较多的存储空间。
(3)索引存储方式是用结点的索引号来确定结点的存储地址。
在储存结点信息的同时,要建立附加的索引表。
优点:检索速度快。
缺点:增加了附加的索引表,占用较多的存储空间;在增加和删除数据 时需要修改索引表而花费较多时间。
git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
2011-11-13 21
git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
3.1.3 存储结构
(4) 散列存储方式是根据结点的关键字值直接计算出该结 点的存储地址。通过散列函数把结点间的逻辑关系对应到不同 的物理空间。
优点:检索、增加和删除结点的操作都很快; 缺点:当采用不好的散列函数时可能出现结点存储单元的冲
突,为解决冲突需要附加时间和空间的开销。
git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
2011-11-13 22
git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
3.1.3 存储结构
3.数据的运算 数据运算定义在数据的逻辑结构上,即施加于数据的操作。
例如对一张表的记录进行查找、增加、删除、修改,这就是对数据的运 算。
4.数据结构三方面的关系 数据的逻辑结构、数据的存储结构及数据的运算三方面构成一个数据结
构的整体。 存储结构是对数据项的存储。同一逻辑结构可用不同存储结构就对应不同
的存储标识。 例如,线性表若采用顺序存储方式,称为顺序表;若采用链式存储方式,
称为链表;若采用散列存储方式,可称为散列表。 git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
2011-11-13 23
git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
3.2 算法描述
3.2.1算法(Algorithm) 1、算法:简单地说就是解决特定问题的方法。是对问题求
解过程的一种描述。 特定的问题可以是数值的,也可以是非数值的。
一个算法可以用自然语言、计算机程序设计语言或其它语言 (比如类C语言)来说明。
一般而言,描述算法最合适的语言是介于自然语言和程序 设计语言之间的类语言。如:类C,类pascal等。
git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
2011-11-13 24
git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
3.2 算法特点
2、算法的特点 算法是执行特定计算的有穷过程。这个过程有5个特点:
1)动态有穷;
2)确定性;
3)输入:具有0个或多个由外界提供的量(输入)。 4)输出:产生1个或多个结果。
5)可行性:
3.2.2算法描述 一个算法可以用自然语言、数字语言或流程图等来描述,也可以用
计算机高级程序语言来描述,如Pascal语言、C语言或伪代码等, 本书选用C语言作为描述算法的工具。
1.用自然语言描述算法 用日常的自然语言来描述算法(可以是英文,也可以是其它文字
语言)。 优点:简单,便于人们对算法的阅读。 缺点:不够严谨。
3.2.2算法描述 2.用流程图描述算法
使用程序流程图,N-S图等描述算法。特点是描述过程简洁、明 了。目前在一些高级语言程序设计中仍然被采用。
但用这两种方法描述的算法不能直接在计算机上执行,必须通 过编程将它转换成可执行程序。
3.用程序设计(C或C++)语言描述算法
可以直接使用程序设计语言(如C或C++)描述算法,但直接使用 程序设计语言不太容易且不直观,且需要借助于注释才能看明 白。
2011-11-13 27
3.2.2算法描述 为解决理解与执行的矛盾,常使用一种称为伪码(类)语言的
描述方法来进行算法描述。
类语言介于高级程序设计语言和自然语言之间,它忽略高级程 序设计语言中一些严格的语法规则与描述细节,因此它比程序设计 语言更容易描述和被人理解,而且比自然语言更接近程序设计语 言。它虽然不能直接执行但很容易被转换成高级语言。
2011-11-13 28
git@github.com:Kevin-Dfg/Data-Structures-and-Algorithm-Analysis-in-C.git
3.3 算法分析与评价
3.3.1 算法设计的要求 要设计一个好的算法通常要考虑以下要求。
(1)正确性(Correctness):算法的执行结果应当满足预先规定的功能和性能要 求。
(2)可读性(Readability):算法应当思路清晰、层次分明、简单明了、易读易 懂。以有利于阅读者对程序的理解。
(3)健壮性(Robustness):算法应具有容错处理。当输入非法数据时,算法应对 其作出反应并适当处理,不至引起严重后果。
(4)高效性和存储量需求:效率指算法执行的时间。对于解决同一问题的多个算 法,执行时间短的算法效率高。存储量需求指算法执行过程中所需要的最大存 储空间。
3.3.2算法效率的度量 1.时间复杂度(Time complexity)
一个算法的时间复杂度是指算法运行从开始到结束所需要的时 间。
通常是所处理问题规模的一个函数T(n) ,常采用数量级的形 式表示。记作:
T(n)=O(f(n)) 称T(n)为算法的(渐近)时间复杂度。
3.3.2算法的空间复杂度
2.空间复杂度(Space complexity) 一个算法的空间复杂度是指算法运行从开始到结束所需的存储量。 算法的存储量指的是算法执行过程中所需的最大存储空间。
算法执行期间所需要的存储量应该包括以下三部分:
(1) 输入数据所占空间;
(2) 程序本身所占空间;
(3) 辅助变量所占空间。
类似于算法的时间复杂度,通常以算法的空间复杂度作为算法所需存储空间 的量度。定义:S(n)=O(g(n))
称S(n)为算法的空间复杂度。
2011-11-13 31
阶段小节
链式存储的四种结构是什么 算法的空间复杂度是指什么
本章总结
数据结构与算法
数据结构与算法
什么是数据结构
什么是数据结构
基本概念和术语
基本概念和术语
主要讲述数据结构的基本概念
和术语
抽象数据类型的表示与实现
抽象数据类型的表示与实现
抽象数据类型的表示和实现
算法和算法分析
算法和算法分析
重点讲述算法的时间复杂度和
空间复杂度的分析
了解数据结构的定义
实验1 实验内容
题目:对冒泡排序算法进行时间复杂度和空间复杂度的分析
实验目的
理解算法分析的原理,掌握算法分析的操作
实验分析
时间复杂度根据循环的嵌套层次和隔层循环的次数
空间复杂度根据算法使用的资源的空间