迷宫问题课程设计

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

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

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

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

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

6、再从该位置开始搜索通往出口的路径；若是障碍就选择另一个相邻的位置，并从它开始搜索路径。为防止搜索重复出现，则将已搜索过的位置用函数进行判断和标记，同时保留搜索痕迹，在考虑进入下一个位置搜索之前，将当前位置保存在一个队列中，如果所有相邻的非障碍位置均被搜索过，且未找到通往出口的路径，则表明不存在从入口到出口的路径。这实现的是广度优先遍历的算法，如果找到路径，则最短路径。搜索算法流程图如下所示：3.2 概要设计1. 构建一个二维数组mazeM+2M+2用于存储迷宫矩阵自动或手动生成迷宫，即为二维数组mazeM+2M+2赋值构建一个队列用于存储迷宫路径建立迷宫节点,用于存储迷宫中每个节点的访问情况实

7、现搜索算法屏幕上显示操作菜单 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)Status StackEmpty(SqStack S);/检查是否空栈(6)Status MazePath(int maze1212,SqStack &S, PosType

8、start, PosType end); /找通路(7)void Initmaze(int maze1212,int size); /初始化迷宫(8)void printmaze(int maze1212,int size); /显示迷宫(9)Status Pass(int maze1212,PosType CurPos); /判断当前位置是否可通(10)void Markfoot(int maze1212, PosType CurPos); /标记当前位置不可通(11)PosType NextPos(PosType CurPos, int Dir); /进入下一位置(12)void prin

9、tpath(int maze1212,SqStack S,int size); /显示通路3.3 详细设计程序设计的基本思想，原理和算法描述：此算法最大的优点是支持图形化输入与输出，观察效果好迷宫求解问题主要运用了堆栈的性质求迷宫中一条从入口到出口的路径的算法描述：do若当前位置可通则 将当前位置插入栈顶; 若该位置时出口位置，则结束 ； 否则切换当前位置为东邻方块为新的当前位置; 否则 若栈不空且栈顶位置尚有其他方向未经探索， 则设定新的当前位置为沿顺时针方向旋转的栈顶位置的下一相邻模块 若栈不空但栈顶位置的四周均不可通 则 删去栈顶位置; 若栈不空，则重新测试新的栈顶位置 直至找到一个可通

10、的相邻模块或出栈至栈空 ； while(栈不空) 实现的函数为/* 若迷宫maze中从入口 start到出口 end的通道，则求得一条存放在栈中 */Status MazePath(int maze1212,SqStack &S, PosType start, PosType end) PosType curpos; int curstep; SElemType e; InitStack(S); curpos = start; / 设定"当前位置"为"入口位置 curstep = 1; / 探索第一步 do if (Pass(maze,curpos) /

