第3章3.4 算法和数据结构.ppt

文档介绍：算法和数据结构 . 1算法 . 2数据结构 2 算法和数据结构 算法 3 算法和数据结构计算机求解问题的步骤(1) 确定并理解问题; (2) 寻找解决问题的方法与步骤,并将其表示成算法(Algorithm) ; (3) 使用某种程序设计语言描述该算法(编程), 并进行调试; (4) 运行程序,获得问题的解答; (5) 进行评估,改进算法和程序 4 算法和数据结构 1. 什么是算法? 5 算法和数据结构算法是解决问题的方法与步骤?例:有三个硬币,其中一个是伪造的,另两个是真的,伪币与真币重量略有不同。现在提供一座天平, 如何找出伪币呢? ?分析: ?方法明确而有序?按提供的条件进行操作?任何人均可仿照进行(共享智能) 开始 C是伪币 B是伪币 A是伪币 A=B? A=C? 是否否是 6 算法和数据结构关于算法的三方面问题?如何确定算法(算法设计)? ?如何表示算法(算法表示)? ?如何使算法更有效(算法分析)? 7 算法和数据结构 2. 算法设计举例 8 算法和数据结构例:对整数进行排序?问题:任给一组(n个)整数,将它们从小到大进行排序?粗略的思路: ①从所有整数中选一个最小的,作为已排序的第一个数②从剩下未排序整数中选最小的数,添加到已排序整数的后面③反复执行步骤②,直到所有整数都处理完毕?进一步细化: ?把待排序的整数放在一个数组 A中,每个整数是数组 A中的一个元素: A[1], A[2], A[3], ··· ], A[n ], ?排好序的元素在 A的前面部分,无序的元素留在后面,每“循环”一次,有序部分增加 1个元素,无序部分减少 1个元素?每次“循环”只需在数组的无序元素部分选出最小的数?反复进行 n-1 次即可得到排序后的结果 9 算法和数据结构“直接选择排序”算法举例 2345789 第6次循环后,排序结束 2937845 与首元素交换,第 1次循环结束 4937825 数组的初态,全部是未排序元素 4937825 在未排序元素中确定最小数位置 2397845 与首元素交换,第 2次循环结束 2937845 在未排序元素中确定最小数位置 2347895 与首元素交换,第 3次循环结束 2397845 在未排序元素中确定最小数位置 10 算法和数据结构“直接选择排序”算法的描述将原始数据放在数组 A中; 设置 i的初值为 1,循环执行下列操作,直到 i = n : { 确定 A[i ] 到 A[n ]中最小整数的位置,设为 j ; 交换 A[i ]和[j] ; i = i +1 } 原始数据放在数组 A中;令 i=1 确定 A[i ]到 A[n ]中最小整数的位置,设为 j A[i ] 和 A[j ]交换位置 i = i + 1 i = n ? 结束开始用伪代码表示算法用流程图表示算法