迷宮問題課程設計報告

1、<p><b>　　課程設計報告</b></p><p>　　課程名稱： 計算機技術基礎 </p><p>　　系 部： 電氣與信息工程學院 </p><p>　　專業班級： </p><p>　　學 號：

2、 </p><p>　　學生姓名： </p><p>　　指導教師： </p><p>　　完成時間： 2009.10.14 </p><p>　　報告成績：

3、 </p><p><b>　　迷宮通路問題</b></p><p><b>　　一．設計要求</b></p><p>　　通過游戲程序設計，提高編程興趣與編程思路，鞏固C語言中所學的知識，合理的運用資料，實現理論與實際相結合。</p><p>　?。?）．收集資料，分析課題，分解問題，形成總體設計

4、思路；</p><p>　?。?）．深入分析各個小問題，列出大綱，編寫各部分程序模塊；</p><p>　?。?）．對于設計中用到的關鍵函數，要學會通過查資料，弄懂其用法，要聯系問題進行具體介紹；</p><p>　?。?）．上機調試，查錯，逐步分析不能正常運行的原因，確保所設計的程序正確，并且能正常運行；</p><p>　?。?）．完成課

5、程設計報告，并進行答辯。</p><p><b>　　二．設計目的</b></p><p>　　通過游戲程序的設計訓練和提高學生的基本技能，掌握字符串的表示方法和字符串函數的功能、Turbo C圖形操作的基本知識、鍵盤上特殊鍵的獲取以及圖形方式下光標的顯示，提高編程興趣與編程水平，學會如何正確的書寫程序設計說明文檔，提高運用C語言解決實際問題的能力，鞏固C語言語法規則

6、的理解和掌握，學會通過源程序寫出流程圖，提高自學以及查閱資料的能力。</p><p><b>　　三．   問題描述</b></p><p>　　以一個m x n的長方矩陣表示迷宮，1和0分別表示迷宮中的通路和障礙。設計一個程序，對任意設定的迷宮，求出從入口到出口的通路，或者沒有通路的結論。</p><p>　　四、

7、0;  需析求分？</p><p>　　1、      以二維數組migong[M][N]表示迷宮，其中migong[0][j]和migong[i][0](0<=j,i<=N)為添加的一圈障礙。數組中以元素1表示通路，0表示障礙，迷宮的大小理論上可以不限制。</p><p>　　2、   

8、   迷宮數據由程序提供，用戶只需要進行選擇迷宮就行。迷宮的入口和出口由程序提供。</p><p>　　3、      若設定的迷宮存在通路，則以長方形矩陣的形式將迷宮及其通路輸出到標準終端上，其中“0”表示障礙，“2”表示通過的路徑，“3”表示死胡同，沒有顯示的區域表示沒有到達過的地方。</p><p>　　4、

9、60;     本程序只求出一條成功的通路。但是只要對函數進行小量的修改，就可以求出其他全部的路徑。</p><p>　　5、      程序執行命令為：（1）、創建迷宮；（2）、求解迷宮；（3）、輸出迷宮。</p><p><b>　　五、   概要設計</b&g

10、t;</p><p>　　1、 設定棧的抽象數據類型定義：</p><p><b>　　ADT zhan{</b></p><p>　　數據對象：D={ai|ai屬于yanshu，i=1、2…n，n>0}</p><p>　　數據關系：R={<ai-1,ai>|ai-1,ai屬于D，i=2,3,…n}&

11、lt;/p><p><b>　　基本操作：</b></p><p>　　gouzhan(*s,*migong)</p><p>　　操作結果：構造一個空棧</p><p>　　push（*s，*e）</p><p>　　初始條件：棧已經存在</p><p>　　操作結果：將e所

12、指向的數據加入到棧s中</p><p>　　pop（*s,*e）</p><p>　　初始條件：棧已經存在</p><p>　　操作結果：若棧不為空，用e返回棧頂元素，并刪除棧頂元素</p><p>　　getpop（*s，*e）</p><p>　　初始條件：棧已經存在</p><p>　　操

13、作結果：若棧不為空，用e返回棧頂元素</p><p>　　popover(*s)</p><p>　　初始條件：棧已經存在</p><p>　　操作結果：輸出棧中的所有元素，同時清空棧</p><p>　　stackempty(*s)</p><p>　　初始條件：棧已經存在</p><p>　

14、　操作結果：判斷棧是否為空。若棧為空，返回1，否則返回0</p><p>　　destroy(*s)</p><p>　　初始條件：棧已經存在</p><p><b>　　操作結果：銷毀棧s</b></p><p><b>　　}ADT zhan</b></p><p>　　

