迷宫游戏数据结构课程设计.doc

计算机解迷宫问题通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。迷宫的入口点的下标为（1，1），出口点的下标为（m，n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫的任一位置，均可约定有东、南、西、北四个方向可通。有一种简单走出迷宫的方法，把手放在右边的墙上开始前进，始终不要把手从墙上移开。如果迷宫向右拐，你也顺着墙向右拐。只要不把手从墙上移开，最终就会到达迷宫的出口。当然这样得到的路径可能不是一个最短的路径，但它可以最终得到结果，换句话说，这种方法走不出迷宫的风险是最小的。
本设计是为了实现一个可视化迷宫，以及利用最短路径算法寻找迷宫的出路以及将最短路径打印在屏幕上，并且限制小老鼠不能穿越墙，只能在路径上移动。而且可以根据自己的需要设计迷宫地图。

关键词 迷宫；栈；VC++ 6.0

目录
1 课设题目 1
1.1课设题目………………………………………………………………………………….1
1.2基本要求：……………………………………………………………………………….1
1.3 需求分析…………………………………………………………………………………1
2 程序总体设计 2
2.1流程图：………………………………………………………………………………….2
2.2概要设计………………………………………………………………………………….6
2.3 运行结果及分析…………………………………………………………………………7
总结 9
源程序 10
参考文献 20

1 课设题目
1.1课设题目
编写一个程序求解迷宫问题。迷宫由m行n列的二维数组设置，0表示无障碍，1表示有障碍。设入口为（1，1），出口为（m，n），每次只能从一个无障碍单元移到周围四个方向上任一无障碍单元。编程实现对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
算法输入：代表迷宫入口的坐标
算法输出：穿过迷宫的结果。
算法要点：创建迷宫，试探法查找路径，输出解

1.2基本要求：
1.求得的通路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一个坐标的方向。
2.输出迷宫示意图

1.3 需求分析
1、本程序实现迷宫的探索过程. 以用户和计算机对话的方式，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，然后程序就探索路径并输出路径。
2、本演示程序中，输入形式以“回车符”为结束标志，且允许出现重复字符。
3、利用二维指针实现迷宫位置的存储，并用栈存贮探索路径，每个结点含三个整形变量。输入的形式以回车结束。
4、本程序中，用户可以读去文件里的迷宫，也可自己重新输入迷宫，而且用户可以输入任意大小的迷宫，然后程序自动探索路径，并输出迷宫的路径。
2 程序总体设计
2.1流程图：
1.功能结构图

Main主函数模块

输出路径模块printpath（）

获取迷宫模块
探索路径模块
Findpath（）

存储探索路径模块stack类
读文件
Readfile（）
写文件
Writefile（）

Stack类

数据模块

操作模块

盘空函数isempty（）
清空函数clear（）
取栈顶函数getpop（）
进栈与出栈函数push（）
Pop（）
构造与析构函数stack（）
~stack（）
结点模块
Node*top

结点数据类型模块datatype类

2.画出主要数据结构的类图

class 类名DataType //定义描述迷宫中当前位置的类型
数据成员
访问控制权限 数据类型 变量名;
public:
int x; //x代表当前位置的行坐标
int y; //y代表当前位置的列坐标
int dir; //dir表示移动到下一步的方向

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

开始
3.main函数流程图

显示系统信息

选择获取迷宫的方式ch

Ch==’ b’
Ch==’a’

Readfile()文件读取
自行输入
Writefile（）

探索迷宫路径是否存在

输出迷宫路径

是否继续游戏

退出

开始
2.探索路径函数findpath（）

Temp1.x=1
Temp1.y=1

入口进栈p.push
q.push

是否非空

temp2=q.getpop（）

P q栈顶是否相等

探索上下左右四个方位是否有路径

到达新位置

是否到达出口

最后一个元素进栈输出路径

回复以改变的迷宫

结束

开始
3.自行输入迷宫函数writefile（）

