迷宮課程設(shè)計(jì)報(bào)告

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

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

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

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

5、宮路徑初始化棧菜單獲得下一個(gè)可走的位置顯示迷宮路線保存迷宮路線取棧頂元素開始2.各功能函數(shù)的數(shù)據(jù)流程圖MStackElem start,cur;p2=head;（1） 獲得迷宮路徑函數(shù)cur= start; do while (cur.x != chukou0 | cur.y != chukou1)當(dāng)前位置是否走過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) 獲得下一個(gè)可通行的位置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.重點(diǎn)設(shè)計(jì)及編碼獲得迷宮路徑的函數(shù)：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;五測試數(shù)據(jù)及運(yùn)行結(jié)果1正常測試數(shù)據(jù)和運(yùn)行結(jié)果 2.異常測試數(shù)據(jù)及運(yùn)行結(jié)果 六調(diào)試情況，設(shè)計(jì)技巧及體會(huì)1改進(jìn)方案在迷宮問題中，由于走的方向順序不同，存在著多條路徑的結(jié)果。因此就出現(xiàn)了一個(gè)最大的問題，哪條路徑最短，即求最短路徑。由于時(shí)間有限和難度問題，我沒能及時(shí)解決這個(gè)問題，這也是在這次的迷宮課程設(shè)計(jì)中，我唯一的不足之處。不過我并沒有放棄，課程設(shè)計(jì)結(jié)束后，我還會(huì)繼續(xù)努力，解決掉這個(gè)問題。在以后的生活中，我也會(huì)不斷督促自己，提高編程能力。2體會(huì)剛開始，頭腦里沒有任何思路，不知道如何下手，經(jīng)過仔細(xì)研讀課本和上網(wǎng)查資料后，終于有了思緒。先將整個(gè)程序劃分為三個(gè)大模塊：主模塊，棧模塊和迷宮模塊。然

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

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

12、y;/y坐標(biāo) 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);/存儲(chǔ)分配失敗 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);/存儲(chǔ)分配失敗 S-top = S-base + S-StackSize; /因?yàn)槭侵匦路峙淞丝臻g,所以base的值其實(shí)已經(jīng)改

14、變,所以top的值也就相應(yīng)的改變,才能指向新的迷宮棧 S-StackSize += STACKINCREMENT; *(S-top+) = e;/將新元素加到棧頂 /獲得棧頂元素MStackElem GetTop(MStack *S) if (S-top = S-base)printf(n對(duì)不起，沒有出路!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;/構(gòu)造兩個(gè)棧,一個(gè)用來保存探索中的全部路徑,一個(gè)用來保存有效路徑 /判斷當(dāng)前位置是否走過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)-;/每循環(huán)一次令頭指針下移一個(gè)位置 return flag; /獲得東面(即右邊)相

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

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

18、;/當(dāng)cur.x=1時(shí)返回的還是它本身 /獲得下一個(gè)可通行的位置,按東南西北(即順時(shí)針)的方向試探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;/如果當(dāng)前位置的四面或?yàn)閴蛞炎哌^,則返回的next的val值為-1 /獲得迷宮路徑的函數(shù)int GetMazePath() MStackElem start,cur; start.x = rukou0;start.y = rukou1; start.val = Mazerukou0rukou1;/入口坐標(biāo)的值 cur

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

21、ath);/令cur指向棧頂元素 else/如果當(dāng)前位置已經(jīng)走過,說明原來測試的方向不對(duì),現(xiàn)在嘗試其它方向 cur = GetNext(cur); if (cur.val = -1) Pop(&realPath);/仍不通,刪除真實(shí)路徑的棧頂元素 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)+; /最后一個(gè)結(jié)點(diǎn)沒有后繼,所以不再輸出- 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;/結(jié)束符i