数据结构 李云清 杨庆红 揭安全 第01章_概论课件.pptx

《数据结构 李云清 杨庆红 揭安全 第01章_概论课件.pptx》由会员分享，可在线阅读，更多相关《数据结构 李云清 杨庆红 揭安全 第01章_概论课件.pptx（53页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、李云清李云清 杨庆红杨庆红 揭安全揭安全人民邮电出版社人民邮电出版社（第（第2版）版）（第（第2版）版）3/6/20232首首 页页 上一页上一页 下一页下一页 返返 回回 退退 出出什么是数据结构什么是数据结构数据类型和抽象数据类型数据类型和抽象数据类型算法和算法分析算法和算法分析第一章 概述3/6/20233首首 页页 上一页上一页 下一页下一页 返返 回回 退退 出出 瑞士著名的计算机科学家瑞士著名的计算机科学家Nicklaus WirthNicklaus Wirth在在19761976年出版了一本书，书名为年出版了一本书，书名为算法算法算法算法+数据结构数据结构数据结构数据结构=程序设

2、程序设程序设程序设计计计计，它正说明了数据结构在程序设计中的作用。程，它正说明了数据结构在程序设计中的作用。程序设计的实质即为计算机处理问题编制一组序设计的实质即为计算机处理问题编制一组 指令指令，首先需要解决两个问题：即算法和数据结构。算法即首先需要解决两个问题：即算法和数据结构。算法即处理问题的策略，而数据结构即为问题的数学模型。处理问题的策略，而数据结构即为问题的数学模型。很多数值计算问题的数学模型通常可用一组线性很多数值计算问题的数学模型通常可用一组线性或非线性的代数方程组或微分方程组来描述，而大量或非线性的代数方程组或微分方程组来描述，而大量非数值计算问题的数学模型正是本门课程要讨论

3、的数非数值计算问题的数学模型正是本门课程要讨论的数据结构。据结构。第一章 概述3/6/20234首首 页页 上一页上一页 下一页下一页 返返 回回 退退 出出例一、求例一、求 n n 个整数中的最大值。这似乎不成问题，个整数中的最大值。这似乎不成问题，但如果这些整数的值有可能达到但如果这些整数的值有可能达到10101212，那么对，那么对3232位的计位的计算机来说，就存在一个如何表示的问题。算机来说，就存在一个如何表示的问题。例二、交叉路口的红绿灯管理。如今十字路口横例二、交叉路口的红绿灯管理。如今十字路口横竖两个方向都有三个红绿灯，分别控制左拐、直行和竖两个方向都有三个红绿灯，分别控制左拐

4、、直行和右拐，那么如何控制这些红绿灯既使交通不堵塞，又右拐，那么如何控制这些红绿灯既使交通不堵塞，又使流量最大呢？若要编制程序解决问题，首先要解决使流量最大呢？若要编制程序解决问题，首先要解决一个如何表示的问题。一个如何表示的问题。例三、煤气管道的铺设问题。如图需为城市的各例三、煤气管道的铺设问题。如图需为城市的各小区之间铺设煤气管道，对小区之间铺设煤气管道，对 n n 个小区只需铺设个小区只需铺设 n-1 n-1 条管线，由于地理环境不同等因素使各条管线所需投条管线，由于地理环境不同等因素使各条管线所需投资不同资不同(如图上所标识如图上所标识)，如何使投资成本最低？这是，如何使投资成本最低？

5、这是一个讨论图的生成树的问题。一个讨论图的生成树的问题。3/6/20235首首 页页 上一页上一页 下一页下一页 返返 回回 退退 出出A AB BH HI IGGC CE ED DF F181812129 979795252565631311010858598986767212145458 83434（a a）城市距离图）城市距离图A AB BH HI IGGC CE ED DF F12129 979793131101021218 83434（b b）联通各城市最小生成树）联通各城市最小生成树3/6/20236首首 页页 上一页上一页 下一页下一页 返返 回回 退退 出出以上所举例子中的数学

6、模型正是数据结构要讨论以上所举例子中的数学模型正是数据结构要讨论的问题。因此，简单地说，的问题。因此，简单地说，数据结构数据结构是一门讨论是一门讨论 描述描述现实世界实体的数学模型现实世界实体的数学模型(非数值计算非数值计算)及其上的操作及其上的操作在计算机中如何表示和实现在计算机中如何表示和实现 的学科。的学科。3/6/20237首首 页页 上一页上一页 下一页下一页 返返 回回 退退 出出n n而信息的表示和组织又直接关系到处理信息的而信息的表示和组织又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应

