数据结构与程序设计.ppt

《数据结构与程序设计.ppt》由会员分享，可在线阅读，更多相关《数据结构与程序设计.ppt（56页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 数据结构与算法数据结构与算法 林小拉林小拉电话：电话：8411 2133Email: 课程安排课程安排讲授授3学学时/周，周，实验2学学时/周周（分组）总成成绩：平平时（听（听课、作、作业、期中期中）+期末期末教学用教学用书：Robert L.Kruse and Alexander J.Ryba“Data Structures and Program Design in C+”，高教，高教出版社，出版社，2001年年参考参考书：1数数据据结构构，许卓卓群群，张乃乃孝孝，杨冬冬青青，唐唐世世渭渭，高高等教育出版社，等教育出版社，1987年年 2.数数据据结构构C+与与面面向向对象象的的途途径径

2、，张乃乃孝孝，裘裘宗宗燕燕，高等教育出版社，高等教育出版社，1998年年 3数数据据结构构(C语言言版版），严蔚蔚敏敏、吴吴伟民民，清清华大大学学出版社，出版社，1997年年 4.数数据据结构构与与算算法法，王王若若梅梅等等著著，中中山山大大学学出出版版社社，2000年年为什么学习数据结构为什么学习数据结构计算机科学是计算机科学是-“一种关于信息结构转换的科学一种关于信息结构转换的科学”(Wegnor)Input Output-“算法的学问算法的学问,算法是精确定义的一系列规则算法是精确定义的一系列规则,指指出怎样从给定的输入信息经过有限步骤产生所出怎样从给定的输入信息经过有限步骤产生所求的输

3、出信息求的输出信息”(Knuth)信息结构信息结构(数据结构数据结构)和算法是计算机科学的核心和算法是计算机科学的核心课题课题.两者之间有着本质的联系两者之间有着本质的联系.数据结构数据结构+算法算法=程序程序 Computer system程序程序 =算法算法 +数据结构数据结构 数据数据结构：构：一种程序构件（一种程序构件（programming construct)、工具工具;编程中常用的数据程中常用的数据组织形式及其操作的形式及其操作的抽象抽象；编程：程：数据数据结构的构的选择，算法的算法的设计与度量与度量教学目的教学目的掌握常用的数据掌握常用的数据结构及其构及其应用用学会合理地学会合

4、理地组织数据，有效地表示数据和数据，有效地表示数据和处理理数据数据掌握算法掌握算法设计技技术和分析技和分析技术提高程序提高程序设计质量量第一章第一章 概论概论 q什么是数据什么是数据结构构q抽象数据抽象数据类型型q算法的概念算法的概念q算法的度量算法的度量 数据结构示例 数据结构的概念 数据的逻辑结构 数据的存储结构什么是数据结构什么是数据结构-示例示例1 例例1 图书馆的的书目自目自动检索系索系统 所所处理的基本数据（理的基本数据（数据元素数据元素）：）：每本每本书由（登由（登录号，号，书名，名，作者，出版社作者，出版社,分分类号号)组成；成；数据元素数据元素间的关系（的关系（逻辑结构构）：

5、）：一个按登一个按登录号号顺序排列的序排列的书目表和按目表和按书名、作者和分名、作者和分类号号顺序排列的索引表；序排列的索引表；所需的所需的操作操作：一一组作用在作用在这些表上的运算（些表上的运算（查询、插入、修改等）；、插入、修改等）；怎怎样存存储这些数据及其关系使得上述操作容易些数据及其关系使得上述操作容易实现存存储结构构。什么是数据结构什么是数据结构-示例示例2 例例 2 人机人机对弈弈问题（三子棋）。（三子棋）。数据元素数据元素：格局（某格局（某时刻的棋刻的棋盘布局）；布局）；格局之格局之间的关系的关系：一个格局可以派生出几个下一个格：一个格局可以派生出几个下一个格局（局（树状状结构，

