数据结构课程设计

修道士与野人问题

1、需求分析

n个修道士和n个野人渡河，只有一条小船，能容纳c人，两种人都会划船，建立过河方式。满足：

野人无法侵犯修道士。这就要求无论在何处，修道士的个数不得少于野人的人数（除非修道士个数为0）。设计程序模拟该过程。

程序的输入为修道士（野人）的个数以及每条船容纳人的个数。输出为判断是否可以安全渡河。如果能，则给出一个小船来回次数最少的最佳方案。

要求：（1）用一个三元组（x1,x2,x3）表示渡河过程中各个状态。其中，x1表示起始岸上修道士个数，x2表示起始岸上野人个数，x3表示小船位置（0——在目的岸，1——在起始岸）。

例如（5，3，0）表示起始岸上有5个修道士，3个野人，小船在目的岸一边。

（2）采用邻接表做为存储结构。最短路径搜索采用广度搜索法。

（3）输出最优解。

若问题有解（能渡过河去），则输出一个最佳方案。用三元组表示渡河过程中的状态，并用箭头指出这些状态之间的迁移：

目的状态←…中间状态←…初始状态。

若问题无解，则给出“渡河失败”的信息。

4）求出所有的解。

2、设计。2.1设计思想。

1）数据结构设计：根据题目要求，用图形结构，用邻接表来存储结点，以及结点之间的关系，同时在广度优先遍历中利用到队列。

2）算法设计：先定义一个图利用邻接表储存结构，再举出在船上修道士和野人的所有情况，然后判断其修道士是否处于安全的状态，如果安全则将该点添加到图中，点添加完后在看两点之间是否连通如果连通则可将边添加到图中，这样就创建出了图，然后分别利用广度搜索和深度搜索来完成题目的要求。

2.2设计表示

1）函数调用关系图。

2）函数接口规则说明。

int search(adjlgraph *g,int x,int y,int m ) 查找起始和最后的结点，其中x,y,m分别表示起始岸修道士人数，野人人数和船的状态*/

int checking(datatype x) /检查修道士是否安全，x表示邻接表中的一个结点*/

int connect(adjlgraph *g,int i,int j) /将能走通的点连接起来，i，j为图中的两个结点*/

void creat(adjlgraph *g) /图的创建*/

int print(adjlgraph g) /从后向前打印最短路径*/

int broadfsearch(adjlgraph g,int u,int v) /用广度优先遍历搜索最短路径，u表示起始结点，v表示最后的结点*/

void print1(adjlgraph g) /打印输出所有最短路径*/

void dfs(adjlgraph g,int u,int v ,int visited)利用深度搜索找出所有最短路径，u表示起始结点，v表示最后的结点，visited用来标记结点是否被访问*/

2.3详细设计。

首先是定义邻接表。

typedef struct

int daoshi; /道士。

int yeren; /野人。

int ship; /船的位置。

datatype;

typedef struct node //边结点的结构体。

int dest邻接边的弧头顶点序号。

struct node *next; /单链表的下一个结点指针。

edge;typedef struct

datatype data; /顶点数据元素。

int source弧尾顶点序号。

edge *adj邻接边的头指针。

adjlheight;

typedef struct

adjlheight a[200邻接表数组。

int numofverts顶点个数。

int numofedges边个数。

adjlgraph邻接表结构体。

同时定义了几个全局变量，便于函数的直接利用。

int n,c;//修道士和野人人数为n，船能容纳人数为c

int path[200]; 保存结点的后驱结点。

int path1[200]; 保存结点的前驱结点。

利用上述结构和相关函数可以构造出图，然后对图进行利用；

然后在广度优先遍历搜索中用到了队列。

typedef struct

int queue[200];

int rear;

int front;

int count;

seqcqueue;

最后通过主函数main调用各函数得到相关信息。

int main()

printf("输入小船可装的人数：");

return 0;

3、调试分析。

在进行运行的时候，曾出现了打印输出错误，经过一步一步调试，发现在插入结点的时候出现了插入错误，即没有考虑到结点后驱的改变，通过改正，重新运行检测，运行结果正确，在排版时通过一步步调试，能够使输出结果很明显的表示的船的方案。

4、用户手册。

在vc下运行，很简单的输入，只需输入野人和道士的人数n和船能承载的人的个数c即可。

5、测试数据及测试结果。

1）输入修道士和野人的人数n=6，船能容纳的人c=2,；不能安全渡河；

测试结果：2）输入修道士和野人人数为n=3，船能容纳的人c=2；渡河成功。

测试结果：输出一种最短路径。

输出所有最短路径。

输出最短路径数目：

6、源程序清单。

#include <>

int n,c;//修道士和野人人数为n，船能容纳人数为c

int path[200];/保存结点的后驱结点。

int path1[200];/保存结点的前驱结点。

typedef struct

int daoshi; /道士。

int yeren; /野人。

int ship; /船的位置。

datatype;

typedef struct node //边结点的结构体。

int dest邻接边的弧头顶点序号。

struct node *next; /单链表的下一个结点指针。

edge;typedef struct

datatype data; /顶点数据元素。

int source弧尾顶点序号。

edge *adj邻接边的头指针。

adjlheight;

typedef struct

adjlheight a[200]; 邻接表数组。

int numofverts顶点个数。

int numofedges边个数。

adjlgraph邻接表结构体。

void adjinitiate(adjlgraph *g) /初始化。

int i;

g->numofedges=0; /图的边数。

g->numofverts=0; /顶点数。

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

void insertvertex(adjlgraph *g,int i,datatype x) /插入顶点。

if (i>=0&&i<200)

else printf("顶点越界");

void insertedge(adjlgraph *g,int i,int j插入边。

edge *p;

if(i<0||i>=g->numofverts||j<0||j>=g->numofverts)

p=(edge*)malloc(sizeof(edge));申请邻接边单链表结点空间。

p->dest=j;//置邻接边弧头序号。

p->next=g->a[i].adj;//

g->a[i].adj=p;

g->numofedges++;

void adjdestroy(adjlgraph *g)//释放指针内存空间。

int i;

edge *p,*q;

for(i=0;inumofverts;i++)依次释放内存空间。

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了