算法与数据结构基础

大学计算机湖南工业大学计算机与通信学院湖南工业大学计算机公共基础课程系列第6章算法与数据结构基础湖南工业大学计算机与通信学院湖南工业大学《大学计算机》学习目标1、理解算法的基本概念及特性2、掌握算法的三大结构并了解其描述方法3、结合实例理解算法设计方法：穷举法、回溯法、递归法、分治法、贪心法以及动态规划4、认识数据结构研究的三大内容5、了解程序设计概念，了解程序设计语言的发展及分类重点难点1．重点 （1）算法的概念与特性 （2）算法的三大结构并了解其描述方法

（3）掌握算法设计方法

（4）数据结构的基本概念2．难点结合实例掌握算法设计方法6.1 算法的概念目录6.2 算法策略6.3算法设计与数据结构6.4本章小结61974年图灵奖获得者DonaldErvinKnuth:计算机科学就是算法的研究TheArtofComputerProgramming6.1算法的概念算法（Algorithm）是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算，是对解题方案的准确与完整的描述。算法是一种解决问题的方法，是数学及其应用的重要组成部分。

6.1.2算法的特性算法的一般应包含以下特性：（1）有穷性。（2）确定性。（3）可行性。（4）输入。（5）输出。6.1.3算法与计算机程序计算机输入输出算法问题算法与计算机之间的关系在计算机科学中，算法要用计算机算法语言描述，算法代表用计算机解一类问题的精确、有效的方法。算法+数据结构=计算机程序6.1.4算法的控制结构与描述1、算法的控制结构 算法中各操作之间的执行顺序称之为算法的控制结构。 算法一般都可以用顺序结构、分支结构、循环结构三种基本控制结构组合而成。10（1）、自然语言自然语言是人们日常进行交流的语言，如汉语、英语等优点：通俗易懂，即使没有学过算法也能看懂算法执行缺点：不够严谨，容易出现歧义和错误2、算法的描述（2）、流程图 用图直观地描述一个工作过程的具体步骤

常用来描述算法的图形工具有：流程图或程序框图、N-S图和PAD图。

优点：直观形象，简洁明了。

缺点：画起来费事，不易修改。常用的流程图符号：（3）伪代码6.1.5算法的设计要求

1、正确性。2、可读性。3、高效率与低存储量。

6.2算法策略6.2.1穷举法问题1：有一把锁和一串钥匙（共有10把钥匙），怎样找出所有开这把锁的钥匙？ 穷举法又称列举法、枚举法，是蛮力策略的具体体现，是一种简单而直接地解决问题的方法。其基本思想是逐一列举问题所涉及的所有情形，并根据问题提出的条件检验哪些是问题的解，哪些应予排除。

穷举法的特点是算法设计比较简单，解的可能为有限种，一一列举问题所涉及的所有情形。 例如： 在QQ上，OicqPassOver这个工具穷举用户的口令，它根据机器性能最高可以每秒测试20000个口令，如果口令简单，一分钟内，密码就会遭到破译。

穷举法运用于一些经典问题1、百钱百鸡问题 中国古代算书张丘建的《算经》中有一道著名的百鸡问题：公鸡每只值5文钱，母鸡每只值3文钱，而3只小鸡值1文钱。现在用100文钱买100只鸡，问：这100只鸡中，公鸡、母鸡和小鸡各有多少只？ 这个问题流传很广，解法很多，但从现代数学观点来看，实际上是一个求不定方程整数解的问题。解法如下：设公鸡、母鸡、小鸡分别为x、y、z只，由题意得：

用穷举法求解，对每组求得满足等式方程组的值，从而找到百钱百鸡的解。用穷举算法解决问题，通常可以从两个方面进行分析： 1、问题所涉及的情况：问题所涉及的情况有哪些，情况的种数可不可以确定。把它描述出来。 2、答案需要满足的条件：分析出来的这些情况，需要满足什么条件，才成为问题的答案，把这些条件描述出来。由于穷举法穷举的数据量过大，效率较低，对于小规模的问题还是适用的，但是问题规模一旦扩大，穷举法就没有什么可取性了。一般巧妙和高效算法很少来自穷举法。6.2.2回溯法

迷宫游戏

回溯算法也叫试探法，是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

回溯法的指导思想：走不通，就掉头 回溯法在搜索过程中通过对约束条件的判定，排除错误答案，提高了搜索效率。网络爬虫网络爬虫是一个功能强大的自动提取网页的程序，它为搜索引擎从万维网下载网页，是搜索引擎的重要组成部分。它可以完全不依赖用户干预实现网络上的自动“爬行”和搜索。网络爬虫是通过网页的链接地址来寻找网页在抓取网页的时候，网络爬虫采用了深度优先策略，深度优先是指网络爬虫会从起始页开始，一个链接一个链接跟踪下去，处理完这条线路之后再转入下一个起始页，继续跟踪链接。这个方法有个优点是网络爬虫在设计的时候比较容易。这是一种典型的回溯算法。回溯法的本质也是一种穷举法，但与穷举法相比，回溯法的“聪明”之处在于能适时“回头”，若再往前走不可能得到解，就回溯，退一步另找线路，这样可省去大量的无效操作。因此，回溯与穷举相比，回溯更适宜于量比较大，候选解比较多的问题。6.2.3递归法人们都熟悉一个民间故事：从前有一座山，山上有一座庙，庙里有一个老和尚正在给小和尚讲故事，故事里说，从前有一座山，山上有一座庙，庙里有一个老和尚正在给小和尚讲故事，故事里说……。

