迷宮問題代碼.doc

#define OVERFLOW -2#define ERROR 0#define NULL 0#define true 1#define TRUE 1#define false 0#define FALSE 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#include #include /*初始化迷宮,1表示通道,0表示墻*/int maze88 = 1,1,0,1,1,1,0,1, 1,1,0,1,1,1,0,1, 1,1,1,1,0,0,1,1, 1,0,0,0,1,1,1,1, 1,1,1,0,1,1,1,1, 1,0,1,1,1,0,1,1, 1,0,0,0,1,0,0,1, 0,1,1,1,1,1,1,1;/定義棧元素類型 typedef struct MStackElem int x;/x坐標 int y;/y坐標 int val;/mazexy的值MStackElem;/定義棧typedef struct MStackElem * base; MStackElem * top; int stackSize;MStack;/=Stack的實現(xiàn)=/初始化棧-構(gòu)造一個空棧void initStack(MStack *s) s-base = (MStackElem *)malloc(STACK_INIT_SIZE * sizeof(MStackElem); if (!s-base) printf(in initStack().Failed to initalize the MStack ,no enough space! exit now. ); exit(OVERFLOW);/存儲分配失敗 s-top = s-base; s-stackSize = STACK_INIT_SIZE;/向棧中添加元素void push(MStack *s,MStackElem e) /向棧中添加元素前先判斷棧是否還有空間容納新元素 if (s-top - s-base = s-stackSize) /棧滿,追加元素 s-base = (MStackElem *)realloc(s-base, (STACK_INIT_SIZE+STACKINCREMENT) * sizeof(MStackElem); if (!s-base) printf(in push().Failed to realloc the MStack ,no enough space! exit now. ); exit(OVERFLOW);/存儲分配失敗 s-top = s-base + s-stackSize; /因為是重新分配了空間,所以base的值其實已經(jīng)改變,所以top的值也就相應的改變,才能指向新的迷宮棧 s-stackSize += STACKINCREMENT; /將新元素加到棧頂 *(s-top+) = e;/獲得棧頂元素MStackElem getTop(MStack *s) if (s-top = s-base) printf(in getTop(),empty stack! exit now. ); exit(ERROR);else return *(s-top - 1);/刪除棧頂元素void pop(MStack *s) /若棧不為空,則刪除s的棧頂元素 if (s-top = s-base) printf(in pop(),empty stack! exit now. ); exit(ERROR); else -(s-top); /=求解迷宮的相關(guān)操作=/構(gòu)造兩個棧,一個用來保存探索中的全部路徑,一個用來保存有效路徑MStack realPath,path;/判斷當前位置是否走過int unPass(MStack path,MStackElem cur) /這里不能傳path的地址,否則在遍歷過程中它的top值就真的被改了 ! int flag = 1; while(path.top != path.base) MStackElem e = *(path.top - 1); if (e.x = cur.x& e.y = cur.y) flag = 0; /每循環(huán)一次令頭指針下移一個位置 (path.top)-; return flag;/獲得東面相鄰的位置MStackElem getEast(MStackElem cur) if(cur.y != 7) /當y=7時已到了迷宮右邊界,不能再向東(右)行了 cur.y += 1; cur.val = mazecur.xcur.y; return cur;/ 當y=7時返回的是它本身 /獲得南面相鄰的位置MStackElem getSouth(MStackElem cur) if(cur.x != 7) /當x=7時已到了迷宮下邊界,不能再向南(下)行了 cur.x += 1; cur.val = mazecur.xcur.y; return cur;/ 當x=7時返回的是它本身 /獲得西面相鄰的位置MStackElem getWest(MStackElem cur) if(cur.y != 0) /當y=0時已到了迷宮左邊界,不能再向西(左)行了 cur.y -= 1; cur.val = mazecur.xcur.y; return cur;/ 當y=0時返回的是它本身 /獲得北面相鄰的位置MStackElem getNorth(MStackElem cur) if(cur.x != 0) /當cur.x=0時表示在迷宮的上邊界,不能再向北(上)行了 cur.x -= 1; cur.val = mazecur.xcur.y; return cur;/ 當cur.x=0時返回的還是它本身 /獲得下一個可通行的位置,按東南西北的方向試探MStackElem getNext(MStackElem cur) MStackElem next;next.x = next.y=next.val = -1;if(getEast(cur).val != 0 & unPass(path,getEast(cur) next = getEast(cur);else if(getSouth(cur).val != 0 & unPass(path,getSouth(cur) next = getSouth(cur);else if(getWest(cur).val != 0 & unPass(path,getWest(cur) next = getWest(cur);else if(getNorth(cur).val != 0 & unPass(path,getNorth(cur) next = getNorth(cur);/如果當前位置的四面或為墻或已走過,則返回的next的val值為-1 return next;int getMazePath()/獲得迷宮路徑的函數(shù) MStackElem start,end,cur; start.x = 0; start.y = 0; start.val = mazestart.xstart.y; end.x = 7; end.y = 7; end.val = mazeend.xend.y; cur = start; /設定當前為位置為入口位置 /沒有重載=運算符,可以這樣用嗎,結(jié)果對嗎?試試吧: /* printf(%d,cur.x); printf(%d,cur.y); printf(%d,cur.val); */ do if (unPass(path,cur) /如果當前位置未曾走到過 push(&realPath,cur); push(&path,cur); cur = getNext(cur); if (cur.x = end.x & cur.y = end.y) /到達出口了,則跳出循環(huán),并返回true /把出口結(jié)點放入路徑中 push(&realPath,cur); push(&path,cur); /直接跳出函數(shù)(而不只是跳出這個循環(huán) ) return true; else if(cur.val = -1) /當前位置的四面或為墻或已走過 /刪除真實路徑的棧頂元素 pop(&realPath); cur = getTop(&realPath);/令cur指向棧頂元素 else /如果當前位置已經(jīng)走過,說明原來測試的方向不對,現(xiàn)在嘗試其它方向 cur = getNext(cur); if (cur.val = -1) /仍不通,刪除真實路徑的棧頂元素 pop(&realPath); cur = getTop(&realPath);/令cur指向棧頂元素 while (cur.x != end.x | cur.y != end.y);/打印迷宮路徑void printMazePath(MStack *s) /為了安全,這里不傳MStack的地址,以防在遍歷的過程中把它們的top或base的值也修改了 /*注:這種方法實際是倒序打印出路徑,讓人看著別扭,所以我用下面的方法倒序遍歷這個棧 while (s-top != s-base) MStackElem e = *(s-top-1); printf(maze%d%d-,e.x,e.y); (s-top)-; */ MStackElem e; while (s-base top-1) e = *(s-base);/先指向棧底元素,以后依次向上增1 printf(maze%d%d-,e.x,e.y); (s-base)