數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)五-修道士野人問題

實(shí)驗(yàn)報(bào)告五實(shí)驗(yàn)課名稱：數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)實(shí)驗(yàn)實(shí)驗(yàn)名稱：修道士野人問題班級(jí)： 學(xué)號(hào)： 姓名： 時(shí)間：一、問題描述河的左岸有 N個(gè)野人和 N個(gè)修道士以及一條小船，修道士們想用這條小船把所有的人都運(yùn)到河的右岸，但又受到以下限制：所有人都會(huì)劃船，但船一次只能載 C人在任意岸上，野人數(shù)不能超過修道士數(shù)，否則修道士將會(huì)被野人吃掉?，F(xiàn)假定野人服從任意過河安排，需要規(guī)劃出一種確保修道士安全的過河方案。二、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)typedefstruct{intnum1;intnum2;intan;}DataType;

//修道士//野蠻人//表示兩岸//三元組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];intnumOfVerts;}AdjLGraph;

//鄰接表數(shù)組//結(jié)點(diǎn)個(gè)數(shù)//邊個(gè)數(shù)//鄰接表結(jié)構(gòu)體三、算法設(shè)計(jì)1) 圖的初始化在G圖中插入結(jié)點(diǎn)在G圖中插入邊<v1,v2>圖的撤銷檢查當(dāng)前情況下，修道士是否安全用if語句判斷，左岸右岸的修道士人數(shù)都必須不小于野人數(shù)目才可生成在船上修道士仍安全的情況打印安全渡河的過程廣度搜索建立表四、界面設(shè)計(jì)野人和修道士人數(shù)

N:船可乘人數(shù) C:（船所在岸的人數(shù)）

（修

野 岸）

船上人數(shù)

[修道士，野人

]

右邊岸上

[修 野 岸

]??(000)重復(fù)以上方式輸出所有的渡河方式五、運(yùn)行測(cè)試與分析輸入輸出實(shí)際(111)船上人數(shù)[修道士，野人][11]右邊岸上[000]12(000)√(331)船上人數(shù)[修道士，野人][32]右邊岸上[010](010)船上人數(shù)[修道士，野人][10]左邊岸上[111](111)船上人數(shù)[修道士，野人][11]右邊岸上[000](000)(331)船上人數(shù)[修道士，野人][32]右邊岸上[010](010)船上人數(shù)[修道士，野人][01]左邊岸上[021](021)船上人數(shù)[修道士，野人][02]右邊岸上[000](000)(331)船上人數(shù)[修道士，野人][32]右邊岸上[010](010)船上人數(shù)[修道士，野人][02]左邊岸上[031](031)船上人數(shù)[修道士，野人][03]右邊岸上[000](000)(331)船上人數(shù)[修道士，野人][32]右邊岸上[010]35船上人數(shù)[修道士，野人][30]左邊岸上√(010)[311](311)船上人數(shù)[修道士，野人][31]右邊岸上[000](000)(331)船上人數(shù)[修道士，野人][32]右邊岸上[010](010)船上人數(shù)[修道士，野人][21]左邊岸上[221](221)船上人數(shù)[修道士，野人][22]右邊岸上[000](000)(331)船上人數(shù)[修道士，野人][32]右邊岸上[010](010)船上人數(shù)[修道士，野人][31]左邊岸上[321](321)船上人數(shù)[修道士，野人][32]右邊岸上[000](000)(331)船上人數(shù)[修道士，野人][22]右邊岸上[110](110)船上人數(shù)[修道士，野人][20]左邊岸上[311](311) 船上人數(shù) [修道士，野人 ][31] 右邊岸上 [000](000)(331)船上人數(shù)[修道士，野人][22]右邊岸上[110](110)船上人數(shù)[修道士，野人][11]左邊岸上[221](221)船上人數(shù)[修道士，野人][22]右邊岸上[000](000)(331)船上人數(shù)[修道士，野人][22]右邊岸上[110](110)船上人數(shù)[修道士，野人][21]左邊岸上[321](321)船上人數(shù)[修道士，野人][32]右邊岸上[000](000)(331)船上人數(shù)[修道士，野人][31]右邊岸上[020](020)船上人數(shù)[修道士，野人][01]左邊岸上[031](031)船上人數(shù)[修道士，野人][03]右邊岸上[000](000)(331)船上人數(shù)[修道士，野人][31]右邊岸上[020](020)船上人數(shù)[修道士，野人][20]左邊岸上[221](221)船上人數(shù)[修道士，野人][22]右邊岸上[000](000)(331)船上人數(shù)[修道士，野人][31]右邊岸上[020](020)船上人數(shù)[修道士，野人][30]左邊岸上[321](321)船上人數(shù)[修道士，野人][32]右邊岸上[000](000)(331)船上人數(shù)[修道士，野人][03]右邊岸上[300](300)船上人數(shù)[修道士，野人][01]左邊岸上[311](311)船上人數(shù)[修道士，野人][31]右邊岸上[000](000)(331)船上人數(shù)[修道士，野人][03]右邊岸上[300](300)船上人數(shù)[修道士，野人][02]左邊岸上[321](321)船上人數(shù)[修道士，野人][32]右邊岸上[000](000)(331)船上人數(shù)[修道士，野人][02]右邊岸上[310](310)船上人數(shù)[修道士，野人][01]左邊岸上[321](321)船上人數(shù)[修道士，野人][32]右邊岸上[000](000)(331) 船上人數(shù) [修道士，野人 ][11] 右邊岸上 [220](220)船上人數(shù)[修道士，野人][10]左邊岸上[321](321)船上人數(shù)[修道士，野人][32]右邊岸上[000](000)(221)船上人數(shù)[修道士，野人][21]右邊岸上[010](010)船上人數(shù)[修道士，野人][10]左邊岸上[111](111)船上人數(shù)[修道士，野人][11]右邊岸上[000](000)(221)船上人數(shù)[修道士，野人][21]右邊岸上[010](010)船上人數(shù)[修道士，野人][01]左邊岸上[021](021)船上人數(shù)[修道士，野人][02]右邊岸上[000](000)(221)船上人數(shù)[修道士，野人][21]右邊岸上[010](010)船上人數(shù)[修道士，野人][20]左邊岸上[211]23船上人數(shù)[修道士，野人][21]右邊岸上√(211)[000](000)(221)船上人數(shù)[修道士，野人][02]右邊岸上[200](200)船上人數(shù)[修道士，野人][01]左邊岸上[211](211)船上人數(shù)[修道士，野人][21]右邊岸上[000](000)(221)船上人數(shù)[修道士，野人][11]右邊岸上[110](110)船上