算法与数据结构课件

1、算法与数据结构算法与数据结构1课程学时 总学时:36学时2本课程主要参考书1 宁正元等. 算法与数据结构（第二版）.清华大学出版社2 漆涛等. 算法与数据结构（C+版）.电子工业出版社课 前 简 介21课程学时课 前 简 介4课 前 简 介3学习成绩考核方法期末考试占70%平时(课堂作业+出勤）占30%4. 教师信息 任课教师：刘 玲 E-mail: 3816778483课 前 简 介3学习成绩考核方法5课 程 内 容第一章 绪论第二章 常用算法第三章 线性表第四章 栈与队列第五章 树与二叉树第六章 图与网第七章 检索及基本算法第八章 排序及基本算法4课 程 内 容第一章 绪论61.1 什么是

2、数据结构1.2 基本概念和术语1.3 算法和算法分析第1章 绪论51.1 什么是数据结构1.2 基本概念和术语1.3 1.1 什么是数据结构一、计算机的主要用途早期：主要用于数值计算(关键是列数学方程，输入输出都是数值，如根据半径求圆面积等)。后来：处理逐渐扩大到非数值计算领域(能处理多种复杂的具有一定结构关系的数据)，如人机博弈、各种管理系统等。61.1 什么是数据结构一、计算机的主要用途8二、什么是程序？Niklaus Wirth： Programs = Algorithm + Data Structures程序:算法: 数据结构: 计算机处理问题的指令集 处理问题的策略问题的数学模型1.

3、1 什么是数据结构例如：计算机和人对弈算法：?模型：?对弈的规则和策略棋盘及棋盘的格局7二、什么是程序？Niklaus Wirth：程序:计算机处理 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科(记忆)。三、数据结构研究的范畴1.1 什么是数据结构8 数据结构是一门研究非数值计算的程序设计问题中计算一、数据与数据结构1.数据：是对客观事物的符号表示，是所有能被输入到计算机中且能被计算机处理的符号的集合(如字母、汉字、数字等)。2.数据元素：是数据的基本单位，具有完整确定的实际意义。也是数据结构中讨论的基本单位(如一个学生记录)。 具有相同特性的数据

4、元素的集合称为数据对象(如全班同学的学生记录)。1.2 基本概念和术语9一、数据与数据结构1.数据：是对客观事物的符号表示，是所有能3.数据项：是构成数据元素的项目，是具有独立含义的最小标识单位，是数据结构中讨论的最小单位(如学号、姓名、性别等)。三者之间的关系： 数据项 组成 数据元素 数据 学号、 个人记录 通讯录一、数据与数据结构1.2 基本概念和术语103.数据项：是构成数据元素的项目，是具有独立含义的最小标识单4.数据结构：带结构的数据元素的集合。一、数据与数据结构1.2 基本概念和术语相同的数据+不同的结构不同的数据结构！不同的数据+相同的结构不同的数据结构！114.数据结构：带结

5、构的数据元素的集合。一、数据与数据结构1.5.数据的逻辑结构(理解)集合结构： 仅同属一个集合线性结构: 一对一（1:1) 树形结构: 一对多（1:n)网状结构: 多对多 (m:n)非线性线 性逻辑结构可细分为4类(记忆)： 指数据元素之间的(内在的、本质的)逻辑上的关系，它与数据的存储无关，独立于计算机。一、数据与数据结构1.2 基本概念和术语125.数据的逻辑结构(理解)集合结构： 仅同属一个集合非线性线存储结构可分为4大类：例：要存储一个整数对，有两种存储方式：顺序、链式、索引、散列79030260030004150302600300041579法1：地址 内容法2：地址 内容2字节 是

6、数据元素及其逻辑结构在存储器内的表示(或映像)。依赖于计算机。6.数据的物理结构/存储结构(理解)一、数据与数据结构1.2 基本概念和术语13存储结构可分为4大类：例：要存储一个整数对，有6.数据的物理结构/存储结构 数据元素及其逻辑结构在存储器内的映像 “数据元素”的映象？“逻辑结构”(用x, y表示)的映象？一、数据与数据结构1.2 基本概念和术语用二进制位串表示数据元素，如：(321)10 = (501)8 = (101000001)2 A = (101)8 = (001000001)2146.数据的物理结构/存储结构 数据元素及其逻辑结构在顺序映象：以相对的存储位置表示后继关系链式映象

7、:以附加信息(指针)表示后继关系y xx y6.数据的物理结构/存储结构 一、数据与数据结构1.2 基本概念和术语x, y15顺序映象：以相对的存储位置表示后继关系链式映象:以附加信7.数据结构的形式定义数据结构是一个二元组 Data_Structures = (D, S)其中:D 是数据元素的有限集， S 是 D上逻辑关系的有限集。一、数据与数据结构1.2 基本概念和术语简言之，数据对象及其上的关系称为数据结构167.数据结构的形式定义数据结构是一个二元组 Data_Str二、抽象数据类型 数据类型：是一个值的集合和定义在此集合上的一组操作(相当于运算符或操作符)的总称。 注意：不同类型的变