15、2、 設定迷宮的抽象數據類型定義</p><p>　　ADT yanshu{</p><p>　　數據對象：D={ai,j|ai,j屬于{‘ ’、‘0’、‘2’、‘3’},0<=i<=M,0<=j<=N}</p><p>　　數據關系：R={ROW,COL}</p><p>　　ROW={<ai-1,j,ai,j

16、>|ai-1,j,ai,j屬于D，i=1,2,…M,j=0,1,…N}</p><p>　　COL={<ai,j-1,ai,j>|ai,j-1,ai,j屬于D,i=0,1,…M，j=1,2,…N}</p><p><b>　　基本操作：</b></p><p>　　gouzhaomigong(*migong,m,n)</

17、p><p>　　初始條件：二維數組migong[m][n]已經存在，其中第1至第m-1行，每行自第1到第n-1列的元素已經值，并以值0表示障礙，值1表示通路。</p><p>　　操作結果：構造迷宮的字符數組，以空白表示通路，字符‘0’表示障礙，并在迷宮四周加上一圈障礙。</p><p>　　markprint(*seat)</p><p>　　

18、初始條件：迷宮中的所有坐標seat都已經被賦值</p><p>　　操作結果：若迷宮中該坐標能夠通過且已經通過，則標記為2，若不能夠通過（死胡同），標記為3。</p><p>　　shuchu(*migong,n)</p><p>　　初始條件：迷宮已經存在</p><p>　　操作結果：以字符形式輸出迷宮</p><p&

19、gt;　　}ADT yanshu</p><p>　　3、 本程序包括三個模塊</p><p><b>　　a、 主程序模塊</b></p><p>　　void main()</p><p><b>　　{</b></p><p><b>　　初始化；</b

20、></p><p><b>　　構造迷宮；</b></p><p><b>　　迷宮求解；</b></p><p><b>　　迷宮輸出；</b></p><p><b>　　}</b></p><p>　　b、 棧模塊——實

21、現棧的抽象數據類型</p><p>　　c、 迷宮模塊——實現迷宮的抽象數據類型</p><p><b>　　六、   詳細設計</b></p><p><b>　　1、 坐標位置類型</b></p><p>　　#define zuobiao int</p>&l

