迷宫问题课程设计报告书

1、第一部分引言第二部分课程设计报告第一节课程设计目的第二节课程设计容和要求2. 1问题描述2. 2设计要求第三节课程设计总体方案及分析3. 1问题分析3.2概要设计3. 3详细设计3. 4测试结果3. 5参考文献第三部分课程设计总结附录（源代码）第一部分引言数据结构是一门理论性强、思维抽象、难度较大的课程，是基础课和专业课之间的桥梁。 该课程的先行课程是计算机基础、程序设计语言、离散数学等，后续课程有操作系统、编译 原理、数据库原理、软件工程等。通过本门课程的学习，我们应该能透彻地理解各种数据对 象的特点，学会数据的组织方法和实现方法，并进一步培养良好的程序设计能力和解决实际 问题的能力，而且该

2、课程的研究方法对我们学生在校和离校后的学习和工作，也有着重要的 意义。数据结构是软件工程专业的一门核心专业基础课程，在该专业的课程体系中起着承上启 下的作用，学好数据结构对于提高理论认知水平和实践能力有着极为重要的作用。学习数据 结构的最终目的是为了获得求解问题的能力。对于现实世界中的问题，应该能从中抽象出一 个适当的数学模型，该数学模型在计算机部用相应的数据结构來表示，然后设计一个解此数 学模型的算法，再进行编程调试，最后获得问题的解答。基于此原因，暑期我们开设了数据结构课程设计。针对数据结构课程的特点，着眼于培 养我们的实践能力。实习课程是为了加强编程能力的培养，鼓励学生使用新兴的编程语言

3、。 相信通过数据结构课程实践，无论是理论知识，还是实践动手能力，同学们都会有不同程度 上的提高。第二部分课程设计报告第一节课程设计目的仅仅认识到栈和队列是一种特殊的线性表是远远不够的，本次实习的目的在于使学生深 入了解栈和队列的特征，以便在实际问题背景下灵活运用它，同时还将巩固这种数据结构的 构造方法。第二节课程设计容和要求2. 1问题描述：迷宫问题是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的 门放入，在盒子中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口 处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验, 一直到老鼠从

4、入口走到出口，而不走错一步。老鼠经过多次试验最终学会走通迷宫的路线。 设计一个计算机程序对任意设定的矩形迷宫，求出一条从入口到出口的通路，或得出没有通路 的结果。2. 2设计要求：要求设计程序输出如下：（1）建立一个大小为mXm的任意迷宫（迷宫数据可由用户输入或由程序自动生成）， 并在屏幕上显示出来；（2）在屏幕上输出迷宫和通路；第三节 课程设计总体方案及分析3.1问题分析:1. 迷宫的建立:迷宫中存在通路和障碍，为了方便迷宫的创建，可用o表示通路，用1表示障碍,#表示墙壁，这样迷宫就可以用0、1矩阵來描述，2. 迷宫的存储：迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位置都

5、可 以用其行列号來唯一指定，但是二维数组不能动态定义其大小，我们可以考虑先定义 一个较大的二维数组mazeM+2 M+2,然后用它的前m行m列來存放元素，即可得到 一个mXm的二维数组，这样(0,0)表示迷宫入口位置，表示迷宫出口位置。注：其中M, M分别表示迷宫最大行、列数，本程序M的最大值为9,当然用户也 可根据需要，调整其大小。3. 迷宫路径的搜索：首先从迷宫的入口开始，如果该位置就是迷宫出口，则己经找到了一条路径，搜 索工作结束。否则搜索其上、下、左、右位置是否是障碍，若不是障碍，就移动到该 位置，然后再从该位置开始搜索通往出口的路径；若是障碍就选择另一个相邻的位置, 并从它开始搜索路

6、径。为防止搜索重复出现，则将己搜索过的位置用函数进行判断和 标记，同时保留搜索痕迹，在考虑进入下一个位置搜索之前，将当前位置保存在一个 队列中，如果所有相邻的非障碍位置均被搜索过，且未找到通往出口的路径，则表明 不存在从入口到出口的路径。这实现的是广度优先遍历的算法，如果找到路径，则最11搜索算法流程图如下所港声路由算法流程图：将（0,0）入队列測断首节点县否为诵路Y夬断队列否为空将队头出队存储节点，将节点入队列有解迷宫是否/左边/下边/右边/上边到达/是否/是否/是否/是否迷宫）存在）（存在）（存在）存在ih 口 /通路/通路/通路/通路处/ / / /循环结束 无無迷宫3. 2概要设计1.

