迷宫问题课程设计

目录 1问题描述………………………………………………………………...1 2需求分析 1 3概要设计 1 3.1抽象数据类型定义 1 3.2子程序及功能要求 1 3.3各程序模块之间的调用关系 2 4详细设计 2 4.1设计相应数据结构 2 4.2主要模块的算法描述 3 5测试分析 9 6课程设计总结 10 参考文献 10 附录（源程序清单） 10 1 问题描述编制程序给出一条通过迷宫的路径或报告一个“无法通过”的信息。该迷宫是一个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 10 int 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("%d\n",e); return OK; } int StackEmpty(SqStack *S) //判断栈是否为空 { if(S->top==S->base) return OK; else return 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; e.dir = 1; Push(&S,e); if (x == M-2 && y == M-2) { printf("cunzaichukou\n"); return 1; } NextStep(&x,&y,1); constep++; } else { Pop(&S,&e); while (e.dir == 4 && !StackEmpty(&S)) { maze[e.x][e.y] = '0'; Pop(&S,&e); } { if (e.dir < 4) { e.dir++; Push(&S,e); x = e.x; y = e.y; NextStep(&x, &y, e.dir); } else { printf("meiyouchukou\n"); return 0; } } } }while(S.top!=S.base); 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 10 int 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("%d\n",e); return OK; } int StackEmpty(SqStack *S) //判断栈是否为空 { if(S->top==S->base) return OK; else return 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; e.dir = 1; Push(&S,e); if (x == M-2 && y == M-2) { printf("cunzaichukou\n"); return 1; } NextStep(&x,&y,1); constep++; } else { Pop(&S,&e); while (e.dir == 4 && !StackEmpty(&S)) { maze[e.x][e.y] = '0'; Pop(&S,&e); } { if (e.dir < 4) { e.dir++; Push(&S,e); x = e.x; y = e.y; NextStep(&x, &y, e.dir); } else { printf("meiyouchukou\n"); return 0; } } } }while(S.top!=S.base); 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; }