《算法艺术和 与信息学竞赛》课件3数据结构入门.pptVIP

数据结构入门 清华大学 刘汝佳 什么是数据结构 数据结构的含义 数据 关系 操作 例子：数组 数据：a[1], a[2], …, a[n] 关系：前驱/后继 操作：随机存取，插入，删除… 数据结构为算法服务 根据算法对数据的操作要求，设计合适的数据结构 实现同一套操作，可以用多种数据结构 如何降低时空复杂度，又方便实现？ 抽象数据类型(ADT) 算法对数据结构的要求 维护一个电话薄，方便进行插入删除和查找 操作：插入，删除，查找 如何实现？ 算法不关心！ 只要提供这些操作都可以！ 抽象数据类型：集合 逻辑结构 抽象数据类型没有办法转化成程序 需要设计逻辑结构！ 所有电话记录形成线性结构，记录的顺序无要求 无序线性表 有了逻辑结构，可以设计算法 插入：直接插到表的头部或者尾部 删除：直接删除，再把两段合并在一起 查找：从头开始沿着表找一遍 这个算法仍然不能转化成程序 甚至无法进行复杂度分析！ 物理结构 逻辑结构需要进一步转化成物理结构 逻辑结构：无序线性表 物理结构：数组 插入：插到尾部比较方便，O(1) 删除：“合并两半”导致元素移动，最坏O(n) 查找：最坏O(n) 物理结构：链表 插入：插到头部比较方便，O(1) 删除：找到位置后O(1) 查找：O(n) 不同的物理结构，得到不同的效果！ 如何学习数据结构 了解常见的抽象数据类型 对每种ADT，了解常见的逻辑结构 设计逻辑结构是最难的！ 对给定的逻辑结构，自己设计物理结构 物理结构一般只是数组和链结构 数组可以随机访问（设计下标计算公式） 经典例子：哈希表，二叉堆，并查集，线段树 链结构应该根据元素间关系（链接）进行“移动” 经典例子：伸展树，二项堆，跳跃表 *特殊算法需要自己归纳出ADT并设计逻辑结构 PQ树，后缀树 常见的抽象数据类型 栈 压栈（入栈），弹栈（出栈），判断空 队列 入队，出队，判断空 串 取前缀/后缀，匹配… 字典 插入，删除，查找 优先队列 插入，取最小值，删除最小值，合并 入门学什么？ *栈和队列 串：匹配 树：表示和遍历 图：遍历和拓扑排序 *基本检索算法 *基本排序算法 栈 外特性：后进先出(LIFO) 交卷子 KTV的“点歌单” 作用：保护现场 逻辑结构：只在一端操作的线性表 数组实现：元素stack : array[1..maxn] of integer，栈顶指针top 入栈：inc(top); stack[top] := ele; inc(top) ? top := top + 1 出栈：ele := stack[top]; dec(top) dec(top) ? top := top - 1 空栈条件：top = 0 铁轨问题 例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 队列 外特性：先进先出(FIFO) 食堂排队 吸管里的饮料 作用：维持顺序 数组实现：元素queue[0..maxn-1]，队首front，队尾rear 入队：inc(rear); queue[rear] := ele; 出队：ele := queue[front]; inc(front) 队空条件：front rear 问题：出队的元素还在数组里，不是很浪费吗？ 循环队列 把队列看成环行的，则 入队：rear := (rear + 1) mod maxn; 不定义为queue[1..maxn]的原因 出队：front := (front + 1) mod maxn; 可能存在队满的情况：条件也是front rear （想一想，如何解决？） 小球钟——时间与运动 球钟的状态表示 含有小球的四个部件 分钟轨道：ball[1..4] 5分钟轨道：ball[1..11] 小时轨道：ball[1..11] 底部轨道：ball[1..n] 问题：虽然都是线性结构，但如何操作？ 分钟、5分钟、小时：栈！ 底部小球：队列！ 球钟的模拟 完全模拟 时间复杂度O(t)，t为模拟的时间，可能很大 经过12小时 小球又全部回到底部轨道 但顺序和以前不一样了！ 设一开始各个小球的编号依次为1,2,3…n 新顺序是1,2,3…n的一个排列！ 一个例子：1,2,3,4,5 ? 2,4,5,1,3 小球1的位置变化：1?4?2?1 小球3的位置变化：3?5?3 小球1,2,3,4,5分别经过3,3,2,3,2个12小时回到原地 总时间为[2,3] = 6 时间复杂度：O(n) （想一想，为什么不是O(n2)） 种子填充法 怎样找连通区域？ 走迷宫——没有分身术 栈(DFS) 撒墨水 队列(BFS) 连通区域的种类 四连 八连 怎样高效的实施？ 四连区域和八连区域 四连 dx : array[1..4]