7、构建一个二维数组mazeM+2 M+2用于存储迷宫矩阵 自动或手动生成迷宫，即为二维数组mazeM+2 M+2赋值 构建一个队列用于存储迷宫路径 建立迷宫节点，用于存储迷宫中每个节点的访问情况 实现搜索算法 屏幕上显示操作菜单2. 本程序包含12个函数：(1) 主函数main()(2) Status InitStack (SqStack &S) ; /创建一个空栈 S(3) Status Push(SqStack &S, SElemType &a) ; /插入新元素 a(4) Status Pop (SqStack &S, SElemType &a) ;/删除栈顶元素，a 返回其值(5) St

8、atus StackEmpty (SqStack S) ;/检查是否空栈(6) Status MazePath (int maze 12J 12, SqStack &S, PosType start, PosType end);/找通路(7) void Initmaze (int maze 12 12, int size) ;/初始化迷宫(8) void printmaze (int maze 12 12, int size);显不迷宫(9) Status Pass (int maze 12 12, PosType CurPos) :/判断当前位置是否可通(10) void Markfoot

9、(int maze 12 12, PosType CurPos) ;/标记当前位置不可通仃l)PosType NextPos (PosType CurPos, int Dir) ;/进入下一位置(12)void printpath(int maze12 12, SqStack S, int size) ;/显示通路3. 3详细设计程序设计的基本思想，原理和算法描述：此算法最人的优点是支持图形化输入与输出，观察效果好迷宫求解问题主要运用了堆栈的性质求迷宫中一条从入11到出11的路径的算法描述：do若当前位置可通则将当前位置插入栈顶；若该位置时出II位置，则结束：否则切换当前位置为东邻方块为新的当

10、前位置;否则若栈不空且栈顶位置尚有其他方向未经探索，则设定新的当前位置为沿顺时针方向旋转的栈顶位置的下一相邻模块若栈不空但栈顶位置的四周均不可通则删去栈顶位置；若栈不空，则重新测试新的栈顶位置直至找到一个可通的相邻模块或出栈至栈空；while（栈不空）实现的函数为J*若迷宫maze中从入I丨stait到出丨I end的通道，则求得一条存放在栈中*/Status MazePath(int inaze1212,SqStack &S. PosType start, PosTvpe end)PosTvpe curpos;int curstep;SElemType e;IiiitStack(S);cui

