迷宫问题——数据结构课程设计迷宫问题完整版(含源代码)

《迷宫问题——数据结构课程设计迷宫问题完整版(含源代码)》由会员分享，可在线阅读，更多相关《迷宫问题——数据结构课程设计迷宫问题完整版(含源代码)（26页珍藏版）》请在装配图网上搜索。

1、Ki Ki Ki Ki Ki Ki Ki Ki彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、实践教学Kl Kl Kl Kl Kl Kl Kl Kl Kl Kl Kl Kl Kl Kl Kl Kl Kl Kl Kl彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、兰州理工大学计算机与通信学院2012 年春季学期算法与数据结构 课程设计专业班级 名 学号 指导教师 成绩题 目： 迷宫问题计算机科学与技术一班vl* k1* k1* k1* k1* k1* k1* k1*T *T* *T* *T *T *T *T* *T*目录摘要 3、八、.前言

2、 4正文 5一、采用C+语言定义相关的数据类型5二、各模块的伪码算法6三、函数的调用关系图10四、调试分析 11五、测试结果 121、开始界面 122、自动生成迷宫运行情况123、键盘输入迷宫运行情况14总结 16致谢 17参考文献 18附录 19源程序（带注释）19摘要本程序主要是对任意给定的迷宫，求出一条从入口到出口的通路，或得出没 有通路的结论。使我们基本掌握线性表及栈上基本运算的实现，进一步理解和熟 练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题， 培养我们的动手能力。1、生成迷宫：根据提示输入数据，然后生成一个 8 行8 列的迷宫。2、探索迷宫路径：由输入的入口

3、位置开始，对相邻的（上，下，左，右）四 个方向的方块进行探索，若可通则“纳入路径”，否则顺着“来向”退到“前一通 道块”，朝着“来向”之外的其它方向继续探索。3、保存迷宫路径：若探索到出口则把探索到的路径压入另一个栈中，并最后 弹出路径坐标，输出在屏幕上。关键字：栈，栈的存储结构，出栈与入栈前言求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机 解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探 索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至 所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需 要用一个后进先出的结

4、构来保存从入口到当前位置的路径。因此，在求迷宫通路 的算法中应用“栈”也就是自然而然的事。迷宫问题要求，所求路径必须是简单 路径，即在求得路径上不能同时重复出现同一通道。在迷宫中用 1 和 0 分别表示 迷宫中的通路和障碍。首先，输入迷宫数据，在计算机的屏幕上显示一个8 行8 列的矩阵表示迷宫。 矩阵中的每个数据或为通路（以 0 表示），或为墙（以 1 表示），所求路径必须是 简单路径，即在求得的路径上不能重复出现同一道块。其次，假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块 位置”，则求迷宫中一条路径的算法的基本思想是：若当前位置“可通”，则“纳 入当前路径”，并继续朝“下一个

5、位置”探索，即切换“下一位置”为“当前位置”， 如此重复直到到达出口；若当前位置“不可通”，则应顺着“来向”退回到“前一 通道块”，然后朝着除“来向”，之外的其它方向继续探索，若该通道块的四周四 个方块均“不可通”，则应该从“当前路径”上删除该通道块，所谓“下一个位置” 指的是“当前位置”四周四个方向（上，下，左，右）上相邻的方块。假设以栈s 记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳 入路径”的操作为“当前位置入栈”；从当前路径删除前一通道块的操作为“出栈”。最后，若找到出口，则从栈中弹出数据，在屏幕上显示从入口到出口的路径 坐标。最后希望通过对该课题的设计，

6、理解和掌握所学到的各种数据结构，学会 把学到的知识应用于解决实际的问题当中，培养自己的动手能力。正文、采用C+语言定义相关的数据类型1、定义坐标(X, Y):#include #include using namespace std; struct Coorint row;int column;int direction;2、定义方向： struct Moveint row;int column;3、定义/链表结点： struct LinkNodeCoor data; LinkNode *next;4、定义栈：class stackprivate: LinkNode *top;public:

