数据结构农夫过河.rar

数据结构农夫过河.rar

#include
#include
#define TRUE 1
#define FALSE 0
#define MAXSIZE 16
#define INFINTITY 65535
using namespace std;
int visited[MAXSIZE];
int ray[MAXSIZE]; 
int bay[MAXSIZE][MAXSIZE];//存储   遍历的节点 
int sum =0;		//下标 
int sums =0;	//下标 
int k=0;	   //记录数组的长度
int step=0;  //步骤 
typedef int EdgeType; //图 
typedef int Status;	//创建一个栈用 
typedef int SElemType;//栈 
typedef struct
{
	SElemType *base;
	SElemType *top;
	int stacksize;
}SqStack; 
typedef struct{
	int farmer;
    int wolf;
    int sheep;
    int cabbage;
}status;
typedef struct
{
    int stanum;             //顶点个数
    status vexs[MAXSIZE];   //储存顶点数组
    EdgeType arc[MAXSIZE][MAXSIZE];  //邻接矩阵权值
}MGraph;
Status InitStak_Sq（SqStack &S）{
	S.base=new SElemType[100];
	if（!S.base）{
		exit（0）;
	}
	S.top=S.base;
	S.stacksize=100;
	return 0;
}
int Push_Sq（SqStack &Sint e）{
	if（S.top-S.base==S.stacksize）{
		return -1;
	}
	*S.top++=e;
	return 0;
}
int Pop_Sq（SqStack &S）{
	if（S.top==S.base）{
		return -1;
	}	
	return *--S.top;
}
int isEmpty（SqStack S）{
	if（S.top==S.base）{
		return false;
	}else {
		return true;
	}
} 
//判断节点是否安全
int isSafe（int farmerint wolfint sheepint cabbage）{
	if（（wolf==sheep&&farmer!=wolf）||（sheep==cabbage&&farmer!=sheep））{
		return FALSE;
	}else {
		return TRUE;
	}
} 
//判断节点是否有联系
int trueMove（MGraph Gint iint j）{
	int number=0;//农夫带过河的物品个数 
	if（G.vexs[i].farmer==G.vexs[j].farmer）{
		return  false; //农夫没有移动 
	}
	if（G.vexs[i].cabbage!=G.vexs[j].cabbage）{
		number++; 
	}
	if（G.vexs[i].sheep!=G.vexs[j].sheep）{
		number++;
	}
	if（G.vexs[i].wolf!=G.vexs[j].wolf）{
		number++;
	}
	if（number>1）{
		return false;
	}else{
		return true;
	}
} 
//创建图 
void CreateUDG（MGraph &G）{
	G.stanum=0;
	for（int i=0;i<=1;i++）{
		for（int j =0;j<=1;j++）{
			for（int k=0;k<=1;k++）{
				for（int l=0;l<=1;l++）{
					if（isSafe（ijkl））{//判断节点是否是安全的节点 
						G.vexs[G.stanum].farmer=i; 
						G.vexs[G.stanum].wolf=j; 
						G.vexs[G.stanum].sheep=k; 
						G.vexs[G.stanum].cabbage=l; 
						G.stanum++;
					}
				}
			}
		}
	} 
	for（int i=0;i		for（int j=0;j			if（trueMove（Gij））{
				G.arc[i][j]=TRUE; 
			}else {
				G.arc[i][j]=INFINTITY;
			}
		}
	} 	
} 
//深度优先遍历
void DFS（MGraph GSqStack &Sint i）
{
	if（G.vexs[i].farmer==1&&G.vexs[i].wolf==1&&G.vexs[i].sheep==1&&G.vexs[i].cabbage==1）{
		k=0;
		while（isEmpty（S））{
			bay[sum][sums++]=Pop_Sq（S）;k++;
		}
		for（int i=sums-1;i>=0;i--）{
			Push_Sq（Sbay[sum][i]）;
		}
		sum++;sums=0;
	}	
	for（int j=0;j		if（G.arc[i][j]!=INFINTITY&&!visited[j]）{
			visited[j]=TRUE;//标记为访问状态
			Push_Sq（Sj）;
			DFS（GSj）;
			visited[j]=FALSE;
			Pop_Sq（S）;
		}
	} 
}
void TraverseDFS（MGraph GSqStack &S）{
	for（int i=0;i		visited[i]=FALSE;//初始化访问前的状态 
		ray[i]=-1; 
	}
	visited[0]=TRUE;
	Push_Sq（S0）;
	DFS（GS0）;
}
int find（MGraph Gint m）
{
	for（int i=0;

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       7114  2018-06-15 08:09  数据结构农夫过河.cpp

----------- ---------  ---------- -----  ----

                 7114                    1