PowerPoint 演示文稿

Size: px

Start display at page:

Download "PowerPoint 演示文稿"

月席
7 years ago
Views:

1 课程性质数据结构是计算机专业的专业基础课公共基础课专业基础课专业方向课专业选修课在教学计划中的地位 : 核心承上启下前导课 : 高等数学离散数学程序设计语言后续课 : 数据库操作系统编译原理属于武术中的练功科目练武不练功, 到头一场空考研 : 专业课必考

2 教学目标掌握基本的数据结构工具箱复用修改重组培养算法设计能力程序设计能力算法程序的灵魂问题求解过程 : 问题想法算法程序程序设计研究的层次 : 算法方法学语言工具培养算法分析能力评价算法改进算法

3 学编程的境界学会写程序学会高效地写程序学会写高效的程序学会设计算法学会设计有用的算法

4 学习要求循序渐进, 切忌心浮气躁提高课外学习的时间和内容理解科学而不是背诵科学读书正确对待考试作习题华罗庚 : 学数学不做习题等于入宝山而空返作实验计算机学科是一门科学性与工程性并重的学科, 表现为理论和实践紧密结合的特征

5 大学生混的最高境界 ( 考试版 ) 人 : 什么? 明天要考高数?? 得道 : 什么? 下节课要考高数?? 入仙 : 什么? 刚才考的是高数?? 成佛 : 什么? 昨天有考试?? 高级佛爷 : 高数? 刚才考的不是英语?? 我寝室一哥们 : 高数是什么树??

6 关于教材主教材严蔚敏. 数据结构. 清华大学出版社辅导及实验教材连远锋, 李国和等. 基于 MFC 的可视化数据结构. 清华大学出版社参考教材 1. 王红梅, 胡明. 数据结构 (C++ 版 ) 第 2 版. 清华大学出版社 2. 张铭. 数据结构与算法. 高等教育出版社曹宏庆译. 如何求解问题. 中国水利水电出版社. 2003

7 如何使用立体化教材主教材辅导教材知识结构学习要点重点难点释疑习题解析实验教材验证实验设计实验综合实验教师用书教学重点教学难点教学设计教案讲稿考研辅导

8 成绩组成平时成绩 20%: 出勤 + 作业 + 报告实验成绩 10%: 出勤 + 程序 + 报告期末考试成绩 70%: 接近同类学校考研水平课程设计成绩 : 优良中及不及

9 第 1 章绪论本章的基本内容是 : 数据结构在程序设计中的作用本书讨论的主要内容数据结构的基本概念算法及算法分析

10 数据结构的创始人克努思 1938 年出生,25 岁毕业于加州理工学院数学系, 博士毕业后留校任教,28 岁任副教授 30 岁时, 加盟斯坦福大学计算机系, 任教授从 31 岁起, 开始出版他的历史性经典巨著 :The Art of Computer Programming, 他计划共写 7 卷, 然而出版三卷之后, 已震惊世界, 使他获得计算机科学界的最高荣誉图灵奖, 此时, 他年仅 36 岁

11 1.1 数据结构在程序设计中的作用程序设计的实质是什么? 数据表示 : 将数据存储在计算机 ( 内存 ) 中数据处理 : 处理数据, 设计方案 ( 算法 ) 数据结构问题起源于程序设计

12 1.1 数据结构在程序设计中的作用利用计算机求解问题的一般过程? 计算机不能分析问题并产生问题的解决方案, 必须由人来分析问题, 确定问题的解决方案, 编写程序, 然后让计算机执行程序最终获得问题的解

13 1.1 数据结构在程序设计中的作用例 1-1 手机电话号码查询问题将电话号码集合组织成线性结构和树结构, 查找操作的效率不同, 当数据量较大时差别就更大

14 1.2 本书讨论的主要内容计算机求解问题 : 问题抽象出问题的模型求模型的解问题数值问题非数值问题数值问题数学方程非数值问题数据结构