6、博弈构，博弈树）；）；操作操作：由某个格局出：由某个格局出发，借助于以上的格局，借助于以上的格局树（显式式地或非地或非显式地）找出式地）找出计算机算机赢的步的步骤；存存储结构构：如何存：如何存储格局及其格局格局及其格局间的关系。的关系。什么是数据结构什么是数据结构-示例示例3例例 3 3 多岔路口的交通灯管理系多岔路口的交通灯管理系统。BACDE数据元素数据元素：通路，：通路，如：如：A-BA-B通路间的关系通路间的关系（图）：通路为结点，（图）：通路为结点，两节点相邻，如果两通路不能同时两节点相邻，如果两通路不能同时通行。通行。操作操作：上图的着色问题：用最少的颜色，对每个节：上图的着色问题

7、：用最少的颜色，对每个节点着色，相邻节点着不同的颜色。点着色，相邻节点着不同的颜色。存储存储：如何存储通路间的关系：如何存储通路间的关系。第一章第一章 概论概论 q什么是数据什么是数据结构构q抽象数据抽象数据类型型q算法的概念算法的概念q算法的度量算法的度量 数据结构示例 数据结构的概念数据结构的概念 数据的逻辑结构 数据的存储结构数据结构的概念数据结构的概念数据数据是客是客观事物的符号表示，是信息的事物的符号表示，是信息的载体体数据元素数据元素是数据的基本是数据的基本单位位 数据数据结构是相互构是相互间具有某些关系的数据元素的具有某些关系的数据元素的集合。它包括下面三方面的内容：集合。它包括

8、下面三方面的内容：1 1）数据的数据的逻辑结构构，表示数据元素表示数据元素间的关系；的关系；2 2）数据的运算数据的运算，是数据元素集上所允是数据元素集上所允许的操作；的操作；3 3）数据的存数据的存储结构构，指如何在指如何在计算机上数据元素算机上数据元素及其关系。及其关系。第一章第一章 概论概论 q什么是数据什么是数据结构构q抽象数据抽象数据类型型q算法的概念算法的概念q算法的度量算法的度量 数据结构示例 数据结构的概念 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的逻辑结构数据的逻辑结构 数据的数据的逻辑结构是一个二元构是一个二元组（D,R),D 是数是数据元素的有限集，据元素的有限集

9、，R 是是D上关系的有限集；上关系的有限集；例如，在示例例如，在示例3中，中，D=AB,AC,AD,BA,BC,BD,DA,DB,DC,DA,EB,DC,EDR=R1R1=(AB,EA),(AB,BD),(AB,DA),(AB,BC),逻辑结构的类型逻辑结构的类型我我们将将讨论 R 含有一个关系的情况含有一个关系的情况,即即 R=R1.根据根据R1的特性的特性,数据数据结构构(D,R1)可分可分为下列几种下列几种:D=d1,d2,dn 1.集合集合:数据元素同数据元素同“属于一个集合属于一个集合”.R1=2.线性性结构构:R1=(d1,d2),(d2,d3),(d(n-1),dn),即除开始和

10、即除开始和终结节点点d1,dn外外,每个每个节点有点有一个前一个前驱和一个后和一个后继3.树状状结构构:(D,R1)构成构成树,即每个元素最多有即每个元素最多有一个前一个前驱,可以有多个后可以有多个后继4.图状状结构构:(D,R1)构成一个构成一个图.第一章第一章 概论概论 q什么是数据什么是数据结构构q抽象数据抽象数据类型型q算法的概念算法的概念q算法的度量算法的度量 数据结构示例 数据结构的概念 数据的逻辑结构 数据的存储结构数据的存储结构数据的存储结构数据的存储结构 数据（数据（逻辑）结构的存构的存储包含包含数据元素的存数据元素的存储及其及其逻辑关系关系的存的存储设M M为内存的一片存内

11、存的一片存储区域区域.将数据将数据结构存构存储到到计算机内算机内,我我们需要建立一个映射需要建立一个映射(存储映像):):S :D-M S :D-M 即即对于于D D中的每个数据元素中的每个数据元素d,S(d)M,d,S(d)M,并并且且这个映射具有明个映射具有明显地或者地或者隐含地体含地体现R R的能力的能力.根据存根据存储映像的特点映像的特点,存存储结构可分构可分为:顺序存序存储结构、构、链式存式存储结构、索引和散列构、索引和散列等。等。存储结构的分类存储结构的分类:顺序结构顺序结构 顺序的方法序的方法:将将逻辑上相上相邻的元素存的元素存储到物理上相到物理上相邻的存的存储位置位置.常用于常

