《数据结构与算法》实验报告
评分依据及结果
一、 需求分析
1.问题描述：
以一个m*n的长方阵表示迷宫，空格和感叹号分别表示迷宫中的通路和障碍。设计一个程序，对随机产生的迷宫，求一条从入口到出口的通路，或得出没有通路的结论。
2.基本要求
首先实现一个以链表为存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出。
其中（i，j）表示迷宫的一个坐标，d表示走到下一座标的方向。
3.程序的执行命令有：
1）输入迷宫的列数 2）输入迷宫的行数
二、 概要设计
为实现上述功能，需要以一个链表为存储结构的栈类型
1. 栈的顺序存储表示
typedef struct
{
int x; /*列*/
int y; /*行*/
}PosType; //坐标位置类型
typedef struct
{
int ord; //通道块在路径上的"序号"
PosType seat; //通道块在迷宫中的"坐标位置"
int di; //从此通道块走向下一通道块的"方向"
}SElemType; //栈的元素类型
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize; //当前已分配的存储空间，以元素为单位
}
SqStack;
//迷宫程序
typedef struct
{
int lie; /*列数*/
int hang; /*行数*/
char a[999][999];
}
MazeType; /*迷宫类型*/
2. 基本操作
int InitStack(SqStack *S)//分配空间
int GetTop(SqStack *S,SElemType *e) //若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
int Push(SqStack *S,SElemType *e)//插入元素e作为新的栈顶元素
int Pop(SqStack *S,SElemType *e) //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
int generatemaze( MazeType *maze)// 随机生成迷宫
int Pass(MazeType *maze, PosType curpos ) //判断当前位置可否通过
int FootPrint(MazeType *maze,PosType curpos) //留下足迹
int MarkPrint(MazeType *maze,PosType curpos) //留下不能通过的标记
PosType NextPos(PosType curpos,int di) //返回当前位置的下一位置
int MazePath(MazeType *maze,PosType start,PosType end) //若迷宫有解，则求得一条存放在栈中（从栈底到栈顶），并返回OK，否则返回ERROR
void PrintMaze(MazeType *maze) //打印迷宫
三、 详细设计
//程序的头文件
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
//函数的返回值
#define OK 1
#define ERROR 0
#define NULL 0
#define OVERFLOW -2
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
//栈的顺序存储表示
typedef struct
{
int x; /*列*/
int y; /*行*/
}PosType; //坐标位置类型
typedef struct
{
int ord; //通道块在路径上的"序号"
PosType seat; //通道块在迷宫中的"坐标位置"
int di; //从此通道块走向下一通道块的"方向"
}SElemType; //栈的元素类型
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize; //当前已分配的存储空间，以元素为单位
}
SqStack;
//基本操作
int InitStack(SqStack *S)
{
S->base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if(!S->base)
exit(OVERFLOW);
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
return OK;
}
//若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
int GetTop(SqStack *S,SElemType *e)
{
if(S->top==S->base)
return ERROR;
*e=*(S->top-1);
return OK;
}
int Push(SqStack *S,SElemType *e)//插入元素e作为新的栈顶元素
{
if(S->top-S->base>=S->stacksize)/*栈满，追加存储空间*/
{
S->base=(SElemType*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S->base)
exit(OVERFLOW);
S->top=S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}
*S->top++=*e;
return OK;
}
//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
int Pop(SqStack *S,SElemType *e)
{
if(S->top==S->base)
return ERROR;
*e=*--S->top;
return OK;
}
int StackEmpty(SqStack *S)
{
return(S->top==S->base)
;}
//迷宫程序
typedef struct
{
int lie; /*列数*/
int hang; /*行数*/
char a[999][999];
}
MazeType; /*迷宫类型*/
/*随机生成迷宫*/
int generatemaze( MazeType *maze)
{
int i,j;
maze->a[0][0]=2;
maze->a[++maze->hang][++maze->lie]=3; /*设置外墙*/
maze->a[0][maze->lie]='!';
maze->a[maze->hang][0]='!';
for(j=1;j<maze->lie;j++)
{
maze->a[0][j]='!';
maze->a[maze->hang][j]='!';
}
for(i=1;i<maze->hang;i++)
{
maze->a[i][0]='!';
maze->a[i][maze->lie]='!';
}
srand((unsigned)time( NULL ));
rand();
for(i=1; i <maze->hang; i++)
for(j=1;j<maze->lie;j++)
{
if (rand()>=RAND_MAX/4) maze->a[i][j] =' '; //' ' 暗示出路
else maze->a[i][j] ='!'; //'!'暗示无出路
}
return OK;
}
int Pass(MazeType *maze, PosType curpos ) //判断当前位置可否通过
{
if ((curpos.x < 1) || (curpos.x >= maze->lie))
return ERROR;
if ((curpos.y < 1) || (curpos.y >= maze->hang))
return ERROR;
if (maze->a[curpos.y][curpos.x]==' ')
return OK;
else return ERROR;
}
int FootPrint(MazeType *maze,PosType curpos) //留下足迹
{
maze->a[curpos.y][curpos.x]='*';
return OK;
}
int MarkPrint(MazeType *maze,PosType curpos) //留下不能通过的标记
{
maze->a[curpos.y][curpos.x]='@';
return OK;
}
PosType NextPos(PosType curpos,int di)
//返回当前位置的下一位置
{
PosType pos=curpos;
switch(di)
{
case 1: //右东
pos.x++;
break;
case 2: //下南
pos.y++;
break;
case 3: //左西
pos.x--;
break;
case 4: //上北
pos.y--;
break;
}
return pos;
}
//若迷宫有解，则求得一条存放在栈中（从栈底到栈顶），并返回OK，否则返回ERROR
int MazePath(MazeType *maze,PosType start,PosType end)
{
PosType curpos;
SqStack *S=(SqStack *)malloc(sizeof(SqStack));
InitStack(S);
SElemType *e;
e=(SElemType *)malloc(sizeof(SElemType));
curpos=start; //设定当前位置为入口位置
int curstep = 1; //探索第一步
do {
if(Pass(maze,curpos)) //当前位置可通过
{
FootPrint(maze,curpos);
e->ord=curstep;
e->seat=curpos;
e->di=1;
Push(S,e);
if(curpos.x==end.x&&curpos.y==end.y)
return (OK);
curpos=NextPos(curpos,1);
curstep++;
}
else
{
if(!StackEmpty(S))
{
Pop(S,e);
while(e->di==4&&!StackEmpty(S)) //栈不空但栈顶位置四周均不通
{
MarkPrint(maze,e->seat);
Pop(S,e);
}
if(e->di<4) //栈不空且栈顶位置四周有其他位置未探索
{
e->di++;
Push(S,e);
curpos=e->seat;
curpos=NextPos(curpos,e->di);
}
}
}
}
while(!StackEmpty(S));
return ERROR;
}
void PrintMaze(MazeType *maze) //打印迷宫
{
int i,j,k,n;
int c[999],d[999];
for(i=0,k=0;i<=maze->hang;i++)
{
for(j=0;j<=maze->lie;j++)
{
printf("%c ",maze->a[i][j]);
if(maze->a[i][j]=='*')
{
c[k]=i;
d[k]=j;
k++;
}
}
printf("\n");
}
n=k;
for(k=0;k<n;k++)
printf("<%d,%d>",c[k],d[k]);
printf("\n");
printf("\n");
}
int main()
{
int zmg;
char ch;
printf(" 数据结构课程设计--迷宫问题求解 \n\n");
printf(" |----------------------------------------|\n");
printf(" | |\n");
printf(" | |\n");
printf(" | |\n");
printf(" | |\n");
printf(" | XXXX XXXXXXXXXXXXXX |\n");
printf(" | XXXXXXX |\n");
printf(" |----------------------------------------|\n");
getchar();
do
{
system("cls");
fflush(stdin);
MazeType *maze=(MazeType *)malloc(sizeof(MazeType)); //设置迷宫的长宽不含外墙
printf("请输入迷宫的列数（不含外墙时）:");
scanf("%d",&maze->lie);
printf("请输入迷宫的行数（不含外墙时）:");
scanf("%d",&maze->hang);
generatemaze(maze);
printf("随机创建迷宫\n");
PrintMaze(maze);
getchar();
getchar();
PosType start,end;
start.x=1;start.y=1;
end.x=maze->lie-1;end.y=maze->hang-1;
zmg=MazePath(maze,start,end);
if(zmg)
{
printf("此迷宫通路为\n");
PrintMaze(maze);
}
else
printf("此迷宫无通路\n"); //getchar();
printf("再次尝试？（Y/N）?");
scanf("%c",&ch);
}
while(ch=='Y'||ch=='y');
return 0;
}
四、 调试分析
1. 本程序界面设计合理，以空格为通路，感叹号！为障碍 ，笑脸为起始点，*为行走路线，心形为出口
设计精巧，便于用户使用。
2. 获得用户输入时一步一步的提示用户输入，具有很强的实用性。
3. 本实习作业采用数据抽象的程序设计方法，使得设计思路清晰，实现时调试顺利。
五、 用户守则
1.本程序的运行环境为windows操作系统，可执行文件为：a.exe
2.为了界面更加友好特将背景颜色设计为黑色，字体为白色。
3.进入演示程序后即显示文本形式的用户界面：
按回车键，即可进行迷宫求解
六、 测试结果
七、 附录（源代码）
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define OK 1
#define ERROR 0
#define NULL 0
#define OVERFLOW -2
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
//栈的顺序存储表示
typedef struct
{
int x; /*列*/
int y; /*行*/
}PosType; //坐标位置类型
typedef struct
{
int ord; //通道块在路径上的"序号"
PosType seat; //通道块在迷宫中的"坐标位置"
int di; //从此通道块走向下一通道块的"方向"
}SElemType; //栈的元素类型
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize; //当前已分配的存储空间，以元素为单位
}
SqStack;
//基本操作
int InitStack(SqStack *S)
{
S->base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if(!S->base)
exit(OVERFLOW);
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
return OK;
}
//若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
int GetTop(SqStack *S,SElemType *e)
{
if(S->top==S->base)
return ERROR;
*e=*(S->top-1);
return OK;
}
int Push(SqStack *S,SElemType *e)//插入元素e作为新的栈顶元素
{
if(S->top-S->base>=S->stacksize)/*栈满，追加存储空间*/
{
S->base=(SElemType*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S->base)
exit(OVERFLOW);
S->top=S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}
*S->top++=*e;
return OK;
}
//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
int Pop(SqStack *S,SElemType *e)
{
if(S->top==S->base)
return ERROR;
*e=*--S->top;
return OK;
}
int StackEmpty(SqStack *S)
{
return(S->top==S->base)
;}
//迷宫程序
typedef struct
{
int lie; /*列数*/
int hang; /*行数*/
char a[999][999];
}
MazeType; /*迷宫类型*/
/*随机生成迷宫*/
int generatemaze( MazeType *maze)
{
int i,j;
maze->a[0][0]=2;
maze->a[++maze->hang][++maze->lie]=3; /*设置外墙*/
maze->a[0][maze->lie]='!';
maze->a[maze->hang][0]='!';
for(j=1;j<maze->lie;j++)
{
maze->a[0][j]='!';
maze->a[maze->hang][j]='!';
}
for(i=1;i<maze->hang;i++)
{
maze->a[i][0]='!';
maze->a[i][maze->lie]='!';
}
srand((unsigned)time( NULL ));
rand();
for(i=1; i <maze->hang; i++)
for(j=1;j<maze->lie;j++)
{
if (rand()>=RAND_MAX/4) maze->a[i][j] =' '; //' ' 暗示出路
else maze->a[i][j] ='!'; //'!'暗示无出路
}
return OK;
}
int Pass(MazeType *maze, PosType curpos ) //判断当前位置可否通过
{
if ((curpos.x < 1) || (curpos.x >= maze->lie))
return ERROR;
if ((curpos.y < 1) || (curpos.y >= maze->hang))
return ERROR;
if (maze->a[curpos.y][curpos.x]==' ')
return OK;
else return ERROR;
}
int FootPrint(MazeType *maze,PosType curpos) //留下足迹
{
maze->a[curpos.y][curpos.x]='*';
return OK;
}
int MarkPrint(MazeType *maze,PosType curpos) //留下不能通过的标记
{
maze->a[curpos.y][curpos.x]='@';
return OK;
}
PosType NextPos(PosType curpos,int di)
//返回当前位置的下一位置
{
PosType pos=curpos;
switch(di)
{
case 1: //右东
pos.x++;
break;
case 2: //下南
pos.y++;
break;
case 3: //左西
pos.x--;
break;
case 4: //上北
pos.y--;
break;
}
return pos;
}
//若迷宫有解，则求得一条存放在栈中（从栈底到栈顶），并返回OK，否则返回ERROR
int MazePath(MazeType *maze,PosType start,PosType end)
{
PosType curpos;
SqStack *S=(SqStack *)malloc(sizeof(SqStack));
InitStack(S);
SElemType *e;
e=(SElemType *)malloc(sizeof(SElemType));
curpos=start; //设定当前位置为入口位置
int curstep = 1; //探索第一步
do {
if(Pass(maze,curpos)) //当前位置可通过
{
FootPrint(maze,curpos);
e->ord=curstep;
e->seat=curpos;
e->di=1;
Push(S,e);
if(curpos.x==end.x&&curpos.y==end.y)
return (OK);
curpos=NextPos(curpos,1);
curstep++;
}
else
{
if(!StackEmpty(S))
{
Pop(S,e);
while(e->di==4&&!StackEmpty(S)) //栈不空但栈顶位置四周均不通
{
MarkPrint(maze,e->seat);
Pop(S,e);
}
if(e->di<4) //栈不空且栈顶位置四周有其他位置未探索
{
e->di++;
Push(S,e);
curpos=e->seat;
curpos=NextPos(curpos,e->di);
}
}
}
}
while(!StackEmpty(S));
return ERROR;
}
void PrintMaze(MazeType *maze) //打印迷宫
{
int i,j,k,n;
int c[999],d[999];
for(i=0,k=0;i<=maze->hang;i++)
{
for(j=0;j<=maze->lie;j++)
{
printf("%c ",maze->a[i][j]);
if(maze->a[i][j]=='*')
{
c[k]=i;
d[k]=j;
k++;
}
}
printf("\n");
}
n=k;
for(k=0;k<n;k++)
printf("<%d,%d>",c[k],d[k]);
printf("\n");
printf("\n");
}
int main()
{
int zmg;
char ch;
printf(" 数据结构课程设计--迷宫问题求解 \n\n");
printf(" |----------------------------------------|\n");
printf(" | |\n");
printf(" | |\n");
printf(" | |\n");
printf(" | |\n");
printf(" | XXXX XXXXXXXXXXXXXX |\n");
printf(" | XXXXXXX |\n");
printf(" |----------------------------------------|\n");
getchar();
do
{
system("cls");
fflush(stdin);
MazeType *maze=(MazeType *)malloc(sizeof(MazeType)); //设置迷宫的长宽不含外墙
printf("请输入迷宫的列数（不含外墙时）:");
scanf("%d",&maze->lie);
printf("请输入迷宫的行数（不含外墙时）:");
scanf("%d",&maze->hang);
generatemaze(maze);
printf("随机创建迷宫\n");
PrintMaze(maze);
getchar();
getchar();
PosType start,end;
start.x=1;start.y=1;
end.x=maze->lie-1;end.y=maze->hang-1;
zmg=MazePath(maze,start,end);
if(zmg)
{
printf("此迷宫通路为\n");
PrintMaze(maze);
}
else
printf("此迷宫无通路\n"); //getchar();
printf("再次尝试？（Y/N）?");
scanf("%c",&ch);
}
while(ch=='Y'||ch=='y');
return 0;
}