1、西安郵電大學數據結構課程設計報告題 目： 迷宮問題院系名稱： 計算機學院 專業名稱： 軟件工程班 級： 1101 學生姓名： 武妍娜學號（8位）： 04113027指導教師： 李培 設計起止時間：2012年12月3日2012年12月14日17 / 17文檔可自由編輯打印一. 設計目的1.熟悉C語言程序的編輯、編譯鏈接和運行的過程，能夠熟練地編輯、編譯及調試程序。2.掌握文件和文件指針的概念以及文件的定義方法，學會熟練使用文件打開、關閉、讀、寫 等基本操作。3.熟練掌握結構體、鏈表、指針的使用，及函數間的調用。4.能夠熟練運用所學棧的相關知識及操作，順利完成題目的要求。二. 設計內容迷宮是實驗心

2、理學中一個古典問題。用計算機解迷宮路徑的程序，就是仿照人走迷宮。計算機解迷宮時，通常用的是窮舉求解的方法，即從入口出發，順某一方向向前探索，若能走通，則繼續往前走；否則沿原路退回，換一個方向再繼續探索，直至所有可能的通路都探索到為止。 1.功能與數據需求 迷宮求解問題描述：以一個MN的矩陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設計一個程序，對任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結論。1.1 題目要求的功能 （1）基本要求：首先實現一個以鏈表作存儲結構的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以二元組（i,j）的形式輸出，其中：（i,j）指迷宮中對應的坐

3、標。 （2）測試數據：左上角（1,1）為入口，右下角（9,8）為出口。左上角（1,1）為入口，右上角（1,8）為出口。（3） 如下圖所示： 1.2 擴展功能（1）編寫非遞歸形式的算法，求得迷宮中所有可能的通路；（2）以方陣形式輸出迷宮及其通路2.界面需求（1）在菜單中選擇要執行的操作（2）輸出方陣迷宮（3）用戶自己輸入迷宮起始位置（4）輸出所走的迷宮路徑（5）輸出方陣路徑，并保存到文件中3.開發環境與運行需求Microsoft Visual C+6.0Ubuntu 三概要設計主模塊1功能模塊圖；本程序包含三個模塊（1）主程序模塊：void main（）文件模塊棧模塊迷宮模塊初始化；do接受命令

4、；處理命令；while（命令！=“退出”）；（2）棧模塊實現棧抽象數據類型（3） 迷宮模塊實現迷宮抽象數據類型2 各個模塊詳細的功能描述。（1）菜單：從菜單中選擇要執行的操作（2）文件模塊：實現文件的各項基本操作a）打開文件b）關閉文件c）從文件讀信息d）向文件中寫入內容（3）棧模塊：實現棧的各項基本操作a）初始化棧b）入棧c）出棧d）取棧頂元素(4）迷宮模塊：求解迷宮問題a）顯示迷宮b)獲取迷宮路徑c）判斷當前路徑是否走過d）獲得下一個可走的位置e）獲得東面，南面，西面，北面相鄰的位置4 詳細設計1功能函數的調用關系圖打開源文件輸出迷宮路徑判斷當前路徑是否走過顯示迷宮主函數 入棧 出棧獲得迷

5、宮路徑初始化棧菜單獲得下一個可走的位置顯示迷宮路線保存迷宮路線取棧頂元素開始2.各功能函數的數據流程圖MStackElem start,cur;p2=head;（1） 獲得迷宮路徑函數cur= start; do while (cur.x != chukou0 | cur.y != chukou1)當前位置是否走過Push(&realPath,cur)Push(&path,cur);cur = GetNext(cur);cur=GetNext(cur); 是 否 else ifcur.val=-1Push(&realPath,cur)Push(&path,cur);return 1; ifcu

