迷宫问题课程设计
目 录
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;
}【迷宫问题课程设计】相关文章：
课程设计报告07-20
方法、思路与问题06-01
论文答辩问题01-17
休谟问题与先验范畴05-06
施工组织设计课程设计开题报告07-13
论文答辩问题与答案04-27
论文答辩的问题及答案04-06
答辩时要注意的问题04-14
让学生善于质疑问题06-11
物体平衡问题的求解方法05-13