火烧连营.doc

Lab_2 栈和队列及其应用
一、实习目的与要求
1、熟练掌握栈和队列结构的概念、结构特点及相关操作(构造、入/出栈(队列)等);
2、熟悉顺序栈和链式栈,循环队列和链式队列结构的特点及异同;
3、选择并设计合适的栈或队列结构解决实际应用问题。
4、从以下题目选择至少1题完成。
二、实习题目
【题目】火烧连营
【问题描述】
“火烧连营”是三国演义中的著名典故之一广为流传,,每个字符A代表一个营帐,营帐是可燃物,其他字符代表不可燃的空白地段,文件共有40行70列。
【基本要求】
请你编写程序,读入文本文件的内容。提供MFC界面,输入任意点的x和y值(x<70,y<40)作为着火点,“火烧连营”后,被燃烧的营帐标上字符’X’,。
【实现提示】
基本思想:从着火点位置开始,按四连通思想上下左右寻找其邻居点……
实现思路:开辟一个堆栈,先将着火点压栈,然后重复以下操作:栈顶点出栈并标记‘X’,同时将符合被燃烧条件的邻居点入栈……,直到栈空为止。
输出:X序列,搜索可以燃烧的字符!
【测试数据】

【算法分析与设计】
问题分析与设计思想
该程序的实现需要做到文件的输入输出,栈的应用,以及MFC的使用。读取文件中的数据,然后储存在数组中,在利用算法实现其中字符的改变,最后再将字符存入文件中,保存起来。
算法实现思想:开辟一个堆栈,从着火点位置开始,按四连通思想上下左右寻找其邻居点,先将着火点压栈,然后重复以下操作:栈顶点出栈并标记‘X’,同时将符合被燃烧条件的邻居点入栈……,直到栈空为止。
出现的问题及解决办法
:使用fstream的头文件以及循环成功将数据导入。
。二位数组作参数传递,得把每个数组的首地址传过去才行。
。需要压栈的是二位数组的下标,是一个坐标。解决方法有两个:一是定义一个Point类,作为坐标。二则是利用出入栈的有序性,两个数一组。
。文件新建的位置需要自