海南大学数据结构课程设计迷宫求解.doc

海南大学 数据结构课程设计 迷宫求解 班级： 姓名： 学号： 需求分析： 1问题描述 求迷宫中从入口到出口的所有路径是一个经典的程序设计问题，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。 本需求的编写目的在于将C语言与数据结构结合起来，使程序能够顺利进行，并且简洁，在此基础上更好的理解并运用数据结构知识。 2基本要求 (1)?设计一个迷宫； 　　(2)?对其求解； (3)?输出从入口到出口的路径； 概要设计 说明本程序中用到的所有抽象数据类型的定义。主程序的流程以及各程序模块之间的层次(调用)关系。 数据结构 typedef struct StackNode/* 构造栈 */ { ElemType *base; /*基指针*/ ElemType *top; /*栈顶指针*/ int stacksize; /*长度*/ }SqStack; 程序模块 int InitStack(SqStack *S) /*/初始化栈 int Push(SqStack *S,ElemType e) /*进栈操作，加入路径*/ int Pop(SqStack *S,ElemType *e) /*出栈操作*/ int StackEmpty(SqStack *S) /*判断栈是否为空*/ int FindWay(char maze[M][M]) int NextStep(int *x, int *y, int dir) 各模块之间的调用关系以及算法设计 void Input(char b[M][M])//输入时候请注意把一圈都输入为墙即# { int i, j; printf(请输入迷宫形状:\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(迷宫的形状为:\n); for (i = 0; i M; i++) { for (j = 0; j M; j++) { printf(%c,b[i][j]); } printf(\n); } } int main(void) { char a[M][M]; Input(a); Ouput(a); FindWay(a); Ouput(a); system(pause); return 0; } 详细设计 构造栈 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(ElemType)); 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; } 找寻路径 int F