1、教材:自考数据结构 苏仕华 编著 授课教师：涂风华授课教师：涂风华开始日期：开始日期：2014年年3月月1日日 1.1 1.1 基本概念和术语基本概念和术语 1.2 1.2 学习数据结构的意义学习数据结构的意义 1.3 1.3 算法的描述和分析算法的描述和分析第1章 概论数据数据（data)data)是信息的载体。它能够被计算机识是信息的载体。它能够被计算机识别、存储和加工处理，是计算机程序加工的别、存储和加工处理，是计算机程序加工的 原料原料。数据元素数据元素（data elementdata element）是数据的是数据的基本单位基本单位，由若干个数据项组成，也称结点、元素、顶点或由若干
2、个数据项组成，也称结点、元素、顶点或记记录。录。数据项数据项（data itemdata item）是具有独立含义的是具有独立含义的最小标最小标识单位识单位，有时也称为域（，有时也称为域（fieldfield），即数据表中的字），即数据表中的字段。段。1.1 基本概念和术语基本概念和术语数据结构数据结构(data structure)(data structure)：指的是数据之间指的是数据之间的的相互关系相互关系，即数据的组织形式。，即数据的组织形式。数据结构一般包括以下三方面内容：数据结构一般包括以下三方面内容：数据元素之间的逻辑关系，也称数据的数据元素之间的逻辑关系，也称数据的逻辑结构（
3、逻辑结构（Logical StructureLogical Structure）；数据元素及其关系在计算机存储器内的数据元素及其关系在计算机存储器内的表示，称为数据的表示，称为数据的存储结构（存储结构（Storage Storage StructureStructure）；数据的运算数据的运算，即对数据施加的操作。，即对数据施加的操作。数据的数据的逻辑结构逻辑结构是从逻辑关系上描述数据，与是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模辑结构可以看作是从具体问题抽象出来的数学模型。型。数据的
4、数据的存储结构存储结构是逻辑结构用计算机语言的实是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。对机现（亦称为映象），它依赖于计算机语言。对机器语言而言，存储结构是具体的。一般，只在高器语言而言，存储结构是具体的。一般，只在高级语言的层次上讨论存储结构。级语言的层次上讨论存储结构。数据的数据的运算运算定义在数据的逻辑结构上，每种逻定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的检索、插辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。的数据上所施加的一系
5、列抽象的操作。所谓所谓抽象的操作抽象的操作，是指我们只知道这些操作是，是指我们只知道这些操作是做什么做什么，而无须考虑，而无须考虑如何做如何做。只有确定了存。只有确定了存储结构之后，才考虑如何具体实现这些运算。储结构之后，才考虑如何具体实现这些运算。3 3为了增加对数据结构的感性认识，下面举例来说明有关数据结构的概为了增加对数据结构的感性认识，下面举例来说明有关数据结构的概念。念。【例【例11】学生成绩表，见下表。学生成绩表，见下表。（1）逻辑结构）逻辑结构表中的每一行是一个数据元素（或记录、结点），它由学号、表中的每一行是一个数据元素（或记录、结点），它由学号、姓名、各科成绩及平均成绩等数据
6、项组成。姓名、各科成绩及平均成绩等数据项组成。表中数据元素之间的逻辑关系是：对表中任一个结点，与它相邻且表中数据元素之间的逻辑关系是：对表中任一个结点，与它相邻且在它前面的结点（亦称为直接前趋（在它前面的结点（亦称为直接前趋（Immediate Predecessor）最）最多只有一个；与表中任一结点相邻且在其后的结点（亦称为直接后多只有一个；与表中任一结点相邻且在其后的结点（亦称为直接后继（继（Immediate Successor）也最多只有一个。表中只有第一个结）也最多只有一个。表中只有第一个结点没有直接前趋，故称为开始结点；也只有最后一个结点没有直接点没有直接前趋，故称为开始结点；也只
7、有最后一个结点没有直接后继。故称之为终端结点。例如，表中后继。故称之为终端结点。例如，表中李四李四所在结点的直接前趋所在结点的直接前趋结点和直接后继结点分别是结点和直接后继结点分别是张三张三和和王五王五所在的结点，上述结点所在的结点，上述结点间的关系构成了这张学生成绩表的逻辑结构。间的关系构成了这张学生成绩表的逻辑结构。（2）存储结构该表的存储结构是指用计算机语言如何表示结点之间的这种关系，即表中的结点是顺序邻接地存储在一片连续的单元之中，还是用指针将这些结点链接在一起？（3）数据的运算在上面的学生成绩表中，可能要经常查看某一学生的成绩；当学生退学时要删除相应的结点；进来新学生时要增加结点。究
8、竟如何进行查找、删除、插入，这就是数据的运算问题。搞清楚了上述三个问题，也就弄清了学生成绩表这个数据结构。2数据的逻辑结构分类数据的逻辑结构分类 在不产生混淆的前提下，常将数据的逻辑结构简称在不产生混淆的前提下，常将数据的逻辑结构简称为数据结构。数据的逻辑结构有两大类：为数据结构。数据的逻辑结构有两大类：（1）线性结构）线性结构 线性结构的逻辑特征是：若结构是非空集，则有且线性结构的逻辑特征是：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。最多只有一个直接前趋和一个直接后继。线性表是一个典型
9、的线性结构。栈、队列、串等都线性表是一个典型的线性结构。栈、队列、串等都是线性结构。是线性结构。（2）非线性结构）非线性结构 非线性结构的逻辑特征是：一个结点可能有多个直非线性结构的逻辑特征是：一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。构都是非线性结构。3数据的四种基本存储方法数据的四种基本存储方法 数据的存储结构可用以下四种基本存储方法得到：数据的存储结构可用以下四种基本存储方法得到：（1）顺序存储方法）顺序存储方法 该方法把逻辑上相邻的结点存储在物理位置上相该方法把逻辑上相邻的结点存储在物理位置上相邻的
10、存储单元里，结点间的逻辑关系由存储单元的邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。邻接关系来体现。由此得到的存储表示称为由此得到的存储表示称为顺序存储结构顺序存储结构，通常借，通常借助程序语言的数组描述。助程序语言的数组描述。该方法主要应用于线性的数据结构。非线性的数该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。据结构也可通过某种线性化的方法实现顺序存储。（2）链接存储方法）链接存储方法 该方法不要求逻辑上相邻的结点在物理位置上亦该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。相邻，结点间的逻辑关系
11、由附加的指针字段表示。由此得到的存储表示称为由此得到的存储表示称为链式存储结构链式存储结构（Linked Storage Structure）,通常借助于程序语言的指针类型通常借助于程序语言的指针类型描述。描述。元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容Loc(元素元素i)=Lo+（i-1)*m顺序存储顺序存储1536元素元素2 21400元素元素1 11346元素元素3 3 元素元素4 41345h存储地址存储地址 存储内容存储内容 指针指针 13451345 元素元素1 1 1400140
12、0 13461346 元素元素4 4 .14001400 元素元素2 2 15361536 .15361536 元素元素3 3 13461346 链式存储链式存储 h（3）索引存储方法）索引存储方法 该方法通常在储存结点信息的同时，还建立附加的索引表。该方法通常在储存结点信息的同时，还建立附加的索引表。索引表由若干索引项组成。若每个结点在索引表中都有一个索引表由若干索引项组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（索引项，则该索引表称之为稠密索引（Dense Index）。若一组）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引结点在索引表中只对应一个索引
13、项，则该索引表称为稀疏索引(Spare Index)。索引项的一般形式是：。索引项的一般形式是：(关键字、地址关键字、地址)关键字是能唯一标识一个结点的那些数据项。稠密索引中索引关键字是能唯一标识一个结点的那些数据项。稠密索引中索引项的地址指示结点所在的存储位置；稀疏索引中索引项的地址项的地址指示结点所在的存储位置；稀疏索引中索引项的地址指示一组结点的起始存储位置。指示一组结点的起始存储位置。（4）散列存储方法）散列存储方法 该方法的基本思想是：根据结点的关键字直接计算出该结点该方法的基本思想是：根据结点的关键字直接计算出该结点的存储地址。的存储地址。四种基本存储方法，既可单独使用，也可组合起
14、来对数据结四种基本存储方法，既可单独使用，也可组合起来对数据结构进行存储映像。构进行存储映像。同一逻辑结构采用不同的存储方法，可以得到不同的存储结同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构，视具体要求而构。选择何种存储结构来表示相应的逻辑结构，视具体要求而定，主要考虑运算方便及算法的时空要求。定，主要考虑运算方便及算法的时空要求。4数据结构三方面的关系数据结构三方面的关系 数据的逻辑结构、数据的存储结构及数据的运算这三方面是数据的逻辑结构、数据的存储结构及数据的运算这三方面是一个整体。孤立地去理解一个方面，而不注意它们之间的联系一个整体。孤立地
15、去理解一个方面，而不注意它们之间的联系是不可取的。是不可取的。存储结构是数据结构不可缺少的一个方面：同一逻辑结构的存储结构是数据结构不可缺少的一个方面：同一逻辑结构的不同存储结构可冠以不同的数据结构名称来标识。不同存储结构可冠以不同的数据结构名称来标识。【例【例】线性表是一种逻辑结构，若采用顺序方法的存储表示线性表是一种逻辑结构，若采用顺序方法的存储表示，可称其为顺序表；若采用链式存储方法，则可称其为链表；，可称其为顺序表；若采用链式存储方法，则可称其为链表；若采用散列存储方法，则可称为散列表。若采用散列存储方法，则可称为散列表。数据的运算也是数据结构不可分割的一个方面。在给定了数数据的运算也
16、是数据结构不可分割的一个方面。在给定了数据的逻辑结构和存储结构之后，按定义的运算集合及其运算的据的逻辑结构和存储结构之后，按定义的运算集合及其运算的性质不同，也可能导致完全不同的数据结构。性质不同，也可能导致完全不同的数据结构。【例【例】若对线性表上的插入、删除运算限制在表的一端进行若对线性表上的插入、删除运算限制在表的一端进行，则该线性表称之为栈；若对插入限制在表的一端进行，而删，则该线性表称之为栈；若对插入限制在表的一端进行，而删除限制在表的另一端进行，则该线性表称之为队列。更进一步除限制在表的另一端进行，则该线性表称之为队列。更进一步，若线性表采用顺序表或链表作为存储结构，则对插入和删除
17、，若线性表采用顺序表或链表作为存储结构，则对插入和删除运算做了上述限制之后，可分别得到顺序栈或链栈，顺序队列运算做了上述限制之后，可分别得到顺序栈或链栈，顺序队列或链队列。或链队列。5数据类型和抽象数据类型数据类型和抽象数据类型数据类型（数据类型（Data Type）自自20世纪世纪70年代以来，几乎所有的高级程序设计语言都提供了这一年代以来，几乎所有的高级程序设计语言都提供了这一概念。在用高级语言编写的程序中间，程序中出现的每个变量，常量概念。在用高级语言编写的程序中间，程序中出现的每个变量，常量或表达式，都必须事先说明它们所属的数据类型，每个类型都明显或或表达式，都必须事先说明它们所属的数
18、据类型，每个类型都明显或隐含的规定了在程序执行期间它的变量，它的表达式所允许取值的范隐含的规定了在程序执行期间它的变量，它的表达式所允许取值的范围，以及允许进行的操作，因此围，以及允许进行的操作，因此所谓数据类型是一个值的集合以及在这些值上定义的一组操作的总称。所谓数据类型是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。通常数据类型可以看作是程序设计语言中已实现的数据结构。【例【例12】C语言的语言的整数类型整数类型就定义了一个整数可取值的范围（其就定义了一个整数可取值的范围（其最大值最大值INT-MAX依赖于具体机器）以及对整数可施加的
19、加、减、乘、依赖于具体机器）以及对整数可施加的加、减、乘、除和取模等操作。除和取模等操作。按按值值是否可分解，可将数据类型划分为两类：是否可分解，可将数据类型划分为两类：原子类型：原子类型：其值不可分解。通常是由语言直接提供。其值不可分解。通常是由语言直接提供。【例】【例】C语言的整型、字符型等标准类型及指针等简单的导出类型；语言的整型、字符型等标准类型及指针等简单的导出类型；结构类型：结构类型：其值可分解为若干个成分（或称为分量）。是用户借助其值可分解为若干个成分（或称为分量）。是用户借助于语言提供的描述机制自己定义的，它通常是由标准类型派生的，故于语言提供的描述机制自己定义的，它通常是由标
20、准类型派生的，故它也是一种导出类型。它也是一种导出类型。【例】【例】C的数组、结构等类型。的数组、结构等类型。用户也可用用户也可用typedef 自己定义数据类型自己定义数据类型typedef struct int num;char name20;float score;STUDENT;STUDENT stu1,stu2,*p;抽象数据类型抽象数据类型ADTADT（Abstract Abstract Data Type)Data Type)定义：是指抽象数据的组织和与之相关的操作。可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。数据结构数据结构+定义在此数据结构上的一组操作定义在此数据结构
21、上的一组操作=抽象抽象数据类型数据类型 一个一个ADT可描述为：可描述为：ADT ADT-Name Data:/数据说明数据说明 数据元素之间逻辑关系的描述数据元素之间逻辑关系的描述 Operations:/操作说明操作说明 Operation1:/操作操作1，它通常可用，它通常可用C或或C的函数原的函数原型来描述型来描述 Input:对输入数据的说明对输入数据的说明 Preconditions:执行本操作前系统应满足的状态执行本操作前系统应满足的状态/可看作初可看作初始条件始条件 Process:对数据执行的操作对数据执行的操作 Output:对返回数据的说明对返回数据的说明 Postcon
22、ditions:执行本操作后系统的状态执行本操作后系统的状态/系统系统可看作可看作某个数据结构某个数据结构 Operation2:/操作操作2 /ADT v描述方法描述方法形式定义：我们用一个三元组形式定义：我们用一个三元组（D，S，P）来表示一个来表示一个 抽象数据类型抽象数据类型，其中，其中D是数据对是数据对象，象，S是是D上的关系集，上的关系集，P是对是对D的基本操作集的基本操作集。格式：格式：ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象的定义数据对象：数据对象的定义 数据关系：数据关系的定义数据关系：数据关系的定义 基本操作：基本操作的定义基本操作：基本操作的定义 ADT
23、抽象数据类型名抽象数据类型名 v基本操作的定义格式：基本操作的定义格式：基本操作名（参数表）基本操作名（参数表）初始条件：初始条件描述初始条件：初始条件描述 操作结果：操作结果描述操作结果：操作结果描述 赋值参数赋值参数引用参数，以引用参数，以“”打头打头例：抽象数据类型三元组的定义：例：抽象数据类型三元组的定义：ADT Triplet 数据对象：数据对象：D=e1,e2,e3|e1,e2,e3Elemset 数据关系数据关系：R1=,基本操作：基本操作：InitTriplet(&T,v1,v2,v3)操作结果：构造了三元组操作结果：构造了三元组T，元素元素e1，e2和和e3分别被赋以分别被赋
24、以 参数参数v1,v2和和v3的值。的值。DestroyTriplet（&T）操作结果：三元组操作结果：三元组T被销毁。被销毁。Get（T,i,&e）初始条件：三元组初始条件：三元组T已存在，已存在，1=i=3.操作结果：用操作结果：用e返回返回T的第的第i元的值。元的值。Put(&T,i,e)初始条件：三元组初始条件：三元组T已存在，已存在，1=i=3.操作结果：改变操作结果：改变T的第的第i元的值为元的值为e。IsAscending(T)初始条件：三元组初始条件：三元组T已存在。已存在。操作结果：如果操作结果：如果T的的3个元素按升序排列个元素按升序排列，则返回，则返回1，否则返回，否则返
25、回0。IsDescending(T)初始条件：三元组初始条件：三元组T已存在。已存在。操作结果：如果操作结果：如果T的的3个元素按降序排列，则个元素按降序排列，则 返回返回1，否则返回，否则返回0。Max(T,&e)初始条件：三元组初始条件：三元组T已存在。已存在。操作结果：用操作结果：用e返回返回T的的3个元素中的最大值。个元素中的最大值。Min(T,&e)初始条件：三元组初始条件：三元组T已存在。已存在。操作结果：用操作结果：用e返回返回T的的3个元素中的最小值。个元素中的最小值。ADT Triplet 抽象数据类型可以看作是描述问题的模型，它独立于具体实现。抽象数据类型可以看作是描述问题
26、的模型，它独立于具体实现。它的优点是将数据和操作封装在一起，使得用户程序只能通过它的优点是将数据和操作封装在一起，使得用户程序只能通过在在ADT里定义的某些操作来访问其中的数据，从而实现了里定义的某些操作来访问其中的数据，从而实现了信息信息隐藏隐藏。在。在C中，我们可以用类（包括模板类）的说明来表中，我们可以用类（包括模板类）的说明来表示示ADT，用类的实现来实现，用类的实现来实现ADT。因此，。因此，C中实现的类相中实现的类相当于是数据的存储结构及其在存储结构上实现的对数据的操作。当于是数据的存储结构及其在存储结构上实现的对数据的操作。ADT和类的概念实际上反映了程序或软件设计的两层抽象：和
27、类的概念实际上反映了程序或软件设计的两层抽象：ADT相当于是在概念层（或称为抽象层）上描述问题，而类相相当于是在概念层（或称为抽象层）上描述问题，而类相当于是在实现层上描述问题。当于是在实现层上描述问题。此外，此外，C中的类只是一个由中的类只是一个由用户定义的普通类型，可用它来定义变量（称为对象或类的实用户定义的普通类型，可用它来定义变量（称为对象或类的实例）。因此，在例）。因此，在C中，最终是通过操作对象来解决实际问中，最终是通过操作对象来解决实际问题的，所以我们可将该层次看作是应用层。例如，题的，所以我们可将该层次看作是应用层。例如，main程序就程序就可看作是用户的应用程序。可看作是用户
28、的应用程序。由于由于C语言中没有提供语言中没有提供类类这一数据类型，因此无法实现这一数据类型，因此无法实现ADT，故我们不采用，故我们不采用ADT的形式来描述数据结构，以节省篇幅。的形式来描述数据结构，以节省篇幅。大家只要记住，它实际上等价于我们定义的数据的逻辑结构以大家只要记住，它实际上等价于我们定义的数据的逻辑结构以及在逻辑结构上定义的抽象操作。及在逻辑结构上定义的抽象操作。1.2 学习数据结构的意义著名计算机科学家、著名计算机科学家、PascalPascal语言发明者语言发明者N.N.沃思教授提出：沃思教授提出：程序程序 =算法算法 +数据结构数据结构 程序程序:处理问题编制一组指令集处
29、理问题编制一组指令集 算法算法:处理问题的策略处理问题的策略数据结构数据结构:问题的数学模型问题的数学模型也就是说，计算机按照程序所描述的算法也就是说，计算机按照程序所描述的算法对某种结构的数据进行加工处理。对某种结构的数据进行加工处理。1 计算机处理问题的分类计算机处理问题的分类（1）数值计算问题 在计算机发展初期，人们使用计算机主要是处理数值计算问题。【例】线性方程的求解 该类问题涉及的运算对象是简单的整型、实型或布尔型数据。程序设计者的主要精力集中于程序设计的技巧，无须重视数据结构。随着计算机应用领域的扩大和软、硬件的发展随着计算机应用领域的扩大和软、硬件的发展，“非数值性问题非数值性问
30、题”越来越显得重要。据统计，越来越显得重要。据统计，当今处理非数值性问题占用了当今处理非数值性问题占用了90%以上的机器时以上的机器时间，这类问题涉及到的数据结构更为复杂，数据间，这类问题涉及到的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式加以元素之间的相互关系一般无法用数学方程式加以描述。因此，解决此类问题的关键已不再是分析描述。因此，解决此类问题的关键已不再是分析数学和计算方法，而是要设计出合适的数据结构数学和计算方法，而是要设计出合适的数据结构，才能有效地解决问题。，才能有效地解决问题。程序设计的实质是对实际问题选择一种好的数程序设计的实质是对实际问题选择一种好的数据结构
31、，加之设计一个好的算法，而好的算法在据结构，加之设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。很大程度上取决于描述实际问题的数据结构。（2 2）非数值计算的程序设计问题：）非数值计算的程序设计问题：例例1 1 书目自动检索系统书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片001高等数学樊映川S01002理论力学罗远祥L01003高等数学华罗庚S01004线性代数栾汝书S02书目文件按书名按作者名按分类号高等数学001，003理论力学002，.线性代数004，.樊映川001,华罗庚002,.栾汝书004,.L002,S001,003,索引
32、表线性表算法：需要检索的书目？如何检索？用户算法：需要检索的书目？如何检索？用户界面？界面？模型：？模型：？例例2 2 人机对奕问题人机对奕问题树.算法：对奕的规则算法：对奕的规则 和策略和策略模型：？模型：？例例3 3 教学计划编排问题教学计划编排问题 图课程代号课程名称先修课程C1C1计算机导论计算机导论无无C2C2数据结构数据结构C1,C4C1,C4C3C3汇编语言汇编语言C1C1C4C4C C语言语言C1C1C5C5计算机图形学计算机图形学C2,C3,C4C2,C3,C4C6C6接口技术接口技术C3C3C7C7数据库原理数据库原理C2,C9C2,C9C8C8编译原理编译原理C4C4C9
33、C9操作系统操作系统C2C2C1C3C4C7C6C5C2C8C9 算法：如何确定课程的次序关系算法：如何确定课程的次序关系?模型：？模型：？从上述例子不难看出：从上述例子不难看出：解决问题的一个关解决问题的一个关键步骤是，选取合适的数据结构表示该键步骤是，选取合适的数据结构表示该问题，然后才能写出有效的算法。问题，然后才能写出有效的算法。1.3 算法的描述和分析v有穷性：有穷性：对于任意一组合法输入值，在对于任意一组合法输入值，在执行执行有穷步有穷步之后结束，且算法中的每个步之后结束，且算法中的每个步骤都能在骤都能在有限时间有限时间内完成；内完成；v确定性：确定性：每条指令都有确切的含义，在每
34、条指令都有确切的含义，在任何条件下算法都只有一条执行路径；任何条件下算法都只有一条执行路径；算法五个重要特性：算法五个重要特性：算法：是对特定问题求解算法：是对特定问题求解步骤的一种描述步骤的一种描述，它是指令的有限序列。它是指令的有限序列。v可行性：可行性：算法中的所有操作都必须算法中的所有操作都必须足够足够基本基本，都可以通过已经实现的基本操作运，都可以通过已经实现的基本操作运算有限次实现之；算有限次实现之；v输入：输入：有零个或多个输入，取自特定的有零个或多个输入，取自特定的对象集合对象集合v输出：输出：有一个或多个输出，是算法进行有一个或多个输出，是算法进行信息加工后得到的结果。信息加
35、工后得到的结果。二、算法分析二、算法分析1评价算法好坏的标准评价算法好坏的标准求解同一计算问题可能有许多不同的算法，究求解同一计算问题可能有许多不同的算法，究竟如何来评价这些算法的好坏以便从中选出较好的竟如何来评价这些算法的好坏以便从中选出较好的算法呢？算法呢？选用的算法首先应该是选用的算法首先应该是正确正确的。此外，主要考的。此外，主要考虑如下三点：虑如下三点：执行算法所耗费的时间；执行算法所耗费的时间；执行算法所耗费的存储空间，其中主要考虑辅助执行算法所耗费的存储空间，其中主要考虑辅助存储空间；存储空间；算法应易于理解，易于编码，易于调试等等。算法应易于理解，易于编码，易于调试等等。v2算
36、法性能选择算法性能选择一个占存储空间小、运行时间短、其它性能一个占存储空间小、运行时间短、其它性能也好的算法是很难做到的。原因是上述要求有时也好的算法是很难做到的。原因是上述要求有时相互抵触：要节约算法的执行时间往往要以牺牲相互抵触：要节约算法的执行时间往往要以牺牲更多的空间为代价；而为了节省空间可能要耗费更多的空间为代价；而为了节省空间可能要耗费更多的计算时间。因此我们只能根据具体情况有更多的计算时间。因此我们只能根据具体情况有所侧重：所侧重：若该程序使用次数较少，则力求算法简明易懂；若该程序使用次数较少，则力求算法简明易懂；对于反复多次使用的程序，应尽可能选用快速对于反复多次使用的程序，应
37、尽可能选用快速的算法；的算法；若待解决的问题数据量极大，机器的存储空间若待解决的问题数据量极大，机器的存储空间较小，则相应算法主要考虑如何节省空间。较小，则相应算法主要考虑如何节省空间。v3算法的时间性能分析算法的时间性能分析（1）算法耗费的时间和语句频度）算法耗费的时间和语句频度一个算法所耗费的时间一个算法所耗费的时间=算法中每条语句的执算法中每条语句的执行时间之和行时间之和每条语句的执行时间每条语句的执行时间=语句的执行次数语句的执行次数(即频度即频度(Frequency Count)语句执行一次所需时间语句执行一次所需时间 算法转换为程序后，每条语句执行一次所需的时算法转换为程序后，每条
38、语句执行一次所需的时间取决于机器的指令性能、速度以及编译所产生的间取决于机器的指令性能、速度以及编译所产生的代码质量等难以确定的因素。代码质量等难以确定的因素。若要独立于机器的软、硬件系统来分析算法的时若要独立于机器的软、硬件系统来分析算法的时间耗费，则设每条语句执行一次所需的时间均是单间耗费，则设每条语句执行一次所需的时间均是单位时间，一个算法的时间耗费就是该算法中所有语位时间，一个算法的时间耗费就是该算法中所有语句的频度之和。句的频度之和。算法执行时间的衡量方法和准则算法执行时间的衡量方法和准则 有有两种两种衡量算法效率的方法衡量算法效率的方法:1.1.事后统计法：利用计算机内记时功事后统
39、计法：利用计算机内记时功能，用一组或多组相同的统计数据区能，用一组或多组相同的统计数据区分。分。2.2.事前分析估计法：求出算法的一个事前分析估计法：求出算法的一个时间界限函数。时间界限函数。和算法和算法执行时间执行时间相关的因素：相关的因素：算法选用的策略算法选用的策略 问题的规模问题的规模 书写程序的语言书写程序的语言 编译程序产生机器代码质量编译程序产生机器代码质量 机器执行指令速度机器执行指令速度v（2）时间复杂度：程序运行从开始到结束）时间复杂度：程序运行从开始到结束所需要的时间。所需要的时间。设解决一个问题的规模为设解决一个问题的规模为n，基本操作，基本操作被重复执行的次数是被重复
40、执行的次数是n的一个函数的一个函数 f（n），），假如，随着问题规模假如，随着问题规模n的增长，算法执行时的增长，算法执行时间的增长率和间的增长率和f(n)的增长率相同，则可记作：的增长率相同，则可记作：T(n)=O(f(n)其中其中T(n)叫算法的叫算法的渐进时间复杂度渐进时间复杂度，简，简称时间复杂度。称时间复杂度。P8例例1 1：NXNNXN矩阵相乘矩阵相乘for(i=1;i=n;i+)for(j=1;j=n;j+)cij=0;for(k=1;k=n;k+)cij=cij+aik*bkj;33)(nOnTnnf 显然，被称做问题的基本操作的原操显然，被称做问题的基本操作的原操作应是其重复
41、执行次数和算法的执行时间作应是其重复执行次数和算法的执行时间成正比的原操作，多数情况下是成正比的原操作，多数情况下是最深层循最深层循环内环内的语句中的原操作，它的执行次数和的语句中的原操作，它的执行次数和包含它的包含它的语句频度语句频度相同。相同。例例2 2+x;s=0;+x;s=0;例例for(i=1;for(i=1;i=n;i=n;+i)+i)+x;+x;s+=x;s+=x;例例.for(i=2;.for(i=2;i=n;i=n;+i)+i)for(j=2;for(j=2;j=i-1;j=1&change;-i)change=false;for(j=0;jaj+1)aj aj+1;chan
42、ge=TURE；最好情况：最好情况：1次次最坏情况：（最坏情况：（n-1）+（n-2）+1=n(n-1)/2平均时间复杂度为：平均时间复杂度为：O(n2)v空间复杂度：算法所需存储空间的度量，记作：空间复杂度：算法所需存储空间的度量，记作：S(n)=O(f(n)算法的存储量包括：（算法的存储量包括：（1）输入数据所占空间；）输入数据所占空间；（2）程序本身所占空间；）程序本身所占空间；（3）辅助变量所占空间。）辅助变量所占空间。注意：算法的所有性能之间都存在着或多或少的相互影响，因此，当设计一个算法，特别是大型算法时，要综合考虑算法的各项性能、算法的使用频率、算法处理的数据量的大小、算法描述语言的特性及算法运行的机器系统环境等各方面因素，才能设计出比较好的算法。（3）算法的存储空间需求）算法的存储空间需求 1.熟悉各名词、术语的含义，掌握基本概念。2.理解学习数据结构的意义。本章学习要点本章学习要点3.掌握计算语句频度和估算算法时间复杂度的方法。
