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

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 类型的一维数组， 依次将房间的信息存储在这个一位数组中。最后定义一个邻接表的结构体类型，其中包含Vexnod

6、e类型的一维数组，将房子中所有的房间有序的存储在一维数组中， 以及两个记录房间个数和门的个数的整形变量。通过以上结构体类型的定义，即可得到一个邻接表的存储方式，从而将房子转换成图的思想把每个房间和每个门的信息都存储在邻接表中。对于建立邻接表的函数，也就是将房间和门的信息由用户输入并存储在邻接表中。将房间编号以后，对邻接表的表头结点进行初始化：首先将房间的信息存储进表头结点中：for(i=1;i<=n;i+)ali.vexdata=i;ali.firstarc=NULL;让数组 ali 是表头结点Vexnodeali 的指针域初始化指向空。类型的，将房间的存储在一维数组中的vexdata中

7、，并其次将门的信息存储在邻接表中，即通过表头结点中的firstarc 指针域来指向第一个邻接点，然后其它邻接点的nextarc 指针域又指向下一个结点，从而将各个房间串起来。在用户输入门的信息时，如果门是从001 号房间开向010 号房间的，则让用户输入001010 ，即确定了开门的方向，就相当于有向图中输入弧的起始点和终止点，即可将门的所有信息都存储进来了，从而将这所房子用图的思想存储在邻接表中。其中，每输入一个门的信息，则动态生成一个结点，让一个指针p 指向该结点，将弧的终止点存入p->adjvex中，采用头插法，将表头结点中firstarc 指针所指向结点全部赋给p 指针中的nex

8、tarc 指针，再让表头结点中的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=alj.firstarc;alj.firstarc=p;对于深度优先搜索遍历，我额外又定义了一个函数DFS_trave(ALGraph alg)

9、，该函数的作用一是对所有的房间信息进行初始化，标记其未被访问过，二是在调用深度优先搜索遍历函数后， 判读各个房间之间是否可以互相相通。在访问房间的过程中，由于需要以每一个房间都为一次初始点开始遍历，进行一次深度优先搜索遍历后，必须其他的每一个房间都被标记访问过了， 才能代表各个房间之间是可以互相相通的。注意，证明房间之间互相相通即证明该有向图为连通图，则以每一个房间为起始点时只要进行一次深度优先搜索遍历，就能使每个结点都被访问过，这才能说明它是连通图，否则就不是连通图，即各个房间之间无法互相相通。那么在标记房间是否被访问过，采用二维数组的方式标记visitedij。该二维数组的行下标代表以哪个

10、房间为起始点开始遍历的，即存储起始点房间的，用num 表示，在一次遍历中num 的值是不变的，因为一次遍历始终是以该房间为起始点的，列下表代表访问到哪个房间， 也存储该房间的，所以列下表在一次遍历中是变化的。初始化该数组时，令二维数组中所有的值都为0，代表所有的房间都未被访问过，当某一个房间被访问过，则将代表这个房间的二维数组的值变为1，如：以 005 号房间为起始点，访问到了012 号房间，则令 visited512=1。代码如下：void DFS_trave(ALGraph alg)int i,j;for(i=1;i<=alg.vexnum;i+)for(j=1;j<=alg.

11、vexnum;j+)visitedij=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(visitedij=0)flag=0;break;if(flag=1)printf(" 任意两个房间都可以互相相通！");elseprintf(" 任意两个房间都不可以互相相通！");在深度优先搜索函数中， 采用递归的方法反复调用深度优先搜索函数， 定义一个指针 p ，当指针指向某一个结点时，判断该结点

12、是否为空，如不为空，再判断该结点是否被访问过，如果没有被访问过， 则调用一次深度优先搜索遍历函数， 并对该结点标记上已被访问过， 当遍历到某一个结点的指针域 firstarc 指向 NULL 时，并且其它的结点都被访问过了，则一次遍历结束。代码如下：void DFS(ALGraph alg,int i)visitednumi=1;Arcnode *p=alg.vexticesi.firstarc;while(p!=NULL)if(visitednump->adjvex=0)DFS(alg,p->adjvex);p=p->nextarc;上机调试情况记录1. 在定义邻接表结点结

