数据结构全册配套最完整精品课件3.ppt

1、数据结构全册配套最完整 精品课件3 2021-8-30 2021-8-30数据结构2 数据结构数据结构 2021-8-30数据结构3 教材教材：严蔚敏，吴伟民：严蔚敏，吴伟民：数据结构数据结构，第三版，第三版， 清华大学出版社，清华大学出版社，1992年年 课程安排：课程安排： 总总18周，授课周，授课16周，最后两周考核周，最后两周考核 预备知识：预备知识：熟练掌握熟练掌握C或或C+语言，尤其是语言，尤其是指针指针和和 类类 2021-8-30数据结构4 学习网址：学习网址： 1、视频、视频 http:/ 2、http:/ 参考书目：参考书目： 1 Williaw Ford et al.Da

2、ta Structures with C+.Prentice Hall Inc.,1996 2 数据结构数据结构刘大有等刘大有等高教出版社高教出版社 2021-8-30数据结构5 开设和学习本课程的意义所在： n生产方式的变革：材料、能源、信息；材料和 能源的迅速减少，使得人们最终将开发和应用 的重点日益转向到信息中来； n人们必须更加集约地利用地球上有限的物质资 源，同时，必须掌握更加有效的加工自然物手 段 高新技术； n信息技术（Information Technology，简称IT） 一直处于高新技术的核心地位； 2021-8-30数据结构6 计算机硬件技术 计算机软件技术 计算机通信技

3、术 数据的组成 常用的算法 软件设计和开发 软件的实现原理和技术 IT 计算机软件技术 数据的组成 常用的算法 软件的实现原理和技术 2021-8-30数据结构7 n加强“每一种数据结构都存在代价与效益”的 概念。 n学习一些最基本、最常用的数据结构。 n它们组成了一个程序员的基本数据结构工具 箱（toolkit）。 n掌握如何评估一个数据结构和算法的有效性。 n这些技术也使程序员能够判断自己或别人发 明的新数据结构的价值。 2021-8-30数据结构8 什么是数据结构 为什么要学习数据结构 如何评价一个算法 2021-8-30数据结构9 科学计算科学计算-非数值计算非数值计算 数值数值-结构

4、数据结构数据 随着社会的发展，计算机应用的范围已经深入到 社会的各个领域，计算机的应用已经不在局限于 科学计算，而是更多用于控制、管理及数据处理 等非数值计算。 相应的计算机加工处理的对象由纯粹的数值发展 到字符、表格和图像等具有一定结构的数据。 为了编写一个好程序，必须分析待处理对象的特 性以及各处理对象之间存在的关系。 2021-8-30数据结构10 n数据结构是介于数据结构是介于数学、计算机硬件和计算机软件数学、计算机硬件和计算机软件三者三者 之间的一门核心课程。之间的一门核心课程。 2021-8-30数据结构11 n1、算法和数据结构是计算机科学的两大支柱、算法和数据结构是计算机科学的

5、两大支柱 n计算机科学早期定义为：研究算法的科学计算机科学早期定义为：研究算法的科学 n 近期定义为：研究数据的科学近期定义为：研究数据的科学 n2、数据结构是程序设计的基础、数据结构是程序设计的基础 n3、是信息类学科的专业基础课程。、是信息类学科的专业基础课程。 算法数据结构程序算法数据结构程序 程序设计的程序设计的实质实质是对实际问题选择一种好的数据结构，是对实际问题选择一种好的数据结构， 加之设计一个好的算法，而好的算法在很大程度上取决加之设计一个好的算法，而好的算法在很大程度上取决 于描述实际问题的数据结构于描述实际问题的数据结构 2021-8-30数据结构12 1、掌握各类基本数据

6、结构类型和相应的存储结构、掌握各类基本数据结构类型和相应的存储结构 2、提高阅读和编写算法的能力、提高阅读和编写算法的能力 3、能针对给定问题，选择相适应的数据结构，并能、能针对给定问题，选择相适应的数据结构，并能 设计和分析算法。设计和分析算法。 2021-8-30数据结构13 n众所周知，计算机的程序是对信息进众所周知，计算机的程序是对信息进 行加工处理。在大多数情况下，这些行加工处理。在大多数情况下，这些 信息并不是没有组织，信息（数据）信息并不是没有组织，信息（数据） 之间往往具有重要的结构关系，这就之间往往具有重要的结构关系，这就 是数据结构的内容。那么，什么是数是数据结构的内容。那

