《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告迷宮求解

1、課程設(shè)計(jì)任務(wù)書(shū)題目迷宮設(shè)計(jì)學(xué)號(hào)：姓名：專(zhuān)業(yè)：網(wǎng)絡(luò)技術(shù)課程：數(shù)據(jù)結(jié)構(gòu)指導(dǎo)教師：職稱(chēng)：講師完成時(shí)間：2013年12月-2014年1月年月曰課程設(shè)計(jì)任務(wù)書(shū)及成績(jī)?cè)u(píng)定實(shí)驗(yàn)任務(wù)：通過(guò)數(shù)據(jù)結(jié)構(gòu)運(yùn)用c語(yǔ)言寫(xiě)迷宿算法,實(shí)驗(yàn)?zāi)康模和ㄟ^(guò)綜合性課程設(shè)計(jì)題目的完成過(guò)程，運(yùn)用所學(xué)數(shù)據(jù)結(jié)構(gòu)知識(shí),解決生活中遇到的實(shí)際問(wèn)題，達(dá)到活學(xué)活用，所學(xué)所用的目的，進(jìn)一步理解數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)目的，提高實(shí)際應(yīng)用水平日期:指導(dǎo)教師簽字:成績(jī)：指導(dǎo)教師簽字：日期:聯(lián)想筆記本win7系統(tǒng)，win-tc課程設(shè)計(jì)進(jìn)度計(jì)劃起至日期工作內(nèi)容備注13年12月初選擇題目13年12月中旬13年12月下旬制定方案制作設(shè)計(jì)參考文獻(xiàn)、資料索引序號(hào)文獻(xiàn)、資料名稱(chēng)編者者

2、出版單位蔣秀英燕孝飛等，數(shù)據(jù)結(jié)構(gòu).東營(yíng)：中國(guó)石油大學(xué)，2011嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)（c語(yǔ)言版）.北京：清華大學(xué)出版社，2007目錄?迷宿求解（1）問(wèn)題描述2）需求分析及設(shè)計(jì)思路3）數(shù)據(jù)結(jié)構(gòu)定義4）系統(tǒng)功能模塊介紹5）源代碼6）運(yùn)行結(jié)果及調(diào)試分析7）課程設(shè)計(jì)總結(jié)迷宮求解(1) 問(wèn)題描述輸入一個(gè)任意大小的迷宿數(shù)據(jù)，用遞歸和非遞歸兩種方法求出一條走出迷宿的路徑，并將路徑輸出。(2) 需求分析及設(shè)計(jì)思路從入口出發(fā)，按某一方向向前探索，若能走通并且未走過(guò)，即某處可以到達(dá)，則到達(dá)新點(diǎn)，否則試探下一個(gè)方向；若所有的方向均沒(méi)有通路，則沿原路返回前一點(diǎn)，換下一個(gè)方向再繼續(xù)試探，直到找到一條通路，或無(wú)路可走又返回入口

3、點(diǎn)。在求解過(guò)程中，為了保證在到達(dá)某一點(diǎn)后不能向前繼續(xù)行走(無(wú)路)時(shí)，能正確返回前一點(diǎn)以便繼續(xù)從下一個(gè)方向向前試探，則需要用一個(gè)棧(遞歸不需要)保存所能夠到達(dá)的每一點(diǎn)的下標(biāo)及從該點(diǎn)前進(jìn)的方向。設(shè)迷H為m行n列，利用mazemn來(lái)表示一個(gè)迷H,mazeij=0或1;其中：0表示通路，1表示不通，當(dāng)從某點(diǎn)向下試探時(shí)，中間點(diǎn)有四個(gè)方向可以試探，而四個(gè)角點(diǎn)有兩個(gè)方向，其他邊緣點(diǎn)有三個(gè)方向，為使問(wèn)題簡(jiǎn)單化，用mazem+2n+2來(lái)表示迷宿，而迷宿的四周的值全部為1,這樣做使問(wèn)題簡(jiǎn)單了，每個(gè)點(diǎn)的試探方向全部為4,不用再判斷當(dāng)前點(diǎn)的試探方向有幾個(gè)。數(shù)據(jù)結(jié)構(gòu)定義#definem6#definen8#define

