算法与数据结构第1章节绪论.ppt

算法与数据结构 主讲人：黄紫成 zicheng12345@163.com 考核方式 平时30%+期末70% 平时如何考核？？ 作业得分：书面作业+上机实验 表现得分：出勤、上机 选用教材 算法与数据结构，宁正元 清华大学出版社 绪论 学习算法与数据结构的意义及要求 算法与数据结构的主要内容 基本术语 算法描述及分析 1.1学习数据结构的意义及要求 意义 1、算法和数据结构是计算机科学的两大支柱 2、数据结构是程序设计的基础 3、数据结构是计算机专业的一门综合性专业基础课 是计算机专业本科生必修课程 是计算机研究生入学考试科目 是软件人员水平考试内容 要求 掌握各类基本数据结构类型和相应的存储结构 提高阅读和编写算法的能力 能针对给定问题，选择相适应的数据结构，并能设计和分析算法 1.2数据结构的主要内容 e.g.1 35001405918765012520080101 350014：邮编 059187650125：固定电话学号 e.g.2 电话号码簿（a1，b1）（ a2，b2 ）（ a3，b3 ）…（ an，bn） 其中： ai为某人姓名，bi为此人的电话号码 要求：设计一个算法，给定某人的姓名时，能查出此人的电话号码 e.g.3 井字棋对弈树 e.g.4 企业员工信息管理系统 设每个员工包含：员工姓名、性别、出生年月、员工编号、工资等 对员工信息常有如下操作： 查找：某人是否是该企业的员工？ 插入：新进员工的信息录入 删除：离职员工或因其他原因不在该公司继 续任职 综上所述：数据结构主要研究内容 数据的各种逻辑结构和物理结构，以及它们之间的相应关系 并对各种结构定义相适应的各种运算 设计出相应的算法 分析算法的效率 常见的数据结构有：数组、栈、队列、表、串、树、图和文件等 1.3算法描述和算法分析 一、算法概述 1、什么是算法? 2、算法解决的问题？ 3、算法的特性 4、算法的表示 二、算法的设计原则 三、算法效率的衡量方法和准则 1、事后统计法 2、事前分析估算法(环路复杂度，时空复杂度) 一、算法概述1、什么是算法？ e.g.求解两个整数的最大公因子的解题步骤 要求解的问题描述为：“给定两个正整数m和n，求它们的最大公因”。 欧几里德当时给出的算法如下： ⑴ 以n除m，并令所得余数为r（必有rn）； ⑵ 若r=0，输出结果n，算法结束；否则继续步骤⑶； ⑶ 令m=n和n=r，返回步骤⑴继续进行。 算法就是求解问题的方法和步骤 算法是为了解决某类问题而规定的一个有限长的操作序列。 《计算机程序的艺术》（ Art of Computer Program）中非形式化的定义是： 一个算法，就是一个有穷规则的集合，其中之规则定义了一个解决某一特定类型问题的运算序列。 例如：排序问题（非降序排列） 输入：n个数组成的序列a1, a2, a3,…an 输出：对输入序列的一个重排 a’1, a’2, a’3,… a’n 其中： a’1≤a’2≤a’3≤… ≤a’n 2、算法解决的问题 因特网（数据传输路径，有哪些信誉好的足球投注网站引擎Search Engine Spider） 电子商务（安全方面——密钥（数值算法、数论知识）） 算法解决的具体的问题 道路交通（确定两个交叉路口间的最短路径） 矩阵乘法顺序（A1A2A3A4A5A6A7） 旅行商问题（Traveling Salesman Problem） 表明算法： 可供选择的方案多 实际应用性强 3、一个算法必须满足以下五个重要特性 1．有穷性 2．确定性 3．可行性 4．有输入 5．有输出 4、算法的表示 自然语言表示 流程图表示 N—S图表示 伪代码表示 程序语言表示 流程图表示 N-S图表示 伪代码表示 Begin(算法开始) Read(m,n) m mod n→r while r≠0 do {n→m r→n m mod n→r } write(n) End(算法结束) 程序语言表示 #include stdio.h main() { int m,n,r; printf(“请输入两个正整数：”)； scanf(“%d%d”,m,n); printf(“\n%d和%d的最大公约数是：”，m,n); r=m