课件第一章绪论

1、 开设本课程的背景开设本课程的背景 数据结构是计算机相关专业的一门重要的专业基础课。它数据结构是计算机相关专业的一门重要的专业基础课。它主要研究计算机加工对象的逻辑结构、在计算机中的表示形式以主要研究计算机加工对象的逻辑结构、在计算机中的表示形式以及实现各种基本操作的算法。它是学习操作系统、编译原理、数及实现各种基本操作的算法。它是学习操作系统、编译原理、数据库原理等计算机专业核心课程的基础，掌握好这门课程的内容，据库原理等计算机专业核心课程的基础，掌握好这门课程的内容，是学习计算机其他相关课程的必备条件。是学习计算机其他相关课程的必备条件。 本课程讲述的主要内容本课程讲述的主要内容 本课程将

2、分别讲述数据结构的基本概念、线性表、栈和队列、本课程将分别讲述数据结构的基本概念、线性表、栈和队列、串、树形结构、图结构等内容。串、树形结构、图结构等内容。课程安排课程安排 总学时：总学时：72 讲课学时：讲课学时：48 实验学时：实验学时：24教材：教材： 数据结构数据结构C语言版严蔚敏、吴伟民语言版严蔚敏、吴伟民 -清华大学出版社清华大学出版社学习要点学习要点1. 熟悉各名词、术语的含义，掌握基本概熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的念，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存关系。分清哪些是逻辑结构的性质，哪些是存

3、储结构的性质。储结构的性质。2. 熟悉类熟悉类C语言的书写规范，特别要注意值语言的书写规范，特别要注意值调用和引用调用的区别，输入、输出的方式以调用和引用调用的区别，输入、输出的方式以及错误处理方式。及错误处理方式。 3. 理解算法五个要素的确切含义和对算法理解算法五个要素的确切含义和对算法正确性的理解。正确性的理解。4. 掌握计算语句频度和估算算法时间复杂掌握计算语句频度和估算算法时间复杂度的方法。度的方法。 1.1 数据结构讨论的范畴数据结构讨论的范畴 1.2 基本概念和术语基本概念和术语 1.3 算法及其描述和分析算法及其描述和分析瑞士的计算机专家瑞士的计算机专家 Niklaus Wir

4、th提出：提出：算法算法+数据结构数据结构 = 程序设计程序设计 （Algorithm + Data Structures = Programs ）程序设计程序设计:为计算机处理问题编制一组指令集为计算机处理问题编制一组指令集 算法算法: 处理问题的策略处理问题的策略数据结构数据结构:问题的数学模型问题的数学模型 当今计算机应用的特点：当今计算机应用的特点： l所处理的数据量大且具有一定的关系；所处理的数据量大且具有一定的关系； l对其操作不再是单纯的数值计算，而更多地是需要对对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。其进行组织、管理和检索。 应用举例应用举例1学籍

5、档案管理学籍档案管理 假设一个学籍档案管理系统应包含如下表假设一个学籍档案管理系统应包含如下表1-1所示所示的学生信息。的学生信息。 学 生 基本 情 况学 号姓 名性 别出 生 年 月.99070101李 军男80 12.99070102王 颜 霞女81 2.99070103孙 涛男80 9.99070104单 晓 宏男81 3. 特点：特点： l每个学生的信息占据一行，所有学生的信每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；息按学号顺序依次排列构成一张表格； l表中每个学生的信息依据学号的大小存在着一种前后表中每个学生的信息依据学号的大小存在着一种前后关系，这就是

6、我们所说的线性结构；关系，这就是我们所说的线性结构； l对它的操作通常是插入某个学生的信息，删除某个学对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。生的信息等等。 应用举例应用举例2输出输出n个对象的全排列个对象的全排列 输出输出n个对象的全排列可以使用下图个对象的全排列可以使用下图1-1所示的形式所示的形式描述。描述。31213212312321231213211 特点：特点： l在求解过程中，所处理的数据之间具有层次关系，这在求解过程中，所处理的数据之间具有层次关系，这是我们所说的树形

