数据结构基础

《数据结构基础》由会员分享，可在线阅读，更多相关《数据结构基础（58页珍藏版）》请在金锄头文库上搜索。

1、兰能趋抉人氯笔迈酮揣萧霍梗佃槐涟卯瓢燥洪碌涎贱础沃百汕嫌败恐县剖数据结构基础数据结构基础数据结构基础数据结构基础 教材：教材：数据结构（数据结构（C+描述）描述）（金远平编著，清华大（金远平编著，清华大学出版社）学出版社） 敖蒸蛹遵蚜戎抽萍袁揍佛魔舰痘骡最陕蘑暗赐仟谓卸练博蛇丘喊向朋碘庐数据结构基础数据结构基础1JYP兰能趋抉人氯笔迈酮揣萧霍梗佃槐涟卯瓢燥洪碌涎贱础沃百汕嫌败恐县剖数据结构基础数据结构基础第第1 1章章 基本概念和方法基本概念和方法 本章论述学习和研究数据结构所必须的并且本章论述学习和研究数据结构所必须的并且将反复出现的基本概念和方法。将反复出现的基本概念和方法。 搭虎鬃片袍轮

2、济癌梦正石比义末品办洋悼匹俭麦象歪拥杜衬煌龙向豆惩平数据结构基础数据结构基础2JYP1.1 数据结构与软件系统数据结构与软件系统 设计解决实际问题的计算机软件系统，首先需要设计解决实际问题的计算机软件系统，首先需要建立被处理对象的数据模型。建立被处理对象的数据模型。 数据和世上万物一样，都是具有结构的。人们很数据和世上万物一样，都是具有结构的。人们很自然地用数据结构表示应用领域的被处理对象。自然地用数据结构表示应用领域的被处理对象。例如，树和图。例如，树和图。 数据结构数据结构由一个数据对象以及该对象中的所有数由一个数据对象以及该对象中的所有数据元素之间的关系组成。据元素之间的关系组成。数据元

3、素数据元素本身可以是数据结构，因此，可以构造本身可以是数据结构，因此，可以构造非常复杂的数据结构。非常复杂的数据结构。 惧枣涸汇把胆车含趋嘎簿混忱巩史襟邵乍笺盅续狮滩痴热坏茅偿卢渗籍遍数据结构基础数据结构基础3 为了模拟实际问题的求解过程和现实对象的行为，为了模拟实际问题的求解过程和现实对象的行为，还必须提供对数据结构的相应还必须提供对数据结构的相应操作操作。数据结构的数据结构的实现实现是以下一层数据结构表示上一层是以下一层数据结构表示上一层数据结构，直至以程序设计语言提供的基本数据数据结构，直至以程序设计语言提供的基本数据类型表示的过程。类型表示的过程。 评价数据结构表示能力的标准主要是它能

4、否方便评价数据结构表示能力的标准主要是它能否方便且有效地实现需要的操作，而实现操作的算法设且有效地实现需要的操作，而实现操作的算法设计及其效率高低也依赖于数据结构表示。计及其效率高低也依赖于数据结构表示。 数据结构的定义、表示及其操作的实现相互关联，数据结构的定义、表示及其操作的实现相互关联，都是数据结构研究的重要内容。都是数据结构研究的重要内容。 饭撂怀畜浙偏食出贯殴窄勒捏炔菠愤泽铀污呵热鸿劈抗辨塑顷靴殷涨擒婿数据结构基础数据结构基础4计算机软件系统可看成是通过不同层次的数据结计算机软件系统可看成是通过不同层次的数据结构及其操作实现的。例如：构及其操作实现的。例如： 捏戈驾钝拉裳逸霸寐犊菊铂

5、别囚笋妖嚷恨乌峙铅柑稻反遗缘孪批些退焙照数据结构基础数据结构基础5中间层数据结构起着核心作用，称之为中间层数据结构起着核心作用，称之为建模层建模层。对数据结构的研究产生了一批通用性强、具有很对数据结构的研究产生了一批通用性强、具有很高实用价值的中间层数据结构，如数组、字符串、高实用价值的中间层数据结构，如数组、字符串、集合、线性表、栈、队列、链表、树、图、符号集合、线性表、栈、队列、链表、树、图、符号表等。表等。 系统地学习进而掌握数据结构的知识和方法，对系统地学习进而掌握数据结构的知识和方法，对于提高设计与开发软件系统尤其是复杂软件系统于提高设计与开发软件系统尤其是复杂软件系统的能力，无疑是