13、构类型中，刚开始的定义如下： typedef structint adjvex;Arcnode *nextarc;Arcnode;出现了下图所示的错误提示：经检查，得知，在结构体类型中，定义Arcnode *nextarc中，编译器还不知道Arcnode是什么意思，所以无法定义一个Arcnode 类型的指针变量，故需将代码改为：typedef struct Arcnodeint adjvex;Arcnode *nextarc;Arcnode;2.在刚开始运行时，输入的不是连通图，程序输出的结果却是：“任意两个房间都可以互相相通！ ”原因是由于， 刚开始在标记房间是否被访问过时我用的是一维数组来

14、标记的，而默认人从第一个房间开始走向其他房间，当一次深度优先搜索遍历后，所有的房间都能够被访问过，即说明这个人都能够到达其他的所有房间， 则说明各个房间之间是互相相通的。 错就错在我默认以第一个房间为起始点去遍历其他房间， 即使一次遍历后其他所有的房间都能够被访问过，也只能说明从第一个房间能够到达其他的所有房间， 并不能说明从其它的房间开始能够到达所有的房间。 所以， 需要以每一个房间都为一次起始点开始遍历， 所以应该采用二维数组来标记房间是否被访问过， 只有以每一个房间为起始点都能访问到其他房间， 才能说明各个房间之间是可以互相相通的。3. 还有个小错误，就是在 if 条件判断时，又是把判断

15、相等的符号写成了赋值，即两个等号写成了一个等号，导致结果怎么也不对。测试用例、结果及其算法性能分析性能分析：在建立邻接表函数create_AdjListGraph()中，在输入房间的个数后，对各个房间的信息进行初始化的时间性能为O(n) ，输入门的信息后，对开门的方向存入各个结点中，其时间性能为O(e) ，最后又将表头结点中一维数组的值一一赋给了定义的一个邻接表类型的变量alg 中的一维数组vexticesi ，其时间性能为O(n) ，故总的时间性能为O(2n+e) 。在深度优先搜索遍历函数中，采用了递归的方法，而每一个房间都要调用n 次深度优先搜索遍历函数，故n 个房间在深度优先搜索中的时间

16、性能为O(n2) 。用户使用说明1.房间数目最多为100 个，所以在输入房间数目时应输入少于100 的整数。2. 输入开门的方向时，如果门是从001 号房间开向 012 号房间，则输入 001 012 ，两个房间之间用空格分开，不能用逗号或其他符号，并且房间也要输入整数，前面0 可以写也可以不写。3.当输入结束后，均以回车键结束。参考文献1王昆仑，红 . 数据结构与算法. ：中国铁道，2011.附录（完整源程序）#include<stdio.h>#include<malloc.h>#define MAX_VERTEX_NUM 100int flag=1;int num;

17、int visitedMAX_VERTEX_NUMMAX_VERTEX_NUM;/visited二维数组用于判断每个typedef struct Arcnodeint adjvex;Arcnode *nextarc;Arcnode;房间是否都被访问过/ 邻接表中结点结构类型的定义typedef struct/ 邻接表表头结点结构类型的定义int vexdata;Arcnode *firstarc;/ 指向第一个邻接点Vexnode;typedef struct/ 邻接表类型的定义Vexnode vexticesMAX_VERTEX_NUM;int vexnum,arcnum;/vexnum记录

18、房间的个数，ALGraph;arcnum记录门的个数ALGraph create_AdjListGraph()int i,j,k,n,e;Arcnode *p;Vexnode alMAX_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;i<e;i+)scanf("%d%d",&j,&k);p=(Arcnode*)malloc(sizeof(Arcnode);p->adjvex=k;p->nextarc=alj.firstarc;alj.firstarc=p;ALGraph alg;for(i=1;i<=n;i+)alg.vexticesi=ali;/ 将al数组中的房间号依次存储在邻接表表头结