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

《农夫过河和骑士周游(数据结构课程设计)(10页).doc》由会员分享，可在线阅读，更多相关《农夫过河和骑士周游(数据结构课程设计)(10页).doc（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-农夫过河和骑士周游(数据结构课程设计)姓名：高明学号：129074151专业：软件工程2014/6/20Click here to enter text. 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：栈的相关函数PSe

3、qStack 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：查找状态

4、(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：输出所有从状态下标

5、为u到状态下标为v的所有简单路径void print_path(MGraph *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 edgesMaxVertexNumMaxVertexN

6、um;int vertexNum;MGraph; /邻接矩阵存储结构类型typedef 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_S

7、eqStack(S,&u);m=1;for(i=0;ivertexNum;i+) /判定后继结点的个数及将其后继结点访问标志置TRUEif(G-edgesui & !visitedi) pathum=i; /将下标为U的后继结点下标赋给pathum m用来记录直接后继结点的个数visitedi=TRUE;m+;for(j=1;j2) /栈中元素个数大于2 则一直出栈Pop_SeqStack(S,&u);m=1;for(i=0;ivertexNum;i+)if(G-edgesui & !visitedi) /pathum 为状态下标u的直接后继状态下标 m表示状态下标u的后继结点个数pathum

8、=i;visitedi=TRUE;m+;Destroy_SeqStack(&S); /销毁栈void print_path(MGraph *G,int u,int v) /输出所有从状态下标为u到状态下标为v的所有简单路径int 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-

9、vertexk.vegetable);m=CountAdjoin(G,k);if(m=0) /结束条件 后继结点个数为零break;if(m!=1)for(i=m;i0;i-) /输出某个结点后的所有分支后继结点t=k;t=pathti;n=0;l=j;while(t!=-1) if(nvertext.farmer,G-vertext.wolf,G-vertext.sheep,G-vertext.vegetable);a=t;t=patht1;visitedt=FALSE;n+;elsebreak;printf(n);j=l;k=a;k=pathk1;3：实验结果结果分析：农夫过河的安全步骤：

10、NO1：农夫，狼，羊，白菜都在河的左岸NO2:农夫带羊到河的右岸NO3:农夫回到河的左岸NO4:农夫带狼到河的右岸 或者 农夫带白菜到河的右岸NO5:农夫带羊回到河的左岸 或者 农夫带羊回到河的左岸NO6:农夫带狼到河的右岸NO7:农夫回到河的左岸NO8:农夫带羊到和的右岸4：实验心得通过农夫过河的实验，使我初步了解解决一些复杂较难问题的思路和掌握了解决问题的方法。通过该实验的代码编程过程中也进一步提高了我对c语言的掌握，掌握了栈，深度广度遍历的算法，也提高了我对算法的学习设计能力，同时提高了编程调试的能力，使我遇到那些逻辑上的错误，能通过自己一点一点的调试，搜寻逻辑错误所在处。在编程调试中遇

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

12、个条约方向：（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 y) 递归算法模块 2.3: 主要源代码#include #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,

13、 0, 0, 0, 0, 0,0, 0, 0, 0, 0, 0, 0, 0int pathNN; /记录周游路径int flag=0; /结束标记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=

14、0) & (x+incXi)=0) & (y+incYi)N) & (ditux+incXiy+incYi=0)go(n+1,x+incXi,y+incYi); /递归周游dituxy = 0; /8个方向中 如果探测方向不是合适的落马点 则清除马走过的标记return;void main()printf(骑士从棋盘左上角开始的周游路径n);go(1,0,0); /设置从0,0开始出发for(int i=0;iN;i+) /输出路径for(int j=0;jN;j+)printf(%4d,pathij);printf(n);3：实验结果4：实验心得通过该实验让我掌握了数据结构进一步了解，对图的深度优先遍历算法的由来更深的理解与体会，对骑士周游问题有自己的见解和体会。让我学习的理论与实际运用相结合，提高了独立解决问题的能力。-第 9 页