15 例 1-2 学籍管理问题 1.2 本书讨论的主要内容完成什么功能? 各表项之间是什么关系?

16 1.2 本书讨论的主要内容例 1-3 人机对弈问题如何实现对弈? 各格局之间是什么关系?

17 例 1-4 七巧板涂色问题 1.2 本书讨论的主要内容如何表示区域之间的邻接关系?

18 1.2 本书讨论的主要内容本书讨论非数值问题的数据组织和处理, 主要内容如下 : (1) 数据的逻辑结构 : 线性表树图等数据结构, 其核心是如何组织待处理的数据以及数据之间的关系 ; (2) 数据的存储结构 : 如何将线性表树图等数据结构存储到计算机的存储器中, 其核心是如何有效地存储数据以及数据之间的逻辑关系 ; (3) 算法 : 如何基于数据的某种存储结构实现插入删除查找等基本操作, 其核心是如何有效地处理数据 ; (4) 常用数据处理技术 : 查找技术排序技术索引技术等

19 1.3 数据结构的基本概念数据结构的基本概念数据 : 所有能输入到计算机中并能被计算机程序识别和处理的符号集合数值数据 : 整数实数等非数值数据 : 图形图象声音文字等数据元素 : 数据的基本单位, 在计算机程序中通常作为一个整体进行考虑和处理数据项学号姓名性别出生日期政治面貌 0001 陆宇男 1986/09/02 团员 0002 李明男 1985/12/25 党员 0003 汤晓影女 1986/03/26 团员数据项 : 构成数据元素的不可分割的最小单位数据元素

20 1.3 数据结构的基本概念数据数据元素数据项之间的关系包含关系 : 数据由数据元素组成, 数据元素由数据项组成数据元素是讨论数据结构时涉及的最小数据单位, 其中的数据项一般不予考虑数据结构数据元素关系

21 1.3 数据结构的基本概念数据结构的基本概念数据结构 : 相互之间存在一定关系的数据元素的集合按照视点的不同, 数据结构分为逻辑结构和存储结构逻辑结构 : 指数据元素之间逻辑关系的整体关联方式或邻接关系学籍管理问题中, 表项之间的逻辑关系指的是什么? 人机对弈问题中, 格局之间的逻辑关系指的是什么? 教学计划编排问题中, 课程之间的逻辑关系指的是什么? 数据的逻辑结构是从具体问题抽象出来的数据模型

22 1.3 数据结构的基本概念数据结构的基本概念数据结构 : 相互之间存在一定关系的数据元素的集合按照视点的不同, 数据结构分为逻辑结构和存储结构逻辑结构 : 指数据元素之间逻辑关系的整体数据的逻辑结构在形式上可定义为一个二元组 : Data_Structure = (D, R) 其中 D 是数据元素的有限集合,R 是 D 上关系的集合

23 1.3 数据结构的基本概念数据结构的基本概念数据结构 : 相互之间存在一定关系的数据元素的集合按照视点的不同, 数据结构分为逻辑结构和存储结构逻辑结构 : 指数据元素之间逻辑关系的整体 Data_Structure = (D, R) 其中 D = {A, B, C, D, E, F, G} R = {R1},R1 = {<A, B>, <A, E>, <A, F>, <B, C>, <B, D>, <C, D>, <D, E>, <D, G>, <E, F>, <E, G>}

24 1.3 数据结构的基本概念数据结构的基本概念数据结构 : 相互之间存在一定关系的数据元素的集合按照视点的不同, 数据结构分为逻辑结构和存储结构逻辑结构 : 指数据元素之间逻辑关系的整体存储结构 : 又称为物理结构, 是数据及其逻辑结构在计算机中的表示内存存储结构实质上是内存分配, 在具体实现时依赖于计算机语言

25 1.3 数据结构的基本概念数据结构的基本概念数据结构从逻辑上分为四类 : ⑴ 集合 : 数据元素之间就是属于同一个集合 ;

