Microsoft PowerPoint - 1绪论.ppt [兼容模式]

Size: px

Start display at page:

Download "Microsoft PowerPoint - 1绪论.ppt [兼容模式]"

清圈冯
5 years ago
Views:

1 1 绪论董洪伟

2 主要内容什么是数据结构定义内容基本术语数据 : 数据对象数据元素数据项数据结构 : 逻辑结构物理结构抽象数据类型定义表示算法和算法分析算法的概念算法复杂度

3 什么是数据结构程序 = 数据结构 + 算法 Pascal 之父,Niklaus Wirth 数据结构 : 问题的数学模型数据表示算法 : 处理问题的策略数据处理程序 : 一组指令数据结构和算法的实现计算机解决问题的步骤 : ( 抽象出 ) 数学模型 ( 设计 ) 求解算法 ( 编制 ) 程序

4 什么是数据结构例 : 学生名单学号姓名性别籍贯年龄张三男北京李斯女上海王武男广州赵柳女香港

5 什么是数据结构例 : 四皇后问题

6 什么是数据结构例 : 城市交通咨询图查询两地的最短路径

7 基本术语数据数据对象数据元素数据项结构逻辑结构物理结构

8 基本术语 : 数据数据所有需输入计算机并被程序所处理的对象的总称例如 : 图书借阅管理系统图书信息 : 登录号书名借阅者编号 001 理论力学高等数学

9 基本术语 : 数据元素数据元素数据的基本单位, 在程序中常作为一个整体考虑和处理一个数据元素 ( 一条记录 ) 登录号书名借阅者编号 001 理论力学高等数学

10 基本术语 : 数据项数据项数据的不可分割的最小单位一个数据元素可由一或多个数据项构成 3 个数据项登录号书名借阅者编号 001 理论力学高等数学

11 基本术语 : 数据项数据对象性质相同的数据元素的集合是数据 ( 全集 ) 的子集教科书登录号书名借阅者编号 001 理论力学高等数学 9001

12 基本术语 : 逻辑结构逻辑结构数据元素间的逻辑关系分类集合 : 同在一个集合中比如同班同学之间

13 基本术语 : 逻辑结构线性结构 : 一个接一个比如学生花名册中的记录之间树形结构 : 一对多比如家谱图形结构 : 多对多比如地图

14 基本术语 : 物理结构物理结构 : 也称存储结构数据元素及其关系在计算机中存储时的关系顺序映象 ( 顺序存储结构 ) 以存储地址的相邻性表示数据元素间的逻辑关系非顺序映象 ( 链式存储结构 ) 通过指示信息表示数据元素间的逻辑关系

15 基本术语 : 物理结构例 : 学生花名册学号姓名性别籍贯年龄张三男北京李斯女上海王武男广州赵柳女香港数据元素之间的逻辑关系 : 线性关系

16 基本术语 : 物理结构顺序存储 : 各个数据元素在计算机中的存储地址也是线性关系, 即连续存放张三男李斯女... 一个数据元素 typedef struct{ string _id,_name; bool boy; }student; student students[60];

17 基本术语 : 物理结构优点 : 随机存取缺点 : 1 数组满时, 无法继续插入学生成绩, 设置较大的数组空间, 又可能会浪费存储空间解决办法 : 动态数组 (malloc,realoc,free) 或 (new,delete) 2 插入删除元素要大量移动记录 17

18 基本术语 : 物理结构链式存储 : 各个数据元素在计算机中的存储位置任意, 通过指针相互连接起来下一个张三节点的地址男下一个李斯节点的地址女 typedef struct{ string _id,_name; bool boy; }student; struct LNode{ student stu; LNode *next; }; 18

19 基本术语 : 物理结构优点 : 插入删除方便, 且只要内存空间够大, 就不会满缺点 : 不能随机存取 19

20 抽象数据类型不考虑数据元素的具体内容以及数据结构的具体实现, 仅仅从抽象的角度描述数据结构的逻辑结构及基本操作的逻辑含义如 : 整数 : 3 不涉及具体是 3 个苹果还是 3 个人. 能进行的运算 : 加减乘除取模手机 : 接打电话上网视频功能, 但不考虑具体哪种或哪个手机... 20

21 抽象数据类型 : 格式说明数据元素的关系及基本操作 ADT Queue{ // 数据元素关系为线形结构操作 : bool EnQueue(Queue &Q,T e); // 进队 bool DeQueue(Queue &Q,T &e); // 出队 bool IsEmpty(Queue Q); // 是空队列吗? int size(queue Q); // 队列中元素个数 }; 21

22 抽象数据类型 void main(){ Queue q; T e,e1,e2; EnQueue(q,e1); EnQueue(q,e2); while(!isempty(q)){ DeQueue(q,e); print(e); } } 22

23 算法和算法分析 : 概念算法 (Algorithm) 算法是对问题求解步骤的描述是指令的有限序列, 其中每条指令表示一或多个操作 23

24 算法和算法分析 : 概念算法的特性一个正确的算法必须满足有穷性 : 算法在执行有穷步后结束, 且每步可在有穷时间内完成确定性 : 每个步骤都有确切的含义, 相同的输入具有相同的执行路径和结果可行性 : 算法中各操作可通过已实现的基本运算执行有限次完成输入 : 零或多个输入输出 : 一或多个输出 24

25 算法和算法分析 : 概念算法设计的要求一个好的算法应当满足 : 正确性 : 算法应能满足具体问题的需求可读性 : 算法应易于阅读和理解健壮性 : 输入数据非法时, 算法也能适当作出反应或进行处理高效性 : 算法执行时间短, 占用存储空间少 25

26 算法和算法分析 : 时间复杂度算法时间效率的量度事后统计法测量一个算法执行所需要的时间缺点 : 需要编写测试程序测量结果依赖于具体的软硬件事前分析估算法 26

27 算法和算法分析 : 时间复杂度事前分析估算法一个程序的执行时间取决于如下因素 : 算法问题的规模编程语言编译程序硬件性能 27

28 算法和算法分析 : 时间复杂度同一个算法在不同的语言编译程序和硬件的条件下, 执行时间是不同的. 所以评价算法的优劣应当排除这三者的影响比如 : 算法 A 在硬件 A 上执行时间为 1 秒, 算法 B 在硬件 B 上执行时间为 2 秒, 并不能因此就认为算法 A 的效率更高因此只需要考虑算法本身和问题的规模 28

29 算法和算法分析 : 时间复杂度渐进时间复杂度 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]; } 基本操作 : c[i][j]+= a[i][k]*b[k][j] 其执行次数 F = n 3 整个程序的执行时间和 F 成正比 29

