资源描述：
《【实习二】栈及队列的应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、【实习二】栈和队列的应用实习二（1）栈的应用【实习题目】（1）数制转换问题（2）火烧连营（3）算术表达式求值（2）火烧连营【问题描述】“火烧连营”是三国演义中的著名典故之一广为流传，假定文本文件c1.txt是火烧连营中的军营分布图，每个字符A代表一个营帐，营帐是可燃物，其他字符代表不可燃的空白地段，文件共有40行70列。【基本要求】请你编写程序，读入文本文件的内容。提供MFC界面，输入任意点的x和y值（x<70,y<40）作为着火点，“火烧连营”后，被燃烧的营帐标上字符’X’，并把整个结果输出到文件c2.txt中。【实现提示】基本思想：从着火点位置开始，按
2、四连通思想上下左右寻找其邻居点……实现思路：开辟一个堆栈，先将着火点压栈，然后重复以下操作：栈顶点出栈并标记‘X’，同时将符合被燃烧条件的邻居点入栈……，直到栈空为止。输出：X序列，搜索可以燃烧的字符！【测试数据】c1.txt（3）算术表达式求值【问题描述】对一个合法的表达式求值。假设表达式只包含+、-、*、/四个双目运算符，并且允许有括号出现，运算符本身不具有二义性。例如：3.5*(7+2)/(-6)【基本要求】正确解释表达式；符合四则运算规则：先乘除、后加减从左到右运算先括号内，后括号外输出最后的计算结果【实现关键】两个栈的使用两位数以上、负数、小数点
3、？【实现方式】基本：控制台程序MFC对话框（注意ON_CONTROL_RANGE的使用）Example可选：功能扩展算数运算符支持：%增加函数运算：sqrt、pow、sin、cos、tanMFC界面（仿标准型计算器）表达式求值的几点提示1、使用两个工作栈：一个栈OPTR：存放运算符；stack另一个栈OPND：存放操作数；stack2、运算符之间的优先关系可用二维数组算符优先顺序+-*/()#+>><<<>>->><<<>>*>>>><>>/>>>><>>(<<<<<=)>>>>>>#<<<<<=示例：运算符优先级比较charM
4、yCalculator::Comp(constcharleft,constcharright)//此函数用来比较两个符号的优先级{chart[9]={'+','-','*','/','%','^','(',')','#'};intsmax[9][9]=/*+*/{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
5、,2,3,0,/*)*/1,1,1,1,1,1,0,1,1,/*#*/2,2,2,2,2,2,2,0,3};intj,k;for(inti=0;i<9;i++){if(left==t[i])j=i;if(right==t[i])k=i;}switch(smax[j][k]){case1:return'>';case2:return'<';case3:return'=';default:……}}实习二（2）栈与队列的综合应用1、停车场问题2、魔王语言解释器3、用栈模拟队列——实习二的选做内容【问题描述】设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可
6、供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。1、停车场管理模拟【基本要求】以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列（或MF
7、C界面）进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息，汽车牌照号以及到达或离去的时刻。对每一组输入的数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。【实现提示】需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。【思考】（1）两个栈
8、共享空间，思考应开辟数组的空间是多少？（2）汽车可有不同种类，则他