7、么，什么是数 据结构呢？先看以下几个例子据结构呢？先看以下几个例子。 2021-8-30数据结构14 例例1、电话号码查询系统、电话号码查询系统 n 设有一个电话号码薄，它记录了设有一个电话号码薄，它记录了N个人的个人的 名字和其相应的电话号码，假定按如下形式安名字和其相应的电话号码，假定按如下形式安 排：排： n (a1，b1)(a2，b2)(an，bn) n 其中其中ai，bi(i=1，2n) 分别表示某人的名分别表示某人的名 字和对应的电话号码。要求设计一个算法，当字和对应的电话号码。要求设计一个算法，当 给定任何一个人的名字时，该算法能够打印出给定任何一个人的名字时，该算法能够打印出

8、此人的电话号码，如果该电话簿中根本就没有此人的电话号码，如果该电话簿中根本就没有 这个人，则该算法也能够报告没有这个人的标这个人，则该算法也能够报告没有这个人的标 志。志。 2021-8-30数据结构15 姓名姓名 电话号码电话号码 张三张三 张林张林 . . . 张杰张杰 李四李四 . . . 李中李中 姓地址 张 李 . . . . . . 例一：电话号码查询问题例一：电话号码查询问题 电话号码查询问题的索引存储电话号码查询问题的索引存储 2021-8-30数据结构16 n算法的设计，依赖于计算机如何存储人的名字和对应算法的设计，依赖于计算机如何存储人的名字和对应 的电话号码，或者说依赖于

9、名字和其电话号码的结构。的电话号码，或者说依赖于名字和其电话号码的结构。 n数据的结构，直接影响算法的选择和效率。数据的结构，直接影响算法的选择和效率。 n上述的问题是一种数据结构问题。可将名字和对应的上述的问题是一种数据结构问题。可将名字和对应的 电话号码设计成：二维数组、表、向量。电话号码设计成：二维数组、表、向量。 n假定名字和其电话号码逻辑上已安排成假定名字和其电话号码逻辑上已安排成N元向量的形元向量的形 式，它的每个元素是一个数对式，它的每个元素是一个数对(ai，bi)， 1in n数据结构还要提供每种结构类型所定义的各种运算的数据结构还要提供每种结构类型所定义的各种运算的 算法算法

10、 2021-8-30数据结构17 数据结构研究的内容(contd) n图书目录文件示例图书目录文件示例 001高等数学樊映川S01 002理论力学罗远祥L01 003高等数学华罗庚S01 004线性代数栾汝书S02 高等数学001,003, 理论力学002, 线性代数004, 樊映川001, 华罗庚 003, 栾汝书 004, L002, S001,00 3, 2021-8-30数据结构18 数据结构的定义数据结构的定义 通过以上例子可以直接认为：通过以上例子可以直接认为： 数据结构是一门研究非数值计算的程序设计问题中计算机的数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象操作对象

11、以及它以及它 们之间们之间关系和操作关系和操作等的学科。等的学科。 研究内容：研究内容： 1、数据结构是研究数据的逻辑结构和物理结构以及它们之间相互关系、数据结构是研究数据的逻辑结构和物理结构以及它们之间相互关系 2、并对每种结构定义相适应的各种运算、并对每种结构定义相适应的各种运算 3、设计出相应的算法、设计出相应的算法 4、分析算法的效率、分析算法的效率 2021-8-30数据结构19 一、术语一、术语 是信息的载体，能被计算机识别、存储、加工处理。是信息的载体，能被计算机识别、存储、加工处理。 数据的基本单位数据的基本单位, 即数据集合中的一个个体。也称即数据集合中的一个个体。也称元素元

12、素、 结点结点、顶点顶点、记录记录 是具有独立含义的是具有独立含义的最小最小标识单位标识单位 唯一唯一能识别一个数据元素的能识别一个数据元素的数据项数据项。 数据元素由数据元素由组成组成 2021-8-30数据结构20 具有具有性质相同性质相同的数据元素的集合，是数据的子集。的数据元素的集合，是数据的子集。 例如：例如： 数据集合数据集合D=0，1，。，。A，B，。，。Z 正整数正整数N=0,1, 字符字符C=A,B,Z 2021-8-30数据结构21 按某种按某种组织起来的一批数据组织起来的一批数据, ,应用计应用计 算机语言按一定的算机语言按一定的将其将其在计算机中在计算机中, , 在这些