7、stack();stack();void Push(Coor data);Coor Pop();Coor GetPop();void Clear();bool IsEmpty();5、定义迷宫定义移动的 4 个方向：Move move4=0,1,1,0,0,-1,-1,0;6、几个函数功能的描述:stack(); /构造函数，置空栈stack();/析构函数void Push(Coor data);/把元素 data 压入栈中Coor Pop();/使栈顶元素出栈Coor GetPop();/取出栈顶元素void Clear();/把栈清空bool IsEmpty(); /判断栈是否为空 bo

8、ol Mazepath(int *maze,int m,int n);寻找迷宫maze中从(0, 0)到(m,n)的路径到则返回true，否则返回falsevoid PrintPath(stack p);/输出迷宫的路径void PrintPath2(int m,int n,stack p,int *maze);/输出路径void Restore(int *maze,int m,int n);/恢复迷宫二、各模块的伪码算法1、根据输入产生一个 8*8 的迷宫：m=a;n=b;maze=new int *m+2; /申请长度等于行数加 2 的二级指针 for(i= 0;im+2;i+) /申请每

9、个二维指针的空间mazei=new intn+2;for(i=1;i=m;i+) for(j=1;jmazeij;coutvv是否保存新迷宫？ n;coutvv用Y或y表示保存、N或n表示不保存n; char choose;cinchoose;if(choose=Y|choose=y)char ch;ofstream fop(Newtest.txt);for(i=1;i=m;i+) for(j=1;j=n;j+) ch=0+mazeij; fopch;fopendl;flush(cout); fop.close();/给迷宫的四周加一堵墙，即把迷宫四周定义为1for(i=0;im+2;i+)

10、mazei0=mazein+1=1;for(i=0;in+2;i+) maze0i=mazem+1i=1;for(int p=0;pm+2;+p)for(int q=0;q=1)coutvv ”；coutendl；return maze；/返回存贮迷宫的二维指针 maze2、探索路径函数： bool Mazepath(int *maze,int m,int n)寻找迷宫maze中从(0, 0)至到 (m,n)的路径 到则返回true，否则返回falsestack q,p;Coor Temp1,Temp2； int row,column,loop； Temp1.row=1； Temp1.colu

11、mn=1； q.Push(Temp1)； p.Push(Temp1)； maze11=8； while(!q.IsEmpty()Temp2=q.GetPop()；定义栈p、q,分别存探索迷宫的存储和路径过程/将入口位置入栈/标志入口位置已至达过/栈 q 非空,则反复探索/获取栈顶元素if(!(p.GetPop().row=q.GetPop().row&p.GetPop().column=q.GetPop().column)p.Push(Temp2)；如果有新位置入栈，则把上一个探索的位置存入栈pfor(loop=0；loopchoose;if(choose=1)PrintPath(p);/坐标

12、显示输出Restore(maze,m,n);elsePrintPath2(m,n,p,maze);/矩阵显示输出Restore(maze,m,n);return 1;/表示成功找到路径 if(p.GetPop().row=q.GetPop().row&p.GetPop().column=q.GetPop().colu mn)/如果没有新位置入栈,则返回到上一个位置 p.Pop();q.Pop();/表示查找失败,即迷宫无路经return 0;3、输出迷宫void PrintPath(stack p)/输出路径coutvv迷宫的路径为n;coutvv括号内的内容分别表示为(行坐标,列坐标，数字化

13、方向，方向)n; stack t;/定义一个栈，按从入口到出口存取路径int a,b;Coor data;LinkNode *temp;temp=new LinkNode;/申请空间temp-data=p.Pop();/取栈 p 的顶点元素，即第一个位置t.Push(temp-data); /第一个位置入栈 t delete temp;/释放空间while(!p.IsEmpty() /栈 p 非空，则反复转移temp=new LinkNode;temp-data=p.Pop();/获取下一个位置/得到行走方向 a=t.GetPop().row-temp-data.row; /行坐标方向 b=t

14、.GetPop().column-temp-data.column; /列坐标方向 if(a=1) temp-data.direction=1;/方向向下，用 1 表示else if(b=1) temp-data.direction=2; /方向向右，用 2 表示 else if(a=-1) temp-data.direction=3; /方向向上，用 3 表示 else if(b=-1) temp-data.direction=4; /方向向左，用 4 表示 t.Push(temp-data);/把新位置入栈delete temp;coutvv坐标(row,column,direction)

15、中x在指向当前位置所在的行数，y 指向当前位置所在的列数， ;coutvvdirection 表示下一位置走向。vvendl;/输出路径，包括行坐标，列坐标，下一个位置方向 while(!t.IsEmpty()/栈非空，继续输出data=t.Pop(); coutvv(vvdata.rowvv,vvdata.columnvv,vvdata.directionvv,; / 输 出行坐标，列坐标switch(data.direction)/输出相应的方向case 1:coutvv I )n;break;case 2:coutvvf )n;break; case 3:cout t )n;break;

16、 case 4:coutvv j)n;break; case 0:coutvv)n;break;void PrintPath2(int m,int n,stack p,int *maze)输出路径coutvv迷宫的路径为n;for (int i = 0; i m+2; +i )for (int j = 0; j n+2; +j)cout mazeij;cout =0 &chlXcoutn ；后，吃图现象在没有发生，如图;a “口鈕匚I口 口 駁迥口2、算法的时间复杂度和空间复杂度 空间复杂度：O (1)；时间复杂度随机生成迷宫：O (n*n)； 探寻出口： O (n*n)； 输出迷宫：O (n

17、*n)； 判断当前位置可通：O (1)。五、测试结果1、开始界面10级计算机一班学号；10240127 F;migan gDebwgrTnigQng.exe请选择生咸(1)或键盘输入:2、自动生成迷宫运行情况(1) 选择生成迷宫输入1如下图所示+:+ +:*:+:*:+:+:+ +:+办 j 卬-停 用 j生吕 * 英拟 柱 序 *:*:* +:+山级计算机一班三程文參学号:10240127001111101011111001011111011110001101QQ1Q000110000i青谨择主成（J或谨盘输汎灼）：1 生成迷宫如下：口口口口 口 口口口1青走扌睪坐冲示Ff?我 (r ua=

18、| cijLurnn 5 ilirecti）输出迷宫迭1）或以方卩车形式输出迷宫迭辺（2）选择以坐标形式输出迷宫：输入1如下图所示-F:rn igo ngDebugnn igong.eKepi=i口口口口口口 口口口口口口口口口口口口清选择以坐标形式cclumn, airectioi.输岀谜宫迭1或以方B车球式输出谜宫迭 迷宫的路径为括号内的內吝分别表示为行坐标-列坐标埶李化方向方向）坐标eclumn, directly?中盟在扌旨向肖前位走所在的行数，诃旨向肖前位走所在的列数 di f e u t i on表7F下一检置走向。.1. .J .1. .1. .1. .1.1-! mll各 -

19、- s1 z 2 3 _J 3 3 n- 4 5 in 6 7 _y- - - - - - - - - - - LE 口1.1匹住口辺C5ec7crcrcr迷Press any key to coittinue（3）选择以方阵形式输出迷宫：输入2如下图所示（其中8代表路径，1代表墙） 001Cl11i1 0 10i1 1 0 1101 0 01 0001 1 000i青迭择坐标开纟式? n: Qli-UTllL?输出迷宫迭(们或以方醉疵式输出迷宫选圧)迷宫的路径为1 1 11 1 111111 0 81 1 1110111 SS S 811111 1 1s a eee111S 88 1 81i

20、111 1 88 8 810111 1 18 8 81i0111SS1Sss011 1 11 1 11i11迷宫路桓採索成功！Frezi ：=jLykey to crintinue3、键盘输入迷宫运行情况(1)选择键盘输入输入2如下图所示（2）键盘输入10*10的迷宫，运行结果及通路结果如下图所示F:inig or gDebiug_nnigcng-eKeB序冲冲冲車畫魯魯4（暮魯畫家字亭亭工1匹彳申用 迷宫*臣|_：耳呈 序車耳耳耳耳車卓序冲冲冲車畫 10级计算机一班 程文鑫 学号：10240127请选择生咸或键盘输A（2：2100011111110nn1100110001u100010011

21、u10111訂1p0111000uu00LI01111uu110000111u111UUIJIJIJ1u10U00111uu请输入迷宫的行数和列数：中间用空格谨分幵溝输入迷宫内容：Q表示通路1表示不连通。中间用空格健分幵是否（呆疗前进宫彳用Y或煤示4呆存、瞰皿表示不保存 请选择以坐标影式roW? column, directi ci.）输出迷宫迭（11或以方陌形式输出迷宫选住 :迷宫的路径为1 11 81 1迷宫路径探索咸功！P r t： e e ：=lTlv Icey tc c -jni i nue总结我的课设题目为迷宫问题，通过该题目的设计过程,我加深了对栈的逻辑结构, 存储结构及入栈出栈

22、过程的理解,对栈的基本运算的实现有所掌握,对课本中所学 的各种数据结构进一步理解和掌握,学会了如何把学到的知识用于解决实际问题, 锻炼了自己动手的能力。本次课程设计，使我对数据结构线性表的设计方法、步骤、思路，有一定的 了解和认识，它相当于实际设计工作的模拟。在课程设计过程中，基本能按照规 定的程序进行，先针对表达式算法为背景，建立系统模型：收集、调查有关资料， 共同与老师和同学进行几次讨论、修改、再讨论、再修改，最后确定方案。通过此次课程设计，我了解了编写应用软件的一般步骤，获得了很多宝贵的 经验，特别是怎么样通过理论与实践相结合，把书本上的内容应用到我们做的程 序上去。怎样使各个子模块实施

23、其的详细功能，特别是各个子模块之间的接口， 一定要相当清晰，达到相互协调的作用。其次，我熟悉了数据结构知识，学会了 很多关于程序设计的经验和技巧，明白了程序的使用性和通用性是程序生存周期 长短的关键。学会了调试程序的一般方法，知道了如何在困难重重中一步一步发 现问题，解决问题。一个人要完成所有的工作是非常困难和耗时的。在以后的学习中我会更加注 意各个方面的能力的协调发展。在课程设计时遇到了很多的问题，在老师的帮助， 和对各种资料的查阅中，将问题解决，培养了我自主动手，独立研究的能力，为 今后在学习工作中能更好的发展打下了坚实的基础。三周的课程设计很短暂，但其间的内容是很充实的，在其中我学习到了

24、很多 平时书本中无法学到的东西，积累了经验，锻炼了自己分析问题，解决问题的能 力，并学会了如何将所学的各课知识融会，组织，来配合学习，三周中我收益很 大，学到很多。致谢在此次课程设计的撰写过程中，我得到了许多人的帮助和支持。首先，我要感谢张永老师在课程设计上给予我的指导、提供给我的支持和帮 助，这是我能顺利完成这次报告的主要原因，更重要的是张老师的帮助使我解决 了许多技术上的难题，让我能把系统做得更加完善。在此期间，我不仅学到了许 多新的知识，而且也开阔了视野，提高了自己的设计能力和实践能力。其次，我 要感谢本班同学和帮助过我的同学，是他们的帮助和支持使我顺利的完成了本次 课程设计，他们也为我

25、解决了不少我不太明白的设计上的难题。同时也感谢学院 为我提供良好的做课程设计的环境。最后，再一次感谢所有在课程设计中曾经帮助过我的良师益友和同学。参考文献1 严蔚敏，吴伟民.数据结构（C语言版）清华大学出版社.2 严蔚敏，吴伟民.数据结构题集（C语言版）清华大学出版社.3 DATA STRUCTURE WITH C+.W订liam Ford,William Topp 清华大学出 版社（影印版）.4 谭浩强.c语言程序设计清华大学出版社.5 数据结构与算法分析（ Java 版） , A Practical Introduction to Data Structures and Algorithm

26、 Analysis Java Edition Clifford A. Shaffer , 张 铭,刘晓丹译 电子工业出版社 2001 年1月附录源程序（带注释）#include#include using namespace std;struct Coor/定义描当前位置的结构类型int row;int column;int direction;struct Move/定义下一个位置的方向int row;int column;struct LinkNode/链表结点Coor data; LinkNode *next;/定义栈 class stackprivate:/构造函数，置空栈/析构函数把

27、元素data压入栈中/使栈顶元素出栈 /取出栈顶元素/把栈清空/判断栈是否为空/构造函数，置空栈LinkNode *top; public:stack();stack();void Push(Coor data);Coor Pop(); Coor GetPop(); void Clear();bool IsEmpty(); stack:stack()top=NULL;stack:stack()/析构函数void stack:Push(Coor x)把元素data压入栈中Coor stack:GetPop()LinkNode *TempNode; TempNode=new LinkNode; T

28、empNode-data=x; TempNode-next=top; top=TempNode;Coor stack:Pop()Coor Temp;LinkNode *TempNode;TempNode=top; top=top-next;Temp=TempNode-data; delete TempNode; return Temp;return top-data;void stack:Clear()top=NULL;bool stack:IsEmpty()if(top=NULL)return true;elsereturn false;Move move4=0,1,1,0,0,-1,-1,

29、0;/定义移动的 4个方向bool Mazepath(int *maze,int m,int n);寻找迷宫maze中从(0, 0)到(m,n)的路径到则返回true，否则返回falsevoid PrintPath(stack p);/输出迷宫的路径void PrintPath2(int m,int n,stack p,int *maze); void Restore(int *maze,int m,int n);/恢复int* GetMaze(int &m,int &n);/获取迷宫(可从文件中读取，也可输入)/返回存取迷宫的二维指针int main()system(color f5);co

30、ut vv ttcout vv ttcout vv ttint *maze;/定义二维指针存取迷宫* endl;cout int m=0,n=0;10 级计算机一班 endl; 程文鑫 endl;学号：10240127 Choose;if(Choose=T)当标志Choose为T时，读取文件coutvv生成迷宫如下:n;char ch;/定义一个字符，读取文件中的内容i=0,j=0;/首先得到文件中数字字符的数目，并得到迷宫的长和宽ifstream fip(test.txt);定义一个文件对象，并打开文件“test.txt”while(fip.get(ch)/从读取文件中内容(一个个字符)if

31、(ch=0&chv=9) /获取文件中的数字字符j+;/如果是字符，列就加 1if(ch=n)i+;/如果是换行，就行加 1n=j;/得到宽，即列数j=0;fip.close();/读取文件结束m=i;/得到长即行数maze=new int *m+2; /申请长度等于行数加 2 的二级指针 for(i= 0;i=0&ch=9)mazeij=ch-0;/把数字字符转化为数字，并存到指针里coutmazeij; /在屏幕中显示迷宫j+;if(ch=n)/遇到换行，指针也相应换行coutendl;i+;j=1;fip2.close(); /读取结束coutab;coutvv请输入迷宫内容:(0表示通

32、路,1表示不连通。中间用空格键分开)n; m=a;n=b;maze=new int *m+2; /申请长度等于行数加2的二级指针for(i= 0;im+2;i+) /申请每个二维指针的空间mazei=new intn+2;for(i=1;i=m;i+)for(j=1;jmazeij;coutvv是否保存新迷宫？ n; coutvv用Y或y表示保存、N或n表示不保存n; char choose;cinchoose;if(choose=Y|choose=y)char ch;ofstream fop(Newtest.txt); for(i=1;i=m;i+) for(j=1;j=n;j+) ch=0

33、+mazeij;fopch;fopendl; flush(cout);fop.close(); /给迷宫的四周加一堵墙，即把迷宫四周定义为1 for(i=0;im+2;i+)mazei0=mazein+1=1; for(i=0;in+2;i+)maze0i=mazem+1i=1;for(int p=0;pm+2;+p)for(int q=0;q=1)coutvv口coutendl;bool Mazepath（int *maze,int m,int n）寻找迷宫maze中从（0, 0）到（m,n）的路径到则返回true，否则返回falsestack q,p;定义栈p、q,分别存探索迷宫的存储和路

34、径过程Coor Temp1,Temp2; int row,column,loop;Temp1.row=1;Temp1.column=1;q.Push(Temp1);p.Push(Temp1);maze11=8; while(!q.IsEmpty()Temp2=q.GetPop();/将入口位置入栈/标志入口位置已到达过/栈 q 非空,则反复探索/获取栈顶元素if(!(p.GetPop().row=q.GetPop().row&p.GetPop().column=q.GetPop().column)p.Push(Temp2);如果有新位置入栈，则把上一个探索的位置存入栈p for(loop=0;

35、loopchoose;if(choose=1)PrintPath(p);/坐标显示输出Restore(maze,m,n); else PrintPath2(m,n,p,maze);/矩阵显示输出Restore(maze,m,n);return 1;/表示成功找到路径 if(p.GetPop().row=q.GetPop().row&p.GetPop().column=q.GetPop().column) /如果没有新位置入栈，则返回到上一个位置p.Pop();q.Pop();return 0;/表示查找失败，即迷宫无路经void PrintPath(stack p)/输出路径coutvv迷宫的

36、路径为n;coutvv括号内的内容分别表示为(行坐标,列坐标，数字化方向，方向)n; stack t;/定义一个栈，按从入口到出口存取路径int a,b;Coor data; LinkNode *temp; temp=new LinkNode;/申请空间temp-data=p.Pop();/取栈 p 的顶点元素，即第一个位置t.Push(temp-data); /第一个位置入栈 t delete temp;/释放空间while(!p.IsEmpty()/栈 p 非空，则反复转移 temp=new LinkNode; temp-data=p.Pop();/获取下一个位置/得到行走方向 a=t.G

37、etPop().row-temp-data.row; /行坐标方向 b=t.GetPop().column-temp-data.column;/列坐标方向if(a=1) temp-data.direction=1;/方向向下，用1 表示else if(b=1) temp-data.direction=2; /方向向右，用 2 表示 else if(a=-1) temp-data.direction=3; /方向向上，用3 表示 else if(b=-1) temp-data.direction=4; /方向向左，用 4 表示 t.Push(temp-data);/把新位置入栈delete te

38、mp;coutvv坐标(row,column,direction)中x在指向当前位置所在的行数，y指向当前位置所 在的列数， ;coutvvdirection 表示下一位置走向。vvendl;/输出路径，包括行坐标，列坐标，下一个位置方向while(!t.IsEmpty()/栈非空，继续输出data=t.Pop();coutvv(vvdata.rowvv,vvdata.columnvv,vvdata.directionvv,; /输出行坐标，列坐 标switch(data.direction)/输出相应的方向case l:coutJ)n;break;case 2:coutf)n;break;c

39、ase 3:coutf)n;break;case 4:coutvv)n;break;case 0:coutvv)n;break;void PrintPath2(int m,int n,stack p,int *maze)/输出路径coutvv迷宫的路径为5;for (int i = 0; i v m+2; +i )for (int j = 0; j v n+2; +j)cout vv mazeijvv cout vv endl;/恢复迷宫/遍历指针/恢复探索过位置，即把-1恢复为0void Restore(int *maze,int m,int n)int i,j;for(i=0;ivm+2;i+) for(j=0;jvn+2;j+)if(mazeij=8)mazeij=0;