《数据结构》全册配套课件.ppt

1、数据结构全册配套课件数据结构全册配套课件2022-1-162022-1-16数据结构2数据结构数据结构 2022-1-16数据结构3教材教材：严蔚敏，吴伟民：严蔚敏，吴伟民：数据结构数据结构，第三版，第三版，清华大学出版社，清华大学出版社，1992年年课程安排：课程安排：总总18周，授课周，授课16周，最后两周考核周，最后两周考核预备知识：预备知识：熟练掌握熟练掌握C或或C+语言，尤其是语言，尤其是指针指针和和类类2022-1-16数据结构4开设和学习本课程的意义所在：n生产方式的变革：材料、能源、信息；材料和能源的迅速减少，使得人们最终将开发和应用的重点日益转向到信息中来；n人们必须更加集约

2、地利用地球上有限的物质资源，同时，必须掌握更加有效的加工自然物手段 高新技术；n信息技术（Information Technology，简称IT）一直处于高新技术的核心地位；2022-1-16数据结构5计算机硬件技术计算机软件技术计算机通信技术数据的组成常用的算法软件设计和开发软件的实现原理和技术IT计算机软件技术数据的组成常用的算法软件的实现原理和技术2022-1-16数据结构6n加强“每一种数据结构都存在代价与效益”的概念。n学习一些最基本、最常用的数据结构。n它们组成了一个程序员的基本数据结构工具箱（toolkit）。n掌握如何评估一个数据结构和算法的有效性。n这些技术也使程序员能够判断

3、自己或别人发明的新数据结构的价值。2022-1-16数据结构7 什么是数据结构 为什么要学习数据结构 如何评价一个算法2022-1-16数据结构8科学计算科学计算-非数值计算非数值计算数值数值-结构数据结构数据随着社会的发展，计算机应用的范围已经深入到社会的各个领域，计算机的应用已经不在局限于科学计算，而是更多用于控制、管理及数据处理等非数值计算。相应的计算机加工处理的对象由纯粹的数值发展到字符、表格和图像等具有一定结构的数据。为了编写一个好程序，必须分析待处理对象的特性以及各处理对象之间存在的关系。2022-1-16数据结构9n数据结构是介于数据结构是介于数学、计算机硬件和计算机软件数学、计

4、算机硬件和计算机软件三者三者之间的一门核心课程。之间的一门核心课程。2022-1-16数据结构10n1、算法和数据结构是计算机科学的两大支柱、算法和数据结构是计算机科学的两大支柱n计算机科学早期定义为：研究算法的科学计算机科学早期定义为：研究算法的科学n 近期定义为：研究数据的科学近期定义为：研究数据的科学n2、数据结构是程序设计的基础、数据结构是程序设计的基础n3、是信息类学科的专业基础课程。、是信息类学科的专业基础课程。算法数据结构程序算法数据结构程序 程序设计的程序设计的实质实质是对实际问题选择一种好的数据结构，是对实际问题选择一种好的数据结构，加之设计一个好的算法，而好的算法在很大程度

5、上取决加之设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构于描述实际问题的数据结构2022-1-16数据结构111、掌握各类基本数据结构类型和相应的存储结构、掌握各类基本数据结构类型和相应的存储结构2、提高阅读和编写算法的能力、提高阅读和编写算法的能力3、能针对给定问题，选择相适应的数据结构，并能、能针对给定问题，选择相适应的数据结构，并能设计和分析算法。设计和分析算法。2022-1-16数据结构12n众所周知，计算机的程序是对信息进众所周知，计算机的程序是对信息进行加工处理。在大多数情况下，这些行加工处理。在大多数情况下，这些信息并不是没有组织，信息（数据）信息并不是没有