12、用于线性的数据性的数据结构构.例如例如,D=d1,d2,d3,d4,d5,D=d1,d2,d3,d4,d5 R=(d1,d2),(d2,d3),(d3,R=(d1,d2),(d2,d3),(d3,d4),(d4,d5)d4),(d4,d5)假定一个假定一个结点占一个点占一个单元元,d1 d1存放于存放于200200号号单元元.d1d2d3d4d5200201202203204存储结构的分类存储结构的分类:链式结构链式结构 这种种结构是构是给结点附加一个指点附加一个指针字段字段,指出其后指出其后继节点的位置点的位置,即存放即存放结点的存点的存储单元分元分为两部分两部分:数据项指针项指针项可以有多

13、个,以指示多个后继.例如,R=(d1,d2),(d1,d3),(d2,d4),(d2,d5),(d3,d6)d1d2d3d6d5d4d1d2d3d4d5d6空指针索引索引(Indexing)的方法的方法在在线性性结构中，将每个构中，将每个节点的序号作点的序号作为其索引号。其索引号。索引的存索引的存储结构就是用构就是用节点的索引号来确定点的索引号来确定节点的存点的存储地址。地址。数据存储区12345索引表存储索引号及地址M存储映像：Z-M假假设每个每个节点占用点占用p p个个单元且元且顺序存序存储，q q为开开时节点的存点的存储位置，那么第位置，那么第 i i 个个节点的存点的存储位置位置为 （

14、i-1)*p+qi-1)*p+q存存储映像可以是非映像可以是非线性的。性的。散列（散列（hashing)的方法的方法 散列的方法是用散列的方法是用结点的点的值来确定其地址。来确定其地址。假假设每个数据元素都有一个关每个数据元素都有一个关键字，字，K K是关是关键字的集字的集合。函数：合。函数：称称为散列函数。最好的散列函数最好的散列函数应满足不同的关足不同的关键字具有不同的地址。字具有不同的地址。如果不同的关如果不同的关键字字对应的地址相同，的地址相同，则称称为“碰撞碰撞”（冲突）。（冲突）。h:K-M以上四种方法可以以上四种方法可以组合使用。例如，合使用。例如，先用散列的先用散列的方法存方法

15、存储表，表，发生碰撞生碰撞时，用一个用一个链表存表存储所有所有的同的同义词。逻辑结构相同，但存构相同，但存储结构不同，构不同，则认为是不同是不同的数据的数据结构。构。如如顺序表和序表和链表具有相同的表具有相同的逻辑结构，但存构，但存储结构分构分别为顺序序结构和构和链表表结构。构。第一章第一章 概论概论q什么是数据什么是数据结构构q抽象数据抽象数据类型型q算法的概念算法的概念q算法的度量算法的度量数据类型数据类型(Data Type)一般的高一般的高级语言都提供了一些言都提供了一些数据数据类型型,如整数如整数型型,字符型等字符型等.数据数据类型是一个型是一个值的集合和定的集合和定义在此集合上的一

16、在此集合上的一组操作的操作的总称称.用用户还可以定可以定义自己的数据自己的数据类型型.数据数据类型可分型可分为原子类型(不可分解的不可分解的,如如int,int,bool,char bool,char 等等)和和结构类型(由其他由其他类型构成型构成)数据数据类型型为程序程序员提供了极大的方便提供了极大的方便:它将数据它将数据集合及其上的操作与其集合及其上的操作与其实现细节分离开来来,或者或者说将将数据的数据的逻辑表示和运算表示和运算与它与它们的的实现相分离。相分离。程序程序员只需要了解此集合由哪些只需要了解此集合由哪些值构成构成,可以可以进行那些运算行那些运算.抽象数据类型抽象数据类型(ADT

17、)我我们把数据元素集合把数据元素集合(或者一个数据模型或者一个数据模型)及其上的及其上的一一组操作的数学操作的数学说明称明称为抽象数据抽象数据类型型(Abstract(Abstract Data Types),Data Types),常用常用ADTADT表示。表示。例如，表示例如，表示圆的的ADTADT：数据模型：表示数据模型：表示圆的半径和的半径和圆心的三个心的三个实数；数；操作：构造一个操作：构造一个给定定圆心和半径的心和半径的圆；求；求圆的面的面积等等一个数据一个数据结构是一个构是一个ADTADT的的实现。现代程序代程序设计使用信息使用信息隐蔽和数据封装，使得蔽和数据封装，使得ADTAD