13、数据上定义了若干基本在这些数据上定义了若干基本, ,并且讨论这并且讨论这 些基本些基本基于存储方式上基于存储方式上。 这种逻辑关系称为结构。常见结构：这种逻辑关系称为结构。常见结构： 1 1、集合、集合 2 2、线性结构（、线性结构（1 1对对1 1） 3 3、树形结构；（、树形结构；（1 1对多）对多） 4 4、图状结构或网状结构。（多对多）、图状结构或网状结构。（多对多） 2021-8-30数据结构22 n数据结构的形式定义为：数据结构是一个二元组：数据结构的形式定义为：数据结构是一个二元组： nData-Structure=(D，S) n其中：其中：D是数据元素的有限集，是数据元素的有限

14、集，S是是D上关系的有限集。上关系的有限集。 n例例 复数的数据结构定义如下：复数的数据结构定义如下： nComplex=(C，R) n其中：其中：C是含两个实数的集合是含两个实数的集合C1，C2，分别表示，分别表示 复数的实部和虚部。复数的实部和虚部。R=P，P是定义在集合上的一种是定义在集合上的一种 关系关系C1，C2。 n数据结构在计算机中的表示称为数据的物理结构，又数据结构在计算机中的表示称为数据的物理结构，又 称为存储结构。称为存储结构。 2021-8-30数据结构23 n数据对象可以是有限的，也可以是无限数据对象可以是有限的，也可以是无限 的。的。 n数据结构不同于数据类型，也不同

15、于数数据结构不同于数据类型，也不同于数 据对象，它不仅要描述数据类型的数据据对象，它不仅要描述数据类型的数据 对象，而且要描述数据对象各元素之间对象，而且要描述数据对象各元素之间 的相互关系。的相互关系。 2021-8-30数据结构24 是具有相同性质的计算机数据的集合及在这个是具有相同性质的计算机数据的集合及在这个 集合上的一组操作。按数据的不同特性：集合上的一组操作。按数据的不同特性： 2021-8-30数据结构25 n例例1、 在在FORTRAN语言中，语言中， n 变量的数据类型有整型、实型、和复数型变量的数据类型有整型、实型、和复数型 n例例2、在、在C语言中语言中 n 数据类型：基

16、本类型和构造类型数据类型：基本类型和构造类型 n 基本类型：整型、浮点型、字符型基本类型：整型、浮点型、字符型 n 构造类型：数组、结构、联合、指针、枚举型、自定构造类型：数组、结构、联合、指针、枚举型、自定 义义 n在某种意义上，数据结构可以看成是在某种意义上，数据结构可以看成是“一组具有相同结构的一组具有相同结构的 值值”，而结构类型可以看成由，而结构类型可以看成由一种数据结构一种数据结构和定义在其上的和定义在其上的 一组操作一组操作组成。组成。 2021-8-30数据结构26 n“抽象抽象”的意义在于数据类型的数学抽象特性的意义在于数据类型的数学抽象特性 n一个数学模型以及定义在该模型上

17、的一组操作。一个数学模型以及定义在该模型上的一组操作。 （ADT的定义仅取决于它的一组逻辑特性，而与其在的定义仅取决于它的一组逻辑特性，而与其在 计算机内部如何表示和实现无关。）计算机内部如何表示和实现无关。） n抽象数据类型实际上就是对该数据结构的定义。因为抽象数据类型实际上就是对该数据结构的定义。因为 它定义了一个数据的逻辑结构以及在此结构上的一组它定义了一个数据的逻辑结构以及在此结构上的一组 算法。算法。 n一个含抽象数据类型的软件模块应包括一个含抽象数据类型的软件模块应包括定义、表示和定义、表示和 实现实现3个部分个部分 n 用三元组描述如下：用三元组描述如下： n （，）（，）D是数

18、据对象，是数据对象，S是是D上的关系集，上的关系集， P是对是对D的操作集的操作集 2021-8-30数据结构27 格式： ADT抽象数据类型名 数据对象： 数据关系： 基本操作： ADT抽象数据类型名 基本操作定义格式： 基本操作名（参数表） 初始条件： 操作结果： 2021-8-30数据结构28 数据结构包括四方面的内容数据结构包括四方面的内容： 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 逻辑结构上的基本运算逻辑结构上的基本运算 存储结构上基本运算的实现存储结构上基本运算的实现 2021-8-30数据结构29 数据的逻辑结构数据的逻辑结构 指的是数据之间的逻辑关系，其独立

