数据结构第7章修道士实验报告

《数据结构第7章修道士实验报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、实验报告第七章实验名称:实验类型:班级：学号：姓名：实验日期:修道士野人问题综合性实验2014年5月21日1.问题描述河的左岸有N个野人和N个修道士以及一条小船，修道士们想用这条小船把所有的人都运到河的右岸，但又受到以下限制：•修道士和野人都会划船，但船一次只能载C人。•在任何岸边，为了防止野人侵犯修道士，野人数不能超过修道士数，否则修道士将会被野人吃掉。假定野人愿意服从任何一种过河的安排，本设计的主要任务是规划出一种确保修道士安全的过河方案。2.数据结构设计用一个三元组（numl，num2,an）表示渡河过

2、程中的各个状态。numl表示左岸上修道丄•的个数，ntim2表示左岸上野人的个数，an表示小船位置（0•在右岸上，1-在左岸上）。定义一个结构体，用于存放各个时刻的状态：typedefstruct{intnuml;//修道士人数intniim2;//野蛮人人数intan;//表示两岸，0在右岸，1在左岸}DataType;用邻接表存储结构实现阁的操作，其存储结构为：typedefstructNode{intdest;//邻接表的弧头结点序号structNode*next;//邻接表单链表的结点结构体}Edge

3、;typedefstructDataTypedata;intsorce;Edge*adj;intpre;JAdjLHeight;typedefstruct{AdjLHeighta[10000];intnumOfVerts;intnumOfEdges;}AdjLGraph;//结点数据元素//邻接表的弧尾结点序号//邻接边的头指针//指向此点的点的序号//数组的数据元素类型结构体//邻接表数组/结点个数//边个数//邻接表结构体1.算法设计一侧的野人数目和修道士数R以及船在哪一岸共同构成一种状态，分析一会发现合

4、法的状态是有限且同定的。此吋这个问题的求解便类似于寻路问题，已知两个结点和所有节点间的连接关系，求两结点之间的一条路径，简单地进行广度优先搜索即可。根据给出的小船上的位置数量，生成小船上的安全状态，即在船上的吋候修道士的人数也要比野人的数量要多（除非修道士人数为0）。渡船优先规则：左岸一次运走的人越多越好（即左岸运多人优先），同时野人优先运走；右岸一次运走的人越少越好（即右岸运少人优先），同时修道士优先运走。类似于操作系统中的银行家算法的安全性检测，即让修道士跟野人上船后，检测当船到达对岸后，两岸修道士的安全

5、状态，若修道士安全，则将此结点加入到邻接表中。采用广度优先搜索，得到一条通路将其输出即可。部分关键程序：intfindfa（DataTypex）//生成在船上修道士仍安全的情况{inti=O，a，b，t=O;//从始案到末岸的状态if（x.an）{a=0;b=c-a;while（a+b>=1）{t++；while（b〉=0）{fa[i].numl=a;fa[i].num2=b;i++；a++;b-;}a=0;b=c-a-t;}}else//从末岸到始岸的状态{a=l;b=O;t=O;while(a+b<=c)

6、{t++;while(a>=0){fa[i].numl=a*(-l);fa[i].num2=b*(-l);i++;a--;b++;}a=fa[O].numl*(-l)+t;b=0;}}returni;}intprint(AdjLGraph*p,intg)//打印安全渡河的过程{DataTypeb[1000];inti=0;while(g!=-l){b[i++]=p->a[g].data;g=p->a[g].pre;}while((--i)〉-l){printf("(%d%d%d)",b[i].numl,b[i

7、].num2,b[i].an);if(!(b[i].numl==0&&b[i].num2==0&&b[i].an==0)){if(bfil.an==l)printff船上人数[修道士，野人][%d%d]右边岸上[%d%dO]’’，b[i].num1-b[i-lJ.numl，b[i].num2-b[i-l].num2,b[i-1].num1，b[i-1].num2);elseprintf("船上人数[修道士，野人][%d%d]左边岸上[%d%dI]"，(b[i].numl-b[i-l].numl)*(-

8、l)，(-l)*(b[i].num2-b[i-l].num2)，b[i-l].numl，b[i-l].num2);}elseprintf(n");}printf(Mn);return1;}voidwork(AdjLGraph*p)//广度搜索建立表{DataTypetem;inti,flag1,g=0,j,count=0,k=0,t;while(p->a[k].data.an!=-1){j=