两两房间相连.doc

计算机科学与技术系课程设计报告20102011学年第二学期课程 数据结构与算法课程设计题目名称两两相连的房间问题学生姓名任学号专业班级09网工(2)指导教师2011年6月1.题目：（两两相连的房间问题）一所奇怪的房子，这所房子里有n个房间，每个房间里有一些门通向别的房间，可是这些门十分奇怪，它们只能从房间a开向房间b，也就是说，一扇从a开向b的门是不能让一个人从b房间走到a房间的。你能计算一下任意两个房间之间都互相相通吗？编写程序的相关要求：（1） 应用“数据结构与算法”课程知识建立该问题的数据结构模型；（2） 编写算法解决问题；（3） 分析算法的时间性能；（4） 按“课程设计教学大纲”的要求完成“数据结构与算法课程设计报告”。2.问题分析：目说是要求有n个房子，其中只能从房间a到房间b，而不能从房间b到a，于是通过对题目的分析，应该是利用有向图的遍历，定义一个结构体，将图的每个门信息输入，最终通过计算来计算是否所有的房间都是连通的。如果只要有一个点到某个点不是连通的，则不是所有的房间都是连通的。如果任意一个点到任意一个点都是连通的，则所有的房间都是连通的。实现本程序应该需要解决以下问题：（1）根据题目要求，需要用到什么数据结构；（2）图的类型应该怎样定义，并且考虑里面应该存储哪些信息；（3）必须要用到图的什么知识点来解决这个问题；（4）解决怎样找到哪些房间是直接相连的，怎样输出图的邻接矩阵；（5）如何判断间接相连的房子是相连的；（6）怎样判断任意的两个房间都是连通的。3.数据结构的选择和概要设计：实验是考察图的搜索和遍历算法，题目说有n个房子，其中只能从房间a到房间b，而不能从房间b到a，而且每个房间还有若干个门，这让我想起必须得用到数据结构中图的数据结构，采用对图的遍历标记房间的通道关系来解决的。首先要设定一个最大房子数目，即#define Maxsize 100，接着定义三个结构体变量，房间数目n，门的数目e，以及数组int edgesMaxsizeMaxsize，是用来存储门的信息。例如 int edges33,表示房间数为3个，门的数量也为3个。实现题目要求的功能的函数主要是：有向图的建立Create( ),找出直接相连通的门Findroad( ),找出间接相连通的门Change( ),判断任意房间是否都是连通的函数Chick( ),最后在void main( )函数中实现对各个子函数的调用，它们之间的关系如图1所示:为了更直观的看到操作后的输出结果，我也输出了图的邻接矩阵以及转换后的矩阵，通过这两个矩阵的比较，可以看出哪些房间之间是间接相连的，哪些房间是直接相连的；同时能从第二个矩阵判断是否任意的两个房间都是相连的，如果矩阵中所有的元素都是1，则能判断所有的房间都是连通的，反之，只要有一个元素是0，则不是判断所有的房间都是连通的。 该程序流程图如图1：开始主函数创建有向图 找直接相连房间in&jnn找间接相连房间 i=i+1,j=j+1判断结果输出结果结束是 否n 图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 edgesMaxsizeMaxsize; /*二维数组，存储门信息*/MGraph; 下面是对该程序进行分析和说明，为了更好的说明问题，首先需要先建立一个图，如图2所示： 1234图2 有向图它为一个有向图，有4个房间和六个门由图可知，可以知道各个房间门的信息，1房间可以到2房间，1房间可以到3房间，2房间可以到4房间，3房间可以到2房间，4房间可以到1房间，4房间也可以到3房间。首先执行主函数,先定义一个Mgraph类型的数据mg1，然后把mg1的地址赋给mg，即Mgraph mg1，*mg=&mg1；然后执行mg=Create（），创建一个有向图，输入房间数目和门的数目，例如4个房间和8个门，并执行(*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).edgesij); q+; if(q%(*mg).n=0) printf(n); 首先当i=1时，执行内循环，执行完之后，再执行外循环，当q值对房间数n求余为0时换行，最终可以输出入得邻接矩阵，如图3所示：0 1 1 00 0 0 10 1 0 01 0 1 0图3 有向图的邻接矩阵 现在需要找直接连通的房间了，执行Findroad( )函数，首先先将相同的房间之间赋值为1，设置为相连通的。就是1房间和1房间是相连通的，2房间和2房间是相连通的等等。for(i=0;i(*G).n;i+) for(j=0;j(*G).n;j+) if(i!=j&(*G).edgesij=1) /*排除对角线上的数据*/ Change(G,i,j); 利用两个for循环，执行顺序同上面介绍的一样，找出edgesij=1的情况，并执行子函数调用子函数过程，执行Change（G，i，j），找出间接相连通的房间。if(*G).edgeski=1&(*G).edgeskj=0) (*G).edgeskj=1;现在我从图2中截取一段图来解释这个问题：243 图4 截取的有向图在Change（）函数里，我们同样利用一个for循环假设找出k的值，假设k=4，i=3，j=2，则根据判断条件if（*G).edges43= &(*G).edges42=0）可得出(*G).edges42=1；这样我们就得出房间4和房间2是连通的，而且他们是间接相连的。找到一个间接连通的房子以后，并赋值数组的元素值为1，再回到Findroad（）函数，继续执行同样的步骤，再调用Change（）函数，最终找到所有的间接相连的房间。找到后，我们就可以执行Chick（）函数，判断任意的两个房间之间是否是互相连通的。在Chick（）子函数中，我们首先依据上面介绍的步骤来输出转换后的矩阵，如图5：1 1 1 11 1 1 11 1 1 11 1 1 1图5 转换后的矩阵根据转换后的矩阵，我们可以得出结论：如果数组的所有元素值都为1，执行return 1，则将逻辑值传到主函数中，执行printf语句输出任意两个房间之间是连通的；如果只要有一个数组的元素值是0，执行return 0，则将逻辑值传到主函数中，执行printf语句输出不是任意两个房间之间都是互相连通的。6.上机调试情况记录：6.1语法错误及修改：由于本课程实验题目代码不是很多，所以不会出现像以前C+课程设计时第一次运行时有五六十个错误的现象了，但自己这次开始还是有不少语法错误的，例如error C2143: syntax error : missing ; before ，就说明我在某一行有一个“；”漏写了；error C2065: q : undeclared identifier表明我q没有定义；missing ) before identifier scanf也是一个语法错误，其实很简单，就是我在前面一句程序中漏掉了一个双引号；我还遇到了一个提醒，虽然这个提醒可能不会对我的运行结果造成影响，但总感觉程序不是很完美，必须让程序一个错误都没才是最好的，这个错误时这样的，warning C4715: Chick : not all control paths return a value，经过分析，自己豁然开朗，我开始是这样写的，if(*G).edgesij=0) return 0; else return 1;但是else应该是多余的，只要执行if语句，再执行return 0后，就会跳出子函数不会再执行return 1了，反之就直接执行return 1跳出子函数，而return 0不会执行。其实有很多类似地错误，但这些错误都很容易解决，根据提示就可以轻松改正过来。但这也侧面的放映我平时在编程序时没有养成一个好的习惯，比如在写printf（）时，括号里面应该直接写两个双引号，否则就很容易漏掉其中后面的一个双引号，造成语法的错误。6.2逻辑问题的修改和调整：在编这个程序的时候，逻辑问题并不像上面所说的语法错误那么容易修改了，其实还是这些逻辑错误给我制造了真正的麻烦，让我感觉到这个程序并不像自己想象的那么简单。虽然逻辑错误不多，就三四个，但个个都要花费自己大量的时间，通过自己不断的找资料，问老师同学来各个击破。现在就让我将这些逻辑错误一个个的描述出来：（1）当我把Change（）函数写在Findroad（）函数的下面时，就会出现两个错误，分别是error C2065: Change : undeclared identifier和error C2373: Change : redefinition; different type modifiers，我当时真的不能理解为什么这个Change（）函数有错误了，并一遍又一遍的检查了Change（）函数，可是还是发现不了到底是哪错了，然后自己只有求助网络了，把错误百度一下，上面有人说这可能是函数没有声明问题，后来自己仔细一想，记得老师上课讲过，在调用某个函数之前有时需要声明一下这个函数，还有一种解决的办法就是把即将调用的函数放在这个函数的前面，所以我立刻将Change（）函数放在了Findroad（）函数的前面了，结果这两个问题解决了，我万分高兴。（2）这个错误说让我最头疼的，因为我对指针只是略知皮毛，当时我并不知道MGraph mg1,*mg=&mg1这个用法，只写了MGraph *mg；，结果显示是0个错误，0个提醒，可当我输入数据时，按下Enter键，结果令我失望的是出现了下面的图片，如图6：图6 运行时出现的错误截图我真不知道为什么会出现这样的情况，为什么显示没有错误时，还会运行不了了，我都蒙了，看了一下错误提示，不知道“Oxcccccccc”内存不能为“written”是什么意思，真是让我空欢喜一场，我查询了数据结构的书后程序，才知道原来首先是需要定义一个MGraph类型的数据mg1，然后吧mg1的地址赋给mg，即MGraph mg1,*mg=&mg1，虽然不知道上面的错误时什么意思，但最终问题还是解决了。（3）老实说，这根本不算是一个错误，因为在运行时没有任何错误，可以进入用户界面，但实验结果就是不跟自己预想的一样，显然是个逻辑错误，运行的错误如图7：图7 运行后输出错误结果的截图根据上图分析，显然邻接矩阵和转换后的矩阵都没有输出来，但是还输出了结果，程序在运行时没有执行Create（）和Findroad（）函数，结果我请教了老师，他把我的程序一看，说我在Create（）函数没有将变量n、e和结构体的变量房间数n、门数e联系起来，应该在输入房间数和门数之后再写上(*mg).n=n; (*mg).e=e;，之后便没有出项上面的错误了。最后输出的结果也是正确的了。6.3时间性能分析：本算法的时间复杂度还是非常高的，由于在该程序中，用到了大量的for循环，需要依次寻找直接相连的房间，而且在把所有的直接相连的房间找到后，还要利用for循环，将所有的间接相连的房间给找到，最后还要输出图的邻接矩阵和转换后的矩阵，根据转换后的矩阵来判断任意的两个房间是否相连通的，所有该程序在出现最坏情况时侯时间复杂度是O（6n2+10n+4），不断的对图进行搜索和遍历。因此需要对这个算法进行优化，我有一个改进措施，就是有的不是连通的房间希望不要遍历，设定一个标记位。但由于时间原因和自己的知识掌握程度，只能在课下通过不断的查找资料学习思考和请教老师同学来优化这个算法了。7.测试用例结果及其分析：现在该程序已经没有错误了，当运行后，首先出现的是以下用户界面，如图8：图8 初始用户界面上图是初始用户界面，可以设定用户所规定的房间数目和门的数目，例如现在规定房间数目为4个，门的数目为6个。接下来便是输入门的出口和入口信息了，如图9：图9 输入门信息后的用户界面上图显示已经输入了各个门的信息了，例如第一个门的出口和入口分别是1和2，第二个门的出口和入口分别是1和3，第三个门的出口和入口分别是2和4，最后将六个门的信息都输入完毕以后，便能输出矩阵以及最后的判断结果了，如图10：图10 输出矩阵和判断结果根据图10，我们能很显然的看出图的邻接矩阵经过转换后，矩阵元素全部都为1，所以可以得出结论任意两个房间直接是互相连通的。上面的测试实例图是连通的，现在我们来简单的举个数据结构课本上的一个图作为实例，来说明当不是所有的房间都是连通的情况，例图（数据结构与算法P316图10-16）如图11：123456 图11 输出结果不是都连通的例图如果我们按照图11来输入房间数和门数，并输入七个门的出口和入口，便会得到如图12的用户界面：图12 输出结果不是都连通的用户界面根据图12我们可得出结论，当通过图的邻接矩阵转换得来的矩阵，如果有一个为0，则这个图就不是所有的结点都是互相连通的，即是指不是所有的房间都是连通的。8.用户使用说明：本实验运行过程时带有提示性语句。由于本程序可以对不同情况下的房间进行判断，所以在运行开始时根据提示分别输入房间数目和门的数目。在这要说明一下，由于本实验要通过大量的for循环来实现最终功能，时间复杂度很高，所以建议用户在输入房间数目和门的数目时，要考虑到运行时间情况，不要将房间数和门数设得很大。其次，再根据提示语句信息，依次输入每个门的出口和入口。最后便可以看到图的矩阵信息和对图的判断结果。9.参考文献：1 王昆仑，李红. 数据结构与算法. 北京：中国铁道出版社，2011年1月。2 严蔚敏，吴伟民.数据结构.北京：清华大学出版社，2006年1月。3 蒋盛益.数据结构(学习指导与训练).北京：中国水利水电出版社，2003年8月。4 李红，王昆仑.数据结构实验指导.合肥：合肥学院，2009年2月。5 何钦铭，颜辉.C语言程序设计.北京：高等教育出版社，2009年5月。6 张引.C程序设计基础课程设计.杭州：浙江大学出版社，2007年1月。10.附录（完整源程序）：#include stdio.h#define Maxsize 100 /*房间的最大个数*/typedef struct /*定义图的类型*/int n; /*房间数目*/int e; /*门的数目*/int edgesMaxsizeMaxsize; /*二维数组，存储门的信息*/MGraph;MGraph *Create( ) /*有向图的建立*/ int door_out,door_in,i,n,e,j,q=0; MGraph mg1,*mg=&mg1; printf(请输入房间数目和门的数目:); /*读入房间数和门数*/ scanf(%d,&n); scanf(%d,&e); (*mg).n=n; (*mg).e=e; for(i=0; in; i+) for(j=0; jn; j+) (*mg).edgesij=0; /*先把所有的边置空*/ for(i=0; ie; i+) printf(请输入第%d个门的出口和入口:,i+1); scanf(%d%d,&door_out,&door_in); (*mg).edgesdoor_out-1door_in-1=1; /*直接相连的边赋值为1*/ printf(该图的邻接矩阵如下:n); for(i=0;i(*mg).n;i+) /*输出邻接矩阵*/ for(j