1、目 錄引 言1一設(shè)計(jì)目的2二問題描述2三需求分析3四設(shè)計(jì)3五測試分析5六完整代碼10七設(shè)計(jì)體會與小結(jié)17八、成績：21 引 言 數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)過程，是進(jìn)行復(fù)雜程序設(shè)計(jì)的訓(xùn)練過程，是算法構(gòu)造性思維方法的訓(xùn)練過程，技能培養(yǎng)的過程不亞于知識傳授。數(shù)據(jù)結(jié)構(gòu)課程教學(xué)的重要內(nèi)容和主要難點(diǎn)在于讓我們理解、習(xí)慣算法構(gòu)造性思維方法。培養(yǎng)我們的數(shù)據(jù)抽象能力、算法設(shè)計(jì)能力以及創(chuàng)造性思維方法，才能夠舉一反三、觸類旁通，從而達(dá)到應(yīng)用知識解決復(fù)雜問題的目的。數(shù)據(jù)結(jié)構(gòu)作為專業(yè)基礎(chǔ)課程，可以對去年學(xué)習(xí)的語言知識進(jìn)行總結(jié)提高，為后續(xù)專業(yè)基礎(chǔ)課程提供基礎(chǔ)，它承上啟下，貫通始終，是計(jì)算機(jī)科學(xué)與技術(shù)人才素質(zhì)框架中的脊梁，對我們能力的

2、培養(yǎng)至關(guān)重要。通過對數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)，我們能夠以問題求解方法、程序設(shè)計(jì)方法及一些典型的數(shù)據(jù)結(jié)構(gòu)算法為對象，學(xué)會分析數(shù)據(jù)對象特征，掌握數(shù)理算法，初步掌握算法的時間、空間復(fù)雜分析基礎(chǔ)，培養(yǎng)良好的程序設(shè)計(jì)風(fēng)格以及進(jìn)行復(fù)雜程序設(shè)計(jì)的技能。一設(shè)計(jì)目的 這次課程設(shè)計(jì)，我們的題目是迷宮求解。迷宮求解是數(shù)據(jù)結(jié)構(gòu)中的經(jīng)典問題，我期望達(dá)到的目的有以下4個。1.鞏固書本知識，對書上的知識能更透徹的了解.通過自己設(shè)計(jì)程序積累調(diào)試數(shù)據(jù)結(jié)構(gòu)的經(jīng)驗(yàn)，培養(yǎng)我們的編程能力。鞏固我們所學(xué)的數(shù)據(jù)結(jié)構(gòu)知識，消化課堂所講解的內(nèi)容。也是對所學(xué)知識的整理，將原來在我們腦中比較混亂的課程設(shè)計(jì)重新梳理。2.通過課程設(shè)計(jì)能更好的掌握迷宮求解中的設(shè)

3、計(jì)思路，為以后靈活運(yùn)用奠定基礎(chǔ)。3.能夠獨(dú)立的完成簡單程序的設(shè)計(jì)以及完成一份較為滿意的程序設(shè)計(jì)報(bào)告。4.通過課程設(shè)計(jì)達(dá)到增強(qiáng)鞏固數(shù)據(jù)結(jié)構(gòu)知識的目的，使知識全面化、系統(tǒng)化。 二問題描述 迷宮問題來源于古希臘的神話，而后被人們演化為一個游戲。以一個N*M的方正表示迷宮，0、1分別表示迷宮中的通路和障礙。設(shè)計(jì)一個程序?qū)θ我庠O(shè)定的迷宮求出一條從入口的通道，或者的出沒有通路的結(jié)論。假設(shè)一個老鼠從起點(diǎn)0.0沿X軸的八個方向逆時針旋轉(zhuǎn)，老鼠每走到一處，總讓它按東，東南，南，西南，西，西北，北，東北8個方向順序試探下一個位置，如果某方向可以通過，則前進(jìn)一步，在新位置上繼續(xù)進(jìn)行搜索；如果8個方向都走不通或曾經(jīng)到