输入长宽m，n
动态申请空间二位数组空间

i<=m

是否保存迷宫

J<=n

i++ ；j++
输入迷宫

输入保存迷宫的文件名

保存迷宫

结束

2.2概要设计
1.①构建一个二维数组maze[M+2][N+2]用于存储迷宫矩阵
②自动或手动生成迷宫，即为二维数组maze[M+2][N+2]赋值
③构建一个队列用于存储迷宫路径
④建立迷宫节点struct point,用于存储迷宫中每个节点的访问情况
⑤实现搜索算法
⑥屏幕上显示操作菜单

2.本程序包含10个函数：
(1)主函数 main()
(2)手动生成迷宫函数 shoudong_maze()
(3)打印迷宫路径 (若存在路径) result_maze()
(4)入队 enqueue()
(5)出队 dequeue()
(6)判断队列是否为空 is_empty()
(7)访问节点 visit()
(8)搜索迷宫路径 mgpath()

2.3 运行结果及分析

总结

通过这段时间的数据结构课程设计，本人对计算机的应用，数据结构的作用以及C语言的使用都有了更深的了解。尤其是C语言的进步让我深刻的感受到任何所学的知识都需要实践，没有实践就无法真正理解这些知识以及掌握它们，使其成为自己的财富。在理论学习和上机实践的各个环节中，通过自主学习和认真听老师讲课分析，我收获了不少。当然也遇到不少的问题，也正是因为这些问题引发的思考给我带了收获。从当初不喜欢上机写程序到现在能主动写程序，从当初拿着程序不只如何下手到现在知道如何分析问题，如何用专业知识解决实际问题的转变，我发现无论是专业知识还是动手能力，自己都有很大程度的提高。在这段时间里，我对for、while等的循环函数用法更加熟悉，逐渐形成了较好的编程习惯。在老师的指导帮助下，同学们课余时间的讨论中，这些问题都一一得到了解决。在程序的调试能力上，无形中得到了许多的提高。例如：头文件的使用，变量和数组的范围问题，定义变量时出现的问题等等。
在实际的上机操作过程中，不仅是让我们了解数据结构的理论知识，更重要的是培养解决实际问题的能力，所以相信通过此次实习可以提高我们分析设计能力和编程能力，为后续课程的学习及实践打下良好的基础。时间过得真快，大学生活不知不觉就走过了一学期，这一学期的大学学习和课程实践阶段的提高，使我们本身知识得到提高的同时，也增强了我们对未来工作的信心，我们相信自己未来两年半的学习更使我们有能力胜任将来的工作。

源程序
#include<iostream>
using namespace std;

class T//定义描述迷宫中当前位置的结构类型
{
public:
int x;//x代表当前位置的行坐标
int y;//y代表当前位置的列坐标
int dir;//0:无效,1:东,2:南,3:西,4:北
};

class LinkNode//链表结点
{
friend class Stack;
public:
T data;
LinkNode *next;
};

class Stack
{
private:
LinkNode *top;//指向第一个结点的栈顶指针
public:
Stack();//构造函数，置空栈
~Stack()//析构函数
{}
void Push(T e);//元素data入栈中
T Pop();//栈顶元素出栈
T GetPop();//取出栈顶元素
void Clear();//把栈清空
bool empty();//判断栈是否为空，如果为空则返回1，否则返回0
};

Stack::Stack()//构造函数，置空栈
{
top=NULL;
}

void Stack::Push(T e)//元素x入栈中
{
LinkNode *P;
P=new LinkNode;
P->data=e;
P->next=top;
top=P;
}

T Stack::Pop()//栈顶元素出栈
{
T Temp;
LinkNode *P;
P=top;
top=top->next;
Temp=P->data;
delete P;
return Temp;
}

T Stack::GetPop()//取出栈顶元素
{
return top->data;
}

void Stack::Clear()//把栈清空
{
top=NULL;
}

bool Stack::empty()//判断栈是否为空，如果为空则返回1，否则返回0
{
if(top==NULL) return 1;
else return 0;
}