8、量，其所能取的值的范围不同，所能进行的运算不同。如：-9不能作开方运算！1.2 基本概念和术语ADT与DS的关系如同int与-9的关系。17二、抽象数据类型 数据类型：是一个值的集合和定义在此集二、抽象数据类型(Abstract Data Type，简称ADT) ADT是指一个数学模型(DS)以及定义在此数学模型上的一组操作(运算)。1.定义： ADT可用三元组表示： ADT = （D，S，P）数据对象D上的关系集D上的基本操作集1.2 基本概念和术语抽象数据类型和数据类型实质上是一个概念(基本数据类型由系统提供存储及运算的实现。ADT由程序员提供，属于用户自定义数据类型)18二、抽象数据类型

9、(Abstract Data Type，简称2. 定义格式 数据对象： D. 数据关系集合： R 基本操作集合P： ADT 类型名 ADT 类型名 基本操作定义格式：基本操作名(参数表) 初始条件： 操作结果：二、抽象数据类型1.2 基本概念和术语DS192. 定义格式 数据对象： ADT 类型名 例如，抽象数据类型复数的定义(程序员提供)： 数据对象： De1,e2e1,e2RealSet 数据关系： R | e1是复数的实数部分,e2是虚数部分 ADT Complex /复数类型基本操作：/运算符，系统不提供，由程序员定义 AssignComplex( &Z, v1, v2 ) Destr

10、oyComplex( &Z) GetReal( Z, &realPart ) GetImag( Z, &ImagPart ) Add( z1,z2, &sum ) ADT Complex1.2 基本概念和术语2. 定义格式20例如，抽象数据类型复数的定义(程序员提供)： AssignComplex( &Z, v1, v2 )操作结果：以参数v1 和v2 分别作为实部和虚部构造复数Z。DestroyComplex( &Z)操作结果：复数Z被销毁。 GetReal( Z, &realPart )初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。1.2 基本概念和术语GetIma

11、g( Z, &ImagPart )初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。Add( z1,z2, &sum )初始条件：z1, z2是复数。操作结果：用sum返回两个复数z1, z2 的和。 2. 定义格式21AssignComplex( &Z, v1, v2 )Des3.ADT的表示和实现(如何让计算机知道此用户自定义类型) 可通过基本数据类型如整型、实型等来表示和实现抽象数据类型。本课程用类C语言作为描述工具但上机时要用具体语言实现，如C或C+等二、抽象数据类型1.2 基本概念和术语ADT的定义及实现是本书重要内容，定义及实现了ADT之后，ADT就可以当作基本

12、数据类型一样使用。223.ADT的表示和实现(如何让计算机知道此用户自定义类型) typedef struct float realpart； float imagpart；complex；/DS的存储结构的定义/对DS的基本操作的函数原型说明void Assign( complex &Z, float realval, float imagval )；/构造复数 Z,其实部和虚部分别被赋以参数/ realval 和 imagval 的值例如，对前面定义的复数的表示和实现：1.2 基本概念和术语3.ADT的表示和实现23typedef struct /DS的存储结构的定义/float GetR

13、eal( cpmplex Z )； / 返回复数 Z 的实部值float Getimag( cpmplex Z )； / 返回复数 Z 的虚部值void add( complex z1, complex z2, complex &sum )； / 以 sum 返回两个复数 z1, z2 的和 /续，对DS的基本操作的函数原型说明1.2 基本概念和术语3.ADT的表示和实现24float GetReal( cpmplex Z )；flo/续，基本操作的函数实现void add( complex z1, complex z2, complex &sum ) / 以 sum 返回两个复数 z1, z

14、2 的和 sum.realpart = z1.realpart + z2.realpart; sum.imagpart = z1.imagpart + z2.imagpart; 其它省略 1.2 基本概念和术语定义及实现了Complex 之后，Complex 就可以当作基本数据类型一样使用。3.ADT的表示和实现25/续，基本操作的函数实现void add( complex 算法是为了解决某类问题而规定的一个有限长的操作序列。一、算法1.算法及其特性一个算法必须满足的重要特性：1.3 算法和算法分析1)有穷性:对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限

15、时间内完成。26 算法是为了解决某类问题而规定的一个有限长的操作序列。2)确定性:对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。一、算法1.算法及其特性1.3 算法和算法分析3)可行性：算法中的所有操作都必须足够基本， 可通过将已经实现的基本操作执行有限次来实现。272)确定性:对于每种情况下所应执行的操作，在算法中都有确切的4)有输入：作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。一、算法1.算法及其

