栈、队列及其应用

线性表的应用 1 问题描述 线性表a和b分别表示两个线性表 它们的数据元素类型相同 现要将b中存在而a中不存在的数据元素插入到线性表a中 设线性表a的长度与线性表b的长度之和不超过线性表a允许的最大长度 参考程序 proceduIreunion vara list b list beginn length a fori 1tolength b dobegingetlist b i x 取线性表b中第i位上的数给T k loclist a x 返回z在线性表a中的位置 ifk 0thenbegininslist a n 1 x 将z插入线性表a的末尾 n n 1 end end end 线性表的应用 2 问题描述 已知线性表 和b中的数据元素按递增的顺序排列 现要求将a和b归并为一个新的线性表c c中的数据元素仍按递增排列 用数组实现 用链表实现 线性表的应用 3 Joseph 约瑟夫 问题 问题描述 m只猴子要选大王 选举办法如下 所有猴子按1 m编号围坐一圈 从第1号开始按顺序1 2 n报数 凡报到竹的猴子退出到圈外 如此循环 直到圈内只剩下一只猴子时 这只猴子就是大王 m和咒由键盘输入 打印出最后剩下的那只猴子的编号 运行示例 Inputm n 83Themonkeykingisno 7 用数组实现 算法分析 在确定程序设计方法之前首先来考虑如何组织数据 由于要记录m只猴子的状态 可利用含m个元素的数组monkey来实现 利用元素下标代表猴子的编号 元素的值表示猴子的状态 用monkeyEk l表示第k只猴子仍在圈中 monkeyEk 0则表示第k只猴子已经出圈 程序采用模拟选举过程的方法 开始时将报数变量count置为1 用变量current表示当前报数的猴子的编号 初始时也置为1 变量 out记录出圈猴子数 当count n时 对当前报数的猴子做出圈处理 即monkey current O count 0 out out 1 然后继续往下报数 直到圈中只剩一只猴子为止 即out m 1 用数组实现 算法分析 在组织数据时 也可以考虑只记录仍在圈中的猴子的情况 用一个线性表按编号由小到大依次记录圈中所有猴子的编号 每当有猴子出圈时 即从线性表中删除对应元素 表中元素减少一个 程序中用变量rest表示圈中剩余的猴子数 即线性表中元素的总数 用单向循环链表实现 算法分析 结点的数据域为猴子的编号 指针域指向下一个猴子 报数实际上是计数 只要设一个计数器就可以了 当计数器由0变化到n时 删除该结点 计数器回0继续计数 或者用求余运算 直到链表中剩下一个结点 线性表的应用 4 一元多项式加减运算 问题描述 给定一个一元n次多项式p和一个一元m次多项式Q 求它们的和与差 算法分析 选方法 遍历两个单链表 根据指数和系数进行相应的加减 生成一个新链表系数为0的结点删除掉 或不生成这种结点 输出该链表 特殊线性结构 栈 栈 stack 是一种特殊的线性表 这种线性表限定其只能在表尾进行插入或删除数据元素 栈的存储方式 顺序存储 通常栈可以用顺序的方式存储 就是用一组连续的存储单元依次存放自栈底到栈顶的数据元素 同时设立指针top 称为栈顶指针 以指示栈顶元素的当前位置 1 用记录方式实现 Typestack recorddata array 1 smaxsize ofselement top 0 smaxsize end 2 用数组方式实现Typeatype array 1 smaxsize ofselement Varstack arraytype top integer 栈的存储方式 链接存储 即链栈 目的是提高空间利用率 但编程复杂度提高了 typelink node node recorddata element next link end Vartop link 栈基本操作的实现 顺序存储栈的操作 栈的初始化Procedureinistack vars stack begins top 0end 判断栈空functionsempty s stack boolean beginsempty s top 0 end 入栈Procedurepush vars stack x selement beginifs top smaxsizethenwriteln overflow elsebegins top s top 1 s data s top end 栈基本操作的实现 顺序存储栈的操作 出栈Procedurepop vars stack beginifsempty s thenwriteln underflow elses top s top 1 end 取栈顶元素functiongettop s stack selement beginifsempty s thenwriteln underflow thengettop s data s top end 栈基本操作的实现 链栈的基本操作 进栈算法procedurepush hs link x element beginnew p p data x p next hs hs p end 出栈functionpop varhs link element beginifhs nilthenwriteln underflow elsebeginpop hs data p hs hs hs next dispose p endend 括号匹配 问题描述 假设一个表达式由英文字母 小写 运算符 一 和左右小 圆 括号构成 以 作为表达式的结束符 请编写一个程序检查表达式中的左右圆括号是否匹配 若匹配 则返回 yes 否则返回 NO 假设表达式长度小于255 左圆括号少于20个 算法分析 将输人的字符串存储在c中 varc string 255 定义一个栈用于存放表达式中从左往右的左圆括号 maXn 20 vars array 1 maxn ofchar top integer 顺序 从左往右 扫描表达式的每个字符c i 若是 则让它进栈 若遇到的是 则让栈顶元素出栈 当栈发生 下溢 或当表达式处理完毕而栈非空时 都表示不匹配 返回 NO 否则表示匹配 返回 YES 栈与递归 递归调用的过程 实质上是不断调用子过程或子函数的过程 由于递归调用一次 所有子程序的变量 局部变量 变参等 地址在计算机内部都是用特殊的管理方法 栈 先进后出 来管理 一旦递归调用结束 计算机便开始根据栈中存储的地址返回各子程序变量的值 并进行相应操作 递归实现的条件 边界条件 是所描述问题的最简单情况 它本身不再使用递归的定义 如求N 当n 0时 f n 1 不再使用f n 1 来定义 递归关系 使问题向边界条件转化的规则 递归定义必须能使问题的规模越来越简单 例 折半查找 问题描述 设有 个数已经按从大到小的顺序排列 现在从键盘上输入x 判断它是否在这 个数中 如果存在 则输出所在位置 否则输出 no 算法分析 该问题属于数据的查找问题 常用方法有顺序查找和折半查找 当行个数排好序时 用折半查找方法的速度会大大加快 折半查找算法如下 设有n个数 存放在数组a中 待查找数为x 用t指向数据的高端 用w指向数据的低端 mid指向中间 若x a mid 输出 yes 若xa mid 则到数据前半段查找 t不变 w mid 1 计算新的mid值 并进行新的一段查找 若t w 则没有查找到 输出 no 练习7 Joseph 约瑟夫 问题 问题描述 m只猴子要选大王 选举办法如下 所有猴子按1 m编号围坐一圈 从第1号开始按顺序1 2 n报数 凡报到n的猴子退出到圈外 如此循环 直到圈内只剩下一只猴子时 这只猴子就是大王 m和n由键盘输入 打印出最后剩下的那只猴子的编号 运行示例 Inputm n 83Themonkeykingisno 7 用数组实现 算法分析 在确定程序设计方法之前首先来考虑如何组织数据 由于要记录m只猴子的状态 可利用含m个元素的数组monkey来实现 利用元素下标代表猴子的编号 元素的值表示猴子的状态 用monkeyEk l表示第k只猴子仍在圈中 monkeyEk 0则表示第k只猴子已经出圈 程序采用模拟选举过程的方法 开始时将报数变量count置为1 用变量current表示当前报数的猴子的编号 初始时也置为1 变量 out记录出圈猴子数 当count n时 对当前报数的猴子做出圈处理 即monkey current O count 0 out out 1 然后继续往下报数 直到圈中只剩一只猴子为止 即out m 1 约瑟夫的新问题 约瑟夫的新问题 问题描述 将1 m这m个自然数按由小到大的顺序沿顺时针方向围成一圈 以s为起点 先沿顺时针方向数到第n个数就出圈 然后沿逆时针方向数到第k个数再出圈 再沿顺时针方向数到第n个数就出圈 然后沿逆时针方向数到第k个数再出圈 这样按顺时针方向和逆时针方向不断循环 直到全部数都出圈为止 请打印先后出圈的数的序列 输入 m s n k m不超过1000 输出 先后出圈的数的序列 每个数之间有1个空格 样例输入 8132样例输出 3l527468 解释 先从1开始沿顺时针方向数到3 所以3先出圈 再从2开始沿逆时针方向数到1 所以1出圈 再从2开始沿顺时针方向数到5 所以5出圈 再从4开始沿逆时针方向数到2 所以2出圈 算法分析 解决这个问题可以有两种思路 第一种思路用数组来模拟 用一指针来指示当前的数字 这样就又有两种办法 一是可以给每一数字做一个标记 来判断它是否已经出圈 这样可以省去移动数组元素的过程 但指针须一个一个地移动 速度较慢 二是每次都把指针直接指向下一个要出圈的数字 并将其输出并删除 这样做需要大量地移动数组元素 造成耗时 这两种方法都需要注意对于指针出界的判断 第二种思路是使用双向循环链表 这是最简单也是最有效的方法 既不用大量地移动数组元素 也不用判断数组出界 可以用最直接的模拟来实现 练习4 特殊线性结构 队列 队列 queue 是另一种特殊的线性表 限定只能在表的一端进行插入 在表的另一端进行删除 队列的存储方式 1 顺序存储typequeue recorddata array 1 1maxsize qelement front rear 0 qmaxsize end 2 链接存储typequeueptr queuenode queuenode recorddata elemtp next queueptr end linkedquetp recordfront rear queueptr end 队列的基本操作 初始化iniqueue q procedureiniqueue varq queue beginq front 0 q rear 0end 判队列空qempty q functionqempty q queue boolean beginqempty q front q rear end 判队列满qfull q functionqempty q queue boolean beginqfull q rear qmaxsize end 入队enqueue q x procedureenqueue varq queue x qelement beginifqfull q thenwriteln overflow elsebeginq rear q rear 1 q data q rear xend end 队列的基本操作 出队delqueue q x proceduredelqueue varq queue X qelement beginifqempty q thenwriteln underflow elsebeginq front q Front 1 x q data q front end end 取队头元素gethead q functiongethead q queue qelement Varm 0 qmaxsize beginifqempty q thenwriteln underflow elsebeginm q front 1 gethead q data m end end 求队列长度lenqueue q functionlenqueue q queue integer beginlenqueue q rear q front end 队列的基本操作 入队enqueue q x procedureenqueue varq linkedquetp x elemtp beginnew q Rear next q rear q rear next q Rear data x q Rear next nil end 出队delqueue q proceduredequeue varq linkedquetp varP queueptr beginifqempty q thenerror thequeueisempty elsebeginP q front q front q Front next dispose p end end 循环队列 在所表示的队列情况下 若另有元素a 需人队 这时rear 5 已满足 上溢 条件 无法实现人队操作 但实际上队列中有三个空位 这种现象称为 假溢出 当 假溢出 时 应该将队列中现有元素向队头方向移动 这显然需要花费一定的时间 如何避免 假溢出 现象呢 设想把q 1 接在q m 之后形成循环表 当删除a1之后插入am 1 时 不移动队列中现有元素 而直接把它加到q 1 的位置上去 这样实际上把队列看作一个环 这种队列称为