程序设计实验报告

1、 兰州商学院陇桥学院兰州商学院陇桥学院 工学系课程设计报告工学系课程设计报告设设 计计 题题 目：目：迷宫与栈问题迷宫与栈问题 系系 别：别：工工 学学 系系 专专 业业 ( (方方 向向) )： 年年 级、级、 班：班： 学学 生生 姓姓 名：名： 学学 生生 学学 号：号： 指指 导导 教教 师：师： 目录目录一、系统开发的背景一、系统开发的背景.1二、系统分析与设计二、系统分析与设计.1（一）系统的分析.1（二）系统的具体分析设计.2三、系统的功能要求三、系统的功能要求.2（一）系统模块结构设计.3四、系统的设计与实现四、系统的设计与实现.4（一）在栈中实现迷宫的具体操作.4（二）栈的生

2、成.6（三）整个系统的生成流程图.8五、系统测试五、系统测试.9（一）测试迷宫与栈问题可通的程序设计.9 （二）测试迷宫与栈问题不可通的程序设计.10六、六、 总总结结.10七、附件（代码、部分图表）七、附件（代码、部分图表）.111迷宫与栈问题迷宫与栈问题一、一、系统开发的系统开发的背景背景迷宫与栈问题的课程设计相当于是一个小游戏的开发，它来源于多年以来，迷宫问题一直是令人感兴趣的题目。实验心理学家训练老鼠在迷宫中寻找食物。许多神秘主义小说家也曾经把英国乡村花园迷宫作为谋杀现场。于是，老鼠过迷宫问题就此产生，这是一个很有趣的计算机问题，主要利用 “栈”是老鼠通过尝试的办法从入口穿过迷宫走到出

3、口。迷宫只有两个门，一个叫做入口，另一个叫做出口。把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。求解迷宫问题，即找出从入口到出口的路径。而数据结构则是数据的组织形式，可以用来表示特定的对象数据，在计算机中对数据的一种存储和组织形式，因此选用栈思想实现迷宫游戏的基本操作，也是我开发迷宫小游戏的基本背景。二、二、 系统分析与设计系统分析与设计( (一一) ) 系统分析：迷宫问题通常是用“穷举求解”方法解决，即从入口出发，顺着某个方向进行搜索，若能走通，则继续往前走；否则沿着原路退回

4、，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。栈是一个后进先出的结构，2可以用来保存从入口到当前位置的路径。定义迷宫类型来存储迷宫数据，通常设定入口点的下标，出口点的下标，为处理方便起见，在迷宫的周围加一圈障碍，对于迷宫任何一个位置均约定为东、西、南、北四个方向可同。( (二二) ) 系统具体设计在某个点上，按照一定的顺序（在本程序中顺序为上、右、下、左）对周围的墙、路进行判断（在本程序中分别用 1、0）代替，若周围某个位置为 0，则移动到该点上，再进行下一次判断；若周围的位置都为 1（即没有通路），则一步步原路返回并判断有

5、无其他通路，然后再次进行相同的判断，直到走到终点为止，或者确认没有任何通路后终止程序。要实现上述算法，需要用到栈的思想。栈里面压的是走过的路径，若遇到死路，则将该位置（在栈的顶层）弹出，再进行下一次判断；若遇到通路，则将该位置压栈并进行下一次判断。如此反复循环，直到程序结束。此时，若迷宫有通路，则栈中存储的是迷宫通路坐标的倒序排列，再把所有坐标顺序打印后，即可得到正确的迷宫通路。三、三、系统功能要系统功能要求求（1）首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非归程序。求得的通路以三元组（i，j，d）的形式输出。其中：（i，j）指示迷宫中的一个坐标，d 表示走到下一坐标的方向。

6、如，对于下列数据的迷宫，输出一条通路为：（1，1，1） ，（1，2，2） ， （2，2，2） ， （3，2，3） ， （3，1，2） ，。3（2）编写递归形式的算法，求得迷宫中所有可能的通路。（3）以方阵形式输出迷宫及其通路。（一）系统模块结构设计（一）系统模块结构设计通过对系统功能的分析，迷宫与栈问题的功能如图 1 所示。 图 1： 迷宫实现的主函数功能图通过上图的功能分析，把整个系统划分为 2 个模块：1、 通过栈后进先出的结构，实现栈判断，首先判断栈是否为空，如果不为空，则实现栈中基本的入栈，出栈的实现。顺序栈是用一组地址连续的 内存单元依次保存栈中的运算规则，在链式存储中链表首部 he

