数据结构课件

1、数据结构讲课教师：杜雅娟Emil:电话Q:295858698课程介绍数据结构课程教学目标 使学生学会分析数据对象的特征，掌握数据组织方法和计算机中的表示方法，以便为应用所涉及数据选择适当的数据结构、存储结构和算法，初步掌握算法空间分析的技巧，培养良好的程序设计技能。学习数据结构的学习方法 学习数据结构必须经过大量的实践，在实践中体会构造思维方法，掌握数据组织和程序设计的技术。 要求： （1）独立完成作业 （2）独立完成实验任务 考核要求：平时作业10% 实验成绩20% 期末卷面分数70% 为什么要学习数据结构？为什么要学习数据结构？v计算机加工处理的对象 纯粹的数值

2、字符、表格和图象等为了编写一些“好”的程序，必须分析待处理对象的特性以及各处理对象间的关系。这就是“数据结构”这门学科形成和发展的原因。 1 1、“数据结构数据结构”学科形成和发展的背学科形成和发展的背景景v计算机的应用: 科学计算(数值计算) 控制、管理及数据处理(非数值计算)具有一定结构的数据具有一定结构的数据“数据结构数据结构”学科形成和发展的背景学科形成和发展的背景形成阶段：形成阶段： 60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。发展阶段：发展阶段： 数据结构的概念不断扩充，包括了网络

3、、集合代数论、关系等“离散数学结构”的内容。 70年代后期，我国高校陆续开设该课程。如今已成熟 数据结构的研究目的是寻求有效的组织和处理非数值数据的理论技术和方法,这类数据具有量大且具有一定内在逻辑关系的特点。 数据结构的研究内容包括三个方面:数据的逻辑结构数据的逻辑结构,存储结构存储结构以及相应的基基本操作运算的定义和实现本操作运算的定义和实现。2 2、数据结构的研究目的和研究内容、数据结构的研究目的和研究内容前期课程前期课程后期课程后期课程数据结构数据结构计算机基础计算机基础C语言语言离散数学离散数学操作系统操作系统编译原理编译原理数据库原理数据库原理软件工程软件工程承上承上启下启下 3

4、3、“数据结构数据结构”是计算机及相关专业的专业基础课之是计算机及相关专业的专业基础课之一，是门十分重要的核心课程一，是门十分重要的核心课程。C语言语言 数据结构数据结构 软件工程软件工程掌握基本编掌握基本编程方法程方法掌握数据组掌握数据组织和数据处织和数据处理的方法理的方法掌握大型软掌握大型软件开发方法件开发方法学习识字学习识字学习写作文学习写作文学习写小说学习写小说基本要求课程关系与语文学习过程类比4 4、C C语言语言、数据结构数据结构和和软件工程软件工程三门课之间的关系：三门课之间的关系：1.1 1.1 什么是数据结构什么是数据结构1.2 1.2 基本概念和术语基本概念和术语1.3 1

5、.3 抽象数据类型的表示与实现抽象数据类型的表示与实现1.4 1.4 算法和算法分析算法和算法分析 一般来说，用计算机解决一个具体问题时，大致需要经过下列几个步骤：（1）首先要从具体问题抽象出一个适当的数学模型；（2）然后设计一个解此数学模型的算法；（3）最后编出程序、进行测试、调整直至得到最终解答。1.1 1.1 什么是数据结构什么是数据结构分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。例如，求解梁架结构中应力的数学模型为线性方程组；预报人口增长情况的数学模型为微分方程。然而，更多的非数值计算问题无法用数学方程加以描述。下面请看三个例子： 寻求数学

6、模型的实质：例1:图书馆的书目检索系统的自动化 在书目检索系统中可以建立一张按登录号顺序排列的书目文件和三张分别按书名、作者名和分类号顺序排列的索引表。 由这由这4 4张表构成的文件张表构成的文件便是书目自动检索的数学便是书目自动检索的数学模型，其中计算机处理的模型，其中计算机处理的对象之间存在着线性关系，对象之间存在着线性关系，这类数学模型可称为线性这类数学模型可称为线性的数据结构。的数据结构。例例2 2：人和计算机对弈：人和计算机对弈算法：算法：模型：模型：对弈的规则和策略棋盘及棋盘的格局(a)(a)棋盘格局示例棋盘格局示例 计算机处理的对象之间有树关系，计算机处理的对象之间有树关系，对弈

7、过程就是从树根到树叶的过程。对弈过程就是从树根到树叶的过程。(b)(b)对弈树的局部对弈树的局部例例3 3 多叉路口交通灯的管理问题多叉路口交通灯的管理问题ABCDE 在路口有13条可行的通路，其中有的可以同时通行，如A至B和E至C，而有的不能同时通行，如E至B和A至D。 这类交通、道路问题的数学模型是一种称为“图”的数据结构。五叉路口交通管理问题等价于对图的顶点的染色问题。即要求对图上的每个顶点染一种颜色，并且要求有连线的两个顶点不能具有相同的颜色。BDBCDBABACADBADADCEAEBECED概括地说：概括地说： 数据结构是一门研究非数值计数据结构是一门研究非数值计算程序设计问题中的