30 算法和算法分析 : 时间复杂度渐进时间复杂度在算法中选择一种基本操作用该基本操作的重复次数表示算法的执行时间, 一般为问题规模 n 的函数 f(n) 此时可记算法的时间量度为 :T(n)=O( f(n) ) 30

31 算法和算法分析 : 时间复杂度例 1 for(i=2; i<=n; ++i) for(j=2; j<=i-1; ++j) { ++x; a[i][j] = x; } 基本操作 ++x 的执行次数 2 ( n 1)( n 2) n 3n + 2 = = 2 2 因此渐进复杂度 =O(n 2 ) i=2: 0 次 i=3: 1 次... i=n: n-2 次 31

32 例 2 for(i = 1; i <= n; i ++) { m = i; for(j = i; j <= n; j ++) { if(data[j] < data[m]) m = j; 执行次数 =n, T(n)=O(n) 执行次数都是 n(n+1)/2, T(n)=O(n 2 ) } } if(m!= i) { temp = data[m]; data[m] = data[i]; data[i] = temp; } 对于整个算法,T(n)=O(n 2 +n)=o(n 2 ) 32

33 矩阵运算的复杂度 a=(a 1,a 2,...a n ) T,b=(b 1,b 2,...b n ) T 是 n 维向量, 则点积 a T b=a 1 b 1 +a 2 b a n b n. 需要 2n-1(flops)=n( 次乘法 )+(n-1)( 次加法 ) 设 A 是 mxn 矩阵,x 是 n 维向量, 则 Ax 是一个 m 维向量, 每个元素由 A 的一行向量和 x 点乘得到需要 m(2n-1) (flops) 设 A 是 mxn 矩阵, B 是 nxp 矩阵, 则 AB 是 mxp 矩阵, 每个元素由 A 的一行和 B 的一列两个 n 维向量点乘得到需要 mp(2n-1) (flops) 33

34 例 3 (AB)x? A(BX) 那种方式更快? A 是 mxn 矩阵, B 是 nxp 矩阵, 则 AB 是 mxp 矩阵,x 是 px1 矩阵. AB: mp(2n-1) (AB)x: mp(2n-1) + m(2p-1) Bx: n(2p-1) A(BX): n(2p-1) + m(2n-1) 34

35 例 3 (AB)x? A(BX) 那种方式更快? 35

36 例 4 Forward substitution 36

37 算法和算法分析 : 时间复杂度各种常见的渐进复杂度 a n >n b >log c n 37

38 算法和算法分析 : 空间复杂度空间复杂度空间复杂度是算法执行时所需存储空间的量度, 记作 S(n), 其中 n 为问题的规模一般不考虑存放数据本身占用的空间, 只考虑执行算法所需辅助空间, 除非数据所占空间与算法本身有关 38

39 算法和算法分析有些算法的复杂度与输入数据有关比如气泡排序, 当输入数据基本有序时, 其时间复杂度为 O(n), 基本无序时, 为 O(n 2 ), 平均为 O(n 2 ) 此时就应该分最好情况最差情况平均情况来讨论 39

40 本章小结基本概念了解算法复杂度的量度掌握量度和表示的方法 40

41 附录 : 冒泡排序示意图 41

42 附录 : 冒泡排序示意图 42

43 附录 : 一些约定数据元素类型一律用 Type 或 ElemType. typedef int Status; #define OK 0 #define Error 1 #define NoMemory 2 #define OVERFLOW 3 43

44 作业 1. 设 n 是偶数, 试计算运行下列程序段后 m 的值并给出该程序段的时间复杂度 ( 答案 : 频度为 n^2/4) m=0; for( i=1 ; i<= n ; i++ ) for( j=2*i ;j<= n ;j++ ) m=m+1; 2. 从逻辑上可以把数据结构分为 ( ) 两大类 A. 动态结构静态结构 B. 顺序结构链式结构 C. 线性结构非线性结构 D. 初等结构构造型结构 3. 什么叫顺序映像? 链式映像能用数组表示吗? 44

Microsoft PowerPoint - ds-1.ppt [兼容模式]

Microsoft PowerPoint - ds-1.ppt [兼容模式] http://jwc..edu.cn/jxgl/ HomePage/Default.asp 2 说明总学时 : 72( 学时 )= 56( 课时 )+ 16( 实验 ) 行课时间 : 第 1 ~14 周周学时 : 平均每周 4 学时上机安排待定考试时间 : 课程束第 8 11 12 章的内容为自学内容 ; 目录中标有