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

《数据结构实验五——修道士野人问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、//邻接表的弧头结点序号structNode*next;}Edge;//邻接表单链表的结点结构体typedefstruct{DataTypedata;//结点数据元素intsorce;//邻接表的弧尾结点序号Edge*adj;//邻接边的头指针intpre;//指向此点的点的序号}AdjLHeight;//数组的数据元素类型结构体typedefstruct{AdjLHeighta[10000];//邻接表数组intnumOfVerts;//结点个数intnumOfEdges;//边个数}AdjLGraph;//邻接表结构体三、算法设计1)图的初始化1)在G图中插入结点1)在G

3、图中插入边2)图的撤销1)检查当前情况下，修道士是否安全用if语句判断，左岸右岸的修道士人数都必须不小于野人数目才可2)生成在船上修道士仍安全的情况3)打印安全渡河的过程1)广度搜索建立表四、界面设计野人和修道士人数N:船可乘人数C:（船所在岸的人数）（修野岸）船上人数[修道士，野人]右边岸上[修野岸]……(000)重复以上方式输出所有的渡河方式五、运行测试与分析输入输出实际12(111)船上人数[修道士，野人][11]右边岸上[000](000)√35(331)船上人数[修道士，野人][32]右边岸上[010](010)船上人数[修道士，野人][10]左边岸上

4、[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](010)船上人数[修道士，野人][30]左边岸上[311](

5、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)船

6、上人数[修道士，野人][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)船上人数[修道

7、士，野人][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)船上人数[修