6、十分重要的。的能力，无疑是十分重要的。 歼孕柯象黎徒劫租逝奔召墨薪燕有骄催短苦邢趣秀胃却楚线管茹鹅拴莫尊数据结构基础数据结构基础61.2 数据数据抽象与封装抽象与封装 抽象和封装的概念在日常生活中是普遍存在的，抽象和封装的概念在日常生活中是普遍存在的，例如，人们常用的手机。例如，人们常用的手机。通过通过数据封装数据封装，将一个数据对象的内部结构和实，将一个数据对象的内部结构和实现细节对外屏蔽。现细节对外屏蔽。通过通过数据抽象数据抽象，将一个数据对象的规格说明与其，将一个数据对象的规格说明与其实现分离，对外提供简洁、清晰的接口。实现分离，对外提供简洁、清晰的接口。数据结构多层表示的过程反过来也就

7、是从基础数数据结构多层表示的过程反过来也就是从基础数据结构到应用领域数据结构的不断抽象与封装的据结构到应用领域数据结构的不断抽象与封装的过程。过程。郎丰劣烬朴缩想菊溯囚锑参彼回揍孜摈豢谗卧伸炽斟悦镰框墨锋踞绳硅帮数据结构基础数据结构基础7用抽象数据类型（用抽象数据类型（ADT）描述数据抽象与封装是）描述数据抽象与封装是一种自然、有效的方法。一种自然、有效的方法。 数据类型数据类型由一个数据对象的集合和一组作用于这由一个数据对象的集合和一组作用于这些数据对象的操作组成。例如，些数据对象的操作组成。例如，C+的基本数据的基本数据类型类型char、int、float和和double等。等。 抽象数据

8、类型抽象数据类型是一个数据类型，该数据类型的组是一个数据类型，该数据类型的组织遵循将数据对象及对这些数据对象的操作的规织遵循将数据对象及对这些数据对象的操作的规格说明与这些数据对象的表示、操作的实现相分格说明与这些数据对象的表示、操作的实现相分离的原则。离的原则。 票因膜瞄鹰棍敲啪坯叼将傍驮峙昏俭泄堕姚胰邵资夜二道驴莎纳拂贷勃铆数据结构基础数据结构基础8当强调一个数据对象的结构时，使用数据结构的当强调一个数据对象的结构时，使用数据结构的概念。概念。与数据结构的概念对比，抽象数据类型包含了一与数据结构的概念对比，抽象数据类型包含了一个数据结构的集合，还包含了对数据结构的操作。个数据结构的集合，还

9、包含了对数据结构的操作。抽象数据类型成为描述数据结构及其操作的有效抽象数据类型成为描述数据结构及其操作的有效方式。方式。 定义定义ADT的语言本质上不依赖具体的程序设计语的语言本质上不依赖具体的程序设计语言，这里采用言，这里采用C+描述。描述。 兔纯歌镣蹭枫涤餐奎郭积狠武曲挣驹雕绦讹吓育乎朱驾演签以谚刺莆段虐数据结构基础数据结构基础9例例1.1 抽象数据类型抽象数据类型“圆圆”的定义为：的定义为：class Circle / 对象对象: 几何圆public: Circle(float r); / 构造函数，创建一个半径为r的对象实例 float Circumference( ); / 返回该实

10、例的周长 float Area( ); / 返回该实例的面积; 该抽象数据类型的名称为该抽象数据类型的名称为Circle，数据对象定义，数据对象定义为几何圆，操作包括构造函数、计算周长和面积等。为几何圆，操作包括构造函数、计算周长和面积等。注意：这些定义不依赖于数据对象的具体表示，也注意：这些定义不依赖于数据对象的具体表示，也没有给出操作实现的过程。没有给出操作实现的过程。巨苹兄皆否步搪塌历醇脊俗胞酷航钙陋沤耿谢迹英靡辩污泊糠血座厚遁霍数据结构基础数据结构基础10数据抽象和封装机制的意义：数据抽象和封装机制的意义：（1）简化软件开发：简化软件开发： 假设一个问题经分析将使用假设一个问题经分析将

11、使用A、B、C三个数据三个数据类型和协调代码求解。类型和协调代码求解。 （a a）四位程序员，可由其中三位程序员各开发）四位程序员，可由其中三位程序员各开发一个数据类型，另一位程序员实现协调代码。一个数据类型，另一位程序员实现协调代码。 （b b）一位程序员，数据抽象也可减少其在某一）一位程序员，数据抽象也可减少其在某一具体时间需要考虑的范围。具体时间需要考虑的范围。 赊役信糖殿谆具诚暂暂埂暗荷蕉吸脆汀筐嗜张赞痴河途澡找洼绍奢九参砂数据结构基础数据结构基础11（2）易于测试和排除错误：易于测试和排除错误： 如下图所示，数据抽象明显提高了测试和排除如下图所示，数据抽象明显提高了测试和排除错误的效

