《实习二栈及队列的应用.ppt》由会员分享，可在线阅读，更多相关《实习二栈及队列的应用.ppt（25页珍藏版）》请在三一文库上搜索。
1、【实习二】 栈和队列的应用,实习二 （1）栈的应用,【实习题目】 （1）数制转换问题 （2）火烧连营 （3）算术表达式求值,（2）火烧连营,【问题描述】 “火烧连营”是三国演义中的著名典故之一广为流传，假定文本文件c1.txt是火烧连营中的军营分布图，每个字符A代表一个营帐，营帐是可燃物，其他字符代表不可燃的空白地段，文件共有40行70列。 【基本要求】 请你编写程序，读入文本文件的内容。提供MFC界面，输入任意点的x和y值（x70,y40）作为着火点，“火烧连营”后，被燃烧的营帐标上字符X，并把整个结果输出到文件c2.txt中。,【实现提示】 基本思想：从着火点位置开始，按四连通思想上下左右
2、寻找其邻居点 实现思路：开辟一个堆栈，先将着火点压栈，然后重复以下操作：栈顶点出栈并标记X，同时将符合被燃烧条件的邻居点入栈，直到栈空为止。 输出：X序列，搜索可以燃烧的字符！ 【测试数据】 c1.txt,（3）算术表达式求值,【问题描述】 对一个合法的表达式求值。 假设表达式只包含+、-、*、/ 四个双目运算符，并且允许有括号出现，运算符本身不具有二义性。 例如：3.5*(7+2) /(-6),【基本要求】 正确解释表达式； 符合四则运算规则： 先乘除、后加减 从左到右运算 先括号内，后括号外 输出最后的计算结果,【实现关键】 两个栈的使用 两位数以上、负数、小数点？ 【实现方式】 基本：控
3、制台程序 MFC对话框（注意ON_CONTROL_RANGE的使用） Example,可选：功能扩展 算数运算符支持：% 增加函数运算：sqrt、pow、sin、cos、tan MFC界面（仿标准型计算器）,表达式求值的几点提示,1、使用两个工作栈： 一个栈OPTR：存放运算符；stack 另一个栈OPND：存放操作数；stack 2、运算符之间的优先关系 可用二维数组,算符优先顺序,示例：运算符优先级比较,char MyCalculator:Comp(const char left,const char right) /此函数用来比较两个符号的优先级 char t9=+,-,*,/,%,(,
4、),#; int smax99=/*+*/1,1,2,2,2,2,2,1,1, /*-*/ 1,1,2,2,2,2,2,1,1, /*/ 1,1,1,1,1,2,2,1,1, /*/*/ 1,1,1,1,1,2,2,1,1, /*%*/ 1,1,1,1,1,2,2,1,1, /*/ 1,1,1,1,1,1,2,1,1, /*(*/ 2,2,2,2,2,2,2,3,0, /*)*/ 1,1,1,1,1,1,0,1,1, /*#*/ 2,2,2,2,2,2,2,0,3;,int j,k; for(int i=0;i; case 2:return ; case 3:return =; default
5、: ,实习二 （2）栈与队列的综合应用,1、停车场问题 2、魔王语言解释器 3、用栈模拟队列,实习二 的选做内容,【问题描述】 设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为
6、停车场编制按上述要求进行管理的模拟程序。,1、停车场管理模拟,【基本要求】 以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列（或MFC界面）进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息，汽车牌照号以及到达或离去的时刻。对每一组输入的数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。 栈以顺序结构实现，队列以链表结构实现。,【实现提示】 需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据
7、按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。,【思考】 （1）两个栈共享空间，思考应开辟数组的空间是多少？ （2）汽车可有不同种类，则他们的占地面积不同，收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。 （3）汽车可以直接从便道上开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。 （4）停车在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。,2、魔王语言解释器,【问题描述】 有一个魔王总是使用自己的一种非常精炼而抽象的语言讲话，没有人能
8、听懂，但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的： （1）12m （2）（12n）nn-11 在这两种形式中，从左到右均表示解释。试写一个魔王语言的解释系统，把他的话解释成人能听得懂的话。,【基本要求】 用下述两条具体规则和上述规则形式（2）实现。设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量，魔王语言可含人的词汇。 （1）B-tAdA （2）A-sae,【测试数据】 B(ehnxgz)B将解释成tsaedsaeezegexenehetsaedsae 若将小写字母与汉字建立下表所示
9、的对应关系，则魔王说的话是：“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。,【实现提示】 将魔王的语言自右至左进栈，总是处理栈顶字符。若是开括号，则逐一出栈，将字母顺序入队列，直至括号出栈，并按规则要求逐一出队列再处理后入栈。,3、用栈模拟队列,【问题描述】 请用两个栈s1和s2来模拟一个队列。已知栈的三个运算定义如下： Push(S,x)：元素x入S栈; Pop（S，x）：S栈顶元素出栈； S_IsEmpty（S）：判断栈空，true为空，false不为空。 top为栈顶指针 试用栈的运算实现队列的三个运算： （1）EnQueue：入队列，在队列中插入一个元素； （2）
10、DeQueue：出队列，从队列中删除一个元素； （3）Q_IsEmpty：判断队列为空。,【实现提示】利用两个栈模拟一个队列运算的思想： 用一个栈作为输入，另一个栈作为输出。 当进队列时，总是将数据进入到作为输入的栈中； 在输出时，如果作为输出的栈已空，则从输入栈将已输入到输入栈的所有数据输入到输出栈中，然后由输出栈输出数据；如果作为输出的栈不空，则从输出栈输出数据。,【题目分析】栈的特点是后进先出，队列的特点是先进先出。所以，用两个栈s1和s2模拟一个队列时， s1作输入栈，逐个元素压栈，以此模拟队列元素的入队。 当需要出队时，将栈s1退栈并逐个压入栈s2中，s1中最先入栈的元素，在s2中处
11、于栈顶。 s2退栈，相当于队列的出队，实现了先进先出。 显然，只有栈s2为空且s1也为空，才算是队列空。,【算法讨论】算法中假定栈s1和栈s2容量相同。 出队：从栈s2出，当s2为空时，若s1不空，则将s1倒入s2再出栈。 入队：在s1，当s1满后，若s2空，则将s1倒入s2，之后再入队。 因此，队列的容量为两栈容量之和。 元素从栈s1倒入s2，必须在s2空的情况下才能进行，即在要求出队操作时，若s2空，则不论s1元素多少（只要不空），就要全部倒入s2中。,算法思想,栈s1和s2，s1用作入队，s2出队 1、判队满：如果s1满且s2不为空，则队满； 2、判队空：如果s1和s2都为空，则队空； 3、入队：首先判队满， 若队不满：(1)栈s1若不满，则直接压入栈s1； (2)若s1满，则将s1中的所有元素弹出到栈s2中，然后再将元素入栈s1。 4、出队： (1)若s2空就将s1中的所有元素弹出到栈s2中，然后出栈； (2)s2不空就直接从s2中弹出元素。,实习一、二平时成绩记录评分标准,实习一 顺序表、单链表合并拆分（=80分） 大数阶乘 实习二 火烧连营（80=分） 表达式求值或栈和队列综合运用,