農(nóng)夫過河和騎士周游(數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)).doc

姓名：高明學(xué)號(hào)：129074151專業(yè)：軟件工程2014/6/20數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 1:實(shí)驗(yàn)要求1.1實(shí)驗(yàn)?zāi)康恼莆請(qǐng)D的遍歷問題，運(yùn)用圖的遍歷算法解決復(fù)雜問題。掌握并應(yīng)用鄰接存儲(chǔ)結(jié)構(gòu)和圖的深度遍歷問題。培養(yǎng)學(xué)習(xí)使用圖的相關(guān)知識(shí)解決實(shí)際問題的能力。1.2實(shí)驗(yàn)內(nèi)容問題描述問題描述：農(nóng)夫攜帶一只狼，一只羊，一棵白菜從和的左岸到達(dá)河的右岸，由于船只較小，農(nóng)夫每次只能攜帶一樣過河，在無人看管的情況下狼吃羊，羊吃白菜。1.3：實(shí)驗(yàn)輸出要求 要求輸出農(nóng)夫攜帶所有東西安全過河的步驟。2：程序設(shè)計(jì)分析2.1：實(shí)驗(yàn)內(nèi)容分析 農(nóng)夫需要多次駕船往返于河的左右兩岸，農(nóng)夫每次過河都會(huì)使農(nóng)夫，狼，羊，白菜的位置發(fā)生變化。利用四元組（農(nóng)夫，狼，羊，白菜）來表示各自所處于河的左岸右岸的位置，0表示河的左岸，1表示河的右岸。初始狀態(tài)時(shí)（0,0,0,0）都處在河的左岸，終態(tài)是（1，1,1,1）四者都處在河的右岸。共有16種狀態(tài)，但其中有些狀態(tài)不安全，刪除不安全的狀態(tài)，將安全的狀態(tài)按照合理的過河步驟聯(lián)系起來.（0,0,0，0）(1,0,1,0)(0,0,1,0)(1,1,1,0) (1,0,1,1)(0,1,0,0) (0,0,0,1)(1,1,0,1)(0,1,0,1)(1,1,1,1)安全過河狀態(tài)圖2.2主要函數(shù)模塊算法分析1：棧的相關(guān)函數(shù)PSeqStack Init_SeqStack(void)/棧的初始化int Empty_SeqStack(PSeqStack s) /判斷棧是否為空棧非空1表示?？誺oid Push_SeqStack(PSeqStack s,int x) /入棧 int Pop_SeqStack(PSeqStack s,int *x) /出棧int Size_SeqStack(PSeqStack s) /順序棧中元素的個(gè)數(shù)void Destroy_SeqStack(PSeqStack *S) /銷毀棧 2,：求結(jié)點(diǎn)直接后繼結(jié)點(diǎn)個(gè)數(shù)的函數(shù)int CountAdjoin(MGraph *G,int u) 3：查找狀態(tài)(f,w,s,v)在無向圖中的位置的函數(shù)int located(MGraph *G,int f,int w,int s,int v) 4：結(jié)點(diǎn)值安全狀態(tài)判斷函數(shù)int if_safe(int f,int w,int s,int v) 5：判斷農(nóng)夫過河的兩個(gè)狀態(tài)是否是相鄰的函數(shù)int if_connected(MGraph *G,int i,int j) 6：創(chuàng)建農(nóng)夫過河狀態(tài)的無向圖 void Creat_MGraph(MGraph *G) 7：廣優(yōu)度先遍歷 遍歷所有從狀態(tài)下標(biāo)u到狀態(tài)下標(biāo)v的路徑函數(shù)void BFS_path(MGraph *G,int u,int v) 8：輸出所有從狀態(tài)下標(biāo)為u到狀態(tài)下標(biāo)為v的所有簡單路徑void print_path(MGraph *G,int u,int v) 2.3部分函數(shù)源代碼 pathum 為狀態(tài)下標(biāo)u的直接后繼狀態(tài)下標(biāo) m表示狀態(tài)下標(biāo)u的直接后繼結(jié)點(diǎn)個(gè)數(shù)：int pathMaxVertexNumMaxVertexNum; 主要結(jié)構(gòu)：typedef struct int farmer;int wolf;int sheep;int vegetable;vertexType; /頂點(diǎn)結(jié)點(diǎn)類型 typedef structvertexType vertexMaxVertexNum;int edgesMaxVertexNumMaxVertexNum;int vertexNum;MGraph; /鄰接矩陣存儲(chǔ)結(jié)構(gòu)類型typedef struct int dataMAXSIZE;int top; /棧頂SeqStack,*PSeqStack;void BFS_path(MGraph *G,int u,int v) /深度優(yōu)先遍歷 從狀態(tài)下標(biāo)u到狀態(tài)下標(biāo)vint i,j,m,n; PSeqStack S;S=Init_SeqStack(); Push_SeqStack(S,v);visitedu=TRUE;/改變路徑頭結(jié)點(diǎn)的訪問標(biāo)志為TRUEPush_SeqStack(S,u); while(!Empty_SeqStack(S)Pop_SeqStack(S,&u);m=1;for(i=0;ivertexNum;i+) /判定后繼結(jié)點(diǎn)的個(gè)數(shù)及將其后繼結(jié)點(diǎn)訪問標(biāo)志置TRUEif(G-edgesui & !visitedi) pathum=i; /將下標(biāo)為U的后繼結(jié)點(diǎn)下標(biāo)賦給pathum m用來記錄直接后繼結(jié)點(diǎn)的個(gè)數(shù)visitedi=TRUE;m+;for(j=1;j2) /棧中元素個(gè)數(shù)大于2 則一直出棧Pop_SeqStack(S,&u);m=1;for(i=0;ivertexNum;i+)if(G-edgesui & !visitedi) /pathum 為狀態(tài)下標(biāo)u的直接后繼狀態(tài)下標(biāo) m表示狀態(tài)下標(biāo)u的后繼結(jié)點(diǎn)個(gè)數(shù)pathum=i;visitedi=TRUE;m+;Destroy_SeqStack(&S); /銷毀棧void print_path(MGraph *G,int u,int v) /輸出所有從狀態(tài)下標(biāo)為u到狀態(tài)下標(biāo)為v的所有簡單路徑int n,k,i,j,m,t,a,l;k=u;j=1;visitedu=FALSE; /改變第一個(gè)結(jié)點(diǎn)的訪問標(biāo)志 pathv1=-1; /將一條路徑的最后一個(gè)頂點(diǎn)的后繼結(jié)點(diǎn)下標(biāo)置為無窮大while(k!=-1) printf(ttNO%d:(%d,%d,%d,%d)n,j+,G-vertexk.farmer,G-vertexk.wolf,G-vertexk.sheep,G-vertexk.vegetable);m=CountAdjoin(G,k);if(m=0) /結(jié)束條件 后繼結(jié)點(diǎn)個(gè)數(shù)為零break;if(m!=1)for(i=m;i0;i-) /輸出某個(gè)結(jié)點(diǎn)后的所有分支后繼結(jié)點(diǎn)t=k;t=pathti;n=0;l=j;while(t!=-1) if(nvertext.farmer,G-vertext.wolf,G-vertext.sheep,G-vertext.vegetable);a=t;t=patht1;visitedt=FALSE;n+;elsebreak;printf(n);j=l;k=a;k=pathk1;3：實(shí)驗(yàn)結(jié)果結(jié)果分析：農(nóng)夫過河的安全步驟：NO1：農(nóng)夫，狼，羊，白菜都在河的左岸NO2:農(nóng)夫帶羊到河的右岸NO3:農(nóng)夫回到河的左岸NO4:農(nóng)夫帶狼到河的右岸 或者 農(nóng)夫帶白菜到河的右岸NO5:農(nóng)夫帶羊回到河的左岸 或者 農(nóng)夫帶羊回到河的左岸NO6:農(nóng)夫帶狼到河的右岸NO7:農(nóng)夫回到河的左岸NO8:農(nóng)夫帶羊到和的右岸4：實(shí)驗(yàn)心得通過農(nóng)夫過河的實(shí)驗(yàn)，使我初步了解解決一些復(fù)雜較難問題的思路和掌握了解決問題的方法。通過該實(shí)驗(yàn)的代碼編程過程中也進(jìn)一步提高了我對(duì)c語言的掌握，掌握了棧，深度廣度遍歷的算法，也提高了我對(duì)算法的學(xué)習(xí)設(shè)計(jì)能力，同時(shí)提高了編程調(diào)試的能力，使我遇到那些邏輯上的錯(cuò)誤，能通過自己一點(diǎn)一點(diǎn)的調(diào)試，搜尋邏輯錯(cuò)誤所在處。在編程調(diào)試中遇相關(guān)的問題時(shí)，讓我明白遇到問題不可怕，怕的是遇到問題不想解決或者沒有解決問題恒定的決心，即使一些問題在困難，當(dāng)時(shí)對(duì)遇到的可能絲毫沒有頭緒，只要一點(diǎn)點(diǎn)的對(duì)問題剖析，哪怕在困難的問題也會(huì)被解決。實(shí)驗(yàn)二1：實(shí)驗(yàn)要求：1.1：實(shí)驗(yàn)?zāi)康奶岣叻治鲈O(shè)計(jì)解決問題的能力，并掌握選擇策略的圖的深度優(yōu)先搜索等先關(guān)的知識(shí)。1.2：實(shí)驗(yàn)內(nèi)容問題描述 馬隨機(jī)放在國際象棋8*8的方格中，馬按照走馬的規(guī)則進(jìn)行移動(dòng)，要求馬走過每個(gè)格走過僅走過一次并且每個(gè)格都走過，編程求輸出馬走過的路徑1.3: 實(shí)驗(yàn)輸出輸出騎士周游的路徑2：程序設(shè)計(jì)分析2.1：實(shí)驗(yàn)內(nèi)容分析在國際象棋的棋盤上，馬共有八個(gè)可能的跳躍方向。設(shè)置一組坐標(biāo)增量來描述這八個(gè)條約方向：（1，2）（2，1）（2，-1）（1，-2）（-1，-2）（-2，-1）（-2，1）（-1，2）2.2：主要算法模塊分析void go(int n,int x,int y) 遞歸算法模塊 2.3: 主要源代碼#include #define N 8int dituNN = /棋盤初始化所有點(diǎn)為零0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0;int pathNN; /記錄周游路徑int flag=0; /結(jié)束標(biāo)記int incX=1,2,2,1,-1,-2,-2,-1; /指示方向 橫坐標(biāo)int incY=-2,-1,1,2,2,1,-1,-2; /指示方向 縱坐標(biāo)void go(int n,int x,int y)if (n=(N*N) /判斷是否走完整個(gè)地圖flag=1;pathxy=n;if (flag=1) /遞歸結(jié)束標(biāo)志return;pathxy=n; /將騎士走的路徑記錄dituxy=1; /標(biāo)記坐標(biāo)（x,y）點(diǎn)走過for (int i=0;i=0) & (x+incXi)=0) & (y+incYi)N) & (ditux+incXiy+incYi=0)go(n+1,x+incXi,y+incYi); /遞歸周游dituxy = 0; /8個(gè)方向中 如果探測方向不是合適的落馬點(diǎn) 則清除馬走過的標(biāo)記return;void main()printf(騎士從