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

数据结构实验五——修道士野人问题数据结构实验五——修道士野人问题全文共数据结构实验五——修道士野人问题全文共9页，当前为第1页。实验课名称：数据结构与程序设计实验实验名称：修道士野人问题班级：学号：姓名：时间：一、问题描述河的左岸有N个野人和N个修道士以及一条小船，修道士们想用这条小船把所有的人都运到河的右岸，但又受到以下限制：所有人都会划船，但船一次只能载C人在任意岸上，野人数不能超过修道士数，否则修道士将会被野人吃掉。现假定野人服从任意过河安排，需要规划出一种确保修道士安全的过河方案。二、数据结构设计typedefstruct{intnum1;//修道士intnum2;//野蛮人intan;//表示两岸}DataType;//三元组typedefstructNode{intdest;//邻接表的弧头结点序号structNode*next;}Edge;//邻接表单链表的结点结构体typedefstruct{DataTypedata;//结点数据元素intsorce;//邻接表的弧尾结点序号Edge*adj;//邻接边的头指针intpre;//指向此点的点的序号}AdjLHeight;//数组的数据元素类型结构体typedefstruct{AdjLHeighta[10000];//邻接表数组intnumOfVerts;//结点个数intnumOfEdges;//边个数}AdjLGraph;//邻接表结构体三、算法设计图的初始化在G图中插入结点数据结构实验五——数据结构实验五——修道士野人问题全文共9页，当前为第2页。在G图中插入边<v1,v2>图的撤销数据结构实验五——数据结构实验五——修道士野人问题全文共9页，当前为第3页。检查当前情况下，修道士是否安全用if语句判断，左岸右岸的修道士人数都必须不小于野人数目才可生成在船上修道士仍安全的情况打印安全渡河的过程数据结构实验五数据结构实验五——修道士野人问题全文共9页，当前为第4页。广度搜索建立表数据结构实验五数据结构实验五——修道士野人问题全文共9页，当前为第5页。数据结构实验五——数据结构实验五——修道士野人问题全文共9页，当前为第6页。四、界面设计野人和修道士人数N:野人和修道士人数N:船可乘人数C:（船所在岸的人数）（修野岸）船上人数[修道士，野人]右边岸上[修野岸]……(000)重复以上方式输出所有的渡河方式五、运行测试与分析输入输出实际12(111)船上人数[修道士，野人][11]右边岸上[000](000)√35(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](010)船上人数[修道士，野人][30]左边岸上[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]数据结构实验五——数据结构实验五——修道士野人问题全文共9页，当前为第7页。(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)数据结构实验五——修道士野人问题全文共9页，当前为第8页。数据结构实验五——修道士野人问题全文共9页，当前为第8页。(220)船上人数[修道士，野人][10]左边岸上[321](321)船上人数[修道士，野人][32]右边岸上[000](000)√23(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](211)船上人数[修道士，野人][21]右边岸上[000](000)(221)船上人数[修道士，野人][02]右边岸上[200](200)船上人数[修道士，野人][01]左边岸上[211](211)船上人数[修道士，野人][21]右边岸上[000](000)(221)船上人数[修道士，野人][11]右边岸上[110](110)船上