迷宫问题课程设计

1、    迷宫问题课程设计    目 录 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列

2、的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

3、 *top; int stacksize; SqStack; 3.2 子程序及功能要求 （1）void Input(char bMM); （2）void Ouput(const char bMM); （3）int FindWay(char mazeMM); （4）int NextStep(int *x, int *y, int dir).    3.3 各程序模块之间的调用关系 主函数可调用子程序void Input(char bMM); void Ouput(const char bMM); int FindWay(char mazeMM); int

4、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(ElemTyp

5、e); 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

6、 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); i

7、f(!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("m

8、emory 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

9、) return OK; else return ERROR; void Input(char bMM) /输入时候请注意把一圈都输入为墙即'#' int i, j; printf("qingshuirumigongxingzhuang:n"); for (i = 0; i #include #define M 10 /自己规定为10*10的迷宫 #define OK 1 #define ERROR 0 #define OVERFLOW -1 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 int

10、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("

11、;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

12、,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; else retur

13、n ERROR; void Input(char bMM) /输入时候请注意把一圈都输入为墙即'#' int i, j; printf("qingshuirumigongxingzhuang:n"); for (i = 0; i < M; i+) for (j = 0; j < M; j+) scanf("%c",&bij); getchar();/吃掉内存中的残留换行符号 void Ouput(const char bMM) int i, j; printf("migongxingzhuangwei:n&q

14、uot;); for (i = 0; i < M; i+) for (j = 0; j < M; j+) printf("%c",bij); printf("n"); int FindWay(char mazeMM) ElemType e; int constep = 1; int x = 1, y = 1; SqStack S; InitStack(&S); do if (mazexy = ' ') /当第3次时 mazexy!=' ' 照样通不过 mazexy = '1' e.x =

15、 x; e.y = y; e.dir = 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 (e.dir = 4 && !StackEmpty(&S) mazee.xe.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("meiyouchukoun"); return 0; while(S.top!=S.base); return 0; int NextStep(int *x, in