6、组织，信息（数据）之间往往具有重要的结构关系，这就之间往往具有重要的结构关系，这就是数据结构的内容。那么，什么是数是数据结构的内容。那么，什么是数据结构呢？先看以下几个例子据结构呢？先看以下几个例子。2022-1-16数据结构13例例1、电话号码查询系统、电话号码查询系统n 设有一个电话号码薄，它记录了设有一个电话号码薄，它记录了N个人的个人的名字和其相应的电话号码，假定按如下形式安名字和其相应的电话号码，假定按如下形式安排：排：n (a1，b1)(a2，b2)(an，bn)n 其中其中ai，bi(i=1，2n) 分别表示某人的名分别表示某人的名字和对应的电话号码。要求设计一个算法，当字和对应

7、的电话号码。要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标这个人，则该算法也能够报告没有这个人的标志。志。2022-1-16数据结构14姓名姓名 电话号码电话号码 张三张三 张林张林 . . . 张杰张杰 李四李四 . . . 李中李中 姓地址张李.例一：电话号码查询问题例一：电话号码查询问题电话号码查询问题的索引存储电话号码查询问题的索引存储2022-1-16数据结构15n算法的设计，依赖于计算机如何存储人的名字和对应算

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

9、数据结构还要提供每种结构类型所定义的各种运算的算法算法2022-1-16数据结构16数据结构研究的内容(contd)n图书目录文件示例图书目录文件示例001高等数学樊映川S01002理论力学罗远祥L01003高等数学华罗庚S01004线性代数栾汝书S02高等数学001,003,理论力学002,线性代数004,樊映川001,华罗庚 003,栾汝书 004,L002,S001,003,2022-1-16数据结构17数据结构的定义数据结构的定义 通过以上例子可以直接认为：通过以上例子可以直接认为： 数据结构是一门研究非数值计算的程序设计问题中计算机的数据结构是一门研究非数值计算的程序设计问题中计算机

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

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

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

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

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

15、型：整型、浮点型、字符型n 构造类型：数组、结构、联合、指针、枚举型、自定构造类型：数组、结构、联合、指针、枚举型、自定义义n在某种意义上，数据结构可以看成是在某种意义上，数据结构可以看成是“一组具有相同结构的一组具有相同结构的值值”，而结构类型可以看成由，而结构类型可以看成由一种数据结构一种数据结构和定义在其上的和定义在其上的一组操作一组操作组成。组成。2022-1-16数据结构25n“抽象抽象”的意义在于数据类型的数学抽象特性的意义在于数据类型的数学抽象特性n一个数学模型以及定义在该模型上的一组操作。一个数学模型以及定义在该模型上的一组操作。（ADT的定义仅取决于它的一组逻辑特性，而与其在

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

17、T抽象数据类型名数据对象：数据关系：基本操作：ADT抽象数据类型名基本操作定义格式：基本操作名（参数表）初始条件：操作结果：2022-1-16数据结构27数据结构包括四方面的内容数据结构包括四方面的内容： 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 逻辑结构上的基本运算逻辑结构上的基本运算 存储结构上基本运算的实现存储结构上基本运算的实现2022-1-16数据结构28数据的逻辑结构数据的逻辑结构 指的是数据之间的逻辑关系，其独立于具体指的是数据之间的逻辑关系，其独立于具体的计算机，为具体问题抽象出来的数学模型的计算机，为具体问题抽象出来的数学模型。（1）线性结构）线性结构（2）

18、非线性结构）非线性结构特征：一个结点可能有多个直接前趋和直接后继特征：一个结点可能有多个直接前趋和直接后继。 特征：仅有一个开始结点和一个终端结点，并且特征：仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继所有结点都最多只有一个直接前趋和一个直接后继。逻辑结构的分类逻辑结构的分类：2022-1-16数据结构29数据结构包括四方面的内容数据结构包括四方面的内容： 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 逻辑结构上的基本运算逻辑结构上的基本运算 存储结构上基本运算的实现存储结构上基本运算的实现2022-1-16数据结构30 指的是数据的逻辑结构在