18、T的的使用和使用和实现相分离，相分离，ADTADT的使用和的使用和 ADTADT的的实现可以同可以同时进行，行，ADTADT实现的修改不影响的修改不影响ADTADT的使用。的使用。本本课程介程介绍的数据的数据结构将由抽象数据构将由抽象数据结构描述构描述.ADT在在OO语言中的实现语言中的实现在在C+C+中，一个中，一个ADTADT与其与其实现构成一个构成一个class,class,或者或者说抽象数据抽象数据类型可以由型可以由C+C+的的类来描述，来描述，ADTADT的每个的每个运算运算对应一个成一个成员函数。函数。例如，表示例如，表示圆的的class class Circle private:

19、float r,x,y;public:Circle(float v1,float v2,float v3);float area()=return pi*r*r;一个抽象数据一个抽象数据类型中的数据元素集可以是任意型中的数据元素集可以是任意时，即即多态ADTADT，这样的的ADTADT可用可用template来描述。来描述。第一章第一章 概论概论q什么是数据什么是数据结构构q抽象数据抽象数据类型型q算法的概念算法的概念q算法的度量算法的度量算法的概念算法的概念一个一个算法算法是是对特定特定问题求解步求解步骤的一种描述的一种描述,它是指它是指令的有令的有穷序列序列.算法具有以下特性算法具有以下特

20、性:1)1)有有穷性性:一个算法一个算法总是在是在执行有行有穷步后步后结束束 2)2)确定性确定性:算法的每一步都必算法的每一步都必须是明确地定是明确地定义的的.3)3)可行性可行性:算法中的每一步都是可以通算法中的每一步都是可以通过已已经实现的操作来完成的的操作来完成的 4)4)输入入:一个算法有零个或者多个一个算法有零个或者多个输入入,这些些输入入取自于特定的取自于特定的对象集合象集合 5)5)输出出:一个算法有一个或者多个一个算法有一个或者多个输出，它出，它们是与是与输入有特定关系的量入有特定关系的量算法的描述算法的描述算法的描述可以用下列算法的描述可以用下列语言描述：言描述：自然自然语

21、言言 程序程序设计语言言介于自然介于自然语言和程序言和程序设计语言的言的伪代代码框框图算法的设计要求算法的设计要求算法的算法的设计应满足：足：1 1）正确性正确性：对于合法的于合法的输入入产生符合要求的生符合要求的输出；出；2 2）可可读性性：算法：算法应该易易读、便于交流，、便于交流，这也是保也是保证算算法正确性的前提；添加注法正确性的前提；添加注释也是一种增加可也是一种增加可读性的性的办法；法；3 3）健壮性健壮性：当：当输入非法入非法时，算法算法还能做出适当的反能做出适当的反应而不会崩而不会崩溃，如如输出出错误信息；算法中信息；算法中应该考考虑适适当的当的错误处理；理；4 4）效率高且内

22、存消耗小效率高且内存消耗小：效率高指运行：效率高指运行时间短。存短。存储指算法指算法执行行过程中所需的最大存程中所需的最大存储空空间。算法设计算法设计例例:假假设有有n(=1)n(=1)个整数个整数a1,a2,a1,a2,an.,an.要求要求对此数此数列由小到大列由小到大进行排序。行排序。显然然这个数列构成一个个数列构成一个线性性结构。我构。我们选择顺序序存存储结构，即用一个数构，即用一个数组A A存存储此数列及排序后的数此数列及排序后的数列。列。思路：思路：1 1 从未排好序的数列中从未排好序的数列中选出最小的元素，将其放到出最小的元素，将其放到排好序的数列后排好序的数列后 2 2 重复重

