数据结构农夫过河问题课程设计

课程设计成绩

总评成绩

指导老师签名

《照据信构C》

课程设计报告

一.课程设计概述

本次数据结构课程设计共完成5个题目：成

绩分析问题，哈夫曼编码器，迷宫问题，八

皇后问题，农夫过河问题的求解。

使用环境：C语言。

编译环境：VisualStudio2022o

实验内容：

农夫过河问题的求解。

问题描述：

一个农夫带着一只狼，一只羊和一颗白菜,

身处河的南岸。他要把这些东西全部运到北

岸。他面前只有一条小船，船只能容下他和

一件物品。只有农夫才能乘船。如果农夫在

场，则狼不能吃羊，羊不能吃白菜，否则狼

会吃羊，羊会吃白菜，所以农夫不能留下羊

和白菜自己离开，也不能留下狼和羊自己离

开，而狼不吃白菜。

需求分析：

编写程序求农夫将所有东西运过河的方案

■■=ADT=・"*

(

intsafe(intf,intw,ints,intv)〃判断是否安全

intconnected(intp,intq)//判断顶点vx[p]和vx[q]是否连接

voidcreate_graph()//创建图

voidprint_path(intu,intv)//输出方法

voiddfs_path(intu,intv)//深度搜索路径

)

存储结构：

typedefstruct{

intfarmer,wolf,sheep,vegetable;

}VERTEX;

VERTEXvx[MAX];

〃而为数组存处有向图的邻接矩阵

intmatrix[MAX][MAX],vnum,visited[MAX],path[MAX];

设计思路：

下面是农夫过河问题的设计思路和关键算法：

1.**数据结构设计**:

-使用结构体'VERTEX'表示一个状态，其中包括了农夫、

狼、羊和白菜的位置信息。

-定义了顶点数组'vx',用于存储所有可能的状态。

-声明了邻接矩阵'matrix',用于表示状态之间的连接关系。

-定义了标记数组'visited',用于记录顶点是否被访问过。

-声明了路径数组'path',用于存储路径信息。

2.**安全性判断**:

-'safe'函数用于判断当前状态是否安全。

-根据题目规则，如果农夫和羊不在同一岸边，并且（狼与

羊在同一岸边，或者羊与白菜在同一岸边），则认为当前状态是

不安全的。否则，认为是安全的。

3.**连接性判断**:

-'connected'函数用于判断两个顶点是否相连。

-根据题目规则，只有当农夫和另一样物体在同一岸边，并

且其他物体在两个顶点中的位置相同的情况下，两个顶点才能相

连。

4.**图的创建**:

-'create_graph'函数用于创建图。

-使用四重嵌套的循环遍历了所有可能的顶点状态，并利用

'safe'函数判断当前状态是否安全。

-如果当前状态安全，则将该状态下各个物体的位置信息赋

值给对应的顶点结构体'vxtvnum]',并增加'vnum'的值，表

示顶点数量增加了一个。

-接下来，再次使用两重循环遍历每对顶点，通过调用

'connected'函数判断两个顶点是否相连。如果两个顶点是相连

的，则在邻接矩阵'matrix'中设置对应位置的值为1,表示它

们之间有一条边；否则，将对应位置的值设置为0。

5.**深度优先搜索**:

-'dfsjpath'函数用于进行深度优先搜索，并找到从起点到

终点的路径。

-先将起点标记为已访问。

-遍历与当前节点相连的未访问过的节点，将其添加到路径

中，并以该节点作为新的起点递归调用'dfs_path'函数。

-通过递归的方式，不断向前搜索路径，直到回溯到起点节

点。

6,**输出路径**:

-'print_path'函数用于输出路径。

-从终点节点开始回溯，沿着路径向前输出节点，直到回溯

到起点节点。

7.**主函数**:

-在'main'函数中调用'create_graph'创建图，然后初

始化标记数组'visited'o

-设置起点和终点的索引，并调用'dfs_path'进行深度优

先搜索。

-如果终点被访问过，则输出路径。

详细设计：

^include"stdio.h"

#defineMAX20

typedefstruct{

intfarmer,wolf,sheep,vegetable;

}VERTEX;

VERTEXvx[MAX];

〃而为数组存处有向图的邻接矩阵

intmatrix[MAX][MAX],vnum,visited[MAX],path[MAX];

〃判断是否安全

intsafe(intf,intw,ints,intv)

(

if(f!=s&&

(w=s||

s==v))〃当农夫和羊，(羊或者白菜,浪或者羊中的一种),

不再同一岸边时

return(0);

else

return(1);

)

intconnected(intp,intq){//判断顶点vx[p]和vx[q]是否

连接

intk=0;

if(vx[p].wolf!=vx[q].wolf)

k++;

if(vx[p].sheep!=vx[q].sheep)

k++;

if(vx[pj.vegetable!=vx[q].vegetable)

k++;

if(vx[pj.farmer!=vx[q].farmer&&k<=1)

return(1);

}else

return(0);

)

voidcreate_graph(){//创建图

inti,j,f,w,s,v;

vnum=0;

for(f=0;f<=1;f++)

for(w=0;w<=1;w++)

for(s=0;s<=1;s++)

for(v=0;v<=1;v++)

if(safe(f,w,s,v)==1){

vx[vnum].farmer=f;

vx[vnumLwolf=w;

vx[vnum].sheep=s;

vx[vnum].vegetable=v;

vnum++;

)

for(i=0;i<vnum;i++)

for(j=0;j<vnum;j++)

if(connected(i,j)==1){

matrix[i][j]=1;

}else

matrix[i][j]=0;

return;

voidprint_path(intu,intv){//输出方法

intk=u;

while(k!=v){

printf(，?%d%d%d%d\n”,vx[k].farmer,vx[kLwolf,

vx[k].sheep,

vx[k].vegetable);

k=path[k];

)

printf("%d%d%d%d\n”,vx[k].farmer,vx[k].wolf,

vx[k].sheep,

vx[k].vegetable);

}

voiddfs_path(intu,intv){

intj;

visited[u]=1;

for(j=0;j<vnum;j++)

if(matrix[u][j]=1&&visited[j]==0&&visited[v]=

0){

path[u]=j;

dfs_path(j,v);

)

)

intmain(){

inti,j;

create_graph();

for(i=0;i<vnum;++i)

visited[i]=0;

i=0;

j=vnum-1;

dfsjpath(i,j);

if(visited[j]==1){

printf(z，»»thepathis>>>\n");

printjpath(i,j);

)

getchar();

)

调试分析：

本题主要采用构建农夫，牙良，羊，白菜的图，并进

行图的