22、t;p>　　zuobiao migong[M][N];</p><p><b>　　2、 迷宮類型</b></p><p>　　typedef struct yanshu</p><p><b>　　{</b></p><p>　　int xuhao; //序號</p><

23、p>　　zuobiao *seat; //棧元素的坐標</p><p>　　int fangxiang; //要查找的方向</p><p><b>　　}yanshu;</b></p><p><b>　　3、 棧類型</b></p><p>　　typedef struct zhan<

24、/p><p><b>　　{</b></p><p>　　yanshu *base; //棧構造之前和銷毀之后base的值均為NULL</p><p>　　yanshu *top;//棧頂指針</p><p>　　int size; //當前分陪的存儲空間的長度，單位：元素</p><p><b

25、>　　}zhan;</b></p><p><b>　　七、   偽代碼 </b></p><p>　　1、     主函數</p><p>　　void main()</p><p><b>　　{</b></p&

26、gt;<p><b>　　變量的定義；</b></p><p>　　gouzhaomigong(migong,M,N); //構造一個迷宮</p><p>　　shuchu(migong,M,N); //將該構造好的迷宮輸出</p><p>　　tansuo(weizhi,&migong[1][1],&migong

27、[M-2][N-2]); //探索迷宮</p><p>　　shuchu(migong,M,N); //輸出探索出來的迷宮</p><p><b>　　}</b></p><p>　　2、     迷宮構造</p><p>　　void gouzhaomigong(zuobiao

28、migong[M][N],int M,int N)</p><p>　　{ //該函數是用來構造一個迷宮，通過更改還能夠構造其他類型迷宮</p><p>　　定義變量 a,b,c,i,k;</p><p>　　i=n/3-1;k=/2;a=k-2;</p><p>　　if(k*2==n) b=k;</p><p>　

29、　else b=k+1;</p><p>　　for(a=0;a<b;a++)</p><p><b>　　{</b></p><p>　　for(c=0;c<k;c++)</p><p><b>　　{</b></p><p>　　migong[a][c]=0;

30、 migong[n-a][c]=0;</p><p>　　migong[a][n-c-1]=0; migong[n-a][n-c-1]=0;</p><p>　　migong[c][a]=0; migong[c][n-c-1]=0;</p><p>　　migong[n-c-1][n-a-1]=0; migong[n-c-1][a]=0;</p>&l

31、t;p><b>　　}</b></p><p>　　if(a==b-1&&c!=1)</p><p><b>　　{</b></p><p>　　migong[a][c]=0; migong[a][n-c-1]=0;</p><p>　　migong[n-c-1][n-a-1]

32、=0; migong[c][n-a-a]=0;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　migong[1][i]=1; migong[k-2][i]=1;</p><p>　　migong[1][n-i-1]=1; migong[i][k+

33、1]=1;</p><p>　　migong[n-2][i]=1; migong[n-i][k+1]=1; migong[n-i][n-2]=1;</p><p><b>　　}</b></p><p>　　3、     棧的操作</p><p>　　zhan *gouzhan(z

34、han *s,zuobiao *migong) //構造一個棧</p><p><b>　　{</b></p><p>　　s->base=分配一定空間；</p><p>　　s->top=s->base;</p><p>　　s->top->seat=s->base->seat

35、=migong;</p><p>　　s->top->fangxiang=0; s->top->xuhao=0;</p><p><b>　　return s;</b></p><p><b>　　}</b></p><p>　　void push(zhan *s,yansh

36、u *e) //將e所指向的元素加入到棧中</p><p><b>　　{</b></p><p><b>　　if(空間不足)</b></p><p>　　分配連續空間，給各值賦值；</p><p>　　s->top++; s->top->seat=e->seat;<

37、/p><p>　　s->top->fangxiang=e->fangxiang+1;</p><p>　　s->top->xuhao=e->xuhao;</p><p><b>　　}</b></p><p>　　yanshu *pop（zhan *s,yanshu *e）//棧不為空，刪

38、除棧頂元素，用e返回</p><p><b>　　{</b></p><p>　　if(?？? retrun NULL;</p><p>　　e->seat=s->top-seat; e->seat--;</p><p>　　e->fangxiang=s->top->fangxiang

39、;</p><p>　　e->xuhao=s->top-xuhao; s->top--; return e;</p><p><b>　　}</b></p><p>　　yanshu *gettop（zhan *s,yanshu *e）// 用e返回棧頂元素，不刪除</p><p><b>　

40、　{</b></p><p>　　if(棧為空) return NULL;</p><p>　　e->seat=s->top->seat; e->seat=s-top->seat;</p><p>　　e->xuhao=s->top->xuhao; return e;</p><p>

41、;<b>　　}</b></p><p>　　int stackempty(zhan *s) //判斷棧是否為空</p><p><b>　　{</b></p><p>　　if(s->top==s->base) return 1;</p><p>　　else return 0;<

42、;/p><p><b>　　}</b></p><p>　　void popover(zhan *s) //輸出棧中的所有元素，同時清空棧</p><p><b>　　{for(;;)</b></p><p><b>　　{</b></p><p>　　e=

43、pop(s,e)；</p><p>　　if(s->top-s->base==0) return;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　八．系統程序結構及流程圖 不規范！還要繼續修改。</p><p>

44、;　　4、     求解迷宮中的一條路徑</p><p>　　void tansuo(yanshu weizhi,zuobiao *rukou,zuobiao *chukou)</p><p>　　{ //若迷宮weizhi中存在從rukou到chukou的通道，則求出其中一條</p><p>　　定義和初始化所需要的變量；&

45、lt;/p><p>　　gouzhan(s,curpos);//</p><p><b>　　do{</b></p><p>　　if(pass(curpos))//當前位置可以通過，即未曾走過的模塊</p><p><b>　　{</b></p><p>　　e=zuhe(cu

46、rstep,curpos,0);//組合成一個元素</p><p>　　push(s,e);//加入到路徑棧中</p><p>　　if(e->seat==chukou) braek; //到達終端</p><p>　　curpos=nestpos1(curpos,0);//下一位置是當前位置的東臨位</p><p>　　curstep

47、++; //探索下一步</p><p><b>　　}</b></p><p><b>　　else{</b></p><p>　　if(!=stackempty（s）)//如果棧不空</p><p>　　{ e=pop(s,e);</p><p>　　while(e-<

