资源描述：
《数据结构课程设计__修道士野人问题和西文图书管理系统》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、题号题目：3、修道士与野人问题1、需求分析n个修道士和n个野人渡河，只有一条小船，能容纳c人，两种人都会划船，建立过河方式。满足：野人无法侵犯修道士。这就要求无论在何处，修道士的个数不得少于野人的人数（除非修道士个数为0）。设计程序模拟该过程。程序的输入为修道士（野人）的个数以及每条船容纳人的个数。输出为判断是否可以安全渡河。如果能，则给出一个小船来回次数最少的最佳方案。要求：（1）用一个三元组（x1,x2,x3）表示渡河过程中各个状态。其中，x1表示起始岸上修道士个数，x2表示起始岸上野人个数，x3表示小船位置（0——在目的岸，1——在起始岸）。例如（5，3，0）表示起始岸上有5
2、个修道士，3个野人，小船在目的岸一边。（2）采用邻接表做为存储结构。最短路径搜索采用广度搜索法。（3）输出最优解若问题有解（能渡过河去），则输出一个最佳方案。用三元组表示渡河过程中的状态，并用箭头指出这些状态之间的迁移：目的状态←…中间状态←…初始状态。若问题无解，则给出“渡河失败”的信息。（4）求出所有的解。2、设计2.1设计思想（1）数据结构设计：根据题目要求，用图形结构，用邻接表来存储结点，以及结点之间的关系，同时在广度优先遍历中利用到队列。（2）算法设计：先定义一个图利用邻接表储存结构，再举出在船上修道士和野人的所有情况，然后判断其修道士是否处于安全的状态，如果安全则将该点
3、添加到图中，点添加完后在看两点之间是否连通如果连通则可将边添加到图中，这样就创建出了图，然后分别利用广度搜索和深度搜索来完成题目的要求。Printf1()DFS()2.2设计表示（1）函数调用关系图AdjLGraphMain()Printf()BroadFSearch()SeqCQueueCreat()Connect()Checking()28（1）函数接口规则说明intSearch(AdjLGraph*G,intx,inty,intm)/*查找起始和最后的结点，其中x,y,m分别表示起始岸修道士人数，野人人数和船的状态*/intChecking(DataTypex)/*检查修道士
4、是否安全,x表示邻接表中的一个结点*/intConnect(AdjLGraph*G,inti,intj)/*将能走通的点连接起来，i，j为图中的两个结点*/voidCreat(AdjLGraph*G)/*图的创建*/intPrint(AdjLGraphG)/*从后向前打印最短路径*/intBroadFSearch(AdjLGraphG,intu,intv)/*用广度优先遍历搜索最短路径，u表示起始结点，v表示最后的结点*/voidPrint1(AdjLGraphG)/*打印输出所有最短路径*/voidDFS(AdjLGraphG,intu,intv,intvisited[])/*利
5、用深度搜索找出所有最短路径，u表示起始结点，v表示最后的结点，visited[]用来标记结点是否被访问*/2.3详细设计首先是定义邻接表typedefstruct{intdaoshi;//道士intyeren;//野人intship;//船的位置}DataType;typedefstructNode//边结点的结构体{intdest;//邻接边的弧头顶点序号structNode*next;//单链表的下一个结点指针}Edge;typedefstruct{DataTypedata;//顶点数据元素intsource;//弧尾顶点序号Edge*adj;//邻接边的头指针}AdjLHei
6、ght;typedefstruct{AdjLHeighta[200];//邻接表数组intnumOfVerts;//顶点个数intnumOfEdges;//边个数}AdjLGraph;//邻接表结构体同时定义了几个全局变量，便于函数的直接利用intn,c;//修道士和野人人数为n，船能容纳人数为cintPath[200];//保存结点的后驱结点intPath1[200];//保存结点的前驱结点利用上述结构和相关函数可以构造出图，然后对图进行利用；然后在广度优先遍历搜索中用到了队列typedefstruct28{intqueue[200];intrear;intfront;intco
7、unt;}SeqCQueue;最后通过主函数main调用各函数得到相关信息intmain(){AdjLGraphG;intvisited[200];//标记结点是否被访问printf("输入小船可装的人数:");while(scanf("%d",&c)!=EOF){memset(Path,0,sizeof(0));memset(visited,0,sizeof(visited));memset(Path1,0,sizeof(Path1));N=0;printf("
