#include?
#include?
#define?M?8
#define?N?11
typedef?struct{
	int?xyd;
}DataType;//堆棧數據域
struct?SeqStack
{
?int?MAXNUM;//棧的最大長度
?int?t;//棧頂指針
?DataType?*s;//基指針
?};
typedef?struct?SeqStack?*PSeqStack;
int?isEmptyStack_seq（PSeqStack?pastack）//判斷棧是否為空
{
	return（pastack->t==-1）;//t為棧頂
}
PSeqStack?creatEmptyStack_seq（int?m）//建立空棧
{
????PSeqStack?pastack?=?（PSeqStack）malloc（sizeof（struct?SeqStack））;
	//開辟SeqStack的長度的地址空間，并返回這段空間的首地址
??	if?（pastack!=NULL）{
?????pastack->s?=?（DataType*）malloc（sizeof（DataType）*m）;//如果不為空，開辟m長度空間給*S
?	?if?（pastack->s）{
???????pastack->MAXNUM=m;
???????pastack?->t?=?-1;
???????return?（pastack）;
??????}//開辟成功，則MAXNUM等于m，棧頂元素為空
???	else?free?（pastack）;
????}
????printf（“Out?of?space!!\n“）;
????return?NULL;
}
void??push_seq（?PSeqStack?pastack?DataType?x?）
/*?在棧中壓入一元素x?*/
{??if（?pastack->t?>=?pastack->MAXNUM?-?1??）
??????printf（?“Overflow!?\n“?）;
??else
	{??pastack->t?=?pastack->t?+?1;//棧頂長度增1
	???pastack->s[pastack->t]?=?x;
	?}
}

void??pop_seq（?PSeqStack?pastack?）
/*?刪除棧頂元素?*/
{??	if?（pastack->t?==?-1?）
	printf（?“Underflow!\n“?）;
????else
	pastack->t?=?pastack->t?-?1;
	}
DataType??top_seq（?PSeqStack?pastack?）
/*?當pastack所指的棧不為空棧時，求棧頂元素的值?*/
{?	if?（pastack->t?==?-1?）
	printf（?“It?is?empty!\n“?）;
????else
????return?（pastack->s[pastack->t]）;
}

void?mazePath（int?*maze[]int?*direction[]int?x1int?y1int?x2int?y2）
/*?迷宮maze[M][N]中求從入口maze[x1][y1]到出口maze[x2][y2]的一條路徑?*/
/*?其中?1<=x1x2<=M-2??1<=y1y2<=N-2?*/
{?int?ijk;?
int?gh;
PSeqStack??st;
DataType?element;
st=creatEmptyStack_seq（M*N）;
maze[x1][y1]?=?2;??							/*?從入口開始進入作標記?*/
element.x?=?x1;	??
element.y?=?y1;
element.d?=?-1;
push_seq（stelement）;???						/*?入口點進棧?*/
while?（!?isEmptyStack_seq（st））???				/*?走不通時一步步回退?*/
{
	element?=?top_seq（st）;
????pop_seq（st）;
????i?=?element.x;
????j?=?element.y;
????k?=?element.d?+?1;
????while?（k<=3）??							/*?依次試探每個方向?*/
	{?
		g?=?i?+?direction[k][0];
????????h?=?j?+?direction[k][1];
????????if?（g==x2?&&?h==y2?&&?maze[g][h]==0）??	/*?走到出口點?*/
		{?element.x?=?i;	??
	??????element.y?=?j;
??????????element.d?=?k;
		??push_seq（stelement）;
		??element.x?=?g;	??
	??????element.y?=?h;
??????????element.d?=?k;
??????????push_seq（stelement）;
		??printf（“The?revers?path?is:\n“）;???			/*?打印路徑上的每一點?*/
????????????while（!isEmptyStack_seq（st））
			{
??????????????element=top_seq（st）;
??????????????pop_seq（st）;
?????????????printf（“the?node?is:?%d?%d?\n“element.xelement.y）;
			}
????????????return;
		}
????????if?（maze[g][h]==0）?					/*?走到沒走過的點?*/
		{?maze[g][h]?=?2;???					/*?作標記?*/
??????????element.x?=?i;	??
	??????element.y?=?j;
??????????element.d?=?k;
??????????push_seq（stelement）;??				/*?進棧?*/
??????????i?=?g;?????							/*?下一點轉換成當前點?*/
??????????j?=?h;
??????????k?=?-1;
		}	???
??????k?=?k?+?1;
	}
}
printf（“The?path?has?not?been?found.\n“）;?	/*?棧退完未找到路徑?*/
}
void?main（）
{
	int?maze[M][N]={
	

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2014-03-25?21:15??數據結構_迷宮問題\
?????文件???????84992??2014-03-25?21:15??數據結構_迷宮問題\課程設計報告.doc
?????目錄???????????0??2014-03-25?21:14??數據結構_迷宮問題\迷宮問題\
?????目錄???????????0??2014-03-25?21:14??數據結構_迷宮問題\迷宮問題\Debug\
?????文件???????50176??2011-06-21?21:14??數據結構_迷宮問題\迷宮問題\Debug\vc60.idb
?????文件???????53248??2010-07-05?16:03??數據結構_迷宮問題\迷宮問題\Debug\vc60.pdb
?????文件??????176217??2010-07-05?16:05??數據結構_迷宮問題\迷宮問題\Debug\迷宮問題.exe
?????文件??????176636??2010-07-05?16:05??數據結構_迷宮問題\迷宮問題\Debug\迷宮問題.ilk
?????文件????????9545??2010-07-05?16:05??數據結構_迷宮問題\迷宮問題\Debug\迷宮問題.obj
?????文件??????220224??2010-07-05?10:42??數據結構_迷宮問題\迷宮問題\Debug\迷宮問題.pch
?????文件??????427008??2010-07-05?16:03??數據結構_迷宮問題\迷宮問題\Debug\迷宮問題.pdb
?????文件????????3662??2010-07-05?16:03??數據結構_迷宮問題\迷宮問題\迷宮問題.cpp
?????文件????????3427??2010-07-05?14:58??數據結構_迷宮問題\迷宮問題\迷宮問題.dsp
?????文件?????????524??2010-07-05?16:09??數據結構_迷宮問題\迷宮問題\迷宮問題.dsw
?????文件???????58368??2011-06-21?21:14??數據結構_迷宮問題\迷宮問題\迷宮問題.ncb
?????文件???????48640??2011-06-21?21:14??數據結構_迷宮問題\迷宮問題\迷宮問題.opt
?????文件?????????762??2010-07-05?16:05??數據結構_迷宮問題\迷宮問題\迷宮問題.plg