数据结构迷宫设计

1、软件学院课程设计报告设计名称： 数据结构课程设计 选题名称： 迷宫问题求解 姓 名： 王海洋 学 号： 1515925530 专业班级 移动二班 系 （院）： 软件学院 设计时间： 2016.12.52016.12.9 设计地点： 15#606 1课程设计目的通过布置具有一定难度的实际程序设计项目，使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法；使学生掌握分析问题，求解问题的方法并提高学生设计编程实现的能力。2课程设计任务与要求：任务设计题目从任务书所列选题表中选取，每人1题。要求：基本要求：1. 要求利用CC+语言来完成系统

2、的设计； 2. 突出C语言的函数特征（以多个函数实现每一个子功能）或者C+语言面向对象的编程思想；3. 画出功能模块图；4. 进行简单界面设计，能够实现友好的交互；5. 具有清晰的程序流程图和数据结构的详细定义；6. 熟练掌握C语言或者C+语言的各种操作。创新要求：在基本要求达到后，可进行创新设计，如系统用户功能控制，改进算法的实现，实现友好的人机交互等等 3课程设计说明书一 需求分析1.可以任意定义一个迷宫，用栈的方法求出找出迷宫的通路，并把路径输出出来。2. 迷宫的存储使用数组存储；3. 应该考虑算法的时间和空间复杂度。4. 当确定迷宫的规模以及形态以后要把至少一条能走出迷宫的路径输出出来

3、；5.当迷宫不通时要能修改迷宫和出入口6.程序应当满足正确性、可读性、健壮性和高效率及低存储量等目标要求，遵循代码规范，方便调试和阅读。二 系统设计 利用了C+完成了这个迷宫问题求解。在设计中采用二维数组来保存迷宫地图，利用栈来在迷宫中找寻通道； 基本功能：（1） 选择自动生成迷宫还是手动输入迷宫地图，0为通路，1为不通（2） 选择出入口的设置是随机生成还是手动输入；（3） 当迷宫不通时，选择重新生成迷宫或者重新设置出口、入口；有功能模块图和流程图 1.迷宫流程图：2.寻找迷宫通路函数：3.查找迷宫通路方向函数三 详细设计 1、首先写入头文件和宏定义#include <iostream&

4、gt; #include<stdlib.h>#include<windows.h>#include<time.h>using namespace std; #define OVERFLOW -1 /分配空间时未分配 返回值 #define MAXSIZE 100 /栈的最大空间 #define INCREASE 10 /栈慢时 再分配空间 #define ERROR 0#define OK 1#define Status int2、栈的元素类型和栈指针等的定义typedef struct/迷宫中x行y列的位置 int x; int y; Locate; ty

