农夫过河和骑士周游(数据结构课程设计).doc

PAGE 11 姓名：高明 学号：129074151 专业：软件工程 2014/6/20 数据结构课程设计  1:实验要求 1.1实验目的 掌握图的遍历问题，运用图的遍历算法解决复杂问题。掌握并应用邻接存储结构和图的深度遍历问题。培养学习使用图的相关知识解决实际问题的能力。 1.2实验内容问题描述 问题描述：农夫携带一只狼，一只羊，一棵白菜从和的左岸到达河的右岸，由于船只较小，农夫每次只能携带一样过河，在无人看管的情况下狼吃羊，羊吃白菜。 1.3：实验输出要求 要求输出农夫携带所有东西安全过河的步骤。 2：程序设计分析 2.1：实验内容分析 农夫需要多次驾船往返于河的左右两岸，农夫每次过河都会使农夫，狼，羊，白菜的位置发生变化。利用四元组（农夫，狼，羊，白菜）来表示各自所处于河的左岸右岸的位置，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：栈的相关函数 PSeqStack Init_SeqStack(void) //栈的初始化 int Empty_SeqStack(PSeqStack s) //判断栈是否为空栈非空1表示栈空 void Push_SeqStack(PSeqStack s,int x) //入栈 int Pop_SeqStack(PSeqStack s,int *x) //出栈 int Size_SeqStack(PSeqStack s) //顺序栈中元素的个数 void Destroy_SeqStack(PSeqStack *S) //销毁栈 2,：求结点直接后继结点个数的函数 int CountAdjoin(MGraph *G,int u) 3：查找状态(f,w,s,v)在无向图中的位置的函数 int located(MGraph *G,int f,int w,int s,int v) 4：结点值安全状态判断函数 int if_safe(int f,int w,int s,int v) 5：判断农夫过河的两个状态是否是相邻的函数 int if_connected(MGraph *G,int i,int j) 6：创建农夫过河状态的无向图 void Creat_MGraph(MGraph *G) 7：广优度先遍历 遍历所有从状态下标u到状态下标v的路径函数 void BFS_path(MGraph *G,int u,int v) 8：输出所有从状态下标为u到状态下标为v的所有简单路径 void print_path(MGraph *G,int u,int v) 2.3部分函数源代码 path[u][m] 为状态下标u的直接后继状态下标 m表示状态下标u的直接后继结点个数：int path[MaxVertexNum][MaxVertexNum]; 主要结构：typedef struct { int farmer; int wolf; int sheep; int vegetable; }vertexType; //顶点结点类型 typedef struct { vertexType vertex[MaxVertexNum]; int edges[MaxVertexNum][MaxVertexNum]; int vertexNum; }MGraph; //邻接矩阵存储结构类型 typedef struct { int data[MAXSIZE]; int top; //栈顶 }SeqStack,*PSeqStack; void BFS_path(MGraph *G,int u,int v) //深度优先遍历 从状态下标u到状态下标v { int i,j,m,n; PSeqStack S; S=Init_SeqStack(); Push_SeqStack(S,v); vis