7、用加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为程序的规模很大，结构又相当复杂。因此，为了编写出一个了编写出一个“好好”的程序，必须分析待处理的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。是数据结构这门课所要研究的问题。n n 计算机是一门研究用计算机进行信息表示和处计算机是一门研究用计算机进行信息表示和处 理的科学。这里面涉及到两个问题：理的科学。这里面涉及到两个问题：信息的表示信息的表示 信息的处理信息的处理综上所述综上所述3/6/20238首首 页页 上一页上一页 下

8、一页下一页 返返 回回 退退 出出1.1数据结构数据结构 1.1.1数据结构 随着计算机软、硬件的发展，计算机的应用范随着计算机软、硬件的发展，计算机的应用范围在不断扩大，计算机所处理的数据的数量也在不围在不断扩大，计算机所处理的数据的数量也在不断扩大，计算机所处理的数据已不再是单纯的数值断扩大，计算机所处理的数据已不再是单纯的数值数据，而更多的是非数值数据。数据，而更多的是非数值数据。需要处理的数据并不是杂乱无章的，它们一定需要处理的数据并不是杂乱无章的，它们一定有内在的联系，只有弄清楚它们之间的本质的联系，有内在的联系，只有弄清楚它们之间的本质的联系，才能使用计算机对大量的数据进行有效的处

9、理。才能使用计算机对大量的数据进行有效的处理。3/6/20239首首 页页 上一页上一页 下一页下一页 返返 回回 退退 出出 例例4 4 某电信公司的市话用户信息表格如下图所示：某电信公司的市话用户信息表格如下图所示：序号用户名电话号码用户住址街道名门牌号00001万方林3800235北京西路165900002吴金平3800667北京西路209900003王 冬5700123瑶湖大道198700004王 三5700567瑶湖大道200800005江 凡8800129学府大道50353/6/202310首首 页页 上一页上一页 下一页下一页 返返 回回 退退 出出 这里序号、用户名、电话号码等

10、项称为基本项，它这里序号、用户名、电话号码等项称为基本项，它是有独立意义的最小标识单位，而用户住址称为组合项，是有独立意义的最小标识单位，而用户住址称为组合项，组合项是由一个或多个基本项或组合项组成，是有独立组合项是由一个或多个基本项或组合项组成，是有独立意义的标识单位，每一行称为一个结点，每一个组合项意义的标识单位，每一行称为一个结点，每一个组合项称为一个字段。称为一个字段。使用计算机处理用户信息表中的数据时，必须弄清楚使用计算机处理用户信息表中的数据时，必须弄清楚下面下面3 3个问题：个问题：3/6/202311首首 页页 上一页上一页 下一页下一页 返返 回回 退退 出出1 数据的逻辑结

11、构 这些数据之间有什么样的内在联系？这些数据之间有什么样的内在联系？除除最最前前和和最最后后两两个个结结点点之之外外，表表中中所所有有其其它它的的结结点点都都有有且且仅仅有有一一个个和和它它相相邻邻位位于于它它之之前前的的一一个个结结点点，也也有有且且仅仅有有一一个个和和它它相相邻邻位位于于它它之之后后的的一一个个结结点点，这这些些就就是是用户信息表的逻辑结构。用户信息表的逻辑结构。2 数据的存储结构 将将用用户户信信息息表表中中的的所所有有结结点点存存入入计计算算机机时时，就就必必须须考考虑虑存存储储结结构构，使使用用C C语语言言进进行行设设计计时时，常常见见的的方方式式是是用用一一个个结

12、结构构数数组组来来存存储储整整个个用用户户信信息息表表，每每一一个个数数组组元元素素是是一一个个结结构构，它它对对应应于于用用户户信信息息表表中中的的一一个个结结点点。数数据在计算机的存储方式称为存储结构。据在计算机的存储方式称为存储结构。3/6/202312首首 页页 上一页上一页 下一页下一页 返返 回回 退退 出出3 数据的运算集合 数据处理必涉及到相关的运算，在上述用户信息表数据处理必涉及到相关的运算，在上述用户信息表中，可以有删除一个用户、增加一个用户和查找某个用中，可以有删除一个用户、增加一个用户和查找某个用户等操作。应该明确指明这些操作的含义。比如删除操户等操作。应该明确指明这些

