第1章 算法与程序.ppt

算法与数据结构
1/5/2018
1
数据结构课程地位
数据结构与其它课程关系图:
数据结构
数据库
人工智能
专业基础课
操作系统
编译原理
非线性程序设计
离散数学
语言程序设计
计算机原理设计
1/5/2018
2
数据结构课程地位
算法+数据结构=程序
例:火车调度问题
1/5/2018
3
参考书籍
《数据结构(C语言版)》严蔚敏
《C程序设计(第三版)》谭浩强
1/5/2018
4
课程安排
本课程理论教学50学时,实践教学20学时,共70学时,实验为五个实验
序号
实验项目名称
实验学时
实验类型
一
线性表及其应用(多项式相加、相乘)
4
验证
二
哈夫曼树及哈夫曼编码译码的实现
4
验证
三
Dijkstra最短路径或
Prim最小生成树
4
验证
四
i检索算法
4
验证
五
快速、堆、基数排序算法的设计
4
综合
1/5/2018
5
第一章算法与程序
1/5/2018
6
第1章算法与程序
  算法的基本概念
算法的表示
  算法的设计与评价
  算法与程序
1/5/2018
7
算法的基本概念

算法是求解问题的方法和步骤。
定义了这样机械的步骤后,就可以交给机器处理
1/5/2018
8

例:求解两个正整数m和n的最大公因子的欧几里德算法。
①以n除m,并令所得余数为r(必有r<n)。
②若r为0,输出结果n,算法结束;否则继续步骤③。
③令m=n,n=r,返回步骤①,继续进行。
思考:最小公倍数该如何计算?
1/5/2018
9
算法的基本特性
输入: 有多个或0个输入
输出: 至少有一个或多个输出。
确定性:算法中的每一个步骤必须有确定含义,无二义性得以实现。
有穷性:有限步骤之内正常结束,不能形成无穷循环
有效性:即算法的可行性,所描述的操作都是建立在可以通过、已经实现的基本运算的基础上。
1/5/2018
10