PowerPoint Presentation

Size: px

Start display at page:

Download "PowerPoint Presentation"

反柳
5 years ago
Views:

1 数据结构与算法 ( 一 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社, ( 十一五国家级规划教材 )

2 第 1 章概论问题求解数据结构及抽象数据类型算法的特性及分类算法的效率度量数据结构的选择和评价 2

3 1.1 问题求解问题求解设计方法编写计算机程序的目的? 解决实际的应用问题问题抽象分析和抽象任务需求, 建立问题模型数据抽象确定恰当的数据结构表示数学模型算法抽象在数据模型的基础上设计合适的算法数据结构 + 算法, 进行程序设计模拟和解决实际问题算法理论数据结构数据模型描述语言 3

4 1.1 问题求解农夫过河菜羊狼 4

5 1.1 问题求解问题抽象 : 人狼羊菜乘船过河 - 只有人能撑船 - 船只有两个位置 ( 包括人 ) - 狼羊羊菜不能在没有人时共处数据抽象 : 图模型 - 不合理状态 : 狼羊人菜羊菜人狼狼羊菜人 - 顶点表示原岸状态 10 种 ( 包括空 ) - 边 : 一次合理的渡河操作实现的状态转变人羊狼菜人狼菜人羊狼人羊菜人羊 ( 人羊狼菜 ) 狼菜 ( 人狼菜 ) 菜 ( 人羊菜 ) 羊 ( 人羊 ) 空农夫过河人羊人狼人羊人菜人人羊人 ( 人羊菜 ) 羊 ( 人羊狼 ) 狼 ( 人狼菜 ) 狼菜 ( 人狼菜 ) 人羊狼菜狼菜狼菜羊空 ( 成功 ) 5

6 1.1 问题求解农夫过河数据结构 - 相邻矩阵算法抽象 : - 最短路径人羊狼菜人狼菜人羊狼人羊菜人羊狼菜狼菜羊空 ( 成功 ) 6

7 1.1 问题求解农夫过河问题最短路径模型问题抽象? 数据抽象? 算法抽象? 不妨编程序模拟实现还有其他模型吗? 思考 : 问题求解过程 7

8 第 1 章概论问题求解数据结构及抽象数据类型算法的特性及分类算法的效率度量数据结构的选择和评价 8

9 1.2 什么是数据结构结构 : 实体 + 关系数据结构 : 按照逻辑关系组织起来的一批数据, 按一定的存储方法把它存储在计算机中逻辑数据结构运算存储在这些数据上定义了一个运算的集合 9

10 1.2 什么是数据结构数据结构的逻辑组织线性结构线性表 ( 表, 栈, 队列, 串等 ) 非线性结构树 ( 二叉树,Huffman 树, 二叉检索树等 ) 图 ( 有向图, 无向图等 ) 图树二叉树线性表

11 1.2 什么是数据结构数据的存储结构逻辑结构到物理存储空间的映射内存 0 计算机主存储器 ( 内存 ) 非负整数地址编码, 相邻单元的集合基本单位是字节访问不同地址所需时间基本相同 ( 即随机访问 ) x A M-1 11

12 1.2 什么是数据结构数据的存储结构对逻辑结构 (K,r), 其中 r R 对结点集 K 建立一个从 K 到存储器 M 的单元的映射 :K M, 对于每一个结点 j K 都对应一个唯一的连续存储区域 c M int a[3] a[0] a[1] a[2] 存储映射内存 12

13 1.2 什么是数据结构数据的存储结构关系元组 (j 1, j 2 ) r ( 其中 j 1, j 2 K 是结点 ) 顺序 : 存储单元的顺序地址 S 链接 : 指针的地址指向关系四类 : 顺序链接索引散列 13

14 1.2 什么是数据结构抽象数据类型简称 ADT (Abstract Data Type) 定义了一组运算的数学模型与物理存储结构无关逻辑数据结构存储使软件系统建立在数据之上 ( 面向对象 ) 运算模块化的思想的发展隐藏运算实现的细节和内部数据结构软件复用 14

15 void BracketMatch(char *str) { Stack<char> S; int i; char ch; // 栈可以是顺序或链式的, 都一样引用 for(i=0; str[i]!='\0'; i++) { switch(str[i]) { case '(': case '[': case '{': S.Push(str[i]); break; case ')': case ']': case '}': if (S.IsEmpty( )) { cout<<" 右括号多余!"; return; } else { 1.2 什么是数据结构 ADT 不关心存储细节例,C++ 版本括号匹配算法 } ch = S.GetTop( ); if (Match(ch,str[i])) ch = S.Pop( ); else { cout << " 括号不匹配!"; return; } } /*else*/ }/*switch*/ }/*for*/ if (S.IsEmpty( )) cout<<" 括号匹配!"; else cout<<" 左括号多余 " ; 15

16 什么是数据结构 C 的顺序栈括号匹配算法 ( 与链式略不同 ) void BracketMatch(char *str) { SeqStack S; int i; char ch; InitStack(&S); for(i=0; str[i]!='\0'; i++) { switch(str[i]) { case '(': case '[': case '{': Push(&S,str[i]); break; case ')': case ']': case '}': if (IsEmpty(&S)) { printf("\n 右括号多余!"); return; } else { GetTop (&S,&ch); if (Match(ch,str[i])) Pop(&S,&ch); else { printf("\n 括号不匹配!"); return; } } /*else*/ }/*switch*/ }/*for*/ if (IsEmpty(&S)) printf("\n 括号匹配!"); else printf("\n 左括号多余 " ); }

17 什么是数据结构 C 的链式栈括号匹配算法 ( 与顺序栈不同 ) void BracketMatch(char *str) { LinkStack S; int i; char ch; InitStack(/*&*/S); for(i=0; str[i]!='\0'; i++) { switch(str[i]) { case '(': case '[': case '{': Push(/*&*/S, str[i]); break; case ')': case ']': case '}': if (IsEmpty(S)) { printf("\n 右括号多余!"); return; } else { GetTop (/*&*/S,&ch); if (Match(ch,str[i])) Pop(/*&*/S,&ch); else { printf( \n 括号不匹配!"); return; } } /*else*/ }/*switch*/ }/*for*/ if (IsEmpty(/*&*/S)) printf("\n 括号匹配!"); else printf("\n 左括号多余 " ); }

18 1.2 什么是数据结构抽象数据类型 ADT 抽象数据结构二元组 < 数据对象 D, 数据操作 P> 先定义逻辑结构, 再定义运算逻辑结构 : 数据对象及其关系运算 : 数据操作 18

19 1.2 什么是数据结构出栈进栈例 : 栈的抽象数据类型 ADT 逻辑结构 : 线性表操作特点 : 限制访问端口只允许在一端进行插入删除操作入栈 ( push ) 出栈 (pop) 取栈顶 ( top ) 判栈空 ( isempty ) template <class T> class Stack { public: void clear(); bool push(const T item); bool pop(t & item); bool top(t& item); bool isempty(; bool isfull(); }; // 栈的元素类型为 T // 栈的运算集 // 变为空栈 // item 入栈, 成功返回真, 否则假 // 弹栈顶, 成功返回真, 否则返回假 // 读栈顶但不弹出, 成功真, 否则假 // 若栈已空返回真 // 若栈已满返回真栈顶栈底 K i+1 K i... k 1 k 0 19

20 1.2 什么是数据结构思考 : 关于抽象数据类型 ADT 怎么体现逻辑结构? 抽象数据类型等价于类定义? 不用模板来定义可以描述 ADT 吗? 20

21 目录页大纲 1.3 算法第 1 章概论问题求解数据结构及抽象数据类型算法的特性及分类算法的效率度量 21

22 1.3 算法问题算法程序目标 : 问题求解问题 (problem) 一个函数从输入到输出的一种映射算法 (algorithm) 一种方法对特定问题求解过程的描述, 是指令的有限序列程序 (program) 是算法在计算机程序设计语言中的实现 22

23 1.3 算法算法的特性通用性对参数化输入进行问题求解保证计算结果的正确性有效性算法是有限条指令组成的指令序列即由一系列具体步骤组成确定性算法描述中的下一步应执行的步骤必须明确有穷性算法的执行必须在有限步内结束换句话说, 算法不能含有死循环 Q Q Q Q 23

24 Q 第一章 Q Q Q 1.3 算法皇后问题 ( 四皇后 ) 解 <x1,x2,x3,x4>( 放置列号 ) 搜索空间 :4 叉树 ( 排列树 ) 1 X 1 = X 2 = X 3 = X 4 =

25 1.3 算法基本算法分类穷举法顺序找 K 值回溯搜索八皇后树和图遍历递归分治二分找 K 值快速排序归并排序贪心法 Huffman 编码树最短路 Dijkstra 算法最小生成树 Prim 算法动态规划最短路 Floyd 算法 25

26 template <class Type> class Item { private: Type key; public: Item(Type value):key(value) {} Type getkey() {return key;} 26 顺序找 k 值 // 关键码域 // 其它域 // 取关键码值 void setkey(type k){ key=k;} // 置关键码 }; vector<item<type>*> datalist; template <class Type> int SeqSearch(vector<Item<Type>*>& datalist, int length, Type k) { int i=length; } 1.3 算法 datalist[0]->setkey (k); while(datalist[i]->getkey()!=k) i--; return i; // 将第 0 个元素设为待检索值, 设监视哨 // 返回元素位置

27 1.3 算法二分法找 k 值对于已排序顺序线性表数组中间位置的元素值 k mid 如果 k mid = k, 那么检索工作就完成了当 k mid > k 时, 检索继续在前半部分进行相反地, 若 k mid < k, 就可以忽略 mid 以前的那部分, 检索继续在后半部分进行快速 k mid = k 结束 K mid k 起码缩小了一半的检索范围 27

28 二分法找 k 值 template <class Type> int BinSearch (vector<item<type>*>& datalist, int length, Type k){ int low=1, high=length, mid; while (low<=high) { mid=(low+high)/2; } if (k<datalist[mid]->getkey()) high = mid-1; // 右缩检索区间 else if (k>datalist[mid]->getkey()) low = mid+1; // 左缩检索区间 else return mid; // 成功返回位置 } return 0; // 检索失败, 返回算法

29 1.3 算法二分法检索图示 low mid high 检索关键码 18 low=1 high=9 K=18 第一次 :mid=5; array[5]=35>18 high=4; (low=1) 第二次 :mid=2; array[2]=17<18 low=3; (high=4) 第三次 :mid=3; array[3]=18=18 mid=3;return 3 29

30 1.3 算法思考 : 算法的时空限制设计一个算法, 将数组 A(0..n-1) 中的元素循环右移 k 位, 假设原数组序列为 a 0, a 1,, a n-2,a n-1 ; 移动后的序列为 a n-k, a n-k+1,, a 0, a 1,, a n-k-1 要求只用一个元素大小的附加存储, 元素移动或交换次数与 n 线性相关例如,n=10, k=3 原始数组 : 右移后的 : i-k i i+k 30

31 目录页大纲 1.4 算法复杂性分析第 1 章概论问题求解数据结构及抽象数据类型算法的特性及分类算法的效率度量 31

32 1.4 算法复杂性分析算法的渐进分析 2 f (n) n 100n log10 n 1000 数据规模 n 逐步增大时, f(n) 的增长趋势当 n 增大到一定值以后, 计算公式中影响最大的就是 n 的幂次最高的项其他的常数项和低幂次项都可以忽略 32

33 1.4 算法复杂性分析算法渐进分析 : 大 O 表式法函数 f,g 定义域为自然数, 值域非负实数集定义 : 如果存在正数 c 和 n 0, 使得对任意的 n n 0, 都有 f(n) cg(n), 称 f(n) 在集合 O(g(n)) 中, 简称 f(n) 是 O(g(n)) 的, 或 f(n) = O(g(n)) 大 O 表示法 : 表达函数增长率上限一个函数增长率的上限可能不止一个当上下限相同时则可用表示法 33

34 f(n) = O(g(n)), 当且仅当 1.4 算法复杂性分析大 O 表示法存在两个参数 c > 0,n 0 > 0, 对于所有的 n n 0, 都有 f(n) cg(n) iff c, n 0 > 0 s.t. n n 0 : 0 f(n) cg(n) cg(n) n 足够大 g(n) 是 f(n) 的上界 f(n) 34 n 0 n

35 1.4 算法复杂性分析大 O 表示法的单位时间简单布尔或算术运算简单 I/O 指函数的输入 / 输出例如, 从数组读数据等操作不包括键盘文件等 I/O 函数返回 35

36 加法规则 : f 1 (n)+f 2 (n)=o(max(f 1 (n), f 2 (n))) 顺序结构,if 结构,switch 结构乘法规则 : f 1 (n) f 2 (n) =O(f 1 (n) f 2 (n)) for, while, do-while 结构 for (i=0; j<n; i++) for (j=i; j<n; j++) k++; 1.4 算法复杂性分析大 O 表示法的运算法则 n n i 2 n 1 n n 2 O n n 1 n i i 0 2 2? 36

37 1.4 算法复杂性分析算法渐进分析 : 大表式法定义 : 如果存在正数 c 和 n 0, 使得对所有的 n n 0, 都有 f(n) cg(n), 则称 f(n) 在集合 (g(n)) 中, 或简称 f(n) 是 (g(n)) 的, 或 f(n) = (g(n)) 大 O 表示法和大表示法的唯一区别在于不等式的方向而已采用大表示法时, 最好找出在函数增值率的所有下限中那个最紧 ( 即最大 ) 的下限 37

38 1.4 算法复杂性分析 f(n) = (g(n)) 大表示法 iff c, n 0 > 0 s.t. n n0, 0 cg(n) f(n) 与大 O 表示法的唯一区别在于不等式的方向 f(n) n 足够大 g(n) 是 f(n) 的下界 cg(n) n 0 n 38

39 1.4 算法复杂性分析算法渐进分析 : 大表式法当上下限相同时则可用表示法定义如下 : 如果一个函数既在集合 O (g(n)) 中又在集合 (g(n)) 中, 则称其为 (g(n)) 也即, 当上下限相同时则可用大表示法存在正常数 c 1, c 2, 以及正整数 n 0, 使得对于任意的正整数 n > n 0, 有下列两不等式同时成立 : c 1 g(n) f(n) c 2 g(n) 39

40 f(n) = (g(n)) 1.4 算法复杂性分析大表示法 iff c 1, c 2, n 0 > 0 s.t. 0 c 1 g(n) f(n) c 2 g(n), n n 0 上下限相同, 则可用表示法 c 2 g(n) n 足够大 f(n) 与 g(n) 增长率一样 f(n) c 1 g(n) n 0 40 n

41 f(n) 第一章 f(n) 算法复杂性分析增长率函数曲线 2 n n nlog 2 n n 41 n n log 2 n

42 1.4 算法复杂性分析问题空间 vs 时间开销时间代价最坏平均问题的输入数据空间最坏情况不好不坏情况的数据空间最好情况最佳规模 n 42

43 1.4 算法复杂性分析顺序找 k 值顺序从一个规模为 n 的一维数组中找出一个给定的 K 值最佳情况数组中第 1 个元素就是 K 只要检查一个元素最差情况 K 是数组的最后一个元素检查数组中所有的 n 个元素 43

44 1.4 算法复杂性分析如果等概率分布顺序找 k 值平均情况 - K 值出现在 n 个位置上概率都是 1/n 则平均代价为 O(n) n n n

45 1.4 算法复杂性分析概率不等顺序找 k 值平均情况出现在第 1 个位置的概率为 1/2 第 2 个位置上的概率为 1/4 出现在其他位置的概率都是 1 1/ 2 1/ n (n 2) 平均代价为 O(n) n n(n 1) 6 n (n 2) 8(n 2)

46 1.3 算法二分法找 k 值对于已排序顺序线性表数组中间位置的元素值 k mid 如果 k mid = k, 那么检索工作就完成了当 k mid > k 时, 检索继续在前半部分进行相反地, 若 k mid < k, 就可以忽略 mid 以前的那部分, 检索继续在后半部分进行快速 k mid = k 结束 K mid k 起码缩小了一半的检索范围 46

47 最大检索长度为失败的检索长度是或 log( 2 n 1 ) log( 2 n 1 ) log 2 ( n 1 ) 平均检索代价为在算法复杂性分析中 log n 是以 2 为底的对数以其他数值为底, 算法量级不变算法复杂性分析二分法检索性能分析 O(log n) low mid high

48 1.4 算法复杂性分析数据结构时间 / 空间权衡一定的空间来存储它的每一个数据项一定的时间来执行单个基本操作代价和效益空间和时间的限制软件工程 48

49 1.4 算法复杂性分析时空权衡增大空间开销可能改善算法的时间开销可以节省空间, 往往需要增大运算时间 49

50 1.4 算法复杂性分析仔细分析所要解决的问题数据结构和算法的选择特别是求解问题所涉及的数据类型和数据间逻辑关系问题抽象数据抽象数据结构的初步设计往往先于算法设计注意数据结构的可扩展性考虑当输入数据的规模发生改变时, 数据结构是否能够适应求解问题的演变和扩展 50

51 1.4 算法复杂性分析问题求解的目标? 思考 : 数据结构和算法的选择数据结构与算法选择的过程? 51

52 1.4 算法复杂性分析思考 : 数据结构的三要素以下哪几种结构是逻辑结构, 而与存储和运算无关 ( ) A. 顺序表 B. 散列表 C. 线性表 D. 单链表下面术语 ( ) 与数据的存储结构无关 A. 顺序表 B. 链表 C. 队列 D. 循环链表 52

53 数据结构与算法谢谢聆听国家精品课数据结构与算法张铭, 王腾蛟, 赵海燕高等教育出版社, 十一五国家级规划教材

PowerPoint Presentation

PowerPoint Presentation 数据结构与算法 ( 六 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg 第 6 章树 C 树的定义和基本术语树的链式存储结构子结点表表示方法静态左孩子 / 右兄弟表示法动态表示法动态左孩子 / 右兄弟表示法父指针表示法及其在并查集中的应用