23、复这个个过程，直至排序程，直至排序结束。束。a1a2a3an找出最小元素aja1a2a3anaj交换a1和aja1a2a3anaj找出最小元素aja1a2a3anaj交换a2 和aj 进一步细化：假设n个数存放在一个数组A0.n-1中1.循环 i 以1 步长，从0到 n-2,执行 （1）j i /Ai 存储从Ai 到An-1的最小整数 (2)循环 k以1为步长,从i+1到n-1,执行 若Ak Aj,则 j k /从Ai到An中选出最小整数 (3)t Ai;Ai Aj;Aj t /交换Ai,Aj2.算法结束.void selectSort(int a,const int n)/将整数列a0,an

24、-1按非递减序排列 for(int i=0;i n-1;i+)int j=i;/找出ai到an-1的最小数aj for(int k=i+1;k n,k+)if(ak aj)j=k;/j指示当前的最小数 /交换ai和aj int temp t=ai;ai=aj;aj=t;模板模板（Template)前一程序只适用于整数列的排序。事实上，此前一程序只适用于整数列的排序。事实上，此算法适用于任何（定义了比较运算）类型的序列。算法适用于任何（定义了比较运算）类型的序列。我们可以用我们可以用C+C+提供的模板机制来设计一个更通用提供的模板机制来设计一个更通用的排序算法。的排序算法。一个模板函数是适用于很

25、多类型的函数一个模板函数是适用于很多类型的函数:在这在这些类型上运算遵从相同的模式。些类型上运算遵从相同的模式。它带有类型参数它带有类型参数的函数，的函数，当类型参数用特定的参数代换时，编译当类型参数用特定的参数代换时，编译器生成针对此类型的特定函数。器生成针对此类型的特定函数。同样，一个模板类是带有类型参数的类，它适同样，一个模板类是带有类型参数的类，它适用于多种类型。通过简单的类型代换，编译器便用于多种类型。通过简单的类型代换，编译器便可生成代换类型的类。可生成代换类型的类。template class dataList1private:T*element;int arraySize;vo

26、id swap(const int m1,const int m2);int minKey(const int low,const int high);public:dataList(int size=10):arraySize(size),element(new Tsize)dataList()delete element;void sort();template void dataList:swap(const int m1,const int m2)T temp=elementm1;elementm1=elementm2;elementm2=temp;template int dataL

27、ist:minKey(const int low,const int high)int min=low;for(int k=low+1;k=high;k+)if(elementk elementmin)min=k;return min;template void dataList:sort()for(int i=0;iarraySize-1;i+)int j=minKey(i,arraySize-1);if(j!=i)swap(j,i);第一章第一章 概论概论q什么是数据什么是数据结构构q抽象数据抽象数据类型型q算法的概念算法的概念q算法的度量算法的度量算法分析算法分析 解决同一解决同一问题的

28、算法可以有多种。的算法可以有多种。我我们希希望从中望从中选出最出最优的算法，效率高或者存的算法，效率高或者存储空空间小。小。为此，我此，我们需要需要对算法算法进行行评估，分析。通常有估，分析。通常有两种方法：两种方法：事后事后统计：不同算法的程序运行在同一：不同算法的程序运行在同一组输入上，入上，根据根据时间和空和空间的的统计来比来比较优劣。劣。缺陷：事缺陷：事先先编写程序；写程序；依依赖于程序运行的于程序运行的软硬件硬件环境。境。习题:试统计函数函数sort()sort()在不同大小在不同大小输入上的运入上的运行行时间.算法分析算法分析事前估事前估计：一种不考：一种不考虑算法的程序运行算法的

