數(shù)據(jù)結(jié)構(gòu)第7章修道士實(shí)驗(yàn)報(bào)告

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告第七章實(shí)驗(yàn)名稱：修道士野人問題實(shí)驗(yàn)類型：綜合性實(shí)驗(yàn)班級(jí)：學(xué)號(hào)：姓名：實(shí)驗(yàn)日期：2014年5月21日問題描述河的左岸有N個(gè)野人和N個(gè)修道士以及一條小船，修道士們想用這條小船把所有的人都運(yùn)到河的右岸，但又受到以下限制：修道士和野人都會(huì)劃船，但船一次只能載C人。在任何岸邊，為了防止野人侵犯修道士，野人數(shù)不能超過修道士數(shù)，否則修道士將會(huì)被野人吃掉。假定野人愿意服從任何一種過河的安排，本設(shè)計(jì)的主要任務(wù)是規(guī)劃出一種確保修道士安全的過河方案。數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)用一個(gè)三元組（num1，num2，an）表示渡河過程中的各個(gè)狀態(tài)。num1表示左岸上修道士的個(gè)數(shù)，num2表示左岸上野人的個(gè)數(shù)，an表示小船位置（0-在右岸上，1-在左岸上）。定義一個(gè)結(jié)構(gòu)體，用于存放各個(gè)時(shí)刻的狀態(tài)：typedefstruct{ intnum1;//修道士人數(shù) intnum2;//野蠻人人數(shù) intan;//表示兩岸，0在右岸，1在左岸}DataType;用鄰接表存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)圖的操作，其存儲(chǔ)結(jié)構(gòu)為：typedefstructNode{ intdest; //鄰接表的弧頭結(jié)點(diǎn)序號(hào) structNode*next; }Edge; //鄰接表單鏈表的結(jié)點(diǎn)結(jié)構(gòu)體typedefstruct{ DataTypedata; //結(jié)點(diǎn)數(shù)據(jù)元素 intsorce; //鄰接表的弧尾結(jié)點(diǎn)序號(hào) Edge*adj; //鄰接邊的頭指針 intpre; //指向此點(diǎn)的點(diǎn)的序號(hào)}AdjLHeight; //數(shù)組的數(shù)據(jù)元素類型結(jié)構(gòu)體typedefstruct{ AdjLHeighta[10000]; //鄰接表數(shù)組 intnumOfVerts; /結(jié)點(diǎn)個(gè)數(shù) intnumOfEdges; //邊個(gè)數(shù)}AdjLGraph; //鄰接表結(jié)構(gòu)體算法設(shè)計(jì)一側(cè)的野人數(shù)目和修道士數(shù)目以及船在哪一岸共同構(gòu)成一種狀態(tài)，分析一會(huì)發(fā)現(xiàn)合法的狀態(tài)是有限且固定的。此時(shí)這個(gè)問題的求解便類似于尋路問題，已知兩個(gè)結(jié)點(diǎn)和所有節(jié)點(diǎn)間的連接關(guān)系，求兩結(jié)點(diǎn)之間的一條路徑，簡(jiǎn)單地進(jìn)行廣度優(yōu)先搜索即可。根據(jù)給出的小船上的位置數(shù)量，生成小船上的安全狀態(tài)，即在船上的時(shí)候修道士的人數(shù)也要比野人的數(shù)量要多（除非修道士人數(shù)為0）。渡船優(yōu)先規(guī)則：左岸一次運(yùn)走的人越多越好（即左岸運(yùn)多人優(yōu)先），同時(shí)野人優(yōu)先運(yùn)走；右岸一次運(yùn)走的人越少越好（即右岸運(yùn)少人優(yōu)先），同時(shí)修道士?jī)?yōu)先運(yùn)走。類似于操作系統(tǒng)中的銀行家算法的安全性檢測(cè)，即讓修道士跟野人上船后，檢測(cè)當(dāng)船到達(dá)對(duì)岸后，兩岸修道士的安全狀態(tài)，若修道士安全，則將此結(jié)點(diǎn)加入到鄰接表中。采用廣度優(yōu)先搜索，得到一條通路將其輸出即可。部分關(guān)鍵程序：intfindfa(DataTypex)//生成在船上修道士仍安全的情況{ inti=0,a,b,t=0;//從始案到末岸的狀態(tài) if(x.an) { a=0;b=c-a; while(a+b>=1) { t++; while(b>=0) { fa[i].num1=a; fa[i].num2=b; i++; a++; b--; } a=0; b=c-a-t; } } else//從末岸到始岸的狀態(tài) { a=1;b=0;t=0; while(a+b<=c) { t++; while(a>=0) { fa[i].num1=a*(-1); fa[i].num2=b*(-1); i++; a--; b++; } a=fa[0].num1*(-1)+t; b=0; } } returni;}intprint(AdjLGraph*p,intg)//打印安全渡河的過程{DataTypeb[1000];inti=0;while(g!=-1){b[i++]=p->a[g].data;g=p->a[g].pre;}while((--i)>-1){ printf("(%d%d%d)",b[i].num1,b[i].num2,b[i].an);if(!(b[i].num1==0&&b[i].num2==0&&b[i].an==0)){ if(b[i].an==1) printf("船上人數(shù)[修道士，野人][%d%d]右邊岸上[%d%d0]\n",b[i].num1-b[i-1].num1,b[i].num2-b[i-1].num2,b[i-1].num1,b[i-1].num2); else printf("船上人數(shù)[修道士，野人][%d%d]左邊岸上[%d%d1]\n",(b[i].num1-b[i-1].num1)*(-1),(-1)*(b[i].num2-b[i-1].num2),b[i-1].num1,b[i-1].num2);}else printf("\n");}printf("\n"); return1;}voidwork(AdjLGraph*p) //廣度搜索建立表{ DataTypetem; inti,flag1,g=0,j,count=0,k=0,t; while(p->a[k].data.an!=-1) { j=findfa(p->a[k].data);for(i=0;i<j;i++) { tem.num1=p->a[k].data.num1-fa[i].num1; tem.num2=p->a[k].data.num2-fa[i].num2; tem.an=1-p->a[k].data.an; if(check(tem)) { flag1=1; t=k;while(t!=-1) { if(tem.num1==p->a[t].data.num1&&tem.num2==p->a[t].data.num2&&tem.an==p->a[t].data.an) { flag1=0; break; } t--; } if(flag1==1) { g++; p->a[g].pre=k; InsertVertex(p,g,tem); InsertEdge(p,k,g); if(tem.num1==0&&tem.num2==0&&tem.an==0) { count++; print(p,g); } } } } k++; } if(count==0) printf("不能渡河\n");}4.運(yùn)行、測(cè)試與分析5.實(shí)驗(yàn)收獲及思考遇到的問題：1.無法編譯。2.不知道選用什么樣的數(shù)據(jù)結(jié)構(gòu)。3.廣度優(yōu)先遍歷結(jié)果不正確。解決辦法：1.通過錯(cuò)誤提示，發(fā)現(xiàn)均是變量書寫錯(cuò)誤，改正后解決問題。2.和同學(xué)討論、上網(wǎng)查詢相關(guān)資料后確定數(shù)據(jù)結(jié)構(gòu)。3.逐步執(zhí)行程序并查看運(yùn)行過程的結(jié)果，找出問題所在，修改后解決問題。實(shí)驗(yàn)的收獲：通過此次編程感覺收獲了好多，又一次復(fù)習(xí)了圖的知識(shí)，并親自編寫了廣度遍歷的程序。同時(shí)也意識(shí)到知識(shí)不能只死學(xué)，要學(xué)會(huì)分析問題，把已經(jīng)學(xué)過的知識(shí)用到解決實(shí)際問題中，比如這道我們小學(xué)就見過的過河問題。同時(shí)編寫程序要按部就班，從最基本的做起，如果沒有頭緒可以上網(wǎng)查閱相關(guān)資料，看看其他人是怎么解決這個(gè)問題的。多積累相關(guān)知識(shí)，并多加練習(xí)，提高編程能力。附錄：#include<stdio.h> #include<stdlib.h>#include<malloc.h>intn,c;typedefstruct{ intnum1;//修道士 intnum2;//野蠻人 intan;//表示兩岸}DataType;DataTypefa[5000];typedefstructNode{ intdest; //鄰接表的弧頭結(jié)點(diǎn)序號(hào) structNode*next; }Edge; //鄰接表單鏈表的結(jié)點(diǎn)結(jié)構(gòu)體typedefstruct{ DataTypedata; //結(jié)點(diǎn)數(shù)據(jù)元素 intsorce; //鄰接表的弧尾結(jié)點(diǎn)序號(hào) Edge*adj; //鄰接邊的頭指針 intpre; //指向此點(diǎn)的點(diǎn)的序號(hào)}AdjLHeight; //數(shù)組的數(shù)據(jù)元素類型結(jié)構(gòu)體typedefstruct{ AdjLHeighta[10000]; //鄰接表數(shù)組 intnumOfVerts; //結(jié)點(diǎn)個(gè)數(shù) intnumOfEdges; //邊個(gè)數(shù)}AdjLGraph; //鄰接表結(jié)構(gòu)體voidAdjInitiate(AdjLGraph*G) //圖的初始化 { inti; G->numOfEdges=0; G->numOfVerts=0; for(i=0;i<10000;i++) { G->a[i].sorce=i;//置鄰接邊的弧頭結(jié)點(diǎn)序號(hào) G->a[i].adj=NULL;//置鄰接邊單鏈表頭指針初值 G->a[i].data.an=-1; G->a[i].pre=-1; }}voidInsertVertex(AdjLGraph*G,inti,DataTypevertex) //在G圖中插入結(jié)點(diǎn){ if(i>=0&&i<10000) { G->a[i].data.num1=vertex.num1; G->a[i].data.num2=vertex.num2; G->a[i].data.an=vertex.an; G->numOfVerts++; } elseprintf("結(jié)點(diǎn)越界!\n");}voidInsertEdge(AdjLGraph*G,intv1,intv2) //在G圖中插入邊<v1,v2> { Edge*p; if(v1<0||v1>=G->numOfVerts||v2<0||v2>G->numOfVerts) { printf("參數(shù)v1或v2越界出錯(cuò)!"); exit(0); } p=(Edge*)malloc(sizeof(Edge));/*申請(qǐng)鄰接邊單鏈表結(jié)點(diǎn)空間*/ p->dest=v2;/*置鄰接邊弧頭序號(hào)*/ p->next=G->a[v1].adj;/*新結(jié)點(diǎn)插入單鏈表的表頭*/ G->a[v1].adj=p;/*頭指針指向新的單鏈表表頭*/ G->numOfEdges++;/*邊個(gè)數(shù)加1*/}voidAdjDestroy(AdjLGraph*G){ //G圖的撤銷 inti; Edge*p,*q; for(i=0;i<G->numOfVerts;i++) { p=G->a[i].adj; while(p!=NULL) { q=p->next; free(p); p=q; } }}intcheck(DataTypex)//檢查當(dāng)前情況下，修道士是否安全{if((x.num1>=x.num2||x.num1==0)&&((n-x.num1)>=(n-x.num2)||x.num1==n)&&x.num1>=0&&x.num1<=n&&x.num2>=0&&x.num2<=n)return1;elsereturn0;}intfindfa(DataTypex)//生成在船上修道士仍安全的情況{ inti=0,a,b,t=0;//從始案到末岸的狀態(tài) if(x.an) { a=0;b=c-a; while(a+b>=1) { t++; while(b>=0) { fa[i].num1=a; fa[i].num2=b; i++; a++; b--; } a=0; b=c-a-t; } } else//從末岸到始岸的狀態(tài) { a=1;b=0;t=0; while(a+b<=c) { t++; while(a>=0) { fa[i].num1=a*(-1); fa[i].num2=b*(-1); i++; a--; b++; } a=fa[0].num1*(-1)+t; b=0; } } returni;}intprint(AdjLGraph*p,intg)//打印安全渡河的過程{DataTypeb[1000];inti=0;while(g!=-1){b[i++]=p->a[g].data;g=p->a[g].pre;}while((--i)>-1){ printf("(%d%d%d)",b[i].num1,b[i].num2,b[i].an);if(!(b[i].num1==0&&b[i].num2==0&&b[i].an==0)){ if(b[i].an==1) printf("船上人數(shù)[修道士，野人][%d%d]右邊岸上[%d%d0]\n",b[i].num1-b[i-1].num1,b[i].num2-b[i-1].num2,b[i-1].num1,b[i-1].num2); else printf("船上人數(shù)[修道士，野人][%d%d]左邊岸上[%d%d1]\n",(b[i].num1-b[i-1].num1)*(-1),(-1)*(b[i].num2-b[i-1].num2),b[i-1].num1,b[i-1].num2);}else printf("\n");}printf("\n"); return1;}voidwork(AdjLGraph*p) //廣度搜索建立表{ DataTypetem; inti,flag1,g=0,j,count=0,k=0,t; while(p->a[k].data.an!=-1) { j=findfa(p->a[k].data);for(i=0;i<j;i++) { tem.num1=p->a[k].data.num1-fa[i].num1; tem.num2=p->a[k].data.num2-fa[i].num2; tem.an=1-p->a[k].data.an