03–算法和数据结构.ppt

第三章 算法与数据结构 设计程序首先要了解需要研究要解决的问题，提出适当的计算模型并列出解决问题的方法和步骤,模型一旦建立起来，就要选择合适的算法，并将解题步骤表述出来 本章着重讨论解决问题的核心 -- 算法以及算法的处理对象 -- 数据的结构 3．1算法 解题过程的准确、完整的描述称作解该问题的算法 程序就是用计算机语言表述的算法，流程图就是图形化了的算法 程序＝算法＋数据结构 3.1.1 算法的两要素 算法由操作与控制结构两要素组成 1.操作 2. 控制结构 算法的控制结构，决定了各操作的执行次序。用流程图 可以形象地表示出算法的控制结构 任何复杂的算法都可以用顺序、选择、循环三种控制结构组合而成 3.1.2 算法的特征 1. 算法是由一套计算规则组成的一个过程 2. 组成算法的规则是确定的、可执行的 3. 每种算法必须有确定的结果，产生一个或多个输出 4. 每个算法必须有0个（自动生成初始数）或多个输入 5. 解答必须在有限步内得到,不能出现“死循环” 我们可以得出如下的结论：算法是一个过程，这个过程由一套明确的规则组成，这些规则指定了一个操作的顺序，以便用有限的步骤提供特定类型问题的解答 3.1.3 算法的表示 算法设计一般是由粗到细的过程，一般可以使用下面几种类型的工具描述算法: 1.自然语言 自然语言描述算法通俗易懂，但它有着难以克服的缺陷： (1) 易产生歧义性 (2) 语句繁琐冗长，很难清楚地表达算法的逻辑流程 (3) 当今的计算机尚不能处理用自然语言表示的算法 2.专用工具 常用的有流程图、PAD图和N-S图、伪代码等 3.算法描述语言 为了便于转换成某种编程语言，一般采用准程序设计语言作算法描述语言。在本书中为类VB语言 继续 流程图 是采用不同的几何图形来描述算法的逻辑结构，每个几何图形表示不同性质的操作 1.枚举法（穷举法） 基本思想是： 先依据题目的部分条件确定答案的大致范围 在此范围内对所有可能的情况逐一验证，直到全部情况验证完 若某个情况使验证符合题目的条件，则为本题的一个答案；若全部情况验证完后均不符合题目的条件，则问题无解 2.迭代法 使一个复杂问题的求解过程转化为相对简单的迭代算式的重复执行过程 使用迭代法构造算法的基本方法是： 首先确定一个合适的迭代公式，选取一个初始近似值以及解的误差 然后用循环处理实现迭代过程，终止循环过程的条件是前后两次得到的近似值之差的绝对值小于或等于预先给定的误差 并认为最后一次迭代得到的近似值为问题的解。 3.递归法 如果一个过程直接或间接地调用它自身，则称该过程是递归的 例：求阶乘。 Func fac(n As Integer) If n=1 then fac=1 Else fac=n*fac(n-1) Endif 4.递推法 所谓递推法，它的数学公式也是递归的。只是在实现计算时与递归相反。从给定边界出发逐步迭代到达指定计算参数。 例：求阶乘 f(n)＝n! ＝n×(n-1)! ＝n×f(n-1) 要计算10!，可以从递推初始条件f(0)=1出发，应用递推公式f(n)=n×f(n-1)逐步求出f(1)、f(2)…、f(9)、最后求出f(10)的值 递推操作是提高递归函数执行效率最有效的方法，科技计算中最常见 5.分治法 解一个夏杂的问题时，尽可能地把这个问题分解为较小部分，找出各个的解，然后再把各部分的解组合成整个问题的解，这就是所谓的分治法 6.回溯法 在那些涉及到寻找一组解的问题或者满足某些约束条件的最优解的问题中，有许多可以用回溯法来求解 回溯法的算法是： Proc Backtracking(succ : Boolean) 确定起始状态值走第一步 确定下一步还有几种可能 选一可能走下一步，记住可能和本步特征 做完新一步应做的事 While 目标未达到 do 确定下一步有几种可能 While 没有可能and 还有上一步 do 回退上一步 查有无下一可能 Enddo If 上一步没有了Then return (SUCC=FALSE) EndIf 选一可能走一步，记住可能和本步特征 做完新一步应做的事 Enddo return (SUCC=TRUE) End Backtracking 3.2 数据结构 3.2.1 数据结构概述 。 1．数据结构的研究内容 数据的逻辑结构、数据的存储结构、数据的运算 数据的逻辑结构：Data-Structure ＝ (D,R) 其中：D是数据元素的集合，R是D上关系的集合 一般将数据结构分为两大类：线