第3章3._算法和数据结构.pptVIP

3.4 算法和数据结构 3.4.1 算法 3.4.2 数据结构 3.4.1 算法 计算机求解问题的步骤 (1) 确定并理解问题； (2) 寻找解决问题的方法与步骤，并将其表示成算法(Algorithm) ； (3) 使用某种程序设计语言描述该算法(编程), 并进行调试； (4) 运行程序，获得问题的解答； (5) 进行评估，改进算法和程序 1. 什么是算法？ 算法是解决问题的方法与步骤 例：有三个硬币，其中一个是伪造的，另两个是真的，伪币与真币重量略有不同。现在提供一座天平，如何找出伪币呢？ 分析： 方法明确而有序 按提供的条件进行操作 任何人均可仿照进行(共享智能) 关于算法的三方面问题 如何确定算法（算法设计）？ 如何表示算法（算法表示）？ 如何使算法更有效（算法分析）？ 2. 算法设计举例 例：对整数进行排序 问题：任给一组(n个)整数，将它们从小到大进行排序 粗略的思路： ① 从所有整数中选一个最小的，作为已排序的第一个数 ② 从剩下未排序整数中选最小的数，添加到已排序整数的后面 ③ 反复执行步骤②，直到所有整数都处理完毕 进一步细化： 把待排序的整数放在一个数组a中，每个整数是数组a中的一个元素：a(1), a(2), a(3), ···, a(n), 排好序的元素在a的前面部分，无序的元素留在后面，每“循环”一次，有序部分增加1个元素，无序部分减少1个元素 每次“循环”只需在数组的无序元素部分选出最小的数 反复进行n-1次即可得到排序后的结果 “直接选择排序”算法举例 “直接选择排序”算法的描述 将原始数据放在数组a中； 设置i的初值为1，循环执行下列操作，直到i = n ： { 确定a(i) 到a(n)中最小整数的位置，设为j ； 交换a(i)和a(j) ； i = i +1 } 直接选择排序的VB语言程序 3. 算法的表示 算法的表示方法 文字说明 流程图表示 用N-S盒图表示算法 用PAD图描述算法 伪代码（一种介于自然语言和程序设计语言之间的文字和符号表达工具） 自然语言描述 “比较Ａ与Ｂ的重量，若Ａ＝Ｂ，则Ｃ是伪造的；否则再比较Ａ与Ｃ的重量，若Ａ＝Ｃ，则Ｂ是伪造的；否则Ａ是伪造的。” 缺点： 容易产生歧义，很难 “精确”地进行表达 叙述冗长，很难清楚地表达算法的逻辑流程 算法的流程图表示 流程图由结点和有向边构成，它描述了算法所执行操作的顺序及执行操作的条件 流程图符号 ： 4. 算法的分析 算法分析的基本内容 正确性：给定有效输入后，经过有限时间的计算，产生正确的输出结果 简单性 算法是否容易理解，是否容易验证其正确性，程序是否容易调试 简单的算法效率不一定高，要在保证一定效率的前提下力求算法简单 时间复杂性(Time Complexity) ： 当问题的规模n充分大时，运行该算法所需要的时间的数量级表示 空间复杂性(Space Complexity) ： 除原始数据之外，额外占用的存储空间的大小 4. 小结 计算机中处处是算法！ 例1：Word程序如何在文档中查找用户指定的词语？ 例2：在Word文档的表格中如何将表格内容排序？ 例3：如何把一幅彩色图片转换为灰度(黑白)图片？ 例4： Windows如何在硬盘中找到用户指定的文件？ 例5：媒体播放器如何把MP3文件转换成动听的音乐？ 例6：有哪些信誉好的足球投注网站引擎如何在WWW网中找到用户需要的网页？ 算法是计算机软件的灵魂 计算机的通用性是因为它能运行各种各样的程序，而程序之所以能解决问题，是因为它所体现了正确的算法 算法所解决的是一类问题而不是一个特定的问题，例如 排序(sort) 可以是表格内容的排序，也可以是文件夹中文件的排序，可以按数字或文字排序，也可以按日期排序，等等 查找(search)， 可以在文档中查找某个单词或在硬盘中查找某个文件，也可在Web上查找某个网页，等等 开发计算机应用的核心是：根据实际问题给出解题的算法，然后再将该算法在计算机上实现(即开发成为软件) 计算机算法的4个特点 目的：完成某个特定的信息处理任务 必须满足的性质： ① 确定性：算法中每一步操作的含义必须清楚明确，无二义性 ② 能行性： 算法中有待实现的操作都是计算机可执行的，即必须在计算机的能力范围之内 ③ 有穷性： 算法在执行了有限步操作后必须结束 ④ 算法结束后至少产生一个输出（包括参量或状态的变化） 3.4.2 数据结构 算法(程序)的组成 什么是数据结构？ 数据结构 研究如何在计算机中表示被处理的对象及对象之间的关系，即如何组织数据。例如： 选择排序中，未排序整数和已排序整数如何表示？ 排序算法中，排序的对象若不是整数而是姓名如何表示？是文件夹中的文件名又如何表示？是表格中