4、達(dá)過則退回一步，都要進(jìn)行判斷：若前進(jìn)到了出口處，則說明不存在通路。如此重復(fù)直至走到終于，即為成功。三需求分析 通過主函數(shù)調(diào)用棧和遞歸的算法，來創(chuàng)作迷宮游戲或者解決迷宮問題。1.迷宮用類型的二維數(shù)組77矩陣來表示，其中每一個格用一個MG結(jié)構(gòu)體表示，包括以下元素：是否是障礙物，0表示通過，1表示障礙物，mx(橫坐標(biāo)),my(縱坐標(biāo))，迷宮的暫時位置為固定。2.程序的輸出信息主要有：（1）.打印的迷宮模塊（2）.小老鼠所走的路徑（3）.漢諾塔分步搬遷表示過程。3.程序的功能包括：（1）.對迷宮加密（2）.顯示主菜單函數(shù)（3）保存恢復(fù)原函數(shù)信息（4）用遞歸和棧顯示老鼠所走路徑（5）用漢諾塔是實(shí)現(xiàn)搬遷（

5、6）用清屏函數(shù)來清屏四設(shè)計(jì) 概要設(shè)計(jì)1. 定義棧的抽象數(shù)據(jù)類型ADT Stack數(shù)據(jù)元素：可以是任意類型的數(shù)據(jù)，但必須屬于同一個 數(shù)據(jù)對象。結(jié)論關(guān)系：棧中數(shù)據(jù)元素之間是線性關(guān)系?；静僮鳎号袛鄺Ｊ欠駷榭铡Ｈ魲榭胀瞥鲅h(huán)。否則讓該元素入棧ADT Stack2. 定義數(shù)組抽象數(shù)據(jù)類型ADT Stack數(shù)據(jù)對象：D=a j1 j2 .jn n0.稱為數(shù)組的維數(shù)，ji是數(shù)組的第i維下標(biāo)，1=ji=bi,bi為數(shù)組第i維的長度，Aj1j2.jn屬于ElementSet數(shù)據(jù)關(guān)系：R=R1,R2,RnRi= | 1=jk=bk,1=k=n且k!=I,1=ji+bi-1,aj1jijn,aj1ji+1jn屬

6、于D，i=1,n3. 基本操作1. InitArray(A,n,boundl,boundn)：若維數(shù)n和各維的長度合法，則構(gòu)造相應(yīng)的數(shù)組A，并返回TRUE。2. GetValue(A,e,index1,indexn):若下標(biāo)合法，則用e返回?cái)?shù)組A中由index1,indexn所指的元素的值.程序結(jié)構(gòu)可以化分成以下幾個模塊： 1-主函數(shù)main()主函數(shù)調(diào)用其它子函數(shù)2-指令函數(shù)void login()用來設(shè)置迷宮的密碼3-菜單函數(shù)select_menu()顯示菜單界面4-遞歸函數(shù)void digui(int mazeNM, int x,int y, int v, int xx,int yy)用

7、遞歸函數(shù)實(shí)現(xiàn)迷宮走向5-棧函數(shù)void stack(int mazeNM, int x,int y, int xx,int yy)用棧實(shí)現(xiàn)迷宮走向6-漢諾塔void hanio(int q, int a, int b, int c)hanio實(shí)現(xiàn)搬遷7-保存函數(shù)void save( int mazeM,int backupM)保存初始值8-恢復(fù)函數(shù)void load (int mazeM,int backupM)恢復(fù)程序功能，繼續(xù)執(zhí)行程序9-清屏函數(shù) system(cls)清除執(zhí)行過的界面各函數(shù)之間的調(diào)用關(guān)系如下：菜單函數(shù)主函數(shù)1依次調(diào)用上面的2、3、4、5、6、7、8、9，實(shí)現(xiàn)迷宮行走路徑及

8、漢諾塔的搬遷。指令函數(shù)主函數(shù)遞歸函數(shù)棧函數(shù)漢諾塔函數(shù)保存函數(shù)恢復(fù)函數(shù)清屏函數(shù)圖1 函數(shù)調(diào)用關(guān)系圖五測試分析首先二個圖是錯誤的運(yùn)行結(jié)果，圖2 登陸錯誤時界面的顯示圖3 用棧實(shí)現(xiàn)的結(jié)果選擇2時，是系統(tǒng)用棧解決了迷宮問題。如圖3所示。如果接著輸入數(shù)字1就是下面的結(jié)果。圖4 用棧和遞歸實(shí)現(xiàn)后的結(jié)果圖5 用遞歸實(shí)現(xiàn)圖6 漢諾塔實(shí)現(xiàn)的結(jié)果 清屏函數(shù)加入依次輸入1、2、3，上圖是輸入3后的結(jié)果，按回車鍵控制輸出漢諾塔的搬遷次數(shù)。六完整代碼 #include#include #include #include#include#include#include#define N 7#define M 7#defi

