南华大学
计算机科学与技术学院
课 程 设 计 报 告
（ 2007 ~ 2008 学年度 第 1学期 ）
1.实验目的及要求
1）、设计目标（问题描述）
迷宫问题
问题描述：迷宫实验是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。老鼠经多次试验终于得到它学习走迷宫的路线。
2）、功能设计要求
编写一个程序求解迷宫问题。迷宫由m行n列的二维数组设置，0表示无障碍，1表示有障碍。设入口为（1，1），出口为（m，n），每次只能从一个无障碍单元移到周围四个方向上任一无障碍单元。编程实现对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
算法输入：代表迷宫入口的坐标
算法输出：穿过迷宫的结果。
算法要点：创建迷宫，试探法查找路径，输出解
3）、实验目的
1、加深对栈特性理解，以便在解决实际问题中灵活运用它们
2、加深对栈操作实际算法的理解
3、进一步熟悉掌握链表的操作；
4、掌握指针的应用
5、更进一步掌握有关类的操作
4）、 需求分析
1、本程序实现迷宫的探索过程. 以用户和计算机对话的方式，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，然后程序就探索路径并输出路径。
2、本演示程序中，输入形式以“回车符”为结束标志，且允许出现重复字符。
3、利用二维指针实现迷宫位置的存储，并用栈存贮探索路径，每个结点含三个整形变量。输入的形式以回车结束。
4、本程序中，用户可以读去文件里的迷宫，也可自己重新输入迷宫，而且用户可以输入任意大小的迷宫，然后程序自动探索路径，并输出迷宫的路径
5）、创新（见源程序附录）
6）、软件、硬件环境
软件环境：Microsoft Windows Xp Processional2002 Service
Microsoft Visual C++6.0
硬件环境：cpu：AMD Athlon（tm）64x Dual
Processor 3800+2.01GHz Main memory:960MB
2.实验步骤
a.认真阅读课本的相关知识章节。
b.认真分析课题的需求分析和功能分析。
c.根据分析的思路写出伪代码。
d.根据伪代码上机编写程序，进行初步调试。
e.逐步增加完善系统的功能，实现人工智能化。
f.记录上机运行时遇到的错误，进行认真分析。
g.最后认真撰写实验报告，写出实验心得总结。
3. 实验内容
1）、设计概述
(a) 开发平台：VC6.0
(b) 参考书籍：
1.数据结构C++描述 熊岳山 陈怀义 编著 国防科技大学出版社
2、《数据结构与算法》黄定 黄煜廉 编著 广东科技出版社 20##年1月第1版
3、《数据结构辅导与提高》徐孝凯 编著 清华大学出版社 20##年12月第1版
(c) 开发周期： 10天（构思3天、雏形3天、修改2天、再修改1天、完善1天）
2）、处理流程
(a)画出功能结构图
(b)画出主要数据结构的类图
(c)主要函数的程序流程图
1.
main函数流程图：
2.探索路径函数findpath（）
3.自行输入迷宫函数writefile（）
(d)写出数据测试表（输入数据/预期结果）
测试一：从文件中读取迷宫： 001000100
001000101
000011000
011100100
000100001
010001010
011110011
110001011
110000000
输出：
探索路径： （1，1，向下）
（2，1，向下）
（3，1，向下）
（4，1，向下）
（5，1，向右）
（5，2，向右）
（5，3，向下）
（6，3，向右）
（6，4，向右）
（6，5，向上）
（5，5，向右）
（5，6，向右）
（5，7，向下）
（6，7，向下）
（7，7，向下）
（8，7，向下）
（9，7，向右）
（9，8，向右）
（9，9）
测试二：
自己输入迷宫：
001
000
100
输出探索路径：
（1，1，向下）
（2，1，向右）
（2，2，向下）
（3，2，向右）
（3，3）
测试三：
自己输入迷宫：
111
111
000
输出探索路径：
Sorry！找不到路径！
4.实验结果
结果为以下三种情形之一：
1）编译不通过：给出编译错。
Compiling...
stack.cpp
Skipping... (no relevant changes detected)
main.cpp
Linking...
stack.obj : error LNK2005: "public: __thiscall stack::stack(void)" (??0stack@@QAE@XZ) already defined in main.obj
stack.obj : error LNK2005: "public: __thiscall stack::~stack(void)" (??1stack@@QAE@XZ) already defined in main.obj
stack.obj : error LNK2005: "public: void __thiscall stack::Push(struct DataType)" (?Push@stack@@QAEXUDataType@@@Z) already defined in main.obj
stack.obj : error LNK2005: "public: struct DataType __thiscall stack::Pop(void)" (?Pop@stack@@QAE?AUDataType@@XZ) already defined in main.obj
stack.obj : error LNK2005: "public: struct DataType __thiscall stack::GetPop(void)" (?GetPop@stack@@QAE?AUDataType@@XZ) already defined in main.obj
stack.obj : error LNK2005: "public: void __thiscall stack::Clear(void)" (?Clear@stack@@QAEXXZ) already defined in main.obj
stack.obj : error LNK2005: "public: bool __thiscall stack::IsEmpty(void)" (?IsEmpty@stack@@QAE_NXZ) already defined in main.obj
Debug/迷宫问题.exe : fatal error LNK1169: one or more multiply defined symbols found
执行 link.exe 时出错.
迷宫问题.exe - 1 error(s), 0 warning(s)
改正：
在main。cpp中原来包含的是stack.cpp把它改为包含stack.h即可
错误二：
用string直接定义字符串str时，说没有定义str
原因：#include<string>
using namespace std ;没有用标准空间
错误三：
拼写错误
正确结果输出：
接上面：
接上面：
5. 实验总结分析
1)、时间和空间分析
该算法的运行时间和使用系统栈所占有的存储空间与迷宫的大小成正比，迷宫长为m，宽为n，在最好情况下的时间和空间复杂度均为O（m+n），在最差情况下均为O（m*n），平均情况在它们之间
2)、程序的优点
a. 进入演示程序后即显示文本方式的用户界面
b. 本程序模块划分比较合理，且利用指针存储迷宫，操作方便。
c. 能按照玩游戏人的意愿任意输入迷宫大小，并且可以保存新输入的迷宫，方便退出游戏后仍可打开自己定义文件查看迷宫。
3)、遇到的问题及如何解决
a.如何知道哪一点被探索过且路径不通？
答：maze【i】【j】本来时表示通与不通，那么可以当探索该点之后，将其值赋为-1,就可以知道此点已经被访问过
b.如何正确的使用文件读入迷宫？
答：查看大一学的C++课本，仔细阅读文件那一章。
c.我想让用户在每次玩游戏之后都能查看输入的迷宫，我想的是运行程序时随意新建文本文档，开始是直接输入一个.txt结尾的字符串，但编译好多错误,我猜应该是要调用相关函数，但具体是那一个不清楚。
答：去图书馆借阅相关资料，要调用相应的库函数。
4)、存在的缺陷、改进设想
每当自行输入迷宫后，生成相应的文件保存，但是我在想：一旦玩游戏的人多了，玩的次数多了，那么生成的保存迷宫文件就会很多，会给人工智能化系统造成文件冗余。我设想：能不能在一段时间之后系统自动调用函数来清除冗余文件。
5)、自我评价、经验体会等
通过这次课程设计，体会如下：
１、进一步熟悉掌握了有关栈的基本操作；
２、对迷宫有了更多的认识
3、更进一步掌握有关类的操作
4、由于对栈的算法推敲不足，使程序调试时费时不少
总之：我认为这次课程设计做的很好。课程设计的成功使我相信一句话：有付出就会有收获，要相信自己。
6. 附录（源程序清单，要求含有至少30%的源码附有注释）
迷宫程序代码（本程序有个创新点）
/////////////////////////////////////////////////////////////////////
/*
Name: stack.h
Author: 罗丹
Description: 用于记录探索路径的栈类头文件
*/
#include<iostream>
#include"fstream"
using namespace std;
class DataType //定义描述迷宫中当前位置的类型
{public:
int x; //x代表当前位置的行坐标
int y; //y代表当前位置的列坐标
int pre; //pre表示移动到下一步的方向
};
class Move //定义下一个位置的方向
{ public:
int x;
int y;
};
class Node //链表结点
{public:
DataType data;
Node *next;
};
//下面定义栈
class stack
{private:
Node *top; //指向第一个结点的栈顶指针
public:
stack(); //构造函数，置空栈
~stack(); //析构函数
void Push(DataType data);//把元素data压入栈中
DataType Pop(); //使栈顶元素出栈
DataType GetPop(); //取出栈顶元素
void Clear(); //把栈清空
bool IsEmpty(); //判断栈是否为空，如果为空则返回1，否则返回0
};
/////////////////////////////////////////////////////////////////////
/*
Name: stack.cpp
Author: 罗丹
Description: 用于记录探索路径的栈类实现文件
*/
#include"stack.h"
stack::stack() //构造函数，置空栈
{top=NULL;}
stack::~stack() //析构函数
{}
void stack::Push(DataType x) //进栈
{Node *TempNode;
TempNode=new Node;
TempNode->data=x;
TempNode->next=top;
top=TempNode;}
DataType stack::Pop() //栈顶元素出栈
{
DataType Temp;
Node *TempNode=NULL;
TempNode=top;
top=top->next;
Temp=TempNode->data;
delete TempNode;
return Temp;
}
DataType stack::GetPop() //取出栈顶元素
{return top->data;}
void stack::Clear() //把栈清空
{top=NULL;}
bool stack::IsEmpty() //判断栈是否为空，如果为空则返回1，否则返回0
{if(top==NULL) return true;
else return false;}
/////////////////////////////////////////////////////////////////////
/*
Name: main.cpp
Author: 罗丹
Description: 主函数文件
*/
#include"stack.h"
#include<iostream>
#include<string>
#include<fstream>
using namespace std ;
/*
Description: 外部函数的声明部分
*/
bool findpath(int **maze,int m,int n); //寻找迷宫路径
void PrintPath(stack p); //输出路径
void Restore(int **maze,int m,int n); //恢复迷宫
Move move[4]={{0,1},{1,0},{0,-1},{-1,0}}; //定义当前位置移动的4个方向(上，右，下，左)
int** readFile (int &m,int &n);
int** writeFile(int &m,int &n);
/*
Description: main.cpp
*/
void main()
{
cout<<endl;//
cout<<"◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆"<<endl;
cout<<" 20##-20##年度第一学期数据结构课程之课程设计 "<<endl;
cout<<endl;
cout<<" ——迷宫问题 "<<endl;
cout<<" 开发员 : 罗丹"<<endl;
cout<<" 专业班级: 计算机061班"<<endl;
cout<<"◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆"<<endl;
cout<<" 欢迎进入迷宫游戏 "<<endl;
int m=0,n=0;
int **maze;
char ch;
int flag=0,flag1=0;
while(flag1==0)
{
while(flag==0)//标志是否重新选择
{cout<<endl;
cout<<" ★请从以下选项中选择获取迷宫的方法！"<<endl;
cout<<" <a>从文件中读取"<<endl;
cout<<" <b>直接自行输入"<<endl;
cout<<" ★请选择:";
cin>>ch;
if(ch=='a'){maze=readFile(m,n);flag=1;}
else if(ch=='b'){maze=writeFile(m,n);flag=1;}
else
cout<<" ★ Sorry!您输入的选择代码不在范围内!请从新选择"<<endl;
}
if(findpath(maze,m,n))
cout<<" ★ Congratulations! 迷宫路径探索成功!"<<endl; //得到路径
else
cout<<" ★Sorry! 路径不存在★"<<endl;
cout<<endl;
cout<<" ★ 继续玩吗？(y/n)";
char c;
cin>>c;
if(c==n) flag1=1;
else flag=0;
}
cout<<"◆◆◆◆◆◆◆ 谢谢,您已经退出迷宫系统 ◆◆◆◆◆◆◆"<<endl;
cout<<"◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆"<<endl;
}
/*
Description: 获取迷宫函数
*/
int** readFile (int &m,int &n) //读出文件
{int **maze;
int i=0,j=0;
cout<<" ★您选择的是直接从文件中读取迷宫!"<<endl;
cout<<endl;
cout<<" 文件中的迷宫如下： "<<endl;
char ch; //定义一个字符，读取文件中的内容
ifstream open("maze.txt"); //定义一个文件对象，并打开文件"maze.txt"
//读取内容记录行数和列数 （创新点一：从文件中直接读取迷宫）
while(open.get(ch)) //从读取文件中内容（一旦个字符形式）
{if(ch=='0'||ch=='1')
{j++; } //是‘0’或‘1’字符宽就加1
if(ch=='\n')
{
i++; //如果是换行符，就行加1
n=j; //得列数
j=0;
}
}
open.close(); //读取文件结束
m=i;
maze=new int *[m+2]; //申请长度等于行数加2的二维指针(为后面的回复迷宫打下基础)
for(i= 0;i<m+2;i++) //申请空间
{maze[i]=new int[n+2];}
i=j=1;
ifstream open1("maze.txt"); //重新读取文件，以得到内容
while(open1.get(ch))
{
if(ch=='1'||ch=='0')
{maze[i][j]=ch-'0'; //把数字字符转化为数字，并存到指针里
cout<<maze[i][j]<<" "; //在屏幕中显示迷宫
j++;}
if(ch=='\n') //遇到换行，指针也相应换行
{cout<<endl;
i++;
j=1;}
}
open1.close(); //读取结束
return maze;
}
int** writeFile (int &m,int &n) //将自定义迷宫写入文件
{int a,b;
int i,j;
int**maze;
cout<<" ★您选择的是自行输入迷宫!"<<endl;
cout<<" 请输入迷宫的长:";cin>>b; //输入迷宫的长和宽
cout<<" 请输入迷宫的宽:";cin>>a;
cout<<" ★请输入迷宫内容(0代表可通，1代表不通):\n";
m=a;
n=b; //m,n分别代表迷宫的行数和列数
maze=new int *[m+2];
for(i= 0;i<m+2;i++)
{maze[i]=new int[n+2];} //创新点二：:随意申请空间
for(i=1;i<=m;i++) //输入迷宫的内容，0代表可通，1代表不通
for(j=1;j<=n;j++)
cin>>maze[i][j];
cout<<" ★是否保存新迷宫？(y/n): ";
char choose;
cin>>choose;
if(choose=='Y'||choose=='y')
{char ch;
string str;
cout<<" ★请输入保存迷宫的文件名(以.txt结束):";
cin>>str;
ofstream open(str.c_str()); //创新点三：按玩游戏人的意愿创建存储迷宫的文件，也可不建立。
for(i=1;i<=m;i++)
{for(j=1;j<=n;j++)
{ch='0'+maze[i][j];
open<<ch;}
open<<endl;
flush(cout);}
open.close();}
for(i=0;i<m+2;i++)
maze[i][0]=maze[i][n+1]=1;
for(i=0;i<n+2;i++)
maze[0][i]=maze[m+1][i]=1;
return maze;
}
/*
Description: 探索路径函数
*/
bool findpath(int **maze,int m,int n)
{stack q,p; //创新点四：用栈p、q,分别存探索迷宫的过程和存储路径
DataType Temp1,Temp2;
int x,y,loop;
Temp1.x=1;
Temp1.y=1;
q.Push(Temp1); //将入口位置入栈
p.Push(Temp1);
maze[1][1]=-1; //创新点五：标志入口位置已到达过
while(!q.IsEmpty()) //栈q非空，则反复探索
{Temp2=q.GetPop();
if(!(p.GetPop().x==q.GetPop().x&&p.GetPop().y==q.GetPop().y))
p.Push(Temp2);
//如果有新位置入栈，则把上一个探索的位置存入栈p
for(loop=0;loop<4;loop++) //探索当前位置的4个相邻位置
{x=Temp2.x+move[loop].x;
y=Temp2.y+move[loop].y;
if(maze[x][y]==0) //判断新位置是否可达
{Temp1.x=x;
Temp1.y=y;
maze[x][y]=-1; //标志新位置已到达过
q.Push(Temp1); } //新位置入栈
if((x==(m))&&(y==(n))) //成功到达出口
{Temp1.x=m;
Temp1.y=n;
Temp1.pre=0;
p.Push(Temp1); //把最后一个位置入栈
PrintPath(p);
Restore(maze,m,n); //恢复路径（因为迷宫里面的内容已被改变
return 1; }} //表示成功找到路径
if(p.GetPop().x==q.GetPop().x&&p.GetPop().y==q.GetPop().y)//如果没有新位置入栈，则返回到上一个位置
{p.Pop();
q.Pop();}}
return 0; //表示查找失败，即迷宫无路经
}
/*
Description: 输出路径函数
*/
void PrintPath(stack p) //输出路径
{cout<<endl;
cout<<" ★★迷宫的路径为"<<endl;
cout<<" 说明:括号内的内容分别表示为(行坐标,列坐标,方向)\n";
stack t; //定义一个栈，按从入口到出口存取路径
int row,column;
DataType data;
Node *temp;
temp=new Node; //申请空间
temp->data=p.Pop();
t.Push(temp->data); //第一个位置入栈
delete temp;
while(!p.IsEmpty()) //栈p非空，则转移
{temp=new Node;
temp->data=p.Pop(); //获取下一个位置
//得到行走方向
row=t.GetPop().x-temp->data.x; //行坐标方向
column=t.GetPop().y-temp->data.y; //列坐标方向
if(row==1) temp->data.pre=1; //向下，用1表示
else if(column==1) temp->data.pre=2; //向右，用2表示
else if(row==-1) temp->data.pre=3; //向上，用3表示
else if(column==-1) temp->data.pre=4; //向左，用4表示
t.Push(temp->data); //把新位置入栈
delete temp;
}
while(!t.IsEmpty()) //栈非空，继续输出
{data=t.Pop();
cout<<" "<<'('<<data.x<<','<<data.y<<",";
switch(data.pre) //输出相应的方向
{case 0:cout<<")\n";break;
case 1:cout<<"向下)\n";break;
case 2:cout<<"向右)\n";break;
case 3:cout<<"向上)\n";break;
case 4:cout<<"向左)\n";break;
}}}
/*
Description: 恢复路径函数
*/
void Restore(int **maze,int m,int n) //恢复迷宫
{int i,j;
for(i=0;i<m+2;i++) //遍历指针
for(j=0;j<n+2;j++)
{if(maze[i][j]==-1) //恢复探索过位置，即把-1恢复为0
maze[i][j]=0;}
}