两两房间相连.docVIP

计算机科学与技术系 课程设计报告 2010～2011学年第二学期 课程 数据结构与算法 课程设计题目名称 两两相连的房间 1.题目： （两两相连的房间问题）一所奇怪的房子，这所房子里有n个房间，每个房间里有一些门通向别的房间，可是这些门十分奇怪，它们只能从房间a开向房间b，也就是说，一扇从a开向b的门是不能让一个人从b房间走到a房间的。你能计算一下任意两个房间之间都互相相通吗？问#define Maxsize 100，接着定义三个结构体变量，房间数目n，门的数目e，以及数组int edges[Maxsize][Maxsize]，是用来存储门的信息。例如 int edges[3][3],表示房间数为3个，门的数量也为3个。 实现题目要求的功能的函数主要是：有向图的建立Create( ),找出直接相连通的门Findroad( ),找出间接相连通的门Change( ),判断任意房间是否都是连通的函数Chick( ),最后在void main( )函数中实现对各个子函数的调用，它们之间的关系如图1所示: 为了更直观的看到操作后的输出结果，我也输出了图的邻接矩阵以及转换后的矩阵，通过这两个矩阵的比较，可以看出哪些房间之间是间接相连的，哪些房间是直接相连的；同时能从第二个矩阵判断是否任意的两个房间都是相连的，如果矩阵中所有的元素都是1，则能判断所有的房间都是连通的，反之，只要有一个元素是0，则不是判断所有的房间都是连通的。 该程序流程图如图1： 图1 程序流程图 4.算法思想： 由于本实验是说有n个房子，其中只能从房间a到房间b，而不能从房间b到a，于是我们可以利用二位数组来存储一个房间的出口和入口，并且利用数据结构中对图的有哪些信誉好的足球投注网站及遍历的算法。首先定义一个结构体，里面有三个结构体变量，房间数量n，门的数量e，门的信息数组edges[ ][ ]，要求计算任意两个房间是否是连通的，所以当我们创建一个图后，有两种情况，一种是两个房间直接是连通的，另一种情况是两个房间是间接连通的，比如说1房间和2房间连通，2房间和3房间连通，则1房间和3房间就是连通的，这就说明1房间和3房间是间接连通的。首先我们得必须把所建立的图转换成为有向图的邻接矩阵，然后再通过直接连通的房间的条件去找出间接连通的房间，并赋值为1，表示这两个房间也是连通的。依照上述方法，并通过两个for循环，将所有间接连通的房间赋值为1，重新形成一个矩阵，如果该矩阵中的元素全部为1，则任意的两个房间之间都互相连通，否则则不是任意的两个房间之间都互相连通的。 5.详细设计和主要编码段： 一个图的邻接矩阵存储结构可以用一个二维数组来表示，用来存储门的出口和入口信息，房间数目用n表示，门的数目用e表示，所以先定义一个数据类型： typedef struct{ /*定义图的类型*/ int n; /*房间数目*/ int e; /*门的数目*/ int edges[Maxsize][Maxsize]; /*二维数组，存储门信息*/ }MGraph; 图2 有向图 它为一个有向图，有4个房间和六个门由图可知，可以知道各个房间门的信息，1房间可以到2房间，1房间可以到3房间，2房间可以到4房间，3房间可以到2房间，4房间可以到1房间，4房间也可以到3房间。首先执行主函数,先定义一个Mgraph类型的数据mg1，然后把mg1的地址赋给mg，Mgraph mg1，*mg=mg1；mg=Create（）(*mg).n=n; (*mg).e=e;将房间的数量n门的数量e和结构体联系起来。然后就可以输入各个门的出口和入口了，根据图2 ，输入第1个门的出口和入口分别是1房间和2房间，第2个门的出口和入口分别是1房间和3房间，第3个门的出口和入口分别是2房间和3房间，利用同样方法，将图中显示的所有门的出口和入口都输入进去，然后利用以上输入的信息将可以连通的门赋值为1，并执行程序，for(i=0;i(*mg).n;i++) /*输出邻接矩阵*/ { for(j=0;j(*mg).n;j++) { printf(%2d,(*mg).edges[i][