int move[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//定义当前位置移动的4个方向

void PrintPath(Stack p)//输出路径
{
cout<<"迷宫的路径为\n";
cout<<"括号内的内容分别表示为(行坐标,列坐标,数字化方向,方向)\n";
Stack t;//定义一个栈，按从入口到出口存取路径
int a,b;
T data;
LinkNode *temp;
temp=new LinkNode;//获取空间
temp->data=p.Pop();//取栈p的顶点元素，即第一个位置
t.Push(temp->data);//第一个位置入栈t
delete temp;//释放空间
while(!p.empty())//如果栈p非空，则反复转移
{
temp=new LinkNode;
temp->data=p.Pop();//获取下一个位置
//得到行走方向
a=t.GetPop().x-temp->data.x;//行坐标方向
b=t.GetPop().y-temp->data.y;//列坐标方向
if(a==1) temp->data.dir=1;//方向向下，用1表示
else if(b==1) temp->data.dir=2;//方向向右，用2表示
else if(a==-1) temp->data.dir=3;//方向向上，用3表示
else if(b==-1) temp->data.dir=4;//方向向左，用4表示
t.Push(temp->data);//把新位置入栈
delete temp;
}//输出路径，包括行坐标，列坐标，下一个位置方向
while(!t.empty())//栈非空，继续输出
{
data=t.Pop();
cout<<'('<<data.x<<','<<data.y<<','<<data.dir<<",";//输出行坐标，列坐标
switch(data.dir)//输出相应的方向
{
case 1:cout<<"↓)\n";break;
case 2:cout<<"→)\n";break;
case 3:cout<<"↑)\n";break;
case 4:cout<<"←)\n";break;
case 0:cout<<")\n";break;
}
}
}

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;
}
}

int** GetMaze(int &m,int &n)//返回存取迷宫的二维指针
{
int **maze;//定义二维指针存取迷宫
int i=0,j=0;
cout<<"请输入迷宫的长和宽:";
int a,b;cin>>a>>b;//输入迷宫的长和宽
cout<<"请输入迷宫内容:(0为通路，1为墙)\n";
m=a;
n=b;//m,n分别代表迷宫的行数和列数
maze=new int *[m+2];//获取长度等于行数加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];
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;//返回存贮迷宫的二维指针maze
};

bool Mazepath(int **maze,int m,int n)//寻找迷宫maze中从（0，0）到（m,n）的路径
{
Stack q,p;//定义栈p、q,分别存探索迷宫的过程和存储路径
T Temp1,Temp2;
int x,y,loop;
Temp1.x=1;
Temp1.y=1;
q.Push(Temp1);//将入口位置入栈
p.Push(Temp1);
maze[1][1]=-1;//标志入口位置已到达过
while(!q.empty())//栈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][0];//计算出新位置x位置值
y=Temp2.y+move[loop][1];//计算出新位置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.dir=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;//表示查找失败，即迷宫无路经
}

int main()
{
int m=0,n=0;//定义迷宫的长和宽
int **maze;//定义二维指针存取迷宫
maze=GetMaze(m,n);//调用GetMaze(int &m,int &n)函数，得到迷宫
if(Mazepath(maze,m,n))//调用Mazepath(int **maze,int m,int n)函数获取路径
cout<<"迷宫路径探索成功!\n";
else cout<<"路径不存在!\n";
return 0;
}

参考文献
[1] 严蔚敏吴伟民数据结构（C语言版）清华大学出版社，2000
[2] 文益民周学毛李健数据结构与程序设计人民邮电出版社 2008
[3] 谭浩强 C程序设计（第三版）清华大学出版设 2008
[4] 林锐韩永泉高质量程序设计指南—C++/C语言第3版 2007

