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