29、程序运行软硬件硬件环境的分析方法。一个算法的运行工作量的大小只境的分析方法。一个算法的运行工作量的大小只依依赖于于问题的的规模。模。通常考通常考虑两个度量：两个度量：时间复复杂度：算法度：算法执行的操作的行的操作的总数作数作为问题规模的函数。模的函数。空空间复复杂度：算法度：算法执行行时所占用的存所占用的存储空空间作作为问题规模的函数。模的函数。时间复杂度时间复杂度对于于给定定规模的模的问题，计算算法运行的算算法运行的总“步数步数”：在算法中在算法中选取一种基本操作作取一种基本操作作为“程序步程序步”（多（多种不同的操作可种不同的操作可视为一个程序步，或者不同的操一个程序步，或者不同的操作具有

30、不同的作具有不同的权）；）；统计算法从开始到运行算法从开始到运行终止止时所需所需总程序步数程序步数T,T,并将其并将其视为问题规模模n n的函数的函数T(n).T(n)T(n).T(n)称称为算算法的法的时间复复杂度。度。例例 迭代累加求和迭代累加求和 float sum(int a,const int n)float s=0.0;/计一步 for(int i=0;i n;i+)s+=ai;/每次循环计步:赋值 return s;总计步数:n+问题的规模即数组的规模n 包含函数调用的赋值语句的程序步数：x=sum(A,n);总步数：调用的步数+1 即 (n+)+1 基本运算的完成时间不应该依基

31、本运算的完成时间不应该依赖于所涉及参数值赖于所涉及参数值求总程序步数求总程序步数(数组的大小n为问题的规模)：void selectSort(int a,const int n)for(int i=0;i n-1;i+)int j=i;/计一次 for(int k=i+1;k n,k+)if(ak aj)j=k;/if 语句最多计步 /此循环总步数=2*(n-i-1)int temp t=ai;ai=aj;aj=t;/计3步 /n-1 次循环,每次 1+*(n-i-1)+3/总计 T(n)=n-2i=0(1+(n-i-1)+3)=（n+4)*(n-1)/T(n)与输入有关系.时间复复杂度度T(

32、n)T(n)可能依可能依赖于于输入，即不同的入，即不同的输入入（相同的（相同的规模）其复模）其复杂度不同，譬如排序算法度不同，譬如排序算法此此时可以可以计算平均复算平均复杂度或者最坏情况复度或者最坏情况复杂度度平均复平均复杂度度(The Average Case)(The Average Case)：所有可能：所有可能输入入数据集的期望数据集的期望值最坏情况复最坏情况复杂度度(The Worst Case)(The Worst Case)：估算最坏情：估算最坏情况下况下时间复复杂度的一个上界度的一个上界这也是通常所指的也是通常所指的复复杂度度复复杂度的度量通常度的度量通常计算到数量算到数量级如