11、pos = start; /设定当前位置为入I I位置cuistep = 1;/ 探索第一步doif(Pass(inaze,curpos) /当前位置可通过，即是未曾走到过的通道块 Maikfoot(maze,cuipos);/ 留下足迹e.di =1;e.oid = cuistep;e.seat= curpos;Push(S,e);/加入路径if (cuipos.row=end.row & cuiposine=end.lme)return OK;/到达终点(出I)curpos = NextPos(curpos, 1); 下一位置是当前位置的东邻 cuistep卄；/探索下一步else/当前位

12、置不能通过if (!StackEmpty(S)Pop(S,e);while (e.di=4 & ?StackEmpty(S)Maikfoot(maze,e.seat); /留卜不能通过的标记，并退回一步Pop(S,e);if (e.diseat.rowp-seat.lme=2; 标记为路径中的点P卄；然后显示通路时只要等于2的地方就打印一个0,否则打印空格。if(iiiazeij=2) pmitfC%celsepnntf(n H);4. 进入下一位置PosType NextPos(PosType CurPos, int Du); 进入卜一位置时按顺时针方向向卞一位置探索5. 堆栈操作，包拾创建

13、，入栈，出栈，判空。Status InitStack(SqStack &S);/创建一个空栈 SStatus Push(SqStack &S.SElemTvpe &a); /插入新元素 aStatus Pop(SqStack &S.SElemTvpe &a); 删除栈顶元素，a 返回其值Status StackEmpty(SqStack S);/检查是否空栈3. 3测试结果Bu订dLogConfiguration:迷宫求解 - Win32DebugCommand LinesResults迷宫求解 exe - 0 error (s), 0 warning (s)错误输入頁 乜：迷宫求宫求解.ex

14、e*|创建一个正方形迷宫，请输入迷宫尺寸注訝要大于50: 选择创建方式A ：自动生成B：手动创建1输入错误？显示所建的迷宫表示外面的墙:it # # -858993460 itit it it输入入口行坐标和列坐标：正确路径21 ： X3输入出口行坐标和列坐标:42c C:DocuMeirts and SettingsAdinistratorDebug迷宫问题 exe 显示所產爲址宫如表示拆 錨培tt#tt101100100#tt010000111#tt000100111#tt100110001#tt110111101#tt010011001#tt011010011#tt011010011#t

15、t110111101#tt#tt#tt输入入口行坐标和列坐标:2通路路径为：tt tt tt tt tt tt #tttttttttttttttt创建一个正方形迷宫，请输入迷宫尺寸注意不要大于10:3. 5参考文献1. 谭浩强C程序设计北京：清华大学，2006.2. 严蔚敏 M.北京：清华大学3. 王华，叶爱亮等.Visual C卄6.0编程实例与技巧M.北京：机械工业4. 钱新贤，程兆炜等.Visual C卄编程疑难详解 M.北京：人民邮电，2000.第三部分课程设计总结通过这段时间的课程设计，本人对软件专业的应用，数据结构的作用以及C语言的使用 都有了更深的了解。尤其是C语言的进步让我深刻

16、的感受到任何所学的知识都需要实践，没 有实践就无法真正理解这些知识以及掌握它们，使其成为自己的财富。在理论学习和上机实 践的各个环节中，通过自主学习和请教老师，我收获了不少。当然也遇到不少的问题，也正 是因为这些问题引发的思考给我带了收获。从当初不喜欢上机写程序到现在能主动写程序， 从当初拿着程序不只如何下手到现在知道如何分析问题，如何用专业知识解决实际问题的转 变，我发现无论是专业知识还是动手能力，自己都有很大程度的提高。在这段时间里，我对 forwhile等的循环函数用法更加熟悉，逐渐形成了较好的编程习惯。在老师的指导帮助下， 同学们课余时间的讨论中，这些问题都一一得到了解决。在程序的调试

17、能力上，无形中得到 了许多的提高。例如：头文件的使用，变量和数组的围问题，定义变量时出现的问题等等。在实际的上机操作过程中，不仅是让我们了解数据结构的理论知识，更重要的是培养解 决实际问题的能力，所以相信通过此次实习可以提高我们分析设计能力和编程能力，为后续 课程的学习及实践打下良好的基础。在这次短短的课程实践里，我们得到了邓彬老师的关心和帮助。她给了我们很多的信息, 与我们一起探讨问题，询问我们遇到了哪些问题并耐心给予指导。当我们遇到技术上难以解 决的问题时，她就会指导我们解决问题，她把自己多年來积累的经验教给我们，使我们顺利 地完成了课程实践任务。时间过得真快，大学生活不知不觉就走过了一年

18、，一年的大学学习 和课程实践阶段的提高，使我们本身知识得到提高的同时，也增强了我们对未来工作的信心, 我们相信自己未來三年的学习更使我们有能力胜任将來的工作。附录：（原程序代码）#include#include 卜卜丄丄xtx 卜 丄数据定义卜 丄丄丄丄丄丄丄丄丄丄丄丄丄丄丄丄丄xtx 丄“ 卜 丄丄ftypedef enum ERROR, OK Status: typedef structint row; /row 表示行号int line; /line 表示列”号PosType; /位置的元素类型typedef structintord;/该通道在路径上的“序号”PosType seat;

19、/通道块在迷宫中的坐标位置”intdi;/从此通道走向下以通道块的“方向”SElemType;/栈的元素类型typedef structSElemType * base;SElemType * top;intstacksize;SqStack;卜 卜 卜 卜 卜 卜 丄卜 丄丄丄卜 丄丄丄丄卜 丄卜 丄丄卜f函数原型说明丄卜 丄”丄”丄”丄”丄丄卜 ”丄卜 ” 卜 卜Status InitStack(SqStack &S);Status Push(SqStack &S, SElemType &a):Status Pop (SqStack &S, SElemType &a);Status Sta

20、ckEmpty(SqStack S);Status MazePath(int maze12L12, SqStack &S,找通路void Initmaze(int maze1212, int size):void printmaze(int mazeL1212,int size);Status Pass (int maze L1212, PosType CurPos); void Markfoot(int maze12L12, PosType CurPos);PosType NextPos(PosType CurPos, int Dir);/创建一个空栈S插入新元素a/删除栈顶元素，a返回其值

21、/检查是否空栈PosType start, PosType end); /初始化迷宫/显示迷宫/判断当前位置是否可通/标记当前位置不可通/进入下一位置void printpath(int maze L12 12, SqStack S, int size) : /显水通路卜 卜 卜 卜 %f卜 %f卜 丄卜 卜 %f卜%f 卜丄卜 丄丄%A# 卜 ” X# 卜 %A# 卜 %A# 卜%A#f主函数 卜 vA vA vL %! 卜 %f卜 %f卜 %f卜 %f卜 %f卜 %f%f A# %! %A# %! %f 卜%f 卜%f %t”丄卜 丄xf %f%A# %!%A# 丄“ %tfvoid ma

22、in (void)SqStackS;intsize;/正方形迷宫尺寸33intmaze 12 12 ;/存储迷宫路径可通情况for (int n二0;n10)printf(“ 输/设置迷宫大小scanf(%d, &size);if (size 卜 丄卜 *丄”*丄”*丄”丄丄卜 丄 卜 丄若迷宫maze中从入口 start到出口 end的通道，则求得一条存放在栈中丄“ 卜 丄卜 丄丄”丄”丄”丄”丄丄 丄”丄”丄卜 丄”*丄”%Xx 丄丄卜 丄丄*丄丄*丄丄丄卜 丄卜 %A# “ 卜fStatus MazePath(int maze1212, SqStack &S, PosType start

23、, PosType end)PosType curpos:int curstep;SElemType e;InitStack (S);curpos = start;设定当前位置为入口位置curstep = 1;/ 探索第一步doif (Pass (maze, curpos) /当前位置可通过，即是未曾走到过的通道块Markfoot (maze, curpos) ;/ 留下足迹e. di =1;e.ord = curstep;e. seat二 curpos:Push(S, e) ;/加入路径if (curpos. row=end. row & curpos. line=end. line)ret

24、urn OK;/到达终点(出口)curpos = NextPos (curpos, 1) ;/下一位置是当前位置的东curstep+;/ 探索下一步else/当前位置不能通过if (!StackEmpty (S)(Pop(S, e);while (e. di二二4 & !StackEmpty(S)Markfoot (maze, e. seat) ; / 留下不能通过的 标记，并退回一步Pop(S, e);/换下一个方向探索if (e. diA# 卜 丄丄void Initmaze(int maze12L12, int size)char select;printf(z，选择创建方式A:自动生成

25、B:手动创建n);label: scanf W &select);if (select二二a | | select二A)/自动生成for(int i二0;isize+2;i+)maze0i二1;for( i二1;isize+l;i+)mazei0二1;for(int j二1;jsize+l;j+)mazei j=rand()%2;mazei size+1二1;for (i=0; iXsize+2; i+)maze size+1 i二1;else if （select二二b | select二二B） 手动设置printf （按行输入%d*%d数据,0代表可通，1代表不可通（每行以Enter结 束

26、）:n size, size）;for(int i二0;isize+2;i+)maze0 i=l; for ( i=l;isize+l:i+)mazei0二1;for(int j=l;jsize+l;j+)scanf&mazeij);mazeisize+1二1;for(i=0;isize+2;i+)maze size+1 i二1;else 辻(select=，n ) goto label;排除 Enter 键的影响else printf (”输入错误!);显示迷宫void printmaze(int maze1212, int size)printf Cnn):printf(z/显示所建的迷宫

27、(#表示外面的墙)：n)；for (int i=0; isize+2; i +)printf (z，%c;printf (n);for (i=l;isize+l;i+)printf (%c , ;for (int j二1;jsize+l;j+)printf(“%d , mazeij);printf (%c, ;printf Cn/Z)；for (i=0;i 卜 卜 卜 丄丄丄丄丄丄丄卜 卜 卜%! 卜 卜 卜丄卜卜 卜 卜void printpath(int maze12.12, SqStack S, int size)printf （，znn 通路路径为:n）;SElemType * p=S

28、.base; while(p!二S top)mazep-seat rowp-seatline二2;标记为路径中的占八八p+;for (int i=0; isize+2; i +)printf (%c ”，#);printf (n);for (i二1;isize+l;i+)printf (，%c ”，;for (int j=l;j ;printf Cn，z);for(i=0:i 卜 %! 卜 %! 卜 卜 卜 卜 卜 卜 卜 卜 %! 卜 %fx 卜 . 卜 %!x 卜 %fx 卜 %! 卜 丄 丄丄%fx 卜 丄卜Status Pass (int maze1212, PosType CurPo

29、s)if (mazeCurPos rowCurPosline二二0)return OK;/如果当前位置是可以通过，返回1else return ERROR;/其它情况返回0:卜 卜 卜 卜 卜 卜 卜 丄%Lx %fx 卜 卜 %!x 卜 丄%tx 卜 丄卜 丄” A# %tx 丄卜 %fx 卜 %Az 丄卜 卜标记当前位置不可通vL 丄卜 %!x 卜 卜 卜 卜 卜 丄卜丄卜 ”丄%L#丄丄%fx 卜 丄%Lx 丄丄”丄” A# %tx 丄卜 %fx 卜void Markfoot(int maze12L12, PosType CurPos)mazeCurPos rowCurPosline二1;进入下一位置PosType NextPos (PosType CurPos, int Dir)PosType ReturnPos;switch (Dir)case 1:/下一模块为东临模块ReturnPos row二CurPos row;ReturnPos line二CurPos line+1;break;case 2:/下一模块为南临模块ReturnPos row=CurPos row+1;ReturnPos line二CurPos line;break;case 3:/下一模块为西临模块ReturnPos