文档介绍：算法和数据结构
第一页，共三十九页。
算法和数据结构
第二页，共三十九页。
算法
第三页，共三十九页。
计算机求解问题的步骤
(1) 确定并理解问题；
(2) 寻找解决问题的方法与步骤，并将其表示
比文字描述简明，但当算法比较复杂时，理解困难，容易产生错误
端点符
处理
判断
预定义功能
原始数据放在
数组A中；令 i=1
确定A[i]到A[n]中最
小整数的位置,设为j
A[i] 和A[j]交换位置
i = i + 1
i = n ?
结束
开始
第十六页，共三十九页。
求最大公约数的伪代码表示
算法3：辗转相除法求最大公约数
BEGIN
input m,n; /*输入正整数m和n*/
do
{
r←m mod n;
m ← n; n ← r;
} while r≠0;
print m； /*输出最大公约数*/
END
Y
N
r不等于0?
输出m的值
输入正整数m和n
开始
结束
r←m被n除的余数
m ← n; n ← r
第十七页，共三十九页。
4. 算法的分析
第十八页，共三十九页。
算法分析的基本内容
正确性：给定有效输入后，经过有限时间的计算，产生正确的输出结果
简单性
算法是否容易理解，是否容易验证其正确性，程序是否容易调试
简单的算法效率不一定高，要在保证一定效率的前提下力求算法简单
时间复杂性(Time Complexity) ：
当问题的规模n充分大时，运行该算法所需要的时间的数量级表示
空间复杂性(Space Complexity) ：
除原始数据之外，额外占用的存储空间的大小
第十九页，共三十九页。
选择排序算法的时间复杂性
假设参加排序的整数有n个
（1）比较操作的次数：
在第i趟排序中选出最小整数时，需做n-i次比较操作，
因此，总的比较操作次数为：n(n-1)/2 = (n2 -n)/2
（2）移动操作的次数：
最好情况(原始数据已经排序)时，移动次数为0 最坏情况(原始数据逆序排列)时，每趟均要执行交换操作(3次传送)，总的移动次数取最大值为：3(n-1)
所以，直接选择排序的时间复杂性 为 O(n2)
设置i的初值为1，循环执行下列操作，直到I = n ：
{ 确定A[i] 到A[n]中最小的整数元素的位置，设为j ；
交换A[i]和[j] ；
i = i +1
}
第二十页，共三十九页。
4. 小结
第二十一页，共三十九页。
计算机中处处是算法！
例1：Word程序如何在文档中查找用户指定的词语？
例2：在Word文档的表格中如何将表格内容排序？
例3：如何把一幅彩色图片转换为灰度(黑白)图片？
例4： Windows如何在硬盘中找到用户指定的文件？
例5：媒体播放器如何把MP3文件转换成动听的音乐？
例6：搜索引擎如何在WWW网中找到用户需要的网页？
第二十二页，共三十九页。
算法是计算机软件的灵魂
计算机的通用性是因为它能运行各种各样的程序，而程序之所以能解决问题，是因为它所体现了正确的算法
算法所解决的是一类问题而不是一个特定的问题，例如
排序(sort) 可以是表格内容的排序，也可以是文件夹中文件的排序，可以按数字或文字排序，也可以按日期排序，等等
查找(search)， 可以在文档中查找某个单词或在硬盘中查找某个文件，也可在Web上查找某个网页，等等
开发计算机应用的核心是：根据实际问题给出解题的算法，然后再将该算法在计算机上实现(即开发成为软件)
第二十三页，共三十九页。
计算机算法的4个特点
目的：完成某个特定的信息处理任务
必须满足的性质：
① 确定性：算法中每一步操作的含义必须清楚明确，无二义性
② 能行性： 算法中有待实现的操作都是计算机可执行的，即必须在计算机的能力范围之内，且在有限时间内能够完成
③ 有穷性： 算法在执行了有限步操作后必须结束
④ 算法结束后至少产生一个输出（包括参量或状态的变化）
第二十四页，共三十九页。
数据结构
第二十五页，共三十九页。
算法(程序)的组成
算法(程序) 由2个部分组成：
进行的操作
所涉及的操作对象(数据)
算法
操作对象
操作步骤与条件
程序
说明所要处理的数据的名字和类型
描述所要执行的算法
说 明 语 句
命 令 语 句
第二十六页，共三十九页。
什么是数据结构？
数据结构 研究如何在计算机中表示被处理的对象及对象之间的关系，