16、特性1.3 算法和算法分析 5)有输出：它是一组与输入有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。284)有输入：作为算法加工对象的量值，通常体现为算法中的一组变注意：算法和程序的关系，二者含义相似，但不相同。程序不一定满足有穷性，可以死循环，如OS；程序中的指令必须是可执行的，算法中的操作无此限制；用计算机语言描述的算法是程序。一、算法1.算法及其特性1.3 算法和算法分析29注意：算法和程序的关系，二者含义相似，但不相同。一、算法1.2.算法的描述和实现描述-可采用自然语言、数学语言或伪代码。实现-必须借助程序设计语言提供的数据类型及其运算。本课程-采用类

17、C语言。一、算法1.3 算法和算法分析302.算法的描述和实现描述-可采用自然语言、数学语言或伪代二、算法设计的原则算法设计应考虑达到以下目标：1正确性2. 可读性3健壮性4高效率与低存储量1.3 算法和算法分析31二、算法设计的原则算法设计应考虑达到以下目标：1正确性2.1.正确性 首先，算法应当满足以特定的“规格说明”方式给出的需求。 其次，对算法是否“正确”的理解可以有以下四个层次：二、算法设计的原则1.3 算法和算法分析321.正确性 首先，算法应当满足以特定的“规格说明”方式给出3）程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；4）程序对于一切合法的

18、输入数据都能得出满足要求的结果。1）程序中不含语法错误；2）程序对于几组输入数据能够得出满足要求的结果；通常以第3层意义的正确性作为衡量一个算法是否合格的标准。1.正确性二、算法设计的原则1.3 算法和算法分析333）程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据2.可读性 算法主要是为了人的阅读与交流，其次才是为编写程序让计算机执行，因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。二、算法设计的原则1.3 算法和算法分析342.可读性 算法主要是为了人的阅读与交流，其次才是为编3.健壮性 当输入非法数据时，算法应进行相应处理，而不是产生莫名奇妙的结果。

19、处理方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。二、算法设计的原则1.3 算法和算法分析4.高效率与低存储量 通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间，两者都与问题的规模有关。353.健壮性 当输入非法数据时，算法应进行相应处理，而不三、算法效率的度量1.通常有两种度量算法效率的方法:事后统计法事前分析估算法缺点：必须执行程序；其它因素掩盖算法本质。1.3 算法和算法分析36三、算法效率的度量1.通常有两种度量算法效率的方法:事后统计2.和算法执行时间相关的因素：1)算法选用的策略2)问题的规模3)编写程序的

20、语言4)编译程序产生的机器代码的质量5)计算机执行指令的速度三、算法效率的度量1.3 算法和算法分析372.和算法执行时间相关的因素：1)算法选用的策略2)问题的规3.时间复杂度 一个特定算法的“运行工作量”的大小，只依赖于问题的规模(通常用整数n表示)。或者说，它是问题规模的函数。 假如：随着问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同，则可记作： T (n) = O(f(n)。称T(n)为算法的(渐近)时间复杂度。三、算法效率的度量1.3 算法和算法分析383.时间复杂度 假如：随着问题规模 n 的增长，复杂度高复杂度低3.时间复杂度时间复杂度T(n)按数量级递增顺

21、序为：三、算法效率的度量1.3 算法和算法分析39复杂度高复杂度低3.时间复杂度三、算法效率的度量1.3 算法4.时间复杂度的估算算法 = 控制结构 + 原操作 （基本数据类型的操作）算法的执行时间 = 原操作(i)的执行次数原操作(i)的执行时间 三、算法效率的度量1.3 算法和算法分析 因此，从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。404.时间复杂度的估算算法 = 控制结构 + 原操作算法的执行 程序段 语句频度 时间复杂度x+; 1 O(1) for (i=1; i=n; +i) x+; n O(n) for

22、(i=1; i=n; +i) for (j=1; j=n; +j) x+; n2 O(n2)for (i=1; i=n; +i) for (j=1; j=n; +j) for (k=1; k=n; +k) x+ n3 O(n3)基本操作: x+4.时间复杂度的估算三、算法效率的度量1.3 算法和算法分析41 程序段 四、算法的存储空间需求算法的空间复杂度定义为: 表示随着问题规模 n 的增大，算法运行所需存储量的增长率与 g(n) 的增长率相同。S(n) = O(g(n)1.输入数据所占空间2.程序本身所占空间3.辅助变量所占空间1.3 算法和算法分析 若输入数据所占空间只取决于问题本身，和算

23、法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。 若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。 若所需存储量依赖于特定的输入，则通常按最坏情况考虑。42四、算法的存储空间需求算法的空间复杂度定义为: 表示随数据结构数据结构数据元素数据项逻辑结构物理结构集合线性结构树结构图结构线性非线性顺序链式索引散列程序算法特性原则时间复杂度正确性可读性健壮性高效率低存储有穷性确定性可行性有输入有输出O (f(n)知识小结 1.熟悉各名词、术语的含义，理解和掌握DS、ADT等重要概念。 2.理解算法五个要素的确切含义。 3.掌握计算语句频度和估算算法时间复杂度的方法。43数据结构数据结构数据元素数据项逻辑结构物理结构集合