19、计算机中的存储实现，指的是数据的逻辑结构在计算机中的存储实现，其依赖于具体的计算机语言其依赖于具体的计算机语言。数据的逻辑结构和物理结构是密切联数据的逻辑结构和物理结构是密切联系的两个方面，任何一个算法的系的两个方面，任何一个算法的设计设计取决于选定的数据（逻辑）结构，而取决于选定的数据（逻辑）结构，而算法的算法的实现实现依赖于采用的存储结构依赖于采用的存储结构2022-1-16数据结构31（1）顺序存储方法）顺序存储方法 将逻辑上相邻的结点存储在物理位置上相邻的将逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接存储单元里，结点间的逻辑关系由存储单元的邻接关系

20、来体现。采用顺序存储方法所得到的存储表示关系来体现。采用顺序存储方法所得到的存储表示称为称为顺序存储结构顺序存储结构。（2）链接存储方法）链接存储方法 不要求逻辑上相邻的结点在物理位置上亦相不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由存储结点时附加的指针邻，结点间的逻辑关系由存储结点时附加的指针字段表示。采用链接存储方法所得到的存储表示字段表示。采用链接存储方法所得到的存储表示称为称为链式存储结构链式存储结构。2022-1-16数据结构32（4）散列存储方法）散列存储方法 根据结点的关键字直接计算出该结点的存储地根据结点的关键字直接计算出该结点的存储地址，以实现对结点的存储和访

21、问址，以实现对结点的存储和访问。 在存储结点信息的同时，还建立附加的索引表，索引在存储结点信息的同时，还建立附加的索引表，索引表中的每一项称为索引项，其一般形式为：（关键字，地表中的每一项称为索引项，其一般形式为：（关键字，地址）。址）。（3）索引存储方法）索引存储方法2022-1-16数据结构33数据结构包括四方面的内容数据结构包括四方面的内容： 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 逻辑结构上的基本运算逻辑结构上的基本运算 存储结构上基本运算的实现存储结构上基本运算的实现2022-1-16数据结构34 每种逻辑结构都涉及到一些基本运算，这些每种逻辑结构都涉及到一些基本

22、运算，这些基本运算实际上是基本运算实际上是定义定义在抽象的数据上的一系列在抽象的数据上的一系列操作。操作。最常用的运算有：检索、插入、删除、更最常用的运算有：检索、插入、删除、更新、排序等。新、排序等。2022-1-16数据结构35数据结构包括四方面的内容数据结构包括四方面的内容： 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 逻辑结构上的基本运算逻辑结构上的基本运算 存储结构上基本运算的实现存储结构上基本运算的实现2022-1-16数据结构36 运算的实现实际上指的是采用怎样的步骤或运算的实现实际上指的是采用怎样的步骤或方法去实现定义在逻辑结构上的运算的功能。方法去实现定义在逻

23、辑结构上的运算的功能。2022-1-16数据结构37例例:计算机系学员的选课、业余爱好、担当职务情计算机系学员的选课、业余爱好、担当职务情况统计如下：况统计如下：学号学号选修课程选修课程爱好爱好职务职务1B.F无无班长班长2A.C体育体育3A.D.F体育体育体委体委4D.E文艺文艺5C.E文艺文艺6D.F体育体育7B.E体育体育8A.E体育体育9B.F文艺文艺文委文委10B.D文艺文艺2022-1-16数据结构38学号学号选修课程选修课程爱好爱好职务职务1B.F无无班长班长2A.C体育体育3A.D.F体育体育体委体委4D.E文艺文艺5C.E文艺文艺6D.F体育体育7B.E体育体育8A.E体育体

24、育9B.F文艺文艺文委文委10B.D文艺文艺建立数据元素之间的逻辑结构建立数据元素之间的逻辑结构：1 1。按学号顺序建立并表示。按学号顺序建立并表示该集合的关系该集合的关系1 2 3 4 5 6 7 8 9 10线性结构：线性表线性结构：线性表2。按职务和爱好建立关系。按职务和爱好建立关系1 2396 784 5 10非线性结构：树非线性结构：树2022-1-16数据结构392、存储结构、存储结构线性表线性表1、逻辑结构、逻辑结构a1+9顺序表顺序表 a1a1+1a1+212 3 10 a10链表链表 a112 3 10 a2a32022-1-16数据结构402、存储结构、存储结构树树1、逻辑