19、于具体指的是数据之间的逻辑关系，其独立于具体 的计算机，为具体问题抽象出来的数学模型的计算机，为具体问题抽象出来的数学模型。 （1）线性结构）线性结构 （2）非线性结构）非线性结构 特征：一个结点可能有多个直接前趋和直接后继特征：一个结点可能有多个直接前趋和直接后继。 特征：仅有一个开始结点和一个终端结点，并且特征：仅有一个开始结点和一个终端结点，并且 所有结点都最多只有一个直接前趋和一个直接后继所有结点都最多只有一个直接前趋和一个直接后继。 逻辑结构的分类逻辑结构的分类： 2021-8-30数据结构30 数据结构包括四方面的内容数据结构包括四方面的内容： 数据的逻辑结构数据的逻辑结构 数据的

20、存储结构数据的存储结构 逻辑结构上的基本运算逻辑结构上的基本运算 存储结构上基本运算的实现存储结构上基本运算的实现 2021-8-30数据结构31 指的是数据的逻辑结构在计算机中的存储实现，指的是数据的逻辑结构在计算机中的存储实现， 其依赖于具体的计算机语言其依赖于具体的计算机语言。 数据的逻辑结构和物理结构是密切联数据的逻辑结构和物理结构是密切联 系的两个方面，任何一个算法的系的两个方面，任何一个算法的设计设计 取决于选定的数据（逻辑）结构，而取决于选定的数据（逻辑）结构，而 算法的算法的实现实现依赖于采用的存储结构依赖于采用的存储结构 2021-8-30数据结构32 （1）顺序存储方法）顺

21、序存储方法 将逻辑上相邻的结点存储在物理位置上相邻的将逻辑上相邻的结点存储在物理位置上相邻的 存储单元里，结点间的逻辑关系由存储单元的邻接存储单元里，结点间的逻辑关系由存储单元的邻接 关系来体现。采用顺序存储方法所得到的存储表示关系来体现。采用顺序存储方法所得到的存储表示 称为称为顺序存储结构顺序存储结构。 （2）链接存储方法）链接存储方法 不要求逻辑上相邻的结点在物理位置上亦相不要求逻辑上相邻的结点在物理位置上亦相 邻，结点间的逻辑关系由存储结点时附加的指针邻，结点间的逻辑关系由存储结点时附加的指针 字段表示。采用链接存储方法所得到的存储表示字段表示。采用链接存储方法所得到的存储表示 称为称

22、为链式存储结构链式存储结构。 2021-8-30数据结构33 （4）散列存储方法）散列存储方法 根据结点的关键字直接计算出该结点的存储地根据结点的关键字直接计算出该结点的存储地 址，以实现对结点的存储和访问址，以实现对结点的存储和访问。 在存储结点信息的同时，还建立附加的索引表，索引在存储结点信息的同时，还建立附加的索引表，索引 表中的每一项称为索引项，其一般形式为：（关键字，地表中的每一项称为索引项，其一般形式为：（关键字，地 址）。址）。 （3）索引存储方法）索引存储方法 2021-8-30数据结构34 数据结构包括四方面的内容数据结构包括四方面的内容： 数据的逻辑结构数据的逻辑结构 数据

23、的存储结构数据的存储结构 逻辑结构上的基本运算逻辑结构上的基本运算 存储结构上基本运算的实现存储结构上基本运算的实现 2021-8-30数据结构35 每种逻辑结构都涉及到一些基本运算，这些每种逻辑结构都涉及到一些基本运算，这些 基本运算实际上是基本运算实际上是定义定义在抽象的数据上的一系列在抽象的数据上的一系列 操作。操作。最常用的运算有：检索、插入、删除、更最常用的运算有：检索、插入、删除、更 新、排序等。新、排序等。 2021-8-30数据结构36 数据结构包括四方面的内容数据结构包括四方面的内容： 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 逻辑结构上的基本运算逻辑结构上

24、的基本运算 存储结构上基本运算的实现存储结构上基本运算的实现 2021-8-30数据结构37 运算的实现实际上指的是采用怎样的步骤或运算的实现实际上指的是采用怎样的步骤或 方法去实现定义在逻辑结构上的运算的功能。方法去实现定义在逻辑结构上的运算的功能。 2021-8-30数据结构38 例例:计算机系学员的选课、业余爱好、担当职务情计算机系学员的选课、业余爱好、担当职务情 况统计如下：况统计如下： 学号学号选修课程选修课程爱好爱好职务职务 1B.F无无班长班长 2A.C 体育体育 3A.D.F体育体育体委体委 4D.E文艺文艺 5C.E文艺文艺 6D.F体育体育 7B.E 体育体育 8A.E体育