7、ad 指针所指向元素为栈顶元素，栈表尾部指向地址为 NULL 为栈底。2、 借助函数的嵌套与使用，由 while 语句对整体进行控制，return语句控制跳出函数，判断在迷宫中是否有出路，如果有出路，则通过东，西，南，北的方向进行路径的输出；如果无出路，则说明此迷宫不能走出。主函数初始化栈入栈出栈判断栈是否为空判断方向留下足迹判断能否通过初始化迷宫求解所有路径输出迷宫留下标记4四、四、 系统的设计系统的设计与实现与实现（一）（一） 在栈中实现迷宫的基本操作在栈中实现迷宫的基本操作分析：首先输出表头，然后依次输入想要实现的步骤。功能图如图 2所示。入口，出口位置传人方法里判断当前是否通过循环不结

8、束，无解迷宫将元素入栈是否到达迷宫出口右边是否存在通路上边是否存在通路下边是否存在通路左边是否存在通路存在结点入栈有解迷宫5图 2：迷宫的实现功能图该模块的具体代码如下所示。void lujing(struct Zuobiao start,struct Zuobiao end,int mazeMN,int diradd42) int i,j,d;int a,b; lianzhan elem,e; PLStack S1, S2; InitStack(S1); InitStack(S2); mazestart.xstart.y=2; /入口点作上标记 elem.x=start.x; elem.y=