33、果如果f(n)f(n)是一是一个函数，并且存在一个常数个函数，并且存在一个常数c,c,当当n n充分大充分大时，则记为T(n)=O(f(n)如如 T(n)=3n2+12n,则T(n)=O(n2)累加求和的例子累加求和的例子:T(n)=O(n)排序的例子排序的例子:T(n)=O(n2)注意：我注意：我们不写不写T(n)=O(3n2),或者或者T(n)=O(n3),应该取最小的上界。取最小的上界。常常见的复的复杂度：度：O(1),O(log2 n),O(n),O(nlog2 n),O(n2),O(2n),O(n!)T(n)=c f(n)nT(n)200log2n100n5n22n201020001

34、000T1(n)=100nlog n,T2(n)=n2,假设问题规模为n=28规模nT1(n)花费时间T2(n)花费时间1000.06秒秒0.01秒秒10001秒秒1秒秒1000013秒秒100秒秒1000002分分166分分100000033分分16666分分=11.5天天更快的机器还是更快的算法更快的机器还是更快的算法换一个快换一个快10倍的机器能否解决更大的问题呢？倍的机器能否解决更大的问题呢？T(n)n n变化变化 n/n10n100010000n=10n1020n5005000n=10n105nlogn25018423nn10n7.372n270223n=101/2n3.162n13

35、16n=n+3n:原机器一小时解决问题规模，n:新机器一小时解决问题规模大大O表示法表示法加法法加法法则：(n)=T1(n)+T2(n)=O(f1(n)+O(f2(n)=O(max(f1(n),f2(n)即：如果两个程序段的复杂度分别为即：如果两个程序段的复杂度分别为O(f1(n)和和O(f2(n),则将这两个程序段顺序连接的程序的复杂则将这两个程序段顺序连接的程序的复杂度为度为O(max(f1(n),f2(n).例如，考虑以下的程序段：例如，考虑以下的程序段：action1();/action1的时间复杂度为O(f1(n)actions();/action2的时间复杂度为O(f2(n)此程序

36、段的时间复杂度为此程序段的时间复杂度为O(max(f1(n),f2(n).乘法法乘法法则：(n)=T1(n)T2(n)=O(f1(n)O(f2(n)=O(f1(n)f2(n)例例 如，下面的程序段如，下面的程序段：for(i =1;i=n,i+)action()这里，这里，如果以如果以action的时间代价为单位，则的时间代价为单位，则 for 循环的代循环的代价为价为T1(n)=O(n)。假设假设action的时间复杂度为的时间复杂度为O(f(n),按乘按乘法法则，此程序段的时间法杂度为法法则，此程序段的时间法杂度为 O(n f(n).如果一个程序的执行代价为如果一个程序的执行代价为O(f1

37、(n),但其单位是另一个但其单位是另一个程序的执行代价，而后一个程序的执行代价为程序的执行代价，而后一个程序的执行代价为O(f2(n),则则原程序的执行代价为原程序的执行代价为O(f1(n)f2(n).空间复杂度空间复杂度计算算法运行算算法运行过程所占用的存程所占用的存储量作量作为问题规模模的函数的函数 S(n)=O(f(n).通常以通常以简单变量的存量的存储空空间为单位位算法的存算法的存储空空间包括：包括：1 1）程序本身、常量和）程序本身、常量和变量等所需空量等所需空间 2 2）程序运行中）程序运行中动态申申请的空的空间和和递归调用所用所需空需空间通常考通常考虑除除输入和程序以外的空入和程

38、序以外的空间.如果相如果相对于于输入是常数入是常数,则称称为原地工作原地工作.如如sum sum 和和selectSort.selectSort.NotationT(n)is said to be(g(n),if there exist two positive constants c and n0 such that T(n)cg(n)for all nn0.For example,for selectSort(),T(n)=(n2)An algorithm is said to be(h(n)if it is O(h(n)and(h(n).For selectSort(),T(n)=(n2

39、)T(n)=(h(n),if the limit of T(n)/h(n)is a nonzero constant.小结和要求小结和要求理解数据理解数据结构和算法的内容构和算法的内容理解和掌握抽象数据理解和掌握抽象数据类型的概念型的概念掌握使用程序掌握使用程序设计语言描述数据的存言描述数据的存储结构构掌握算法的概念，算法的定掌握算法的概念，算法的定义和特点和特点理解理解设计算法的一般要求算法的一般要求掌握算法的掌握算法的设计与描述与描述掌握算法掌握算法时间复复杂度的概念、表示法和基本分析方度的概念、表示法和基本分析方法法上机实习上机实习1.定定义集合的集合的ADT并并实现之（包括集合的交之（

40、包括集合的交,并并,判定判定是否是否为空空,求基数等运算）。求基数等运算）。2.编写一个程序写一个程序创建（英文）文本文件的索引：建（英文）文本文件的索引：统计一个文本文件每个一个文本文件每个词出出现的所有行号并按字典序的所有行号并按字典序排列之。排列之。进一步一步统计文件的行数和文件的行数和总字数。字数。3.编写一个写一个汉字字输入方法。入方法。4.实现一个排序算法一个排序算法.a)利用事后利用事后统计法法观察其察其时间复复杂度度.(利用某种方利用某种方法生成足法生成足够大的大的输入入,将将输入和入和输出存到文件中以出存到文件中以便于便于观察察.)b)利用事前估利用事前估计法估算其复法估算其复杂度度,并用大并用大O表示法表表示法表示之示之.c)你是如何确保你的排序是正确的你是如何确保你的排序是正确的?能否能否给出一种函出一种函数数测试排序的正确性排序的正确性?