25、体育 9B.F文艺文艺文委文委 10B.D文艺文艺 2021-8-30数据结构39 学号学号选修课程选修课程爱好爱好职务职务 1B.F无无班长班长 2A.C 体育体育 3A.D.F体育体育体委体委 4D.E文艺文艺 5C.E文艺文艺 6D.F体育体育 7B.E 体育体育 8A.E体育体育 9B.F文艺文艺文委文委 10B.D文艺文艺 建立数据元素之间的逻辑结构建立数据元素之间的逻辑结构： 1 1。按学号顺序建立并表示。按学号顺序建立并表示 该集合的关系该集合的关系 1 2 3 4 5 6 7 8 9 10 线性结构：线性表线性结构：线性表 2。按职务和爱好建立关系。按职务和爱好建立关系 1 2

26、 3 9 6 7 84 5 10 非线性结构：树非线性结构：树 2021-8-30数据结构40 2、存储结构、存储结构 线性表线性表 1、逻辑结构、逻辑结构 a1+9 顺序表顺序表 a1 a1+1 a1+2 1 2 3 10 a10 链表链表 a1 1 2 3 10 a2 a3 2021-8-30数据结构41 2、存储结构、存储结构 树树 1、逻辑结构、逻辑结构 a1+9 顺序存储顺序存储 a1 a1+1 a1+2 1 3 9 10 -1 a1 a1 a1+2 链式存储链式存储 3 9 1 2 . 10 1 2 3 9 6 7 84 5 10 2021-8-30数据结构42 3、数据的运算：退

27、学、数据的运算：退学 插班插班 查看查看 删除删除 插入插入 查找查找 4、运算的实现：、运算的实现： a1+9 a1 a1+1 a1+2 1 2 3 10 a1 2 3 10 a2 a3 a10 1 2021-8-30数据结构43 4、运算的实现：、运算的实现： 3、数据的运算：退学、数据的运算：退学 插班插班 查看查看 删除删除 插入插入 查找查找 a1+9 a1 a1+1 a1+2 1 2 3 10 a1+9 a1 2 3 10 a2 a3 a10 1 2021-8-30数据结构44 说明：说明： 同一批数据可以抽象出不同的逻辑结构同一批数据可以抽象出不同的逻辑结构 同一逻辑结构采用不同

28、的存储方法，可以得同一逻辑结构采用不同的存储方法，可以得 到不到不 同的存储结构，并冠以不同的名称；同的存储结构，并冠以不同的名称； 存储方法可以单独使用，也可以结合起来使存储方法可以单独使用，也可以结合起来使 用；用； 数据结构的逻辑结构、存储结构、运算三个数据结构的逻辑结构、存储结构、运算三个 方面是一个整体；方面是一个整体； 运算是数据结构的重要方面运算是数据结构的重要方面 2021-8-30数据结构45 逻辑结构上定义的定义的基本运算在存储结构上的 实现是通过算法来描述的。 一、算法定义一、算法定义 算法（算法（algorithm）是对特定问题求解 步骤的一种描述，由有限的指令序列构成

29、，其 中每一条指令表示一个或多个操作。 2021-8-30数据结构46 二、算法应具有的五个特性二、算法应具有的五个特性： （1）输入）输入(Input) 一个算法有零个或多个的输入，它们一个算法有零个或多个的输入，它们 是算法开始前给出的最初量。是算法开始前给出的最初量。 （2）输出）输出(Output) 一个算法至少有一个输出，它们是同输入一个算法至少有一个输出，它们是同输入 有某种关系的量有某种关系的量 （3）有穷性）有穷性(Finite)算法执行有穷步运算后能够终止，且每一算法执行有穷步运算后能够终止，且每一 步都可以在有穷时间内完成。步都可以在有穷时间内完成。 （4）确定性）确定性(

30、Definite )每一条指令必须有确切的含义，无二每一条指令必须有确切的含义，无二 义性。相同输入只能产生相同输出。义性。相同输入只能产生相同输出。 （5）可行性）可行性(Effective) 每种运算都是相当基本的、行得通的，每种运算都是相当基本的、行得通的， 原则上能精确实施。原则上能精确实施。 2021-8-30数据结构47 一个算法可以用自然语言自然语言、数学语言数学语言或约定的符号语言约定的符号语言 来描述。本书用C语言语言描述算法。 四、算法描述四、算法描述 三、算法与程序的关系三、算法与程序的关系 区别区别：1、程序不一定满足有穷性、程序不一定满足有穷性 2、程序中的指令必须是

