数据结构课程设计
设计题目： 迷宫问题
学 院： 信息技术学院
专 业： 网络工程
班 级： B1204
学 号： 0913120419
姓 名： 葛晨阳
指导老师： 戴玉洁
课程设计日期： 2013年 7月 20日— 2013年 8月日 1
实验题目
一、问题描述
输入一个任意大小的迷宫数据，用递归和非递归两种方法求出一条走出迷宫的路径，并将路径输出。
二、实现目标
综合运用递归、栈等数据结构知识，掌握、提高分析、设计、实现及测试程序的综合能力
三、主要功能模块及实现功能
（创建一顺序栈：
PSeqStack Init_SeqStack(void)
判断栈是否为空：
int Empty_SeqStack(PSeqStack S)
在栈顶插入一新元素x ：
int Push_SeqStack (PSeqStack S, DataType x)
删除栈顶元素并保存在*x ：
int Pop_SeqStack(PSeqStack S ,DataType *x)
销毁栈 ：
void Destroy_SeqStack(PSeqStack *S)
利用栈的非递归算法求迷宫路径：
int mazepath(int maze [ ][n+2] ,item move[ ],int x0,int y0)
递归算法求迷宫路径：
int mazepath1(int maze[][n+2],item move[],int x,int y)
主函数：
int main()
{ 出口坐标已定，
利用while 循环多次输入入点坐标，
调用mazepath(int maze [ ][n+2] ,item move[ ],int x0,int y0)
输出可走的路径
}
四、主要模块流程图
五、实验结果及测试数据
初始界面
游戏界面
游戏界面
附录:源代码
#include
#include
#define m 6
#define n 8
#define MAXSIZE 100
int maze[m+2][n+2]={
{1,1,1,1,1,1,1,1,1,1},//四周为1代表围墙,0为可走路径
{1,0,0,1,1,0,0,0,1,1},
{1,0,0,0,0,1,1,1,1,1},
{1,0,1,0,0,0,0,0,1,1},
{1,0,1,1,1,0,0,1,1,1},
{1,1,0,0,1,1,0,0,0,1},
{1,0,1,0,0,0,1,1,0,1},
{1,1,1,1,1,1,1,1,1,1}
}; //入口坐标为（1，1），出口坐标为（6，8）
typedef struct
{
int x,y;/*试探方向*/
}item;
item move[4]={{0,1},{1,0},{0,-1},{-1,0}};
typedef struct/*栈的设计*/
{
int x,y,d; /*纵横坐标及方向*/
}DataType;
typedef struct/*栈*/
{
DataType data[MAXSIZE];
int top;
}SeqStack,*PSeqStack;
PSeqStack Init_SeqStack(void)
{ /*创建一顺序栈，入口参数无，返回一个指向顺序栈的指针，为零表示分配空间失败*/
PSeqStack S;
S=(PSeqStack)malloc(sizeof(SeqStack));
if (S)
S->top= -1;
return S;
}
int Empty_SeqStack(PSeqStack S)
{ /*判断栈是否为空，入口参数：顺序栈，返回值：1表示为空，0表示非空*/ if (S->top== -1)
return 1;
else
return 0;
}
int Push_SeqStack (PSeqStack S, DataType x)
{ /*在栈顶插入一新元素x ， 入口参数：顺序栈，返回值：1表示入栈成功，0表示失败。*/
if (S->top==MAXSIZE-1)
return 0; /*栈满不能入栈*/
else
{
S->top++;
S->data[S->top]=x;
return 1;
}
}
int Pop_SeqStack(PSeqStack S ,DataType *x)
{ /*删除栈顶元素并保存在*x， 入口参数：顺序栈，返回值：1表示出栈成功，0表示失败。*/
if (Empty_SeqStack ( S ) )
return 0; /*栈空不能出栈 */
else
{
*x= S->data[S->top];
S->top--;
return 1;
}
}
void Destroy_SeqStack(PSeqStack *S)
{
if(*S)
free(*S);
*S=NULL;
return;
}
/*利用栈的非递归算法*/
int mazepath(int maze [ ][n+2] ,item move[ ],int x0,int y0)
{ /*求迷宫路径, 入口参数：指向迷宫数组的指针，下标移动的增量数组，开始点（x0，y0），到达点（m ，n ）, 返回值：1表示求出路径，0表示无路径*/
PSeqStack S ;
DataType temp ;
int x, y, d, i, j ;
temp.x=x0 ;temp.y=y0 ; temp.d=-1 ;
S=Init_SeqStack(); /*初始化栈*/
if (!S)
{ printf("栈初始化失败");
return(0);
}
Push_SeqStack (S,temp) ; /* 迷宫入口点入栈 */
while (! Empty_SeqStack (S ) )
{
Pop_SeqStack(S,&temp);
x=temp.x ; y=temp.y ; d=temp.d+1 ;
while (d
{
i=x+move[d].x ; j=y+move[d].y ;
if( maze[i][j]==0 ) /*此方向可走*/
{
temp.x=x;temp.y=y; temp.d=d;
Push_SeqStack ( S, temp ) ;/*点{x,y}可以走，用栈保存可以走的路径*/ x=i; y=j; maze[x][y]= -1;
if (x==m&&y==n) /*迷宫有路*/
{
while( !Empty_SeqStack(S) )
{
Pop_SeqStack (S,&temp) ;
printf("(%d,%d)
Destroy_SeqStack(&S); /*销毁栈*/
return 1 ;
}
else d=0 ;/*方向复位，从第一个方向开始试探*/
}
else d++ ;/*试探下一个方向*/
} /*while (d
} /*while */
Destroy_SeqStack(&S); /*销毁栈*/
return 0 ;/*迷宫无路*/
}
/*递归算法*/
int mazepath1(int maze[][n+2],item move[],int x,int y)
{/*求迷宫路径，入口参数：迷宫数组，下标移动的增量数组，开始点（x ，y ）， 以及开始点对应的步数step ，（m,n ）是终点，返回值：1表示求出路径，0表示无路径*/
int i;
int step=0;
step++;
maze[x][y]=step;
if(x==m&&y==n)
return 1; /*起始位置是出口，找到路径，结束*/ for(i=0;i
{
if(maze[x+move[i].x][y+move[i].y]==0)
if(mazepath(maze,move,x+move[i].x,y+move[i].y))
return 1; /*下一个是出口，则返回*/ }
step--;
maze[x][y]=0;
return 0;
}
int main()
{ int i,j,k;
char u;
int x,y;
printf("*****欢迎进入迷宫游戏*****\n");
printf("~~~~~~~~游戏快乐~~~~~~~~~\n");
printf(" 这是6*8的迷宫\n");
printf("****************************\n");
for(i=0;i
{ printf("****");
for(j=0;j
{
printf("%-2d",maze[i][j]);
}
printf("****");
printf("\n");
}
printf("****************************\n");
printf("现在开始游戏？（y/n）:");
scanf("%c",&u);
while(u!='n')
{
printf("请输入迷宫入口坐标(x,y)：");
scanf("%d,%d",&x,&y);
printf("出口：(6,8)
k=mazepath(maze,move,x,y);
printf("：入口\n");
if(k==1)printf("恭喜！走出迷宫\n\n");
else printf("抱歉，迷宫无路\n\n");
printf("继续游戏:");
scanf("%c",&u); printf("\n"); }
return 0; }
数据结构课程设计
设计题目： 迷宫问题
学 院： 信息技术学院
专 业： 网络工程
班 级： B1204
学 号： 0913120419
姓 名： 葛晨阳
指导老师： 戴玉洁
课程设计日期： 2013年 7月 20日— 2013年 8月日 1
实验题目
一、问题描述
输入一个任意大小的迷宫数据，用递归和非递归两种方法求出一条走出迷宫的路径，并将路径输出。
二、实现目标
综合运用递归、栈等数据结构知识，掌握、提高分析、设计、实现及测试程序的综合能力
三、主要功能模块及实现功能
（创建一顺序栈：
PSeqStack Init_SeqStack(void)
判断栈是否为空：
int Empty_SeqStack(PSeqStack S)
在栈顶插入一新元素x ：
int Push_SeqStack (PSeqStack S, DataType x)
删除栈顶元素并保存在*x ：
int Pop_SeqStack(PSeqStack S ,DataType *x)
销毁栈 ：
void Destroy_SeqStack(PSeqStack *S)
利用栈的非递归算法求迷宫路径：
int mazepath(int maze [ ][n+2] ,item move[ ],int x0,int y0)
递归算法求迷宫路径：
int mazepath1(int maze[][n+2],item move[],int x,int y)
主函数：
int main()
{ 出口坐标已定，
利用while 循环多次输入入点坐标，
调用mazepath(int maze [ ][n+2] ,item move[ ],int x0,int y0)
输出可走的路径
}
四、主要模块流程图
五、实验结果及测试数据
初始界面
游戏界面
游戏界面
附录:源代码
#include
#include
#define m 6
#define n 8
#define MAXSIZE 100
int maze[m+2][n+2]={
{1,1,1,1,1,1,1,1,1,1},//四周为1代表围墙,0为可走路径
{1,0,0,1,1,0,0,0,1,1},
{1,0,0,0,0,1,1,1,1,1},
{1,0,1,0,0,0,0,0,1,1},
{1,0,1,1,1,0,0,1,1,1},
{1,1,0,0,1,1,0,0,0,1},
{1,0,1,0,0,0,1,1,0,1},
{1,1,1,1,1,1,1,1,1,1}
}; //入口坐标为（1，1），出口坐标为（6，8）
typedef struct
{
int x,y;/*试探方向*/
}item;
item move[4]={{0,1},{1,0},{0,-1},{-1,0}};
typedef struct/*栈的设计*/
{
int x,y,d; /*纵横坐标及方向*/
}DataType;
typedef struct/*栈*/
{
DataType data[MAXSIZE];
int top;
}SeqStack,*PSeqStack;
PSeqStack Init_SeqStack(void)
{ /*创建一顺序栈，入口参数无，返回一个指向顺序栈的指针，为零表示分配空间失败*/
PSeqStack S;
S=(PSeqStack)malloc(sizeof(SeqStack));
if (S)
S->top= -1;
return S;
}
int Empty_SeqStack(PSeqStack S)
{ /*判断栈是否为空，入口参数：顺序栈，返回值：1表示为空，0表示非空*/ if (S->top== -1)
return 1;
else
return 0;
}
int Push_SeqStack (PSeqStack S, DataType x)
{ /*在栈顶插入一新元素x ， 入口参数：顺序栈，返回值：1表示入栈成功，0表示失败。*/
if (S->top==MAXSIZE-1)
return 0; /*栈满不能入栈*/
else
{
S->top++;
S->data[S->top]=x;
return 1;
}
}
int Pop_SeqStack(PSeqStack S ,DataType *x)
{ /*删除栈顶元素并保存在*x， 入口参数：顺序栈，返回值：1表示出栈成功，0表示失败。*/
if (Empty_SeqStack ( S ) )
return 0; /*栈空不能出栈 */
else
{
*x= S->data[S->top];
S->top--;
return 1;
}
}
void Destroy_SeqStack(PSeqStack *S)
{
if(*S)
free(*S);
*S=NULL;
return;
}
/*利用栈的非递归算法*/
int mazepath(int maze [ ][n+2] ,item move[ ],int x0,int y0)
{ /*求迷宫路径, 入口参数：指向迷宫数组的指针，下标移动的增量数组，开始点（x0，y0），到达点（m ，n ）, 返回值：1表示求出路径，0表示无路径*/
PSeqStack S ;
DataType temp ;
int x, y, d, i, j ;
temp.x=x0 ;temp.y=y0 ; temp.d=-1 ;
S=Init_SeqStack(); /*初始化栈*/
if (!S)
{ printf("栈初始化失败");
return(0);
}
Push_SeqStack (S,temp) ; /* 迷宫入口点入栈 */
while (! Empty_SeqStack (S ) )
{
Pop_SeqStack(S,&temp);
x=temp.x ; y=temp.y ; d=temp.d+1 ;
while (d
{
i=x+move[d].x ; j=y+move[d].y ;
if( maze[i][j]==0 ) /*此方向可走*/
{
temp.x=x;temp.y=y; temp.d=d;
Push_SeqStack ( S, temp ) ;/*点{x,y}可以走，用栈保存可以走的路径*/ x=i; y=j; maze[x][y]= -1;
if (x==m&&y==n) /*迷宫有路*/
{
while( !Empty_SeqStack(S) )
{
Pop_SeqStack (S,&temp) ;
printf("(%d,%d)
Destroy_SeqStack(&S); /*销毁栈*/
return 1 ;
}
else d=0 ;/*方向复位，从第一个方向开始试探*/
}
else d++ ;/*试探下一个方向*/
} /*while (d
} /*while */
Destroy_SeqStack(&S); /*销毁栈*/
return 0 ;/*迷宫无路*/
}
/*递归算法*/
int mazepath1(int maze[][n+2],item move[],int x,int y)
{/*求迷宫路径，入口参数：迷宫数组，下标移动的增量数组，开始点（x ，y ）， 以及开始点对应的步数step ，（m,n ）是终点，返回值：1表示求出路径，0表示无路径*/
int i;
int step=0;
step++;
maze[x][y]=step;
if(x==m&&y==n)
return 1; /*起始位置是出口，找到路径，结束*/ for(i=0;i
{
if(maze[x+move[i].x][y+move[i].y]==0)
if(mazepath(maze,move,x+move[i].x,y+move[i].y))
return 1; /*下一个是出口，则返回*/ }
step--;
maze[x][y]=0;
return 0;
}
int main()
{ int i,j,k;
char u;
int x,y;
printf("*****欢迎进入迷宫游戏*****\n");
printf("~~~~~~~~游戏快乐~~~~~~~~~\n");
printf(" 这是6*8的迷宫\n");
printf("****************************\n");
for(i=0;i
{ printf("****");
for(j=0;j
{
printf("%-2d",maze[i][j]);
}
printf("****");
printf("\n");
}
printf("****************************\n");
printf("现在开始游戏？（y/n）:");
scanf("%c",&u);
while(u!='n')
{
printf("请输入迷宫入口坐标(x,y)：");
scanf("%d,%d",&x,&y);
printf("出口：(6,8)
k=mazepath(maze,move,x,y);
printf("：入口\n");
if(k==1)printf("恭喜！走出迷宫\n\n");
else printf("抱歉，迷宫无路\n\n");
printf("继续游戏:");
scanf("%c",&u); printf("\n"); }
return 0; }