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

数据结构实验报告第七章实验名称：修道士野人问题实验类型：综合性实验班级：学号：姓名：实验日期：2014年5月21日问题描述河的左岸有N个野人和N个修道士以及一条小船，修道士们想用这条小船把所有的人都运到河的右岸，但又受到以下限制：修道士和野人都会划船，但船一次只能载C人。在任何岸边，为了防止野人侵犯修道士，野人数不能超过修道士数，否则修道士将会被野人吃掉。假定野人愿意服从任何一种过河的安排，本设计的主要任务是规划出一种确保修道士安全的过河方案。数据结构设计用一个三元组（num1，num2，an）表示渡河过程中的各个状态。num1表示左岸上修道士的个数，num2表示左岸上野人的个数，an表示小船位置（0-在右岸上，1-在左岸上）。定义一个结构体，用于存放各个时刻的状态：typedefstruct{ intnum1;//修道士人数 intnum2;//野蛮人人数 intan;//表示两岸，0在右岸，1在左岸}DataType;用邻接表存储结构实现图的操作，其存储结构为：typedefstructNode{ intdest; //邻接表的弧头结点序号 structNode*next; }Edge; //邻接表单链表的结点结构体typedefstruct{ DataTypedata; //结点数据元素 intsorce; //邻接表的弧尾结点序号 Edge*adj; //邻接边的头指针 intpre; //指向此点的点的序号}AdjLHeight; //数组的数据元素类型结构体typedefstruct{ AdjLHeighta[10000]; //邻接表数组 intnumOfVerts; /结点个数 intnumOfEdges; //边个数}AdjLGraph; //邻接表结构体算法设计一侧的野人数目和修道士数目以及船在哪一岸共同构成一种状态，分析一会发现合法的状态是有限且固定的。此时这个问题的求解便类似于寻路问题，已知两个结点和所有节点间的连接关系，求两结点之间的一条路径，简单地进行广度优先搜索即可。根据给出的小船上的位置数量，生成小船上的安全状态，即在船上的时候修道士的人数也要比野人的数量要多（除非修道士人数为0）。渡船优先规则：左岸一次运走的人越多越好（即左岸运多人优先），同时野人优先运走；右岸一次运走的人越少越好（即右岸运少人优先），同时修道士优先运走。类似于操作系统中的银行家算法的安全性检测，即让修道士跟野人上船后，检测当船到达对岸后，两岸修道士的安全状态，若修道士安全，则将此结点加入到邻接表中。采用广度优先搜索，得到一条通路将其输出即可。部分关键程序：intfindfa(DataTypex)//生成在船上修道士仍安全的情况{ inti=0,a,b,t=0;//从始案到末岸的状态 if(x.an) { a=0;b=c-a; while(a+b>=1) { t++; while(b>=0) { fa[i].num1=a; fa[i].num2=b; i++; a++; b--; } a=0; b=c-a-t; } } else//从末岸到始岸的状态 { a=1;b=0;t=0; while(a+b<=c) { t++; while(a>=0) { fa[i].num1=a*(-1); fa[i].num2=b*(-1); i++; a--; b++; } a=fa[0].num1*(-1)+t; b=0; } } returni;}intprint(AdjLGraph*p,intg)//打印安全渡河的过程{DataTypeb[1000];inti=0;while(g!=-1){b[i++]=p->a[g].data;g=p->a[g].pre;}while((--i)>-1){ printf("(%d%d%d)",b[i].num1,b[i].num2,b[i].an);if(!(b[i].num1==0&&b[i].num2==0&&b[i].an==0)){ if(b[i].an==1) printf("船上人数[修道士，野人][%d%d]右边岸上[%d%d0]\n",b[i].num1-b[i-1].num1,b[i].num2-b[i-1].num2,b[i-1].num1,b[i-1].num2); else printf("船上人数[修道士，野人][%d%d]左边岸上[%d%d1]\n",(b[i].num1-b[i-1].num1)*(-1),(-1)*(b[i].num2-b[i-1].num2),b[i-1].num1,b[i-1].num2);}else printf("\n");}printf("\n"); return1;}voidwork(AdjLGraph*p) //广度搜索建立表{ DataTypetem; inti,flag1,g=0,j,count=0,k=0,t; while(p->a[k].data.an!=-1) { j=findfa(p->a[k].data);for(i=0;i<j;i++) { tem.num1=p->a[k].data.num1-fa[i].num1; tem.num2=p->a[k].data.num2-fa[i].num2; tem.an=1-p->a[k].data.an; if(check(tem)) { flag1=1; t=k;while(t!=-1) { if(tem.num1==p->a[t].data.num1&&tem.num2==p->a[t].data.num2&&tem.an==p->a[t].data.an) { flag1=0; break; } t--; } if(flag1==1) { g++; p->a[g].pre=k; InsertVertex(p,g,tem); InsertEdge(p,k,g); if(tem.num1==0&&tem.num2==0&&tem.an==0) { count++; print(p,g); } } } } k++; } if(count==0) printf("不能渡河\n");}4.运行、测试与分析5.实验收获及思考遇到的问题：1.无法编译。2.不知道选用什么样的数据结构。3.广度优先遍历结果不正确。解决办法：1.通过错误提示，发现均是变量书写错误，改正后解决问题。2.和同学讨论、上网查询相关资料后确定数据结构。3.逐步执行程序并查看运行过程的结果，找出问题所在，修改后解决问题。实验的收获：通过此次编程感觉收获了好多，又一次复习了图的知识，并亲自编写了广度遍历的程序。同时也意识到知识不能只死学，要学会分析问题，把已经学过的知识用到解决实际问题中，比如这道我们小学就见过的过河问题。同时编写程序要按部就班，从最基本的做起，如果没有头绪可以上网查阅相关资料，看看其他人是怎么解决这个问题的。多积累相关知识，并多加练习，提高编程能力。附录：#include<stdio.h> #include<stdlib.h>#include<malloc.h>intn,c;typedefstruct{ intnum1;//修道士 intnum2;//野蛮人 intan;//表示两岸}DataType;DataTypefa[5000];typedefstructNode{ intdest; //邻接表的弧头结点序号 structNode*next; }Edge; //邻接表单链表的结点结构体typedefstruct{ DataTypedata; //结点数据元素 intsorce; //邻接表的弧尾结点序号 Edge*adj; //邻接边的头指针 intpre; //指向此点的点的序号}AdjLHeight; //数组的数据元素类型结构体typedefstruct{ AdjLHeighta[10000]; //邻接表数组 intnumOfVerts; //结点个数 intnumOfEdges; //边个数}AdjLGraph; //邻接表结构体voidAdjInitiate(AdjLGraph*G) //图的初始化 { inti; G->numOfEdges=0; G->numOfVerts=0; for(i=0;i<10000;i++) { G->a[i].sorce=i;//置邻接边的弧头结点序号 G->a[i].adj=NULL;//置邻接边单链表头指针初值 G->a[i].data.an=-1; G->a[i].pre=-1; }}voidInsertVertex(AdjLGraph*G,inti,DataTypevertex) //在G图中插入结点{ if(i>=0&&i<10000) { G->a[i].data.num1=vertex.num1; G->a[i].data.num2=vertex.num2; G->a[i].data.an=vertex.an; G->numOfVerts++; } elseprintf("结点越界!\n");}voidInsertEdge(AdjLGraph*G,intv1,intv2) //在G图中插入边<v1,v2> { Edge*p; if(v1<0||v1>=G->numOfVerts||v2<0||v2>G->numOfVerts) { printf("参数v1或v2越界出错!"); exit(0); } p=(Edge*)malloc(sizeof(Edge));/*申请邻接边单链表结点空间*/ p->dest=v2;/*置邻接边弧头序号*/ p->next=G->a[v1].adj;/*新结点插入单链表的表头*/ G->a[v1].adj=p;/*头指针指向新的单链表表头*/ G->numOfEdges++;/*边个数加1*/}voidAdjDestroy(AdjLGraph*G){ //G图的撤销 inti; Edge*p,*q; for(i=0;i<G->numOfVerts;i++) { p=G->a[i].adj; while(p!=NULL) { q=p->next; free(p); p=q; } }}intcheck(DataTypex)//检查当前情况下，修道士是否安全{if((x.num1>=x.num2||x.num1==0)&&((n-x.num1)>=(n-x.num2)||x.num1==n)&&x.num1>=0&&x.num1<=n&&x.num2>=0&&x.num2<=n)return1;elsereturn0;}intfindfa(DataTypex)//生成在船上修道士仍安全的情况{ inti=0,a,b,t=0;//从始案到末岸的状态 if(x.an) { a=0;b=c-a; while(a+b>=1) { t++; while(b>=0) { fa[i].num1=a; fa[i].num2=b; i++; a++; b--; } a=0; b=c-a-t; } } else//从末岸到始岸的状态 { a=1;b=0;t=0; while(a+b<=c) { t++; while(a>=0) { fa[i].num1=a*(-1); fa[i].num2=b*(-1); i++; a--; b++; } a=fa[0].num1*(-1)+t; b=0; } } returni;}intprint(AdjLGraph*p,intg)//打印安全渡河的过程{DataTypeb[1000];inti=0;while(g!=-1){b[i++]=p->a[g].data;g=p->a[g].pre;}while((--i)>-1){ printf("(%d%d%d)",b[i].num1,b[i].num2,b[i].an);if(!(b[i].num1==0&&b[i].num2==0&&b[i].an==0)){ if(b[i].an==1) printf("船上人数[修道士，野人][%d%d]右边岸上[%d%d0]\n",b[i].num1-b[i-1].num1,b[i].num2-b[i-1].num2,b[i-1].num1,b[i-1].num2); else printf("船上人数[修道士，野人][%d%d]左边岸上[%d%d1]\n",(b[i].num1-b[i-1].num1)*(-1),(-1)*(b[i].num2-b[i-1].num2),b[i-1].num1,b[i-1].num2);}else printf("\n");}printf("\n"); return1;}voidwork(AdjLGraph*p) //广度搜索建立表{ DataTypetem; inti,flag1,g=0,j,count=0,k=0,t; while(p->a[k].data.an!=-1) { j=findfa(p->a[k].data);for(i=0;i<j;i++) { tem.num1=p->a[k].data.num1-fa[i].num1; tem.num2=p->a[k].data.num2-fa[i].num2; tem.an=1-p->a[k].data.an