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

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

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

3、點(diǎn)。在求解過程中，為了保證在到達(dá)某一點(diǎn)后不能向前繼續(xù)行走(無路)時，能正確返回前一點(diǎn)以便繼續(xù)從下一個方向向前試探，則需要用一個棧(遞歸不需要)保存所能夠到達(dá)的每一點(diǎn)的下標(biāo)及從該點(diǎn)前進(jìn)的方向。設(shè)迷H為m行n列，利用mazemn來表示一個迷H,mazeij=0或1;其中：0表示通路，1表示不通，當(dāng)從某點(diǎn)向下試探時，中間點(diǎn)有四個方向可以試探，而四個角點(diǎn)有兩個方向，其他邊緣點(diǎn)有三個方向，為使問題簡單化，用mazem+2n+2來表示迷宿，而迷宿的四周的值全部為1,這樣做使問題簡單了，每個點(diǎn)的試探方向全部為4,不用再判斷當(dāng)前點(diǎn)的試探方向有幾個。數(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è)計*/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)銷毀棧：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è)計*/intx,y,d;/*縱橫坐標(biāo)及方向*/DataType;typedefstruct/*棧*/DataTypedataMAXSIZE

8、;inttop;SeqStack,*PSeqStack;PSeqStackInit_SeqStack(void)/*創(chuàng)建一順序棧，入口參數(shù)無，返回一個指向順序棧的指針，為零表示分配空間失敗*/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;/*棧滿不能入棧*/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)移動的增雖數(shù)組，開始點(diǎn)(x0,yO),到達(dá)點(diǎn)(m,n),返回值：1表示求出路徑，0表示無路徑*/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);/*銷毀棧*/return1;elsed=0;/*方向復(fù)位，從第一個方向開始試探*/elsed+;/*試探下一個方向*/*while(d<4)*/*while*/Destroy_SeqStack(&S);/*銷毀棧*/return0;/*迷宿無

13、路*/*遞歸算法*/intmazepath1(intmazen+2,itemmove,intx,inty)/*求迷宿路徑，入口參數(shù)：迷宿數(shù)組，下標(biāo)移動的增雖數(shù)組，開始點(diǎn)(x,y),以及開始點(diǎn)對應(yīng)的步數(shù)step,(m,n)是終點(diǎn)，返回值：1表示求出路徑，0表示無路徑*/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;/*下一個是出口，則返回*/step-;mazexy=0;return0;)intmain()(inti,j,k;charu;intx,y;printf("*歡迎進(jìn)入迷!游戲圖為一個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)在開始游戲？(y/n):");scanf("%c”,&u);while(u!='n')(printf("請輸入迷宿入口坐標(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、"迷宿無路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)來驗(yàn)證程序的可行性。(7)課程設(shè)計總結(jié)在這次實(shí)踐中遇到了各種問題，碰到問題有時總是百思不得其解經(jīng)過反復(fù)測試，最終確定原因，導(dǎo)致數(shù)據(jù)無法更新。迷宿問題：是加深對棧運(yùn)用的好程序。這個程序又加了個遞歸的算法，相同的程序不同的算法。我結(jié)合老師提過的思想與教材上的例子，很順利的完成了這個程序。其實(shí)在寫完這個程序后?；侍觳回?fù)有心人，按照步驟，忙碌了兩周，在不斷地努力下，總算將