大数据结构与算法课程设计程序及报告材料

1、实用文案数据结构与算法课程设计报告题目两两相连的房间问题：一所奇怪的房子，这所房子里有n个房间，每个房间里有一些门通向别的房间，可是这些门十分奇怪，它们只能从房间a开向房间b，也就是说，一扇从a开向b的门是不能让一个人从b房间走到a房间的。你能计算一下任意两个房间之间都互相相通吗？问题分析此程序需要完成如下要求：在这所房子里，从任意一个房间开始，按照开门的方向，均能够找到一个合适的路线，使得一个人能够不重复的到达其他的每一个房间，所以，需以每一个房间都为一次起始点来走向其他的房间，以此来判断这所房子里的任意两个房间之间是否互相相通。实现本程序需要解决以下问题：1.如何表示每一个房间，即存储房间

2、的信息，并且还要确定这所房子里的各个房间的位置。2.各个房间之间的门，以及门是从哪个房间开向哪个房间的该如何表示和存储的。3.从某一个房间开始，如何走到其他各个房间，即如何对房间进行遍历。4.为了在遍历过程中，不重复的遍历每一个房间，该如何标记已被遍历过的房间，从而只访问未走过的房间。5.最后通过什么的遍历方式才能判断各个房间之间是否互相相通。标准文档实用文案数据结构的选择和概要设计通过对题目要求的理解，我们可以用图来表示这所房子，而房子中的各个房间就相当于图中的各个结点，由于房间的门是有方向的，一扇从a开向b的门是不能让一个人从b房间走到a房间的，从而可知该图为有向图，那么门就相当于有向图中

3、的弧，从一个门开向另一个门即代表有向图中弧的起始点和终止点。对于图的存储，我采用邻接表的形式来存储，并将每一个房间进行编号，对于邻接表，则需要定义一个邻接表结点类型、邻接表表头结点类型，通过表头与结点的连接而将有向图中弧的信息存储起来。那么人从任意一个房间走向另一个房间，即相当于有向图中从一个结点按照弧的信息访问其他的结点，可以采用深度优先搜索遍历。如果从每一个结点以起始点开始一次遍历就都能访问到其他结点的话则说明有向图是连通图，即该房子里的各个房间能够互相相通。定义一个全局的整形变量flag，如果是连通图的话则flag=1，否则flag=0。程序实现的流程图如下：定义邻接表结点类型、邻接表表

4、头结点类型给各个房间编号，以方便存储初始化各个房间，标记让其开始都为被访问过创建邻接表函数，由用户输入房间和门的信息，并存入邻接表中建立深度优先搜索函数，用递归的方式来遍历各个房间main（）调用创建邻接表函数和深度优先搜索函数标准文档否两两房间不可以互相相通flag是否等于1是两两房间可以互相相通实用文案算法思想主要是把现实中的房子转换成数据结构与算法中图的思想，并用邻接表的存储方式来存储图，房子里的房间即相当于图中的一个个结点，门只能从一个房间开向另一个房间，则说明了该图是有向图，那么遍历的过程中只能按照有向图中弧所指的方向来遍历。在深度优先搜索遍历的算法中，对于连通图的遍历，以某一个结点

5、为起始点开始遍历，只需要遍历一次就可以访问到所有的结点，所以以此条件来判断该图是否是连通图，即可得出房子里的各个房间是否可以互相相通。详细设计和主要编码段首先结构体类型，分别是邻接表中结点结构类型arcnode，其包含存储房间号码的整标准文档实用文案形变量adjvex，和指向下一个结点的指针nextarc。邻接表中表头结点结构类型vexnode，其同样包含存储房间号码的整形变量vexdata，和指向第一个邻接点的指针firstarc，同时定义一个vexnode类型的一维数组，依次将房间的信息存储在这个一位数组中。最后定义一个邻接表的结构体类型，其中包含vexnode类型的一维数组，将房子中所有

