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

数据结构与算法课程设计报告题目两两相连的房间问题：一所奇怪的房子，这所房子里有n个房间，每个房间里有一些门通向别的房间，可是这些门十分奇怪，它们只能从房间a开向房间b，也就是说，一扇从a开向b的门是不能让一个人从b房间走到a房间的。你能计算一下任意两个房间之间都互相相通吗？问题分析此程序需要完成如下要求：在这所房子里，从任意一个房间开始，按照开门的方向，均能够找到一个合适的路线，使得一个人能够不重复的到达其他的每一个房间，所以，需以每一个房间都为一次起始点来走向其他的房间，以此来判断这所房子里的任意两个房间之间是否互相相通。实现本程序需要解决以下问题：如何表示每一个房间，即存储房间的信息，并且还要确定这所房子里的各个房间的位置。各个房间之间的门，以及门是从哪个房间开向哪个房间的该如何表示和存储的。从某一个房间开始，如何走到其他各个房间，即如何对房间进行遍历。为了在遍历过程中，不重复的遍历每一个房间，该如何标记已被遍历过的房间，从而只访问未走过的房间。最后通过什么的遍历方式才能判断各个房间之间是否互相相通。数据结构的选择和概要设计通过对题目要求的理解，我们可以用图来表示这所房子，而房子中的各个房间就相当于图中的各个结点，由于房间的门是有方向的，一扇从a开向b的门是不能让一个人从b房间走到a房间的，从而可知该图为有向图，那么门就相当于有向图中的弧，从一个门开向另一个门即代表有向图中弧的起始点和终止点。对于图的存储，我采用邻接表的形式来存储，并将每一个房间进行编号，对于邻接表，则需要定义一个邻接表结点类型、邻接表表头结点类型，通过表头与结点的连接而将有向图中弧的信息存储起来。那么人从任意一个房间走向另一个房间，即相当于有向图中从一个结点按照弧的信息访问其他的结点，可以采用深度优先搜索遍历。如果从每一个结点以起始点开始一次遍历就都能访问到其他结点的话则说明有向图是连通图，即该房子里的各个房间能够互相相通。定义一个全局的整形变量flag，如果是连通图的话则flag=1，否则flag=0。程序实现的流程图如下:算法思想主要是把现实中的房子转换成数据结构与算法中图的思想，并用邻接表的存储方式来存储图，房子里的房间即相当于图中的一个个结点，门只能从一个房间开向另一个房间，则说明了该图是有向图，那么遍历的过程中只能按照有向图中弧所指的方向来遍历。在深度优先搜索遍历的算法中，对于连通图的遍历，以某一个结点为起始点开始遍历，只需要遍历一次就可以访问到所有的结点，所以以此条件来判断该图是否是连通图，即可得出房子里的各个房间是否可以互相相通。详细设计和主要编码段首先结构体类型，分别是邻接表中结点结构类型Arcnode，其包含存储房间号码的整形变量adjvex，和指向下一个结点的指针nextarc。邻接表中表头结点结构类型Vexnode，其同样包含存储房间号码的整形变量vexdata，和指向第一个邻接点的指针firstarc，同时定义一个Vexnode类型的一维数组，依次将房间的信息存储在这个一位数组中。最后定义一个邻接表的结构体类型，其中包含Vexnode类型的一维数组，将房子中所有的房间号码有序的存储在一维数组中，以及两个记录房间个数和门的个数的整形变量。通过以上结构体类型的定义，即可得到一个邻接表的存储方式，从而将房子转换成图的思想把每个房间和每个门的信息都存储在邻接表中。对于建立邻接表的函数，也就是将房间和门的信息由用户输入并存储在邻接表中。将房没有落日般的瑰丽，没有流云般的飘逸，但可以有水晶般的清纯与透明。没有大山般的巍峨，没有湖水般的轻柔，但可以有岩石般的坚毅与稳重。没有大海般的浩瀚，没有瀑布般的飞泻，但可以有泥土般的朴素与随和。风从水上走过，留下粼粼波纹;骆驼从沙漠上走过，留下深深的脚印;哨鸽从天空飞过，留下串串欢韵;岁月从树林穿过，留下圈圈年轮。啊，朋友，我们从时代的舞台走过，将给社会留下些什么?花从春走过，留下缕缕花香;叶从夏走过，留下片片荫凉;风从秋走过，留下阵阵金浪;雪从冬走过，留下种种希望。啊，朋友，我们从人生的四季走过，将给人生留下些什么？间编号以后，对邻接表的表头结点进行初始化：首先将房间的信息存储进表头结点中：for(i=1;i<=n;i++){al[i].vexdata=i;al[i].firstarc=NULL;}数组al[i]是表头结点Vexnode类型的，将房间的号码存储在一维数组中的vexdata中，并让al[i]的指针域初始化指向空。其次将门的信息存储在邻接表中，即通过表头结点中的firstarc指针域来指向第一个邻接点，然后其它邻接点的nextarc指针域又指向下一个结点，从而将各个房间串起来。在用户输入门的信息时，如果门是从001号房间开向010号房间的，则让用户输入001010，即确定了开门的方向，就相当于有向图中输入弧的起始点和终止点，即可将门的所有信息都存储进来了，从而将这所房子用图的思想存储在邻接表中。其中，每输入一个门的信息，则动态生成一个结点，让一个指针p指向该结点，将弧的终止点存入p->adjvex中，采用头插法，将表头结点中firstarc指针所指向结点全部赋给p指针中的nextarc指针，再让表头结点中的firstarc重新指向新生成的链表。代码如下：printf("请输入开门的方向(如门从001号房间开向010号房间，那么就输入001010)：\n");for(i=0;i<e;i++){scanf("%d%d”,&j,&k);p=(Arcnode*)malloc(sizeof(Arcnode));p->adjvex=k;p->nextarc=al[j].firstarc;al[j].firstarc=p;}对于深度优先搜索遍历，我额外又定义了一个函数DFS_trave(ALGraphalg),该函数的作用一是对所有的房间信息进行初始化，标记其未被访问过，二是在调用深度优先搜索遍历函数后，判读各个房间之间是否可以互相相通。在访问房间的过程中，由于需要以每一个房间都为一次初始点开始遍历，进行一次深度优先搜索遍历后，必须其他的每一个房间都被标记访问过了，才能代表各个房间之间是可以互相相通的。注意，证明房间之间互相相通即证明该有向图为连通图，则以每一个房间为起始点时只要进行一次深度优先搜索遍历，就能使每个结点都被访问过，这才能说明它是连通图，否则就不是连通图，即各个房间之间无法互相相通。那么在标记房间是否被访问过，采用二维数组的方式标记visited[i][j]。该二维数组的行下标代表以哪个房间为起始点开始遍历的，即存储起始点房间的号码，用num表示，在一次遍历中num的值是不变的，因为一次遍历始终是以该房间为起始点的，列下表代表访问到哪个房间，也存储该房间的号码，所以列下表在一次遍历中是变化的。初始化该数组时，令二维数组中所有的值都为0，代表所有的房间都未被访问过，当某一个房间被访问过，则将代表这个房间的二维数组的值变为1，如：以005号房间为起始点，访问到了012号房间，则令visited[5][12]=1。代码如下：voidDFS_trave(ALGraphalg){inti,j;for(i=1;i<=alg.vexnum;i++)for(j=1;j<=alg.vexnum;j++)visited[i][j]=0;for(num=1;num<=alg.vexnum;num++)DFS(alg,num);for(i=1;i<=alg.vexnum;i++)for(j=1;j<=alg.vexnum;j++)if(visited[i][j]==0){flag=0;break;}if(flag==1)printf("任意两个房间都可以互相相通！”)；elseprintf("任意两个房间都不可以互相相通！”)；}在深度优先搜索函数中，采用递归的方法反复调用深度优先搜索函数，定义一个指针p，当指针指向某一个结点时，判断该结点是否为空，如不为空，再判断该结点是否被访问过，如果没有被访问过，则调用一次深度优先搜索遍历函数，并对该结点标记上已被访问过，当遍历到某一个结点的指针域firstarc指向NULL时，并且其它的结点都被访问过了，则一次遍历结束。代码如下：voidDFS(ALGraphalg,inti){visited[num][i]=1;Arcnode*p=alg.vextices[i].firstarc;while(p!=NULL){if(visited[num][p->adjvex]==0)DFS(alg,p->adjvex);p=p->nextarc;}}上机调试情况记录在定义邻接表结点结构类型中，刚开始的定义如下：typedefstruct{intadjvex;Arcnode*nextarc;}Arcnode;出现了下图所示的错误提示：日rror匚2143：syntaxmirror:miwwirLg'beEore：'errorC4430:missingtypespecifier-intaEEuiriHil.Note:C++dueEnotsupportdefault-int:errorC4430:miEsingtyjwspecifier-intaseijitied.Note：C++doesnotsupportdefaijlt-interrorC2039:'rLext：=Lt_cJ:isnutamemberofJAi-cnode''cpp(8):seedecl：=Lra+ionofJAi-crLode-'errorC2039:'rLext：=Lrc'':isnotamemberof'虹血门腥'■zpp(8):seedecl：=LrationofJAi-cnode''>1经检查，得知，在结构体类型中，定义Arcnode*nextarc中，编译器还不知道Arcnode是什么意思，所以无法定义一个Arcnode类型的指针变量，故需将代码改为：typedefstructArcnode{intadjvex;Arcnode*nextarc;}Arcnode;在刚开始运行时，输入的不是连通图，程序输出的结果却是：''任意两个房间都可以互相相通！〃原因是由于，刚开始在标记房间是否被访问过时我用的是一维数组来标记的，而默认人从第一个房间开始走向其他房间，当一次深度优先搜索遍历后，所有的房间都能够被访问过，即说明这个人都能够到达其他的所有房间，则说明各个房间之间是互相相通的。错就错在我默认以第一个房间为起始点去遍历其他房间，即使一次遍历后其他所有的房间都能够被访问过，也只能说明从第一个房间能够到达其他的所有房间，并不能说明从其它的房间开始能够到达所有的房间。所以，需要以每一个房间都为一次起始点开始遍历，所以应该采用二维数组来标记房间是否被访问过，只有以每一个房间为起始点都能访问到其他房间，才能说明各个房间之间是可以互相相通的。还有个小错误，就是在if条件判断时，又是把判断相等的符号写成了赋值，即两个等号写成了一个等号，导致结果怎么也不对。测试用例、结果及其算法性能分析

请锄入房间的数目：4请亲入右的数ao请医输入开门的方向《比如门从3131淞32&304，那么就输A001010＞：.±.请锄入房间的数目：4请亲入右的数ao请医输入开门的方向《比如门从3131淞32&304，那么就输A001010＞：.±.跚3跚1002003意两个房间都可以互相相通!请按任意键继续;--，那么就输A001010＞：输入开I。届方向《比如门从叫1号房间开向阪。号房间3101愁3&3959505002SB5SB5碱翎1任意两个房间都不可以相通！请按任意键继续---eC:\¥TKDQ¥S\syst3101愁3&3959505002094005094005002H01005002094005094005002H01005潮3涵1顷碱泗3S04润4b弱…•遂意两个房间都可以互相相通！请技任意键继续;,.•一性能分析：在建立邻接表函数create_AdjListGraph()中，在输入房间的个数后，对各个房间的信息进行初始化的时间性能为O(n)，输入门的信息后，对开门的方向存入各个结点中，其时间性能为0(e)，最后又将表头结点中一维数组的值一一赋给了定义的一个邻接表类型的变量alg中的一维数组vextices[i]，其时间性能为0(n)，故总的时间性能为0(2n+e)。在深度优先搜索遍历函数中，采用了递归的方法，而每一个房间都要调用n次深度优先搜索遍历函数，故n个房间在深度优先搜索中的时间性能为0(n2)。

用户使用说明房间数目最多为100个，所以在输入房间数目时应输入少于100的整数。输入开门的方向时，如果门是从001号房间开向012号房间，则输入001012，两个房间之间用空格分开，不能用逗号或其他符号，并且房间号码也要输入整数，前面0可以写也可以不写。当输入结束后，均以回车键结束。参考文献[1]王昆仑，李红.数据结构与算法.北京：中国铁道出版社，2011.附录(完整源程序)#include<stdio.h>#include<malloc.h>#defineMAX_VERTEX_NUM100intflag=1;intnum;intvisited[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//visited二维数组用于判断每个房间是否都被访问过typedefstructArcnode{〃邻接表中结点结构类型的定义intadjvex;Arcnode*nextarc;}Arcnode;typedefstruct{intvexdata;Arcnode*firstarc;}Vexnode;typedefstruct{intvexdata;Arcnode*firstarc;}Vexnode;Vexnodevextices[MAX_VERTEX_NUM];intvexnum,arcnum;//vexnum记录房间的个数，arcnum记录门的个数}ALGraph;ALGraphcreate_AdjListGraph(){〃建立邻接表函数，将房间和门存入邻接表中inti,j,k,n,e;风从水上走过，留下粼粼波纹;骆驼从沙漠上走过，留下深深的脚印;哨鸽从天空飞过，留下串串欢韵;岁月从树林穿过，留下圈圈年轮。啊，朋友，我们从时代的舞台走过，将给社会留下些什么?花从春走过，留下缕缕花香;叶从夏走过，留下片片荫凉;风从秋走过，留下阵阵金浪;雪从冬走过，留下种种希望。啊，朋友，我们从人生的四季走过，将给人生留下些什么？Arcnode*p;Vexnodeal[MAX_VERTEX_NUM];printf("请输入房间的数目：");scanf("%d”,&n);for(i=1;i<=n;i++){〃初始化表头结点数组al[i].vexdata=i;al[i].firstarc=NULL;}printf("请输入门的数目：");scanf("%d",&e);printf("请再输入开门的方向(比如门从号房间开向号房间，那么就输入010)：\n");for(i=0;i<e;i++){scanf("%d%d",&j,&k);p=(Arcnode*)malloc(sizeof(Arcnode));p->adjvex=k;p->nextarc=al[j].firstarc;al[j].firstarc=p;}ALGraphalg;for(i=1;i<=n;i++)alg.vextices[i]=al[i];〃将al数组中的房间号依次存储在邻接表表头结点的一维数组vextices中alg.vexnum=n;alg.arcnum=e;returnalg;}