迷宫问题课程设计

目 录1问题描述………………………………………………………………...12需求分析 13概要设计 13.1抽象数据类型定义 13.2子程序及功能要求 13.3各程序模块之间的调用关系 24详细设计 24.1设计相应数据结构 24.2主要模块的算法描述 35测试分析 96课程设计总结 10参考文献 10附录（源程序清单） 101 问题描述编制程序给出一条通过迷宫的路径或报告一个“无法通过”的信息。该迷宫是一个M行N列的0-1矩阵，其中0表示无障碍，1表示有障碍。设入口为（1，1）出口为（M，N）每次移动只能从一个无障碍的单元移到其周围8个方向上任一无障碍的单元，2 需求分析该算法的基本思想是：（1） 若当前位置“可通”，则纳入路径，继续前进;（2）若当前位置“不可通”，则后退，换方向继续探索;（3）若四周“均无通路”，则将当前位置从路径中删除出去。3 概要设计3.1 抽象数据类型定义typedef struct{int x, y; //坐标int dir; //方向}ElemType;typedef struct StackNode//构造栈{ElemType *base;ElemType *top;int stacksize;}SqStack;3.2 子程序及功能要求（1）void Input(char b[M][M]);（2）void Ouput(const char b[M][M]);（3）int FindWay(char maze[M][M]);（4）int NextStep(int *x, int *y, int dir).3.3 各程序模块之间的调用关系主函数可调用子程序void Input(char b[M][M]); void Ouput(const char b[M][M]); int FindWay(char maze[M][M]); int NextStep(int *x, int *y, int dir).4 详细设计4.1 设计相应数据结构（1）迷宫类型定义typedef struct{int x, y; //坐标int dir; //方向}ElemType;typedef struct StackNode//构造栈{ElemType *base;ElemType *top;int stacksize;}SqStack;（2）栈元素类型定义int InitStack(SqStack *S) //初始化栈{S->base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S->base){printf("memory allocation failed,goodbye");exit(1);}S->top=S->base;S->stacksize=STACK_INIT_SIZE;return OK;}4.2 主要模块的算法描述#include#include#define M 10 //自己规定为10*10的迷宫#define OK 1#define ERROR 0#define OVERFLOW -1#define STACK_INIT_SIZE 100#define STACKINCREMENT 10int findway(int);int NextStep(int *, int *, int );typedef struct{int x, y; //坐标int dir; //方向}ElemType;typedef struct StackNode//构造栈{ElemType *base;ElemType *top;int stacksize;}SqStack;int InitStack(SqStack *S) //初始化栈{S->base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S->base){printf("memory allocation failed,goodbye");exit(1);}S->top=S->base;S->stacksize=STACK_INIT_SIZE;return OK;}int Push(SqStack *S,ElemType e) //进栈操作{if(S->top-S->base>=S->stacksize){S->base=(ElemType*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(Eleme));if (!S->base){printf("memory allocation failed,goodbye");exit(1);}S->top = S->base+S->stacksize;S->stacksize += STACKINCREMENT;}*S->top++=e;return OK;}int Pop(SqStack *S,ElemType *e) //出栈操作{if(S->top==S->base){return ERROR;}*e=*--S->top;printf("%dn",e);return OK;}int StackEmpty(SqStack *S) //判断栈是否为空{if(S->top==S->base)return OK;elsereturn ERROR;}void Input(char b[M][M]) //输入时候请注意把一圈都输入为墙即'#'{int i, j;printf("qingshuirumigongxingzhuang:n");for (i = 0; i < M; i++){for (j = 0; j < M; j++){scanf("%c",&b[i][j]);}getchar();//吃掉内存中的'残留换行符号}}void Ouput(const char b[M][M]){int i, j;printf("migongxingzhuangwei:n");for (i = 0; i < M; i++){for (j = 0; j < M; j++){printf("%c",b[i][j]);}printf("n");}}int FindWay(char maze[M][M]){ElemType e;int constep = 1;int x = 1, y = 1;SqStack S;InitStack(&S);do{if (maze[x][y] == ' ') //当第3次时 maze[x][y]!=' ' 照样通不过{maze[x][y] = '1';e.x = x;e.y = y; = 1;Push(&S,e);if (x == M-2 && y == M-2){printf("cunzaichukoun");return 1;}NextStep(&x,&y,1);constep++;}else{Pop(&S,&e);while ( == 4 && !StackEmpty(&S)){maze[e.x][e.y] = '0';Pop(&S,&e);}{if ( < 4){++;Push(&S,e);x = e.x;y = e.y;NextStep(&x, &y, );}else{printf("meiyouchukoun");return 0;}}}}while(!=);return 0;}int NextStep(int *x, int *y, int dir){switch(dir){case 1:(*y)++;break;case 2:(*x)++;break;case 3:(*y)--;break;case 4:(*x)--;break;default:break;}return 0;}int main(void){char a[M][M];Input(a);Ouput(a);FindWay(a);Ouput(a);system("pause");return 0;}5 测试分析6 课程设计总结该次程序设计我作为组长，我先写了任务书，再把模板及其要求告诉了组员，再跟他们一起编写程序、查找资料来修改程序，再一起测试分析，最后以总结结束通过这次课程设计，我深刻的体会到了数据结构的重要性。学数据结构不只是为了考试，更重要的是它对我们以后也会有很大的帮助，尤其是我们这个注专业。在整个课程设计过程中，我遇到了许多困难，不管是编程序改还是调试等都存在很多问题。一遇到问题我就查看各种资料来解决，但还是又很多不明白的地方，特别是运行的时候我还问了同学。由此我意识到自己有许多要学的，学的也不够认真不够透彻。参考文献：[1] 严蔚敏，吴伟民. 数据结构（C语言版）[M]. 北京：清华大学出版社，2002 [2] 刘振鹏，张晓莉，郝杰．数据结构[M]．北京：中国铁道出版社，2003 [3] 李春葆．数据结构习题与解析（C语言篇）[M]．北京：清华大学出版社，2000附录（源程序清单）#include#include#define M 10 //自己规定为10*10的迷宫#define OK 1#define ERROR 0#define OVERFLOW -1#define STACK_INIT_SIZE 100#define STACKINCREMENT 10int findway(int);int NextStep(int *, int *, int );typedef struct{int x, y; //坐标int dir; //方向}ElemType;typedef struct StackNode//构造栈{ElemType *base;ElemType *top;int stacksize;}SqStack;int InitStack(SqStack *S) //初始化栈{S->base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S->base){printf("memory allocation failed,goodbye");exit(1);}S->top=S->base;S->stacksize=STACK_INIT_SIZE;return OK;}int Push(SqStack *S,ElemType e) //进栈操作{if(S->top-S->base>=S->stacksize){S->base=(ElemType*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(Eleme));if (!S->base){printf("memory allocation failed,goodbye");exit(1);}S->top = S->base+S->stacksize;S->stacksize += STACKINCREMENT;}*S->top++=e;return OK;}int Pop(SqStack *S,ElemType *e) //出栈操作{if(S->top==S->base){return ERROR;}*e=*--S->top;printf("%dn",e);return OK;}int StackEmpty(SqStack *S) //判断栈是否为空{if(S->top==S->base)return OK;elsereturn ERROR;}void Input(char b[M][M]) //输入时候请注意把一圈都输入为墙即'#'{int i, j;printf("qingshuirumigongxingzhuang:n");for (i = 0; i < M; i++){for (j = 0; j < M; j++){scanf("%c",&b[i][j]);}getchar();//吃掉内存中的残留换行符号}}void Ouput(const char b[M][M]){int i, j;printf("migongxingzhuangwei:n");for (i = 0; i < M; i++){for (j = 0; j < M; j++){printf("%c",b[i][j]);}printf("n");}}int FindWay(char maze[M][M]){ElemType e;int constep = 1;int x = 1, y = 1;SqStack S;InitStack(&S);do{if (maze[x][y] == ' ') //当第3次时 maze[x][y]!=' ' 照样通不过{maze[x][y] = '1';e.x = x;e.y = y; = 1;Push(&S,e);if (x == M-2 && y == M-2){printf("cunzaichukoun");return 1;}NextStep(&x,&y,1);constep++;}else{Pop(&S,&e);while ( == 4 && !StackEmpty(&S)){maze[e.x][e.y] = '0';Pop(&S,&e);}{if ( < 4){++;Push(&S,e);x = e.x;y = e.y;NextStep(&x, &y, );}else{printf("meiyouchukoun");return 0;}}}}while(!=);return 0;}int NextStep(int *x, int *y, int dir){switch(dir){case 1:(*y)++;break;case 2:(*x)++;break;case 3:(*y)--;break;case 4:(*x)--;break;default:break;}return 0;}int main(void){char a[M][M];Input(a);Ouput(a);FindWay(a);Ouput(a);system("pause");return 0;}