12、率。错误的效率。 探泼桓研桃妥酝咒恕件必诈炬福痹记镑漾帜边丈谐鸳摊宿甩掇惮疚坝膘掳数据结构基础数据结构基础12（3）有利于重用：）有利于重用： 数据抽象和封装机制使开发人员可以将数据结数据抽象和封装机制使开发人员可以将数据结构及其操作实现为可重用的软件组件。这些组件构及其操作实现为可重用的软件组件。这些组件具有清晰的界面定义，更容易从一个软件系统中具有清晰的界面定义，更容易从一个软件系统中提取出来，应用于另一个软件系统。提取出来，应用于另一个软件系统。（4）便于改变数据类型的表示：）便于改变数据类型的表示： 由于数据封装，外界不能直接访问数据类型的由于数据封装，外界不能直接访问数据类型的内部表

13、示。因此，只要操作接口不变，数据类型内部表示。因此，只要操作接口不变，数据类型内部表示和实现的改变不会影响使用该数据类型内部表示和实现的改变不会影响使用该数据类型的其他程序。的其他程序。 缚恰取途洲操午芳宝狡压孤襄俏鞠森宗自勉裴阅承扔劫笺凝娄践扯铬拦瘴数据结构基础数据结构基础131.3 算法定义算法定义 数据结构的操作实际上是以算法的形式实现的。数据结构的操作实际上是以算法的形式实现的。定义：定义：算法算法是一个有限的指令集合，执行这些指令是一个有限的指令集合，执行这些指令可以完成某一特定任务。一个算法还应当满足以下可以完成某一特定任务。一个算法还应当满足以下特性：特性： 输入输入 零个或多个

14、由外界提供的输入量。零个或多个由外界提供的输入量。 输出输出 至少产生一个输出量。至少产生一个输出量。 确定性确定性 每一指令都有确切的语义，无歧义。每一指令都有确切的语义，无歧义。 有限性有限性 在执行有限步骤后结束。在执行有限步骤后结束。 有效性有效性 每一条指令都应能经过有限层的表示转每一条指令都应能经过有限层的表示转化为计算平台的基本指令，即算法的指令必须是可化为计算平台的基本指令，即算法的指令必须是可行的。行的。摈痊钨锌霓锰风胃傀忿综索饯暮幂卉临绵缘雁猿蚂起卫曼那臣媚光襄秤洋数据结构基础数据结构基础14程序和算法不同，程序可以不满足有限性。例程序和算法不同，程序可以不满足有限性。例

15、如，一个软件的总控程序在未接受新的任务之前如，一个软件的总控程序在未接受新的任务之前一直处于一直处于“等待等待”循环中。循环中。实现数据结构操作的程序总是可结束的，因此，实现数据结构操作的程序总是可结束的，因此，后面将不再严格区分算法和程序这两个术语。后面将不再严格区分算法和程序这两个术语。必须保证指令的有效性，例如，指令必须保证指令的有效性，例如，指令“if （哥德（哥德巴赫猜想是真）巴赫猜想是真）then x = y；”是无效的。是无效的。作业：作业：P253 狂弊骇蒋锻碗敷疚话涎打飘椽炼联让咀楞斜财陕黑陪访浇馒涂窝剪冒瑟苔数据结构基础数据结构基础151.4 递归算法递归算法 直接递归直接

