《算法与数据结构》ppt课件

《《算法与数据结构》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章算法与数据结构设计程序首先要了解需要研究要解决的问题，提出适当的计算模型并列出解决问题的方法和步骤,模型一旦建立起来，就要选择合适的算法，并将解题步骤表述出来本章着重讨论解决问题的核心--算法以及算法的处理对象--数据的结构3．1算法解题过程的准确、完整的描述称作解该问题的算法程序就是用计算机语言表述的算法，流程图就是图形化了的算法程序＝算法＋数据结构3.1.1算法的两要素算法由操作与控制结构两要素组成1.操作(1)逻辑运算：“与”、“或”、“非”；(2)算术运算：加、减、乘、除；(3)数据比较：大于

2、、小于、等于、不等于；(4)数据传送：输入、输出、赋值。2.控制结构算法的控制结构，决定了各操作的执行次序。用流程图可以形象地表示出算法的控制结构任何复杂的算法都可以用顺序、选择、循环三种控制结构组合而成3.1.2算法的特征1.算法是由一套计算规则组成的一个过程2.组成算法的规则是确定的、可执行的3.每种算法必须有确定的结果，产生一个或多个输出4.每个算法必须有0个（自动生成初始数）或多个输入5.解答必须在有限步内得到,不能出现“死循环”我们可以得出如下的结论：算法是一个过程，这个过程由一套明确的规则组成，

3、这些规则指定了一个操作的顺序，以便用有限的步骤提供特定类型问题的解答3.1.3算法的表示算法设计一般是由粗到细的过程，一般可以使用下面几种类型的工具描述算法:1.自然语言自然语言描述算法通俗易懂，但它有着难以克服的缺陷：(1)易产生歧义性(2)语句繁琐冗长，很难清楚地表达算法的逻辑流程(3)当今的计算机尚不能处理用自然语言表示的算法2.专用工具常用的有流程图、PAD图和N-S图、伪代码等3.算法描述语言为了便于转换成某种编程语言，一般采用准程序设计语言作算法描述语言。在本书中为类VB语言继续流程图是采用不同

4、的几何图形来描述算法的逻辑结构，每个几何图形表示不同性质的操作常用流程图符号：返回1.枚举法（穷举法）基本思想是：先依据题目的部分条件确定答案的大致范围在此范围内对所有可能的情况逐一验证，直到全部情况验证完若某个情况使验证符合题目的条件，则为本题的一个答案；若全部情况验证完后均不符合题目的条件，则问题无解3.1.4常用算法2.迭代法使一个复杂问题的求解过程转化为相对简单的迭代算式的重复执行过程使用迭代法构造算法的基本方法是：首先确定一个合适的迭代公式，选取一个初始近似值以及解的误差然后用循环处理实现迭代过程

5、，终止循环过程的条件是前后两次得到的近似值之差的绝对值小于或等于预先给定的误差并认为最后一次迭代得到的近似值为问题的解。3.递归法如果一个过程直接或间接地调用它自身，则称该过程是递归的例：求阶乘。Funcfac(nAsInteger)Ifn=1thenfac=1Elsefac=n*fac(n-1)Endif递归过程必须有一个递归终止条件，当n=0时定义为1，是阶乘递归定义的递归出口递归则是从函数本身出发，逐次上溯调用其本身求解过程，直到递归的出口，然后再从里向外倒推回来，得到最终的值4.递推法所谓递推法，它

6、的数学公式也是递归的。只是在实现计算时与递归相反。从给定边界出发逐步迭代到达指定计算参数。例：求阶乘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.回溯法在那些涉

7、及到寻找一组解的问题或者满足某些约束条件的最优解的问题中，有许多可以用回溯法来求解回溯法的算法是：ProcBacktracking(succ:Boolean)确定起始状态值走第一步确定下一步还有几种可能选一可能走下一步，记住可能和本步特征做完新一步应做的事While目标未达到do确定下一步有几种可能While没有可能and还有上一步do回退上一步查有无下一可能EnddoIf上一步没有了Thenreturn(SUCC=FALSE)EndIf选一可能走一步，记住可能和本步特征做完新一步应做的事Enddoretu

8、rn(SUCC=TRUE)EndBacktracking3.2数据结构3.2.1数据结构概述。1．数据结构的研究内容数据的逻辑结构、数据的存储结构、数据的运算数据的逻辑结构：Data-Structure＝(D,R)其中：D是数据元素的集合，R是D上关系的集合一般将数据结构分为两大类：线性数据结构和非线性数据结构。线性数据结构有线性表、栈、队列、串、数组和文件；非线性数据结构有树和图程序中的数据运算是定义在数据的逻