5、pedef struct/栈类型 int ord; /通道块在路径上的“序号” Locate seat; /通道块在迷宫中的“坐标位置” int di; /从此通道块走向下一通道块的方向1:东 2:北 3:西 顺时针) MazeType; typedef struct MazeType *base;/栈底指针 MazeType *top; /栈顶指针 int stacksize; /栈储存数据大小 MazeStack;3.。所有函数的声明Status InitStack(MazeStack &S); /栈的初始化 Status Push(MazeStack &S, MazeTy

6、pe &e);/入栈 Status Pop(MazeStack &S, MazeType &e); /出栈 Status StackEmpty(MazeStack &S); /判断栈是否为空 Status MazePath(Locate start,Locate end);/迷宫路径 求解 Status Pass(Locate &pos); /判断该位置能否通过 void Menu();/菜单函数，选择手动生成迷宫还是自动生成等 void CreatMaze(int mazeMap1010);/自动创建迷宫void InputMaze(int mazeM

7、ap1010);/手动生成迷宫 void SetMaze(Locate &start,Locate &end);/设置迷宫出口入口 void ResetMaze(Locate &start,Locate &end);/当迷宫不通时，重新设置入口出口坐标 void PrintMaze(int mazeMap1010);/输出迷宫 void FootPrint(Locate pos); /走过的路留下标记 2void MakePrint(Locate pos); /不通 设置为不通 1 Locate NextPos(Locate curPos, int &i

8、); /切换查找路径方向 4、栈的初始化、入栈、出栈、判断为空的等函数Status InitStack(MazeStack &S)/新建一个栈 S.base = (MazeType *)malloc(MAXSIZE*sizeof(MazeType); if(!S.base) exit(OVERFLOW); S.top = S.base; S.stacksize =MAXSIZE; return OK; Status Push(MazeStack &S, MazeType &e)/入栈 if(S.top-S.base >= S.stacksize) /如果栈空间不够

9、，加大空间 S.base=(MazeType *)realloc(S.base,(S.stacksize+INCREASE)*sizeof(MazeType); if(!S.base) exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=INCREASE; *S.top+ = e; return OK; Status Pop(MazeStack &S, MazeType &e)/出栈 if(S.top = S.base) return ERROR; e = *-S.top; return OK; Status Stack

10、Empty(MazeStack &S)/判断是否为空 if(S.base = S.top) return OK; return ERROR; 5.迷宫中寻找通路函数。Status MazePath(Locate start,Locate end)/找迷宫的路径 Locate curpos; MazeStack S; MazeType e; int curstep; InitStack(S); curpos = start; /设定当前位置为入口位置 curstep = 1; /第一步 cout << "起点: "<< "("

11、; <<start.y << "," << start.x << ")" << endl; do if(Pass(curpos) /当前位置可以通过即是未曾走到的通道块 FootPrint(curpos); /留下足迹 e.ord = curstep; e.seat = curpos; e.di = 1; Push(S, e); if(curpos.x = end.x && curpos.y = end.y) cout << "n到达终点 (" &

12、lt;< e.seat.y << "," << e.seat.x << ")" return OK; curpos = NextPos(curpos, e.di); /下一位置是当前位置的东 +curstep; /探索下一步 else /当前位置不能通过 if(!StackEmpty(S) Pop(S, e); while(e.di = 4 && !StackEmpty(S) MakePrint(e.seat); /留下不能通过的标记 1 Pop(S, e); cout << &quo

13、t;倒退到(" << e.seat.y << "," << e.seat.x << ")" if(e.di = 4 && StackEmpty(S) return ERROR; if(e.di < 4) +e.di; /换下一个方向探索 Push(S, e); curpos=NextPos(e.seat,e.di); /设定当前位置是该新方向上的相邻块 while(!StackEmpty(S); return ERROR; Status Pass(Locate &pa

14、ss) if(mazeMappass.ypass.x = 1 | mazeMappass.ypass.x=2) return ERROR; cout << "->(" << pass.y << "," << pass.x << ")" return OK; void FootPrint(Locate pos) /走过的位置留下足迹 2 mazeMappos.ypos.x = 2; /将走过的路径设为 2 Locate NextPos(Locate curPos, int

15、 &i)/下一个位置 switch(i) /顺时针方向 case 1: +curPos.x; /东 if(mazeMapcurPos.ycurPos.x != 2) break; -curPos.x; case 2: i = 2; +curPos.y; /南 if(mazeMapcurPos.ycurPos.x != 2) break; -curPos.y; case 3: i = 3; -curPos.x; /西 if(mazeMapcurPos.ycurPos.x != 2) break; +curPos.x; case 4: i = 4; -curPos.y; /北 if(maz

16、eMapcurPos.ycurPos.x = 2) /最后一个 来时的方向 返回 +curPos.y; /mazeMapcurPos.ycurPos.x = 0; break; return curPos; void MakePrint(Locate pos) /后退,设置为1 不通 cout << "n(" << pos.y << "," << pos.x << ")走不通后退" mazeMappos.ypos.x = 1; /将走不通的块替换为墙壁 6.设置迷宫出入口、随

17、机生成迷宫、菜单函数等。void ResetMaze(Locate &start,Locate &end) cout<<"tttt " cout<<"输入要设置的入口坐标(y,x)"<<endl; cout<<"tttt " cin>>start.y; cout<<"tttt " cin>>start.x; cout<<"tttt " cout<<"输入要设置的出

18、口坐标(y,x)"<<endl; cout<<"tttt " cin>>end.y; cout<<"tttt " cin>>end.x; void Menu() char choice; lable: cout<<endl<<"ttttt"<<" 迷宫: "<<endl<<endl; cout<<"tttt" cout<<"请选择手动

19、生成迷宫还是自动生成:"<<endl; cout<<"tttt" cout<<" A.自动生成。"<<endl; cout<<"tttt" cout<<" B.手动生成。"<<endl; cout<<"tttt" cin>>choice; switch(choice) case 'A': case 'a':CreatMaze(mazeMap);br

20、eak; case 'B': case 'b':InputMaze(mazeMap);break; default: cout<<"tttt" cout<<" 输入错误！"<<endl; goto lable; void InputMaze(int mazeMap1010) for(int i=1;i<9;i+) cout<<endl<<endl<<endl<<"tttt" cout<<"请输

21、入第"<<i<<"行数据(0为通路1为不通)"<<endl; cout<<"tttt 每行8个数据"<<endl; for(int j=1;j<9;j+) cout<<"tttt" cin>>mazeMapij; for(int i=0;i<10;i+) mazeMap0i=1; mazeMap9i=1; mazeMapi0=1; mazeMapi9=1;cout<<"tttt"cout<&l

22、t;"迷宫已生成！"<<endl;Sleep(1000);void CreatMaze(int mazeMap1010) for(int i=0;i<10;i+) mazeMap0i=1; mazeMap9i=1; mazeMapi0=1; mazeMapi9=1;srand(unsigned)time(NULL);for(int i=1;i<9;i+) for(int j=1;j<9;j+) mazeMapij=0+rand()%2;cout<<"tttt"cout<<"迷宫已生成！&qu

23、ot;<<endl;Sleep(1000);void SetMaze(Locate &start,Locate &end)/设置迷宫出口和入口 char choice; system("cls"); srand(unsigned)time(NULL); lable: cout<<endl<<"ttttt"<<" 迷宫: "<<endl<<endl; cout<<"tttt" cout<<"请选择

24、使用已有出口入口坐标还是手动输入:"<<endl; cout<<"tttt" cout<<" A.自动生成。"<<endl; cout<<"tttt" cout<<" B.手动生成。"<<endl; cout<<"tttt" cin>>choice; switch(choice) case 'A': case 'a':start.x=1+rand(

25、)%8; start.y=1+rand()%8; end.x=1+rand()%8; end.y=1+rand()%8;break; case 'B': case 'b': start.x = 1;/开始与结束点 start.y = 1; end.x = 8; end.y = 8; break; default: cout<<"tttt" cout<<" 输入错误！"<<endl; goto lable; cout<<"tttt" cout<<

26、"迷宫的入口坐标为("<<start.y<<","<<start.x<<")"<<endl; cout<<"tttt" cout<<"迷宫的出口坐标为("<<end.y<<","<<end.x<<")"<<endl;void PrintMaze(int mazeMap1010) cout<<endl&l

27、t;<"tttttt"<<" 迷宫: "<<endl<<endl; cout<<"t*" cout<<"*"<<endl; for(int i = 0; i < 10; i+) cout<<"ttttt " for(int j = 0; j < 10; j+) cout<<mazeMapij<<" " cout << endl; cout&

28、lt;<"t*" cout<<"*"<<endl; cout << endl << endl; 7.主函数。int main() system("title 迷宫"); system("color 0A"); Locate start,end; char choice; Menu(); /CreatMaze(mazeMap); SetMaze(start,end); PrintMaze(mazeMap); lable: if(MazePath(start,end

29、) cout << "n走通迷宫" << endl; else cout << "n走不通迷宫" << endl; cout<<"tttt " cout<<"输入1重新设置出口入口坐标"<<endl; cout<<"tttt "cout<<"输入2重新生成迷宫"<<endl; cout<<"tttt "cout<<

30、"输入3结束程序"<<endl; reset: cout<<"tttt 请输入"<<endl;cout<<"tttt "cin>>choice;switch(choice) case '1': ResetMaze(start,end); goto lable;break; case '2': CreatMaze(mazeMap); goto lable;break; case '3': break; default: cout&

31、lt;<"输入错误请重新输入！"<<endl; goto reset; system("PAUSE"); return 0; 五 系统运行与演示1、 运行主界面如下图：2.选择自动生成迷宫：3.选择自动生成出入口：4.生成如下迷宫：5.当迷宫不通时修改出入口：7.修改出入口使迷宫走通：七、附录（代码） #include <iostream> #include<stdlib.h>#include<windows.h>#include<time.h>using namespace std; #

32、define OVERFLOW -1 /分配空间时未分配 返回值 #define MAXSIZE 100 /栈的最大空间 #define INCREASE 10 /栈慢时 再分配空间 #define ERROR 0#define OK 1#define Status int/typedef enum ERROR,OK Status ; typedef struct/迷宫中x行y列的位置 int x; int y; Locate; typedef struct/栈类型 int ord; /通道块在路径上的“序号” Locate seat; /通道块在迷宫中的“坐标位置” int di; /从此通

33、道块走向下一通道块的方向1:东 2:北 3:西 顺时针) MazeType; typedef struct MazeType *base;/栈底指针 MazeType *top; /栈顶指针 int stacksize; /栈储存数据大小 MazeStack; Status InitStack(MazeStack &S); /栈的初始化 Status Push(MazeStack &S, MazeType &e);/入栈 Status Pop(MazeStack &S, MazeType &e); /出栈 Status StackEmpty(MazeSt

34、ack &S); /判断栈是否为空 Status MazePath(Locate start,Locate end);/迷宫路径 求解 Status Pass(Locate &pos); /判断该位置能否通过 void Menu();/菜单函数，选择手动生成迷宫还是自动生成等 void CreatMaze(int mazeMap1010);/自动创建迷宫void InputMaze(int mazeMap1010);/手动生成迷宫 void SetMaze(Locate &start,Locate &end);/设置迷宫出口入口 void ResetMaze(L

35、ocate &start,Locate &end);/当迷宫不通时，重新设置入口出口坐标 void PrintMaze(int mazeMap1010);/输出迷宫 void FootPrint(Locate pos); /走过的路留下标记 2void MakePrint(Locate pos); /不通 设置为不通 1 Locate NextPos(Locate curPos, int &i); /切换查找路径方向 /迷宫地图1表示墙壁0表示通路,入口:mazeMap11,出口mazeMap88 int mazeMap1010 ;/= / /0,1,2,3,4,5,6

36、,7,8,9 / 1,1,1,1,1,1,1,1,1,1, /0 / 1,0,0,1,0,0,0,1,0,1, /1 / 1,1,0,1,0,0,0,1,0,1, /2 / 1,1,0,0,0,1,1,0,0,1, /3 / 1,1,0,0,1,0,0,0,0,1, /4 / 1,0,1,0,1,0,0,0,0,1, /5 / 1,0,1,0,0,0,1,0,0,1, /6 / 1,0,1,1,1,0,1,1,0,1, /7 / 1,1,0,0,0,1,0,0,0,1, /8 / 1,1,1,1,1,1,1,1,1,1 /9 /; int main() system("title 迷

37、宫"); system("color 0A"); Locate start,end; char choice; Menu(); /CreatMaze(mazeMap); SetMaze(start,end); PrintMaze(mazeMap); lable: if(MazePath(start,end) cout << "n走通迷宫" << endl; else cout << "n走不通迷宫" << endl; cout<<"tttt "

38、cout<<"输入1重新设置出口入口坐标"<<endl; cout<<"tttt "cout<<"输入2重新生成迷宫"<<endl; cout<<"tttt "cout<<"输入3结束程序"<<endl; reset: cout<<"tttt 请输入"<<endl;cout<<"tttt "cin>>choice;

39、switch(choice) case '1': ResetMaze(start,end); goto lable;break; case '2': CreatMaze(mazeMap); goto lable;break; case '3': break; default: cout<<"输入错误请重新输入！"<<endl; goto reset; system("PAUSE"); return 0; void ResetMaze(Locate &start,Locate

40、&end) cout<<"tttt " cout<<"输入要设置的入口坐标(y,x)"<<endl; cout<<"tttt " cin>>start.y; cout<<"tttt " cin>>start.x; cout<<"tttt " cout<<"输入要设置的出口坐标(y,x)"<<endl; cout<<"tttt &

41、quot; cin>>end.y; cout<<"tttt " cin>>end.x; void Menu() char choice; lable: cout<<endl<<"ttttt"<<" 迷宫: "<<endl<<endl; cout<<"tttt" cout<<"请选择手动生成迷宫还是自动生成:"<<endl; cout<<"ttt

42、t" cout<<" A.自动生成。"<<endl; cout<<"tttt" cout<<" B.手动生成。"<<endl; cout<<"tttt" cin>>choice; switch(choice) case 'A': case 'a':CreatMaze(mazeMap);break; case 'B': case 'b':InputMaze(ma

43、zeMap);break; default: cout<<"tttt" cout<<" 输入错误！"<<endl; goto lable; void InputMaze(int mazeMap1010) for(int i=1;i<9;i+) cout<<endl<<endl<<endl<<"tttt" cout<<"请输入第"<<i<<"行数据(0为通路1为不通)"&l

44、t;<endl; cout<<"tttt 每行8个数据"<<endl; for(int j=1;j<9;j+) cout<<"tttt" cin>>mazeMapij; for(int i=0;i<10;i+) mazeMap0i=1; mazeMap9i=1; mazeMapi0=1; mazeMapi9=1;cout<<"tttt"cout<<"迷宫已生成！"<<endl;Sleep(1000);void Cr

45、eatMaze(int mazeMap1010) for(int i=0;i<10;i+) mazeMap0i=1; mazeMap9i=1; mazeMapi0=1; mazeMapi9=1;srand(unsigned)time(NULL);for(int i=1;i<9;i+) for(int j=1;j<9;j+) mazeMapij=0+rand()%2;cout<<"tttt"cout<<"迷宫已生成！"<<endl;Sleep(1000);void SetMaze(Locate &

46、;start,Locate &end)/设置迷宫出口和入口 char choice; system("cls"); srand(unsigned)time(NULL); lable: cout<<endl<<"ttttt"<<" 迷宫: "<<endl<<endl; cout<<"tttt" cout<<"请选择使用已有出口入口坐标还是手动输入:"<<endl; cout<<&qu

47、ot;tttt" cout<<" A.自动生成。"<<endl; cout<<"tttt" cout<<" B.手动生成。"<<endl; cout<<"tttt" cin>>choice; switch(choice) case 'A': case 'a':start.x=1+rand()%8; start.y=1+rand()%8; end.x=1+rand()%8; end.y=1+r

48、and()%8;break; case 'B': case 'b': start.x = 1;/开始与结束点 start.y = 1; end.x = 8; end.y = 8; break; default: cout<<"tttt" cout<<" 输入错误！"<<endl; goto lable; cout<<"tttt" cout<<"迷宫的入口坐标为("<<start.y<<",&

49、quot;<<start.x<<")"<<endl; cout<<"tttt" cout<<"迷宫的出口坐标为("<<end.y<<","<<end.x<<")"<<endl;void PrintMaze(int mazeMap1010) cout<<endl<<"tttttt"<<" 迷宫: "<

50、;<endl<<endl; cout<<"t*" cout<<"*"<<endl; for(int i = 0; i < 10; i+) cout<<"ttttt " for(int j = 0; j < 10; j+) cout<<mazeMapij<<" " cout << endl; cout<<"t*" cout<<"*"<&

51、lt;endl; cout << endl << endl; Status InitStack(MazeStack &S)/新建一个栈 S.base = (MazeType *)malloc(MAXSIZE*sizeof(MazeType); if(!S.base) exit(OVERFLOW); S.top = S.base; S.stacksize =MAXSIZE; return OK; Status Push(MazeStack &S, MazeType &e)/入栈 if(S.top-S.base >= S.stacksize)

52、/如果栈空间不够，加大空间 S.base=(MazeType *)realloc(S.base,(S.stacksize+INCREASE)*sizeof(MazeType); if(!S.base) exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=INCREASE; *S.top+ = e; return OK; Status Pop(MazeStack &S, MazeType &e)/出栈 if(S.top = S.base) return ERROR; e = *-S.top; return OK; Stat

53、us StackEmpty(MazeStack &S)/判断是否为空 if(S.base = S.top) return OK; return ERROR; Status MazePath(Locate start,Locate end)/找迷宫的路径 Locate curpos; MazeStack S; MazeType e; int curstep; InitStack(S); curpos = start; /设定当前位置为入口位置 curstep = 1; /第一步 cout << "起点: "<< "(" &l

54、t;<start.y << "," << start.x << ")" << endl; do if(Pass(curpos) /当前位置可以通过即是未曾走到的通道块 FootPrint(curpos); /留下足迹 e.ord = curstep; e.seat = curpos; e.di = 1; Push(S, e); if(curpos.x = end.x && curpos.y = end.y) cout << "n到达终点 (" << e.seat.y <<