9、ne Q 5int r=2;int movex9=0,1,1,0,-1,-1,-1,0,1;/用結(jié)構(gòu)體表示位置int movey9=0,0,1,1,1,0,-1,-1,-1;int mazeNM=/按照用戶輸入的二維數(shù)組（0或1）設(shè)置迷宮maze的初值，包括加上邊緣一圈的值1,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0,0,1,1,1,1,0,0,1,0,1,1,1,1,1,0,1,1,1,1,0,1,0,0,1,1,1,1,1,1,1,1,1;int backup N M;void save( int mazeM,int backupM)/保存函數(shù)int i, j;for

10、(i=0;iN;i+)for(j=0;jM;j+)backupij=mazeij;void load (int mazeM,int backupM)/恢復(fù)函數(shù)int i,j;for(i=0;iN;i+)for(j=0;jM;j+)mazeij=backupij;int select_menu()/菜單函數(shù) int i,n; for(i=1;i用遞歸實(shí)現(xiàn) &n ); printf(nt& 2-用棧實(shí)現(xiàn) &n ); printf(nt& 3- 漢諾塔 &n ); printf(nt& 4- 退出 &n ); printf(nt& &n); printf(nt& 設(shè)計(jì)者:楊瑞嬌 杜春雨 趙詢 黃錦

11、&n); printf(nt& (第十三組)&n); printf(nt& 團(tuán)結(jié)協(xié)作 實(shí)現(xiàn)共贏 &n); for(i=1;i=1) hanio( q-1, a,c,b); printf( 現(xiàn)在是第%d 搬遷 從%c-到%cn,+step, a+64, c+64); system(pause);/起暫停作用 hanio(q-1, b,a, c);void print( int aNM)/打印設(shè)置迷宮的模塊 int i, j; for(i=0; iN; i+) for(j=0; jM; j+) printf(%3d, aij); printf(n); void digui(int mazeNM,

12、int x,int y, int v, int xx,int yy)/遞歸函數(shù)int x1,y1; mazexy=r+;/記錄路徑長度 for(v=1; v=8; v+)/v為老鼠所走路徑的方向，1-8表示八個方向 x1=x+movexv; y1=y+moveyv;/隨v的變化，更新老鼠所處位置 if(x1=xx&y1=yy) mazex1y1=r+;/記錄路徑長度 print(maze);/調(diào)用print函數(shù)/ getchar(); return;/當(dāng)老鼠走到出口時，打印 else if(mazex1y1=0) /如果成立，說明這是一個通路 digui(maze,x1,y1,1,xx,yy)

13、; /調(diào)用go函數(shù) mazexy=0;/通路void stack(int mazeNM, int x,int y, int xx,int yy)/棧函數(shù) int i;int x1,y1,x2,y2,v,top=1;structint x;int y;int v; sN*M;/定義結(jié)構(gòu)體 stop.x=x; stop.y=y;/x、y入棧 stop.v=0;/路徑長度附初值 mazexy=2;while(top!=0)/判斷棧是否為空，若非空，則出棧 x1=stop.x; y1=stop.y; v=stop.v+1; top-; while(v=8) x2=x1+movexv; y2=y1+mo

14、veyv;/隨v的變化，更新老鼠所處位置 if(x2=xx&y2=yy)/當(dāng)老鼠走到出口時，輸出出老鼠所走路徑 for(i=1; i8時退出循環(huán) void login()/設(shè)置秘密 char pass6; int i; for(i=1;i=3; i+)/三次機(jī)會,若三次密碼都未輸對,則不能進(jìn)入界面 printf(nnnnntttplease input password:n); gets(pass); if(strcmp(pass,)=0) break;/若輸進(jìn),則退出循環(huán),進(jìn)入主界面 if(i=3) printf(n *weclome you to here*n);/若輸密碼次數(shù)=3,則出現(xiàn)

15、括號內(nèi)的字符 printf(n); else printf(ntno usen);/輸出no use exit(0);/退出本層循環(huán) void main() int x0=1, y0=1,xx=5,yy=4; int i=1,j=0; login();/調(diào)用login函數(shù) for(;)/循環(huán)調(diào)出主菜單 switch(select_menu()/調(diào)用select_menu()函數(shù) case 1:save(maze,backup);digui(maze,x0,y0,1,xx,yy);load(maze,backup);/調(diào)用digui函數(shù) system(cls);/清屏函數(shù) break; case 2: save(maze,backup); stack(