6、r.x=chukou0&cur.y=chukou1 Pop(&realPath);cur=GetTop(&realPath) 開始(2) 獲得下一個可通行的位置GetEast(cur).val=&UnPass(path,GetEast(cur)GetWest(cur).val=&UnPass(path,GetWest(cur)MStackElem next;next.x=next.y=next.val = -1; if else if GetNorth(cur).val=&UnPass(path,GetNorth(cur)GetSouth(cur).val=&UnPass(path,GetSo

7、uth(cur) else if else ifnext= GetSouth(cur);next= North(cur);next= GetEast(cur);next= GetEast(cur);3.重點設計及編碼獲得迷宮路徑的函數：int GetMazePath() MStackElem start,cur; start.x = rukou0;start.y = rukou1; start.val = Mazerukou0rukou1; cur = start; do if (UnPass(path,cur) Push(&realPath,cur); Push(&path,cur); cu

8、r = GetNext(cur); if (cur.x = chukou0 & cur.y = chukou1) Push(&realPath,cur); Push(&path,cur); return 1; else if(cur.val = -1) Pop(&realPath); cur = GetTop(&realPath); else cur = GetNext(cur); if (cur.val = -1) Pop(&realPath); cur = GetTop(&realPath); while (cur.x != chukou0 | cur.y != chukou1);retu

9、rn 0;五測試數據及運行結果1正常測試數據和運行結果 2.異常測試數據及運行結果 六調試情況，設計技巧及體會1改進方案在迷宮問題中，由于走的方向順序不同，存在著多條路徑的結果。因此就出現了一個最大的問題，哪條路徑最短，即求最短路徑。由于時間有限和難度問題，我沒能及時解決這個問題，這也是在這次的迷宮課程設計中，我唯一的不足之處。不過我并沒有放棄，課程設計結束后，我還會繼續努力，解決掉這個問題。在以后的生活中，我也會不斷督促自己，提高編程能力。2體會剛開始，頭腦里沒有任何思路，不知道如何下手，經過仔細研讀課本和上網查資料后，終于有了思緒。先將整個程序劃分為三個大模塊：主模塊，棧模塊和迷宮模塊。然

10、后再依次實現每個大模塊中的小操作。最后將所有的程序拼接起來，進行調試。我覺得所有模塊中最難編的就是查找迷宮路徑函數，經過苦思冥想，再加上老師和同學的幫助，總算做出來了，但是非常復雜。在編譯的過程中總會出現五花八門的錯誤，比如：從文件里讀不出信息，又或者是存不進去文件，或者是亂碼等。后來才發現原來是源文件中存的信息類型和程序中定義的類型不匹配，經過改正之后果然正確了。改正完后，當把所有的小塊連接在一起時，雖然沒有錯誤，但是總有許多警告語句，運行的結果也不盡人意。通過上網查資料后，發現這都是一些格式問題?？磥砭幊谈袷胶苤匾?！經過兩個星期的上機實踐學習，我才發現我的C語言上機實踐能力還有待加強，有

11、待進步。以后不但要重視課本與習題，更要重視上機實踐。七參考文獻1. 耿國華主編，數據結構C語言描述，高等教育出版社，2005年2. 陳銳，數據結構（C語言版），清華大學出版社 2012年八附錄#include #include #include #define M 11/迷宮行數#define N 10/迷宮列數#define STACK_INIT_SIZE 100#define STACKINCREMENT 10char MazeMN=0;/迷宮char sMN=0;/迷宮路線圖int rukou2,chukou2;/定義棧元素類型typedef struct int x;/x坐標 int

12、y;/y坐標 char val;/Mazexy的值MStackElem;/定義棧typedef struct MStackElem * base; MStackElem * top; int StackSize;MStack; /初始化棧InitStack(MStack *S) S-base = (MStackElem *)malloc(STACK_INIT_SIZE * sizeof(MStackElem); if (!S-base) printf(初始化棧失敗!n); exit(-1);/存儲分配失敗 S-top = S-base; S-StackSize = STACK_INIT_SIZ

13、E;/入棧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(空間不足，入棧失敗!n);exit(-1);/存儲分配失敗 S-top = S-base + S-StackSize; /因為是重新分配了空間,所以base的值其實已經改

14、變,所以top的值也就相應的改變,才能指向新的迷宮棧 S-StackSize += STACKINCREMENT; *(S-top+) = e;/將新元素加到棧頂 /獲得棧頂元素MStackElem GetTop(MStack *S) if (S-top = S-base)printf(n對不起，沒有出路!nn);exit(0);elsereturn *(S-top - 1); /出棧Pop(MStack *S)/若棧不為空,則刪除s的棧頂元素 if (S-top = S-base) printf(棧為空，出棧失敗!n); exit(0); else -(S-top); MStack real

15、Path,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;/曾走過 (path.top)-;/每循環一次令頭指針下移一個位置 return flag; /獲得東面(即右邊)相

16、鄰的位置MStackElem GetEast(MStackElem cur)if(cur.y != N-2)/當y=N-2時已到了迷宮右邊界,不能再向東(右)行了 cur.y += 1; cur.val = Mazecur.xcur.y; return cur;/當y=N-2時返回的是它本身 /獲得南面(即下邊)相鄰的位置MStackElem GetSouth(MStackElem cur)if(cur.x != M-2)/當x=M-2時已到了迷宮下邊界,不能再向南(下)行了 cur.x += 1; cur.val = Mazecur.xcur.y; return cur;/當x=M-2時返回

17、的是它本身/獲得西面(即左邊)相鄰的位置MStackElem GetWest(MStackElem cur)if(cur.y != 1)/當y=1時已到了迷宮左邊界,不能再向西(左)行了 cur.y -= 1; cur.val = Mazecur.xcur.y; return cur;/當y=1時返回的是它本身/獲得北面(即上邊)相鄰的位置MStackElem GetNorth(MStackElem cur) if(cur.x != 1)/當cur.x=1時表示在迷宮的上邊界,不能再向北(上)行了 cur.x -= 1; cur.val = Mazecur.xcur.y; return cur

18、;/當cur.x=1時返回的還是它本身 /獲得下一個可通行的位置,按東南西北(即順時針)的方向試探MStackElem GetNext(MStackElem cur) MStackElem next;next.x = next.y=next.val = -1;if(GetEast(cur).val = & UnPass(path,GetEast(cur) next = GetEast(cur);else if(GetSouth(cur).val = & UnPass(path,GetSouth(cur) next = GetSouth(cur);else if(GetWest(cur).val

19、 = & UnPass(path,GetWest(cur) next = GetWest(cur);else if(GetNorth(cur).val = & UnPass(path,GetNorth(cur) next = GetNorth(cur); return next;/如果當前位置的四面或為墻或已走過,則返回的next的val值為-1 /獲得迷宮路徑的函數int GetMazePath() MStackElem start,cur; start.x = rukou0;start.y = rukou1; start.val = Mazerukou0rukou1;/入口坐標的值 cur

20、 = start; /設定當前位置為入口位置 do if (UnPass(path,cur)/如果當前位置未曾走到過 Push(&realPath,cur); Push(&path,cur); cur = GetNext(cur); if (cur.x = chukou0 & cur.y = chukou1)/到達出口 Push(&realPath,cur);/把出口結點放入路徑中 Push(&path,cur); return 1; else if(cur.val = -1)/當前位置的四面都為墻 Pop(&realPath);/刪除真實路徑的棧頂元素 cur = GetTop(&realP

21、ath);/令cur指向棧頂元素 else/如果當前位置已經走過,說明原來測試的方向不對,現在嘗試其它方向 cur = GetNext(cur); if (cur.val = -1) Pop(&realPath);/仍不通,刪除真實路徑的棧頂元素 cur = GetTop(&realPath);/令cur指向棧頂元素 while (cur.x != chukou0 | cur.y != chukou1);return 0; /輸出迷宮路徑PrintMazePath(MStack *S)/為了安全,這里不傳MStack的地址,以防在遍歷的過程中把它們的top或base的值也修改了 MStackE

22、lem e;int i,j;for(i=0;iM;i+)for(j=0;jbase top-1) e = *(S-base);/先指向棧底元素,以后依次向上增1se.xe.y=.;printf(%d,%d) - ,e.x,e.y);(S-base)+; /最后一個結點沒有后繼,所以不再輸出- e = *(S-base);se.xe.y=.; printf(%d,%d),e.x,e.y);/打開文件，獲取迷宮OpenFile() FILE *fp;int i,j,c;system(cls);if(fp=fopen(in.txt,rt)=NULL)/打開迷宮文件in.txtprintf(打開文件失??！n);exit(1);for(i=0;iM;i+)/將文件中的迷宮存放到Maze中for(j=0;jN;j+)fscanf(fp,%c,&Mazeij); fscanf(fp,%c,&c);/換行fclose(fp); /保存迷宮路線圖SaveFile()FILE *fp;int i,j;char strMN+1;for(i=0;iM;i+)for(j=0;jN;j+)strij=sij;strij=n;strM-1N=0;/結束符i