7、结构；是我们所说的树形结构； l对它的操作有：建立树形结构，输出最低层结点内容对它的操作有：建立树形结构，输出最低层结点内容等等。等等。 应用举例应用举例3制定教学计划制定教学计划 在制定教学计划时，需要考虑各门课程的开设顺在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表业课程的开设情况如下表1-2所示：所示： 计 算 机 专 业 学 生 的 必 修 课 程课 程 编 号课 程 名 称需 要 的

8、先 导 课 程编 号C 1程 序 设 计 基 础无C 2离 散 数 学C 1C 3数 据 结 构C 1 ， C 2C 4汇 编 语 言C 1C 5算 法 分 析 与 设 计C 3 ， C 4C 6计 算 机 组 成 原 理C 1 1C 7编 译 原 理C 5 ， C 3C 8操 作 系 统C 3 ， C 6C 9高 等 数 学无C 1 0线 性 代 数C 9C 1 1普 通 物 理C 9C 1 2数 值 分 析C 9 ， C 1 0 ， C 1课程先后关系的图形描形式：课程先后关系的图形描形式：c1c9c4c2c12c10c11c5c3c6c7c8 特点特点 l课程之间的先后关系用图结构描述；

9、课程之间的先后关系用图结构描述； l通过实施创建图结构，按要求将图结构中的顶点进行通过实施创建图结构，按要求将图结构中的顶点进行线性排序。线性排序。 结论结论 计算机的操作对象的关系更加复杂，操作形计算机的操作对象的关系更加复杂，操作形式不再是单纯的数值计算，而更多地是对这些具式不再是单纯的数值计算，而更多地是对这些具有一定关系的数据进行组织管理，我们将此称为有一定关系的数据进行组织管理，我们将此称为非数值性处理。要使计算机能够更有效地进行这非数值性处理。要使计算机能够更有效地进行这些非数值性处理，就必须弄清楚这些操作对象的些非数值性处理，就必须弄清楚这些操作对象的特点，在计算机中的表示方式以

10、及各个操作的具特点，在计算机中的表示方式以及各个操作的具体实现手段。体实现手段。 以上所举例子中的数学模型正是数据结构要以上所举例子中的数学模型正是数据结构要讨论的问题。因此，简单地说，数据结构是一门讨论的问题。因此，简单地说，数据结构是一门讨论讨论“描述现实世界实体的数学模型描述现实世界实体的数学模型(非数值计算非数值计算)及其上的操作在计算机中如何表示和实现及其上的操作在计算机中如何表示和实现”的学的学科。科。 1.2.1 基本概念和术语基本概念和术语 数据数据 是所有能被输入到计算机中，且能被计算机处理是所有能被输入到计算机中，且能被计算机处理的符号的符号(数字、字符等数字、字符等)的集

11、合，它是计算机操作对象的的集合，它是计算机操作对象的总称。是计算机处理的信息的某种特定的符号表示形总称。是计算机处理的信息的某种特定的符号表示形式。式。 数据元素数据元素 是数据集合中的一个实体，是计算机程序中加工是数据集合中的一个实体，是计算机程序中加工处理的基本单位。处理的基本单位。 有两类数据元素：一类是不可分割的有两类数据元素：一类是不可分割的“原子原子”型数型数据元素，如：整数据元素，如：整数“5”，字符，字符 “N” 等；另一类是由多等；另一类是由多个款项构成的数据元素，其中每个款项被称为一个个款项构成的数据元素，其中每个款项被称为一个“数数据项据项”。例如描述一个学生的信息的数据

12、元素可由学号，。例如描述一个学生的信息的数据元素可由学号，姓名等数据项组成。这些不可分割的数据项为姓名等数据项组成。这些不可分割的数据项为“原子原子项项”。数据项是数据结构中讨论的最小单位。数据项是数据结构中讨论的最小单位 数据对象数据对象是具有相同特性的数据元素的集合，如：整数、是具有相同特性的数据元素的集合，如：整数、实数等。它是数据的一个子集。实数等。它是数据的一个子集。 姓 名学 号班 号性别出生日期入学成绩1.2.2 数据结构数据结构 简单地说，数据结构就是相互之间存在一种或多简单地说，数据结构就是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构种特定关系的数据元素