1. 基于C8051F单片机直流电动机反馈控制系统的设计与研究
2. 基于单片机的嵌入式Web服务器的研究
3. MOTOROLA单片机MC68HC（8）05PV8/A内嵌EEPROM的工艺和制程方法及对良率的影响研究
4. 基于模糊控制的电阻钎焊单片机温度控制系统的研制
5. 基于MCS-51系列单片机的通用控制模块的研究
6. 基于单片机实现的供暖系统最佳启停自校正（STR）调节器
7. 单片机控制的二级倒立摆系统的研究
8. 基于增强型51系列单片机的TCP/IP协议栈的实现
9. 基于单片机的蓄电池自动监测系统
10. 基于32位嵌入式单片机系统的图像采集与处理技术的研究
11. 基于单片机的作物营养诊断专家系统的研究
12. 基于单片机的交流伺服电机运动控制系统研究与开发
13. 基于单片机的泵管内壁硬度测试仪的研制
14. 基于单片机的自动找平控制系统研究
15. 基于C8051F040单片机的嵌入式系统开发
16. 基于单片机的液压动力系统状态监测仪开发
17. 模糊Smith智能控制方法的研究及其单片机实现
18. 一种基于单片机的轴快流CO〈,2〉激光器的手持控制面板的研制
19. 基于双单片机冲床数控系统的研究
20. 基于CYGNAL单片机的在线间歇式浊度仪的研制
21. 基于单片机的喷油泵试验台控制器的研制
22. 基于单片机的软起动器的研究和设计
23. 基于单片机控制的高速快走丝电火花线切割机床短循环走丝方式研究
24. 基于单片机的机电产品控制系统开发
25. 基于PIC单片机的智能手机充电器
26. 基于单片机的实时内核设计及其应用研究
27. 基于单片机的远程抄表系统的设计与研究
28. 基于单片机的烟气二氧化硫浓度检测仪的研制
29. 基于微型光谱仪的单片机系统
30. 单片机系统软件构件开发的技术研究
31. 基于单片机的液体点滴速度自动检测仪的研制
32. 基于单片机系统的多功能温度测量仪的研制
33. 基于PIC单片机的电能采集终端的设计和应用
34. 基于单片机的光纤光栅解调仪的研制
35. 气压式线性摩擦焊机单片机控制系统的研制
36. 基于单片机的数字磁通门传感器
37. 基于单片机的旋转变压器-数字转换器的研究
38. 基于单片机的光纤Bragg光栅解调系统的研究
39. 单片机控制的便携式多功能乳腺治疗仪的研制
40. 基于C8051F020单片机的多生理信号检测仪
41. 基于单片机的电机运动控制系统设计
42. Pico专用单片机核的可测性设计研究
43. 基于MCS-51单片机的热量计
44. 基于双单片机的智能遥测微型气象站
45. MCS-51单片机构建机器人的实践研究
46. 基于单片机的轮轨力检测
47. 基于单片机的GPS定位仪的研究与实现
48. 基于单片机的电液伺服控制系统
49. 用于单片机系统的MMC卡文件系统研制
50. 基于单片机的时控和计数系统性能优化的研究
51. 基于单片机和CPLD的粗光栅位移测量系统研究
52. 单片机控制的后备式方波UPS
53. 提升高职学生单片机应用能力的探究
54. 基于单片机控制的自动低频减载装置研究
55. 基于单片机控制的水下焊接电源的研究
56. 基于单片机的多通道数据采集系统
57. 基于uPSD3234单片机的氚表面污染测量仪的研制
58. 基于单片机的红外测油仪的研究
59. 96系列单片机仿真器研究与设计
60. 基于单片机的单晶金刚石刀具刃磨设备的数控改造
61. 基于单片机的温度智能控制系统的设计与实现
62. 基于MSP430单片机的电梯门机控制器的研制
63. 基于单片机的气体测漏仪的研究
64. 基于三菱M16C/6N系列单片机的CAN/USB协议转换器
65. 基于单片机和DSP的变压器油色谱在线监测技术研究
66. 基于单片机的膛壁温度报警系统设计
67. 基于AVR单片机的低压无功补偿控制器的设计
68. 基于单片机船舶电力推进电机监测系统
69. 基于单片机网络的振动信号的采集系统
70. 基于单片机的大容量数据存储技术的应用研究
71. 基于单片机的叠图机研究与教学方法实践
72. 基于单片机嵌入式Web服务器技术的研究及实现
73. 基于AT89S52单片机的通用数据采集系统
74. 基于单片机的多道脉冲幅度分析仪研究
75. 机器人旋转电弧传感角焊缝跟踪单片机控制系统
76. 基于单片机的控制系统在PLC虚拟教学实验中的应用研究
77. 基于单片机系统的网络通信研究与应用
78. 基于PIC16F877单片机的莫尔斯码自动译码系统设计与研究
79. 基于单片机的模糊控制器在工业电阻炉上的应用研究
80. 基于双单片机冲床数控系统的研究与开发
81. 基于Cygnal单片机的μC/OS-Ⅱ的研究
82. 基于单片机的一体化智能差示扫描量热仪系统研究
83. 基于TCP/IP协议的单片机与Internet互联的研究与实现
84. 变频调速液压电梯单片机控制器的研究
85. 基于单片机γ-免疫计数器自动换样功能的研究与实现
86. 基于单片机的倒立摆控制系统设计与实现
87. 单片机嵌入式以太网防盗报警系统
88. 基于51单片机的嵌入式Internet系统的设计与实现
89. 单片机监测系统在挤压机上的应用
90. MSP430单片机在智能水表系统上的研究与应用
91. 基于单片机的嵌入式系统中TCP/IP协议栈的实现与应用
92. 单片机在高楼恒压供水系统中的应用
93. 基于ATmega16单片机的流量控制器的开发
94. 基于MSP430单片机的远程抄表系统及智能网络水表的设计
95. 基于MSP430单片机具有数据存储与回放功能的嵌入式电子血压计的设计
96. 基于单片机的氨分解率检测系统的研究与开发
97. 锅炉的单片机控制系统
98. 基于单片机控制的电磁振动式播种控制系统的设计
99. 基于单片机技术的WDR-01型聚氨酯导热系数测试仪的研制
100. 一种RISC结构8位单片机的设计与实现
101. 基于单片机的公寓用电智能管理系统设计
102. 基于单片机的温度测控系统在温室大棚中的设计与实现
103. 基于MSP430单片机的数字化超声电源的研制
104. 基于ADμC841单片机的防爆软起动综合控制器的研究
105. 基于单片机控制的井下低爆综合保护系统的设计
106. 基于单片机的空调器故障诊断系统的设计研究
107. 单片机实现的寻呼机编码器
108. 单片机实现的鲁棒MRACS及其在液压系统中的应用研究
109. 自适应控制的单片机实现方法及基上隅角瓦斯积聚处理中的应用研究
110. 基于单片机的锅炉智能控制器的设计与研究
111. 超精密机床床身隔振的单片机主动控制
112. PIC单片机在空调中的应用
113. 单片机控制力矩加载控制系统的研究
项目论证，项目可行性研究报告，可行性研究报告，项目推广，项目研究报告，项目设计，项目建议书，项目可研报告，本文档支持完整下载，支持任意编辑！选择我们，选择成功！
项目论证，项目可行性研究报告，可行性研究报告，项目推广，项目研究报告，项目设计，项目建议书，项目可研报告，本文档支持完整下载，支持任意编辑！选择我们，选择成功！
单片机论文，毕业设计，毕业论文，单片机设计，硕士论文，研究生论文，单片机研究论文，单片机设计论文，优秀毕业论文，毕业论文设计，毕业过关论文，毕业设计，毕业设计说明，毕业论文，单片机论文，基于单片机论文，毕业论文终稿，毕业论文初稿，本文档支持完整下载，支持任意编辑！本文档全网独一无二，放心使用，下载这篇文档，定会成功！

21