数据结构与算法实习 一数据结构设计技巧之 此京太骨信息学載木学院 主讲铭、部丹 zhang [at] net. pku. edu. cn http://www.jpk.pku,educn/pkujpk/course/sjjg/shixi/ 2011.8 张铭赵海糞王膳姣宋迄,《数据构与算法实 验永程》(家十一五舰划激材)高教社2011年1月
数据结构与算法实习 ——数据结构设计技巧之一 北京大学信息科学技术学院 主讲：张 铭、郝 丹 mzhang [at] net.pku.edu.cn http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/shixi/ 2011.8 张铭 赵海燕 王腾蛟 宋国杰，《数据结构与算法实 验教程》（国家十一五规划教材），高教社2011年1月
重点火纲 口1.数据结构与算法的知识体系 口2时间空间代价分析和权衡 日3.KMP算法的灵活应用 口4. Huffman树的灵活应用 日7.观察森林的角度 8.树/森林和二叉树的顺序表示 国题量大、覆盖面广,要全面复习、透彻理解 灵活应用、快速答卷
重点大纲 1. 数据结构与算法的知识体系 2. 时间空间代价分析和权衡 3. KMP算法的灵活应用 4. Huffman树的灵活应用 5. 带返回值的二叉树递归算法 6. 二叉树与栈 7. 观察森林的角度 8. 树/森林和二叉树的顺序表示 题量大、覆盖面广，要全面复习、透彻理解、 灵活应用、快速答卷
1.数据结构的三个基本要素 口数据的逻辑结构 ■图树二又树线性表 数据的存储结构 逻 存 ■索引方法、散列方法 辑数据储 结构 ∏数据的运算 ■增、删、查、改排序、检索 运算 +一依规数也是王线零x,《物不故索盐们,,m滤亲
“十一五”国家级规划教材。张铭，赵海燕，王腾蛟，宋国杰，《数据结构与算法实验教程》，高教社，2010.12 1. 数据结构的三个基本要素 数据的逻辑结构 ◼ 图树二叉树线性表 数据的存储结构 ◼ 顺序方法、链接方法 ◼ 索引方法、散列方法 数据的运算 ◼ 增、删、查、改、排序、检索 存 数据 储 结构 逻 辑 运 算
数据结构与算法体条图 前沿应用:后缀树、 XML DOM树、搜索引擎… 抽象数据类型ADT 算法分析 时空折衷 基础: 逻辑 算 存储 理论抽象设 线性(表、栈、 排序:插入、分治 顺序、链接、 队列、串) 快速、堆、基数 散列、索引 树(二叉树、森 检索:二分、散列 内存、外存 林) 图(有向、无 向、DAG) 索引:BsT、B+ 外排序 B+树,倒排 计 扩展研究:外排序,广义表,稀疏矩阵,字符树 Patricia树,AVL,红黑树,伸展树
“十一五”国家级规划教材。张铭，赵海燕，王腾蛟，宋国杰，《数据结构与算法实验教程》，高教社，2010.12 索引： BST、B+ 扩展研究: 逻辑 运算 存储 线性（表、栈、 队列、串） 树(二叉树、森 林) 图（有向、无 向、DAG） 排序：插入、分治 、快速、堆、基数 检索: 二分、散列 内存、外存 外排序 B+树，倒排 理 论 前沿应用： 后缀树、 XML DOM树、搜索引擎…... 数据结构与算法体系图 抽象数据类型ADT 算法分析 时空折衷 抽 象 设 计 顺序、链接、 散列、索引 外排序，广义表，稀疏矩阵，字符树， Patricia树，AVL， 红黑树，伸展树 …… 基础:
规定财间内能解决的问题规模 口假设CPU每秒处理106个指令,则每小 时能够解决的最大问题规模 T(n)106≤3600 口对T(n)=2n2, 即2n2≤3600×106 ■n≤42,426 口T(n)= nlogn ■即nogn≤3600×10 ■n<133,000,000 +一依规数也是王线零x,《物不故索盐们,,m滤亲
“十一五”国家级规划教材。张铭，赵海燕，王腾蛟，宋国杰，《数据结构与算法实验教程》，高教社，2010.12 规定时间内能解决的问题规模 假设CPU每秒处理106 个指令，则每小 时能够解决的最大问题规模 ◼ T(n)/106 3600 对T(n) = 2n2 ， ◼ 即 2n2 3600 106 ◼ n 42 , 426 T(n) = nlogn ◼ 即 nlogn 3600 106 ◼ n 133 , 000 , 000
快10倍的计算机所能解决的问题规模? T(n Che lange n'/n 10n 100010000 n'′=10n 10 20n 5005000 n′=10n 10 5 n log n2501.842√10n<n'<10n7.37 2n2 70 223 n"'=y10n 3.16 2 13 16 n'=n+3 +一依规数也是王线零x,《物不故索盐们,,m滤亲
“十一五”国家级规划教材。张铭，赵海燕，王腾蛟，宋国杰，《数据结构与算法实验教程》，高教社，2010.12 快10倍的计算机所能解决的问题规模? 2 13 16 n ’ = n + 3 ----- n 2n 2 70 223 n ’ = 10n 3.16 5n log n 250 1,842 10 n < n ’ < 10n 7.37 20n 500 5,000 n ’ = 10n 10 10n 1,000 10,000 n ’ = 10n 10 T(n) n n ’ Change n ’/n
2时空限制 设计一个算法,将数组A(0.n-1)中的元素循环右移k 位,假设原数组序列为a,a1,…an-2,an1;移动后 的序列为ank,an-k+1,…,a0,a an-k 要求只 用一个元素大小的附加存储,元素移动或交换次数为 0(n)。例如,n=10,k=3,则算法要求如下: 原始数组:0123456789 右移后的:7890123456 i-k ●● i+k +一依规数也是王线零x,《物不故索盐们,,m滤亲
“十一五”国家级规划教材。张铭，赵海燕，王腾蛟，宋国杰，《数据结构与算法实验教程》，高教社，2010.12 2. 时空限制 设计一个算法，将数组A(0..n-1)中的元素循环右移k 位，假设原数组序列为a0, a1, …, an-2,an-1；移动后 的序列为an-k, an-k+1, …, a0, a1, …, an-k-1。要求只 用一个元素大小的附加存储，元素移动或交换次数为 O(n)。例如，n=10, k=3，则算法要求如下： 原始数组： 0 1 2 3 4 5 6 7 8 9 右移后的： 7 8 9 0 1 2 3 4 5 6 … i-k … i … i+k …
n=10.k=3 原始数组:0123456789 右移后的:7890123456 n-2K, n-k-1 n-k, n-1 口如果可以使用k个元素大小的附加存储空间 口只需将数组最后k个元素按顺序保存在临时 数组中,等价于 Tmp[o. k-1]= Arrayln-k. n-1] 1然后将数组中第n-k-1个元素移动到n-1的位置上,第n k2个元素移动到n2的位置上 ■依此类推,直到将数组前端元素都移动k位 ■最后将临时数组的内容拷贝到数组的前k位,即 Arrayl0.k-1=Tmp[0. k-11 +一依规数也是王线零x,《物不故索盐们,,m滤亲
“十一五”国家级规划教材。张铭，赵海燕，王腾蛟，宋国杰，《数据结构与算法实验教程》，高教社，2010.12 如果可以使用k个元素大小的附加存储空间 只需将数组最后k个元素按顺序保存在临时 数组中，等价于 ◼ Tmp[0..k-1] = Array[n-k..n-1] ◼ 然后将数组中第n-k-1个元素移动到n-1的位置上，第nk-2个元素移动到n-2的位置上 ◼ 依此类推，直到将数组前端元素都移动k位 ◼ 最后将临时数组的内容拷贝到数组的前k位，即 Array[0..k-1] = Tmp[0..k-1] n-2k, n-k-1 n-k, n-1 n=10, k=3 原始数组： 0 1 2 3 4 5 6 7 8 9 右移后的： 7 8 9 0 1 2 3 4 5 6
浪费时间:0(kn) void MultiDolphin(int Array, int n, int k)i int i, j int X k=k%n;if(k=:0)reur;/边界 for(i=1; ko j- Array[j]= Array[j-1 Aray[o]=× 补回 口注意:0(kn)!=0(n) 例如,k=n/2,则0(k.n)=0(n2) +一依规数也是王线零x,《物不故索盐们,,m滤亲
“十一五”国家级规划教材。张铭，赵海燕，王腾蛟，宋国杰，《数据结构与算法实验教程》，高教社，2010.12 浪费时间： O(k.n) void MultiDolphin(int *Array, int n, int k) { int i,j; int X; k = k % n; if (k == 0) return; // 边界 for (i=1; i0 j--) Array[j] = Array[j-1] Array[0] = X; //补回x } } 注意：O(k.n) != O(n) ◼ 例如， k=n/2, 则O(k.n) = O(n2)
浪费空间:辅助空间为尺 void SHift(int *Array, int n, int k) int *Tmp= new int[k] nt 1, J: for(i=0: i=0; i-) Array[i+k]= Array[i] for(i=0: k<k; i++) Array[i]=Tmp[] delete [] Tmp: +规数水也是王线零x,《物不故索盐们,右世,m滤亲
“十一五”国家级规划教材。张铭，赵海燕，王腾蛟，宋国杰，《数据结构与算法实验教程》，高教社，2010.12 浪费空间：辅助空间为k void KShift(int *Array, int n, int k) { int *Tmp = new int[k]; int i, j; for (i=0; i= 0; i--) Array[i+k] = Array[i]; for (i=0; i<k; i++) Array[i] = Tmp[i]; delete [] Tmp; }