13、的集合。换句话说，数据结构是带是带“结构结构”的数据元素的集合。的数据元素的集合。“结构结构”即指数据元素即指数据元素之间存在的关系。之间存在的关系。 数据结构的形式定义为：数据结构的形式定义为： 数据结构是一个二元组数据结构是一个二元组Data_Structures = ( D,S )其中：其中：D是数据元素的有限集，是数据元素的有限集，S是是D上关系的有限集。上关系的有限集。 假设以三个假设以三个4位的十进制数表示一个含位的十进制数表示一个含12位位十进制数的十进制数的长整数长整数，则可用如下描述，则可用如下描述的数学模型表示：它是一个含三个数据的数学模型表示：它是一个含三个数据元素元素a

14、1,a2,a3的集合，且在集合上存在的集合，且在集合上存在下列次序关系：下列次序关系：，。例如，长整数例如，长整数 321465879345 可用可用 a1=3214，a2=6587 和和 a3=9345 的集合表的集合表示，且三者之间的次序关系必须是，示，且三者之间的次序关系必须是，a1 表示最高表示最高4位，位，a3 表示最低的表示最低的4位，位，a2 则则是中间是中间4位。位。又如管理工作中人和人之间的关系是一种层次关系。例又如管理工作中人和人之间的关系是一种层次关系。例如，某校一个年级有两个班，由一个级主任带班，每如，某校一个年级有两个班，由一个级主任带班，每个班按所住宿舍分组，他们之

15、间的关系可如下描述：个班按所住宿舍分组，他们之间的关系可如下描述： ，,， ，如下图所，如下图所示。示。从关系或结构分，数据结构可归结为以下四类:线性结构线性结构树形结构树形结构图状结构图状结构集合结构集合结构 上述对数据结构的定义还只是数学上的抽象概念，并没有涉上述对数据结构的定义还只是数学上的抽象概念，并没有涉及计算机，完整的数据结构定义还应该包括它在计算机中的表示，及计算机，完整的数据结构定义还应该包括它在计算机中的表示，即数据的存储结构（物理结构）。即数据的存储结构（物理结构）。 数据结构应该包括数据的数据结构应该包括数据的逻辑结构逻辑结构和数据的和数据的物理结构物理结构两两个方面（层

16、次）。个方面（层次）。数据逻辑结构是对数据元素之间存在的逻辑关系的描述，它数据逻辑结构是对数据元素之间存在的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系表示。可以用一个数据元素的集合和定义在此集合上的若干关系表示。数据物理结构是数据逻辑结构在计算机中的表示和实现，故数据物理结构是数据逻辑结构在计算机中的表示和实现，故又称数据又称数据存储结构存储结构。 存储结构（物理结构）存储结构（物理结构） 存储结构是逻辑结构在存储器中的映象，它包含存储结构是逻辑结构在存储器中的映象，它包含数据元素的映象和关系的映象。数据元素的映象和关系的映象。 数据元素的映象的方法：数据元素的映象的

17、方法： 在计算机中表示信息的最小单位是在计算机中表示信息的最小单位是“位位(bit)”，任，任何一个数据元素都可以用一个何一个数据元素都可以用一个 “位串位串” （或称结点）表（或称结点）表示，如，数值示，如，数值“321” 可用位串可用位串 101000001 表示，当数表示，当数据元素由多个数据项构成时，每个数据项即为表示数据元素由多个数据项构成时，每个数据项即为表示数据元素的位串中的一个据元素的位串中的一个“子位串子位串”（数据域）。（数据域）。关系的映象方法：关系的映象方法：（表示（表示x, yx, y的方法）的方法）顺序映象顺序映象以相对的存储位置表示后继关系以相对的存储位置表示后继

