资源描述：
《农夫过河和骑士周游(数据结构课程设计)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、姓名：高明学号：129074151专业：软件工程2014/6/20数据结构课程设计111:实验要求1.1实验目的掌握图的遍历问题，运用图的遍历算法解决复杂问题。掌握并应用邻接存储结构和图的深度遍历问题。培养学习使用图的相关知识解决实际问题的能力。1.2实验内容问题描述问题描述：农夫携带一只狼，一只羊，一棵白菜从和的左岸到达河的右岸，由于船只较小，农夫每次只能携带一样过河，在无人看管的情况下狼吃羊，羊吃白菜。1.3：实验输出要求要求输出农夫携带所有东西安全过河的步骤。2：程序设计分析2.1：实验内容分析农夫需要多次驾船往返于河的左右两岸，农夫每次过河都会
2、使农夫，狼，羊，白菜的位置发生变化。利用四元组（农夫，狼，羊，白菜）来表示各自所处于河的左岸右岸的位置，0表示河的左岸，1表示河的右岸。初始状态时（0,0,0,0）都处在河的左岸，终态是（1，1,1,1）四者都处在河的右岸。共有16种状态，但其中有些状态不安全，删除不安全的状态，将安全的状态按照合理的过河步骤联系起来.（0,0,0，0）(1,0,1,0)(0,0,1,0)(1,1,1,0)(1,0,1,1)(0,1,0,0)(0,0,0,1)(1,1,0,1)(0,1,0,1)(1,1,1,1)安全过河状态图2.2主要函数模块算法分析1：栈的相关函数P
3、SeqStackInit_SeqStack(void)//栈的初始化11intEmpty_SeqStack(PSeqStacks)//判断栈是否为空栈非空1表示栈空voidPush_SeqStack(PSeqStacks,intx)//入栈intPop_SeqStack(PSeqStacks,int*x)//出栈intSize_SeqStack(PSeqStacks)//顺序栈中元素的个数voidDestroy_SeqStack(PSeqStack*S)//销毁栈2,：求结点直接后继结点个数的函数intCountAdjoin(MGraph*G,intu
4、)3：查找状态(f,w,s,v)在无向图中的位置的函数intlocated(MGraph*G,intf,intw,ints,intv)4：结点值安全状态判断函数intif_safe(intf,intw,ints,intv)5：判断农夫过河的两个状态是否是相邻的函数intif_connected(MGraph*G,inti,intj)6：创建农夫过河状态的无向图voidCreat_MGraph(MGraph*G)7：广优度先遍历遍历所有从状态下标u到状态下标v的路径函数voidBFS_path(MGraph*G,intu,intv)8：输出所有从状态下标
5、为u到状态下标为v的所有简单路径voidprint_path(MGraph*G,intu,intv)2.3部分函数源代码path[u][m]为状态下标u的直接后继状态下标m表示状态下标u的直接后继结点个数：intpath[MaxVertexNum][MaxVertexNum];主要结构：typedefstruct{intfarmer;intwolf;intsheep;intvegetable;}vertexType;//顶点结点类型typedefstruct11{vertexTypevertex[MaxVertexNum];intedges[MaxVe
6、rtexNum][MaxVertexNum];intvertexNum;}MGraph;//邻接矩阵存储结构类型typedefstruct{intdata[MAXSIZE];inttop;//栈顶}SeqStack,*PSeqStack;voidBFS_path(MGraph*G,intu,intv)//深度优先遍历从状态下标u到状态下标v{inti,j,m,n;PSeqStackS;S=Init_SeqStack();Push_SeqStack(S,v);visited[u]=TRUE;//改变路径头结点的访问标志为TRUEPush_SeqStack
7、(S,u);while(!Empty_SeqStack(S)){Pop_SeqStack(S,&u);m=1;for(i=0;ivertexNum;i++)//判定后继结点的个数及将其后继结点访问标志置TRUE{if(G->edges[u][i]&&!visited[i]){11path[u][m]=i;//将下标为U的后继结点下标赋给path[u][m]m用来记录直接后继结点的个数visited[i]=TRUE;m++;}}for(j=1;j<=m;j++){n=path[u][j];if(n!=v)//判断结束标志如果数的后继结点下标与要找
8、的一条路径最后一个结点的下标不一样则将后继元素下标入栈Push_SeqStack(S,n);e