48、;fangxiang==4&&!=stackempty(s))</p><p>　　{ markprint(e->seat);//留下不能通過標記，退一步</p><p>　　e=pop(s,e);</p><p><b>　　}</b></p><p>　　if(e->fangxiang&l

49、t;4)</p><p>　　{ push(s,e); //探索下一方向</p><p>　　curpos=nextpos1(e->seat,e->fangxiang);</p><p>　　//設定當前位置是新方向上的相鄰模塊</p><p><b>　　}</b></p><p>

50、<b>　　}</b></p><p>　　}while(!stackempty(s));</p><p><b>　　return;</b></p><p><b>　　}</b></p><p>　　5、     迷宮的輸出顯示<

51、;/p><p>　　void shuchu(zuobiao migong[M][N],intm，int n)</p><p>　　{ //給出迷宮的行列數和首地址，輸出迷宮矩陣</p><p>　　for（i=0;i<M;i++）</p><p>　　{for(j=0;j<N;j++)</p><p>　　i

52、f(migong[i][j]==1) printf(“ “)；</p><p>　　else printf(“%d”,migong[i][j]);</p><p>　　printf(“\n”);</p><p><b>　　}</b></p><p><b>　　}</b></p>&

53、lt;p>　　九、   源代碼（省略）</p><p>　　十、   調試結果和分析</p><p>　　十一．設計心得體會 整篇文檔的字間距應整齊一致！</p><p>　　課程設計使我學到了很多書本以外的東西，同時也提高了查閱資料的能力以及解決問題的能力，培養培養學生綜合運用所學知識,發現,提出,分析和解決實際問題

54、,鍛煉實踐能力的重要環節,是對學生實際工作能力的具體訓練和考察過程。熟練掌握TC集成環境的使用方法。認真編寫實習報告和實習總結，描述實習操作和心得體會，總結在這次實習中的業務收獲，作出自我評價。熟練掌握并應用TC程序設計的各個知識點。掌握結構體和指針的聯合使用，學會鏈表的構造和常用操作方法，認真編寫實習日志和實習體會。并通過各種途徑查找所需資料，拓寬視野，培養自學能力。也懂得了理論與實際相結合的重要性，只有理論知識是遠遠不夠的，只有把所

55、學的理論知識與實踐相結合起來，從理論中得出結論，才能真正為社會服務，從而提高自己的實際動手能力和獨立思考的能力。在設計的過程中遇到問題，可以說得是困難重重，這畢竟第一次做的，難免會遇到過各種各樣的問題，同時在設計的過程中發現了自己的不足之處，對以前所學過的知識理解得不夠深刻，掌握得不夠牢固。</p><p>　　在做這次課程設計的時候，遇到這樣那樣的麻煩，因此，我也得到了許多寶貴的經驗：</p>&

56、lt;p>　　1、在設計程序之前,務必要對你所設計的題目和內容有一個系統的了解,知道所設計的題目和內容包含那些資源。</p><p>　　2、設計程序采用什么編程語言并不是非常重要,關鍵要有一個清晰的思路和一個完整的軟件流程圖，因而，要先把設計原理與思路搞清楚，再把流程圖畫出來，這樣設計起來就簡單多了。</p><p>　　3、在設計程序時,不能妄想一次就將整個程序設計好,“反復修改

57、,不斷改進”是程序設計的必經之路，發現錯誤也是取得成績的一種。</p><p>　　4、要養成注釋程序的好習慣,一個程序的完美與否不僅僅是實現功能,而應該讓人一看就能明白你的思路,這樣也為資料的保存和交流提供了方便。</p><p>　　5、在設計程序過程中遇到問題是很正常的,但我們應該將每次遇到的問題記錄下來,并分析清楚,以免下次再碰到同樣的問題。</p><p>

58、;　　在14天編程的過程當中彌補了我許多知識上的缺陷，弄清楚了我不懂的地方和似是而非的地方，使我及時補上了欠缺。其次，通過14天綜合實訓編程使我的知識形成了一個完整的框架結構，而不再是零散的知識個體，使我在使用時更加的方便。在14天的實習結束后，我對做完的習題檢查比再是一切的走馬觀花，而是仔細核對、認真檢查。這也改變了我做題時心煩氣燥的習慣，現在做題可以平和靜氣的完成。我的自制能力更強了，基本完全可以控制自己，避免外界的干擾，安心地完成