18、关系例如例如: :令令 y y 的存储位置和的存储位置和 x x 的存储位置的存储位置之间差一个常量之间差一个常量 C C而 C 是一个隐含值，整个存储结构中只含数据元素本身的信息 x y链式映象链式映象以附加信息以附加信息( (指针指针) )表示后继关系表示后继关系需要用一个和 x 在一起的附加信息指示 y 的存储位置y x 常见的存储结构常见的存储结构 顺序存储结构：特点是借助于数据元素的相对存顺序存储结构：特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构；储位置来表示数据元素之间的逻辑结构； 链式存储结构：特点是借助于指示数据元素地址链式存储结构：特点是借助于指示数据元素地

19、址的指针表示数据元素之间的逻辑结构。的指针表示数据元素之间的逻辑结构。在不同的编程环境中，存储结构可有不同的描述方法当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。例如例如: : 以三个带有次序关系的整数表示一个长整数时，可利用 C 语言中提供的整数数组类型， typedef int Long_int 3 typedef int Long_int 3定义长整数为定义长整数为: :typedef struct int y; / 年号年号 Year int m; / 月号月号 Month int d; / 日号日号 Day DateType; / 日期类型日期类型定义定

20、义“日期日期”为为: :定义定义“学生学生”为为: :typedef struct char id8; / 学号学号 char name16; / 姓名姓名 char sex; / 性别性别M/F:男男/女女 DateType bdate; / 出生日期出生日期 Student; / 学生类型学生类型 1.2.3 数据类型和抽象数据类型数据类型和抽象数据类型 在用高级程序设计语言编写的程序中，必须对程在用高级程序设计语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。例如，所属的数据类型。例如，C语言中的基本数据

21、类型有：语言中的基本数据类型有：整型、字符型、实型（包括单精度型和双精度型）及整型、字符型、实型（包括单精度型和双精度型）及枚举型。枚举型。 数据类型是一个数据类型是一个“值值”的集合和定义在此集合上的的集合和定义在此集合上的“一组操作一组操作”的总称。的总称。 抽象数据类型（抽象数据类型（Abstract Data Type 简称简称 ADT）是指一个数学模型以及定义在此数学模型上的一组操是指一个数学模型以及定义在此数学模型上的一组操作。作。 各种高级程序设计语言中都拥有“整数”类型，尽管它们在不同处理器上实现的方法不同，但对程序员而言是“相同的”，因为它们的数学特性相同。从“数学抽象”的角

22、度看，可称它为一个“抽象数据类型” 。抽象数据类型还包括用户在设计软件系统时自己定义的数据类型。在构造软件系统的各个相对独立的模块时，定义一组数据和施与这些数据之上的一组操作，并在模块内部给出它们的表示和实现细节，在模块外部使用的只是抽象的数据和抽象的操作。抽象数据类型有两个重要特性：抽象数据类型有两个重要特性：数据抽象数据抽象 用用ADT描述程序处理的实体时，强调的是其描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。用户的接口（即外界使用它的方法）。数据封装数据封装 将实体的外部特性和其内部实现

23、细节分离，将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。并且对外部用户隐藏其内部实现细节。 抽象数据类型的形式描述为：抽象数据类型的形式描述为：ADT = ( D，S，P )其中：其中：D 是数据对象，是数据对象，S 是是 D 上的关系集，上的关系集，P 是是 对对D 的基本操作集。的基本操作集。 ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象： 数据对象的定义数据对象的定义 数据关系：数据关系： 数据关系的定义数据关系的定义 基本操作：基本操作： 基本操作的定义基本操作的定义 ADT 抽象数据类型名抽象数据类型名 其中，数据对象和数据关系的定义用伪码描述，

24、其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为基本操作的定义格式为基本操作名（参数表）基本操作名（参数表）初始条件：初始条件描述初始条件：初始条件描述操作结果：操作结果描述操作结果：操作结果描述 基本操作有两种参数：赋值参数只为操作提供输基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以入值；引用参数以&打头，打头， 除可提供输入值外，还将除可提供输入值外，还将返回操作结果。返回操作结果。 “初始条件初始条件”描述了操作执行之前数据结构和参数描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应应满足的条件，若不满足，则操作失败，并返回相

