#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
)？)
