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

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

精品文档

姓名：高明

学号：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);
visited[u]=TRUE; //改变路径头结点的访问标志为TRUE
Push_SeqStack(S,u);
while(!Empty_SeqStack(S))
{
Pop_SeqStack(S,&u);
m=1;
for(i=0;i<G->vertexNum;i++) //判定后继结点的个数及将其后继结点访问标志置TRUE
{
if(G->edges[u][i] && !visited[i])
{
path[u][m]=i; //将下标为U的后继结点下标赋给path[u][m] m用来记录直接后继结点的个数
visited[i]=TRUE;
m++;
}
}
for(j=1;j<=m;j++)
{
n=path[u][j];
if(n!=v) //判断结束标志 如果数的后继结点下标与要找的一条路径最后一个结点的下标不一样 则将后继元素下标入栈
Push_SeqStack(S,n);
else //或者将栈中的最后一个元素出栈
Pop_SeqStack(S,&u);
}
while(Size_SeqStack(S)>2) //栈中元素个数大于2 则一直出栈
{
Pop_SeqStack(S,&u);
m=1;
for(i=0;i<G->vertexNum;i++)
{
if(G->edges[u][i] && !visited[i]) //path[u][m] 为状态下标u的直接后继状态下标 m表示状态下标u的后继结点个数
{
path[u][m]=i;
visited[i]=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;
visited[u]=FALSE; //改变第一个结点的访问标志
path[v][1]=-1; //将一条路径的最后一个顶点的后继结点下标置为无穷大
while(k!=-1)
{
printf("\t\tNO%d:(%d,%d,%d,%d)\n",j++,G->vertex[k].farmer,G->vertex[k].wolf,G->vertex[k].sheep,G->vertex[k].vegetable);
m=CountAdjoin(G,k);
if(m==0) //结束条件 后继结点个数为零
break;
if(m!=1)
{
for(i=m;i>0;i--) //输出某个结点后的所有分支后继结点
{
t=k;
t=path[t][i];
n=0;
l=j;
while(t!=-1)
{
if(n<=1) //（某个结点分支后继结点个数）//用于转换输出另外一条分支后继结点的判断条件
{
printf("\tNO%d:(%d,%d,%d,%d)",l++,G->vertex[t].farmer,G->vertex[t].wolf,G->vertex[t].sheep,G->vertex[t].vegetable);
a=t;
t=path[t][1];
visited[t]=FALSE;
n++;
}
else
break;
}
printf("\n");
}
j=l;
k=a;
}
k=path[k][1];
}
}
3：实验结果

结果分析：
农夫过河的安全步骤：
NO1：农夫，狼，羊，白菜都在河的左岸
NO2:农夫带羊到河的右岸
NO3:农夫回到河的左岸
NO4:农夫带狼到河的右岸 或者 农夫带白菜到河的右岸
NO5:农夫带羊回到河的左岸 或者 农夫带羊回到河的左岸
NO6:农夫带狼到河的右岸
NO7:农夫回到河的左岸
NO8:农夫带羊到和的右岸
4：实验心得
通过农夫过河的实验，使我初步了解解决一些复杂较难问题的思路和掌握了解决问题的方法。通过该实验的代码编程过程中也进一步提高了我对c语言的掌握，掌握了栈，深度广度遍历的算法，也提高了我对算法的学习设计能力，同时提高了编程调试的能力，使我遇到那些逻辑上的错误，能通过自己一点一点的调试，搜寻逻辑错误所在处。在编程调试中遇相关的问题时，让我明白遇到问题不可怕，怕的是遇到问题不想解决或者没有解决问题恒定的决心，即使一些问题在困难，当时对遇到的可能丝毫没有头绪，只要一点点的对问题剖析，哪怕在困难的问题也会被解决。

实验二
1：实验要求：
1.1：实验目的
提高分析设计解决问题的能力，并掌握选择策略的图的深度优先搜索等先关的知识。
1.2：实验内容问题描述
马随机放在国际象棋8*8的方格中，马按照走马的规则进行移动，要求马走过每个格走过仅走过一次并且每个格都走过，编程求输出马走过的路径
1.3: 实验输出
输出骑士周游的路径
2：程序设计分析
2.1：实验内容分析
在国际象棋的棋盘上，马共有八个可能的跳跃方向。

设置一组坐标增量来描述这八个条约方向：
① （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 <stdio.h>
#define N 8
int ditu[N][N] = //棋盘初始化所有点为零
{
{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 path[N][N]; //记录周游路径
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;
path[x][y]=n;
}
if (flag==1) //递归结束标志
return;
path[x][y]=n; //将骑士走的路径记录
ditu[x][y]=1; //标记坐标（x,y）点走过
for (int i=0;i<8;i++) //8方向探路
if ((((x+incX[i])>=0) && ((x+incX[i])<N)) && (((y+incY[i])>=0) && ((y+incY[i])<N)) && (ditu[x+incX[i]][y+incY[i]]==0))
go(n+1,x+incX[i],y+incY[i]); //递归周游
ditu[x][y] = 0; //8个方向中 如果探测方向不是合适的落马点 则清除马走过的标记
return;
}

void main()
{
printf("骑士从棋盘左上角开始的周游路径\n");
go(1,0,0); //设置从0,0开始出发
for(int i=0;i<N;i++) //输出路径
{
for(int j=0;j<N;j++)
{
printf("%4d",path[i][j]);
}
printf("\n");
}
}
3：实验结果

4：实验心得
通过该实验让我掌握了数据结构进一步了解，对图的深度优先遍历算法的由来更深的理解与体会，对骑士周游问题有自己的见解和体会。让我学习的理论与实际运用相结合，提高了独立解决问题的能力。

收集于网络，如有侵权请联系管理员删除