13、操作的含义。比如删除操作，是删除序号为作，是删除序号为5 5的用户还是删除用户名为王三的用的用户还是删除用户名为王三的用户是应该明确定义的，如果需要可以定义两个不同的删户是应该明确定义的，如果需要可以定义两个不同的删除操作，为一批数据定义的所有运算（或称操作）构成除操作，为一批数据定义的所有运算（或称操作）构成一个运算（操作）集合。一个运算（操作）集合。对待处理的数据，只有分析清楚上面对待处理的数据，只有分析清楚上面3 3个方面的问个方面的问题，才能进行有效的处理！题，才能进行有效的处理！数数数数据据据据结结结结构构构构就就是是指指按按一一定定的的逻逻辑辑结结构构组组成成的的一一批批数数据据，

14、使使用用某某种种存存储储结结构构将将这这批批数数据据存存储储于于计计算算机机中中，并并在在这些数据上定义了一个运算集合。这些数据上定义了一个运算集合。基于这个二维表格，我们可以在上面执行的操基于这个二维表格，我们可以在上面执行的操 作有：增加一个元素，删除元素，查找元素等。作有：增加一个元素，删除元素，查找元素等。存在的问题：线性查找的效率较低（等概率情存在的问题：线性查找的效率较低（等概率情况下为况下为n/2n/2）。数组存储时插入一个元素与删除一）。数组存储时插入一个元素与删除一个元素效率较低。个元素效率较低。解决办法：改变数据存储结构，在新的存储结解决办法：改变数据存储结构，在新的存储结

15、构上开发新的算法。构上开发新的算法。找找9595找找3535例5、旅游交通网络图实际问题：实际问题：如何选择任意两个城市之间的最短路径？如何选择任意两个城市之间的最短路径？建立通信网络时，如何在建立通信网络时，如何在n n个城市之间找到个城市之间找到n-1n-1连连线，使得这线，使得这n-1n-1条连线的和最小。（即花费最小的条连线的和最小。（即花费最小的代价连通各个城市）代价连通各个城市）解决办法解决办法：将城市与城市之间的距离等数据在计算机中采用将城市与城市之间的距离等数据在计算机中采用图型结构图型结构组织（点与点之间存在多对多的关系）。组织（点与点之间存在多对多的关系）。上述问题便可转化

16、为图中两点之间的最短距离和上述问题便可转化为图中两点之间的最短距离和图的最小生成树问题。图的最小生成树问题。3/6/202315首首 页页 上一页上一页 下一页下一页 返返 回回 退退 出出1.1.2数据的逻辑结构数据的逻辑结构 数数据据的的逻逻辑辑结结构构是是数数据据和和数数据据之之间间所所存存在在的的逻逻辑辑关关系，它可以用一个二元组系，它可以用一个二元组B=B=（K K，R R）来表示，其中来表示，其中K K是数据、即结点的有限集合；是数据、即结点的有限集合；R R是集是集合合K K上关系的有限集合，这里的关系是从集合上关系的有限集合，这里的关系是从集合K K到集到集合合K K的关系，这

17、里一般只涉及到一个关系的逻辑结构。的关系，这里一般只涉及到一个关系的逻辑结构。3/6/202316首首 页页 上一页上一页 下一页下一页 返返 回回 退退 出出1.1.2数据的逻辑结构数据的逻辑结构 例例如如，有有5 5个个人人，分分别别记记为为a,b,c,d a,b,c,d,e,e,其其中中a a是是b b的的父父亲亲，b b是是c c的的父父亲亲，c c是是d d的的父父亲亲,d,d是是e e的的父父亲亲，如如果果只只讨讨论论他他们们之之间间所所存存在在的的父父子子关关系系，则则可可以以用用下下面面的的二二元元组组形形式式化地予以表达。化地予以表达。B=B=（K K，R R）其中：其中：K

18、=a,b,c,d,eK=a,b,c,d,e R=r R=r r=,r=,逻逻辑辑结结构构的的图图形形表表示示方方式式，对对K K中中的的每每个个结结点点k ki i用用一一个个方方框框表表示示，而而结结点点之之间间的的关关系系用用带带箭箭头头的的线线段段表表示示，这这5 5人之间的逻辑结构用图形的方式表达如下图人之间的逻辑结构用图形的方式表达如下图 所示。所示。若若k ki iK K，k kj jR R，k r r，则称，则称k ki i是是k kj j的相对的相对于关系于关系r r的的前驱结点前驱结点，k kj j是是k ki i的相对于关系的相对于关系r r的的后继结点后继结点，因为一般只