8、算程序设计问题中的计算机的操计算机的操作对象作对象以及它们之间以及它们之间关系关系和和操作操作等的学科。等的学科。1.2 1.2 基本概念基本概念一、一、数据与数据结构数据与数据结构二、二、数据类型数据类型三、三、抽象数据类型抽象数据类型一、数据与数据结构一、数据与数据结构 所有能被输入到计算机中，且能被计算机所有能被输入到计算机中，且能被计算机处理的符号的集合。处理的符号的集合。1 1、数据、数据(data)(data) 是计算机操作的对象的总称。是计算机操作的对象的总称。 是计算机处理的信息的某种特定的符号表是计算机处理的信息的某种特定的符号表示形式。示形式。是数据（集合）中的一个“个体”

9、。2 2、数据元素、数据元素(data element)(data element)是数据结构中讨论的基本单位基本单位 3、数据项数据项(data item)(data item)：是数据结构中讨论的最小单位最小单位数据元素可以是数据项的集合数据元素可以是数据项的集合例如：描述学生的数据元素可以是年年月月日日称之为组合项称之为组合项学号学号姓名姓名性别性别年龄年龄出生日期出生日期成绩成绩是性质相同的数据元素的集合，是数据的一个子集。整数数据对象是集合整数数据对象是集合N=0N=0，1 1，2 2，字母字符数据对象是集合字母字符数据对象是集合C=AC=A，BB，ZZ。 4 4、数据对象、数据对象

10、(Data Object)(Data Object)例如：5 5、数据结构（、数据结构（data structuredata structure）可以认为是带结构结构的数据元素的集合3214,6587,9345 a1(3214),a2(6587),a3(9345)则在数据元素 a1、a2 和 a3 之间存在着“次序次序”关系关系 a1,a2 、 a2,a3 3214，6587，9345 a1 a2 a3 6587，3214，9345 a2 a1 a3例如例如: :又例，在2行3列的二维数组a1, a2, a3, a4, a5, a6中六个元素之间存在两个关系: a1 a2 a3 a4 a5 a

11、6行的次序关系行的次序关系:列的次序关系列的次序关系: :row = ,col = , a1 a3 a5 a2 a4 a6 a1 a2 a3a4 a5 a6数据结构：数据结构： 带结构结构的数据元素的集合再例，在一维数组 a1, a2, a3, a4, a5, a6 的数据元素之间存在如下的次序关系次序关系:| i=1, 2, 3, 4, 5数据结构：数据结构： 带结构结构的数据元素的集合可见，不同的“关系关系”构成不同的“结构结构” 或者说，数据结构数据结构是相互之间存在相互之间存在着某种逻辑关系的数据元素的集合着某种逻辑关系的数据元素的集合。数据的逻辑结构逻辑结构可归结为以下四类四类: :

12、线性线性结构树形树形结构图状图状结构集合集合结构数据结构的形式定义数据结构的形式定义为:数据结构数据结构是一个二元组 Data_Structures = (D, S)其中:D 是数据元素的有限集数据元素的有限集， S 是 D上关系的有限集关系的有限集。例4，复数是一种数据结构Complex=(C,R)其中，C=c1,c2;R=P,而P是定义在D上的一种关系用来表示c1是复数的实部，c2是复数的虚部。Group = (PGroup = (P，R) R) 例例5 5（P5 P5 例例1-51-5）其中其中: P = T: P = T，G1G1，GnGn，S11SnmS11Snm1=n=31=n=3

13、，1=m=21=m=2， R = R1, R2R = R1, R2R1 = | 1=i=n, 1=n=3 R1 = | 1=i=n, 1=n=3 R2 = | 1=i=n, 1=j=m, R2 = | 1=i=n, 1=j=m, 1=n=3, 1=m=2 1=n=3, 1=m=2 数据的数据的存储结构存储结构 逻辑结构在存储器中的映象逻辑结构在存储器中的映象“数据元素数据元素”的映象的映象 ？“关系关系”的映象的映象 ？数据元素的映象方法：数据元素的映象方法：用二进制位(bit)的位串表示数据元素(321)10 = (501)8 = (101000001)2 A = (101)8 = (001

14、000001)2关系的映象方法：关系的映象方法：（表示x, y的方法）1 1、顺序映象、顺序映象借助元素在存储器中的借助元素在存储器中的相对位置相对位置来来表示数据元表示数据元素之间的关系素之间的关系借助指示元素存储地址的指针（借助指示元素存储地址的指针（PointerPointer）表示）表示数据元素之间的逻辑关系。数据元素之间的逻辑关系。整个存储结构中只含数据元素本身的信息整个存储结构中只含数据元素本身的信息2 2、非顺序映象、非顺序映象 数据的逻辑结构和物理结构是密切相关的两个方面，以后大家会看到，任何一个算法的设计取决于选定的数选定的数据据( (逻辑逻辑) )结构，结构，而算法的实现依

