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

1、姓名：高明学号：129074151专业：软件工程2014/6/20数据结构课程设计 1:实验要求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：栈的相关函数PSeqStack Init_SeqStack(void)/栈的初始化int E

3、mpty_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(MGrap

4、h *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(MGrap

5、h *G,int u,int v) 2.3部分函数源代码 pathum 为状态下标u的直接后继状态下标 m表示状态下标u的直接后继结点个数：int pathMaxVertexNumMaxVertexNum; 主要结构：typedef struct int farmer;int wolf;int sheep;int vegetable;vertexType; /顶点结点类型 typedef structvertexType vertexMaxVertexNum;int edgesMaxVertexNumMaxVertexNum;int vertexNum;MGraph; /邻接矩阵存储结构类型t

6、ypedef struct int dataMAXSIZE;int top; /栈顶SeqStack,*PSeqStack;void BFS_path(MGraph *G,int u,int v) /深度优先遍历 从状态下标u到状态下标vint i,j,m,n; PSeqStack S;S=Init_SeqStack(); Push_SeqStack(S,v);visitedu=TRUE;/改变路径头结点的访问标志为TRUEPush_SeqStack(S,u); while(!Empty_SeqStack(S)Pop_SeqStack(S,&u);m=1;for(i=0;i<G-

7、>vertexNum;i+) /判定后继结点的个数及将其后继结点访问标志置TRUEif(G->edgesui && !visitedi) pathum=i; /将下标为U的后继结点下标赋给pathum m用来记录直接后继结点的个数visitedi=TRUE;m+;for(j=1;j<=m;j+) n=pathuj;if(n!=v) /判断结束标志 如果数的后继结点下标与要找的一条路径最后一个结点的下标不一样 则将后继元素下标入栈 Push_SeqStack(S,n);else/或者将栈中的最后一个元素出栈 Pop_SeqStack(S,&u);whil

8、e(Size_SeqStack(S)>2) /栈中元素个数大于2 则一直出栈Pop_SeqStack(S,&u);m=1;for(i=0;i<G->vertexNum;i+)if(G->edgesui && !visitedi) /pathum 为状态下标u的直接后继状态下标 m表示状态下标u的后继结点个数pathum=i;visitedi=TRUE;m+;Destroy_SeqStack(&S); /销毁栈void print_path(MGraph *G,int u,int v) /输出所有从状态下标为u到状态下标为v的所有简单路径i

9、nt n,k,i,j,m,t,a,l;k=u;j=1;visitedu=FALSE; /改变第一个结点的访问标志 pathv1=-1; /将一条路径的最后一个顶点的后继结点下标置为无穷大while(k!=-1) printf("ttNO%d:(%d,%d,%d,%d)n",j+,G->vertexk.farmer,G->vertexk.wolf,G->vertexk.sheep,G->vertexk.vegetable);m=CountAdjoin(G,k);if(m=0) /结束条件 后继结点个数为零break;if(m!=1)for(i=m;i&

10、gt;0;i-) /输出某个结点后的所有分支后继结点t=k;t=pathti;n=0;l=j;while(t!=-1) if(n<=1) /（某个结点分支后继结点个数）/用于转换输出另外一条分支后继结点的判断条件printf("tNO%d:(%d,%d,%d,%d)",l+,G->vertext.farmer,G->vertext.wolf,G->vertext.sheep,G->vertext.vegetable);a=t;t=patht1;visitedt=FALSE;n+;elsebreak;printf("n");j

11、=l;k=a;k=pathk1;3：实验结果结果分析：农夫过河的安全步骤：NO1：农夫，狼，羊，白菜都在河的左岸NO2:农夫带羊到河的右岸NO3:农夫回到河的左岸NO4:农夫带狼到河的右岸 或者 农夫带白菜到河的右岸NO5:农夫带羊回到河的左岸 或者 农夫带羊回到河的左岸NO6:农夫带狼到河的右岸NO7:农夫回到河的左岸NO8:农夫带羊到和的右岸4：实验心得通过农夫过河的实验，使我初步了解解决一些复杂较难问题的思路和掌握了解决问题的方法。通过该实验的代码编程过程中也进一步提高了我对c语言的掌握，掌握了栈，深度广度遍历的算法，也提高了我对算法的学习设计能力，同时提高了编程调试的能力，使我遇到那些

12、逻辑上的错误，能通过自己一点一点的调试，搜寻逻辑错误所在处。在编程调试中遇相关的问题时，让我明白遇到问题不可怕，怕的是遇到问题不想解决或者没有解决问题恒定的决心，即使一些问题在困难，当时对遇到的可能丝毫没有头绪，只要一点点的对问题剖析，哪怕在困难的问题也会被解决。实验二1：实验要求：1.1：实验目的提高分析设计解决问题的能力，并掌握选择策略的图的深度优先搜索等先关的知识。1.2：实验内容问题描述 马随机放在国际象棋8*8的方格中，马按照走马的规则进行移动，要求马走过每个格走过仅走过一次并且每个格都走过，编程求输出马走过的路径1.3: 实验输出输出骑士周游的路径2：程序设计分析2.1：实验内容分

13、析在国际象棋的棋盘上，马共有八个可能的跳跃方向。设置一组坐标增量来描述这八个条约方向： （1，2）       （2，1） （2，-1）      （1，-2） （-1，-2）     （-2，-1）  （-2，1）      （-1，2）2.2：主要算法模块分析void go(int n,int x,int

14、 y) 递归算法模块 2.3: 主要源代码#include <stdio.h>#define N 8int dituNN = /棋盘初始化所有点为零0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0;int pathNN; /记录周游路径int flag=0; /结束标记

15、int incX=1,2,2,1,-1,-2,-2,-1; /指示方向 横坐标int incY=-2,-1,1,2,2,1,-1,-2; /指示方向 纵坐标void go(int n,int x,int y)if (n>=(N*N) /判断是否走完整个地图flag=1;pathxy=n;if (flag=1) /递归结束标志return;pathxy=n; /将骑士走的路径记录dituxy=1; /标记坐标（x,y）点走过for (int i=0;i<8;i+)/8方向探路if (x+incXi)>=0) && (x+incXi)<N) && (y+incYi)>=0) && (y+incYi)<N) && (ditux+incXiy+incYi=0)go(n+1,x+incXi,y+incYi); /递归周游dituxy = 0; /8个方向中 如果探测方向不是合适的落马点 则清除马走过的标记return;void main()printf("骑士从棋盘左