所谓递归就是一个函数或过程可以直接或间接地调用自己。递归分为直接递归和间接递归两种方法。如果一个算法直接调用自己，称为直接递归调用；如果一个算法A调用另一个算法B，而算法B又调用算法A，则此种递归称为间接递归调用。德罗斯特效应

1、n！问题

阶乘可以这样递归地定义成函数：

这样，所有自然数的阶乘就可以通过上面的两句话表示了。2的阶乘就是1×2；3的阶乘就是2的阶乘乘3，即1×2×3……不仅如此，人们还可以知道0的阶乘是多少，1的阶乘应该等于0的阶乘乘以1，显然0的阶乘必须是1才行。2、汉诺塔（Hanoi）问题

相传印度有座大寺庙，它曾被认为是宇宙的中心。神庙中放置了一块上面插有三根长木钉的木板，在其中的一根木钉上，由上至下放了64片直径由小至大的圆环形金属片。古印度教的天神指示他的僧侣们将64片金属片全部移至另一根木钉上。移动规则只有两个： （1）在每次的移动中，只能移动一片金属片； （2）过程中任意时刻必须保证金属片小的在上，大的在下。 使用递归时必须符合以下三个条件： （1）可将一个问题转化为一个新的问题，而新问题的解决方法仍与原问题的解法相同，只不过所处理的对象有所不同而已，即它们只是有规律的递增或递减。（2）可以通过转化过程使问题回到对原问题的求解。（3）必须要有一个明确的结束递归的条件，否则递归会无止境地进行下去。递归对某些问题而言存在重复调用，导致算法效率不高。6.2.4分治法分治法的设计思想是将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。分治法所能解决的问题一般具有以下几个特征：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。1、找出伪币一个装有16枚硬币的袋子，16枚硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这枚伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，比如天平。利用这台仪器，可以知道两组硬币的重量是否相同。

方法1任意取1枚硬币，与其他硬币进行比较，若发现轻者，这那枚为伪币。最多可能有15次比较。方法2将硬币分为8组，每组2个，每组比较一次，若发现轻的，则为伪币。最多可能有8次比较。方法3分析上述三种方法,分别需要比较18次,8次,4次,那么形成比较次数差异的根据原因在哪里?方法1:每枚硬币都至少进行了一次比较,而有一枚硬币进行了15次比较方法2:每一枚硬币只进行了一次比较方法3:将硬币分为两组后一次比较可以将硬币的范围缩小到了原来的一半,这样充分地利用了只有1枚伪币的基本性质。根据以上比较，第三种方法就是分治法，可以得到以下的采用分治方法的结论：1、参与比较的硬币数量越多，使用该方法来实现就越快，而且投机性大大减少；2、解决方法关键在于能将大问题分割成若干小问题；3、小问题与原有问题是完全类似的。2、二分法二分查找又称为折半查找，是一种可在有序顺序表上实现的效率比较高的查找算法。是一个典型的分治算法。牛顿二分法二分法查找分治法所能解决的问题一般具有以下几个特征：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。思考：求解一元二次方程实根6.2.5贪心法贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它能产生整体最优解或者是整体最优解的近似解。只顾眼前利益，每次都选最好的1、商场找零 假设只有3种面额的币值，它们的面值分别为20元、10元、5元、和1元。现要找给某顾客37元，这时，售货员几乎不假思索地拿出1个20元、1个l0元、1个5元和2个1元的钱币交给顾客。人们不仅能很快决定要拿哪些钱币，而且与其它找法相比．这时拿出的钱币的个数肯定是最少的。在这里，收货员实际使用了这样的算法：首先选出一个面值不超过37元的最大面额钱币（20元），然后从37元中减去20元，剩下17元中再选出一个不超过17元的最大面额钱币（10元），如此做下去，直到找足37元。这就是所谓的贪心法。2、最短距离

Dijkstra算法又称为单源最短路径，所谓单源是在一个有向图中，从一个顶点出发，求该顶点至所有可到达顶点的最短路径问题。

Dijstra算法是运用贪心的策略，从源点开始，不断地通过相联通的点找出到其他点的最短距离

基本思想是：

设置一个顶点的集合s，并不断地扩充这个集合，一个顶点属于集合s当且仅当从源点到该点的路径已求出。开始时s中仅有源点，并且调整非s中点的最短路径长度，找当前最短路径点，将其加入到集合s，直到终点在s中。贪心法主要有以下两个特点：（1）贪心选择性质：算法中每一步选择都是当前看似最佳的选择，这种选择依赖于已做出的选择，但不依赖于未作出的选择。（2）最优子结构性质：算法中每一次都取得了最优解（即局部最优解），要保证最后的结果最优，则必须满足全局最优解包含局部最优解。6.2.6动态规划

动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。 20世纪50年代美国数学家贝尔曼（RechardBellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优性原理，把多阶段决策过程转化为一系列单阶段问题逐个求解，创立了解决多阶段过程优化问题的新方法——动态规划。动态规划所处理的对象是多阶段决策问题。多阶段决策问题，是指这样的一类特殊的活动过程，问题可以分解成若干相互联系的阶段，在每一个阶段都要做出决策，形成一个决策序列，该决策序列也称为一个策略。1、最短距离

Dijkstra算法又称为单源最短路径，所谓单源是在一个有向图中，从一个顶点出发，求该顶点至所有可到达顶点的最短路径问题。

基本