31、机器可执行的，算法中的指、程序中的指令必须是机器可执行的，算法中的指 令则无此限制令则无此限制 联系联系：算法用机器可执行的语言来书写，就变成一个程序。算法用机器可执行的语言来书写，就变成一个程序。 2021-8-30数据结构48 一、算法评价五要素一、算法评价五要素 1、程序不包含语法错误； 2、程序对于几组输入数据能够得出满 足规格说明要求的结果 3、程序对于精心选择的典型、苛刻而 带有刁难性的几组数据都能产生满足 规格说明要求的结果， 4、程序对于一切合法输入数据都能产 生满足规格说明要求的结果 2021-8-30数据结构49 二、算法运行时间二、算法运行时间 要素要素 （1）对源程序进

32、行编译所需的时间）对源程序进行编译所需的时间 （2）程序运行时所需数据输入的时间）程序运行时所需数据输入的时间 （3）机器执行每条指令所需时间）机器执行每条指令所需时间 （4）程序中的每条指令重复执行的次数）程序中的每条指令重复执行的次数。 假设每条指令执行所需时间为单位时间。算法的时间耗费假设每条指令执行所需时间为单位时间。算法的时间耗费 T(n)可以用可以用每条指令重复执行的次数每条指令重复执行的次数（也称语句频度（也称语句频度 Frequency Count）之和进行度量，）之和进行度量， 2021-8-30数据结构50 例例1.4 求两个求两个n阶方阵的乘积阶方阵的乘积 C=AB,其算

33、法描述如下：其算法描述如下： #define n 自然数自然数 matrixmlt(a,b,c) float an,bn,cn; int i,j,k; (1) for (i=0;in;i+) (2) for(j=0;jn;j+) (3) cij=0; (4) for(k=0;k=n0, 都有都有T(n)=c.f(n)成立，成立，则则称称T的阶不高于的阶不高于f的阶的阶， 并记作并记作T(n)=O(f(n)。 该式表示随问题规模该式表示随问题规模n的增大，算法执行时间的增的增大，算法执行时间的增 长率和长率和f(n)的增长率相同，称作算法的的增长率相同，称作算法的渐近时间复渐近时间复 杂度杂度，

