《精品 数据结构讲义第一章 绪 论.doc》由会员分享，可在线阅读，更多相关《精品 数据结构讲义第一章 绪 论.doc（20页珍藏版）》请在三一文库上搜索。
1、第一章 绪 论1.1 为什么要学习数据结构1.2 数据结构概念历史定义1.1数据是指对象的表示，即按照适合于通信、解释或处理（借助人或自动装置）的方式所形成的关于事实、概念或指令的表示；数据只是表示，而无含义3。数据是计算机科学与技术中最基本的概念，它是计算机程序要处理的“原料”，是所有被计算机识别、存储和加工处理的符号的总称4,5。元素、结点或顶点，数据项（也称为域或字段） 数据元素（或曰数据成分）还可被称为元素、结点或顶点等。数据元素可大可小，大到可以是一篇文稿、一本书，小到可以是一个字符，甚至是计算机二进制数中的一位。数据元素可由若干个数据项（也称为域或字段）组成。例1.1 如表1.1所
2、示的通讯录表，行表示一个结点（数据元素），每个结点由姓名、区号、办公电话和手机四个域（数据项）组成。表1.1 通讯录表姓名区号办公电话手机赵一0105364458713911001234钱二0208963415913809771333孙三0214597652813916586666李四0246342754113804076111 定义1.2 数据结构由若干数据成分按照一定方式构成的复合数据以及作用于其上的函数或运算。数据成分及其间的数据约束关系合称为数据结构的逻辑结构。数据结构从数学上可用适当的数学结构以及其上的函数变换统一地定义。但迄今为止，关于数据结构之定义在计算机科学技术界还未取得完全认
3、同。有些学者认为数据结构应由数据的逻辑结构、数据的存储结构及其运算三部分组成。一个逻辑结构可形式定义为一个二元组5：L = (N, R)，其中，N是结点的有限集合，R 是定义在集合N上的二元关系r的集合。设 L=(N, R) 是一个逻辑结构. r1R是与线性结构、树结构和二叉树结构对应的一种关系，若a，bN，且 (a，b) r1，则称 a是b的前驱结点，b是a的后继结点，a和b是相邻结点；若不存在aN使得 (a，b) r1，则称 b 为始结点；若不存在 bN 使得(a，b) r1，则称 a 为终结点. r2R是与图结构对应的一种关系，若a，bN，且关系 (a，b) r2，则称a和b是相邻结点;
4、对于有向图结构，若存在(a，b) r2，则称a是b的前驱结点，b是a的后继结点。数据的存储结构（或曰物理结构）1.2.3 对数据结构的操作插入、删除、修改、排序、查找1.3 算 法定义1.49 一个算法就是给出求解特定类型问题之运算序列的一个有穷规则集合，一个算法应具有5个重要特征：1) 有限性：一个算法在执行有限步骤后必然终止；2) 确定性：对一个算法的每个步骤都必须给出精确的定义；对要执行的动作都必须给出针对每种情况的严格、无歧义的描述；3) 输入：一个算法有0个或多个输入；4) 输出：算法有1个或多个输出；5) 可行性：算法中的所有操作都必须是充分基本的，因而原则上人们用纸和笔都可在有限
5、时间内精确地完成它们。1.3.2 算法的描述ADL语言例1.3 欧几里得算法E9-10 算法E ( m , n . n )/* 给定两个正整数m和n，算法E求它们的最大公因子（即能同时整除m和n的最大正整数），输出结果在n中 */E1. 求余数 r m - m/n n . / 有0 r N . 与 N 是最大整数矛盾。(3) 肯定原来的结论：因此，没有最大的整数。证毕。2. 数学归纳法证明算法正确性的一般方法是数学归纳法。设THM是一个定理， n是THM中的正参数. 数学归纳法表明，如果下面两个条件为真，则对于参数n的任何值，THM都是正确的：(1) 基础归纳：n = c 时，THM成立。(2
6、) 归纳步骤：如果n = k - 1 时THM 成立，则n = k 时THM也成立。其中，c是一个较小的常量，n c . 通常，证明初始归纳很容易，而证明归纳步骤很难。以上是一般意义下的数学归纳法，而强归纳法在归纳步骤上有所变化： (2) 归纳步骤：如果对于所有的k ( c k 1 .证明：(1) 基础归纳：n =1 时，T ( 1 ) = 1 - 1 = 0，结论成立。(2) 归纳步骤：假设 T ( n - 1 ) = n - 2 成立 （归纳假设）要证明T ( n ) = n - 1 成立。由递归定义可知：n 1 时，有T ( n ) = T ( n - 1 ) + 1 由归纳假设：T (
7、 n ) = T ( n - 1 ) + 1 = n - 2 + 1 = n - 1所以，由数学归纳法推出T ( n ) = n - 1成立。证毕。对于一个算法，证明其正确性是必要的。如果算法比较复杂，至少应该给出其关键步骤的正确性证明。目前，算法或程序的正确性证明仍然是计算机科学领域中具有挑战性的重要研究课题。1.5 算法分析基础1.5.1 算法时间复杂性的分析方法分析算法的时间复杂性需要分析算法的基本运算次数。基本运算是指算法运行过程中起主要作用且花费最多时间的运算。例1.7 A是一个含有n个不同元素的实数数组，给出求A之最大和最小元素的算法。算法SM( A , n . max , min
8、 )/ 求实数数组An的最大和最小元素( max和min ) .SM1. 初始化maxminA1. SM2. 比较FOR i = 2 to n DO（IF Ai max THEN maxAi. IF Ai min THEN minAi）对算法SM 进行分析，容易看出算法SM 对大小为的 n 的数组 A 需要 2(n -1) 次元素比较，如果规定算法SM的基本运算是元素比较，那么算法SM 的基本运算的次数，即时间复杂性为2(n-1) .一般情况下，计算一个算法的基本运算次数是相当困难的，甚至是不可能的（因为一个算法的不同输入往往产生不同的运算次数，而一个算法的所有不同输入的数目可能十分庞大）。一
9、种可行的方法是计算算法的平均运算次数。这样的结果在实际中可能不是特别有用，因为某些输入较之其它的输入可能更经常出现，所以对数目足够的不同输入的加权平均将会给出更有意义的结果。通常在最好、最坏和平均三种情况下，讨论算法的时间复杂性。定义1.5 设一个领域问题的输入规模为n，Dn是该领域问题的所有输入的集合，任一输入IDn，T(I)是（解决该领域问题的）算法在输入I下所执行的基本运算次数，P(I)是I出现的频率，该算法的最好情况下的复杂性为：该算法的最坏情况下的复杂性为：该算法的平均情况下的复杂性，或期望复杂性为：例1.8 实数数组R由 n 个元素组成，给定一个实数K，试确定K是否是R的元素。算法
10、F（R , n , K . i）/*给定一具有n 个元素的实数数组R，判断实数K是否在R中出现，若是，1 i n；否则，i= n+1 .*/F1. 初始化i1.F2. 比较WHILE i n DO（ IF Ri = K THEN RETURN. i i+1） 算法F的运行结果：如果1 i n，则表示 K 是 R 的元素；反之，K 不是 R 的元素。规定算法F 的基本运算为 R 中元素与 K 的比较，假定 q 表示 K 是 R 中元素的概率，又假定 K 等于 R 的每个元素有相同的概率。令 Dn = I1, I2, In, In+1，其中 Ii (1 i n) 表示 K等于 Ri 的任一输入，I
11、n+1 表示 K 不是 R 中元素的任一输入。由上述说明我们有：当1 i n时， P(Ii) = q/n, T(Ii) = i, P(In+1) = 1-q, T(In+1) = n . 算法F的期望复杂性为：如果已知K在R中，即q = 1，则我们有由算法F我们很容易看出，该算法的最坏情况下的时间复杂性为算法F的最好情况下的时间复杂性为Flash动画课件115网盘用户名：2010datastructu密码：forsuccess2010例1.9 算法SM的改进算法BS .算法BS( A, i, j . fmax, fmin )/ 在数组A的第i个元素到第j个元素之间寻找最大和最小元素，已知i j
12、 .BS1. 递归出口IF i = j THEN ( fmaxfminAi. RETURN. )IF i = j - 1 THEN( IF Ai Aj THEN (fmaxAj. fminAi.) ELSE (fmaxAi. fminAj.) RETURN.）BS2. 取中值 mid(i+j) / 2 .BS3. 递归调用BS(A, i, mid . gmax, gmin) .BS(A, mid+1, j . hmax, hmin) .BS4. 合并 fmaxmaxgmax, hmax . fminmingmin, hmin . 如果规定算法BS的基本运算亦为元素的比较，则容易看出算法BS对不
13、同的输入Ai到A j，只要元素个数相同都有相同的基本运算次数。设T(n)表示算法BS的基本运算次数，其中，n = j - i + 1，根据算法BS的递归过程，我们有如下的递归表达式：在上式中，当n是2的幂时（即存在正整数k，使得n = 2k）我们有由上面几个例子可以看出，分析算法时，通常用数学方法将算法的复杂性表示为输入规模n 的函数。1.5.2 复杂性函数的渐近表示在大多情况下，特别当输入规模n较大时，难于确定一个算法的基本运算次数T，即得到T和n间的函数关系。所以，算法分析中通常采用大O、大W和大Q表示法来渐近表示算法的基本运算次数8, 11, 12, 13, 14。(1) 大O表示法18
14、92年，Paul Bachmann在解析数论一书中引进了“大O”记号9，主要用于估计函数的增长速率。定义1.6 设 f(n)和g(n)是正整数集到正实数集上的函数，称f(n)是O(g(n) 当且仅当存在正常数C和n0，使得对任意的n n0，有f(n) Cg(n)，记为f(n) = O(g(n) .设f(n) = O(g(n)，f和g之间的关系可以描述为“f(n)的阶至多为 g(n)”或“f至多与g增长得一样快”。一个算法的时间复杂性为O(g(n)，表明它的基本运算次数至多是g(n)的某个常数倍. O(1)表示算法的时间复杂性为一常数。O(n)、O(n2)、O(n3)、O(nm)和O(2n)分别
15、表示算法的时间复杂性为线性阶的、平方阶的、立方阶的、多项式阶的和指数阶的，其中m 1，且m为常数。例1.10 若f (n) = 3 n -2，证明：f (n) = O(n) .证明：存在C = 3，n0 = 1，使得对任意的n n0，有3 n - 2 3 n，即 f(n) C n . 由大O的定义，f (n) = O(n) . 证毕。例1.11 若 f (n) = 3log n + loglog n，证明：f (n) = O (logn) .证明： 存在C = 4，n0 = 2，使得对任意的 n n0，有3 log n + loglog n 4 logn，即f(n) C logn . 由大O的
16、定义，f (n) = O (logn) . 证毕。定理1.1 若A(n) = am nm + + a1 n + a0是关于n的m次多项式，则A(n) = O(nm) 根据算法的时间复杂性，人们常常把算法分成两类。凡可用多项式来对其时间复杂性限界的算法，被称为多项式阶算法，而时间复杂性需用指数限界的算法被称为指数阶算法。当n很大时，可以证明有如下关系：1 log2log2 n log2 n n nlog2n n2 n3 2n从而有：O(1) O(log2log2 n) O(log2 n) O(n) O(nlog2n) O(n2) O(n3) O(2n)易证，当n很大时，指数函数的值远大于对数函数
17、、幂函数及它们的组合函数的值，也就是说，指数阶算法的执行时间远远大于多项式阶算法的执行时间。由定义1.6和式（1.1），可以证明T(n) = O(n) . 虽然算法SM和算法BS的时间复杂性均为线性阶，但因 ，故就计算时间而言，算法BS优于算法SM . 然而算法BS是递归算法，因此其实现需要额外的辅助空间。那么算法BS和算法SM谁更优呢？为此，我们将在下一小节给出另一个评判标准。(2) 大W表示法和大Q表示法定义1.7 设f(n)和g(n)是正整数集到正实数集上的函数，称f(n)是W(f(n)，当且仅当存在正常数C和n0，使得对任意的n n0，有f(n) Cg(n)，记为f(n) = W (g
18、(n) . 设f(n) =W( g(n)，f和g之间的关系可以描述为“f(n) 的阶至少为 g(n)”或“f的增长速率将不会低于g”.例1.12若f(n) = 3log n + loglog n，证明：f (n) = W (logn) .证明：存在C = 3，n0 = 2，使得对任意的 n n0，有3log n + loglogn 3log n，即 f(n) C log n . 由大W的定义，f (n) = W (logn) . 证毕。定义1.8设 f(n)和g(n)是正整数集到正实数集上的函数，称f(n)是Q(g(n)，当且仅当存在正常数 C1, C2和n0，使得对于所有的n n0，有C1
19、g(n) f(n) C2 g(n) ，记为f(n) = Q (g(n) .设f(n) =Q( g(n)，f和g之间的关系可以描述为“g(n) 和 f(n) 的阶数相同”或“f和g会以相同的速率增长”。例1.13 若f(n) = 3log n + loglog n，证明：f (n) = Q (logn) .证明：由例1.11和例1.12可得：3 log n 3 log n + loglog n 4 logn，即 3 log n f(n) 4 logn .由大Q的定义，f (n) = Q (logn) . 证毕。大O和大W分别提供了一种表达上界和下界的方法，而大Q则提供了一种同时表达上界和下界的方
20、法12。对于函数f，可能有无穷多个上界，即无穷多个g使得 f(n) = O(g(n)；也可能有无穷多个下界，即无穷多个h使得 f(n) = W (h(n) . 通常，在分析算法的时间复杂性时，总是试图找出算法的时间复杂性 f(n) 的最小上界和最大下界。可以看出，如果f(n) = O(g(n)且f(n) = W (g(n)，则f(n) = Q (g(n) . 一个算法的时间复杂性 f(n) = Q(g(n)，意味着该算法在最好和最坏情况下的时间复杂性在一个常数因子的范围内是相同的。不是对所有算法时间复杂性的估计都存在Q表达式。对于有些算法，尽管可以分别估计其上界和下界，但无法找到一个共同的f(
21、n)作为其上下界的共同渐进表示，因此，这些算法的时间复杂性不存在大Q估计表达式。1.5.3 算法时间与空间分析前面我们讨论了算法时间复杂性的分析方法。通常，一个算法的优劣不仅取决于算法的时间复杂性，而且也与算法的空间占用量有关。对于一个算法而言，在不同的执行时间内，它所占用的内存空间量不一定相等，也就是说，占用空间量是时间的函数，即. 我们称积分为该算法的时空积分，其中是该算法的执行时间。807060302010yx时空效率图1.2 时空分布示意图例1.14 一个算法执行时间为30秒，前10秒占用60个字节，第二个10秒占用70个字节，最后10秒占用80个字节。该算法的时空分布如图1.2所示。
22、显然算法的时空积分为60*10+70*10+80*10=2100（字节秒）基于时空积分，我们可以对算法SM和算法BS进行比较，时空积分较小的算法是较优的算法。图1.3 算法SM与算法BS的时空积分比较图(b) 算法BS的时空图(a) 算法SM的时空图L算法所需空间SyTxSM比BS多用的时间算法所需空间SyTxBBS比SM多占用的空间图1.3说明，算法SM的计算时间为L，占用空间为S；算法BS的计算时间为T(T S).结论，若规定数组元素的比较为基本运算，则当数组元素个数达到一定数目时，算法BS优于算法SM .知识点：1. 数据，2. 元素、结点或顶点，3. 数据项（也称为域或字段）4. 数据结构，5. 算法，6. 算法5个特征，7. 算法描述，8. 算法评价，9. 算法正确性证明，10. 算法分析基础（期望复杂性），11. 复杂性函数的渐近表示，（大O是重点）12. 算法时间与空间分析（了解）