26 1.3 数据结构的基本概念数据结构的基本概念数据结构从逻辑上分为四类 : ⑴ 集合 : 数据元素之间就是属于同一个集合 ; ⑵ 线性结构 : 数据元素之间存在着一对一的线性关系 ;

27 1.3 数据结构的基本概念数据结构的基本概念数据结构从逻辑上分为四类 : ⑴ 集合 : 数据元素之间就是属于同一个集合 ; ⑵ 线性结构 : 数据元素之间存在着一对一的线性关系 ; ⑶ 树结构 : 数据元素之间存在着一对多的层次关系 ;

28 1.3 数据结构的基本概念数据结构的基本概念数据结构从逻辑上分为四类 : ⑴ 集合 : 数据元素之间就是属于同一个集合 ; ⑵ 线性结构 : 数据元素之间存在着一对一的线性关系 ; ⑶ 树结构 : 数据元素之间存在着一对多的层次关系 ; ⑷ 图结构 : 数据元素之间存在着多对多的任意关系

29 1.3 数据结构的基本概念数据结构的基本概念通常有两种存储结构 : 1. 顺序存储结构 : 用一组连续的存储单元依次存储数据元素, 数据元素之间的逻辑关系由元素的存储位置来表示例 :(bat, cat, eat) 起始地址 bat cat eat

30 1.3 数据结构的基本概念数据结构的基本概念通常有两种存储结构 : 1. 顺序存储结构 : 用一组连续的存储单元依次存储数据元素, 数据元素之间的逻辑关系由元素的存储位置来表示 2. 链接存储结构 : 用一组任意的存储单元存储数据元素, 数据元素之间的逻辑关系用指针来表示例 :(bat, cat, eat) cat 0325 bat 0200 eat

31 1.3 数据结构的基本概念逻辑结构和存储结构之间的关系数据的逻辑结构属于用户视图, 是面向问题的, 反映了数据内部的构成方式 ; 数据的存储结构属于具体实现的视图, 是面向计算机的一种数据的逻辑结构可以用多种存储结构来存储, 而采用不同的存储结构, 其数据处理的效率往往是不同的

32 抽象数据类型 1.3 数据结构的基本概念 1. 数据类型 (Data Type): 一组值的集合以及定义于这个值集上的一组操作的总称例如 :C++ 中的整型变量 2. 抽象 (Abstract): 抽出问题本质的特征而忽略非本质的细节例如 : 地图驾驶汽车 3. 抽象数据类型 (Abstract Data Type,ADT): 一个数据结构以及定义在该结构上的一组操作的总称

33 抽象数据类型 1.3 数据结构的基本概念在设计 ADT 时, 把 ADT 的定义设计和实现分开来定义部分只包含数据的逻辑结构和所允许的操作集合, 一方面,ADT 的使用者依据这些定义来使用 ADT, 即通过操作集合对该 ADT 进行操作 ; 另一方面,ADT 的实现者依据这些定义来完成该 ADT 各种操作的具体实现

34 抽象数据类型 1.3 数据结构的基本概念 ADT 抽象数据类型名 Data 数据元素之间逻辑关系的定义 Operation 操作 1 前置条件 : 执行此操作前数据所必须的状态输入 : 执行此操作所需要的输入功能 : 该操作将完成的功能输出 : 执行该操作后产生的输出后置条件 : 执行该操作后数据的状态操作 2 操作 n endadt

35 1.3 数据结构的基本概念 ( 小结 ) 数据表示非数值问题数据的逻辑结构数据的存储结构集合线性结构树结构图结构顺序存储链式存储数据的操作 : 插入删除修改检索排序等