34、简称，简称时间复杂度时间复杂度 三、（渐进）时间复杂度三、（渐进）时间复杂度(O(f(n) 2021-8-30数据结构53 常见的时间复杂度有：常数阶常见的时间复杂度有：常数阶O(1)、对数阶对数阶 O(log2n)、线性阶、线性阶O(n)、线性对数阶、线性对数阶O(n log2n)、 平方阶平方阶O(n2)、 立方阶立方阶O(n3)、k次方阶次方阶 O(nk)、指数阶、指数阶O(2n)。 三、（渐进）时间复杂度三、（渐进）时间复杂度(O(f(n) 2021-8-30数据结构54 例一：交换例一：交换a和和b的内容的内容 temp=a; a=b; b=temp; T(n)=O(1) 2021-

35、8-30数据结构55 例二：变量记数之一例二：变量记数之一 (1)x=0;y=0; (2)for(k=1;k=n;k+) (3)x+; (4)for(i=1;i=n;i+) (5)for(j=1;j=n;j+) (6)y+; 频度最大的语句是（频度最大的语句是（6），）， 且且f(n)=n 2，所以该程序段，所以该程序段 的时间复杂度为的时间复杂度为T(n)=O(n 2) 2021-8-30数据结构56 例二：变量记数之二例二：变量记数之二 (1)x=1； (2)for(i=1;i=n;i+) (3) for(j=1;j=i;j+) (4) for(k=1;k=j;k+) (5)x+; 频度最

36、大的语句是（频度最大的语句是（5），）， 且且f(n)=? 。 n i i j n i n i i j j k nOiij 111 3 111 )()1(1 所以该程序段的时间复杂度所以该程序段的时间复杂度 为为T(n)=O(n 3) 2021-8-30数据结构57 四、最坏时间复杂度和平均时间复杂度四、最坏时间复杂度和平均时间复杂度 很多算法的时间复杂度不仅仅是问题规模的函 数，还与它所处理的数据集的状态有关，在这 种情况下，通常是根据数据集中可能出现的最 坏情况，估计出算法的最坏时间复杂度最坏时间复杂度。 有时对数据集的分布作出某种假设（如等概 率），讨论算法的平均时间复杂度平均时间复杂度

37、。 2021-8-30数据结构58 例：例： 在数组在数组An中查找值为中查找值为K的元素，若找到，则返回位置的元素，若找到，则返回位置 I(0=I=0) (4) return I; 最坏事件时间复杂度最坏事件时间复杂度T(n)=n 2021-8-30数据结构59 五、空间复杂度五、空间复杂度(Space Complexity) S(n)： 算法所耗费的存储空间，仍是问题规模算法所耗费的存储空间，仍是问题规模n的函数。的函数。 记作：记作：S(n)=O(f(n) 2021-8-30数据结构60 1、掌握数据、数据元素、数据结构等基本概念。、掌握数据、数据元素、数据结构等基本概念。 2、掌握数据

38、逻辑结构和物理结构的分类。、掌握数据逻辑结构和物理结构的分类。 3、学会算法分析的基本方法。、学会算法分析的基本方法。 2021-8-30数据结构61 习题 n1、简述下列术语：数据、数据元素、数据对 象、数据结构 n2、判断以下算法A和B处语句的语句频度，并 计算该算法的时间复杂度。 nfor（ i=1,in-1,i+) ny+, n for(j=0,j2n,j+) n x=x+1; n n 2021-8-30数据结构62 习题： n3、计算机算法指的是_ nA、计算方法 B、排序方法 nC、解决某一问题的有限指令序列 nD、调度方法 2021-8-30数据结构63 C语言语法结构简介语言语

39、法结构简介 1. C程序是由函数构成的程序是由函数构成的 2. 函数的组成函数的组成 函数说明部分函数说明部分: 函数类型函数类型 函数名函数名( 形式参数表列形式参数表列 ) 函数体函数体: 变量说明部分变量说明部分 语句部分语句部分 int max ( x , y ) 函数类型函数类型函数名函数名 形参表列形参表列 形式参数说明形式参数说明 int x , y; 形参类型形参类型 形参形参 一个程序有且仅有一个一个程序有且仅有一个main函数函数是程函数函数是程 序的基本单位，被调函数既可以是系统提供的库函序的基本单位，被调函数既可以是系统提供的库函 数，也可以是自定义函数。数，也可以是自

40、定义函数。 一、函数形式一、函数形式 2021-8-30数据结构64 3. 一个一个C程序总是从程序总是从main函数开始执行，而不论函数开始执行，而不论 main在整个函数中的位置如何在整个函数中的位置如何 4. C程序书写格式自由，一行内可以写几个语句，程序书写格式自由，一行内可以写几个语句， 一个语句也可以写在几行上一个语句也可以写在几行上 5. 分号；是语句结束符，是语句的一部分分号；是语句结束符，是语句的一部分 6. 函数通常结束于函数通常结束于return语句。语句。 2021-8-30数据结构65 二、条件语句的两种格式二、条件语句的两种格式 1. 1. 格式格式 1 1： if

41、 ( if ( 表达式表达式 ) ) 语句语句 例例: if (a0) a=-a;: if (a0) a=-a; printf( printf(“a=%dna=%dn”,a);,a); 2. 2. 格式格式 2 2： if ( if ( 表达式表达式 ) ) 语句语句 1 1 else else 语句语句 2 2 3. 3. 功能：功能： 把把( ( 表达式表达式 ) )作为条件，根作为条件，根 据其值真假选择所要执行的操作据其值真假选择所要执行的操作 条件条件 语句语句 真真(非非0) 假假(0) 格式格式1 1 条件条件 语句语句1 真真(非非0)假假(0) 语句语句2 格式格式2 202

42、1-8-30数据结构66 1 1、whilewhile循环语句循环语句 2 2）执行过程）执行过程: : 计算计算E E的值的值 若若E E非非0, 0, 则执行则执行S, S, 然后转然后转 若若E E为为0, 0, 则退出循环则退出循环, , 执行该循环后的语句执行该循环后的语句 1 1）格式）格式 while ( while ( 表达式表达式E )E ) 循环体语句序列循环体语句序列S S E S 0 0 非非0 0 3 3）特点）特点: : 先判断表达式，后执行语句先判断表达式，后执行语句, , 因此因此, , 若进入若进入 whilewhile循环时循环时E E的值就是的值就是0 0

43、，则语句，则语句S S一次也不执行一次也不执行 三、循环语句的三种格式三、循环语句的三种格式 2021-8-30数据结构67 2、 dowhile 循环语句循环语句 2 2）执行过程）执行过程: : 执行循环体执行循环体S S 计算计算E E值值 若若E E的值为真的值为真( (非非0), 0), 则转则转 若若E E的值为假的值为假(0), (0), 则结束循环则结束循环 1 1）格式）格式: : do do 循环体语句序列循环体语句序列S S while ( while ( 表达式表达式E);E); E S 0 0 非非0 0 3 3）特点）特点: : 先执行循环体，再判断表达式，因此循环

44、体至少执行一次先执行循环体，再判断表达式，因此循环体至少执行一次 三、循环语句的三种格式三、循环语句的三种格式 2021-8-30数据结构68 3、 for 循环语句循环语句 2 2） 执行过程执行过程: : 计算计算E1E1 计算计算E2E2值值 若若E2E2非非0,0,则执行循环体则执行循环体S,S,再计算再计算E3,E3,转转 若若E2E2为为0,0,则结束循环则结束循环 1 1） 格式格式: : for( for(表达式表达式E1;E1;表达式表达式E2;E2;表达式表达式E3) E3) 循环体语句序列循环体语句序列S S 计算计算E2E2 S 假假(0)(0) 真真( (非非0)0)

45、 计算计算E1E1 计算计算E3E3 三、循环语句的三种格式三、循环语句的三种格式 注意：上述的三种循环体语句中，均可注意：上述的三种循环体语句中，均可 使用使用break语句语句 退出循环体。退出循环体。 2021-8-30数据结构69 四、情况语句四、情况语句( (开关语句开关语句) ) 1. 1. 格式格式: : switch ( switch (表达式表达式) ) case case 常量表达式常量表达式 1: 1: 语句语句1 1； breakbreak； case case 常量表达式常量表达式 2: 2: 语句语句2 2； breakbreak； case case 常量表达式常

46、量表达式 n: n: 语句语句n n； breakbreak； default : default : 语句语句n+1n+1； breakbreak； 2. 2. 执行过程执行过程: : 先计算表达式的值先计算表达式的值; ; 按按casecase语句的顺序测试表达式的值与哪个语句的顺序测试表达式的值与哪个casecase常量值常量值 相同若与某一常量相同相同若与某一常量相同, , 控制转向该控制转向该casecase常量后面的语句常量后面的语句 开始执行开始执行; ; 否则否则, , 在有在有defaultdefault时时, , 执行执行defaultdefault后的语句后的语句, ,无

47、无 defaultdefault时时, , 什么也不执行什么也不执行 2021-8-30数据结构70 五、赋值语句五、赋值语句 1. 1. = = ； 或或 op= op= ； 例例 sum=3 sum=3 * * 75 ; 75 ; sum+=25; sum+=25; 2. 2. 变量变量+ + + 变量加变量加1 1后赋值给变量后赋值给变量 3. 3. 变量变量- - - 变量减变量减1 1后赋值给变量后赋值给变量 2021-8-30数据结构71 六、输入、输出语句六、输入、输出语句 1、字符：用函数、字符：用函数getchar和和putchar实现。实现。 1 1） putchar(c)

48、 ;putchar(c) ; 功能：输出字符变量功能：输出字符变量c c的值，的值，c c可以是字符可以是字符 变量或整型变量变量或整型变量 2 2） getchar( ) ;getchar( ) ; 功能：从终端功能：从终端( (或系统隐含的输入设备或系统隐含的输入设备) )输输 入一个字符入一个字符, , 并把得到的字符作为函数的返回值并把得到的字符作为函数的返回值. . 2021-8-30数据结构72 2、其它数据：用函数、其它数据：用函数scanf和和printf实现其输入和输出。实现其输入和输出。 1 1）printf( printf( 格式控制，输出表列格式控制，输出表列 ) )

49、printf(“a=%d,b=%d”, a , b) ; 2 2）scanf( scanf( 格式控制参数格式控制参数, , 地址地址1, 1, 地址地址2, 2, ) ;) ; 功能功能: : 按格式控制参数的要求从终端上把数据传送按格式控制参数的要求从终端上把数据传送 到地址参数所指的内存空间中，其中到地址参数所指的内存空间中，其中地址地址可以是变量可以是变量 的地址，也可以是字符串的首地址的地址，也可以是字符串的首地址 七、注解形式七、注解形式 /*字符串字符串*/ 一、为什么要规定数据类型：一、为什么要规定数据类型： C C语言规定，在程序中用到的每一个变量都要指定它们属于哪一种类语言

50、规定，在程序中用到的每一个变量都要指定它们属于哪一种类 型，这是因为：型，这是因为： 1. 1.不同类型的数据在内存中占不同长度的存储区，而且数据在计算机不同类型的数据在内存中占不同长度的存储区，而且数据在计算机 内的表示形式也不同内的表示形式也不同. . 例如：一般微机例如：一般微机 2bytes 2bytes 存放一个整型存放一个整型 4bytes 4bytes 存放一个实型存放一个实型 2.2.一种数据对应着一个值的范围一种数据对应着一个值的范围 int -32768int -32768 3276732767float 10float 10-38 -38 10 1038 38之间 之间