数据结构数据结构孟桂娥gemengsjtu.edu.cn1教材教材数据结构：思想与实现数据结构：思想与实现惠玉惠玉 俞勇俞勇 高等教育出版社高等教育出版社数据结构与算法分析数据结构与算法分析 C+ 描述（第描述（第3版）版） Mark Allen Weiss著著 人民邮电出版社人民邮电出版社Introduction to Algorithms (3th Ed) Thomas H.Cormen等等2资料下载（临时）ftp:/public.sjtu.edu.cn用户名：gemeng密码：public3成绩组成成绩组成大作业大作业期末考试期末考试出勤、课堂表现出勤、课堂表现4第一章第一章 引言引言什么是数据结构什么是数据结构算法分析算法分析面向对象的数据结构面向对象的数据结构5什么是数据结构什么是数据结构没有标准的定义，但有共识没有标准的定义，但有共识数据结构：通过抽象的方法研究一组有数据结构：通过抽象的方法研究一组有特定特定关系关系的数据的存储与处理的数据的存储与处理数据结构的研究内容：数据结构的研究内容：数据之间的逻辑关系，以及这种关系对应的操作数据之间的逻辑关系，以及这种关系对应的操作如何存储某种逻辑关系如何存储某种逻辑关系（存储实现）（存储实现）在这种存储模式下，关系的操作是如何实现的在这种存储模式下，关系的操作是如何实现的（运算实现）（运算实现）6数据的逻辑结构数据的逻辑结构集合结构集合结构：元素间的次序是任意的。元素：元素间的次序是任意的。元素之间除了之间除了“属于同一集合属于同一集合”的联系外没有的联系外没有其他的关系。其他的关系。线性结构线性结构：数据元素的有序序列。除了第：数据元素的有序序列。除了第一个和最后一个元素外，其余元素都有一一个和最后一个元素外，其余元素都有一个前趋和一个后继个前趋和一个后继树形结构树形结构：除了根元素外，每个节点有且：除了根元素外，每个节点有且仅有一个前趋，后继数目不限仅有一个前趋，后继数目不限图型结构图型结构：每个元素的前趋和后继数目都：每个元素的前趋和后继数目都不限不限7集合结构集合结构线性结构线性结构树形结构树形结构图形结构图形结构8数据结构的操作数据结构的操作创建：创建一个数据结构创建：创建一个数据结构清除：删除数据结构清除：删除数据结构插入：在数据结构指定的位置上插入一个新元素插入：在数据结构指定的位置上插入一个新元素删除：将数据结构中的某个元素删去删除：将数据结构中的某个元素删去搜索：在数据结构中搜索满足特定条件的元素搜索：在数据结构中搜索满足特定条件的元素更新：修改数据结构中的某个元素的值更新：修改数据结构中的某个元素的值访问：访问数据结构中的某个元素访问：访问数据结构中的某个元素遍历：按照某种次序访问数据结构中的每一元素，使每个遍历：按照某种次序访问数据结构中的每一元素，使每个元素恰好被访问一次元素恰好被访问一次每一种数据结构的特定操作每一种数据结构的特定操作9数据结构的存储实现数据结构的存储实现包括两个部分：包括两个部分：数据元素的存储数据元素的存储数据元素之间的关系的存储数据元素之间的关系的存储 物理结构由三个部分组成：物理结构由三个部分组成：存储结点，每个存储结点存放一个数据元素；存储结点，每个存储结点存放一个数据元素；数据元素之间的关系的存储，也就是逻辑结构数据元素之间的关系的存储，也就是逻辑结构的机内表示；的机内表示；附加信息，便于运算实现而设置的一些附加信息，便于运算实现而设置的一些“哑结哑结点点”，如链表中的头结点。，如链表中的头结点。 10基本的存储方式基本的存储方式数据元素的类型可以是各种各样的，通常数据元素的类型可以是各种各样的，通常不会是简单的内置类型，因此存储结点可不会是简单的内置类型，因此存储结点可以是一个结构体类型的变量或对象以是一个结构体类型的变量或对象数据结构主要讨论关系的存储。因此，数数据结构主要讨论关系的存储。因此，数据结构主要采用据结构主要采用泛型程序设计泛型程序设计的思想的思想11关系的存储关系的存储顺序存储：用存储的位置表示元素之间的关系。顺序存储：用存储的位置表示元素之间的关系。主要用数组实现。主要用数组实现。链接存储：用指针显式地指出元素之间的关系，链接存储：用指针显式地指出元素之间的关系，如单链表就是表示线性关系的。如单链表就是表示线性关系的。哈希存储方式：是专用于集合结构的数据存放方哈希存储方式：是专用于集合结构的数据存放方式。在哈希存储中，各个结点均匀地分布在一块式。在哈希存储中，各个结点均匀地分布在一块连续的存储区域中，用一个哈希函数将数据元素连续的存储区域中，用一个哈希函数将数据元素和存储位置关联起来。和存储位置关联起来。索引存储方式：所有的存储结点按照生成的次序索引存储方式：所有的存储结点按照生成的次序连续存放。另外设置一个索引区域表示结点之间连续存放。另外设置一个索引区域表示结点之间的关系。的关系。 12第一章第一章 引言引言什么是数据结构什么是数据结构算法分析算法分析面向对象的数据结构面向对象的数据结构13算法分析算法分析数据结构是讨论一组数据的处理问题数据结构是讨论一组数据的处理问题每一种存储方式下对应的每一种操作的每一种存储方式下对应的每一种操作的实现都是一个算法实现都是一个算法每种操作有多种实现方式每种操作有多种实现方式如何评价这些算法的好坏如何评价这些算法的好坏14算法的质量评价算法的质量评价正确性：算法应能正确地实现预定的功能；正确性：算法应能正确地实现预定的功能；易读性：算法应易于阅读和理解，以便于调试、易读性：算法应易于阅读和理解，以便于调试、修改和扩充；修改和扩充；健壮性：当环境发生变化（如遇到非法输入）时，健壮性：当环境发生变化（如遇到非法输入）时，算法能适当地做出反应或进行处理，不会产生不算法能适当地做出反应或进行处理，不会产生不正确的运算结果；正确的运算结果；高效率：具有较高的时间和空间性能。高效率：具有较高的时间和空间性能。这四个指标往往是互相冲突的，数据结构主要考这四个指标往往是互相冲突的，数据结构主要考虑的是时空性能。虑的是时空性能。15算法效率分析算法效率分析如何确定一个算法是高效的算法就是分析如何确定一个算法是高效的算法就是分析该算法所需要的资源。算法的资源包括：该算法所需要的资源。算法的资源包括：时间：程序运行所需要的时间。要运行一年的时间：程序运行所需要的时间。要运行一年的算法是很难让人接受的算法是很难让人接受的空间：程序运行所需要的空间。需要几个空间：程序运行所需要的空间。需要几个G G的的内存的算法同样也令人难以接受。内存的算法同样也令人难以接受。16算法分析算法分析时间复杂度的概念时间复杂度的概念 算法运算量的计算算法运算量的计算渐进表示法渐进表示法时间复杂度的计算时间复杂度的计算算法的优化算法的优化空间复杂度的概念空间复杂度的概念 17程序的运行时间程序的运行时间 影响运行时间的因素影响运行时间的因素问题规模和输入数据的分布问题规模和输入数据的分布编译器生成的目标代码的质量编译器生成的目标代码的质量计算机系统的性能计算机系统的性能程序采用的算法的优劣程序采用的算法的优劣关键是算法的优劣关键是算法的优劣18有效算法的重要性有效算法的重要性计算机不是万能的，并非所有的算法，计算机都能够计算计算机不是万能的，并非所有的算法，计算机都能够计算出有用的结果。差的算法不一定有实际意义。如果一台计出有用的结果。差的算法不一定有实际意义。如果一台计算机算机 1 秒能处理秒能处理1000条指令，那么如果处理条指令，那么如果处理n个数据所需个数据所需执行的指令数如表中的函数所示执行的指令数如表中的函数所示时间函数时间函数n=20n=50n=100n=500n.02s.05s.1s.5snlogn.09s.3s.6s4.5sn2.4s2.5s10s250sn38s2分分17分分35小小时2n34分分19有效时间中能够处理的数据量有效时间中能够处理的数据量时间时间函数函数在在 1 秒内秒内 在在 1 分钟内分钟内 在在 1 小时小时n10006 * 1043.6 * 106nlogn14048932 * 105n2312441897n310391532n10152120有效算法的重要性有效算法的重要性关键：提高算法的效率而不是提高机器的速度！关键：提高算法的效率而不是提高机器的速度！时间函数时间函数提速提速10倍前的求倍前的求解规模解规模提速提速10倍后的倍后的求解规模求解规模ns110s1nlogns210s2n2s33.16s3n3s42.15s42ns5s5 + 3.321时间复杂度时间复杂度算法的时间复杂度是一种抽象的度量，即运算算法的时间复杂度是一种抽象的度量，即运算量与问题规模之间的关系。量与问题规模之间的关系。算法的时间复杂度也与被处理的数据分布有关算法的时间复杂度也与被处理的数据分布有关算法的时间复杂度算法的时间复杂度最好情况的时间复杂度最好情况的时间复杂度最坏情况的时间复杂度最坏情况的时间复杂度平均情况的时间复杂度平均情况的时间复杂度 22算法分析算法分析时间复杂度的概念时间复杂度的概念 算法运算量的计算算法运算量的计算渐进表示法渐进表示法时间复杂度的计算时间复杂度的计算算法的优化算法的优化空间复杂度的概念空间复杂度的概念 23算法运算量的计算算法运算量的计算根据问题的特点合理地选择一种或几种根据问题的特点合理地选择一种或几种操作作为操作作为“标准操作标准操作”，将标准操作作，将标准操作作为一个抽象的运算单位；为一个抽象的运算单位；确定每个算法在给定的输入下共执行了确定每个算法在给定的输入下共执行了多少次标准操作；并将它作为算法的计多少次标准操作；并将它作为算法的计算量。算量。24实例实例如果有一组正整数，存放在数组如果有一组正整数，存放在数组arrayarray中，中，要求设计一个算法求数组中的最大值与要求设计一个算法求数组中的最大值与d d的乘积。的乘积。 25算法一算法一int max1(int array, int size, int d)int max=0, i; for (i=0; i size ; +i) arrayi *= d; for (i=0; i max) max = arrayi; return max;算法二算法二int max2(int array, int size, int d)int max=0, i; for (i=0; i max) max = arrayi; return max * d;26运算量的计算运算量的计算用用乘法乘法、赋值赋值和和条件判断条件判断作为标准操作作为标准操作设输入的数组值为设输入的数组值为1,2,3,d=41,2,3,d=4Max1Max1：3 3次乘法，次乘法，1414次赋值，次赋值，1111次比较，次比较，共共2828次标准操作次标准操作 max2max2执行了执行了1 1次乘法，次乘法，7 7次赋值，次赋值，7 7次比较，次比较，共共1515次标准操作。次标准操作。 27找出运算量的函数找出运算量的函数如找出如找出max1max1的最坏情况下的运行时间函数的最坏情况下的运行时间函数 第一个第一个forfor循环：循环：循环控制行中，表达式循环控制行中，表达式1 1执行一次，表达式执行一次，表达式2 2执行执行n+1n+1次，次，表达式表达式3 3执行了执行了n n次。次。每个循环周期执行一次乘法、一次赋值。每个循环周期执行一次乘法、一次赋值。总的运算量为总的运算量为1+(n+1)+n+n*2 = 4n+21+(n+1)+n+n*2 = 4n+2。第二个循环：第二个循环：循环控制行中，表达式循环控制行中，表达式1 1执行了一次，表达式执行了一次，表达式2 2执行了执行了n+1n+1次，表达式次，表达式3 3执行了执行了n n次，次，每个循环周期执行一次比较，一次赋值。每个循环周期执行一次比较，一次赋值。总运算量为总运算量为1+(n+1)+n+n*2 = 4n+21+(n+1)+n+n*2 = 4n+2。max1max1在最坏情况下的总运算量是在最坏情况下的总运算量是8n+48n+4。 28算法分析算法分析时间复杂度的概念时间复杂度的概念 算法运算量的计算算法运算量的计算渐进表示法渐进表示法时间复杂度的计算时间复杂度的计算算法的优化算法的优化时间复杂度的概念时间复杂度的概念 29渐进表示法渐进表示法算法的运行时间函数可能是一个很复杂算法的运行时间函数可能是一个很复杂的函数，如何比较这些函数并从中选取的函数，如何比较这些函数并从中选取出一个好的算法呢？出一个好的算法呢？ 时间性能主要考虑的是问题规模很大的时间性能主要考虑的是问题规模很大的时候运行时间随问题规模的变化规律时候运行时间随问题规模的变化规律 渐进表示法：不考虑具体的运行时间函渐进表示法：不考虑具体的运行时间函数，只考虑运行时间函数的数量级数，只考虑运行时间函数的数量级30渐进表示法渐进表示法定义：定义：( (大大O) O) 如果存在正的常数如果存在正的常数c c和和N N0 0，满足当满足当N=NN=N0 0时有时有T(N)= T(N)=NN=N0 0时有时有T(N) T(N) cF(NcF(N) )，则，则T(N)T(N)是是(F(N)(F(N)。定义：定义：( (大大) ) 当且仅当当且仅当T(N)T(N)是是O(F(N)O(F(N)，并且并且T(N)T(N)又是又是(F(N)(F(N)，则，则T(N)T(N)是是(F(N)(F(N)。定义：定义：( (小小O) O) 当且仅当当且仅当T(N)T(N)是是O(F(N)O(F(N)，并且并且T(N)T(N)不是不是 (F(N) (F(N)，则，则T(N)T(N)是是o(F(N)o(F(N)。31大大O表示法实例表示法实例设设 T(nT(n) = (n+1) = (n+1)2 2 那么，取那么，取n n0 0 = 1 = 1 及及 c=4 c=4 时，时， T(nT(n) = cn) = cn2 2 成立。成立。 所以，所以，T(nT(n) = O(n) = O(n2 2) ) 大大O O表示法就是取运行时间函数的主项表示法就是取运行时间函数的主项32F(N)的选择的选择大大O O表示法的表示法的O O是单词是单词OrderOrder的首字母，表的首字母，表示示“数量级数量级”大大O O表示法并不需要给出运行时间的精确表示法并不需要给出运行时间的精确值，而只需要给出一个数量级，表示当值，而只需要给出一个数量级，表示当问题规模很大时算法运行时间的增长是问题规模很大时算法运行时间的增长是受限于哪一个数量级的函数受限于哪一个数量级的函数在选择在选择F(N)F(N)时，通常选择的是比较简单时，通常选择的是比较简单的函数形式，并忽略低次项和系数。的函数形式，并忽略低次项和系数。 33典型的增长率典型的增长率c c常量常量logNlogN对数对数LogLog2 2N N对数的平方对数的平方N N线性线性NlogNNlogNNlogNNlogNN N2 2平方平方N N3 3立方立方2 2N N指数指数34算法按时间复杂度分类算法按时间复杂度分类多项式时间：渐进时间复杂度有多项式时多项式时间：渐进时间复杂度有多项式时间限界的算法间限界的算法指数时间算法：渐进时间复杂度有指数时指数时间算法：渐进时间复杂度有指数时间限界的算法间限界的算法多项式时间复杂度的关系：多项式时间复杂度的关系： O(1) O(1) O(logNO(logN) O(N) ) O(N) O(NlogNO(NlogN) ) O(N O(N2 2) O(N) O(N3 3) ) 指数时间复杂度的关系：指数时间复杂度的关系： O(2O(2N N) O(N!) O(N) O(N!) O(NN N) )35算法分析算法分析时间复杂度的概念时间复杂度的概念 算法运算量的计算算法运算量的计算渐进表示法渐进表示法时间复杂度的计算时间复杂度的计算算法的优化算法的优化空间复杂度的概念空间复杂度的概念 36大大O表示法的计算表示法的计算时间复杂度的计算先定义标准操作，再时间复杂度的计算先定义标准操作，再计算标准操作的次数，得到一个标准操计算标准操作的次数，得到一个标准操作次数和问题规模的函数。然后取出函作次数和问题规模的函数。然后取出函数的主项，就是它的时间复杂度的大数的主项，就是它的时间复杂度的大O O表表示。示。简化方法：根据两个定理。简化方法：根据两个定理。37大大O表示法的定理表示法的定理求和定理求和定理：假定假定T1(n)T1(n)、T2(n)T2(n)是程序是程序P1P1、P2P2的运的运行时间，并且行时间，并且T1(n)T1(n)是是O(f(n)O(f(n)的，而的，而T2(n)T2(n)是是O(g(n)O(g(n)的。那么，先运行的。那么，先运行P1P1、再运行再运行P2 P2 的总的的总的运行时间是：运行时间是：T1(n)T1(n)T2(n)T2(n)O(MAX(f(n)O(MAX(f(n)，g(ng(n)。求积定理：如果求积定理：如果T1(n) T1(n) 和和 T2(n)T2(n)分别是分别是O(f(n)O(f(n)和和O(g(n)O(g(n)的，那么的，那么T1(n)T2(n)T1(n)T2(n)是是O(f(n)g(n) O(f(n)g(n) 的。的。38大大O表示法的计算规则表示法的计算规则规则规则1 1：每个简单语句，如赋值语句、输入输：每个简单语句，如赋值语句、输入输出语句，它们的运行时间与问题规模无关，在出语句，它们的运行时间与问题规模无关，在每个计算机系统中运行时间都是一个常量，因每个计算机系统中运行时间都是一个常量，因此时间复杂度为此时间复杂度为 O(1)O(1)。规则规则2 2：条件语句，：条件语句，if if then then else else ，的运行时间为执行条件判断的，的运行时间为执行条件判断的代价代价 ，一般为，一般为O(1)O(1)，再加上执行，再加上执行 then then 后面后面的语句的代价的语句的代价( (若条件为真若条件为真) )，或执行，或执行else else 后后面的语句代价面的语句代价( (若条件为假若条件为假) )之和，即之和，即max(O(thenmax(O(then子句子句) )，O(elseO(else子句子句)。39规则规则3 3：循环语句的执行时间是循环控制行和循环体：循环语句的执行时间是循环控制行和循环体执行时间的总和。循环控制一般是一个简单的条件执行时间的总和。循环控制一般是一个简单的条件判断，因此循环语句的执行时间是判断，因此循环语句的执行时间是循环体的运行时循环体的运行时间乘循环次数间乘循环次数。规则规则4 4：嵌套循环语句，对外层循环的每个循环周期，：嵌套循环语句，对外层循环的每个循环周期，内存循环都要执行它的所有循环周期，因此，可用内存循环都要执行它的所有循环周期，因此，可用求积定理计算整个循环的时间复杂度，即最内层循求积定理计算整个循环的时间复杂度，即最内层循环体的运行时间乘所有循环的循环次数。例语句：环体的运行时间乘所有循环的循环次数。例语句： for (i=0; in; i+)for (i=0; in; i+) for (j=0; jn; j+) k+; for (j=0; jn; j+) k+; 的时间复杂性为的时间复杂性为O(nO(n2 2) )40连续语句：利用求和定理把这些语句的时间连续语句：利用求和定理把这些语句的时间复杂性相加。例程序段：复杂性相加。例程序段： for (i=0; in; i+) ai=0;for (i=0; in; i+) ai=0; for (i=0; in; i+) for (i=0; in; i+) for (j=0; jn; j+) ai= i+j; for (j=0; jn; j+) ai= i+j; 有两个连续的循环组成。第一个循环的时有两个连续的循环组成。第一个循环的时间复杂度为间复杂度为O O（n n），第二个循环的时间复杂），第二个循环的时间复杂度为度为O O（n n2 2）。根据求和定理，整段程序的）。根据求和定理，整段程序的的时间复杂性为的时间复杂性为O(nO(n2 2) )41大大O的简化计算的简化计算在程序中找出最复杂、运行时间最长的在程序中找出最复杂、运行时间最长的程序段，计算它的时间复杂度。也就是程序段，计算它的时间复杂度。也就是整个程序的时间复杂度整个程序的时间复杂度在在max1max1中，最复杂的程序段是两个循环，中，最复杂的程序段是两个循环，这两个循环的时间复杂度都是相同的，这两个循环的时间复杂度都是相同的，为为O(nO(n) )，因此整个程序的时间复杂度是，因此整个程序的时间复杂度是O(nO(n) )的的 42算法分析算法分析时间复杂度的概念时间复杂度的概念 算法运算量的计算算法运算量的计算渐进表示法渐进表示法时间复杂度的计算时间复杂度的计算算法的优化算法的优化空间复杂度的概念空间复杂度的概念 43典型实例典型实例-最大连续子序列问题最大连续子序列问题给定给定(可能是负的可能是负的)整数序列整数序列 ，寻找，寻找(并并标识标识) 的值为最大的序列。如果所有的的值为最大的序列。如果所有的整数都是负的，那么最大连续子序列的和是零。整数都是负的，那么最大连续子序列的和是零。例如，假设输入是例如，假设输入是-2, 11, -4, 13, -5, 2，那么答案，那么答案是是20，它表示连续子序列包含了第，它表示连续子序列包含了第2项到第项到第4项。又项。又如第二个例子，对于输入如第二个例子，对于输入1, -3, 4, -2, -1, 6，答案，答案是是7，这个子序列包含最后四项。，这个子序列包含最后四项。44解法一解法一 穷举法穷举法分别求子序列分别求子序列:0，0，0，1， ，0，n1，1，1，2， ,1，nn，n的和，求出最大值的和，求出最大值45int maxSubsequenceSum(int a, int size, int &start, int &end) int maxSum = 0; for (int i = 0; i size; i+ ) for( int j = i; j size; j+ ) int thisSum = 0; for( int k = i; k = j; k+ )for( int k = i; k maxSum ) maxSum = thisSum; start = i; end = j; return maxSum;46时间复杂度分析时间复杂度分析最里层的语句最里层的语句thisSumthisSum += a k ; += a k ;在最里层循环在最里层循环中执行中执行j-i+1j-i+1次。第二个循环的规模是次。第二个循环的规模是n-in-i，最外，最外层的循坏规模是层的循坏规模是n n。因此最里层语句执行的次数是。因此最里层语句执行的次数是47方法二方法二 - O(n2)的算法的算法由于由于 ，因此，方法一中，因此，方法一中最里层的循环可以省略。最里层的循环可以省略。48int maxSubsequenceSum(int a, int size, int &start, int &end) int maxSum = 0; for( int i = 0; i size; i+ ) int thisSum = 0; for( int j = i; j maxSum ) maxSum = thisSum; start = i; end = j; return maxSum; 49算法三算法三 O(N)如果一个子序列的和是如果一个子序列的和是负负的，则它不可能是最大的，则它不可能是最大连续子序列的开始部分，因为我们可以通过不包连续子序列的开始部分，因为我们可以通过不包含它来得到一个更大的连续子序列。含它来得到一个更大的连续子序列。如：如：-2, 11, -4, 13, -5, 2-2, 11, -4, 13, -5, 2的最大子序列不的最大子序列不可能从可能从-2-2开始开始1, -3, 4, -2, -1, 61, -3, 4, -2, -1, 6的最大子序列不可能包的最大子序列不可能包含含11，-3-350算法三算法三 O(N)所有与最大连续子序列毗邻的连续子序列一定有负的（或所有与最大连续子序列毗邻的连续子序列一定有负的（或0 0）和（否则会包含它们）。）和（否则会包含它们）。在算法二中，当检测出一个负的子序列时，不但可以从内在算法二中，当检测出一个负的子序列时，不但可以从内层循环中跳出来，而且还可以让层循环中跳出来，而且还可以让i i直接增加到直接增加到j+1j+1。如：如：1, -3, 4, -2, -1, 61, -3, 4, -2, -1, 6，当检测序列，当检测序列11，-3-3后，发后，发现是负值，则表示该子序列不可能包含在最大子序列中。现是负值，则表示该子序列不可能包含在最大子序列中。因此，接下去就可以从因此，接下去就可以从4 4开始检测。开始检测。注意还有一种情况，当检测序列注意还有一种情况，当检测序列11，-3-3后，可以确定他不后，可以确定他不在最大子序列中，但在最大子序列中，但1 1仍可能是最大子序列，如果仍可能是最大子序列，如果-3-3后面都后面都是负值。因此在找到新的最大子序列前，必须保存是负值。因此在找到新的最大子序列前，必须保存1 1是最大是最大子序列的事实。子序列的事实。51int maxSubsequenceSum(int a, int size, int &start, int &end) int maxSum = 0, thisSum = 0, startTmp = 0; start = end = 0; for( int j = 0; j size ; j+ ) thisSum += aj; if ( thisSum maxSum ) maxSum = thisSum; start = startTmp; end = j; return maxSum; 牺牲了可读行，换取了时间！52算法分析算法分析时间复杂度的概念时间复杂度的概念 算法运算量的计算算法运算量的计算渐进表示法渐进表示法时间复杂度的计算时间复杂度的计算算法的优化算法的优化空间复杂度的概念空间复杂度的概念 53算法的空间复杂度算法的空间复杂度固定空间需求：与处理的问题规模无关固定空间需求：与处理的问题规模无关可变空间需求：与处理的数据量有关可变空间需求：与处理的数据量有关渐进的空间复杂度：当渐进的空间复杂度：当n-占用的空间量与占用的空间量与n n的关系的关系空间复杂度一般按最坏情况处理空间复杂度一般按最坏情况处理空间复杂度的计算比较简单，表示方法与时间空间复杂度的计算比较简单，表示方法与时间复杂度相同复杂度相同54第一章第一章 引言引言什么是数据结构什么是数据结构算法分析算法分析面向对象的数据结构面向对象的数据结构55过程化的数据结构过程化的数据结构分别介绍每一种数据结构可能的存储方分别介绍每一种数据结构可能的存储方式式(记录），以及在这种存储方式下操作记录），以及在这种存储方式下操作是如何实现的（函数）。是如何实现的（函数）。56面向对象的数据结构面向对象的数据结构面向对象的程序设计方法为程序员提供了创建工具面向对象的程序设计方法为程序员提供了创建工具的功能。的功能。将数据结构的存储和处理过程封装起来做成一个个将数据结构的存储和处理过程封装起来做成一个个工具。工具。数据结构的使用者只需要知道数据结构的逻辑特性，数据结构的使用者只需要知道数据结构的逻辑特性，而不需要知道它的逻辑结构是如何存储的，它的操而不需要知道它的逻辑结构是如何存储的，它的操作是如何实现的。作是如何实现的。学习数据结构不仅需要知道数据结构的存储和处理学习数据结构不仅需要知道数据结构的存储和处理方法，还需要知道如何封装更能适合用户的需求。方法，还需要知道如何封装更能适合用户的需求。本课程采用面向对象的方法。本课程采用面向对象的方法。57数据结构的描述和实现数据结构的描述和实现 数据结构的逻辑特性：每种数据结构用一个数据结构的逻辑特性：每种数据结构用一个抽象类描述，指出该数据结构提供的操作抽象类描述，指出该数据结构提供的操作数据结构的实现：每种数据结构可以有若干数据结构的实现：每种数据结构可以有若干种实现的方法，每种实现就是一个类。种实现的方法，每种实现就是一个类。58数据结构的描述和实现数据结构的描述和实现 续续一致性的保证：每个实现类都必须从对应的抽象一致性的保证：每个实现类都必须从对应的抽象类继承，以保证各种实现有同样的用户接口类继承，以保证各种实现有同样的用户接口泛型程序设计的实现：数据结构关注的是数据元泛型程序设计的实现：数据结构关注的是数据元素之间的关系是如何保存的，数据元素可以是任素之间的关系是如何保存的，数据元素可以是任意类型，必须用泛型程序设计。意类型，必须用泛型程序设计。C+中泛型程序中泛型程序设计的工具是模板。数据结构中的所有类都是类设计的工具是模板。数据结构中的所有类都是类模板模板59总结总结数据结构的基本概念数据结构的基本概念算法的确定比程序设计技巧对程序运行时间的算法的确定比程序设计技巧对程序运行时间的影响更大影响更大大大O O 分析是一种很有效的工具，但它也有局限分析是一种很有效的工具，但它也有局限性。如前所述，它的使用不适合输入规模较小性。如前所述，它的使用不适合输入规模较小的场合。此时，最高项的系数或低次项对运行的场合。此时，最高项的系数或低次项对运行时间的影响较大。时间的影响较大。60作业复习C+程序设计程序设计题1，2（P18）61