36 算法的相关概念 1. 算法 (Algorithm): 是对特定问题求解步骤的一种描述, 是指令的有限序列 2. 算法的五大特性 : 1.4 算法及算法分析 ⑴ 输入 : 一个算法有零个或多个输入 ⑵ 输出 : 一个算法有一个或多个输出 ⑶ 有穷性 : 一个算法必须总是在执行有穷步之后结束, 且每一步都在有穷时间内完成 ⑷ 确定性 : 算法中的每一条指令必须有确切的含义, 对于相同的输入只能得到相同的输出 ⑸ 可行性 : 算法描述的操作可以通过已经实现的基本操作执行有限次来实现

37 例 : 欧几里德算法辗转相除法求两个自然数 m 和 n 的最大公约数 1.4 算法及算法分析 m n 欧几里德算法 ( 有穷性确定性可行性 ) r

38 1.4 算法及算法分析算法的描述方法自然语言优点 : 容易理解缺点 : 冗长二义性使用方法 : 粗线条描述算法思想注意事项 : 避免写成自然段

39 例 : 欧几里德算法 1.4 算法及算法分析自然语言步骤 1: 将 m 除以 n 得到余数 r; 步骤 2: 若 r 等于 0, 则 n 为最大公约数, 算法结束 ; 否则执行步骤 3; 步骤 3: 将 n 的值放在 m 中, 将 r 的值放在 n 中, 重新执行步骤 1;

40 1.4 算法及算法分析算法的描述方法流程图优点 : 流程直观缺点 : 缺少严密性灵活性使用方法 : 描述简单算法注意事项 : 注意抽象层次

41 1.4 算法及算法分析例 : 欧几里德算法流程图开始输入 m 和 n r=m % n r=0 N m=n;n=r 输出 n 结束 Y

42 1.4 算法及算法分析算法的描述方法程序设计语言优点 : 能由计算机执行缺点 : 抽象性差, 对语言要求高使用方法 : 算法需要验证注意事项 : 将算法写成子函数

43 例 : 欧几里德算法程序设计语言 1.4 算法及算法分析 #include <iostream.h> int CommonFactor(int m, int n) { int r = m % n; while (r!= 0) { m = n; n = r; r = m % n; } return n; } void main( ) { cout<<commonfactor(63, 54)<<endl; }

44 算法的描述方法伪代码伪代码 (Pseudocode): 介于自然语言和程序设计语言之间的方法, 它采用某一程序设计语言的基本语法, 操作指令可以结合自然语言来设计优点 : 表达能力强, 抽象性强, 容易理解使用方法 :7 ± 算法及算法分析

45 例 : 欧几里德算法 1. r = m % n; 伪代码 1.4 算法及算法分析 2. 循环直到 r 等于 m = n; 2.2 n = r; 2.3 r = m % n; 3. 输出 n ; 上述伪代码再具体一些, 用 C++ 的函数来描述

46 int CommonFactor(int m, int n) { } r = m % n; while (r!= 0) { m = n; n = r; r = m % n; } return n; 1.4 算法及算法分析对 C++ 语言进行了如下简化 : ⑴ 局部变量可以不声明 ; ⑵ 写出子函数即可, 子函数不用在主函数中调用, 省略主函数 ; ⑶ 所有的包含函数 ( 头函数.h) 可以省略 ; ⑷ 交换两个变量的语句可以简写为 a b

47 算法分析 1.4 算法及算法分析度量算法效率的方法 : 事后统计 : 将算法实现, 测算其时间和空间开销缺点 :⑴ 编写程序实现算法将花费较多的时间和精力 ; ⑵ 所得实验结果依赖于计算机的软硬件等环境因素事前分析 : 对算法所消耗资源的一种估算方法

48 1.4 算法及算法分析算法分析算法分析 (Algorithm Analysis): 对算法所需要的计算机资源时间和空间进行估算时间复杂性 (Time Complexity) 空间复杂性 (Space Complexity)