9、start.y; elem.d=-1; /开始为-1 Push(S1,elem); while(!StackEmpty(S1) /栈不为空 有路径可走 Pop(S1,elem); i=elem.x; j=elem.y; d=elem.d+1; /下一个方向 while(d %d,%d,%d,e.x,e.y,e.d); return; /选用 return 跳出两层循环 if(mazeab=0) /找到可以前进的非出口的点 mazeab=2; /标记走过此点 elem.x=i; elem.y=j; elem.d=d; Push(S1,elem); /当前位置入栈 i=a; /下一点转化为当前点

10、j=b; d=-1; d+; printf(迷宫没有路径，你走不出去啦！还想玩吗？n); （二）（二） 栈的生成栈的生成图 3：栈的实现功能图栈的初始化栈为空入栈出栈7该模块的具体代码如下所示。int InitStack(PLStack &S) /构造空栈 S=NULL; return 1; int StackEmpty(PLStack S) /判断栈是否为空 if(S=NULL) return 1; else return 0; int Push(PLStack &S, lianzhan e) /在栈中放入一个新的数据元素 PLStack p; p=(PLStack)mall

11、oc(sizeof(LStack); / 申请新的栈顶结点空间p-elem=e; /将元素值置入结点数据域p-next=S; /原栈顶结点昨晚新结点后继S=p; /将新结点置为栈顶return 1; int Pop(PLStack &S,lianzhan &e) /栈顶元素出栈 PLStack p; if(!StackEmpty(S) e=S-elem; p=S; S=S-next; free(p); /释放结点return 1; else return 0; （三）（三） 整个系统的生成流程图整个系统的生成流程图8NY Y N Y Y N Y N N 初始化判断输入的数据创建

12、并输入迷宫前方是否有墙前行左方右方后转右转左转是否找到出路终点用户输入迷宫大小输入迷宫行行输入迷宫列用户输入入口，出口9Y 五、五、 系测试系测试（一）（一） 测试测试迷宫与栈问题的可通程序设计迷宫与栈问题的可通程序设计测试该函数使用的测试方法，测试的具体步骤，测试用例的选取，测试的结果。图 4： 在测试中可以找到迷宫路径输出迷宫通路结束10（二）（二） 测试迷宫与栈问题的不可通程序设计测试迷宫与栈问题的不可通程序设计测试该函数使用的测试方法，测试的具体步骤，测试用例的选取，测试的结果。图 5： 在测试中并未找到迷宫路径六、总结六、总结迷宫小游戏首先实现了随机输入 m 和 n 的值，自己设定一

13、个矩阵的行与列，在给定空间内控制了迷宫的范围，再从电脑中输入“0”为通路，“1”为围墙显示出一个迷宫的雏形来，最终通过 for 循环给写好的迷宫加一个围墙，得到我们想要的结果，并且给定迷宫的入口和出口，从而寻找11到迷宫的可同路径或者说入口处进入后，并不能找到可通路径从而退出。也可以循环使用此小游戏。系统在设计过程中我只考虑到了迷宫中给定入口和出口，在选择路径时仅有东、西、南、北，这四个方向寻找出口，而不是更加全面的在东南、东北、西南、西北，方向同时寻找迷宫的出路，因此这一点是我认为考虑很不周到的，希望能够在今后的学习中更好的完善，让这个迷宫小游戏更加的充实。我的收获是这次的课程设计的内容是使

14、用 C 语言和数据结构来实现栈的应用，这对我来说是个很具有挑战性的任务，虽然只做了一个迷宫与栈的问题，而且运行起来有很大的局限性，但通过两星期的设计也从中学到了不少的东西，更多的了解到了课本中丰富的内容。 数据结构是一门实践性较强的课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。同时再次深刻的了解了数据结构中数组与基本函数之间的调用，并且使用顺序结构，选择结构，循环结构的嵌套，根据实际问题的需要实现迷宫与栈问题。在本次课程设计中，我明白了理论与实际相结合的重要性，并提高了自己组织数据及编写程序的能力，挺高了综合运用所学知识的能力。七、附件（代码、部分图表）七、附件（代码、部分图

15、表）#include #include #define M 20 /行#define N 20 /列struct Zuobiao /定义迷宫内点的坐标类型 12int x; int y; ; struct lianzhan /链栈元素 int x,y; /x 行,y 列 int d; /d 为下一步的方向 ;typedef struct LStack /链栈 lianzhan elem; struct LStack *next; *PLStack; /*栈函数*/ int InitStack(PLStack &S) /构造空栈 S=NULL; return 1; int StackEm

16、pty(PLStack S) /判断栈是否为空 if(S=NULL) return 1; else return 0; int Push(PLStack &S, lianzhan e) /在栈中放入一个新的数据元素（进栈） PLStack p; p=(PLStack)malloc(sizeof(LStack); / 申请新的栈顶结点空间p-elem=e; /将元素值置入结点数据域p-next=S; /原栈顶结点昨晚新结点后继S=p; /将新结点置为栈顶return 1; int Pop(PLStack &S,lianzhan &e) /栈顶元素出栈 PLStack p;

17、 if(!StackEmpty(S) e=S-elem; p=S; S=S-next; free(p); /释放结点13return 1; else return 0; /*求迷宫路径函数*/ void lujing(struct Zuobiao start,struct Zuobiao end,int mazeMN,int diradd42) int i,j,d;int a,b; lianzhan elem,e; PLStack S1, S2; InitStack(S1); InitStack(S2); mazestart.xstart.y=2; /入口点作上标记 elem.x=start.

18、x; elem.y=start.y; elem.d=-1; /开始为-1 Push(S1,elem); while(!StackEmpty(S1) /栈不为空 有路径可走 Pop(S1,elem); i=elem.x; j=elem.y; d=elem.d+1; /下一个方向 while(d %d,%d,%d,e.x,e.y,e.d); return; /选用 return 跳出两层循环 if(mazeab=0) /找到可以前进的非出口的点 mazeab=2; /标记走过此点 elem.x=i; elem.y=j; elem.d=d; Push(S1,elem); /当前位置入栈 i=a; /

19、下一点转化为当前点 j=b; d=-1; d+; printf(迷宫没有路径，你走不出去啦！还想玩吗？n); /*建立迷宫*/ void initmaze(int mazeMN) int i,j; int m,n; /迷宫行,列 printf(请输入迷宫的行数 :m=); scanf(%d,&m); printf(请输入迷宫的列数 :n=); scanf(%d,&n); printf(*n);printf(n 请用空格隔开输入迷宫的各行各列(0 代表路,1 代表墙):n,m,n); for(i=1;i=m;i+) for(j=1;j=n;j+) scanf(%d,&mazeij); printf(*以下展示的是我所建立的迷宫*n); for(i=0;i=m+1;i+) /加一圈围墙 mazei0=0; 15mazein+1=0; for(j=0;j=n+1;j+) maze0j=0;