25、结构、逻辑结构a1+9顺序存储顺序存储 a1a1+1a1+213 910 -1a1a1a1+2链式存储链式存储 3 9 1 2 . 10 1 2396 784 5 102022-1-16数据结构413、数据的运算：退学、数据的运算：退学 插班插班 查看查看 删除删除插入插入查找查找4、运算的实现：、运算的实现：a1+9a1a1+1a1+212 310 a12 3 10 a2a3a1012022-1-16数据结构424、运算的实现：、运算的实现：3、数据的运算：退学、数据的运算：退学 插班插班 查看查看 删除删除插入插入查找查找a1+9a1a1+1a1+212 310 a1+9a12 3 10

26、a2a3a1012022-1-16数据结构43说明：说明：同一批数据可以抽象出不同的逻辑结构同一批数据可以抽象出不同的逻辑结构同一逻辑结构采用不同的存储方法，可以得同一逻辑结构采用不同的存储方法，可以得到不到不 同的存储结构，并冠以不同的名称；同的存储结构，并冠以不同的名称；存储方法可以单独使用，也可以结合起来使存储方法可以单独使用，也可以结合起来使用；用；数据结构的逻辑结构、存储结构、运算三个数据结构的逻辑结构、存储结构、运算三个方面是一个整体；方面是一个整体；运算是数据结构的重要方面运算是数据结构的重要方面2022-1-16数据结构44 逻辑结构上定义的定义的基本运算在存储结构上的实现是通

27、过算法来描述的。一、算法定义一、算法定义 算法（算法（algorithm）是对特定问题求解步骤的一种描述，由有限的指令序列构成，其中每一条指令表示一个或多个操作。2022-1-16数据结构45 二、算法应具有的五个特性二、算法应具有的五个特性：（1）输入）输入(Input) 一个算法有零个或多个的输入，它们一个算法有零个或多个的输入，它们是算法开始前给出的最初量。是算法开始前给出的最初量。（2）输出）输出(Output) 一个算法至少有一个输出，它们是同输入一个算法至少有一个输出，它们是同输入有某种关系的量有某种关系的量（3）有穷性）有穷性(Finite)算法执行有穷步运算后能够终止，且每一算

28、法执行有穷步运算后能够终止，且每一步都可以在有穷时间内完成。步都可以在有穷时间内完成。（4）确定性）确定性(Definite )每一条指令必须有确切的含义，无二每一条指令必须有确切的含义，无二义性。相同输入只能产生相同输出。义性。相同输入只能产生相同输出。（5）可行性）可行性(Effective) 每种运算都是相当基本的、行得通的，每种运算都是相当基本的、行得通的，原则上能精确实施。原则上能精确实施。 2022-1-16数据结构46一个算法可以用自然语言自然语言、数学语言数学语言或约定的符号语言约定的符号语言来描述。本书用C语言语言描述算法。四、算法描述四、算法描述三、算法与程序的关系三、算法

29、与程序的关系区别区别：1、程序不一定满足有穷性、程序不一定满足有穷性2、程序中的指令必须是机器可执行的，算法中的指、程序中的指令必须是机器可执行的，算法中的指令则无此限制令则无此限制联系联系：算法用机器可执行的语言来书写，就变成一个程序。算法用机器可执行的语言来书写，就变成一个程序。2022-1-16数据结构47一、算法评价五要素一、算法评价五要素 1、程序不包含语法错误；2、程序对于几组输入数据能够得出满足规格说明要求的结果3、程序对于精心选择的典型、苛刻而带有刁难性的几组数据都能产生满足规格说明要求的结果，4、程序对于一切合法输入数据都能产生满足规格说明要求的结果2022-1-16数据结构