15、赖于采用的存储结构采用的存储结构。如何描述存储结构？ 通常只在高级语言（例如，C/C+）的层面上讨论存储结构。即用高级编程语言中提供的数据类型描述之。 在用高级程序语言编写的程序中在用高级程序语言编写的程序中, ,必必须对程序中出现的每个变量、常量或表须对程序中出现的每个变量、常量或表达式达式, ,明确说明它们所属的数据类型。不明确说明它们所属的数据类型。不同类型的变量同类型的变量, ,其所能取的值的范围不同其所能取的值的范围不同, ,所能进行的操作不同。所能进行的操作不同。 二、数据类型二、数据类型如如C/C+C/C+中的中的intint就是整型数据类型。就是整型数据类型。它是所有整数的集合

16、它是所有整数的集合( (在在1616位计算机中位计算机中为为3276832768到到3276732767的全体整数的全体整数) )和相关和相关的整数运算的整数运算( (如、等如、等) )。例如，C 语言中提供的基本数据类型基本数据类型有:整型整型 int浮点型浮点型 float字符型字符型 char逻辑型逻辑型 bool （ C+语言）语言）双精度型双精度型 double实型（实型（ C+语言）语言） 数据类型是一个值的集合和定义在此集合上的一组操作的总称。 不同类型的变量，其所能取的值的范围值的范围不同，所能进行的操作进行的操作不同。 那么，我们仅用高级编程语言中提供的数据类型描述存储结构就

17、可以了吗？三、抽象数据类型三、抽象数据类型 (Abstract Data Type 简称简称ADT) 抽象数据类型抽象数据类型(Abstract Data Type简写为简写为ADT)指的是用户进行软件系统设计时从问题的数学模指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上型中抽象出来的逻辑数据结构和逻辑数据结构上的运算的运算,而不考虑计算机的具体存储结构和运算的而不考虑计算机的具体存储结构和运算的具体实现算法。具体实现算法。 抽象数据类型的描述方法抽象数据类型的描述方法抽象数据类型可用（抽象数据类型可用（D D，S S，P P）三元组表示。）三元组表示。其

18、中：其中：D D 是数据对象；是数据对象； S S 是是 D D 上的关系集；上的关系集； P P 是对是对 D D 的基本操作集。的基本操作集。 ADT ADT 有两个重要特征:数据抽象数据抽象用用ADTADT描述程序处理的实体时，强调的是其本描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。户的接口（即外界使用它的方法）。数据封装数据封装将实体的外部特性和其内部实现细节分离，并将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏且对外部用户隐藏其内部实现细节。其内部实现细节。ADTADT 抽

19、象数据类型名抽象数据类型名 数据对象：数据对象：数据对象的定义 数据关系：数据关系：数据关系的定义 基本操作：基本操作：基本操作的定义 ADT ADT 抽象数据类型名其中基本操作的定义格式为:基本操作名基本操作名（参数表） 初始条件：初始条件：初始条件描述 操作结果操作结果：操作结果描述 赋值参数赋值参数 只为操作提供输入值。引用参数引用参数 以& &打头，除可提供输入值外，还将返回操作结果。初始条件初始条件 描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。操作结果操作结果 说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始

20、条件为空，则省略之。例例6 6，抽象数据类型复数复数的定义： 数据对象：数据对象： De1,e2e1,e2RealSet 数据关系：数据关系： R1 | e1是复数的实数部分 | e2 是复数的虚数部分 ADT Complex 基本操作：基本操作：AssignComplex( &Z, v1, v2 )AssignComplex( &Z, v1, v2 ) 操作结果：构造复数 Z,其实部和虚部 分别被赋以参数 v1 和 v2 的值。DestroyComplex( &Z) 操作结果：复数Z被销毁。 GetReal( Z, &realPart )GetReal( Z,

21、 &realPart ) 初始条件：复数已存在。 操作结果：用realPart返回复数Z的实部值。 GetImag( Z, &ImagPart )GetImag( Z, &ImagPart )初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。 Add( z1,z2, &sum )Add( z1,z2, &sum )初始条件：z1, z2是复数。操作结果：用sum返回两个复数z1, z2 的和值。 ADT Complex假设:z1和z2是上述定义的复数则 Add(z1, z2, z3) 操作的结果z3 = z1 + z2即抽象数据类型的

22、好处：对外部用户隐藏其内部细节例例7 7：抽象数据类型三元组的定义：抽象数据类型三元组的定义ADTTriplet 数据对象：D=e1,e2,e3 | e1,e2,e3ElemSet 数据关系：R1=, 基本操作： InitTriplet(&T,v1,v2,v3) 操作结果：构造了三个元组T，元素e1,e2和e3分别被赋以参数v1,v2和v3的值。 DestroyTriplet(&T) 操作结果：三元组T被销毁Get(T , i, &e ) 初始条件：三元组T已存在，1i3 操作结果：用e返回T的第i个元的值。Put(&T, i, e ) 初始条件：三元组T已存在