25、应出错信息。出错信息。 “操作结果操作结果”说明了操作正常完成之后，数据结构说明了操作正常完成之后，数据结构的变化状况和应返回的结果。的变化状况和应返回的结果。 若初始条件为空，则可省略之。若初始条件为空，则可省略之。 例如，定义抽象数据类型例如，定义抽象数据类型“复数复数” 数据对象：数据对象： De1,e2e1,e2RealSet 数据关系：数据关系： R1 | e1是复数的实数部分是复数的实数部分, | e2 是复数的虚数部分是复数的虚数部分 ADT Complex 基本操作：基本操作： AssignComplex( &Z, v1, v2 )操作结果：构造复数 Z,其实部和虚部

26、分别被赋以参数 v1 和 v2 的值。 DestroyComplex( &Z)操作结果：复数Z被销毁。 GetReal( Z, &realPart )初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。 GetImag( Z, &ImagPart )初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。 Add( z1,z2, &sum )初始条件：z1, z2是复数。操作结果：用sum返回两个复数z1, z2 的 和值。 ADT Complex)34()68()34)(68(iiiiz # include # include

27、complex.h void main() complex z1,z2,z3,z4,z; float RealPart,ImagPart; InitComplex(z1,8.0,6.0); InitComplex(z2,4.0,3.0); Add(z1,z2,z3); Multiply(z1,z2,z4); if (Division (z4,z3,z) GetReal (z, RealPart); GetImag (z, ImagPart); /if 抽象数据类型的实现包括数据结构的实现和操作抽象数据类型的实现包括数据结构的实现和操作的实现，因此不仅要借用高级语言中的数据类型来描的实现，因此不

28、仅要借用高级语言中的数据类型来描述它的存储结构，也要利用高级语言中已经实现的固述它的存储结构，也要利用高级语言中已经实现的固有数据类型的操作来实现抽象数据类型的操作。有数据类型的操作来实现抽象数据类型的操作。 例如利用例如利用C语言实现的语言实现的复数复数类型如下描述：类型如下描述：存储结构的定义存储结构的定义typedef struct float realpart;float imagpart; complex;/ 基本操作的函数原型说明基本操作的函数原型说明void Assign( complex &Z, float realval, float imagval );/ 构造复数

29、构造复数 Z，其实部和虚部分别被赋以参数，其实部和虚部分别被赋以参数 realval 和和 imagval 的值的值void DestroyComplex( complex &Z)/ 销毁复数销毁复数 Zfloat GetReal( cpmplex Z );/ 返回复数返回复数 Z 的实部值的实部值float Getimag( cpmplex Z );/ 返回复数返回复数 Z 的虚部值的虚部值void add( complex z1, complex z2, complex &sum );/ 以以 sum 返回两个复数返回两个复数 z1，z2 的和的和 / 基本操作的实现基本操

30、作的实现void add( complex z1, complex z2, complex &sum ) / 以以 sum 返回两个复数返回两个复数 z1，z2 的和的和sum.realpart = z1.realpart + z2.realpart;sum.imagpart = z1.imagpart + z2.imagpart; 1.3.1 算法的概念算法的概念 算法是对问题求解过程的一种描述，是为解决一个算法是对问题求解过程的一种描述，是为解决一个或一类问题给出的一个确定的、有限长的操作序列或一类问题给出的一个确定的、有限长的操作序列 。 计算机对数据的操作可以分为数值性和非数值

31、性计算机对数据的操作可以分为数值性和非数值性两种类型。在数值性操作中主要进行的是算术运算；两种类型。在数值性操作中主要进行的是算术运算；而在非数值性操作中主要进行的是检索、排序、插入、而在非数值性操作中主要进行的是检索、排序、插入、删除等等。删除等等。 设计算法的基本过程设计算法的基本过程 l通过对问题进行详细地分析，抽象出相应的数学模型；通过对问题进行详细地分析，抽象出相应的数学模型； l确定使用的数据结构，并在此基础上设计对此数据结确定使用的数据结构，并在此基础上设计对此数据结构实施各种操作的算法；构实施各种操作的算法； l选用某种语言将算法转换成程序；选用某种语言将算法转换成程序； l调

32、试并运行这些程序。调试并运行这些程序。 算法应该具有下列五个特性算法应该具有下列五个特性 （1）有穷性：一个算法必须在执行有穷步之后结）有穷性：一个算法必须在执行有穷步之后结束。束。 （2）确定性：算法中的每一步，必须有确切的含）确定性：算法中的每一步，必须有确切的含义，在他人理解时不会产生二义性。义，在他人理解时不会产生二义性。 （3）可行性：算法中描述的每一步操作都可以通）可行性：算法中描述的每一步操作都可以通过已有的基本操作执行有限次实现。过已有的基本操作执行有限次实现。 （4）输入：一个算法应该有零个或多个输入。）输入：一个算法应该有零个或多个输入。 （5）输出：一个算法应该有一个或多

33、个输出。这）输出：一个算法应该有一个或多个输出。这里所说的输出是指与输入有某种特定关系的量。里所说的输出是指与输入有某种特定关系的量。 1.3.2 算法的描述算法的描述 选择算法描述语言的准则选择算法描述语言的准则 （1）该语言应该具有描述数据结构和算法的基本）该语言应该具有描述数据结构和算法的基本功能；功能； （2）该语言应该尽可能地简捷，以便于掌握、理）该语言应该尽可能地简捷，以便于掌握、理解；解； （3）使用该语言描述的算法应该能够比较容易地）使用该语言描述的算法应该能够比较容易地转换成任何一种程序设计语言。转换成任何一种程序设计语言。 “类类C”描述语言是通过对描述语言是通过对C语言进

34、行精心筛选保留语言进行精心筛选保留的一个核心子集，并为了便于描述，又做了若干扩展的一个核心子集，并为了便于描述，又做了若干扩展修改，从而，增强了语言的描述功能。修改，从而，增强了语言的描述功能。 1. 预定义常量及类型预定义常量及类型 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -1 数据元素被约定为数据元素被约定为ElemType 类型，用户需要根据具类型，用户需要根据具体情况，自行定义该数据类型。体情况，自行定义该数据类型。 2. 算法描述为以下的函数形式：算法描述为以下的函数形式

35、： 函数类型函数类型 函数名（函数参数表）函数名（函数参数表） 语句序列；语句序列； 为了简化函数的书写，提高算法描述的清晰度，为了简化函数的书写，提高算法描述的清晰度，我们规定除函数参数表中的参数需要说明数据类型外，我们规定除函数参数表中的参数需要说明数据类型外，函数中使用的局部变量可以不做变量说明，必要时给函数中使用的局部变量可以不做变量说明，必要时给出相应的注释即可。另外，在书写算法时，应该养成出相应的注释即可。另外，在书写算法时，应该养成对重点语句段落添加注解的良好习惯。对重点语句段落添加注解的良好习惯。 3. 在算法描述中可以使用的赋值语句形式有：在算法描述中可以使用的赋值语句形式有

36、： 简单赋值简单赋值 变量名变量名 = 表达式；表达式； 串联赋值串联赋值 变量名变量名1 = 变量名变量名2 = . = 变量名变量名n = 表表达式；达式； 成组赋值成组赋值 （变量名（变量名1，.，变量名，变量名n）=（表达式（表达式1，.，表达式，表达式n）；）； 结构赋值结构赋值 结构名结构名1 = 结构名结构名2； 结构名结构名 =（值（值1，值，值2，.，值，值n）；）； 条件赋值条件赋值 变量名变量名 = 条件表达式条件表达式 ? 表达式表达式1：表达：表达式式2； 交换赋值交换赋值 变量名变量名1 变量名变量名2；4. 在算法描述中可以使用的选择结构语句形式有：在算法描述中可

37、以使用的选择结构语句形式有：条件语句条件语句1 if （表达式）（表达式） 语句；语句；条件语句条件语句2 if （表达式）（表达式） 语句；语句； else 语句；语句；开关语句开关语句1 switch （表达式）（表达式） case 值值1：语句序列：语句序列1；break； case 值值2：语句序列：语句序列2；break； . case 值值n：语句序列：语句序列n；break； default：语句序列：语句序列n+1； 开关语句开关语句2 switch case 条件条件1：语句序列：语句序列1；break； case 条件条件2：语句序列：语句序列2；break； . case

38、 条件条件n：语句序列：语句序列n；break； default：语句序列：语句序列n+1； 5. 在算法描述中可以使用的循环结构语句形式有：在算法描述中可以使用的循环结构语句形式有： for循环语句循环语句 for （表达式（表达式1；循环条件表达式；循环条件表达式；表达式表达式2） 语句；语句； while循环语句循环语句 while （循环条件表达式）（循环条件表达式） 语句；语句； do-while循环语句循环语句 do 语句序列；语句序列； while （循环条件表达式）；（循环条件表达式）； 6. 在描述算法中可以使用的结束语句形式有：在描述算法中可以使用的结束语句形式有： 函数结

39、束语句函数结束语句 return 表达式；表达式； return; case或循环结束语句或循环结束语句 break; 异常结束语句异常结束语句 exit（异常代码）；（异常代码）； 7. 在算法描述中可以使用的输入输出语句形式有：在算法描述中可以使用的输入输出语句形式有： 输入语句输入语句 scanf( 格式串格式串，变量名，变量名1，.，变量名，变量名n)；或；或cin变量名变量名1变量名变量名2变量名变量名n 输出语句输出语句 printf( 格式串格式串，表达式，表达式1，.，表达式，表达式n); 或或cout表达式表达式1 表达式表达式2表达式表达式n; 方括号（方括号（ ）中的内容

40、是可以省略的部分。）中的内容是可以省略的部分。 8. 在算法描述中使用的注释格式为：在算法描述中使用的注释格式为： 单行注释单行注释 /文字序列文字序列 注释注释 /*文字序列文字序列*/ 9. 在算法描述中可以使用的扩展函数有：在算法描述中可以使用的扩展函数有： 求最大值求最大值 max（表达式（表达式1，.，表达式，表达式n）；这个）；这个函数返回参数表中函数返回参数表中n个表达式计算结果中的最大值。个表达式计算结果中的最大值。 求最小值求最小值 min（表达式（表达式1，.，表达式，表达式n）；这个）；这个函数返回参数表中函数返回参数表中n个表达式计算结果中的最小值。个表达式计算结果中的

41、最小值。 1.3.3 算法的分析算法的分析 算法的评价标准算法的评价标准(设计原则）设计原则） (1) 正确性：要求算法能够正确地执行预先规定的正确性：要求算法能够正确地执行预先规定的功能，并达到所期望的性能要求。功能，并达到所期望的性能要求。 (2) 可读性：为了便于理解、测试和修改算法，算可读性：为了便于理解、测试和修改算法，算法应该具有良好的可读性。法应该具有良好的可读性。 (3) 健壮性：算法中拥有对输入数据、打开文件、健壮性：算法中拥有对输入数据、打开文件、读取文件记录、分配内存空间等操作的结果检测，并读取文件记录、分配内存空间等操作的结果检测，并通过与用户对话的形式做出相应的处理选

42、择。通过与用户对话的形式做出相应的处理选择。 (4) 时间与空间效率：算法的时间与空间效率是时间与空间效率：算法的时间与空间效率是指将算法变换为程序后，该程序在计算机上运行时所指将算法变换为程序后，该程序在计算机上运行时所花费的时间及所占据空间的度量。花费的时间及所占据空间的度量。 算法效率的衡量方法算法效率的衡量方法 通常有两种衡量算法效率的方法：事后统计法和通常有两种衡量算法效率的方法：事后统计法和事前分析估算法。相比之下前者的缺点是，必须在计事前分析估算法。相比之下前者的缺点是，必须在计算机上实地运行程序，容易由其它因素掩盖算法本质；算机上实地运行程序，容易由其它因素掩盖算法本质；而后者

43、的优点是，可以预先比较各种算法，以便均衡而后者的优点是，可以预先比较各种算法，以便均衡利弊而从中选优。利弊而从中选优。 算法的时间效率主要由以下因素决定：算法的时间效率主要由以下因素决定： 1）算法所用）算法所用策略策略；2）算法所解问题的）算法所解问题的规模规模；3）编程所用编程所用语言语言；4）编译编译的质量；的质量；5）执行算法的）执行算法的计算机的计算机的速度速度。显然，后三条受着计算机硬件和软。显然，后三条受着计算机硬件和软件的制约，既然是件的制约，既然是估算估算，仅需考虑前两条。，仅需考虑前两条。 一个算法的一个算法的“运行工作量运行工作量”通常是随问题规模的增通常是随问题规模的增

44、长而增长，因此比较不同算法的优劣主要应该以其长而增长，因此比较不同算法的优劣主要应该以其“增增长的趋势长的趋势”为准则。假如，随着问题规模为准则。假如，随着问题规模 n 的增长，算的增长，算法执行时间的增长率和法执行时间的增长率和f(n)的增长率相同，则可记作：的增长率相同，则可记作：T(n)=O(f(n)。其中，称。其中，称T(n)为算法的为算法的(渐近渐近)时间复杂时间复杂度。度。 一般情况下，算法中基本操作重复执行的次数是一般情况下，算法中基本操作重复执行的次数是问题规模问题规模n的某个函数的某个函数f(n) 。 好的算法应该能够在数据量好的算法应该能够在数据量n增长的同时，函数增长的同

45、时，函数T(n)的增长速度比较缓慢。的增长速度比较缓慢。NoImage 如何估算算法的时间复杂度呢？如何估算算法的时间复杂度呢？ 任何一个算法都是由一个任何一个算法都是由一个控制结构控制结构和若干和若干原操原操作作组成的，因此一个算法的执行时间可以看成是所有组成的，因此一个算法的执行时间可以看成是所有原操作的执行时间之和原操作的执行时间之和( 原操作原操作(i)的执行次数原操作的执行次数原操作(i)的执行时间的执行时间 )则算法的执行时间与所有原操作的执行次数之和成正则算法的执行时间与所有原操作的执行次数之和成正比。比。从算法中选取一种对于所研究的问题来说是基本从算法中选取一种对于所研究的问题

46、来说是基本操作的原操作，以该基本操作在算法中重复执行的次操作的原操作，以该基本操作在算法中重复执行的次数作为算法时间复杂度的依据。这种衡量效率的办法数作为算法时间复杂度的依据。这种衡量效率的办法所得出的不是时间量，而是一种增长趋势的量度。它所得出的不是时间量，而是一种增长趋势的量度。它与软硬件环境无关，只暴露算法本身执行效率的优劣。与软硬件环境无关，只暴露算法本身执行效率的优劣。NoImage 下面举例子介绍时间复杂度的估算方法。下面举例子介绍时间复杂度的估算方法。例例1.1 两个两个 nn 的矩阵相乘。其中矩阵的的矩阵相乘。其中矩阵的阶阶 n 为问题为问题的规模。的规模。 【算法【算法1.1】void Mult_matrix( int c , int a , int b ， int n)/ a、b 和和 c 均为均为 n 阶方阵，且阶方阵，且 c 是是 a 和和 b 的乘积的乘积for (i=1; i=n; +i)for (j=1; j=n; +j) ci,j = 0;for (k=1; k1 & change; -i) change = FALSE;for (j=0; j aj+1) w = aj; aj= aj+1; aj+1= w; change = TRUE / bubble_sort 算法