刘汝佳-数据结构入门.ppt

数据结构入门 清华大学 刘汝佳 什么是数据结构 数据结构的含义 数据 关系 操作 例子：数组 数据：a[1], a[2], …, a[n] 关系：前驱/后继 操作：随机存取，插入，删除… 数据结构为算法服务 根据算法对数据的操作要求，设计合适的数据结构 实现同一套操作，可以用多种数据结构 如何降低时空复杂度，又方便实现？ 抽象数据类型(ADT) 算法对数据结构的要求 维护一个电话薄，方便进行插入删除和查找 操作：插入，删除，查找 如何实现？ 算法不关心！ 只要提供这些操作都可以！ 抽象数据类型：集合 逻辑结构 抽象数据类型没有办法转化成程序 需要设计逻辑结构！ 所有电话记录形成线性结构，记录的顺序无要求 无序线性表 有了逻辑结构，可以设计算法 插入：直接插到表的头部或者尾部 删除：直接删除，再把两段合并在一起 查找：从头开始沿着表找一遍 这个算法仍然不能转化成程序 甚至无法进行复杂度分析！ 物理结构 逻辑结构需要进一步转化成物理结构 逻辑结构：无序线性表 物理结构：数组 插入：插到尾部比较方便，O(1) 删除：“合并两半”导致元素移动，最坏O(n) 查找：最坏O(n) 物理结构：链表 插入：插到头部比较方便，O(1) 删除：找到位置后O(1) 查找：O(n) 不同的物理结构，得到不同的效果！ 另一种逻辑结构 有序线性表 物理结构：数组 插入最坏O(n) 删除最坏O(n) 查找最坏O(logn)：二分查找 物理结构：链表 插入（找到后）最坏O(1) 删除（找到后）最坏O(1) 查找最坏O(n)，平均n/2 常见的抽象数据类型 栈 压栈（入栈），弹栈（出栈），判断空 队列 入队，出队，判断空 串 取前缀/后缀，匹配… 字典 插入，删除，查找 优先队列 插入，取最小值，删除最小值，合并 入门学什么？ *栈和队列 串：匹配 树：表示和遍历 图：遍历和拓扑排序 *基本检索算法 *基本排序算法 栈 外特性：后进先出(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] of integer = {1, -1, 0, 0}; dy : array[1..4] of integer = {0, 0, -1, 1}; for direct