C语言与数据结构课程设计报告学号姓名课程设计题目迷宫求解2011 年 12 月目录1 需求分析1.1 功能与数据需求1.1.1 题目要求的功能1.1.2 扩展功能1.2 界面需求1.3 开发环境与运行需求2 概要设计2.1主要数据结构2.2程序总体结构2.3各模块函数说明3 详细设计3.1算法分析与设计3.2主要程序段设计4 测试5 使用说明5.1应用程序功能的详细说明5.2应用程序运行环境要求5.5输入数据类型、格式和内容限制6 总结提高6.1课程设计总结6.2开发中遇到的问题和解决方法6.3 对自己完成课设完成情况的评价6.4《C语言与数据结构课程设计》课程的意见与建议附录：程序源代码1 需求分析1.1 功能与数据需求迷宫求解问题描述：以一个m×n的长方形表示迷宫，0和1分别表示迷宫中的通路和障碍。

设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

1.1.1 题目要求的功能基本要求：首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。

求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。

如：对于下列数据的迷宫，输出的一条通路为：（1,1,1）, （1,2,2）, （2,2,2）（3,2,3）, （3,1,2）,…。

测试数据：迷宫的测试数据如下：左上角（1,1）为入口，右下角（9,8）为出口。

1.1.2 扩展功能（1）编写递归形式的算法，求得迷宫中所有可能的通路；（2）以方阵形式输出迷宫及其通路1.2 界面需求请求输入进入程序请求输入起始位置请求输入终点位置输出方阵迷宫输出路径输出方阵路径1.3 开发环境与运行需求Visual C++6.02 概要设计2.1主要数据结构int top;int base;}Stack; //新建结构体void initStack(Stack *p)//初始化栈Push(Stack *p,int x,int y,int d) //入栈具体操作 Pop(Stack *p,int read[2],int d) //出栈并读出前一步的坐标 initMaze(int Maze[10][9])//建立迷宫Ways(Stack *p,int Maze[10][9],int rukou_x,int rukou_y,int chukou_x,int chukou_y,int d) //具体路径的求解 menu();//调用菜单函数 main();//实现迷宫求解的主函数3 详细设计迷宫的过程可以模拟为一个搜索的过程：每到一处，总让它按左、右、上、下4个方向顺序试探下一个位置；如果某方向可以通过，并且不曾到达，则前进一步，在新位置上继续进行搜索；如果4方向都走不通或曾经到达过，则退回一步，在原来的位置上继续试探下一位置。

每前进或后退一步，都要进行判断：若前进到了出口处，则说明找到了一条合适的通路；若退回到了入口处，则说明不存在合法的通路到达出口。

用一个二维指针数组迷宫表示迷宫，数组中每个元素取值“0”（表示通路）或“1”（表示墙壁）。

迷宫的入口点在位置（1，1）处，出口点在位置（m,n）处。

设计一个模拟走迷宫的算法，为其寻找一条从入口点到出口点的通路。

二维数组的第0行、第m+1行、第0列、第m+1列元素全置成“1”，表示迷宫的外墙；第1行第1列元素和第m行第m列元素置成“0”，表示迷宫的入口和出口；假设当前所在位置是（x,y）。

沿某个方向前进一步，它可能到达的位置最多有4。

4 测试5 使用说明5.1应用程序功能的详细说明按提示输入数字1进入迷宫，输入迷宫入口，迷宫出口5.2应用程序运行环境要求Microsoft Visual C++6.05.5输入数据类型、格式和内容限制输入的数据都是整型（int），输入迷宫的数据间要用空格或回车隔开6 总结提高6.1课程设计总结要能很好的掌握编程,仅仅通过简单的程序的编写是无法达成的,需要大量积累和深入研究才有可能。

就从这个迷宫问题求解来说,在迷宫求路径就需要使用链表的栈,靠出栈和进栈来存取路径数据.在程序的编写中也不能一味的向已有的程序进行模仿,而要自己摸索,去寻找最好的解决方法,只有带着问题去反复进行实践,才能更熟练的掌握和运用,当然,对现有的程序也要多去接触,因为有些程序是我们无法在短时间内想出来的.最重要的一点是持之以恒,要经常性的复习原来接触的程序,这样才能保证我们有足够的经验去面对程序问题.6.2开发中遇到的问题和解决方法问题：在开始时迷宫求解的路径无法显示寻找路径所走的方向等问题。

