专转本计算机第3章3.4_算法和数据结构.ppt

3.4 算法和数据结构 3.4.1 算法 3.4.2 数据结构 3.4.1 算法 1. 什么是算法？ 算法是解决问题的方法与步骤 例：有三个硬币，其中一个是伪造的，另两个是真的，伪币与真币重量略有不同。现在提供一座天平，如何找出伪币呢？ 分析： 方法明确而有序 按提供的条件进行操作 任何人均可仿照进行(共享智能) 关于算法的三方面问题 如何确定算法（算法设计）？ 如何表示算法（算法表示）？ 如何使算法更有效（算法分析）？ 计算机算法的4个特点 目的：完成某个特定的信息处理任务 必须满足的性质： ① 确定性：算法中每一步操作的含义必须清楚明确，无二义性 ② 能行性： 算法中有待实现的操作都是计算机可执行的，即必须在计算机的能力范围之内 ③ 有穷性： 算法在执行了有限步操作后必须结束 ④ 算法结束后至少产生一个输出（包括参量或状态的变化） 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]和[j] ； i = i +1 } 直接选择排序的c语言程序 3. 算法的表示 算法的表示方法 文字说明 流程图表示 伪代码（一种介于自然语言和程序设计语言之间的文字和符号表达工具） 程序设计语言 自然语言描述 “比较Ａ与Ｂ的重量，若Ａ＝Ｂ，则Ｃ是伪造的；否则再比较Ａ与Ｃ的重量，若Ａ＝Ｃ，则Ｂ是伪造的；否则Ａ是伪造的。” 缺点： 容易产生歧义，很难 “精确”地进行表达 叙述冗长，很难清楚地表达算法的逻辑流程 算法的流程图表示 流程图由结点和有向边构成，它描述了算法所执行操作的顺序及执行操作的条件 流程图符号 ： 4. 算法的分析 算法分析的基本内容 正确性：给定有效输入后，经过有限时间的计算，产生正确的输出结果 简单性 算法是否容易理解，是否容易验证其正确性，程序是否容易调试 简单的算法效率不一定高，要在保证一定效率的前提下力求算法简单 时间复杂性(Time Complexity) ： 当问题的规模n充分大时，运行该算法所需要的时间的数量级表示 空间复杂性(Space Complexity) ： 除原始数据之外，额外占用的存储空间的大小 3.4.2 数据结构 算法(程序)的组成 什么是数据结构？ 数据结构 研究如何在计算机中表示被处理的对象及对象之间的关系，即如何组织数据。例如： 选择排序中，未排序整数和已排序整数如何表示？ 排序算法中，排序的对象若不是整数而是姓名如何表示？是文件夹中的文件名又如何表示？是表格中的“行”又如何表示？ Word文档中插入的表格和图片如何表示？ Windows操作系统中菜单如何表示？对话框如何表示？窗口如何表示？ 计算机下棋时，棋盘和棋局如何表示？ 精心设计的数据结构可使算法获得更高的时间效率或空间效率 数据结构的内容 1 数据的抽象(逻辑)结构，即数据结构中包括哪些元素，相互之间有什么关系等。例如： 2. 线性数据结构 举例：线性表(Liner-List) 定义：若干个相同类型的数据元素组成的一个有限序列，其中每个数据元素可由多个数据项组成。表中有且仅有一个开始元素和一个结束元素，且所有元素都最多只有一个直接前趋和一个直接后继 例：考生成绩登记表(table) 线性表的运算(操作) 增加1个新的数据元素 删除1个指定数据元素 查找指定的数据元素 最高分考生 最低分考生 将表中的数据元素排序 对表中的数据进行计算 计算平均分 ··· 3. 非线性数据结构 树(Tree) “树”是一种与线性表不同的数据结构，在树中各数据元素之间的逻辑关系具有层次性 树的数组实现 树的链表实现 树的应用举例： 人-机对弈时棋局变化的数据结构 小 结 1 数据结构研究如何在计算机中描述操作对象和操作对象之间的关系： 所有操作对象在计算机中均表示为某种类型的数据