数据结构实验五-修道士野人问题

实验报告五实验课名称：数据结构与程序设计实验实验名称：修道士野人问题班级： 学号： 姓名： 时间：一、问题描述河的左岸有 N个野人和 N个修道士以及一条小船，修道士们想用这条小船把所有的人都运到河的右岸，但又受到以下限制：所有人都会划船，但船一次只能载 C人在任意岸上，野人数不能超过修道士数，否则修道士将会被野人吃掉。现假定野人服从任意过河安排，需要规划出一种确保修道士安全的过河方案。二、数据结构设计typedefstruct{intnum1;intnum2;intan;}DataType;

//修道士//野蛮人//表示两岸//三元组typedefstructNode{intdest;

//邻接表的弧头结点序号structNode*next;}Edge;

//邻接表单链表的结点结构体typedefstruct{DataTypedata;

//结点数据元素intsorce;

//邻接表的弧尾结点序号Edge*adj;

//邻接边的头指针intpre;

//指向此点的点的序号}AdjLHeight;

//数组的数据元素类型结构体typedefstruct{AdjLHeighta[10000];intnumOfVerts;}AdjLGraph;

//邻接表数组//结点个数//边个数//邻接表结构体三、算法设计1) 图的初始化在G图中插入结点在G图中插入边<v1,v2>图的撤销检查当前情况下，修道士是否安全用if语句判断，左岸右岸的修道士人数都必须不小于野人数目才可生成在船上修道士仍安全的情况打印安全渡河的过程广度搜索建立表四、界面设计野人和修道士人数

N:船可乘人数 C:（船所在岸的人数）

（修

野 岸）

船上人数

[修道士，野人

]

右边岸上

[修 野 岸

]⋯⋯(000)重复以上方式输出所有的渡河方式五、运行测试与分析输入输出实际(111)船上人数[修道士，野人][11]右边岸上[000]12(000)√(331)船上人数[修道士，野人][32]右边岸上[010](010)船上人数[修道士，野人][10]左边岸上[111](111)船上人数[修道士，野人][11]右边岸上[000](000)(331)船上人数[修道士，野人][32]右边岸上[010](010)船上人数[修道士，野人][01]左边岸上[021](021)船上人数[修道士，野人][02]右边岸上[000](000)(331)船上人数[修道士，野人][32]右边岸上[010](010)船上人数[修道士，野人][02]左边岸上[031](031)船上人数[修道士，野人][03]右边岸上[000](000)(331)船上人数[修道士，野人][32]右边岸上[010]35船上人数[修道士，野人][30]左边岸上√(010)[311](311)船上人数[修道士，野人][31]右边岸上[000](000)(331)船上人数[修道士，野人][32]右边岸上[010](010)船上人数[修道士，野人][21]左边岸上[221](221)船上人数[修道士，野人][22]右边岸上[000](000)(331)船上人数[修道士，野人][32]右边岸上[010](010)船上人数[修道士，野人][31]左边岸上[321](321)船上人数[修道士，野人][32]右边岸上[000](000)(331)船上人数[修道士，野人][22]右边岸上[110](110)船上人数[修道士，野人][20]左边岸上[311](311) 船上人数 [修道士，野人 ][31] 右边岸上 [000](000)(331)船上人数[修道士，野人][22]右边岸上[110](110)船上人数[修道士，野人][11]左边岸上[221](221)船上人数[修道士，野人][22]右边岸上[000](000)(331)船上人数[修道士，野人][22]右边岸上[110](110)船上人数[修道士，野人][21]左边岸上[321](321)船上人数[修道士，野人][32]右边岸上[000](000)(331)船上人数[修道士，野人][31]右边岸上[020](020)船上人数[修道士，野人][01]左边岸上[031](031)船上人数[修道士，野人][03]右边岸上[000](000)(331)船上人数[修道士，野人][31]右边岸上[020](020)船上人数[修道士，野人][20]左边岸上[221](221)船上人数[修道士，野人][22]右边岸上[000](000)(331)船上人数[修道士，野人][31]右边岸上[020](020)船上人数[修道士，野人][30]左边岸上[321](321)船上人数[修道士，野人][32]右边岸上[000](000)(331)船上人数[修道士，野人][03]右边岸上[300](300)船上人数[修道士，野人][01]左边岸上[311](311)船上人数[修道士，野人][31]右边岸上[000](000)(331)船上人数[修道士，野人][03]右边岸上[300](300)船上人数[修道士，野人][02]左边岸上[321](321)船上人数[修道士，野人][32]右边岸上[000](000)(331)船上人数[修道士，野人][02]右边岸上[310](310)船上人数[修道士，野人][01]左边岸上[321](321)船上人数[修道士，野人][32]右边岸上[000](000)(331) 船上人数 [修道士，野人 ][11] 右边岸上 [220](220)船上人数[修道士，野人][10]左边岸上[321](321)船上人数[修道士，野人][32]右边岸上[000](000)(221)船上人数[修道士，野人][21]右边岸上[010](010)船上人数[修道士，野人][10]左边岸上[111](111)船上人数[修道士，野人][11]右边岸上[000](000)(221)船上人数[修道士，野人][21]右边岸上[010](010)船上人数[修道士，野人][01]左边岸上[021](021)船上人数[修道士，野人][02]右边岸上[000](000)(221)船上人数[修道士，野人][21]右边岸上[010](010)船上人数[修道士，野人][20]左边岸上[211]23船上人数[修道士，野人][21]右边岸上√(211)[000](000)(221)船上人数[修道士，野人][02]右边岸上[200](200)船上人数[修道士，野人][01]左边岸上[211](211)船上人数[修道士，野人][21]右边岸上[000](000)(221)船上人数[修道士，野人][11]右边岸上[110](110)船上