数据结构与算法复习资料.doc

此文档收集于网络，如有侵权，请联系网站删除数据结构与算法复习资料何谓数据结构数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。 数据结构主要研究什么？数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。什么是数据结构？什么是逻辑结构和物理结构？数据是指由有限的符号（比如，0和1，具有其自己的结构、操作、和相应的语义）组成的元素的集合。结构是元素之间的关系的集合。通常来说，一个数据结构DS 可以表示为一个二元组：DS=(D,S), /i.e., data-structure=(data-part,logic-structure-part)这里D是数据元素的集合（或者是“结点”，可能还含有“数据项”或“数据域”），S是定义在D（或其他集合）上的关系的集合，S = R | R : DD.，称之为元素的逻辑结构。逻辑结构有四种基本类型：集合结构、线性结构、树状结构和网络结构。表和树是最常用的两种高效数据结构，许多高效的算法可以用这两种数据结构来设计实现。表是线性结构的（全序关系），树(偏序或层次关系)和图（局部有序(weak/local orders)）是非线性结构。数据结构的物理结构是指逻辑结构的存储镜像(image)。数据结构 DS 的物理结构 P 对应于从 DS 的数据元素到存储区M（维护着逻辑结构S）的一个映射：P:(D,S) - M存储器模型：一个存储器 M 是一系列固定大小的存储单元，每个单元 U 有一个唯一的地址 A(U)，该地址被连续地编码。每个单元 U 有一个唯一的后继单元 U=succ(U)。P 的四种基本映射模型：顺序（sequential）、链接（linked）、索引（indexed）和散列（hashing）映射。因此，我们至少可以得到44种可能的物理数据结构： sequential(sets) linkedlists indexedtrees hashgraphs（并不是所有的可能组合都合理） 数据结构DS上的操作：所有的定义在DS上的操作在改变数据元素（节点）或节点的域时必须保持DS的逻辑和物理结构。DS上的基本操作：任何其他对DS的高级操作都可以用这些基本操作来实现。最好将DS和他的所有基本操作看作一个整体称之为模块。我们可以进一步将该模块抽象为数据类型（其中DS的存储结构被表示为私有成员，基本操作被表示为公共方法），称之为ADT。作为ADT，堆栈和队列都是一种特殊的表，他们拥有表的操作的子集。对于DATs的高级操作可以被设计为（不封装的）算法，利用基本操作对DS进行处理。好的和坏的DS：如果一个DS可以通过某种“线性规则”被转化为线性的DS（例如线性表），则称它为好的DS。好的DS通常对应于好的（高效的）算法。这是由计算机的计算能力决定的，因为计算机本质上只能存取逻辑连续的内存单元，因此如何没有线性化的结构逻辑上是不可计算的。比如对一个图进行操作，要访问图的所有结点，则必须按照某种顺序来依次访问所有节点（要形成一个偏序），必须通过某种方式将图固有的非线性结构转化为线性结构才能对图进行操作。树是好的DS它有非常简单而高效的线性化规则，因此可以利用树设计出许多非常高效的算法。树的实现和使用都很简单，但可以解决大量特殊的复杂问题，因此树是实际编程中最重要和最有用的一种数据结构。树的结构本质上有递归的性质每一个叶节点可以被一棵子树所替代，反之亦然。实际上，每一种递归的结构都可以被转化为（或等价于）树形结构。计算机中数据的描述方式我们知道，数据可以用不同的形式进行描述或存储在计算机存储器中。最常见的数据描述方法有：公式化描述、链接描述、间接寻址和模拟指针。 公式化描述借助数学公式来确定元素表中的每个元素分别存储在何处，也就通过公式计算元素的存储器地址。最简单的情形就是把所有元素依次连续存储在一片连续的存储空间中，这就是通常所说的连续线性表，即数组。复杂一点的情形是利用复杂的函数关系根据元素的某些特征来计算元素在内存中的位置，这种技术称为散列技术(Hash，经常音译为哈希技术)。 在链接描述中，元素表中的每个元素可以存储在存储器的不同区域中，每个元素都包含一个指向下一个元素的指针。这就是通常所说的链表。这种描述方法的好处是，知道了第一个元素的位置，就可以依次找到第n个元素的位置，而且在其中插入元素非常方便，缺点是查找某个元素要遍历所有在该元素之前的元素，实际应用中经常和公式化描述结合起来使用。 在间接寻址方式中，元素表中的每个元素也可以存储在存储器的不同区域中，不同的是，此时必须保存一张表，该表的第i项指向元素表中的第i个元素，所以这张表是一个用来存储元素地址的表。指针数组（元素为指针的数组）就是这种描述法的应用。这种描述方法是公式化描述和链接描述的一种折衷方案，同时具有两种描述方法的优点，但是需要额外的内存开销。 模拟指针非常类似于链接描述，区别在于它用整数代替了指针，整数所扮演的角色与指针所扮演的角色完全相同。模拟指针的描述方式是链接描述和公式化描述的结合，元素被存储在不同的区域中，每个元素包含一个指示下一个元素位置的整数，可以通过某种公式由该整数计算出下一个元素的存储器地址。线性表的游标实现就是模拟指针描述法。 算法 Algorithm算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。一个算法应该具有以下五个重要的特征： 1. 有穷性： 一个算法必须保证执行有限步之后结束； 2. 确切性： 算法的每一步骤必须有确切的定义； 3. 输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件； 4. 输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的； 5. 可行性： 算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。 Did you knowAlgorithm 一词的由来Algorithm(算法)一词本身就十分有趣。初看起来，这个词好像是某人打算要写“Logarithm”(对数)一词但却把头四个字母写的前后颠倒了。这个词一直到1957年之前在Websters New World Dictionary(韦氏新世界词典)中还未出现，我们只能找到带有它的古代涵义的较老形式的“Algorism”(算术)，指的是用阿拉伯数字进行算术运算的过程。在中世纪时，珠算家用算盘进行计算，而算术家用算术进行计算。中世纪之后，对这个词的起源已经拿不准了，早期的语言学家试图推断它的来历，认为它是从把algiros(费力的)+arithmos(数字)组合起来派生而成的，但另一些人则不同意这种说法，认为这个词是从“喀斯迪尔国王Algor”派生而来的。最后，数学史学家发现了algorism(算术)一词的真实起源：它来源于著名的Persian Textbook(波斯教科书)的作者的名字Abu Jafar Mohammed ibn Ms al-Khowrizm （约公元前825年）从字面上看，这个名字的意思是“Jafar 的父亲，Mohammed 和 Ms 的儿子，Khowrizm 的本地人”。Khowrizm 是前苏联XBA(基发) 的小城镇 。Al-Khowrizm 写了著名的书Kitab al jabr wal-muqabala (复原和化简的规则)；另一个词，“algebra”(代数)，是从他的书的标题引出来的，尽管这本书实际上根本不是讲代数的。逐渐地，“algorism”的形式和意义就变得面目全非了。如牛津英语字典所说明的，这个词是由于同arithmetic(算术)相混淆而形成的错拼词。由algorism又变成algorithm。一本早期的德文数学词典 Vollstandiges Mathematisches Lexicon (数学大全辞典) ，给出了Algorithmus (算法)一词的如下定义：“在这个名称之下，组合了四种类型的算术计算的概念，即加法、乘法、减法、除法”。拉顶短语algorithmus infinitesimalis (无限小方法) ，在当时就用来表示Leibnitz(莱布尼兹)所发明的以无限小量进行计算的微积分方法。1950年左右，algorithm一词经常地同欧几里德算法(Euclids algorithm)联系在一起。这个算法就是在欧几里德的几何原本(Euclids Elements ,第VII卷，命题i和ii)中所阐述的求两个数的最大公约数的过程(即辗转相除法)。伪代码的使用 Usage of Pseudocode伪代码(Pseudocode)是一种算法描述语言。使用为代码的目的是为了使被描述的算法可以容易地以任何一种编程语言(Pascal, C, Java, etc)实现。因此，伪代码必须结构清晰，代码简单，可读性好，并且类似自然语言。下面介绍一种类Pascal语言的伪代码的语法规则。伪代码的语法规则1. 在伪代码中，每一条指令占一行(else if 例外，)，指令后不跟任何符号（Pascal和C中语句要以分号结尾）； 2. 书写上的“缩进”表示程序中的分支程序结构。这种缩进风格也适用于if-then-else语句。用缩进取代传统Pascal中的begin和end语句来表示程序的块结构可以大大提高代码的清晰性；同一模块的语句有相同的缩进量，次一级模块的语句相对与其父级模块的语句缩进； 例如：line 1 line 2 sub line 1 sub line 2 sub sub line 1 sub sub line 2 sub line 3 line 3 而在Pascal中这种关系用begin和end的嵌套来表示， line 1 line 2 begin sub line 1 sub line 2 begin sub sub line 1 sub sub line 2 end; sub line 3 end; line 3在C中这种关系用 和 的嵌套来表示， line 1 line 2 sub line 1 sub line 2 sub sub line 1 sub sub line 2 sub line 3 line 3 3. 在伪代码中，通常用连续的数字或字母来标示同一即模块中的连续语句，有时也可省略标号。 例如： 1. line 1 2. line 2 a. sub line 1 b. sub line 2 1. sub sub line 1 2. sub sub line 2 c. sub line 3 3. line 34. 符号后的内容表示注释； 5. 在伪代码中，变量名和保留字不区分大小写，这一点和Pascal相同，与C或C+不同； 6. 在伪代码中，变量不需声明，但变量局部于特定过程，不能不加显示的说明就使用全局变量； 7. 赋值语句用符号表示，xexp表示将exp的值赋给x，其中x是一个变量，exp是一个与x同类型的变量或表达式（该表达式的结果与x同类型）；多重赋值ije是将表达式e的值赋给变量i和j，这种表示与je和ie等价。 例如： xy x20*(y+1) xy30以上语句用Pascal分别表示为： x := y; x := 20*(y+1); x := 30; y := 30;以上语句用C分别表示为： x = y; x = 20*(y+1); x = y = 30;8. 选择语句用if-then-else来表示，并且这种if-then-else可以嵌套，与Pascal中的if-then-else没有什么区别。 例如: if (Condition1) then Block 1 else if (Condition2) then Block 2 else Block 3 9. 循环语句有三种：while循环、repeat-until循环和for循环，其语法均与Pascal类似，只是用缩进代替begin - end； 例如： 1. x 0 2. y 0 3. z 0 4. while x N 1. do x x + 1 2. y x + y 3. for t 0 to 10 1. do z ( z + x * y ) / 100 2. repeat 1. y y + 1 2. z z - y 3. until z 0 4. z x * y 5. y y / 2上述语句用Pascal来描述是： x := 0; y := 0; z := 0; while x N do begin x := x + 1; y := x + y; for t := 0 to 10 do begin z := ( z + x * y ) / 100; repeat y := y + 1; z := z - y; until z 0; end; z := x * y; end; y := y / 2;上述语句用C或C+来描述是： x = y = z = 0; while( z N ) x +; y += x; for( t = 0; t = 0 ); z = x * y; y /= 2; 10. 数组元素的存取有数组名后跟“下标”表示。例如Aj指示数组A的第j个元素。符号“ ”用来指示数组中值的范围。 例如：A1j表示含元素A1, A2, , Aj的子数组；11. 复合数据用对象(Object)来表示，对象由属性(attribute)和域(field)构成。域的存取是由域名后接由方括号括住的对象名表示。 例如：数组可被看作是一个对象，其属性有length，表示其中元素的个数，则lengthA就表示数组A中的元素的个数。在表示数组元素和对象属性时都要用方括号，一般来说从上下文可以看出其含义。用于表示一个数组或对象的变量被看作是指向表示数组或对象的数据的一个指针。对于某个对象x的所有域f，赋值yx就使fy=fx，更进一步，若有fx3，则不仅有fx=3，同时有fy=3，换言之，在赋值yx后，x和y指向同一个对象。有时，一个指针不指向任何对象，这时我们赋给他nil。12. 函数和过程语法与Pascal类似。 函数值利用 “return (函数返回值)” 语句来返回，调用方法与Pascal类似；过程用 “call 过程名”语句来调用；例如： 1. x t + 10 2. y sin(x) 3. call CalValue(x,y)参数用按值传递方式传给一个过程：被调用过程接受参数的一份副本，若他对某个参数赋值，则这种变化对发出调用的过程是不可见的。当传递一个对象时，只是拷贝指向该对象的指针，而不拷贝其各个域。算法的复杂性傅清祥 王晓东算法与数据结构 , 电子工业出版社,1998摘要本文介绍了算法的复杂性的概念和衡量方法，并提供了一些计算算法的复杂性的渐近阶的方法。目录 简介 比较两对算法的效率 复杂性的计量 复杂性的渐近性态及其阶 复杂性渐近阶的重要性 算法复杂性渐近阶的分析 递归方程组的渐近阶的求法 1.代入法 2.迭代法 3.套用公式法 4.差分方程法 5.母函数法 简介算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。 计算机的资源，最重要的是时间和空间（即存储器）资源。因而，算法的复杂性有时间复杂性和空间复杂性之分。 不言而喻，对于任意给定的问题，设计出复杂性尽可能地的算法是我们在设计算法是追求的一个重要目标；另一方面，当给定的问题已有多种算法时，选择其中复杂性最低者，是我们在选用算法适应遵循的一个重要准则。因此，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。 关于算法的复杂性，有两个问题要弄清楚： 1. 用怎样的一个量来表达一个算法的复杂性； 2. 对于给定的一个算法，怎样具体计算它的复杂性。 让我们从比较两对具体算法的效率开始。比较两对算法的效率考虑问题1：已知不重复且已经按从小到大排好的m个整数的数组A1.m（为简单起见。还设m=2 k，k是一个确定的非负整数）。对于给定的整数c，要求寻找一个下标i，使得Ai=c；若找不到，则返回一个0。问题1的一个简单的算法是：从头到尾扫描数组A。照此，或者扫到A的第i个分量，经检测满足Ai=c；或者扫到A的最后一个分量，经检测仍不满足Ai=c。我们用一个函数Search来表达这个算法：Function Search (c:integer):integer;Var J:integer; BeginJ:=1; 初始化在还没有到达A的最后一个分量且等于c的分量还没有找到时，查找下一个分量并且进行检测 While (Aic)and(jc，则c只可能在A1,A2,.,Am/2-1之中，因而下一步只要在A1, A2, . ，Am/2-1中继续查找；如果Am/2=L时，继续查找While (not Found) and (U=L) do Begin I:=(U+L) div 2; 找数组的中间分量 If c=AI then Found:=Ture else if cAI then L:=I+1 else U:=I-1; End; If Found then B_Search:=1 else B_Search:=0;End;容易理解，在最坏的情况下最多只要测A中的k+1(k=logm,这里的log以2为底，下同)个分量，就判断c是否在A中。算法Search和B_Search解决的是同一个问题，但在最坏的情况下（所给定的c不在A中），两个算法所需要检测的分量个数却大不相同，前者要m=2 k个，后者只要k+1个。可见算法B_Search比算法Search高效得多。以上例子说明：解同一个问题，算法不同，则计算的工作量也不同，所需的计算时间随之不同，即复杂性不同。上图是运行这两种算法的时间曲线。该图表明，当m适当大（mm0）时，算法B_Search比算法Search省时，而且当m更大时，节省的时间急剧增加。不过，应该指出：用实例的运行时间来度量算法的时间复杂性并不合适，因为这个实例时间与运行该算法的实际计算机性能有关。换句话说，这个实例时间不单纯反映算法的效率而是反映包括运行该算法的计算机在内的综合效率。我们引入算法复杂性的概念是为了比较解决同一个问题的不同算法的效率，而不想去比较运行该算法的计算机的性能。因而，不应该取算法运行的实例时间作为算法复杂性的尺度。我们希望，尽量单纯地反映作为算法精髓的计算方法本身的效率，而且在不实际运行该算法的情况下就能分析出它所需要的时间和空间。复杂性的计量算法的复杂性是算法运行所需要的计算机资源的量，需要的时间资源的量称作时间复杂性，需要的空间（即存储器）资源的量称作空间复杂性。这个量应该集中反映算法中所采用的方法的效率，而从运行该算法的实际计算机中抽象出来。换句话说，这个量应该是只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A来表示算法要解问题的规模、算法的输入和算法本身，用C表示算法的复杂性，那么应该有：C =F(N,I,A)其中F(N,I,A)是N,I,A的一个确定的三元函数。如果把时间复杂性和空间复杂性分开，并分别用T和S来表示，那么应该有：T =T(N,I,A) (2.1)和 S =S(N,I,A) (2.2)通常，我们让A隐含在复杂性函数名当中，因而将（2.1）和（2.2）分别简写为T =T(N,I)和 S =S(N,I)由于时间复杂性和空间复杂性概念类同，计算方法相似，且空间复杂性分析相对地简单些，所以下文将主要地讨论时间复杂性。下面以T(N,I)为例，将复杂性函数具体化。根据T(N,I)的概念，它应该是算法在一台抽象的计算机上运行所需的时间。设此抽象的计算机所提供的元运算有k种，他们分别记为O1,O2 ,.,Ok；再设这些元运算每执行一次所需要的时间分别为t1,t2,.,tk 。对于给定的算法A，设经过统计，用到元运算Oi的次数为ei，i=1,2,.,k ，很明显，对于每一个i，1=ima+2mt=(a+2t)m ，于是 Tmax(m)=(m)。我们同样要指出，用评估算法的复杂性，得到的只是该复杂性的一个下界。这个下界的阶越高，则评估就越精确，结果就越有价值。再则，这里的只对问题的一个算法而言。如果它是对一个问题的所有算法或某类算法而言，即对于一个问题和任意给定的充分大的规模N，下界在该问题的所有算法或某类算法的复杂性中取，那么它将更有意义。这时得到的相应下界，我们称之为问题的下界或某类算法的下界。它常常与配合以证明某问题的一个特定算法是该问题的最优算法或该问题在某算法类中的最优算法。明白了记号和之后，记号将随之清楚，因为我们定义f(N)=(g(N)则f(N)=(g(N) 且f(N)=(g(N)。这时，我们说f(N)与g(N)同阶。比如，对于算法Search在最坏情况下的时间复杂性Tmax(m)。已有Tmax(m)=(m)和Tmax(m)=(m)，所以有Tmax(m)=(m)，这是对Tmax(m)的阶的精确估计。最后，如果对于任意给定的0，都存在非负整数N0，使得当NN0时有f(N)g(N)，则称函数f(N)当N充分大时比g(N)低阶，记为f(N)= o(g(N)，例如：4NlogN +7=o(3N 2+4NlogN+7)；而f(N)=(g(N)定义为g(N)=o(f(N)。即当N充分大时f(N)的阶比g(N)高。我们看到o对于有如对于。复杂性渐近阶的重要性计算机的设计和制造技术在突飞猛进，一代又一代的计算机的计算速度和存储容量在直线增长。有的人因此认为不必要再去苦苦地追求高效率的算法，从而不必要再去无谓地进行复杂性的分析。他们以为低效的算法可以由高速的计算机来弥补，以为在可接受的一定时间内用低效的算法完不成的任务，只要移植到高速的计算机上就能完成。这是一种错觉。造成这种错觉的原因是他们没看到：随着经济的发展、社会的进步、科学研究的深入，要求计算机解决的问题越来越复杂、规模越来越大，也呈线性增长之势；而问题复杂程度和规模的线性增长导致的时耗的增长和空间需求的增长，对低效算法来说，都是超线性的，决非计算机速度和容量的线性增长带来的时耗减少和存储空间的扩大所能抵销。事实上，我们只要对效率上有代表性的几个档次的算法作些简单的分析对比就能明白这一点。我们还是以时间效率为例。设A1,A2,和A6。是求解同一间题的6个不同的算法，它们的渐近时间复杂性分别为N，NlogN，N 2，N 3，2N，N!。让这六种算法各在C1和C2两台计算机上运行，并设计算机C2的计算速度是计算机C1的10倍。在可接受的一段时间内，设在C1上算法Ai可能求解的问题的规模为N1i，而在C2上可能求解的问题的规模为N2i，那么，我们就应该有Ti(N2i)=10Ti(N1i)，其中Ti(N)是算法Ai渐近的时间复杂性，i=1,2,6。分别解出N2i和N1i的关系，可列成下表：表4-1算法与渐近时间复杂性的关系算法渐进时间复杂性T(N)在C1上可解的规模N1在C2上可解的规模N2N1和N2的关系A1NN11N21N21=10N11A2NlogNN12N22N2210N12A3N2N13N23A4N3N14N24A52NN15N25N25 =N15+log10A6N!N16N26N26 =N16+小的常数从表4-1的最后一列可以清楚地看到，对于高效的算法A1，计算机的计算速度增长10倍，可求解的规模同步增长10倍；对于A2，可求解的问题的规模的增长与计算机的计算速度的增长接近同步；但对于低效的算法A3，情况就大不相同，计算机的计算速度增长1