线性结构(线形表、栈和队列).ppt

第13讲 数据结构之队列 中缀表达式求值 zhong pas 中缀表达式转换为后缀表达式 change pas 一 概念 在一端进行插入 进队列 在另一端进行删除 出队列 的线性表 插入的一端称为队尾 closed 指向队尾 最后一个元素 删除的一端称为队首 open 习惯指向队首的前一位置 空的位置 open closed 队列数组a下标 1234567 队列空 open closed 非空 open closed 1 定义 ConstmaxVarq array 1 max ofdatatype open closed integer 2 队列的基本运算队列的运算主要有两种 入队 procedureadd x 出队 functiondel 1 过程ADD x 在队列q的尾端插入元素xprocedureADD x qtyper begin 后移队尾指针并插入元素x closed closed 1 q closed x end ADD 2 函数DEL 取出q队列的队首元素functionDEL beginopen open 1 del q open end DEL 重要的用途 bfs 广度优先搜索算法 竞赛试题 已知队列 13 2 11 34 41 77 5 7 18 26 15 第一个进入队列的元素是13 则第五个出队列的元素是 NOIP9 A 5B 41C 77D 13E 18 设栈S和队列Q的初始状态为空 元素e1 e2 e3 e4 e5 e6依次通过栈S 一个元素出栈后即进入队列Q 若出队的顺序为e2 e4 e3 e6 e5 e1 则栈S的容量至少应该为 NOIP8 A 2B 3C 4D 5 二 队列的应用 1 合并石子 问题描述 小Ray在河边玩耍 无意中发现一些很漂亮的石子堆 于是他决定把这些石子搬回家 河滩上共有n堆石子 小Ray在把石子搬回家之前首先要把这n堆石子合并为一堆石子 已知小Ray每次可以选择其中的两堆石子合并为一堆 合并一次石子他要消耗的体力是两堆石子的数量和 请计算小Ray把n堆石子合并成一堆最少消耗的体力值是多少 输入 第一行 n 30000 第二行 那个用空格隔开的数 分别表示n堆石子的数量 每堆 10000 输出 n堆石子合并成一堆所消耗的最小体力值 说明 分别用队列和堆两种算法实现 样例输入 3124 样例输出 10 opena 1 openb 1 closedb 0 ans 0 fori 1ton 1dobeginsum a opena a opena 1 f 1 ifa opena b openb sumthenbeginsum a opena b openb f 2 end ifb openb b openb 1 sumthenbeginsum b openb b openb 1 f 3 end inc closedb b closedb sum inc ans sum casefof1 inc opena 2 2 begininc opena inc openb end 3 inc openb 2 end end 算法 将石子从小到大排序放入数组a 数组b 一次存放合并后的石子 同样是递增的的 将石子从小到大排序放入数组a N 300001 快速排序算法 2 桶排序算法 readln n fori 1tondobeginread k inc t k end k 0 fori 1to30000doforj 1tot i dobegininc k a k i end a n 1 maxlongintdiv2 a n 2 maxlongintdiv2 fori 1ton 2dot i maxlongintdiv2 问题描述 在n n的棋盘上有一匹马在第x行第y列的格子上 棋盘上有些格子上有障碍物 马不能达到有障碍物的格子 已知马在棋盘中的走法按 日 字8个方向可走 如下图所示 问 哪些格子能到达 到达这些格子的最小步数是多少 输入 第一行 n n 100 x y 马的开始位置 接下来n行为棋盘的描述 为空格子 表示该格子有障碍物 输出 n行 每行n个用空格隔开的数 表示马到达该格子的最少步数 如果无法到达则用 1表示 2 马的遍历 422 样例输入 4321303223 111214 样例输出 dx array 1 8 ofinteger 1 2 2 1 1 2 2 1 dy array 1 8 ofinteger 2 1 1 2 2 1 1 2 varcan array 1 maxn 2 1 maxn 2 ofboolean 加边界 方便判断是否出界dist array 1 maxn 1 maxn ofinteger 记录最少步数n i j x0 y0 integer procedureinit vars string beginreadln n x0 y0 fillchar can sizeof can false fori 1tondobeginreadln s forj 1tondocan i j s j end end procedurebfs 广度优先搜索varq array 1 maxn maxn 1 2 ofinteger open closed k x y xx yy integer beginfori 1tondoforj 1tondodist i j 1 open 0 closed 1 dist x0 y0 0 q 1 1 x0 q 1 2 y0 whileopen closeddobegininc open x q open 1 y q open 2 fork 1to8dobeginxx x dx k yy y dy k ifcan xx yy and dist xx yy 1 thenbegindist xx yy dist x y 1 inc closed q closed 1 xx q closed 2 yy end end end end 广度优先搜索算法 bfs 1 适合的题目类型 1 求从给定初始状态到目标状态最少需要的步数 2 给定初始状态 经过k步后能够到达哪些状态 2 利用的数据结构 队列 3 状态的最大值 决定队列的大小 非常重要 4 队列里需要记住哪些状态 一般使用记录数据类型 5 状态的转移 不能遗漏 6 状态的判重 避免重复进入队列 结合跳马题目分析 Bfs的基本框架 初始化 建立数据库 队列 初始状态进入队列 Open 0 队列的首指针 Closed 1 队列的尾指针 开始时指向初始状态 Quene 1 初始结点 While open closed 还有未扩展的结点 队列不空 doBeginInc open 移动队列的首指针 出队列 记录open状态 Fori 1tomethoddo 按规则扩展下一层新的子结点 Begin生成新的结点 If新结点是目标结点then输出目标 搜索结束 If新结点是以前没出现过then保存新结点 入队列 EndEnd 3 中国盒子问题 box 4 翻硬币 coin pas 5 迷宫问题mg pas 给定10个盒子排成一行 其中有两个相邻的盒子是空的 其余的盒子中有4个A和4个B 例如 移动规则 任意两相邻字母可移到空盒子中去 但这两个字母的原来顺序保持改变 目标 全部的A在左边 全部的B在右边 空格在中间 如下图 对于任意给定的一个排列顺序 最少经过多少次移动 能达到目标序列 输入 一行 初始序列 空格用0代替 输出 初始序列达到目标的最少移动次数 样例 输入 ABBA00ABAB输出 5 3 中国盒子问题 box 中国盒子问题 box 1 问题 初始序列达到目标的最少移动次数 适合使用bfs算法 2 队列需要保存的状态 转化后的字符串s 转换需要的步数depth 适合用记录数据类型 typenode recordstr string 10 depth integer end 3 状态的多少 队列的大小 630 4 状态的转移 任意两相邻字母可移到空盒子中去 但这两个字母的原来顺序保持改变 1 确定空格的位置 sp pos 0 s sp S i 1 9 2 i i 1与sp sp 1位置的字符交换 条件 sp i 2 or i sp 2 3 交换 Tem stem sp s i tem sp 1 s i 1 tem i 0 tem i 1 0 5 判重 fori 1tocloseddoifa 1 str tem最简单 最直接的判重方法 缺点 效率低 时间慢 4 翻硬币 coin pas 问题描述有N个硬币正面朝上排成一排 N 6 每次将5个硬币翻过来放在原位置 直到最后全部硬币翻成反面朝上为止 编程找出最少步数输入只有一个整数N 1000 输出翻币的最少次数coin in8Coin out4 关键 反的最少次数仅仅与正面朝上和反面朝上的硬币各数有关 而与硬币的顺序无关 1 需要记录的状态有哪些 2 怎样判重复状态 3 状态转移及条件 4 队列的大小 typenode recordnum integer 正面朝上个数 depth integer 翻的次数 end vara array 1 1000 ofnode n open closed step integer b array 0 1000 ofboolean b i i个正面朝上的情况是否出现过 procedurebfs vari m integer beginopen 0 closed 1 a 1 num n a 1 depth 0 b n true whileopen i and n m 5 i then m i 5 i 正面朝上的个数 beginifm i 5 i 0thenprint step 正面朝上的个数为0时结束 ifnot b m i 5 i thenbegininc closed 进队列 b m i 5 i true a closed num m i 5 i 正面朝上的个数 a closed depth step 翻的次数 end end end end 可以看出 除了6和8是特例外 其他满足 1 if nmod5 0 thens ndiv52 if nmod5 1 or nmod5 3 thens ndiv5 13 if nmod5 2 or nmod5 4 thens ndiv5 2或者 Ifnmod5 0thens ndiv5Elses ndiv5 nmod5 1 mod2 1 设有一个N N方格的迷宫 入口和出口分别在左上角和右上角 迷宫格子中分别放有0和1 0表示可通 1表示不能 迷宫走的规则如下图所示 即从某点开始 有八个方向可走 前进方格中数字为0时表示可通过 为1时表示不可通过 要另找路径 输入例子 从文件中读取数据 80001101010110110010010010011010101000110011111010011101111000000入口 1 1 出口 1 8 输出要求 最少步数 找出一条从入口 左上角 到出口 又上角 的路径 不能重复 8 11 22 33 34 45 36 37 28 18 5 迷宫问题mg pas 求最少步数 类似跳马问题 typenode recordrow col integer depth integer end Varq array 0 maxn maxn ofnode 队列can array 0 maxn 1 0 maxn 1 ofboolean 边界 判重 procedurebfs vark x y xx yy step integer beginopen 0 closed 1 can 1 1 false q 1 row 1 q 1 col 1 q 1 depth 0 whileopen closeddobegininc open x q open row y q open col step q open depth 1 fork 1to8dobeginxx x dx k yy y dy k ifcan xx yy thenif xx 1 and yy n thenprint step elsebegincan xx yy false inc closed q closed row xx q closed col yy q closed depth step end end end print 1 end Bfs 输出方案 proceduredfs i integer beginifq i father0thendf