23、，1i3 操作结果：改变T的第i个元的值。IsAscending(T) 初始条件：三元组T已存在 操作结果：如果T的元素按升序排列，则返回1，否则返回0。 IsDscending(T) 初始条件：三元组T已存在 操作结果：如果T的元素按降序排列，则返回1，否则返回0。 Max(T,&e) 初始条件：三元组T已存在 操作结果：用e返回T的3个元素中的最大值。Min(T,&e) 初始条件：三元组T已存在 操作结果：用e返回T的3个元素中的最小值。ADT Triplet1.3 1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现一、介绍介绍C/C+C/C+命令命令二、抽象数据类型

24、的表示和实现二、抽象数据类型的表示和实现二、抽象数据类型的表示和实现二、抽象数据类型的表示和实现 抽象数据类型需要通过固有数据固有数据类型类型来表示和实现。例例8 8 抽象数据类型三元组（抽象数据类型三元组（Trip1etTrip1et）的表）的表示和实现。示和实现。/-/-采用动态分配的顺序存储结构采用动态分配的顺序存储结构typedef ElemType *Triplet；/Triplet/Triplet类型是类型是ElemTypeElemType类型的指针，类型的指针，/存放存放ElemTypeElemType类型的地址。类型的地址。/-/-基本操作的函数原型说明基本操作的函数原型说明-

25、 Status InitTriplet (Triplet &TStatus InitTriplet (Triplet &T，ElemType vlElemType vl，ElemType v2ElemType v2， ElemType v3)ElemType v3)； /操作结果：构造了三元组操作结果：构造了三元组T T，元素，元素e1e1，e2e2和和e3e3分别被赋以参数分别被赋以参数v1v1，v2v2和和v3v3的值。的值。Status DestroyTriplet (Trlplet &T)Status DestroyTriplet (Trlplet &T

26、)； /操作结果：三元组操作结果：三元组T T被销毁。被销毁。Status Put(Triplet &TStatus Put(Triplet &T，int iint i，ElemType e )ElemType e ) ; ; / /初始条件：三元组初始条件：三元组T T已存在，已存在，1i31i3。 /操作结果：改变操作结果：改变T T的第的第i i元的值为元的值为e eStatus Get(Triplet TStatus Get(Triplet T，int iint i，ElemType &e)ElemType &e)；/初始条件：三元组初始条件：三元组T

27、T已存在，已存在，1i31i3。/操作结果：用操作结果：用e e返回返回T T的第的第i i元的值。元的值。Status IsDescending (Triplet T)Status IsDescending (Triplet T)；/初始条件：三元组初始条件：三元组T T已存在。已存在。/操作结果：如果操作结果：如果T T的三个元素按降序排列，的三个元素按降序排列，/则返回则返回1 1，否则返回，否则返回0 0。Status IsAscending (Triplet T)Status IsAscending (Triplet T)；/初始条件：三元组初始条件：三元组T T已存在。已存在。/操

28、作结果：如果操作结果：如果T T的三个元素按升序排列，则返的三个元素按升序排列，则返回回1 ,1 ,否则返回否则返回0 0。Status Min(Triplet TStatus Min(Triplet T，ElemType &e)ElemType &e)；/初始条件：三元组初始条件：三元组T T已存在。已存在。/操作结果：用操作结果：用e e返回返回T T的三个元素中的最小值。的三个元素中的最小值。Status Max(Triplet TStatus Max(Triplet T，ElemType &e)ElemType &e)；/初始条件：三元组初始条件：三元组