解决方法：在栈中增加一个变量d来表示方向，在寻找路径的时候判断下一个坐标点和本坐标点的关系。

在（x）行不变的情况下：（y+1）列加一则表示坐标往右走了一步记为1、（y-1）列减一则表示坐标往左走了一步记为3；在（y）不变的情况下：（x+1）行加一则表示坐标往下走了一步记为2、（x-1）行减一则表示坐标往上走了一步记为4；6.3 对自己完成课设完成情况的评价经过本次课程设计，我深刻地明白了理论与实践应用相结合的重要性，并努力克服自己在分析复杂问题的弱点。

这次课程设计同时也考验我的综合运用所学知识的能力和操作能力。

参考用书：《数据结构（C 语言）》，严蔚敏、吴伟民等，清华大学出版社，2010 年《数据结构与算法分析（c++语言描述）》第2 版，黄达民编著，清华大学出版社2006.116.4《C语言与数据结构课程设计》课程的意见与建议希望老师能指导我们把所有的课程设计题目都做一遍，因为每一道题目所能体现的知识点是有限的，而且要想提高我们的编程能力还需要大量的练习。

附录：程序源代码#include <stdio.h>#include <malloc.h>#include<stdlib.h>#include<conio.h>#define length 50#define d direction //用d代表所走路径的方向int n=-1;int step=0; //记录步骤数typedef struct{int pos_x[length];//进栈坐标int pos_y[length];int top;int base;}Stack; //新建结构体void initStack(Stack *p){p->top=p->base=0;}//初始化栈.Push(Stack *p,int x,int y,int d) //入栈具体操作{step++;d=0;n=n+1;p->top=p->top+1;p->pos_x[n]=x;p->pos_y[n]=y;}Pop(Stack *p,int read[2],int d) //出栈并读出前一步的坐标{step++;d=0;n=n-1;p->top=p->top-1;read[0]=p->pos_x[n];read[1]=p->pos_y[n];}initMaze(int Maze[10][9])//建立迷宫函数.{int i;for (i=0;i<=9;i++) {Maze[0][i]=1;}for (i=0;i<=10;i++) {Maze[i][0]=1;}for (i=0;i<=9;i++) {Maze[10][i]=1;}for (i=0;i<=10;i++) {Maze[i][9]=1;}Maze[1][1]=0;Maze[1][2]=0;Maze[1][3]=1;Maze[1][4]=0;Maze[1][5]=0;Maze[1 ][6]=0;Maze[1][7]=1;Maze[1][8]=0;Maze[2][1]=0;Maze[2][2]=0;Maze[2][3]=1;Maze[2][4]=0;Maze[2][5]=0;Maze[2 ][6]=0;Maze[2][7]=1;Maze[2][8]=0;Maze[3][1]=0;Maze[3][2]=0;Maze[3][3]=0;Maze[3][4]=0;Maze[3][5]=1;Maze[3 ][6]=1;Maze[3][7]=0;Maze[3][8]=1;Maze[4][1]=0;Maze[4][2]=1;Maze[4][3]=1;Maze[4][4]=1;Maze[4][5]=0;Maze[4 ][6]=0;Maze[4][7]=1;Maze[4][8]=0;Maze[5][1]=0;Maze[5][2]=0;Maze[5][3]=0;Maze[5][4]=1;Maze[5][5]=0;Maze[5 ][6]=0;Maze[5][7]=0;Maze[5][8]=0;Maze[6][1]=0;Maze[6][2]=1;Maze[6][3]=0;Maze[6][4]=0;Maze[6][5]=0;Maze[6 ][6]=1;Maze[6][7]=0;Maze[6][8]=1;Maze[7][1]=0;Maze[7][2]=1;Maze[7][3]=1;Maze[7][4]=1;Maze[7][5]=1;Maze[7 ][6]=0;Maze[7][7]=0;Maze[7][8]=1;Maze[8][1]=1;Maze[8][2]=1;Maze[8][3]=0;Maze[8][4]=0;Maze[8][5]=0;Maze[8 ][6]=1;Maze[8][7]=0;Maze[8][8]=1;Maze[9][1]=1;Maze[9][2]=1;Maze[9][3]=0;Maze[9][4]=0;Maze[9][5]=0;Maze[9 ][6]=0;Maze[9][7]=0;Maze[9][8]=0;}Print( )//打印出迷宫界面｛int m,n，j,sum；int Maze[10][9];printf("迷宫(1代表墙即不通,0代表可通过)\n");printf(" ");for(j=1;j<=8;j++) { printf("%4d",j);}printf("\n");for(m=0;m<=10;m++){for(n=0;n<=9;n++){printf("%4d",Maze[m][n]);sum++;if(sum%10==0) printf("\n");}}｝Ways(Stack *p,int Maze[10][9],int rukou_x,int rukou_y,int chukou_x,int chukou_y,int d) //具体路径的求解函数{int x,y;int read[2];x=rukou_x;y=rukou_y;printf("第%d步:",step);printf("(%d,%d,%d)\n",x,y,d);if(x==chukou_x&&y==chukou_y){printf("到达出口坐标共走了%d步\n",step);return 0;}else if(Maze[x][y+1]==0) {y=y+1;d=1;Push(p,x,y,d);Maze[x][y-1]=1;Maze[x][y]=1;}else if(Maze[x+1][y]==0) {x=x+1;d=2;Push(p,x,y,d);Maze[x-1][y]=1;Maze[x][y]=1;}else if(Maze[x][y-1]==0) {y=y-1;d=3;Push(p,x,y,d);Maze[x][y+1]=1;Maze[x][y]=1;}else if(Maze[x-1][y]==0){x=x-1;d=4;Push(p,x,y,d);Maze[x+1][y]=1;Maze[x][y]=1;}else{Pop(p,read,d);x=read[0];y=read[1];if(p->top==p->base) {printf("找不到出口\n");return 0;}}Ways(p,Maze,x,y,chukou_x,chukou_y,d);return 1;}menu(){printf("\t\t************************************\n");printf("\t\t* 欢迎进入课程设计*\n");printf("\t\t* 迷宫求解程序*\n");printf("\t\t* 菜单: *\n");printf("\t\t***进入迷宫***请输入1 *\n");printf("\t\t***退出迷宫***请输入2 *\n");printf("\t\t************************************\n");}int main(){Stack *p;Stack S;int Maze[10][9]; //定义迷宫int elem_1[1],elem_2[1],a,j;int rukou_x,rukou_y,d=0;int chukou_x,chukou_y;int sum=0;p=&S;initMaze(Maze);system("color 5f");//dos窗口背景颜色函数menu();//调用菜单函数printf("请输入您的选择:");scanf("%d",&a);if(a==1){Print( ) //打印迷宫图.；printf("请输入入口坐标:");scanf("%d",&elem_1[0]);scanf("%d",&elem_1[1]);rukou_x=elem_1[0];rukou_y=elem_1[1];printf("请输入出口坐标:"); //迷宫入口坐标.scanf("%d",&elem_2[0]);scanf("%d",&elem_2[1]);chukou_x=elem_2[0];chukou_y=elem_2[1];//迷宫出口坐标.if(elem_1[0]>10||elem_1[1]>9||elem_2[0]>10||elem_2[1]>9||elem_1[0]<0||elem_1[1]<0||elem_2[0]<0||elem_2[1]<0){printf("输入的入口或出口坐标错误\n");} //首先判断输入坐标是否正确else{ printf("\n");printf("说明(x,y,z)x,y代表坐标点;\n");printf("z代表上个坐标到达这个坐标所走的方向,0为初始值,1234分别代表向右、下、左、上方向\n");printf("查找路径的具体步骤:\n");initStack(p);Push(p,rukou_x,rukou_y,d);Ways(p,Maze,rukou_x,rukou_y,chukou_x,chukou_y,d);}system("pause");system("cls");return main();}else{printf("欢迎您的再次光临,再见!\n");}system("pause");}。