可视化计算》算法综合-加工了的.ppt

基本算法和策略,西安交大可视化计算,学习目标,程序与算法有哪些异同? 算法有哪些基本特性？ 算法的效率如何度量？ 如何为算法设计做准备？,2,,算法定义,算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。 通俗来说，就是通过计算来解决问题的过程，在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法 不同的是：前者是推理实现的算法，后者是操作实现的算法 所以，程序是使用计算机实现的算法；而算法则不一定需要有计算机才能实现,3,,算法的特性,算法具有五个基本特性： 输入（具有零个或多个输入） 输出（一或多个输出） 有穷性（自动结束而不会出现无限循环） 确定性（每一步骤的含义，不会出现二义性） 可行性（能够通过执行有限次数完成）,4,,算法设计的要求,正确性 可读性 健壮性 时间效率高 存储量需求低,5,,正确性的层次,算法程序没有语法错误; 算法程序对于合法的输入数据能够产生满足要求的输出结果; 算法程序对于非法的输入数据能够得出满足规格说明的结果; 算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果。,6,,可读性,为了便于阅读、理解和交流，可读性要素： 增加算法文件名、子图、子程序、算法样本数据文件名的可读性； 在算法语句中增加注释语句，说明重要变量、决策语句的用途； 将算法有关的文档整理在一个目录中,7,,健壮性,能对输入数据不合法的情况做合适的处理 比如输入的时间或者距离不应该是负数 算法的健壮性表现在当输入数据不合法时，算法也能做出相关处理，而不是产生异常或无法解释的结果,8,,时间效率高和存储量需求低,对于同一个问题，如果有多个算法能够达到同样的问题解决标准，执行时间最短的算法效率最高 存储量需求指的是算法在执行过程中需要的最大存储空间，主要指算法程序运行时所占用的内存或外部硬盘存储空间，越少越好,9,,算法效率的度量,一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素： 编译产生的代码质量； 算法采用的策略、方法； 问题的输入规模； 机器执行指令的速度。,10,,2-end,学习目标,什么是基本算法？ 哪些算法在计算问题求解中最为常用？ 算法与算法策略有何区别？ 哪些基本的算法策略在各种算法解决方案中被普遍采用?,12,,基本算法,蛮力法 分段函数 递推法 模运算 字符和字符串运算 递归 组合计算 迭代法,13,,蛮力法,计算机问题求解的第一号方法被称为蛮力法(Brute Force) ，也称穷举法 采用蛮力算法解题的基本思路： 确定穷举对象、穷举范围和判定条件； 一一穷举可能的解，验证是否是问题的解 在蛮力算法中，穷举对象的选择也是非常重要的，它直接影响着算法的时间复杂度，选择适当的穷举对象可以获得更高的效率,14,,百钱买百鸡问题,某个人有一百块钱，打算买一百只鸡。到市场上一看，公鸡五块钱一只，母鸡三块钱一只，小鸡一块钱三只。现在，请编一个算法，算出如何能刚好用一百块钱买一百只鸡?,15,,蛮力法求解,三种鸡的个数为穷举对象 分别设为x，y，z 以三种鸡的总数（x+y+z）和买鸡用去的钱的总数(x*5+y*3+z/3)为判定条件，穷举各种鸡的个数 由于三种鸡的和是固定的，只要穷举二种鸡（x，y），第三种鸡就可以根据约束条件求得（z=100-x-y），这样就缩小了穷举范围,16,,求解流程图,如果需要解决的问题规模不大 用蛮力法设计的算法其速度是可以接受的,17,,分段函数,收费问题与我们的生活息息相关，如水费问题、电费问题、话费问题等 这些收费问题往往根据不同的用量，采用不同的收费方式 以收费为题材的数学问题多以分段函数的形式出现,18,,阶梯电价问题,为鼓励节约用电，某市开始采取按月用电量分段收费办法，某户居民每月应交电费y（元）与用电量x（度）的函数如下： 请设计上述电费的收费算法。,19,,阶梯电价流程图,20,,分段函数求解中的问题,最常见的错误的是将函数的数学表达式直接搬到算法中，例如：“0=x=100”； 函数定义中，没有定义x0，也就是输入为负数的时候，如何处理。当然，可以实验一下，当x取负值时结果如何？ 这个算法没有设计输入和规范的输出界面，例如输入的提示，输出内容的量纲等,21,,递推法,递推法是利用问题本身所具有的一种递推关系求解问题的一种方法 所谓递推，是指从已知的初始条件出发，依据某种递推关系，逐次推出所要求的各中间结果及最后结果 其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简后确定,22,,可递推求解的问题特点,该类题目一般有以下二个特点： 问题可以划分成多个状态； 除初始状态外，其它各个状态都可以用固定的递推关系式来表示 在实际解题中，该类题目一般不会直接给出递推关系式，而是需要通过分析各种状态，找出递推关系式,23,,猴子吃桃问题,小猴子摘桃若干，立即吃了一半还觉得不过瘾，又多吃了一个； 第二天接着吃剩下桃子的一半，仍觉得不过瘾又多吃了一个，以后小猴子都是吃剩下的桃子一半多一个； 到第10天小猴子再去吃桃子的时候，看到只剩下一个桃子； 则小猴子第一天共摘了多少桃子？,24,,递推问题求解,由题意可以得到下表： 分析后可知，猴子吃桃问题递推关系为： Sn=1 （当n=10时） Sn =2（Sn+1+1）（当1n10时） 在此基础上，以第10天的桃数作为基数，用以上归纳出来的递推关系设计出一个循环过程，将第1天的桃数推算出来,25,,递推流程图,为了加强交互性，增加了交互界面，可以输入不同的天数进行递推 算法使用了两个变量，一个用于递推的循环控制，另一个保存递推得到的结果 注意主要的循环控制变量是递减的，与题意设计完全相同，便于理解。 算法中加入了输入数据的正确性控制，也就是不可以输入0和负数,26,,模运算,在算法应用中，有一类计算与模运算（求除法之余数）有关，例如： 一个星期的模为7天 一天的模是24小时或1440分钟 一年的模是12个月（也可以是365或366天） 而模运算在数字比较和诸多计算案例中有应用,27,,求1001000范围内的平方回数,所谓平方回数，是指某个数，既是一个回文数，又是一个平方数， 例如：121是回文数，又是11的平方,28,,模运算求解分析,一个100以上的平方数，必须从平方根大于等于10的数字开始计算，而1000可以作为搜索循环的控制变量 但是，如何求出回文数？ 由于是在三位数中求回文数，也就是要求个位与百位上相等 这个时候，模（在RAPTOR中模运算符：mod）运算就可以派上用场,29,,求平方回数流程图,请思考一下，这个算法还使用了其他什么算法思想？,30,,字符和字符串运算,字符和字符串运算在算法中的用途有： 在输入输出界面中的应用，如在输出过程中将计算结果与量纲结合在一起； 在信息安全中的应用，如信息的加密与解密； 对用户对特定应用的输入的字符串，进行模式正确性的判断（如电子邮件地址需包含“”符号）等,31,,替换加密,试用以下替换码表，实现通信过程的加密 明码表 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 密码表 Q W E R T Y U I O P A S D F G H J K L Z X C V B N M,32,,替换加密,保存明文 Key保存密码表 B保存密文 解密算法，自行设计,33,,递归,在数学和计算机科学中，递归是指由一种（或多种）简单的基线条件(Base case)定义的一类对象或方法，并规定其他所有情况都能被还原为其基线条件 具体表现为：一个函数在其定义或说明中有直接或间接调用自身： 把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解 递归策略只需少量的程序就可描述出解题过程,34,,递归过程,一般来说，递归需要有边界条件、递归前进段和递归返回段 当边界条件不满足时，递归前进； 当边界条件满足时，递归返回 一般递归过程需要通过函数或子程序传递参数 而RAPTOR中要实现子程序的参数调用，必须使用其所谓的“中级模式（Intermediate mode）”,35,,递归算法常用于解决三类问题,(1)数据的定义是按递归定义的 (2)问题解法按递归算法实现 (3)数据的结构形式是按递归定义的 典型的递归算法(带参数传递实现)的运行效率较低 在递归调用的过程当中系统为每一层的返回点、局部变量等开辟了栈来存储 递归次数过多容易造成栈溢出等问题,36,,递归算法,理论上而言，所有递归算法都可以用非递归算法来实现 递归的应用： 递归是很好的求解问题的方法，可以很好的描述一个算法的原理 但是在算法实现中，必须避免“天真的递归”,37,,汉诺塔,有A、B、C三根柱子。A柱子上按从小到大的顺序堆放了N个盘子，要把所有的盘子从A柱移动到C柱，移动过程中如下要求： 一次只能移动一个盘子； 不允许把大盘放在小盘上面； 盘子只能放在三根柱子上,38,,汉诺塔递归求解,N个盘子的移动过程分作3大步： 把A柱上面的N-1个盘子移动到B柱； 把A柱上剩下的一个盘子移动到C柱； 把B柱上面的N-1个盘子移动到C柱； 其中N-1个盘子的移动过程又可按同样的方法分为三大步，这样就把移动过程转化为一个递归的过程，直到最后只剩下一个盘子，按照移动一个盘子的方法移动，递归结束,39,,汉诺塔递归main子图,40,,汉诺塔递归子程序,41,,斐波那契(Fibonacci)数列,一些问题本身是递归定义的，但它并不适合用递归算法来求解 如斐波那契(Fibonacci)数列，它的递归定义为：斐波那契数列为：0、1、1、2、3、，即： fib(0)=0; fib(1)=1; fib(n)=fib(n-1)+fib(n-2) （当n1时）,42,,斐波那契数列的递归求解,43,,递归的辨识,斐波那契递归实现，调用一次产生二个新的递归，调用次数呈指数增长，时间复杂度为O（2n）。 这种使用递归的方式，被称为“天真的递归（Naive recursion）”。 而使用递推算法求斐波那契数列，时间复杂度只是为O（n）,44,,数论问题,数论的本质是对素数性质的研究 2000多年前，欧几里得证明了有无穷个素数。寻找表示所有素数的素数通项公式，或者叫素数普遍公式，是古典数论最主要的问题之一 加法、减法和乘法这三种运算，在整数范围内可以毫无阻碍地进行 整数之间的除法在整数范围内并不一定能够无阻碍地进行 大数密码体系，至今仍然关系着国家的安全,45,,测素子程序,测素子程序是解决数论问题的核心，所以在数论应用算法中，几乎都要用到。 因此它的计算效率，直接影响与数论相关的算法效率,46,,一个测素子程序,如何改善测素子程序的效率？,47,,组合计算,计算一些物品在特定条件下分组方法的数目。这些是关于排列、组合和整数分拆问题的求解，属于组合数学研究的范畴 例如，求解从n个元素中取出m个元素的不同组合，用C(n,m)表示。根据组合的性质有如下公式成立： 1. C(n，m) = n!/(m!*(n-m)!) 但：13！是6227020800会超出32位机的字长,48,,组合计算,另，用C(n，m)表示从n个元素中取出m个元素的不同组合数，也可使用递归的形式定义： 2. C(n，m) = C(n-1，m) + C(n-1，m-1),49,,求n个数中取m个数的所能产生组合形式的数量,根据组合的递归形式的数学定义：公式（2）可知，从从n个元素中取出m个元素的基本案例和递归案例分别为： m=n， c=1 m=1， c=n mn ， c= C(n-1，m) + C(n-1，m-1),50,,递归实现组合数,51,,迭代法,迭代是数值计算中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或者方程组）的过程 为实现这一过程所使用的方法统称为迭代法（Iterative Method）,52,,一个简单的代数方程,三种迭代法,53,,三种迭代方法的比较,54,,测试的目的,迭代法是数值计算中求解非线性方程的基本思想方法，其构造方法可以有多种多样 关键使迭代收敛且有较快收敛速度 取定某个初始值，分别计算（3.3）（3.5）迭代结果，它们的收敛性如何？ 对三个迭代法中的某个，取不同的初始值进行迭代，结果如何？,55,,牛顿迭代法求方程解,请用牛顿迭代法（3.6式）求方程 在区间-3,3上误差不大于10-9的根，分别取初值X0=1.5, X0=0, X0=1分别进行计算，比较它们的迭代次数,56,,牛顿迭代法基本原理,设 ,令其解为 ,得：,这称为f(x)=0的牛顿迭代格式， 给定初值 x0 , 迭代产生数列：,X0，X1，X2, ,Xk, ,57,,牛顿迭代法的主要算法语句,迭代语句： x1=x0-(x0*3-x0-1)/(3*x0*2-1) 决策语句 abs(x1-x0)10*-9,58,,牛顿迭代法流程,三个初值 得到同样的结果 但迭代次数有差异,59,,End-3,基本策略,算法设计过程中，发现问题、分析问题及解决问题的思路、步骤与其他学科中的方法是一致的，就是寻找规律 计算机科学家在算法研究过程中总结了一些具有普遍意义的算法策略和一些可循的规律，能够帮助我们较快地找到算法,61,,基本策略,贪心策略 分治策略 回溯策略 动态规划 将递归算法转成非递归实现,62,,贪心策略,贪心算法在对问题求解时，总是做出在当前看来是最好的选择，因此它仅仅是某种意义上的局部最优解 但在相当广泛范围内，对许多问题它能产生整体最优解或者是整体最优解的近似解 “鼠目寸光” 是对贪心算法的最好描述,63,,贪心算法的特点,以当前情况为基础根据某个偏好原则作最优选择，而不考虑各种可能的整体情况 省去了为寻找最优解要穷尽所有可能而必须耗费的大量时间 采用自顶向下,以迭代的方法做出相关的贪心选择 每做一次贪心选择就将所求问题简化为一个规模更小的子问题,64,,贪心算法的特点,通过每一步贪心选择,可得到问题的一个局部最优解 但由此得到的全局解却不一定都是是最优的,65,,求解数字三角形,有任意一个数字三角形，只能自第一层(顶层)向下行走,且只能走下接的相邻两个结点 如第三层的1只能走第四层的3或1 问能否找到一条路径，使得路径上的权值之和最大？,66,,贪心法求解的算法设计,使用文件保存三角形的层数和所有数据 描述一个n层的三角形，需要(n*（n+1）)/2个数据和一个描述层次的数据; 使用二维数组a，保存数字三角形的所有数据 二维数组的大小为N*N，当然，其中有一半的元素为空值0;,67,,贪心法求解的算法设计,使用line，colum 两个变量在二维数组中，作为数字定位的指针； x作为保存权值累计的变量； line的值同时用来控制路径行走的循环,68,,流程图,69,,分治策略,分治法（Divide and Conquer）的基本思想是，将一个较大规模的问题分解为若干个较小规模的子问题，找出子问题的解，然后把各个子问题的解合并,从而得到整个问题的解 分治法的分（Divide）是指将较大的问题划分为若干个较小的问题，然后用递归法求解子问题； 分治法的治（Conquer）是指从小问题的解来构建大问题的解,70,,分治策略,分治法算法中至少包含有两次递归过程，只有一个递归过程的算法在严格意义上不能算作分治算法,71,,求用分治法进行幂运算降序求解,在公钥加密的RSA算法中将高次幂运算转换为低次幂运算可以加快加密和解密的计算过程，从而提高了RSA算法的运算速度 算法一：采用递推循环的方式实现类似a*b的计算过程； 算法二：采用递归方式实现分治算法： a*b= (a*a)*(b/2) b=偶数 a*b= a*(a*(b-1) b=奇数,72,,分治法的计算效率,以求520为例，使用分治方法与不使用分治方法的递归算法比较，分治法可以节省近三分之二时间,73,,分治方法乘幂运算流程图,74,,回溯策略,如果问题的规模（数量）是按指数速度增加的，那么这些算法的能力将受到一定的限制 在这种情况下，回溯法（Backtracking）也许是一个更好的选择 回溯法也叫穷尽搜索法（Brute-Force Search），其基本思想是尝试分步地去解决一个问题,75,,现有n种物品，对1=i=n，已知第i种物品的重量为正整数Wi，价值为正整数Vi，背包能承受的最大载重量为正整数W 现要求找出这n种物品的一个子集，使得子集中物品的总重量不超过W且总价值尽量大,0-1背包问题的数学描述,76,,设有物件n项，重量为w(5,3,2), 价值v(9,7,8)，如果背包只能装5斤，求可以放背包的物品最大价值。 使用回溯算法，决策树的建树过程为：深度有限，左侧优先，左侧分支不取东西，右侧取当前物件,0-1背包问题求解,（3，5，0）,（2，3，8）,（2，5，0）,（1，2，7）,（1，5，0）,（1，3，8）,i：红色，表示物品的编号 aw：绿色，当前可用空间 V：蓝色，当前物品价值,（1，0，15）,（-，3，8）,（-，5，0）,（-，0，9）,（-，2，7）,（-，-3，16）,（-，-2，17）,77,,k元组的概念,元组(tuple)是一种有穷序列，k个元素的序列称为k元组。与集合不同，集合不考虑元素的顺序，但元组中的元素有严格的顺序规定 在0-1背包问题中的决策树中的元素和重量为w(5,3,2), 价值v(9,7,8)，皆为三元组 k元组的概念在下一章的有限状态机和图灵机中还会用到,78,,0-1背包回溯算法的main子图,建议测试案例从简单的方案开始,79,,0-1背包问题-回溯法求解流程图,80,,0-1背包回溯算法说明,Maxvalue是一个递归实现的子程序，其中的主要传递参数如下： w： 项目物体的重量数组 v： 项目物体的价值数组 length_of(w)： 重量数组的长度，也是最后一个物件下标，遍历循环的开始点，直到第一个元素 max_weight：背包的最大容量 ：最后的返回值，即背包中物体的价值,81,,动态规划,计算Fibonacci数列的第n项：当项数大于2时，F（n）=F（n-1）+F（n-2） 如果计算Fibonacci数列第n项，这需要计算从第3项到第n-1项 随着n值的增大，递归解法的算法时间复杂性会按几何级数增长 这类问题的关键是子问题（sub-problem）有重叠，因而分治法并不适合于此类问题的求解,82,,动态规划,基本思想是：如果一个较大问题可以被分解为若干个子问题，并且子问题有重叠，那么，可以将每个子问题的解存放到一个表中，然后通过查表来解决问题，减少不必要的重复计算 动态规划是20世纪50年代美国数学家Richard Bellman提出的 在这个术语中，Programming与编程没有关系，而是规划和设计的意思,83,,动态规划解Fibonacci数列第n项,84,,算法说明,算法递归子程序中的三个传递参数的作用分别是： a：第n项的输入参数 b：第n项的结果输出 c：计算过程中的中间结果存留数组（也就是一个线形表） 在计算过程中，每次计算的结果都保存在c数组中，出现重叠子问题时，直接到c数组中调取结果,85,,动态规划的分析,要消除计算过程中的重复性过程，动态规划是比较好的选择 这也是计算机科学中，进行问题求解的重要途径之一 由于动态规划需要保存中间计算结果，势必占用较大的内存空间（这点贪心法就完全不同），但时间复杂性则会降低 这就是所谓“空间换时间“的策略,86,,动态规划的分析,动态规划与贪心法不同的地方，它是一种最优化算法 当所有的解空间可以遍历的前提下，利用动态规划的思想保存所有可能的解 再通过比较就可以得到最优的解 实现原理非常简单，但非常实用，也是计算机科学中最常用的算法策略 请设计使用动态规划求解数字三角形,87,,将递归算法转成非递归的实现,递归是计算机科学中非常重要的概念，其主要优点是递归的代码量比非递归的代码量少，算法可以设计的非常简洁 这是由于递归所使用的方式是函数调用 这在计算机算法实现中属于非常自然的栈结构 不需要记录位置信息，不需要添加控制语句 这些工作都由函数调用的特性自行解决,88,,递归算法的弱点,递归算法的执行效率比一般非递归的执行效率要低 因为递归的实质既然是函数调用，而函数调用必然要进行线程栈空间的分配，记录每一次函数调用前的状态等工作，开销是比较大的 这个情况读者可以自行应用递归实现汉诺塔案例，输入不同的铁饼数，运行并观察,89,,非递归算法的特点,非递归算法则不需要进行这些工作（线程栈空间的分配等） 因为非递归使用额外的变量记录当前所处的位置信息，以及额外的控制语句 递归与非递归调用最主要区别就是在函数调用上,90,,递归与非递归策略思想,因此对解决某些问题时，希望用递归算法分析问题，但用非递归算法解决问题 这就需要把递归算法转换为非递归算法,91,,递归算法转化为非递归算法,有如下三种基本方法： 通过分析，跳过分解过程，直接用循环结构的算法实现求解过程。 自己用栈模拟系统的运行栈，通过分析只保存必须保存的信息，从而用非递归算法替代递归算法 利用栈保存参数，由于栈的后进先出特性吻合递归算法的执行过程，因而可以用非递归算法替代递归算法,92,,使用非递归方法实现汉诺塔算法,93,,算法说明,将三个柱子分别命名为na1，na2，na3，初始状态，所有的盘子都在na1上，三个柱子按逆时针方向排列成一个圆环 其中存在一个规律，当对于规模为n的汉诺塔问题时： 1奇数编号盘子总是移动移动到它后的第2个柱子上； 2偶数编号的盘子总是移动移动到它的后第1个柱子上,94,,基本算法策略的讨论,最优化和非最优化： 什么不去追求最优化的解？ 因为存在一个解空间的规模问题，如果在规定时间里，可以找到所有的解，那么选出其中的最优解； 但是，如果不可能（有许多O(2n）以上时间复杂度的问题)，那么，只好退而求其次，用次优解来解决问题 而贪心策略就是求次优解的常用思,95,,基本算法策略的讨论,时间换空间（或空间换时间） 大部分递归算法编写简单，但运行的时间会随着问题规模的增长而急剧增长 而分治方法，一般要花费较多的时间将问题划分成为较小规模，增加了程序的复杂性；递归程序的非传参实现，也是如此 但较为复杂的算法，却换来几何级数的运行时间节省,96,,基本算法策略的讨论,回溯策略所解的一些问题往往是不能用数学公式去直接求解的 它需要通过一个过程，此过程要经过若干个步骤才能完成，每一个步骤又分为若干种可能； 同时，为了完成任务，还必须遵守一些规则和约束； 对于这样一类问题，一般采用搜索的方法来解决，回溯法就是搜索算法中的一种控制策略，它能够解决许多搜索中问题,97,,基本算法策略的讨论,使用递归算法的思路分析问题，但用非递归算法解决问题。 使用递归的思路分析问题，可以得到简便、可行但运行效率低下的算法 通过非递归将该算法进行再实现，可以得到极高效率的优秀算法,98,,小结与回顾,基本算法包含了穷举、分段函数、递推、递归、迭代、组合、模运算、数论问题等，这种问题分类和针对性方法的比对可以避免毫无方向的试错和摸索过程 而基本策略则是计算机科学中解决战略性问题的重要手段，本章专门选择了若干相对简单的案例来分别说明贪心、分治、回溯和动态规划的基本思想 而使用递归的方法分析问题，使用非递归的方法实现算法，具有更为深邃的战略意义,99,,第4章 模型化,可视化计算,如何实现数据类型抽象,无论是进行科学计算或数据处理、过程控制等，都是对数据进行加工处理的过程 必须研究数据的特性及数据间的相互关系及其对应的存储表示 利用这些特性和关系设计出结构好、效率高的程序或算法,如何进行数据抽象?,数据结构是数据存在的形式 它用来反映一个数据的内部构成，即一个数据由哪些成分的数据构成，以什么方式构成，呈现什么结构 数据（Data）是信息的载体 能够被计算机识别、存储和加工处理 数据元素（Data Element）数据基本单位 在计算机程序中作为一个整体考虑和处理,如何进行数据抽象?,数据结构（Data Structure）是指互相之间存在着一种或多种关系的数据元素的集合 四类基本的数据结构： 集合结构 线性结构 树型结构 图形结构,如何进行数据抽象?,一个数据结构必须包含有数据元素的集合和数据关系的集合这两个基本要素 数据结构包括数据的逻辑结构和数据的物理结构,数据的逻辑结构,可以看作是从具体问题抽象出来的数学模型，它与数据的存储无关 研究数据结构的目的是为了在计算机中实现对它的操作，为此还需要研究如何在计算机中表示一个数据结构,数据的物理结构,指数据结构在计算机中的表示方式，也称存储结构或映像 它所研究的是数据结构在计算机中的实现方法，包括数据结构中元素和元素间关系的表示 例如：顺序存储方法是把逻辑上相邻的元素存储在物理位置上相邻的存储单元中，可以借助于程序设计语言中的数组来实现,抽象数据类型,抽象数据类型(Abstract Data Type， ADT)是指一个与某种类型的数据结构行为模式有关的数学模型以及定义在此模型上的一组运算 而所有的运算必需在该类型的数据结构的数学限制条件下才是有效的,抽象数据类型举例,一个数据堆栈（Stack），可以定义三种运算： 压栈(push)：将一些数据插入该结构； 弹出(pop)：从结构中取出并清除数据（按照后入先出的顺序）； 检查（peek），检查结构顶端的数据而不做清除,抽象数据类型的实现,一般抽象数据类型需要通过某个系统子已有的数据类型来间接定义与实现 对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即子图、子程序或函数名，并且规定这些运算的参数性质,抽象数据类型的程序实现,在RAPTOR中实现所定义的抽象数据类型数据部分用一种已知的数据类型（如一维、二维数组，字符串等）来实现 抽象数据类型操作部分中的每个操作用RAPTOR子图或子程序来实现 这样能够同其他计算机程序语言实现算法具有一定的可比性,线性表的基本概念,数据结构分线性结构和非线性结构 线性结构包括线性表、栈、队列、数组和字符串 线性结构特点：在数据元素的非空有限集中 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个外，集合中的每个数据元素均只有一个前趋 除最后一个外，集合中的每个数据元素均只有一个后继,线性表的逻辑结构,一个线性表是n个数据元素的有限序列 特征： 元素个数n表长度，n=0：空表 1in时 ai的直接前趋是ai-1，a1无直接前趋 ai的直接后继是ai+1，an无直接后继 元素同构，且不能出现缺项,例 英文字母表（A,B,C,Z)是一个线性表,顺序表,用一组地址连续的存储单元存放一个线性表叫顺序表 特点： 表中的数据元素逻辑上相邻 实现随机存取 实现：可用RAPTOR的一维数组实现,也是构成本课程其他数据结构的基础,顺序存储结构的优缺点,优点 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑 缺点 插入、删除操作需要移动大量的元素 应用:顺序表的主要应用 参见第5章 排序与查找,堆栈,堆栈是一种特殊的线性表，基本的工作方式是，后入先出（Last In First Out, LIFO） LIFO: 最后放入堆栈的数据最先被取走 常用的堆栈运算： 压栈（Push）,将新的元素放入堆栈 弹栈(Pop)，从堆栈顶端取走元素 堆栈可以使用数组或链表实现 应用：计算器、编译器、程序设计、数制转换,队列,队列是一种特殊线性表，基本的工作方式是，先入先出（First In First Out, FIFO） FIFO: 最先放入队列的数据最先被取走 常用的队列运算： 入队（ Enqueue ）,将新的元素放入堆栈 出队(Dequeue)，从堆栈顶端取走元素 队列可以使用数组或链表实现 应用：打印机、仿真、网络(路由器),Josephs problem,一组n个候选者, 排列成环状，所有第m个人都会被淘汰，只有一位幸运者被选上 将队列Q中，所有人按1到n编号 当队列不空，做以下动作: a. 做以下m-1次 i. x=Dequeue Q ii. Enqueue Q(x) b. x=Dequeue Q 输出X作为最后的幸运者,Josephs problem（约瑟夫问题）,请跟踪第1步和2b的执行，在6取3的情况下： 约瑟夫环上的哪个位子是幸运位？,RAPTOR的队列操作设计,入队操作,初始化队列,出队操作,非线性数据结构-树,树(Tree) 是一种重要的非线性数据结构。 不含有任何节点（元素）的树被称为空树 在一棵非空树中，它有且仅有一个称作根(root)的节点，其余的节点可分为m棵(m0)互不相交的子树(即称作根的子树) 每棵子树(Sub Tree)又同样是一棵树 显然，树的定义是递归的,树的结构与分解,树的基本术语,节点的度和树的度 树中所有节点的度的最大值被定义为该树的度 分支节点和叶子节点 在一棵树中，度等于0的节点称作叶子或终端节点，度大于0的节点称作分支节点或非终端节点 子节点、父节点和兄弟节点 节点的层数和树的深度(高度),树的基本术语,有序树和无序树 一棵反映父子关系的家族树，兄弟节点之间是按照排行大小有序的，所以它是一棵有序树 森林,森林是m(m0)棵互不相交的树的集合,树的性质,性质1: 树中的节点数等于所有节点的度数加1。 性质2: 度为k的树中第i层上至多有ki-1个节点（i1） 性质3深度为h的k叉树最多有 个节点 性质4具有n个节点的k叉树的最小深度为： logk(n(k-1)+1),树的存储,父子链表,使用文件描述树的基本数据,对树T的基本描述,保存在data.csv文件中，每一行保存一个节点的父节点，第一行保存的是根节点，所以其父节点为0 将树的描述保存在文件中，可以方便校验，减少屏幕交互,建立父子链表的main子图,建立父子链表的data_input_from_file子图,建立父子链表的 findchild子图,实现树的存储,parents，数组下标表示各个节点，数组元素保存各个节点的父节点,实际内容从文件得到,这是推断其他数据的基础； child数组是一个字符串数组，元素下标表示各个节点，数组元素使用字符串保存各个节点的子节点 Nodestr保存了所有节点的“数据”,树的运算,树的主要运算包括进行树的遍历、求树的深度、输出树等 常用的树的遍历包括前序遍历（或称深度优先遍历）和按层遍历（或称广度优先遍历）两种 前序遍历T：得到的节点序列为： A B D E G H I C F,小结与回顾,本章的内容围绕模型开始，主要内容可以划分为两个主要部分，使用有限状态机和图灵机对客观物体建立状态模型；使用数组表述抽象数据结构模型 由于软件功能和书的篇幅限制，本书中设计的大部分抽象数据结构都不可能按照经典文献的要求进行完整、规范的定义和描述。所以在实现上进行模拟，尽可能做到“神似”而不是“形似”。,第5章 排序与查找,可视化计算,学习目标,如何在计算机中进行排序? 排序算法有那些分类? 如何实现常用的排序算法? 查找与排序有何关系? 查找算法有哪些分类? 如何实现常用的查找算法？,134,,何为排序?,学习中的排序： 在一些教课书中，会将涉及到的所有术语排成索引，作为附录，方便读者在需要时查找 图书馆工作人员的重要工作，就是把归还的书，插入适当的书架、层次、位置, 方便读者查阅 社会中排序： 会议代表名单的排序（按姓氏笔画）； 联大会议的发言顺序（按国家名称字母排序）,135,,计算机如何进行排序？,从”混沌”到有序：排序自身也是一种应用,同时也为快速的查找提供必要的准备 在计算机科学中，排序(sorting)是研究最多的问题之一 基本排序算法有5类： 插入排序，例如，直接插入排序，二分插入排序等； 交换排序，例如，冒泡排序，快速排序等； 选择排序，例如，选择排序，推排序等 归并排序，例如，归并排序，多相归并排序等 分布排序，例如，桶排序，基数排序等,136,,直接插入排序,直接插入排序与整理扑克牌的过程非常类似 第1张牌没有必要整理 以后每次从牌堆(无序区)的最上面摸出1张牌并插入左手牌(有序区)中正确的位置上 为了确定正确的插入位置，一般从左向右将摸上来的牌与手中已有的牌逐一比较,137,,直接插入排序,假设data.txt文件中存放着待排序的记录R ，则R可以看成是一个长度为n的待排数组 首先从data.txt文件中保存的数组R读入一个数据到a1，生成一个有序数组 由于文件中的数组R呈无序状态，从i=2起至i=n为止，依次将Ri插入当前的有序数组a1i-1中 最后生成含n个记录的有序数组,138,,插入排序main子图,139,,插排look_for_position子图,140,,插排move_to_new_position子图,141,,桶排序,桶排序的思想源于信件分拣 在现实应用中，是把0，1)的数值划分为n个大小相同的子区间，每一子区间可以看作是一个桶 然后将n个记录分配到各个桶内 由于同一桶内的记录其关键字不尽相同，所以必须采用关键字比较的排序方法(通常用插入排序)对每个桶进行排序 然后依次将各非空桶内的记录连接(收集)起来即可,142,,143,,桶排序main子图,144,,桶排序的实现说明,简单的设计就是直接利用random()函数产生待排数据 准备一个10行的二维数组a,每一行就是一个桶 将随机数小数后的第一位为09的数字依次放入这10个桶内 很显然，这个算法离不开上一节介绍的插入排序 使用csv格式的文件保存已排序数据，可以留给其他的应用使用,145,,桶排insert_sort_prepare子图 （I）,146,,桶排insert_sort_prepare子图 （II）,147,,桶排序的输出结果,148,,冒泡排序,冒泡排序（Bubble Sort）的基本概念是： 将被排序的记录数组a1n垂直排列，每个记录ai看作是重量为ai所存数值的气泡 根据轻气泡不能在重气泡之下的原则，从下往上扫描数组a：凡扫描到违反本原则的轻气泡，就使其向上“飘浮“ 如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止,149,,150,,冒泡排序main子图,151,,冒泡算法说明,初始状态： a1n为无序区。 第一次扫描：从无序区底部向上依次比较相邻的两个气泡的重量，若发现轻者在下、重者在上，则交换二者的位置，第一次扫描完毕时，“最轻“的气泡就飘浮到该区间的顶部，即关键字最小的记录被放在最高位置a1上。 第二次扫描：扫描a2n。扫描完毕时，“次轻“的气泡飘浮到a2的位置上。 最后，经过n-1 趟扫描可得到有序区a1n,152,,冒泡排序,bubble子图,153,,冒泡算法如何改进？,假如待排序列已经是基本有序的（只有两个数字需要换位），如何能够在n-1趟之前，结束排序？ 提示：可以将已经排好的数据，有意调换一对，然后使用改进后的算法实验（从文件读入待排数据）,154,htt