29、T T已存在。已存在。/操作结果：用操作结果：用e e返回返回T T的三个元素中的最大值。的三个元素中的最大值。/- - - - -/- - - - -基本操作的实现基本操作的实现- - - - - - - - - - - - Status InitTriplet(Triplet &T，ElemType vl，ElemType v2，ElemType v3) /构造二元组构造二元组T T，依次置，依次置T T的三个元素的初值为的三个元素的初值为v1v1，v2v2和和v3v3。 T = (ElemType *)malloc(3 * sizeof(ElemType)； if ( !T )

30、exit (OVERFLOW)； /分配存储空间失败 T0 = v1； T1 = v2；T2 = v3； return OK； /InitTriplet Status DestroyTriplet (Triplet &T)/销毁三元组T。free(T)；T = NULL； eturn OK；/ DestroyTripletStatus Get ( Triplet T，int i，ElemType &e) /1i3，用e返回T的第i元的值。if(i3) return ERROR；e = Ti-1；return OK； /GetStatus Put(Triplet &T，i

31、nt i，ElemType e) /1i3，置T的第i元的值为e。if (i3) return ERROR；Ti-1 = e；return OK；/PutStatus lsAscending (Triplet T)/如果T的三个元素按升序排列，则返回1，否则返回0。return(T0=T1)&(T1=T1)&(T1=T2)； /IsDescending Status Max( Triplet T，ElemType e)/用e返回指向T的最大元素的值。e = (T0 =T1) ? ( (T0 =T2)? T0 : T2) : ( (T1=T2)? T1 : T2) ；return

32、 OK； /MaxStatus Min (Triplet T，ElemType e)/用e返回指向T的最小元素的值。e = (T0=T1)? ( (T0 =T2)? T0 : T2) : ( (T1=0)个初始数据的输入。 （5 5）输出数据）输出数据-一个算法有一个或多个与输入有某种关系的有效信息的输出。 思考：算法与程序有何区别？例例9 考虑下列两段描述：考虑下列两段描述：(1)void exam1( ) n2; while (n%20) nn+2; printf(%dn,n); (2)void exam2() y=0; x=5/y; printf(“%d,%dn”,x,y); 这两段描述

33、均不能满足算法的特征这两段描述均不能满足算法的特征,试问试问它们违反了哪些特征？它们违反了哪些特征？算法与程序的区别算法与程序的区别程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的求解过程，而程序则是算法在计算机上的实现。算法用特定的程序设计语言来描述，就成了程序。1.4.2 1.4.2 算法设计的要求算法设计的要求通常设计一个通常设计一个“好好”的算法应考虑达到以下目的算法应考虑达到以下目标：标：(1)(1)正确性正确性 (Correctness) p14(Correctness) p14(2)(2)可读性可读性(Readability)(Readability)

34、 (3)(3)健壮性健壮性(Robustness)(Robustness) (4)(4)效率与低存储量需求效率与低存储量需求 (1) (1) 正确性正确性 首先，首先，算法应当满足满足以特定的“规格说明规格说明”方式给出的需求需求。 其次，其次，对算法是否“正确正确”的的理解可以有以下四个层次四个层次：a a程序中不含语法错误；b b程序对于几组输入数据能够得出满足要求的结果； c.程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；通常以第c c层意义的正确性作为衡量一个算法是否合格的标准。 d.d.程序对于一切合法的输入数据都能得出满足要求的结果；(2) (2)

35、 可读性可读性 算法主要是为了人的阅读与交流阅读与交流，其次才是为计算机执行，因此算法应该易易于于人的理解理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。(3) (3) 健壮性健壮性 当输入的数据非法非法时，算法应当恰当地作出反映或进行相应处理进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法处理出错的方法不应是中断程序的执行，而应是返回返回一个表示错表示错误或错误性质的值误或错误性质的值，以便在更高的抽象层次上进行处理。(4) (4) 高效率与低存储量需求高效率与低存储量需求通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间，两者都与问题的规模

36、有关。1.4.3 1.4.3 算法效率的度量算法效率的度量度量一个程序的执行时间通常有两种方法：度量一个程序的执行时间通常有两种方法：(1)(1)事后统计的方法事后统计的方法( (算法编为程序后算法编为程序后) )(2)(2)事前分析估算的方法事前分析估算的方法 P14P14事后统计法事后统计法事前分析估算法事前分析估算法缺点：缺点：1必须执行程序 2其它因素掩盖算法本质和算法执行时间时间相关的因素因素：1 1算法算法选用的策略的策略2 2问题的规模问题的规模3 3编写程序的语言语言4 4编译编译程序产生的机器代码的质量的质量5 5计算机计算机执行指令的速度的速度 一个特定算法的算法的“运行工

37、作量运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数是问题规模的函数。 假如，随着问题规模 n 的增长，算算法执行时间的增长率和法执行时间的增长率和 f(n) f(n) 的增长率相的增长率相同同，则可记作：T (n) = O(f(n)称称T (n) T (n) 为算法的为算法的(渐近)时间复杂度。时间复杂度。 记号记号“O”读作读作“大大O”,它表示随问题规模它表示随问题规模n的增的增大算法执行时间的增长率和大算法执行时间的增长率和f(n)的增长率相同。的增长率相同。“O”的形式定义为：的形式定义为： 若若f(n)是正整数是正整数n的一个函数的一个函数,

38、则则T(n)=O(f(n)表示表示存在一个正的常数存在一个正的常数M,使得当使得当nn0时都满足：时都满足： |T(n)|M|f(n)| 也就是只求出也就是只求出T(n)的最高阶的最高阶,忽略其低阶项和常系忽略其低阶项和常系数数,这样既可简化这样既可简化T(n)的计算的计算,又能比较客观地反映出又能比较客观地反映出当当n很大时很大时,算法的时间性能。算法的时间性能。 例如例如,T(n)=3n2-5n+10000=O(n2)如何估算如何估算 算法的时间复杂度？算法的时间复杂度？算法算法 = = 控制结构控制结构 + + 原操作原操作 （固有数据类型的操作）算法的执行时间算法的执行时间 =原操作原

39、操作(i)(i)的执行次数的执行次数原操作原操作(i)(i)的执行时间的执行时间算法的执行时间算法的执行时间 与与 原操作执行次数之和原操作执行次数之和成正比成正比 从算法中选取一种对于所研究的问题来说是 基本操作基本操作 的原操作，以该基本操作 在算法中重复执行的次在算法中重复执行的次数数作为算法运行时间的衡量准则。例例两两个个矩矩阵阵相相乘乘void mult(int a, int b, int& c ) / 以二维数组存储矩阵元素，c 为 a 和 b 的乘积 for (i=1; i=n; +i) for (j=1; j=n; +j) ci,j = 0; for (k=1; k1

40、& change; -i) / bubble_sort基本操作: 赋值赋值操作时间复杂度: O(nO(n2 2) ) change = FALSE; / change 为元素进行交换标志 for (j=0; j aj+1) aj aj+1; change = TRUE ; / 一趟起泡(1)(1)当当a a中初始序列为自小至大有序，基本操中初始序列为自小至大有序，基本操作的执行次数为作的执行次数为0 0；(2)(2)当当a a中初始序列为自大至小有序时，基本中初始序列为自大至小有序时，基本操作的执行次数为操作的执行次数为n(n-1)/2.n(n-1)/2.对于这类算法的分析，一种解决的

41、办法是计对于这类算法的分析，一种解决的办法是计算它的算它的平均值，平均值，即考虑它对所有可能的输入即考虑它对所有可能的输入数据集的期望值，此时相应的时间复杂度为数据集的期望值，此时相应的时间复杂度为算法的算法的平均时间复杂度。平均时间复杂度。另一种更可行也更常用的办法是讨论算法另一种更可行也更常用的办法是讨论算法在在最坏情况下的时间复杂度，最坏情况下的时间复杂度，即分析最即分析最坏情况以估算算法执行时间的一个上界。坏情况以估算算法执行时间的一个上界。除特别指明外，除特别指明外，以后讨论的时间复杂度均以后讨论的时间复杂度均指最坏情况下的时间复杂度。指最坏情况下的时间复杂度。 一个没有循环的算法的

42、基本运算次数与问题规模一个没有循环的算法的基本运算次数与问题规模n n无关无关, ,记作记作O(1),O(1),也称作常数阶。也称作常数阶。 一个只有一重循环的算法的基本运算次数与问一个只有一重循环的算法的基本运算次数与问题规模题规模n n的增长呈线性增大关系的增长呈线性增大关系, ,记作记作O(n),O(n),也称线性也称线性阶。阶。 其余常用的还有平方阶其余常用的还有平方阶O(nO(n2 2) )、立方阶、立方阶O(nO(n3 3) )、对数阶对数阶O(logO(log2 2n)n)、指数阶、指数阶O(2O(2n n) )等。等。 各种不同数量级对应的值存在着如下关系：各种不同数量级对应的

43、值存在着如下关系： O(1)O(log2n)O(n)O(n*log2n)O(n2)O(n3)O(2n)O(n!) 例例1.4 求两个求两个n阶方阵的相加阶方阵的相加C=A+B的算法如下的算法如下,分分析其时间复杂度。析其时间复杂度。 #define MAX 20 /*定义最大的方阶定义最大的方阶*/ void matrixadd(int n,int AMAXMAX, int BMAXMAX,int CMAXMAX) int i,j; for (i=0;in;i+)for (j=0;jn;j+) Cij=Aij+Bij; 该算法中的基本运算是两重循环中最深层的语句该算法中的基本运算是两重循环中最

44、深层的语句Cij=Aij+Bij,分析它的频度分析它的频度,即即： T(n)= =O(n2) 102101010*11ninininjnnnnn例例1.5 分析以下算法的时分析以下算法的时间复杂度。间复杂度。 int fun(int n) int i,j,k,s; s=0; for (i=0;i=n;i+) for (j=0;j=i;j+) for (k=0;k=j;k+) s+; return(s); 解：解：该算法的基本操该算法的基本操作是语句作是语句s+,其频度：其频度： T(n)= =O(n3)则该算法的时间复杂度则该算法的时间复杂度为为O(n3)。 niijjk0001例：两个NN矩

45、阵相乘的算法如下 for(i = 1；i = n；+i) for(j = 1；j = n；+j) cij = 0； for(k = = 1；k = n；+k) cij + = aik * bki； “乘法乘法”运算是运算是“矩阵相乘问题矩阵相乘问题”的基本操作。整的基本操作。整个算法的执行时间与该基本操作个算法的执行时间与该基本操作( (乘法乘法) )重复执行的重复执行的次数次数n n3 3成正比，记作成正比，记作T(n) = O(nT(n) = O(n3 3) )。example(n) if (n = 1)returnfor i = 1 to nx = x + 1example(n/2)1.

46、4.4 1.4.4 算法的存储空间需求算法的存储空间需求算法的空间复杂度定义为空间复杂度定义为: : 表示随着问题规模表示随着问题规模 n n 的增大，算法的增大，算法运行所需存储量的增长率与运行所需存储量的增长率与g(n) g(n) 的增的增长率相同。长率相同。S(n) = O(g(n)算法的存储量算法的存储量包括:1 1输入数据所占空间输入数据所占空间2 2程序本身所占空间程序本身所占空间3 3辅助变量所占空间辅助变量所占空间 若输入数据输入数据所占空间只取决于问题本身，和和算法无关算法无关，则只需要分析除输入和程序之外的辅辅助变量助变量所占额外空间额外空间。 若所需额外空间相对于输入数据

47、量来说是常数，则称此算法为原地工作原地工作。 若所需存储量依赖于特定的输入，则通常按最坏情况考虑。数据结构参考书数据结构参考书: :1、数据结构教程数据结构教程 李春葆李春葆 清华大学出版社清华大学出版社 200520052 2、数据结构数据结构(C(C语言描述语言描述) )学习指导与习题解答学习指导与习题解答 徐孝凯徐孝凯 贺桂英编著贺桂英编著 清华大学出版社清华大学出版社 199719973 3、从、从数据结构习题与解析数据结构习题与解析第第2 2版李春葆编著，版李春葆编著，清华大学出版社清华大学出版社20042004年年2 2月第二版中选择习题留作业月第二版中选择习题留作业 。1 1、熟

48、悉各名词、术语的含义，深刻理解基本概念，、熟悉各名词、术语的含义，深刻理解基本概念，尤其是理解数据、数据元素和数据项的概念及其相尤其是理解数据、数据元素和数据项的概念及其相互间的关系。互间的关系。2 2、清楚数据结构的逻辑结构、存储结构的联系与区、清楚数据结构的逻辑结构、存储结构的联系与区别以及在数据结构上施加的运算及其实现。别以及在数据结构上施加的运算及其实现。3 3、了解抽象数据类型的定义、表示和实现方法。、了解抽象数据类型的定义、表示和实现方法。4 4、理解抽象数据类型的概念。、理解抽象数据类型的概念。5 5、理解算法的概念及其五个特性，掌握进行简单算、理解算法的概念及其五个特性，掌握进

49、行简单算法分析的方法。法分析的方法。教学要求教学要求补充内容采用采用C/C+C/C+语言描述算法时应该注意的事项语言描述算法时应该注意的事项 说明：说明：C+语言中提供了一种语言中提供了一种引用引用运算符运算符“&”,引用是个别名引用是个别名,当建立引用时当建立引用时,程序用另一个程序用另一个已定义的变量或对象已定义的变量或对象(目标目标)的名字初始化它的名字初始化它,从那从那时起时起,引用作为目标的别名而使用引用作为目标的别名而使用,对引用的改动对引用的改动实际就是对目标的改动。实际就是对目标的改动。 注意：注意：Turbo C不支持引用类型。不支持引用类型。例如：例如： int a

50、=4; /*a为普通的整型变量为普通的整型变量*/ int &b=a; /*b是是a的引用变量的引用变量*/ 这里说明这里说明b变量是变量变量是变量a的引用的引用,b也等于也等于4,之后这两之后这两个变量同步改变。当个变量同步改变。当a改变时改变时b也同步改变，同样，当也同步改变，同样，当b改变时改变时a也同步改变。也同步改变。 引用常用于函数形参中引用常用于函数形参中, ,采用引用型形参时采用引用型形参时, ,在函在函数调用时将形参的改变回传给实参数调用时将形参的改变回传给实参, ,例如例如, ,有如下函数有如下函数( (其中的形参均为引用型形参其中的形参均为引用型形参) )： vo

51、id swap(int &x,int &y) void swap(int &x,int &y) / /* *形参前的形参前的“&”&”符号不是指针运算符符号不是指针运算符* */ / int temp=x; int temp=x; x=y;y=temp x=y;y=temp 当用执行语句当用执行语句swap(a,b)swap(a,b)时时,a,a和和b b的值发生了交换。的值发生了交换。 反之，有以下函数反之，有以下函数swap1( )，当用执行语句，当用执行语句swap1(a,b)时时,a和和b的值不会发生了交换。的值不会发生了交换。 void

52、 swap1(int x,int y) int temp; temp=a;a=b;b=temp; 在在C语言中，由于不支持引用类型，所以采用指语言中，由于不支持引用类型，所以采用指针的方式来回传形参的值，需将上述函数改为：针的方式来回传形参的值，需将上述函数改为： int swap2(int *x, int *y) int temp; temp=*a;/*将将a的值放在的值放在temp中中*/*a=*b; /*将将a所指的值改为所指的值改为*b*/ *b=temp；/*将将b所指的值改为所指的值改为temp*/ 上述函数的调用改为上述函数的调用改为swap2(&a,&b)，显然

53、远不，显然远不如采用引用方式简洁。所以本书后面很多算法都采如采用引用方式简洁。所以本书后面很多算法都采用引用形参。用引用形参。二、介绍二、介绍C/C+C/C+命令命令（1 1）预定义常量和类型：）预定义常量和类型：/函数结果状态代码函数结果状态代码#define TRUE 1 #define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2/Status是函数的类型，其值是函数结果是函数的类型，其值是函数结果状态代码状态代码typedef int Status；(2) (2) 数据结构的表示数据

54、结构的表示数据结构的表示(存储结构)用类型定义(typedef)描述。数据元素类型约定为ElemType，由用户在使用该数据类型时自行定义。(3) (3) 基本操作的算法都用以下形式的基本操作的算法都用以下形式的函数描述：函数描述：函数类型函数名(函数参数表) /算法说明 语句序列 /函数名 (4) (4) 赋值语句赋值语句简单赋值简单赋值变量名变量名 = = 表达式；表达式；串联赋值串联赋值变量名变量名1 = 1 = 变量名变量名2 = = 2 = = 变量名变量名k = k = 表达式；表达式；成组赋值成组赋值 ( (变量名变量名1 1，变量名，变量名k) = (k) = (表达式表达式1

55、 1，表达，表达式式k)k)；结构名结构名 = = 结构名；结构名；结构名结构名 = (= (值值1 1，值，值k)k)；变量名变量名 = = 表达式；表达式；变量名变量名 起始下标起始下标.终止下标终止下标 = =变量名变量名 起始下标起始下标.终止下标终止下标 交换赋值交换赋值变量名变量名变量名；变量名；条件赋值条件赋值 变量名变量名 = = 条件表达式？条件表达式？ 表达式表达式 T : T : 表达式表达式 F F（5 5）选择语句）选择语句(6)(6)循环语句循环语句(7)(7)结束语句结束语句(8) (8) 输入和输出语句输入和输出语句(9) (9) 注释注释 单行注释单行注释 /

56、文字序列文字序列 (10) (10) 基本函数基本函数(11) (11) 逻辑运算约定逻辑运算约定 Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd Edition)计算机程序设计艺术计算机程序设计艺术 第第1卷卷 基本算法（第基本算法（第3版）版）（英文影印版）（英文影印版）作者: Donald E.Knuth / E.KNUTH副标题: 第1卷:基本算法(第3版)英文影印版ISBN: 9787302058144 十位: 7302058148定价: 80.00出版社: 清华大学出版社出版年: 2002-11-

57、1 作者简介Donald.E.Knuth(唐纳德.E.克努特，中文名高德纳)是算法和程序设计技术的先驱者，是计算机排版系统TEX和METAFONT的发明者，他因这些成就和大量创造性的影响深远的著作(19部书和160篇论文)而誉满全球。作为斯坦福大学计算机程序设计艺术的荣誉退休教授，他当前正全神贯注于完成其关于计算机科学的史诗性的七卷集。这一伟大工程在1962年他还是加利福尼亚理工学院的研究生时就开始了。Knuth教授获得了许多奖项和荣誉，包括美国计算机协会图灵奖(ACM Turing Award)，美国前总统卡特授予的科学金奖(Medal of Science)，美国数学学会斯蒂尔奖(AMS

58、Steele Prize)，以及1996年11月由于发明先进技术而荣获的备受推崇的京都奖(Kyoto Prize)。Knuth教授现与其妻Jill生活于斯坦福校园内。 访问Knuth教授的个人主页，可以获得有关本书及本系列其他未出版图书的更多信息： /knuth 本书自第一版出版以来，已经成为世界范围内广泛使用的大学教材和专业人员的标准参考手册。本书全面论述了算法的内容，从一定深度上涵盖了算法的诸多方面，同时其讲授和分析方法又兼顾了各个层次读者的接受能力。各章内容自成体系，可作为独立单元学习。所有算法都用英文和伪码描述，使具备初步编程经验的

59、人也可读懂。全书讲解通俗易懂，且不失深度和数学上的严谨性。第二版增加了新的章节，如算法作用、概率分析与随机算法、线性编程等，几乎对第一版的各个部分都作了大量修订。作者简介作者简介 Thomasd H.Cormen是达特茅斯学院计算机科学系副教授，Charles E.Leiserson是麻省理工学院计算机科学与电气工程系教授，Ronald L.Rivest是麻省理工学院计算机科学系教授，Clifford Stein是哥伦比亚大学工程与运营研究所副教授。算法引论：一种创造性方法算法引论：一种创造性方法国外计算机科学教材系列国外计算机科学教材系列作者：（美）曼博（Manber，U.） 著，黄林鹏 等

60、译 丛书名：国外计算机科学教材系列 出版社：电子工业出版社 ISBN：9787121016653 出版时间：2005-9-1 版次：1 印次： 页数：334 字数：571000 纸张：胶版纸 包装：平装 开本： 线性结构的线性结构的基本特征基本特征为为: :1集合中必存在唯一的一个集合中必存在唯一的一个“第一元素第一元素”；2集合中必存在唯一的一个集合中必存在唯一的一个 “最后元素最后元素” ；3除最后元素在外，均有除最后元素在外，均有 唯一的后继唯一的后继；4除第一元素之外，均有除第一元素之外，均有 唯一的前驱唯一的前驱。线性结构线性结构 是是 一个数据元素的一个数据元素的有序（次序）集有序（次序）集线性表线性表是一种最简单的线性结构线性结构2.1 线性表的类型定义线性表的类型定义2.3 线性表类型的实现线性表类型的实现 链式映象链式映象2.4 一元多项式的表示一元多项式的表示2.2 线性表类型的实现线性表类型的实现 顺序映象顺序映象2.1线性表的类型定义线性表的类型定义抽象数据类型线性表线性表的定义如下：ADT List 数据对象数据对象：D ai | ai ElemSet, i=1,2,.,n, n0 称 n 为线性表的表长表长; 称 n=0 时的线性表为空表空