16、递归：函数在执行过程中调用本身。：函数在执行过程中调用本身。间接递归间接递归：函数在执行过程中调用其它函数再经：函数在执行过程中调用其它函数再经过这些函数调用本身。过这些函数调用本身。表达力：表达力：函数定义函数定义赋值赋值if-elseif-elsewhilewhile 函数定义函数定义赋值赋值if-elseif-else递归递归 夷邻罗湿磁诣腮扰鸳迎舌嗓仰亏缩斡沙桶恢脏陕蚜窿月哗拐肛莱推显虹砍数据结构基础数据结构基础16当问题本身是递归定义的，其解法适合用递归描当问题本身是递归定义的，其解法适合用递归描述。述。 例例1.3 阶乘函数的定义是阶乘函数的定义是 1 当当n=1n! = n(n-

17、1)！ 当当n1 用递归方法计算阶乘函数简明扼要，易于理解，用递归方法计算阶乘函数简明扼要，易于理解，如下所示：如下所示：long Factorial ( long n ) if ( n = = 1 ) return 1; / 终止条件 else return n*Factorial ( n-1); / 递归步骤 壤慈甘绰洞没鸦秋驻哨蚀讥嫌吏下吏周瞳椅碉罪馈超就喧频搓湃皑舌倍旗数据结构基础数据结构基础17用参数用参数n= 5调用调用Factorial的过程如下：的过程如下：Factorial (5) = (5* Factorial (4) = (5* (4* Factorial (3) = (

18、5* (4* (3* Factorial (2) = (5* (4* (3* (2* Factorial (1) = (5* (4* (3* (2* 1) = (5* (4* (3* 2) = (5* (4* 6) = (5* 24) = 120馅即仆盅屿申芯辙幅筹谐媳辰措彝戌假赶挟岳驻浇佃柔迭茅跺渍旬捶景是数据结构基础数据结构基础18递归算法有四个特性：递归算法有四个特性：（1）必必须须有有可可最最终终达达到到的的终终止止条条件件，否否则则程程序序将将陷陷入无穷循环；入无穷循环；（2）子子问问题题在在规规模模上上比比原原问问题题小小，或或更更接接近近终终止止条条件；件；（3）子子问问题题可可

19、通通过过再再次次递递归归调调用用求求解解或或因因满满足足终终止止条件而直接求解；条件而直接求解；（4）子问题的解应能组合为整个问题的解。）子问题的解应能组合为整个问题的解。尊麓此窑扮谚彝绷巳鼠奏琴熔兽编诸盔脊记轻堤睬臃吐撮弃年阑获韧铣桌数据结构基础数据结构基础19例例1.4 全排列生成器：给定一个具有全排列生成器：给定一个具有n1n1个元素的集个元素的集合，打印该集合的全排列。合，打印该集合的全排列。 分析四个元素分析四个元素(a(a，b b，c c，d)d)的情况，结果可以如的情况，结果可以如下构造：下构造： （1） a后接后接(b，c，d)的全排列的全排列 （2） b后接后接(a，c，d)

20、的全排列的全排列 （3） c后接后接(a，b，d)的全排列的全排列 （4） d后接后接(a，b，c)的全排列的全排列 这表明，如果能生成这表明，如果能生成n 1个元素的全排列，就能个元素的全排列，就能生成生成n个元素的全排列。个元素的全排列。息盔堕被腰我刹堂泳殴储假模炙蝎峪落沈译妨秃从滨色捣峭叔硅涕廉胸落数据结构基础数据结构基础20 对于只有对于只有1个元素的集合，可以直接生成其全排个元素的集合，可以直接生成其全排列。于是，全排列生成问题的递归步骤和终止条件列。于是，全排列生成问题的递归步骤和终止条件可以确定。可以确定。 求解函数求解函数perm：void perm (char *a, con

21、st int k，const int n) / n 是数组a的元素个数，生成ak,an-1的全排列 int i; if (k = = n-1) / 终止条件，输出排列 for ( i=0; in; i+) cout ai “ ”; / 输出包括前 / 缀，以构成整个问题的解 cout endl;愁缠岂莫党硼蚤期狂贾湃诲皿定兢女星麓雁萍屯教改淫割晰货掇爬玲巳桐数据结构基础数据结构基础21 else / ak,an-1 的排列大于1，递归生成 for ( i = k; i n; i+) char temp = ak; ak = ai; ai = temp; / 交换ak / 和 ai perm(a

22、,k+1,n); / 生成 ak+1,an-1的全排列 temp = ak; ak = ai; ai = temp; / 再次交换 ak 和 / ai , 恢复原顺序 / else结束 / perm结束 通过调用通过调用perm(a, 0, n)，可以生成，可以生成n个元素的全个元素的全排列。排列。 誓毕济厢虎薛愁奴暗釉回姻鬼氏后蔷凸蓄铰娠抱使搏其锌饰挪惜沫合嘶寥数据结构基础数据结构基础22 用用n = 3 和和 a0.2 = (a, b, c)调用调用perm的示意如下：的示意如下：烈碱般限钎牡遮椰国锁斧握骆汲钞佃啥岩乡酞拧酉俗吊寒圭窍缚舞竞镭剖数据结构基础数据结构基础23当算法操作的数据结

23、构是递归定义的时候也适合当算法操作的数据结构是递归定义的时候也适合使用递归。后面将有许多此类的重要例子使用递归。后面将有许多此类的重要例子。作业：作业：P255，6枣氢峡较关看富殷惹怔优懂靶希可塌了曲浊殆戌摹尝赐游漱授蒲粕嘶平错数据结构基础数据结构基础241.5 性能分析性能分析 除了正确性、可用性、可读性和容错性以外，除了正确性、可用性、可读性和容错性以外，算算法的性能法的性能是评价算法优劣的重要指标。是评价算法优劣的重要指标。空间复杂性空间复杂性：算法开始运行直至结束过程中所需：算法开始运行直至结束过程中所需要的最大存储资源开销的一种度量。要的最大存储资源开销的一种度量。时间复杂性时间复杂

24、性：算法开始运行直至结束所需要的执：算法开始运行直至结束所需要的执行时间的一种度量。行时间的一种度量。性能评价性能评价分为分为事前估计事前估计和和事后测量事后测量。性能分析性能分析就是指对算法的空间复杂性和时间复杂就是指对算法的空间复杂性和时间复杂性进行事前估计。性进行事前估计。邮舞索颖积诞影猖拷掉毋活鸳空惋垦赦崔郝吸窍肃们汕酷痈抖辈跌役爬撂数据结构基础数据结构基础251.5.1 空间复杂性空间复杂性 程序程序P的空间需求的空间需求 S(P) = c + SP(实例特性实例特性) 其中，其中，c是常数，是常数，SP(实例特性实例特性) 是实例特性的是实例特性的函数。函数。分析的重点是分析的重点

25、是SP(实例特性实例特性)。对于一个给定问题，首先要确定其实例特性，才对于一个给定问题，首先要确定其实例特性，才可能分析求解算法的空间要求。可能分析求解算法的空间要求。确定实例特性与具体问题密切相关。确定实例特性与具体问题密切相关。勤牟财亭暖缓摆较咙乏债狡慎目卯梁卜瞅允烬震蹋贞芬敲分赌氖韩怒尤排数据结构基础数据结构基础26例如例如:1 float rsum (float *a, const int n) 2 if (n = 0 ) return 0;/ 当n = 1时返回a03 else return rsum( a, n1) + an1;4 rsum是一个递归求和算法，其实例特性是是一个递归

26、求和算法，其实例特性是n。每。每次递归调用需在栈顶保存次递归调用需在栈顶保存n的值、的值、a的值、返回值和的值、返回值和返回地址，共需返回地址，共需4个存储单元。个存储单元。 由于算法的递归深度是由于算法的递归深度是n+1，故所需栈空间是，故所需栈空间是4(n+1)，即，即Srsum(n) = 4(n+1)。蹋歌耐渠瘸椽量买忘铜烛瘁娃入拥骋祭荐迫矮尾整呵谤舌况是鲤砸彬译辞数据结构基础数据结构基础271.5.2 时间复杂性时间复杂性 算法算法P的运行时间的运行时间 T(P) = c + TP(实例特性实例特性)时间复杂性分析的目的在于揭示算法的运行时间时间复杂性分析的目的在于揭示算法的运行时间随

27、着其实例特性变化的规律。随着其实例特性变化的规律。将一组与实例特性无关的操作抽象为一个程序步，将一组与实例特性无关的操作抽象为一个程序步，从而有效地简化性能分析的过程。从而有效地简化性能分析的过程。程序步程序步：算法中的一个在语法和语义上有意义的：算法中的一个在语法和语义上有意义的指令序列，而且该序列执行时间与算法的实例特指令序列，而且该序列执行时间与算法的实例特性无关。性无关。簇烯霸痪周鹃援辆舌兜斜阴蕴哎慨裹秤亦洒冤卡栅厕蚤充赋婶区王氛鸥疹数据结构基础数据结构基础28各类各类C+C+语句的程序步数详见教科书。语句的程序步数详见教科书。可以通过列出各个语句的程序步数确定整个程序可以通过列出各个

28、语句的程序步数确定整个程序的程序步数。的程序步数。例例1.5 程序程序sum： 1 float sum (float *a, const int n) 2 float s = 0; 3 for (int i = 0; i 0时时Trsum(n) = 2+ Trsum(n-1)。齿栽疏堰鸿独石诲凭搓颁丝彪闹术金跌曲浅少盟抛扁肉勘环双饶肿捏汉桌数据结构基础数据结构基础31通过反复代入可得：通过反复代入可得： Trsum(n) = 2+ Trsum(n-1) = 2+2+Trsum(n-2) = 2*2+ Trsum(n-2) = 2+2+2+ Trsum(n-3) = 2*3+ Trsum(n-3

29、) = 2n+ Trsum(0) = 2n+2 所以所以rsum的程序步数为的程序步数为2n+2。辆稿屏睹搜恢丢豢俄废泉盯即座绥酱虏典敏单傍瓢啸蛤徊淌诚慰党烂景锁数据结构基础数据结构基础32许许多多程程序序的的实实例例特特性性并并不不仅仅仅仅依依赖赖于于实实例例规规模模n，还可能与，还可能与实例内容实例内容密切相关。密切相关。 例例如如，二二分分查查找找的的程程序序步步数数，不不仅仅与与元元素素个个数数n，而且与集合内容有关。，而且与集合内容有关。 有有时时需需要要按按最最好好、最最坏坏和和平平均均三三种种情情况况分分析析算算法法的时间复杂性。的时间复杂性。珐待肿鸦谁锣掐负赚涛滨贷令平妈蓑观揍

30、斩糟旧嘻皑萎桩径鲁踊篆怒坝婿数据结构基础数据结构基础331.5.3 O表示法表示法 程序步本身就不是一个准确的概念，而是一个抽程序步本身就不是一个准确的概念，而是一个抽象的概念。象的概念。 再作一次抽象，从由多种因素构成的时间复杂性再作一次抽象，从由多种因素构成的时间复杂性中抽取出其主要因素，将常数抽象为中抽取出其主要因素，将常数抽象为1，有利于抓，有利于抓住主要矛盾，简化复杂性分析。住主要矛盾，简化复杂性分析。假设函数假设函数f和和g是非负函数。是非负函数。 定义：定义：f(n) = O(g(n) 当且仅当存在正值常数当且仅当存在正值常数c和和n0，使得对所有，使得对所有n n0，f(n)

31、c*g(n)。 邻柳拔艰羹第弹章比伎克昆蹄挽碎填锐那绅敌掩疤不殿覆匙赶凝概附鸵彩数据结构基础数据结构基础34 例例1.8 5n + 4 = O(n) 100n + 6 = O(n) 10 n2 + 4n + 2 = O(n2) 6*2n + n2 = O(2n) 3n + 2 O(1) O(1)表示常数，表示常数， O(log n) 表示对数，表示对数，O(n)表示线表示线性，性，O(n2)表示平方，表示平方，O(n3)表示立方，表示立方， O(2n)表表示指数。示指数。唤坠梢檀豁藐六兹砌切爽痊揭父娠谓胖疯或粪麦磺租殴篱惋罩童舔摘纪扑数据结构基础数据结构基础35f(n) = O(g(n)只表示

32、对所有只表示对所有n n0，g(n)是是f(n)的的上界。因此，上界。因此，n = O(n2) = O(n3) = O(2n)。为了使。为了使f(n) = O(g(n)提供尽可能多的信息，提供尽可能多的信息，g(n)应尽可能应尽可能小。小。有时，由于现有分析能力的限制，人们还不能得有时，由于现有分析能力的限制，人们还不能得出一个算法计算时间的准确数量级。例如对实际出一个算法计算时间的准确数量级。例如对实际计算时间为计算时间为O(n log n)的算法，目前的分析结果只的算法，目前的分析结果只能表明其计算时间是能表明其计算时间是O(n2)，这时说该算法的计算，这时说该算法的计算时间是时间是O(n

33、2)也没错，待到以后认识深入了，可以也没错，待到以后认识深入了，可以改说成改说成O(n log n)。渤贵蔚碘跳表巡蒂柞羊厨葵校踩元浸硷倦绵某趣础砒窖土茨摄粳谢插朵羡数据结构基础数据结构基础36 定理定理1.1 设设f(n)= amnm + am-1nm-1 + + a1n + a0，则则 f(n) = O(nm)。钎宁牙淳淋功心留擞俗作截路壮汝滨合劳览似闺铡戮际寻避背少眺呢觉宿数据结构基础数据结构基础37 例例1.11 n位二进制数加位二进制数加1的时间复杂性。设数组的时间复杂性。设数组a模拟一个模拟一个n位二进制数，下列算法将位二进制数，下列算法将a表示的二进制表示的二进制数加数加1。em

34、un Binary 0, 1 ;void BinaryAddOne ( Binary *a, const int n ) int i = n-1; while (ai = = 1 & i = 0) /从右向左扫描，遇到第一 / 个0位停止，并将所经过的全部1置0 ai = 0; i-; if ( i = 0 ) ai = 1;攘暇整旅鸭讲绷窗砸舅推姚翌蜗歇崩郴垃摹抿诉湘宜泼忻暑欧猿缅卢伏奇数据结构基础数据结构基础38下面分别分析其最好、最坏和平均时间复杂性：下面分别分析其最好、最坏和平均时间复杂性：（1）最好情况最好情况：当右边第一位为：当右边第一位为0 0时，扫描停止，时，扫描停止，算法时间

35、复杂性为算法时间复杂性为O(1)O(1)。（2 2）最坏情况最坏情况：当：当n n个二进制位全为个二进制位全为1 1时，需扫描时，需扫描n n位，算法时间复杂性为位，算法时间复杂性为O(n)O(n)。骸崇铡慎毙唯痊盖呵耸链旭敬申琶输处民卷岭惕希蔑锹钮译猾激范垮抉具数据结构基础数据结构基础39（3 3）平均情况平均情况。n n位二进制数共有位二进制数共有2 2n n种取值。以种取值。以n=3 n=3 为例，有下列取值：为例，有下列取值： 靴终闪笔尊袜离居然盒敏窿褪虱菱榴凯肥窑滩吧信寇绕荫穿邱儿赛谐述盎数据结构基础数据结构基础40一般，从右到左有连续一般，从右到左有连续m个个1需需m + 1次操作

36、，这次操作，这种取值共种取值共2n-(m+1)个（个（m 100），只只有有复复杂杂性性较较小小（如如，n，nlog2n，n2，n3）的的算算法法是是实实用用的的。即即使使计计算算机机的的速速度度再再提提高高1000倍倍，表表中中时时间间也也只只不不过过缩缩小小1000倍倍。在在这这种种情情况况下下，当当n=100时时，n10个个程程序序步步的的运运行行时时间间是是3.17年，年，2n个程序步的运行时间是个程序步的运行时间是4 1010年。年。狞锌味骏压枪樊垣沥把宁杜怯蛛迁宠亏熄印戳出剥篙诡挖援饵难腥投贺络数据结构基础数据结构基础43 可可见见，如如果果一一个个算算法法的的时时间间复复杂杂性性

37、过过高高，当当n n大大于于一一定定值值时时，再再快快的的计计算算机机也也无无法法在在实实际际可可行行的的时时间间内内完成其运行。完成其运行。讹液撅顾者霖装儿划饼耳惹阑禾后诚赂心吸瞒刻肝碰妮轨宅磐堑柑舀崎伐数据结构基础数据结构基础441.6 性能测量性能测量 性能测量性能测量：在一定的数据范围内准确获取程序运：在一定的数据范围内准确获取程序运行所需要的空间和时间，属于事后测量。行所需要的空间和时间，属于事后测量。测量的结果依赖于编译器及其设置，还依赖于程测量的结果依赖于编译器及其设置，还依赖于程序运行的计算机。下面重点研究性能（程序的计序运行的计算机。下面重点研究性能（程序的计算时间）测量的方

38、法。算时间）测量的方法。 假设函数假设函数time ( &hsec )将当前时间返回到变将当前时间返回到变量量hsec中，精度为中，精度为1毫秒。下面以测量顺序查找算毫秒。下面以测量顺序查找算法法seqsearch在最坏情况下的性能为例，说明性能在最坏情况下的性能为例，说明性能测量的方法。测量的方法。区垫诫毒虱蠕同倚诬甘整正寿毒灯举喊在祥凰绍氯因锚橇鉴歧篡篆叉神泛数据结构基础数据结构基础45int seqsearch (int *a, const int n, const int x ) int i = n; a0 = x; while (ai != x) i-; return i; 顺序查找

39、算法的最坏时间复杂性是顺序查找算法的最坏时间复杂性是O(n)。为了。为了反映被忽略的常数因子的影响，对于较小的反映被忽略的常数因子的影响，对于较小的n应选较应选较多的值测量，对于较大的多的值测量，对于较大的n值则可稀疏测量。值则可稀疏测量。 限于时钟精度，对于太短的事件必须限于时钟精度，对于太短的事件必须重复重复m次，次，然后用测得的总时间除以然后用测得的总时间除以m求出事件的时间。求出事件的时间。晓磷腹妄界薪挠挫处剃橙毖被溶嗽虚帘沈栗永瓤琼枕此昂戎灯仿著砒瑟魂数据结构基础数据结构基础46顺序查找算法的测量程序如下：顺序查找算法的测量程序如下： void TimeSearch (const l

40、ong m) int a1001, n20; for ( int j = 1; j=1000; j+ ) aj = j; / 初始化a for ( j=0; j10; j+ ) / n的取值 nj = 10*j; nj+10 = 100*( j+1 ); cout “ n 总时间 运行时间” endl; for ( j=0; j20; j+ ) long start, stop; time (&start);/ 开始计时 for ( long b=1; b = m; b+ )int k = seqsearch(a, nj, 0 ); / 失败查找栅依庸康放惰械欠钒壬崭丧坠晕均搜表吁株畦悠跨股沛

41、炯瓮民亦漓节锦曳数据结构基础数据结构基础47 time (&stop); / 停止计时 long totalTime = stop - start; float runTime = (float) (totalTime) / (float)m; cout nj totalTime runTimeendl; 执行执行TimeSearch(300000)的输出如下表所示。的输出如下表所示。从该表可以看出，从该表可以看出，t基本上随基本上随n线性增长。利用线性增长。利用n = 0和和60这两点的数据，可得线性函数这两点的数据，可得线性函数 t = 0.000096n + 0.0008。由此可推算，当

42、。由此可推算，当n = 1000，t = 0.00968。这。这与实际测量的数据完全吻合。与实际测量的数据完全吻合。 溯獭洁黄瑞乓殷性桶掸范北值茂六俐女藏桃类懊臆伎幸诅也侮餐扔铂翻诌数据结构基础数据结构基础48猎揍械讯翁差酒臆傈遁撤归池妆禄聂砍歌建剃州澜谭创巳檀捉浅即傻罐挝数据结构基础数据结构基础49规划性能测量实验时应注意以下问题：规划性能测量实验时应注意以下问题： 时钟精度、期望的测量结果精度以及与此相关的时钟精度、期望的测量结果精度以及与此相关的重复次数。重复次数。 根据是测量最坏性能还是平均性能，生成合适的根据是测量最坏性能还是平均性能，生成合适的实验数据。实验数据。 实验目的：是为了

43、比较还是为了预测实际运行时实验目的：是为了比较还是为了预测实际运行时间？间？ 当实验目的是预测实际运行时间时，人们需要通当实验目的是预测实际运行时间时，人们需要通过测量数据建立过测量数据建立t与与n之间的函数关系。之间的函数关系。直腊藩豢好松续憋瞄磨萍鸳娶镰料沤御皆喧白灯遮莎科鹅吞点赃郝疟石娱数据结构基础数据结构基础50 一般需用计算机生成导致一个算法最坏性能的一般需用计算机生成导致一个算法最坏性能的数据集。数据集。 但在有的情况下计算机生成也非常困难。这时但在有的情况下计算机生成也非常困难。这时可根据实例特性的值随机生成足够量的实验数据，可根据实例特性的值随机生成足够量的实验数据，取这些数据

44、导致的最长运行时间作为最坏性能。取这些数据导致的最长运行时间作为最坏性能。 生成平均性能数据更为困难，一般也采用随机生成平均性能数据更为困难，一般也采用随机生成的方法。生成的方法。实验作业：实验作业：P2515衙朋切坝网员炯浪丧州唯恫贬禾筐轧谋虾认修铣痰绣键摘炮贩扮嘎氧乖吊数据结构基础数据结构基础511.7 C+中的模板中的模板 C+的模板（的模板（template）有效地提高了函数和）有效地提高了函数和类的可重用性。类的可重用性。 模板模板（又称为参数化类型）是一种能被实例化（又称为参数化类型）是一种能被实例化为任何数据类型的变量，这些类型既包括为任何数据类型的变量，这些类型既包括C+基本基

45、本类型又包括用户定义的类型。类型又包括用户定义的类型。模板函数模板函数:template int seqsearch (KeyType *a, const int n, KeyType x ) int i=n; a0=x; while (ai != x) i-; return i; 蚌时寞循咕艺均考考沤冀谢钉补述炼差铬箔玛浩框克亢籽镍帮倾衬巴持每数据结构基础数据结构基础52 通过调用通过调用seqsearch，可以很容易地在字符数组，可以很容易地在字符数组或浮点数数组中查找元素或浮点数数组中查找元素: char carray200; float farray300; char x = r; f

46、loat y = 306.523; / 设此时以上数组已完成初始化 seqsearch(carray, 200, x); seqsearch(farray, 300, y); 函数函数seqsearch的的KeyType在调用时被实例化为在调用时被实例化为相应的实参类型，例如，调用相应的实参类型，例如，调用seqsearch(farray, 300, y)表示在浮点数数组表示在浮点数数组farray中查找浮点数中查找浮点数y。 盂糜涛狗谚宾争愉赎华肯付剐厢叠蒜驭卒逐葡蓟锤厢席没薪慌张篮嫉擞答数据结构基础数据结构基础53 seqsearch使用操作符使用操作符“!=”比较两个比较两个KeyTyp

47、e对象，使用操作符对象，使用操作符“=”将一个将一个KeyType对象赋值给对象赋值给另一个另一个KeyType对象。对象。 对于用户定义的数据类型，这些操作不可能由对于用户定义的数据类型，这些操作不可能由系统预定义。用户必须重载这些操作以实现新的语系统预定义。用户必须重载这些操作以实现新的语义。义。擦最汁戊龟汐葵猎洼葛杜烙簇距爬须豆匪琐仿蘑残阮笆谚氓胶梳账蚊烯乎数据结构基础数据结构基础54模板类模板类：template class Bag public: Bag ( int MaxSize = DefaultSize ); / 假设DefaultSize已定义 int Add (const

48、Type& x ); / 将对象x加入容器中 int Delete (const int k ); / 从容器中删除并打印k 个对象private: int top; / 指示已用空间 Type *b; / 用数组b存放Type对象 int n; / 容量; 铸宅宵翌埋蒋减占趋殃诣迈窍姆额迫捅炮芋沈赞俏昭茎潘悟何贝钮偶论受数据结构基础数据结构基础55template Bag:Bag ( int MaxSize = DefaultSize ):n(MaxSize) b = new Typen; top = -1;template int Bag:Add (const Type& x) if (t

49、op = = n-1) return 0; / 返回0表示加入失败 else b+top = x; return 1;祸喇揪冷蝴映饵支此题层豆悼筹铰炕做福炊说饱墙蕊闭程发喳亲萎哎棺亏数据结构基础数据结构基础56template int Bag:Delete (const int k) if (top + 1 k ) return 0; / 返回0表示容器内元素不足k/ 个，删除失败 else for (int i = 0; i k; i+) cout btop i “ ” ; top = top - k; return 1; Bag f; Bag c;于是，于是，Bag对象对象f存放浮点数，存放浮点数，c存放圆。存放圆。瀑复硒瞩挝漱答杉灰万纺劲扣狐杠咨梳廷阮席幕股甲脉娩毋研统钩挟庶谁数据结构基础数据结构基础571.8 效率与权衡效率与权衡 时间和空间的权衡；时间和空间的权衡；通用性和效率的权衡；通用性和效率的权衡；开发效率与运行效率的权衡；开发效率与运行效率的权衡；等等。等等。 么缴窜侍拓爵跌天读孟踊劝赵仙拜糜全摘氦旭苯指娥步芒捉帽捍前谜曳漏数据结构基础数据结构基础58