19、讨论具有一种关系的逻辑结构，即因为一般只讨论具有一种关系的逻辑结构，即R=rR=r，所以简称所以简称k ki i是是k kj j前驱，前驱，k kj j是是k ki i的后继。如果某个结点没有的后继。如果某个结点没有前驱结点，称之为前驱结点，称之为开始结点开始结点；如果某个结点没有后继；如果某个结点没有后继结点，称之为结点，称之为终端结点终端结点；既不是开始结点也不是终端；既不是开始结点也不是终端结点的结点称为结点的结点称为内部结点内部结点。abcde线性逻辑结构线性逻辑结构二、二、树型结构树型结构 结构中的数据元素之间存在一结构中的数据元素之间存在一对多的关系。对多的关系。125643三、三

20、、图状结构或网状结构图状结构或网状结构 结构中的数据元素之结构中的数据元素之间存在多对多的关系。间存在多对多的关系。12345671.1.3数据的存储结构数据的存储结构 数数据据的的逻逻辑辑结结构构是是独独立立于于计计算算机机的的，它它与与数数据据在在计计算算机机中中的的存存储储无无关关，要要对对数数据据进进行行处处理理，就就必必须须将将数数据据存存储储在在计计算算机机中中。如如果果将将数数据据在在计计算算机机中中无无规规律律地地存存储储，那那么么在在处处理理时时是是非非常常糟糟的的，是是没没有有用用的的。试试想想一一下下，如如果果一一本本英英汉汉字字典典中中的的单单词词是是随随意意编编排排的

21、的，这本字典谁会用！这本字典谁会用！对对于于一一个个数数据据结结构构B=B=（K K，R R），必必须须建建立立从从结结点点集集合合到到计计算算机机某某个个存存储储区区域域MM的的一一个个映映象象，这这个个映映象象要要直直接接或或间间接接地地表表达达结结点点之之间间的的关关系系R R。数数据据在在计计算算机中的存储方式称为数据的存储结构。机中的存储方式称为数据的存储结构。数据的存储结构主要有数据的存储结构主要有4 4种。种。数据的存储结构主要有数据的存储结构主要有4 4种。种。1 1 顺序存储顺序存储 顺序存储通常用于存储具有线性结构的数据。将顺序存储通常用于存储具有线性结构的数据。将逻辑上相

22、邻的结点存储在连续存储区域逻辑上相邻的结点存储在连续存储区域MM的相邻的存的相邻的存储单元中，使得逻辑相邻的结点一定是物理位置相邻。储单元中，使得逻辑相邻的结点一定是物理位置相邻。对于一个数据结构对于一个数据结构B=B=（K K，R R）其中其中K=kK=k1 1,k,k2 2,k,k3 3,k,k4 4,k,k5 5,k,k6 6,k,k7 7,k,k8 8,k,k9 9 R=r R=r r=kr=,它的顺序存储方式如图所示它的顺序存储方式如图所示 k1k2k3k6k5k4k7k8k9存储地址 M100110021003100410051006100710081009特点：用物理相特点：用物

23、理相邻的位置关系表邻的位置关系表示其逻辑关系示其逻辑关系2 2 链式存储链式存储 链式存储方式是给每个结点附加一个指针段，一链式存储方式是给每个结点附加一个指针段，一个结点的指针所指的是该结点的后继的存储地址，因个结点的指针所指的是该结点的后继的存储地址，因为一个结点可能有多个后继，所以指针段可以是一个为一个结点可能有多个后继，所以指针段可以是一个指针，也可以是一个多个指针。指针，也可以是一个多个指针。例，数据的逻辑结构例，数据的逻辑结构B=B=（K K，R R）其中其中 K=k K=k1 1,k,k2 2,k,k3 3,k,k4 4,k,k5 5 R=r R=r r=k r=,这是一个线性结

24、构，它的链式存储如图所示。这是一个线性结构，它的链式存储如图所示。100010011002100310041005100610071008存储地址 info nextk41006k21007k11003k5k31005特点特点:逻辑上相邻逻辑上相邻物理上不一定相物理上不一定相邻。邻。3 3 索引存储索引存储 在线性结构中，设开始结点的索引号为在线性结构中，设开始结点的索引号为1 1，其它结，其它结点的索引号等于其前继结点的索引号加点的索引号等于其前继结点的索引号加1 1，则每一个结，则每一个结点都有唯一的索引号，索引号就是根据结点的索引号点都有唯一的索引号，索引号就是根据结点的索引号确定该结点

