#include #define ROW 11
#define COLUMN 15
typedef struct
{ /*栈中的数据元素的类型定义*/
int row; /*行下标*/
int col; /*列下标*/
int direction; /*下一步移动方向*/
} DATA;
Typedif struct node
{ /* 栈类定义*/
DATA data;
Struct node *next;
}LinkStack;
Typedef struct
{/*移动方向的坐标偏移值*/
int x_offset;
int y_offset;
}DIRECTIONS;
DIRECTIONS dir[8]={{-1,0},{-1,1},{0,1},{1,1},(1,0),{1,-1},{0,-1},{-1,-1}};
Int maze[ROW+2][COLUMN+2]=
{
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{1,0,1,0,0,0,1,1,0,0,0,1,1,1,1,1,1},
{1,1,0,0,0,1,1,0,1,1,1,0,0,1,1,1,1},
{1,0,1,1,0,0,0,0,1,1,1,1,0,0,1,1,1},
{1,1,1,0,1,1,1,1,0,1,1,0,1,1,0,0,1},
{1,1,1,0,1,0,0,1,0,1,1,1,1,1,1,1,1},
{1,0,0,1,1,0,1,1,1,0,1,0,0,1,0,1,1},
{1,1,1,0,1,1,0,0,1,1,1,1,1,1,1,1,1},
{1,0,0,1,1,0,1,1,0,1,1,1,1,1,0,1,1},
{1,1,1,0,0,0,1,1,0,1,1,0,0,0,0,0,1}，
{1,0,0,1,1,1,1,1,0,0,0,1,1,1,1,0,1},
{1,0,1,0,0,1,1,1,1,1,0,1,1,1,1,0,1},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
}; /*迷宫数组*/
Void InitLinkStack(LinkStack **top)
{ /* 初始化栈，将栈置空*/
*top=(LinkStack *)malloc(sizeof(LinkStack));
(*top)->next=NULL;
}
Bool IsEmpty(LinkStack *top)
{ /*判断栈 是否为空，如果栈空，返回true,否则返回false*/
If(top->next==NULL) return true;
Else return false;
}
Void Push(LinkStack *top,DATA x)
{ /*将元素x压入到栈S中，先申请结点再将其入栈*/
LinkStack*S；
S=(LinkStack *)nalloc(sizeof(Linkstack));
S->data=x; S->next=top->next;top->next=S;
}
DATA Pop(LinkStack *top)
{ /* 将栈S中的栈顶元素出栈*/
LinkStack *S;
DATA data;
If(!IsEmpty(top))
{ /* 如果栈非空，则返回栈顶元素*/
S=top->next; top->next=S->next;
data=S->data; free(S);
return data;
}
}
viod main()
{
LinkStack *S;
DATA d,temp;
int i;
InitLinkStack(&S); /*初始化栈*/
d.col=d.row=1; d direction=0;
Push(S,d); /*将迷宫入口处入栈*/
while(!EsEmpty(S))
{
/*老鼠的当前位置保存在temp中 */
temp=Plp(S);i=temp.direction;
while(i<8)
{
/*生成下一个老鼠位置*/
d.row=temp.row+dir[i].x_offset;
d.col=temp.col+dir[i].y_offset;
d.direction=0;
if(d.row==11&&d.col==15)
{ /*已找到出口*/
print(“[%d,%d]”,d.row,d.col);
while(!IsEmpty(S))
{
d=Pop(S);
printf(“[%d,%d]”,d.row,d.col);
}
free(S);exit(0);
}
else if(maze[d.row][d.col]==0)
{ /*得到下一个可移动位置*/
maze[d.row][d.col]=-1;Push(S,d);
i=d.direction; temp=d;
}
else i++;
}
}
}
3、上机调试、运行程序。
六、 实验报告要求
画出源程序流程图。
7