49 算法分析 1.4 算法及算法分析算法的时间复杂度分析算法的执行时间 = 每条语句执行时间之和每条语句执行次数之和单位时间基本语句的执行次数 for (i=1; i<=n; i++) for (j=1; j<=n; j++) x++; 执行次数执行一次的时间指令系统编译的代码质量

50 算法分析 1.4 算法及算法分析问题规模 : 输入量的多少基本语句 : 是执行次数与整个算法的执行次数成正比的操作指令 for (i=1; i<=n; i++) for (j=1; j<=n; j++) x++; 问题规模 :n 基本语句 :x++

51 算法分析大 O 符号 1.4 算法及算法分析定义若存在两个正的常数 c 和 n 0, 对于任意 n n 0, 都有 T(n) c f(n), 则称 T(n)=O(f(n)) 执行次数 c f(n) T(n) n 0 之前的情况无关紧要 n 0 问题规模 n 当问题规模充分大时在渐近意义下的阶

52 算法分析大 O 符号 1.4 算法及算法分析定理 : 若 A(n)=a m n m +a m-1 n m-1 + +a 1 n+a 0 是一个 m 次多项式, 则 A(n)=O(n m ) 说明 : 在计算算法时间复杂度时, 可以忽略所有低次幂和最高次幂的系数

53 算法分析例 x; 1.4 算法及算法分析例 1-6 for (i=1; i<=n; ++i) ++x; 例 1-7 for (i=1; i<=n; ++i) for (j=1; j<=n; ++j) ++x; 例 1-8 for (i=1; i<=n; ++i) for (j=1; j<=i-1; ++j) ++x;

54 1.4 算法及算法分析算法分析例 1-9 for (i=1; i<=n; ++i) for (j=1; j<=n; ++j) { c[i][j]=0; for (k=1; k<=n; ++k) c[i][j]+=a[i][k]*b[k][j]; } 例 1-10 for (i=1; i<=n; i=2*i) ++x; Ο(1)<(log 2 n)<(n)<(nlog 2 n)<(n 2 )<(n 3 )< <(2 n )<(n!)

55 1.4 算法及算法分析最好情况最坏情况平均情况例 : 在一维整型数组 A[n] 中顺序查找与给定值 k 相等的元素 ( 假设该数组中有且仅有一个元素值为 k) int Find(int A[ ], int n) { for (i = 0; i < n; i++) if (A[i] == k) break; return i; } 基本语句的执行次数是否只和问题规模有关?

56 1.4 算法及算法分析最好情况最坏情况平均情况结论 : 如果问题规模相同, 时间代价与输入数据有关, 则需要分析最好情况最坏情况平均情况最好情况 : 出现概率较大时分析最差情况 : 实时系统平均情况 : 已知输入数据是如何分布的, 通常假设等概率分布

57 本章小结知识结构图绪论数据结构算法基本概念逻辑结构关系存储结构基本概念算法分析 ⑴ 数据 ⑵ 数据元素 ⑶ 数据对象 ⑷ADT ⑴ 逻辑结构 ⑵ 数据结构的分类 ⑴ 存储结构 ⑵ 常用存储方法 ⑴ 算法 ⑵ 算法特性 ⑶ 评价算法 ⑷ 描述算法 ⑴ 问题规模 ⑵ 基本语句 ⑶ 时间复杂度 ⑷ 大 O 记号

数学分析（Ｉ）短课程 [Part 2] 4mm 自然数、整数和有理数

数学分析（Ｉ）短课程 [Part 2] 4mm 自然数、整数和有理数 .. 数学分析 (I) 短课程 [Part 2] 自然数整数和有理数孙伟华东师范大学数学系算子代数中心 Week 2 to 18. Fall 2014 孙伟 ( 数学系算子代数中心 ) 数学分析 (I) 短课程 Week 2 to 18. Fall 2014 1 / 78 3. 自然数理论初步孙伟 ( 数学系算子代数中心 ) 数学分析 (I) 短课程 Week 2 to 18. Fall 2014