4、MAXSIZE100/四周為1代表圍墻,0為可走路徑intmazem+2n+2=1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,0,0,0,1,1,1,1,1,1,0,1,0,0,0,0,0,1,1,1,0,1,1,1,0,0,1,1,1,1,1,0,0,1,1,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1;/入口坐標(biāo)為(1,1),出口坐標(biāo)為(6,8)typedefstructintx,y;/*試探方向*/item;itemmove4=0,1,1,0,0,-1,-1,0;typedefstruct/*棧的

5、設(shè)計(jì)*/intx,y,d;縱橫坐標(biāo)及方向*/*DataType;(3)系統(tǒng)功能模塊介紹創(chuàng)建一順序棧：PSeqStackInit_SeqStack(void)判斷棧是否為空：intEmpty_SeqStack(PSeqStackS)在棧頂插入一新元素x:intPush_SeqStack(PSeqStackS,DataTypex)刪除棧頂元素并保存在*x:intPop_SeqStack(PSeqStackS,DataType*x)銷(xiāo)毀棧：voidDestroy_SeqStack(PSeqStack*S)利用棧的非遞歸算法求迷!路徑：intmazepath(intmazen+2,itemmove,i

6、ntx0,inty0)遞歸算法求迷!路徑：intmazepath1(intmazen+2,itemmove,intx,inty)主函數(shù)：intmain()出口坐標(biāo)已定，利用while循環(huán)多次輸入入點(diǎn)坐標(biāo)，調(diào)用mazepath(intmazen+2,itemmove,intx0,inty0)輸出可走的路徑(5)源代碼#include<stdio.h>#include<stdlib.h>#definem6#definen8#defineMAXSIZE100intmazem+2n+2=1,1,1,1,1,1,1,1,1,1,/四周為1代表圍墻,0為可走路徑1,0,1,1,1,

7、0,1,1,1,1,1,0,0,0,0,1,1,1,1,1,1,0,1,0,0,0,0,0,1,1,1,0,1,1,1,0,0,1,1,1,1,1,0,0,1,1,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1;/入口坐標(biāo)為(1,1),出口坐標(biāo)為(6,8)typedefstructintx,y;/*試探方向*/item;itemmove4=0,1,1,0,0,-1,-1,0;typedefstruct/*棧的設(shè)計(jì)*/intx,y,d;/*縱橫坐標(biāo)及方向*/DataType;typedefstruct/*棧*/DataTypedataMAXSIZE