11、当前位置可通过，即是未曾走到过的通道块 Markfoot(maze,curpos); / 留下足迹 e.di =1; e.ord = curstep; e.seat= curpos; Push(S,e); / 加入路径 if (curpos.row=end.row && curpos.line=end.line) return OK; / 到达终点（出口） curpos = NextPos(curpos, 1); / 下一位置是当前位置的东邻 curstep+; / 探索下一步 else / 当前位置不能通过 if (!StackEmpty(S) Pop(S,e); while

12、 (e.di=4 && !StackEmpty(S) Markfoot(maze,e.seat); / 留下不能通过的标记，并退回一步 Pop(S,e); if (e.di<4) e.di+; / 换下一个方向探索 Push(S, e); curpos = NextPos(e.seat, e.di); /当前位置设为新方向的 /相邻块 while (!StackEmpty(S); return ERROR; 围绕这个函数需要定义一些相关的函数操作，由以下函数实现/* 函数原型说明*/Status InitStack(SqStack &S); /创建一个空栈SSta

13、tus Push(SqStack &S,SElemType &a); /插入新元素aStatus Pop(SqStack &S,SElemType &a); /删除栈顶元素，a返回其值Status StackEmpty(SqStack S); /检查是否空栈Status MazePath(int maze1212,SqStack &S, PosType start, PosType end); /找通路void Initmaze(int maze1212,int size); /初始化迷宫void printmaze(int maze1212,int s

14、ize); /显示迷宫Status Pass(int maze1212,PosType CurPos); /判断当前位置是否可通void Markfoot(int maze1212, PosType CurPos); /标记当前位置不可通PosType NextPos(PosType CurPos, int Dir); /进入下一位置void printpath(int maze1212,SqStack S,int size); /显示通路 算法中我用正方形迷宫，即行数等于列数。迷宫的存储我用了一个整形二维数组表示, int size; /正方形迷宫尺寸 int maze1212; /存储迷宫

15、内路径可通情况 二维数组存储的数字表示对应迷宫位置处可通与否，0表示可通，1表示不可通。尺寸大小size可以设置，但是不能超过10，因为二维数组第一行，最后一行，第一列，最后一列一定要是不可通的，这是算法中用到的一个技巧。 迷宫内通道块位置变量类型定义为PosType typedef struct int row; /row表示“行”号 int line; /line表示“列”号 PosType; /位置的元素类型 这样判断其可通与否的语句为 if (mazeCurPos.rowCurPos.line=0)1.迷宫的初始化 void Initmaze(int maze1212,int size

16、); /初始化迷宫迷宫的初始化有两种方法，一是随即生成，一是手动设置，由用户选择。随即生成的方法是程序生成随机数，除以2取余 mazeij=rand()%2;手动设置是用户输入0,1由程序读取 scanf("%d",&mazeij); 见部分程序2.显示迷宫 void printmaze(int maze1212,int size); /显示迷宫 只需要整齐打印出 0，1即可，可以看到很好的效果显示初始化的迷宫程序见第三部分。 3.显示通路 void printpath(int maze1212,SqStack S,int size); /显示通路 用到了一个技巧，

17、只要是纳入堆栈的位置元素即为通路上的路径，将其迷宫对应位置 值变为2， while(p!=S.top) mazep->seat.rowp->seat.line=2; /标记为路径中的点 p+; 然后显示通路时只要等于2 的地方就打印一个0，否则打印空格。 if(mazeij=2) printf("%c ",'0'); else printf(" "); 4.进入下一位置 PosType NextPos(PosType CurPos, int Dir); /进入下一位置时按顺时针方向 /向下一位置探索5.堆栈操作，包括创建，入栈

18、，出栈，判空。 Status InitStack(SqStack &S); /创建一个空栈S Status Push(SqStack &S,SElemType &a); /插入新元素a Status Pop(SqStack &S,SElemType &a); /删除栈顶元素，a返回其值 Status StackEmpty(SqStack S); /检查是否空栈3.3 测试结果BuildLog-Configuration: 迷宫求解 - Win32 Debug-Command LinesResults迷宫求解.exe - 0 error(s), 0 war

19、ning(s)错误输入正确路径3.5参考文献1. 谭浩强 <<C 程序设计 >>M. 北京：清华大学出版社， 2006.2. 严蔚敏 <<数据结构（C语言版）>>M. 北京：清华大学出版社3. 王华 , 叶爱亮 等 .<<Visual C+6.0 编程实例与技巧 >>M. 北京：机械工业出版社 4. 钱新贤 ,程兆炜等 .<<Visual C+ 编程疑难详解>> M. 北京：人民邮电出版社，2000.第三部分 课程设计总结通过这段时间的课程设计，本人对软件专业的应用，数据结构的作用以及C语言的使用都

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

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

22、知不觉就走过了一年，一年的大学学习和课程实践阶段的提高，使我们本身知识得到提高的同时，也增强了我们对未来工作的信心，我们相信自己未来三年的学习更使我们有能力胜任将来的工作。 附录：（原程序代码）#include<stdio.h>#include<stdlib.h>/* 数据定义*/typedef enum ERROR, OK Status;typedef struct int row; /row表示“行”号 int line; /line表示“列”号 PosType; /位置的元素类型 typedef struct int ord; /该通道在路径上的“序号”

23、 PosType seat; /通道块在迷宫中的“坐标位置” int di; /从此通道走向下以通道块的“方向”SElemType; /栈的元素类型typedef struct SElemType * base; SElemType * top; int stacksize;SqStack;/* 函数原型说明*/Status InitStack(SqStack &S); /创建一个空栈SStatus Push(SqStack &S,SElemType &a); /插入新元素aStatus Pop(SqStack &S,SElemType &a); /删除

24、栈顶元素，a返回其值Status StackEmpty(SqStack S); /检查是否空栈Status MazePath(int maze1212,SqStack &S, PosType start, PosType end); /找通路void Initmaze(int maze1212,int size); /初始化迷宫void printmaze(int maze1212,int size); /显示迷宫Status Pass(int maze1212,PosType CurPos); /判断当前位置是否可通void Markfoot(int maze1212, PosTyp

25、e CurPos); /标记当前位置不可通PosType NextPos(PosType CurPos, int Dir); /进入下一位置void printpath(int maze1212,SqStack S,int size); /显示通路/* 主函数*/void main (void) SqStack S; int size; /正方形迷宫尺寸 int maze1212; /存储迷宫内路径可通情况 for(int n=0;n<10;n+) printf("创建一个正方形迷宫，请输入迷宫尺寸(注意不要大于10):n"); /设置迷宫大小 scanf("

26、;%d",&size);if(size<1 | size>10)printf("输入错误!");return; Initmaze(maze,size); /初始化迷宫 printmaze(maze,size); /显示所创建的迷宫 PosType start,end; /设置入口和出口 printf("输入入口行坐标和列坐标:");scanf("%d",&start.row);scanf("%d",&start.line); printf("输入出口行坐标和列

27、坐标:");scanf("%d",&end.row);scanf("%d",&end.line); if(MazePath(maze,S,start,end) /若有通路，显示通路 printpath(maze,S,size); else printf("找不到通路!nn"); /* 若迷宫maze中从入口 start到出口 end的通道，则求得一条存放在栈中 */Status MazePath(int maze1212,SqStack &S, PosType start, PosType end)

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

29、os.line=end.line) return 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.di<4) e.di+; / 换下一个方向探索 Push(S, e); curpos = NextPos(e

30、.seat, e.di); / 当前位置设为新方向的相邻块 while (!StackEmpty(S); return ERROR; /* 初始化迷宫*/void Initmaze(int maze1212,int size) char select; printf("选择创建方式 A:自动生成 B:手动创建n"); label:scanf("%c",&select); if(select='a'|select='A') /自动生成 for(int i=0;i<size+2;i+)maze0i=1; for(

31、 i=1;i<size+1;i+) mazei0=1; for(int j=1;j<size+1;j+) mazeij=rand()%2; mazeisize+1=1; for(i=0;i<size+2;i+)mazesize+1i=1; else if (select='b'|select='B') /手动设置 printf("按行输入%d*%d数据,0代表可通,1代表不可通(每行以Enter结束):n",size,size); for(int i=0;i<size+2;i+)maze0i=1; for( i=1;i

32、<size+1;i+) mazei0=1; for(int j=1;j<size+1;j+) scanf("%d",&mazeij); mazeisize+1=1; for(i=0;i<size+2;i+)mazesize+1i=1; else if(select='n')goto label; /排除Enter键的影响 else printf("输入错误!");/* 显示迷宫*/void printmaze(int maze1212,int size) printf("nn"); print

33、f("显示所建的迷宫(#表示外面的墙):n"); for(int i=0;i<size+2;i+)printf("%c ",'#');printf("n"); for(i=1;i<size+1;i+) printf("%c ",'#'); for(int j=1;j<size+1;j+） printf("%d ",mazeij); printf("%c",'#'); printf("n");

34、 for(i=0;i<size+2;i+)printf("%c ",'#');printf("n");/* 输出路径*/void printpath(int maze1212,SqStack S,int size) printf("nn通路路径为:n"); SElemType * p=S.base; while(p!=S.top) mazep->seat.rowp->seat.line=2; /标记为路径中的点 p+; for(int i=0;i<size+2;i+)printf("%c ",'#');printf("n"); for(i=1;i<size+1;i+) printf("%c ",'#'); for(int j=1;j<size+1;j+) if(mazeij=2) printf("%c ",'0'); else printf(" "); printf("%c",'#'); printf("n"); for(i=0;i&l