30、48二、算法运行时间二、算法运行时间 要素要素 （1）对源程序进行编译所需的时间）对源程序进行编译所需的时间（2）程序运行时所需数据输入的时间）程序运行时所需数据输入的时间（3）机器执行每条指令所需时间）机器执行每条指令所需时间（4）程序中的每条指令重复执行的次数）程序中的每条指令重复执行的次数。 假设每条指令执行所需时间为单位时间。算法的时间耗费假设每条指令执行所需时间为单位时间。算法的时间耗费T(n)可以用可以用每条指令重复执行的次数每条指令重复执行的次数（也称语句频度（也称语句频度Frequency Count）之和进行度量，）之和进行度量，2022-1-16数据结构49例例1.4 求两

31、个求两个n阶方阵的乘积阶方阵的乘积 C=AB,其算法描述如下：其算法描述如下： #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)的增长率相同，称作算法的的增长率相同，

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

33、(1)2022-1-16数据结构54例二：变量记数之一例二：变量记数之一(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)2022-1-16数据结构55例二：变量记数之二例二：变量记数之二(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+;频度最大的语句是（频度最大

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

35、为K的元素，若找到，则返回位置的元素，若找到，则返回位置I(0=I=0)&(AI!=K)(3)I-;(4) return I;最坏事件时间复杂度最坏事件时间复杂度T(n)=n 2022-1-16数据结构58五、空间复杂度五、空间复杂度(Space Complexity) S(n)： 算法所耗费的存储空间，仍是问题规模算法所耗费的存储空间，仍是问题规模n的函数。的函数。记作：记作：S(n)=O(f(n)2022-1-16数据结构591、掌握数据、数据元素、数据结构等基本概念。、掌握数据、数据元素、数据结构等基本概念。2、掌握数据逻辑结构和物理结构的分类。、掌握数据逻辑结构和物理结构的分类。3、学

36、会算法分析的基本方法。、学会算法分析的基本方法。2022-1-16数据结构60习题n1、简述下列术语：数据、数据元素、数据对象、数据结构n2、判断以下算法A和B处语句的语句频度，并计算该算法的时间复杂度。nfor（ i=1,in-1,i+)ny+,n for(j=0,j2n,j+)n x=x+1;n n2022-1-16数据结构61习题：n3、计算机算法指的是_nA、计算方法 B、排序方法nC、解决某一问题的有限指令序列nD、调度方法2022-1-16数据结构62 C语言语法结构简介语言语法结构简介 1. C程序是由函数构成的程序是由函数构成的2. 函数的组成函数的组成 函数说明部分函数说明部

37、分:函数类型函数类型 函数名函数名( 形式参数表列形式参数表列 )函数体函数体: 变量说明部分变量说明部分 语句部分语句部分 int max ( x , y )函数类型函数类型函数名函数名形参表列形参表列形式参数说明形式参数说明int x , y;形参类型形参类型形参形参 一个程序有且仅有一个一个程序有且仅有一个main函数函数是程函数函数是程序的基本单位，被调函数既可以是系统提供的库函序的基本单位，被调函数既可以是系统提供的库函数，也可以是自定义函数。数，也可以是自定义函数。一、函数形式一、函数形式2022-1-16数据结构63 3. 一个一个C程序总是从程序总是从main函数开始执行，而不

38、论函数开始执行，而不论main在整个函数中的位置如何在整个函数中的位置如何 4. C程序书写格式自由，一行内可以写几个语句，程序书写格式自由，一行内可以写几个语句，一个语句也可以写在几行上一个语句也可以写在几行上 5. 分号；是语句结束符，是语句的一部分分号；是语句结束符，是语句的一部分 6. 函数通常结束于函数通常结束于return语句。语句。2022-1-16数据结构64二、条件语句的两种格式二、条件语句的两种格式1. 1. 格式格式 1 1： if ( if ( 表达式表达式 ) ) 语句语句例例: if (a0) a=-a;: if (a0) a=-a; printf( printf(

39、“a=%dna=%dn”,a);,a);2. 2. 格式格式 2 2： if ( if ( 表达式表达式 ) ) 语句语句 1 1 else else 语句语句 2 23. 3. 功能：功能： 把把( ( 表达式表达式 ) )作为条件，根作为条件，根据其值真假选择所要执行的操作据其值真假选择所要执行的操作条件条件语句语句真真(非非0)假假(0)格式格式1 1条件条件语句语句1真真(非非0)假假(0)语句语句2格式格式22022-1-16数据结构651 1、whilewhile循环语句循环语句2 2）执行过程）执行过程: : 计算计算E E的值的值 若若E E非非0, 0, 则执行则执行S, S

40、, 然后转然后转 若若E E为为0, 0, 则退出循环则退出循环, , 执行该循环后的语句执行该循环后的语句1 1）格式）格式 while ( while ( 表达式表达式E )E ) 循环体语句序列循环体语句序列S S ES0 0非非0 03 3）特点）特点: : 先判断表达式，后执行语句先判断表达式，后执行语句, , 因此因此, , 若进入若进入whilewhile循环时循环时E E的值就是的值就是0 0，则语句，则语句S S一次也不执行一次也不执行三、循环语句的三种格式三、循环语句的三种格式2022-1-16数据结构662、 dowhile 循环语句循环语句2 2）执行过程）执行过程:

41、: 执行循环体执行循环体S S 计算计算E E值值 若若E E的值为真的值为真( (非非0), 0), 则转则转 若若E E的值为假的值为假(0), (0), 则结束循环则结束循环1 1）格式）格式: : do do 循环体语句序列循环体语句序列S S while ( while ( 表达式表达式E);E);ES0 0非非0 03 3）特点）特点: : 先执行循环体，再判断表达式，因此循环体至少执行一次先执行循环体，再判断表达式，因此循环体至少执行一次三、循环语句的三种格式三、循环语句的三种格式2022-1-16数据结构673、 for 循环语句循环语句2 2） 执行过程执行过程: : 计算计

42、算E1E1 计算计算E2E2值值 若若E2E2非非0,0,则执行循环体则执行循环体S,S,再计算再计算E3,E3,转转 若若E2E2为为0,0,则结束循环则结束循环1 1） 格式格式: : for( for(表达式表达式E1;E1;表达式表达式E2;E2;表达式表达式E3) E3) 循环体语句序列循环体语句序列S S 计算计算E2E2S假假(0)(0)真真( (非非0)0)计算计算E1E1计算计算E3E3三、循环语句的三种格式三、循环语句的三种格式注意：上述的三种循环体语句中，均可注意：上述的三种循环体语句中，均可 使用使用break语句语句退出循环体。退出循环体。2022-1-16数据结构6

43、8四、情况语句四、情况语句( (开关语句开关语句) )1. 1. 格式格式: : switch ( switch (表达式表达式) ) case case 常量表达式常量表达式 1: 1: 语句语句1 1； breakbreak； case case 常量表达式常量表达式 2: 2: 语句语句2 2； breakbreak； case case 常量表达式常量表达式 n: n: 语句语句n n； breakbreak； default : default : 语句语句n+1n+1； breakbreak； 2. 2. 执行过程执行过程: : 先计算表达式的值先计算表达式的值; ; 按按case

44、case语句的顺序测试表达式的值与哪个语句的顺序测试表达式的值与哪个casecase常量值常量值相同若与某一常量相同相同若与某一常量相同, , 控制转向该控制转向该casecase常量后面的语句常量后面的语句开始执行开始执行; ; 否则否则, , 在有在有defaultdefault时时, , 执行执行defaultdefault后的语句后的语句, ,无无defaultdefault时时, , 什么也不执行什么也不执行2022-1-16数据结构69五、赋值语句五、赋值语句1. 1. = = ； 或或 op= op= ； 例例 sum=3 sum=3 * * 75 ; 75 ; sum+=25;

45、 sum+=25; 2. 2. 变量变量+ + + 变量加变量加1 1后赋值给变量后赋值给变量3. 3. 变量变量- - - 变量减变量减1 1后赋值给变量后赋值给变量2022-1-16数据结构70六、输入、输出语句六、输入、输出语句1、字符：用函数、字符：用函数getchar和和putchar实现。实现。 1 1） putchar(c) ;putchar(c) ; 功能：输出字符变量功能：输出字符变量c c的值，的值，c c可以是字符可以是字符变量或整型变量变量或整型变量 2 2） getchar( ) ;getchar( ) ; 功能：从终端功能：从终端( (或系统隐含的输入设备或系统隐含

46、的输入设备) )输输入一个字符入一个字符, , 并把得到的字符作为函数的返回值并把得到的字符作为函数的返回值. .2022-1-16数据结构712、其它数据：用函数、其它数据：用函数scanf和和printf实现其输入和输出。实现其输入和输出。1 1）printf( printf( 格式控制，输出表列格式控制，输出表列 ) ) printf(“a=%d,b=%d”, a , b) ;2 2）scanf( scanf( 格式控制参数格式控制参数, , 地址地址1, 1, 地址地址2, 2, ) ;) ; 功能功能: : 按格式控制参数的要求从终端上把数据传送按格式控制参数的要求从终端上把数据传送

47、到地址参数所指的内存空间中，其中到地址参数所指的内存空间中，其中地址地址可以是变量可以是变量的地址，也可以是字符串的首地址的地址，也可以是字符串的首地址七、注解形式七、注解形式 /*字符串字符串*/一、为什么要规定数据类型：一、为什么要规定数据类型： C C语言规定，在程序中用到的每一个变量都要指定它们属于哪一种类语言规定，在程序中用到的每一个变量都要指定它们属于哪一种类型，这是因为：型，这是因为： 1. 1.不同类型的数据在内存中占不同长度的存储区，而且数据在计算机不同类型的数据在内存中占不同长度的存储区，而且数据在计算机内的表示形式也不同内的表示形式也不同. . 例如：一般微机例如：一般微

48、机 2bytes 2bytes 存放一个整型存放一个整型 4bytes 4bytes 存放一个实型存放一个实型2.2.一种数据对应着一个值的范围一种数据对应着一个值的范围int -32768int -32768 3276732767float 10float 10-38-38 10103838之间之间2022-1-16数据结构73 例如：整型数据可以进行求余例如：整型数据可以进行求余(5%2=1)(5%2=1)，而实数不能进行求余运算。，而实数不能进行求余运算。 数值型数据可以进行四则运算，而结构型数据就不能进行四则数值型数据可以进行四则运算，而结构型数据就不能进行四则运算。运算。 一个变量应

49、有确定的类型，在一个程序中一个变量只能属于一一个变量应有确定的类型，在一个程序中一个变量只能属于一个类型，不能先后被定义为二个或多个不同的类型。个类型，不能先后被定义为二个或多个不同的类型。3.3.一种数据类型对应一组允许的操作一种数据类型对应一组允许的操作2022-1-16数据结构74二、二、C C的的数据类型：数据类型：数数据据类类型型基本类型基本类型整型整型短整型短整型 (short)整型整型 ( int )长整型长整型 (long)实型实型(浮点型浮点型)单精度型单精度型 ( float )双精度型双精度型 (double)数值类型数值类型字符类型字符类型 ( char )枚举类型枚举

50、类型 ( enum ) 构造类型构造类型(组合类型组合类型)数组类型数组类型结构体类型结构体类型 (struct)共同体类型共同体类型 (union)文件类型文件类型 ( file )指针类型指针类型空类型空类型 (void)不返回任何类型的数据不返回任何类型的数据2022-1-16数据结构75在程序中，不同类型的数据既可以以常量形式出现，也可以以变量形式在程序中，不同类型的数据既可以以常量形式出现，也可以以变量形式出现。所谓常量是指在程序执行期间其值是不能发生变化。变量则其值出现。所谓常量是指在程序执行期间其值是不能发生变化。变量则其值可以变化的。可以变化的。 例如例如：1.21.2，3 3