8、;inttop;SeqStack,*PSeqStack;PSeqStackInit_SeqStack(void)/*創(chuàng)建一順序棧，入口參數(shù)無(wú)，返回一個(gè)指向順序棧的指針，為零表示分配空間失敗*/PSeqStackS;S=(PSeqStack)malloc(sizeof(SeqStack);if(S)S->top=-1;returnS;intEmpty_SeqStack(PSeqStackS)/*判斷棧是否為空，入口參數(shù)：順序棧，返回值：1表示為空，0表示非空*/if(S->top=-1)return1;elsereturn0;intPush_SeqStack(PSeqStackS,D

9、ataTypex)/*在棧頂插入一新元素x,入口參數(shù)：順序棧，返回值：1表示入棧成功，0表示失敗。*/if(S->top=MAXSIZE-1)return0;/*棧滿(mǎn)不能入棧*/elseS->top+;S->dataS->top=x;return1;intPop_SeqStack(PSeqStackS,DataType*x)/*刪除棧頂元素并保存在*x,入口參數(shù)：順序棧，返回值：1表示出棧成功，0表示失敗。*/if(Empty_SeqStack(S)return0;/*棧空不能出棧*/else*x=S->dataS->top;S->top-;retur

10、n1;voidDestroy_SeqStack(PSeqStack*S)if(*S)free(*S);*S=NULL;return;/*利用棧的非遞歸算法*/intmazepath(intmazen+2,itemmove,intx0,inty0)(/*求迷宿路徑,入口參數(shù)：指向迷宿數(shù)組的指針，下標(biāo)移動(dòng)的增雖數(shù)組，開(kāi)始點(diǎn)(x0,yO),到達(dá)點(diǎn)(m,n),返回值：1表示求出路徑，0表示無(wú)路徑*/PSeqStackS;DataTypetemp;intx,y,d,i,j;temp.x=x0;temp.y=y0;temp.d=-1;S=Init_SeqStack();/*初始化棧*/if(!S)(pri

11、ntf("棧初始化失敗");return(0);Push_SeqStack(S,temp);/*迷宿入口點(diǎn)入棧*/while(!Empty_SeqStack(S)(Pop_SeqStack(S,&temp);x=temp.x;y=temp.y;d=temp.d+1;while(d<4)/*存在剩余方向可以搜索*/(i=x+moved.x;j=y+moved.y;if(mazeij=0)/*(此方向可走*/temp.x=x;temp.y=y;temp.d=d;Push_SeqStack(S,temp);/*走的路徑*/點(diǎn)x,y可以走，用棧保存可以x=i;y=j;

12、mazexy=-1;if(x=m&&y=n)/*迷宿有路*/while(!Empty_SeqStack(S)Pop_SeqStack(S,&temp);printf("(%d,%d)<-",temp.x,temp.y);/*打印可走的路徑*/Destroy_SeqStack(&S);/*銷(xiāo)毀棧*/return1;elsed=0;/*方向復(fù)位，從第一個(gè)方向開(kāi)始試探*/elsed+;/*試探下一個(gè)方向*/*while(d<4)*/*while*/Destroy_SeqStack(&S);/*銷(xiāo)毀棧*/return0;/*迷宿無(wú)

13、路*/*遞歸算法*/intmazepath1(intmazen+2,itemmove,intx,inty)/*求迷宿路徑，入口參數(shù)：迷宿數(shù)組，下標(biāo)移動(dòng)的增雖數(shù)組，開(kāi)始點(diǎn)(x,y),以及開(kāi)始點(diǎn)對(duì)應(yīng)的步數(shù)step,(m,n)是終點(diǎn)，返回值：1表示求出路徑，0表示無(wú)路徑*/inti;intstep=0;step+;mazexy=step;if(x=m&&y=n)return1;/*起始位置是出口，找到路徑,結(jié)束*/for(i=0;i<4;i+)if(mazex+movei.xy+movei.y=0)if(mazepath(maze,move,x+movei.x,y+movei.

14、y)return1;/*下一個(gè)是出口，則返回*/step-;mazexy=0;return0;)intmain()(inti,j,k;charu;intx,y;printf("*歡迎進(jìn)入迷!游戲圖為一個(gè)6*8的迷宿：n");printf("ffor(i=0;i<m+2;i+)(printf("*");for(j=0;j<n+2;j+)(*n");printf("下*n);printf("%-2d”,mazeij);)printf(");printf("n");printf(

15、"f*n");printf("現(xiàn)在開(kāi)始游戲？(y/n):");scanf("%c”,&u);while(u!='n')(printf("請(qǐng)輸入迷宿入口坐標(biāo)(x,y):");scanf("%d,%d”,&x,&y);printf("出口：(6,8)<-");k=mazepath(maze,move,x,y);printf(":入口n");if(k=1)printf("恭喜！走出迷Hnn");elseprintf(

16、"迷宿無(wú)路nn");printf("繼續(xù)游戲:");scanf("%c”,&u);printf("n");return0;(6)運(yùn)行結(jié)果及調(diào)試分析11111tCJCXWI1111r>£rx1111*ww111*Tj1inBillB0(I1111«*«r/tu*Vym：4mlHEIt000111101180wwirilr且以wjy竺*睥b*j<wk仁j,i>-；入口jy：31迷富尢路運(yùn)行結(jié)果達(dá)到預(yù)期結(jié)果達(dá)到，遞歸和非遞歸兩種方法求出一條走出迷宿的路徑，并將路徑輸出，并實(shí)現(xiàn)多次輸入入口點(diǎn)來(lái)驗(yàn)證程序的可行性。(7)課程設(shè)計(jì)總結(jié)在這次實(shí)踐中遇到了各種問(wèn)題，碰到問(wèn)題有時(shí)總是百思不得其解經(jīng)過(guò)反復(fù)測(cè)試，最終確定原因，導(dǎo)致數(shù)據(jù)無(wú)法更新。迷宿問(wèn)題：是加深對(duì)棧運(yùn)用的好程序。這個(gè)程序又加了個(gè)遞歸的算法，相同的程序不同的算法。我結(jié)合老師提過(guò)的思想與教材上的例子，很順利的完成了這個(gè)程序。其實(shí)在寫(xiě)完這個(gè)程序后?；侍觳回?fù)有心人，按照步驟，忙碌了兩周，在不斷地努力下，總算將