6、的房间号码有序的存储在一维数组中，以及两个记录房间个数和门的个数的整形变量。通过以上结构体类型的定义，即可得到一个邻接表的存储方式，从而将房子转换成图的思想把每个房间和每个门的信息都存储在邻接表中。对于建立邻接表的函数，也就是将房间和门的信息由用户输入并存储在邻接表中。将房间编号以后，对邻接表的表头结点进行初始化：首先将房间的信息存储进表头结点中：for(i=1;iadjvex中，采用头标准文档实用文案插法，将表头结点中firstarc指针所指向结点全部赋给p指针中的nextarc指针，再让表头结点中的firstarc重新指向新生成的链表。代码如下：printf(请输入开门的方向(如门从001

7、号房间开向010号房间，那么就输入001010)：n);for(i=0;iadjvex=k;p-nextarc=alj.firstarc;alj.firstarc=p;对于深度优先搜索遍历，我额外又定义了一个函数dfs_trave(algraphalg)，该函数的作用一是对所有的房间信息进行初始化，标记其未被访问过，二是在调用深度优先搜索遍历函数后，判读各个房间之间是否可以互相相通。在访问房间的过程中，由于需要以每一个房间都为一次初始点开始遍历，进行一次深度优先搜索遍历后，必须其他的每一个房间都被标记访问过了，才能代表各个房间之间是可以互相相通的。注意，证明房间之间互相相通即证明该有向图为连通

8、图，则以每一个房间为起始点时只要进行一次深度优先搜索遍历，就能使每个结点都被访问过，这才能说明它是连通图，否则就不是连通图，即各个房间之间无法互相相通。那么在标记房间是否被访问过，采用二维数组的方式标记visitedij。该二维数组的行下标代表以哪个房间为起始点开始遍历的，即存储起始点房间的号码，用num表示，在一次遍历中num的值是不变的，因为一次遍历始终是以该房间为起始点的，列下表代表访问到哪个房间，也存储该房间的号码，所以列下表在一次遍历中是变化的。初始化该标准文档实用文案数组时，令二维数组中所有的值都为0，代表所有的房间都未被访问过，当某一个房间被访问过，则将代表这个房间的二维数组的值

9、变为1，如：以005号房间为起始点，访问到了012号房间，则令visited512=1。代码如下：voiddfs_trave(algraphalg)inti,j;for(i=1;i=alg.vexnum;i+)for(j=1;j=alg.vexnum;j+)visitedij=0;for(num=1;num=alg.vexnum;num+)dfs(alg,num);for(i=1;i=alg.vexnum;i+)for(j=1;jadjvex=0)dfs(alg,p-adjvex);p=p-nextarc;上机调试情况记录1.在定义邻接表结点结构类型中，刚开始的定义如下：typedefstru

10、ctintadjvex;arcnode*nextarc;arcnode;出现了下图所示的错误提示：标准文档实用文案经检查，得知，在结构体类型中，定义arcnode*nextarc中，编译器还不知道arcnode是什么意思，所以无法定义一个arcnode类型的指针变量，故需将代码改为：typedefstructarcnodeintadjvex;arcnode*nextarc;arcnode;2.在刚开始运行时，输入的不是连通图，程序输出的结果却是：“任意两个房间都可以互相相通！”原因是由于，刚开始在标记房间是否被访问过时我用的是一维数组来标记的，而默认人从第一个房间开始走向其他房间，当一次深度优

11、先搜索遍历后，所有的房间都能够被访问过，即说明这个人都能够到达其他的所有房间，则说明各个房间之间是互相相通的。错就错在我默认以第一个房间为起始点去遍历其他房间，即使一次遍历后其他所有的房间都能够被访问过，也只能说明从第一个房间能够到达其他的所有房间，并不能说明从其它的房间开始能够到达所有的房间。所以，需要以每一个房间都为一次起始点开始遍历，所以应该采用二维数组来标记房间是否被访问过，只有以每一个房间为起始点都能访问到其他房间，才能说明各个房间之间是可以互相相通的。3.还有个小错误，就是在if条件判断时，又是把判断相等的符号写成了赋值，即两个等号写成了一个等号，导致结果怎么也不对。标准文档实用文

12、案测试用例、结果及其算法性能分析标准文档实用文案性能分析：在建立邻接表函数create_adjlistgraph()中，在输入房间的个数后，对各个房间的信息进行初始化的时间性能为o(n)，输入门的信息后，对开门的方向存入各个结点中，其时间性能为o(e)，最后又将表头结点中一维数组的值一一赋给了定义的一个邻接，表类型的变量alg中的一维数组vexticesi其时间性能为o(n)，故总的时间性能为o(2n+e)。在深度优先搜索遍历函数中，采用了递归的方法，而每一个房间都要调用n次深度优先搜索遍历函数，故n个房间在深度优先搜索中的时间性能为o(n)。用户使用说明1.房间数目最多为100个，所以在输入

13、房间数目时应输入少于100的整数。2.输入开门的方向时，如果门是从001号房间开向012号房间，则输入001012，两个房间之间用空格分开，不能用逗号或其他符号，并且房间号码也要输入整数，前面0可以写也可以不写。3.当输入结束后，均以回车键结束。标准文档实用文案参考文献1王昆仑，李红.数据结构与算法.北京：中国铁道出版社，2011.附录（完整源程序）#include#include#definemax_vertex_num100intflag=1;intnum;intvisitedmax_vertex_nummax_vertex_num;/visited二维数组用于判断每个房间是否都被访问过t

14、ypedefstructarcnode/邻接表中结点结构类型的定义intadjvex;arcnode*nextarc;arcnode;typedefstruct/邻接表表头结点结构类型的定义intvexdata;arcnode*firstarc;/指向第一个邻接点标准文档实用文案vexnode;typedefstruct/邻接表类型的定义vexnodevexticesmax_vertex_num;intvexnum,arcnum;/vexnum记录房间的个数，arcnum记录门的个数algraph;algraphcreate_adjlistgraph()/建立邻接表函数，将房间和门存入邻接表中

15、inti,j,k,n,e;arcnode*p;vexnodealmax_vertex_num;printf(请输入房间的数目：);scanf(%d,&n);for(i=1;i=n;i+)/初始化表头结点数组ali.vexdata=i;ali.firstarc=null;printf(请输入门的数目：);scanf(%d,&e);printf(请再输入开门的方向(比如门从号房间开向号房间，那么就输入010)：n);for(i=0;iadjvex=k;p-nextarc=alj.firstarc;alj.firstarc=p;algraphalg;for(i=1;iadjvex=0)dfs(alg,p-adjvex);p=p-nextarc;标准文档实用文案voiddfs_trave(algraphalg)inti,j;for(i=1;i=alg.vexnum;i+)for(j=1;j=alg.vexnum;j+)visitedij=0;/初始化访问数组，即让每一个结点都未被访问过for(num=1;n