25、的存储地址。确定该结点的存储地址。4 4 散列存储散列存储 散列存储的思想是构造一个从集合散列存储的思想是构造一个从集合K K到存储区域到存储区域MM的一个函数的一个函数h h，该函数的定义域为，该函数的定义域为K K，值域为，值域为MM，K K中的中的每个结点每个结点k ki i在计算机中的存储地址由在计算机中的存储地址由h(kh(ki i)确定。确定。1.1.4数据的运算集合数据的运算集合 对于一批数据，数据的运算是定义在数据的逻对于一批数据，数据的运算是定义在数据的逻辑结构之上的，而运算的具体实现就依赖于数据的存辑结构之上的，而运算的具体实现就依赖于数据的存储结构。储结构。数数据据的的运

26、运算算集集合合要要视视情情况况而而定定，一一般般而而言言，数数据据的运算包括插入、删除、检索、输出、排序等。的运算包括插入、删除、检索、输出、排序等。插入：在一个结构中增加一个新的结点。插入：在一个结构中增加一个新的结点。删除：在一个结构删除一个结点。删除：在一个结构删除一个结点。检索：在一个结构中查找满足条件的结点。检索：在一个结构中查找满足条件的结点。输出：将一个结构中所有结点的值打印、输出。输出：将一个结构中所有结点的值打印、输出。排序：将一个结构中所有结点按某种顺序重新排列。排序：将一个结构中所有结点按某种顺序重新排列。在程序设计中，数据和运算是两个不可缺少的因在程序设计中，数据和运算

27、是两个不可缺少的因素。所有的程序设计活动都是围绕着数据和其上的相素。所有的程序设计活动都是围绕着数据和其上的相关运算而进行的。从机器指令、汇编语言中的数据没关运算而进行的。从机器指令、汇编语言中的数据没有类型的概念，到现在的面向对象程序设计语言中抽有类型的概念，到现在的面向对象程序设计语言中抽象数据类型概念的出现，程序设计中的数据经历了一象数据类型概念的出现，程序设计中的数据经历了一次次抽象，数据的抽象经历了三个发展阶段。次次抽象，数据的抽象经历了三个发展阶段。1.2数据类型和抽象数据类型数据类型和抽象数据类型从无类型的二进制数到基本数据类型的产生从无类型的二进制数到基本数据类型的产生 从基本

28、数据类型到用户自定义类型的产生从基本数据类型到用户自定义类型的产生 从用户自定义类型到抽象数据类型的出现从用户自定义类型到抽象数据类型的出现 1.2.1数据类型数据类型 数据类型（或简称类型）反映了数据的取值范围以数据类型（或简称类型）反映了数据的取值范围以及对这类数据可以施加的运算。及对这类数据可以施加的运算。1.2.2数据结构数据结构 数数据据结结构构是是计计算算机机科科学学中中广广泛泛使使用用的的一一个个术术语语，在在计计算算机机科科学学中中具具有有非非常常重重要要的的作作用用。数数据据结结构构包包括括三三个个方方面面的的内内容容：一一组组数数据据中中各各数数据据之之间间的的逻逻辑辑关关

29、系系；这这组组数数据据在在计计算算机机中中的的存存储储方方式式；对对这这组组数数据据所所能能施施加加的的运运算算的的集集合合。数数据据结结构构是是数数据据存存在在的的形形式式。所所有有的的数数据据都都是是按按照照数数据据结结构构进进行行分分类类的的。简简单单数数据据类类型型对对应应于于简简单单的数据结构；构造数据类型对应于复杂的数据结构。的数据结构；构造数据类型对应于复杂的数据结构。1.2.3抽象数据类型抽象数据类型 抽象数据类型是与表示无关的数据类型，是一个数抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。对一个抽象数据据模型及定义在该模型上的一组运算。对一个抽

30、象数据类型进行定义时，必须给出它的名字及各运算的运算符类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。名，即函数名，并且规定这些函数的参数性质。1.2.4抽象数据类型的描述和实现抽象数据类型的描述和实现 抽象数据类型的描述包括给出抽象数据类型的名称、抽象数据类型的描述包括给出抽象数据类型的名称、数据的集合、数据之间的关系和操作的集合等方面的描数据的集合、数据之间的关系和操作的集合等方面的描述。抽象数据类型的设计者根据这些描述给出操作的具述。抽象数据类型的设计者根据这些描述给出操作的具体实现，抽象数据类型的使用者依据这些描述使用抽象体实现，抽象数据类型的

31、使用者依据这些描述使用抽象数据类型。数据类型。抽象数据类型描述的一般形式如下：抽象数据类型描述的一般形式如下：ADT ADT 抽象数据类型名称抽象数据类型名称 数据对象：数据对象：数据关系：数据关系：操作集合：操作集合：操作名操作名1 1：操作名操作名n n：ADTADT抽象数据类型名称抽象数据类型名称 1.3 1.3 算法和算法分析算法和算法分析 1.3.1算法算法 为为了了求求解解某某问问题题，必必须须给给出出一一系系列列的的运运算算规规则则，这这一一系系列列的的运运算算规规则则是是有有限限的的，表表达达了了求求解解问问题题方方法和步骤，这就是一个算法。法和步骤，这就是一个算法。一一个个算

32、算法法可可以以用用自自然然语语言言描描述述，也也可可以以用用高高级级程程序序设设计计语语言言描描述述，也也可可以以用用伪伪代代码码描描述述。本本书书采采用用C C语言对算法进行描述。语言对算法进行描述。算法具有五个基本特征：算法具有五个基本特征：有穷性，算法的执行必须在有限步内结束。有穷性，算法的执行必须在有限步内结束。确定性，算法的每一步骤必须是确定无二义性的。确定性，算法的每一步骤必须是确定无二义性的。输入，输入，算法可以有算法可以有0 0个或多个输入。个或多个输入。输出，输出，算法一定有输出结果算法一定有输出结果可行性，算法中的运算都必须是可以实现的。可行性，算法中的运算都必须是可以实现

33、的。算法具有有穷性，程序不需要具备有穷性。一般算法具有有穷性，程序不需要具备有穷性。一般的程序都会在有限时间内终止，但有的程序却可以不的程序都会在有限时间内终止，但有的程序却可以不在有限时间内终止，如一个操作系统在正常情况下是在有限时间内终止，如一个操作系统在正常情况下是永远都不会终止的。永远都不会终止的。1.3.2算法的时间和空间复杂性算法的时间和空间复杂性 一个算法的优劣主要从算法的执行时间和所需一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量，算法执行时间的度要占用的存储空间两个方面衡量，算法执行时间的度量不是采用算法执行的绝对时间来计算的，因为一个量不是采用算法执行

34、的绝对时间来计算的，因为一个算法在不同的机器上执行所花的时间不一样，在不同算法在不同的机器上执行所花的时间不一样，在不同时刻也会由于计算机资源占用情况的不同，使得算法时刻也会由于计算机资源占用情况的不同，使得算法在同一台计算机上执行的时间也不一样，所以对于算在同一台计算机上执行的时间也不一样，所以对于算法的时间复杂性，采用算法执行过程中其基本操作的法的时间复杂性，采用算法执行过程中其基本操作的执行次数，称为计算量来度量。执行次数，称为计算量来度量。算法中基本操作的执行次数一般是与问题规模算法中基本操作的执行次数一般是与问题规模有关的，对于结点个数为有关的，对于结点个数为n n的数据处理问题，用

35、的数据处理问题，用T(n)T(n)表示算法基本操作的执行次数。表示算法基本操作的执行次数。评价一个算法的一般作法：评价一个算法的一般作法：（1 1）合理地选择一个或几个操作作为）合理地选择一个或几个操作作为“标准操作标准操作”。（2 2）计算量）计算量=给定输入下执行标准操作的次数。给定输入下执行标准操作的次数。事实：一个算法的计算量通常依赖于问题的规模。事实：一个算法的计算量通常依赖于问题的规模。为了便于讨论，我们把问题规模假定为为了便于讨论，我们把问题规模假定为n n，则，则算法在问题规模（算法在问题规模（SizeSize）为）为n n的输入下的计算量为的输入下的计算量为T T（n n）。

36、）。定义定义：设：设f f（n n）与）与g g（n n）是定义在正整数集合上的）是定义在正整数集合上的两个函数，如果存在两个正常数两个函数，如果存在两个正常数c c和和n n0 0，对于所有的，对于所有的n nn n0 0，有，有f(n)f(n)c.g(n)c.g(n)则记作则记作 f(n)=O(g(n)f(n)=O(g(n)。也就是说对几乎所有的也就是说对几乎所有的n n值，函数值，函数f f（n n）以函数）以函数g g（n n）为上界。）为上界。渐近记号（一）渐近记号（一）f(n)=O(g(n)表明，当 n 时，f(n)趋于无穷大的阶不大于(即小于等于)g(n)趋于无穷大的阶.例例1

37、1：证明证明n n2 2/2+3/2+3为为OO（n n2 2）证明：要证明：要使使n n2 2/2+3c*n/2+3+3/nc+3/n2 2 当当n 6n 6时，必有时，必有1/2+3/n1/2+3/n2 21 1 故取故取c=1c=1，n n0 0=3=3，则对任意，则对任意n3n3，有，有 n n2 2/2+3/2+3c*nc*n2 2 故故n n2 2/2+3/2+3为为OO（n n2 2）渐近记号（二）渐近记号（二）大 记号：定义定义定义定义:f f(n n)=)=(g g(n n)意味着存在正常数意味着存在正常数 C C 和和 n n0 0,使得使得 当当 n n n n0 0,均

38、有均有 0 0 C C g g(n n)f f(n n)成立。成立。f f(n n)=)=(g g(n n)表明，当表明，当 n n 时，时，f f(n n)趋于无穷大趋于无穷大的阶不小于的阶不小于 g g(n n)趋于无穷大的阶趋于无穷大的阶.渐近记号（三）渐近记号（三）大 记号：定义定义定义定义:f f(n n)=)=(g g(n n)意味着存在正常数意味着存在正常数C C1 1,C C2 2和和n n0 0使使 得当得当n nn n0 0,均有均有 0 0C C1 1g g(n n)f f(n n)C C2 2g g(n n)成立。成立。f f(n n)=)=(g g(n n)表明，当表

39、明，当 n n 时，时，f f(n n)和和g g(n n)趋于无趋于无穷大的阶是相同的。穷大的阶是相同的。例例2 2：求两个：求两个n n阶方阵的乘积阶方阵的乘积C=AC=A*B B for(i=0;in;+i)for(i=0;in;+i)for(j=0;jn;+j)for(j=0;jn;+j)cij=0;cij=0;for(k=0;kn;+k)for(k=0;kn;+k)cij+=aik*bkj;cij+=aik*bkj;n+1n+1n(n+1)n(n+1)n n2 2n n2 2(n+1)(n+1)n n3 3 一般情况下，算法中基本操作重复执行的次一般情况下，算法中基本操作重复执行的次

40、数是问题规模数是问题规模n n的某个函数，当的某个函数，当n n趋向无穷大时，趋向无穷大时，我们把时间复杂度我们把时间复杂度T T（n n）=O=O（f f（n n）的数量级）的数量级（阶）称为算法的（阶）称为算法的渐近时间复杂度。渐近时间复杂度。上述上述n n阶矩阵相乘算法的时间复杂度阶矩阵相乘算法的时间复杂度T T（）为算（）为算法中所有语句的频度之和：法中所有语句的频度之和：T T（n n）=2n=2n3 3+3n+3n2 2+2n+1+2n+1按照按照O O记法，当记法，当n n趋向无穷大时有：趋向无穷大时有：limTlimT（n n）/n/n3 3=lim=lim（2n2n3 3+3

41、n+3n2 2+2n+1+2n+1）/n/n3 3=2=2这表明，当这表明，当n n充分大时，充分大时，T T（n n）和）和n n3 3之比是一个不之比是一个不等于等于0 0的常数，即的常数，即T T（n n）和）和n n3 3是同阶的，所以是同阶的，所以:T T（n n）=O=O（n n3 3 ）l l频度频度：是指该语句重复执行的次数。是指该语句重复执行的次数。n n n n 例例3 3：+x +x；s=0s=0；将将x x自增看成是基本操作，则语句频度为，自增看成是基本操作，则语句频度为，即时间复杂度为即时间复杂度为(1)(1)如果将如果将s=0s=0也看成是基本操作，则语句频度也看成

42、是基本操作，则语句频度为，其时间复杂度仍为为，其时间复杂度仍为(1)(1)，即常量阶。，即常量阶。例例4 4：for for（i=1i=1；i=ni=n；+i+i）+x +x；s+=xs+=x；语句频度为：语句频度为：2n2n其时间复杂度为：其时间复杂度为：O O（n n）即时间复杂度为线性阶。即时间复杂度为线性阶。例例5 5：forfor（i=1i=1；i=ni=n；+i+i）forfor（j=1j=1；j=nj=n；+j+j）+x +x；s+=xs+=x；语句频度为：语句频度为：2n2n2 2其时间复杂度为：其时间复杂度为：O(nO(n2 2)即时间复杂度为平方阶。即时间复杂度为平方阶。定

43、理：若定理：若A(n)=a A(n)=a m m n n m m+a+a m-1m-1 n n m-1m-1+a+a1 1n+an+a0 0是一是一个个mm次多项式，则次多项式，则A(n)=O(nA(n)=O(n m m)证略。证略。例例6 for6 for（i=2i=2；i=ni=n；+i+i）for for（j=2j=2；j=i-1j=i-1；+j+j）+x +x；aij=x;aij=x;语句频度为：语句频度为：1+2+3+n-2=(1+n-2)(n-2)/2 1+2+3+n-2=(1+n-2)(n-2)/2 =(n-1)(n-2)/2 =(n-1)(n-2)/2 =n =n2 2-3n+

44、2-3n+2 时间复杂度为时间复杂度为O(nO(n2 2)即此算法的时间复杂度为平方阶即此算法的时间复杂度为平方阶.一个算法时间为一个算法时间为O(1)O(1)的算法，它的基本运算执行的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为（即零次多项式）来限界。而一个时间为O(nO(n2 2)的的算法则由一个二次多项式来限界。算法则由一个二次多项式来限界。以下六种计算算法时间的多项式是最常用的。以下六种计算算法时间的多项式是最常用的。其关系为：其关系为：O(1)O(logn)O(n)O(nlogn)O(n O

45、(1)O(logn)O(n)O(nlogn)O(n2 2)O(n)O(n3 3)指数时间的关系为：指数时间的关系为：O(2 O(2n n)O(n!)O(n)O(n!)1&change;-i)for(i=n-1,change=1;i1&change;-i)change=0;change=0;for(j=0;ji;+j)for(j=0;jaj+1)if(ajaj+1)aj aj+1;aj aj+1;change=1;change=1;最好情况：最好情况：0 0次次 （原有数据有序时）（原有数据有序时）最坏情况：最坏情况：1+2+3+n-1=n(n-1)/21+2+3+n-1=n(n-1)/2 平均

46、时间复杂度为平均时间复杂度为:O(n:O(n2 2)算法的时间复杂性不仅和问题的规模大小有关，算法的时间复杂性不仅和问题的规模大小有关，还与问题数据的初始状态有关。还与问题数据的初始状态有关。这这样样就就有有了了算算法法在在最最好好、最最坏坏以以及及在在平平均均状状态态下下的时间复杂性的概念。的时间复杂性的概念。算算法法在在最最好好情情况况下下的的时时间间复复杂杂性性是是指指算算法法计计算算量量的的最小值。最小值。算算法法在在最最坏坏情情况况下下的的时时间间复复杂杂性性是是指指算算法法计计算算量量的的最大值。最大值。算法的平均情况下的时间复杂性是指算法在所有可算法的平均情况下的时间复杂性是指算

47、法在所有可能的情况下的计算量经过加权计算出的平均值。能的情况下的计算量经过加权计算出的平均值。算法的存储空间需求算法的存储空间需求空间复杂度空间复杂度:算法所需存储空间的度量，记作算法所需存储空间的度量，记作:S(n)=O(f(n)S(n)=O(f(n)其中其中n n为问题的规模为问题的规模(或大小或大小)空间复杂度空间复杂度Space complexity(Space complexity(空间复杂度空间复杂度空间复杂度空间复杂度):):The amount of computer memory a program needs The amount of computer memory a

48、program needs to run to completion.to run to completion.Why to be interested in it?Why to be interested in it?pp To specify the amount of memory to be To specify the amount of memory to be allocated to a program.allocated to a program.pp To know in advance whether or not sufficient To know in advanc

49、e whether or not sufficient memory is available to run a program.memory is available to run a program.pp To be useful to choose a suitable solution to To be useful to choose a suitable solution to a question.a question.pp To estimate the size of the largest problem To estimate the size of the larges

50、t problem that a program can solvethat a program can solve习题习题1：1.1 什么是数据结构？什么是数据结构？1.2 数据结构涉及哪几个方面？数据结构涉及哪几个方面？1.3 两个数据结构的逻辑结构和存储结构都相同，但两个数据结构的逻辑结构和存储结构都相同，但是它们的运算集合中有一个运算的定义不一样，它是它们的运算集合中有一个运算的定义不一样，它们是否可以认作是同一个数据结构？为什么？们是否可以认作是同一个数据结构？为什么？1.4 线性结构的特点是什么？非线性结构的特点是什线性结构的特点是什么？非线性结构的特点是什么？么？1.5 数据结构