第3章算法与数据结构.ppt

软件技术基础 自动化系：黄巧莉 Email：qlhuang@swu.edu.cn 设计程序首先要了解需要研究解决的问题，提出适当的计算模型并列出解决问题的方法和步骤,模型一旦建立起来，就要选择合适的算法，并将解题步骤表述出来。 本章着重讨论解决问题的核心——算法以及算法的处理对象——数据的结构 程序＝算法＋数据结构 第三章 算法与数据结构 3.1 算法 3.2 数据结构 3.3 查找与排序 3.1 算法 解题过程的准确、完整的描述称作解该问题的算法 程序就是用计算机语言表述的算法 流程图就是图形化了的算法 3.1.1 算法的表示 算法由操作与控制结构两要素组成。 1.操作 (1) 逻辑运算： “与”、“或”、“非”； (2) 算术运算： 加、减、乘、除； (3) 数据比较： 大于、小于、等于、不等于； (4) 数据传送： 输入、输出、赋值。 2.控制结构 算法的控制结构，决定了各操作的执行次序，用流程图 可以形象地表示出算法的控制结构。 任何复杂的算法都可以用顺序、选择、循环三种控制结构组合而成。 3.1.2 算法的描述 算法设计一般是由粗到细的过程，一般可以使用下面几种类型的工具描述算法： 自然语言 专用工具 算法描述语言 1.自然语言 自然语言描述算法通俗易懂，但它有着难以克服的缺陷： (1) 易产生歧义性 (2) 语句繁琐冗长，很难清楚地表达算法的逻辑流程 (3) 当今的计算机尚不能处理用自然语言表示的算法 2.专用工具 常用的有流程图、PAD图和N-S图、伪代码等； 流程图：是采用不同的几何图形来描述算法的逻辑结构，每个几何图形表示不同性质的操作 PAD（问题分析）图：二维树形结构图表示程序的控制流 N－S图（盒图）：结构化控制结构的盒图表示 常用流程图符号： 3.算法描述语言 为了便于转换成某种编程语言，一般采用准程序设计语言作算法描述语言。 3.1.3 算法的定义 1.算法是由一套计算规则组成的一个过程； 2.组成算法的规则是确定的、可执行的； 3.每种算法必须有确定的结果，产生一个或多个输出； 4.每个算法必须有0个（自动生成初始数）或多个输入； 5.解答必须在有限步内得到,不能出现“死循环”。 我们可以得出如下的结论：算法是一个过程，这个过程由一套明确的规则组成，这些规则指定了一个操作的顺序，以便用有限的步骤提供特定类型问题的解答。 算法设计的原则 设计算法时，通常应考虑达到以下目标： 1．正确性 2. 可读性 3．健壮性 4．高效率与低存储量需求 1．正确性 首先，算法应当满足以特定的“规格说明”方式给出的需求。 其次，对算法是否“正确”的理解可以有以下四个层次： a．程序中不含语法错误； b．程序对于几组输入数据能够得出满足要求的结果； c．程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果； d．程序对于一切合法的输入数据都能得出满足要求的结果； 通常以第?c?层意义的正确性作为衡量一个算法是否合格的标准。 2. 可读性 算法主要是为了人的阅读与交流，?其次才是为计算机执行。因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试；? 3．健壮性 当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。 4．高效率与低存储量需求 通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间。两者都与问题的规模有关。 3.1.4 算法效率的度量 通常有两种衡量算法效率的方法： 事后统计法 缺点：1.必须执行程序 2.与计算机软硬件环境因素关系很大，掩盖算法本质 事前分析估算法 和算法执行时间相关的因素： 1．算法选用的策略 2．问题的规模 3．编写程序的语言 4．编译程序产生的机器代码的质量 5．计算机执行指令的速度 一个特定算法的“运行工作量”的大小，依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。 假如，随着问题规模?n?的增长，算法执行时间的增长率和?f(n)?的增长率相同，则可记作： T (n) = O(f(n)) 称T (n) 为算法的(渐近)时间复杂度。 如何估算 算法的时间复杂度？ 算法 = 控制结构 + 原操作 （固有数据类型的操作） 算法的执行时间 = ∑原操作(i)的执行次数×原操作(i)的执行时间 算法的执行时间与原操作执行次数之和成正比 从算法中选取一种对于所研究的问题来说是基本操作的原操作