《刘汝佳-数据结构入门【业界相关】.ppt》由会员分享，可在线阅读，更多相关《刘汝佳-数据结构入门【业界相关】.ppt（39页珍藏版）》请在三一文库上搜索。
1、数据结构入门,清华大学 刘汝佳,1,专业课堂,什么是数据结构,数据结构的含义 数据 关系 操作 例子：数组 数据：a1, a2, , an 关系：前驱/后继 操作：随机存取，插入，删除 数据结构为算法服务 根据算法对数据的操作要求，设计合适的数据结构 实现同一套操作，可以用多种数据结构 如何降低时空复杂度，又方便实现？,2,专业课堂,抽象数据类型(ADT),算法对数据结构的要求 维护一个电话薄，方便进行插入删除和查找 操作：插入，删除，查找 如何实现？ 算法不关心！ 只要提供这些操作都可以！ 抽象数据类型：集合,3,专业课堂,逻辑结构,抽象数据类型没有办法转化成程序 需要设计逻辑结构！ 所有电
2、话记录形成线性结构，记录的顺序无要求 无序线性表 有了逻辑结构，可以设计算法 插入：直接插到表的头部或者尾部 删除：直接删除，再把两段合并在一起 查找：从头开始沿着表找一遍 这个算法仍然不能转化成程序 甚至无法进行复杂度分析！,4,专业课堂,物理结构,逻辑结构需要进一步转化成物理结构 逻辑结构：无序线性表 物理结构：数组 插入：插到尾部比较方便，O(1) 删除：“合并两半”导致元素移动，最坏O(n) 查找：最坏O(n) 物理结构：链表 插入：插到头部比较方便，O(1) 删除：找到位置后O(1) 查找：O(n) 不同的物理结构，得到不同的效果！,5,专业课堂,另一种逻辑结构,有序线性表 物理结构
3、：数组 插入最坏O(n) 删除最坏O(n) 查找最坏O(logn)：二分查找 物理结构：链表 插入（找到后）最坏O(1) 删除（找到后）最坏O(1) 查找最坏O(n)，平均n/2,6,专业课堂,比较一下,7,专业课堂,如何学习数据结构,了解常见的抽象数据类型 对每种ADT，了解常见的逻辑结构 设计逻辑结构是最难的！ 对给定的逻辑结构，自己设计物理结构 物理结构一般只是数组和链结构 数组可以随机访问（设计下标计算公式） 经典例子：哈希表，二叉堆，并查集，线段树 链结构应该根据元素间关系（链接）进行“移动” 经典例子：伸展树，二项堆，跳跃表 *特殊算法需要自己归纳出ADT并设计逻辑结构 PQ树，后
4、缀树,8,专业课堂,常见的抽象数据类型,栈 压栈（入栈），弹栈（出栈），判断空 队列 入队，出队，判断空 串 取前缀/后缀，匹配 字典 插入，删除，查找 优先队列 插入，取最小值，删除最小值，合并,9,专业课堂,入门学什么？,*栈和队列 串：匹配 树：表示和遍历 图：遍历和拓扑排序 *基本检索算法 *基本排序算法,10,专业课堂,栈,外特性：后进先出(LIFO) 交卷子 KTV的“点歌单” 作用：保护现场 逻辑结构：只在一端操作的线性表 数组实现：元素stack : array1.maxn of integer，栈顶指针top 入栈：inc(top); stacktop := ele; inc
5、(top) top := top + 1 出栈：ele := stacktop; dec(top) dec(top) top := top - 1 空栈条件：top = 0,11,专业课堂,铁轨问题,例1：1,2,3,4,5 yes；例2：5,4,3,2,1 yes 例3：3,2,4,5,1 yes；例4：3,1,4,5,2 no,12,专业课堂,队列,外特性：先进先出(FIFO) 食堂排队 吸管里的饮料 作用：维持顺序 数组实现：元素queue0.maxn-1，队首front，队尾rear 入队：inc(rear); queuerear := ele; 出队：ele := queuefron
6、t; inc(front) 队空条件：front rear 问题：出队的元素还在数组里，不是很浪费吗？ 循环队列 把队列看成环行的，则 入队：rear := (rear + 1) mod maxn; 不定义为queue1.maxn的原因 出队：front := (front + 1) mod maxn; 可能存在队满的情况：条件也是front rear （想一想，如何解决？）,13,专业课堂,小球钟时间与运动,14,专业课堂,球钟的状态表示,含有小球的四个部件 分钟轨道：ball1.4 5分钟轨道：ball1.11 小时轨道：ball1.11 底部轨道：ball1.n 问题：虽然都是线性结构，
7、但如何操作？ 分钟、5分钟、小时：栈！ 底部小球：队列！,15,专业课堂,球钟的模拟,完全模拟 时间复杂度O(t)，t为模拟的时间，可能很大 经过12小时 小球又全部回到底部轨道 但顺序和以前不一样了！ 设一开始各个小球的编号依次为1,2,3n 新顺序是1,2,3n的一个排列！ 一个例子：1,2,3,4,5 2,4,5,1,3 小球1的位置变化：1421 小球3的位置变化：353 小球1,2,3,4,5分别经过3,3,2,3,2个12小时回到原地 总时间为2,3 = 6 时间复杂度：O(n) （想一想，为什么不是O(n2)）,16,专业课堂,种子填充法,17,专业课堂,怎样找连通区域？,走迷宫
8、没有分身术 栈(DFS) 撒墨水 队列(BFS) 连通区域的种类 四连 八连 怎样高效的实施？,18,专业课堂,四连区域和八连区域,四连 dx : array1.4 of integer = 1, -1, 0, 0; dy : array1.4 of integer = 0, 0, -1, 1; for direction :=1 to 4 do newx := x + dxdirection; newy := y + dydirection; 八连？自己试一试！ 空间呢？ 六角形呢？,19,专业课堂,回到原题,如何找脸？ 四连？八连？ 如何找脸上的元素？ 四连？八连？ 如何判断两个脸是否一样
9、？ 左上角坐标 比较矩形区域？ 如何表示？,20,专业课堂,种子填充有用吗？,求：上确界(J)和下确界(G),21,专业课堂,二分检索算法,猜一个1n的整数，需要多少次？ 每次告诉你猜大了还是猜小了 可能的范围总是一个区间（怎么证明？） 区间总会一个中点 不管是大还是小，都可以排除约一半的可能性 最坏需要多少次？ log2n次。（想一想，怎么证明？） 如果是在一个排序好的数组中查找一个整数呢？ 本质是一样的 如何处理找不到的情形？ 算法名称：二分检索,22,专业课堂,进一步的考虑,如果不告诉你整数的范围，怎么办？ 每次扩大两倍？ 每次猜Fn？ 如何分析性能？（想一想） 问题变换 优化 判定 例
10、：电缆问题 网线数目给定 每根要求尽量长 不能拼接，只能切割,23,专业课堂,基本排序算法,常见算法 插入排序 选择排序 归并排序 快速排序 分类 基于比较？ 稳定？,24,专业课堂,插入排序,依次处理各个元素。处理第i个时，保持前i-1个有序 找到合适的位置（唯一！） 一个一个找 因为有序嘛.二分检索？ 插进去！数组需要移动元素，链表不需要 讨论：二分检索查找有多大意义？ 适合场所：原始数据基本有序！ 应用：为粗排序做的“收尾”工作 例子：快速排序的边界！,25,专业课堂,选择排序,所有元素一起处理多遍。第i次找到第i大元素 找大最大元素：O(n) 让这个最大的不会再成为最大 删除？ 变成最
11、小值？ 移动到无关区域？ 反复找当前最大值，就找到了第2,3,n大,26,专业课堂,两个应用,输入有间隔？ 选择排序？取决于未来的输入？ 插入排序：来一个插一个 因果系统！ 在线算法 给期末考试成绩表做排名，希望先知道前10 插入排序？如果前10名是最后10个元素 选择排序：选的前10个就是前10名！ 结论：排序算法的选择要看实际应用！,27,专业课堂,归并排序,两个有序表，怎么合起来？ 1, 2, 4, 7, 9 3, 5, 6, 10, 11 合并：n 分治sort(i, j)，设时间为T(n) 排前一半：sort(i, mid), 时间T(n/2) 排后一半：sort(mid+1, j)
12、，时间T(n/2) 合并起来：n T(n) = 2T(n/2) + n T(n) = O(nlogn),28,专业课堂,一个例子,目标：从小到大排序 从下数第k个开始往上翻 (a) (b) (c) 3 1,29,专业课堂,一个应用,逆序对数目：i aj 枚举：O(n2). n = mid，递归处理 i mid j，如何求？ 合并的时候顺便求！ 还是这个例子 1, 2, 4, 7, 9 3, 5, 6, 10, 11 取后一半元素时，前一半还剩多少个就是 时间复杂度：O(nlogn). n = 100,000,30,专业课堂,快速排序,找一个数x 让x左边的数都比x小 让x右边的数都比x大 分别
13、给两边排序 核心：如何调整x左右的数？ 从两边往中间扫描 在x左边第一个比x大的地方停下来 在x右边第一个比x小的地方停下来 两个交换，正好都满足要求 例子：1, 8, 2, 9, 6, 4, 7, 3, 5 第一次交换8和5：1, 5, 2, 9, 6, 4, 7, 3, 8 第二次交换9和3：1, 5, 2, 3, 6, 4, 7, 9, 8 第三次交换6和4：1, 5, 2, 3, 4, 6, 7, 9, 8 两个指针汇合，完成 时间复杂度：O(n),31,专业课堂,快速排序分析,最好情况：均分成两半，则是O(nlogn) 最坏情况：分成长度为1和n-1，则是O(n2) 想一想，为什么是
14、O(n2) 这是不是说明快速排序比归并排序差？ 显然不是，否则就不会叫“快速排序”了嘛 想一想，为什么？ 最坏情况出现的概率 应该分析平均情况！限于篇幅，此处略。 结论为O(nlogn)，而且系数比归并排序小 一些小细节 n = 10时用插入排序加速 x如何选？中间？随机（随机数产生开销）？ 警告！快速排序不稳定！原因？如何修改？,32,专业课堂,快速排序应用,士兵排队问题 n=10,000个士兵在网格中，位置用(x, y)表示 士兵可以沿四个方向移动 进入某一行且排在一起 假设格子可以容纳所有士兵 分析 行：中位数 or 平均数？ 列？（请思考） 中位数如何求？ 快速排序？O(nlogn)
15、其实不需要分别排序，只需要根据k的大小只处理一边 平均情况：O(n),33,专业课堂,有更快的排序方法吗？,计数排序 分数：0100的整数 开一个count0.100的数组，记录个数 for i:=1 to n do inc(countscorei); 就可以了！O(n)！ 但是 有附加关键码（姓名，学号） 稳定性要求？ 怎么会这么快？ 关键码范围限制（如果范围是0100,000，但n=10,000，就） 不是基于比较的！而是直接根据关键码范围 如果只提供比较呢？交互式题目？,34,专业课堂,基于比较的排序时间下限,简单起见，不考虑相等的情形 可以获得多少信息？ 一次比较，两种结果 k次比较2
16、k种结果 需要获得多少信息？ n个数的排列有n!种 最后只剩一种可能性时，排序完成 需要比较多少次？ 比较k次以后最好只能保证剩n!/2k种可能性 n!/2k=1时，即k=log(n!)时排序完成 log(n!) = (nlogn),35,专业课堂,排序的应用,(a) 改变第二行，交换一、三列 (b),36,专业课堂,迷题的解答,先行后列 行的情况：2n 列的情况：n! (b)的第1列是(a)的哪一行变化而来 各行情况都知道 是否能重排各列？ 方法一：枚举判断：O(n3) 方法二： 按同一比较方法排序：O(n2logn) 元素相同的不同的排列排序结果唯一！ 总时间复杂度：O(n3logn) 优化？,37,专业课堂,讨论题目,篮球俱乐部有n(n=6000)个人 俱乐部经理认为身高2米最好 不要太高，也不要太矮！ 有一天，他视察俱乐部 “所有队员排成一行！” 随便选出一个连续的序列，设有k个人，总身高为L(m) 如果|L 2K| 0.1，合格！ 否则不合格？ 队员们应该怎么站呢？ 例子：1.95 1.95 1.96 2.04 2.05 2.05 可以这么站：1.95 2.05 1.95 2.05 1.96 2.04,38,专业课堂,n,1 2 3 4 5 6 7 1 K k O(1) O(N),39,专业课堂,