数据结构与算法课程设计程序及报告样本.docx
《数据结构与算法课程设计程序及报告样本.docx》由会员分享，可在线阅读，更多相关《数据结构与算法课程设计程序及报告样本.docx（12页珍藏版）》请在冰点文库上搜索。
数据结构与算法课程设计程序及报告样本
数据构造与算法课程设计报告
题目
两两相连房间问题：
一所奇怪房子，这所房子里有n个房间，每个房间里有某些门通向别房间，可是这些门十分奇怪，它们只能从房间a开向房间b，也就是说，一扇从a开向b门是不能让一种人从b房间走到a房间。
你能计算一下任意两个房间之间都互相相通吗？
问题分析
此程序需要完毕如下规定：
在这所房子里，从任意一种房间开始，按照开门方向，均可以找到一种适当路线，使得一种人可以不重复到达其她每一种房间，因此，需以每一种房间都为一次起始点来走向其她房间，以此来判断这所房子里任意两个房间之间与否互相相通。
实现本程序需要解决如下问题：
1.如何表达每一种房间，即存储房间信息，并且还要拟定这所房子里各个房间位置。
2.各个房间之间门，以及门是从哪个房间开向哪个房间该如何表达和存储。
3.从某一种房间开始，如何走到其她各个房间，即如何对房间进行遍历。
4.为了在遍历过程中，不重复遍历每一种房间，该如何标记已被遍历过房间，从而只访问未走过房间。
5.最后通过什么遍历方式才干判断各个房间之间与否互相相通。
数据构造选取和概要设计
通过对题目规定理解，咱们可以用图来表达这所房子，而房子中各个房间就相称于图中各个结点，由于房间门是有方向，一扇从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;iscanf（"%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（"任意两个房间都可以互相相通！
"）;
else
printf（"任意两个房间都不可以互相相通！
"）;
}
在深度优先搜索函数中，采用递归办法重复调用深度优先搜索函数，定义一种指针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;
}
}
上机调试状况记录
1.在定义邻接表结点构造类型中，刚开始定义如下：
typedefstruct{
intadjvex;
Arcnode*nextarc;
}Arcnode;
浮现了下图所示错误提示：
经检查，得知，在构造体类型中，定义Arcnode*nextarc中，编译器还不懂得Arcnode是什么意思，因此无法定义一种Arcnode类型指针变量，故需将代码改为：
typedefstructArcnode{
intadjvex;
Arcnode*nextarc;
}Arcnode;
2.在刚开始运营时，输入不是连通图，程序输出成果却是：
“任意两个房间都可以互相相通！
”
因素是由于，刚开始在标记房间与否被访问过时我用是一维数组来标记，而默认人从第一种房间开始走向其她房间，当一次深度优先搜索遍历后，所有房间都可以被访问过，即阐明这个人都可以到达其她所有房间，则阐明各个房间之间是互相相通。
错就错在我默认以第一种房间为起始点去遍历其她房间，虽然一次遍历后其她所有房间都可以被访问过，也只能阐明从第一种房间可以到达其她所有房间，并不能阐明从其他房间开始可以到达所有房间。
因此，需要以每一种房间都为一次起始点开始遍历，因此应当采用二维数组来标记房间与否被访问过，只有以每一种房间为起始点都能访问到其她房间，才干阐明各个房间之间是可以互相相通。
3.尚有个小错误，就是在if条件判断时，又是把判断相等符号写成了赋值，即两个等号写成了一种等号，导致成果怎么也不对。
测试用例、成果及其算法性能分析
性能分析：
在建立邻接表函数create_AdjListGraph（）中，在输入房间个数后，对各个房间信息进行初始化时间性能为O（n），输入门信息后，对开门方向存入各个结点中，其时间性能为O（e），最后又将表头结点中一维数组值一一赋给了定义一种邻接表类型变量alg中一维数组vextices[i]，其时间性能为O（n），故总时间性能为O（2n+e）。
在深度优先搜索遍历函数中，采用了递归办法，而每一种房间都要调用n次深度优先搜索遍历函数，故n个房间在深度优先搜索中时间性能为O（n²）。
顾客使用阐明
1.房间数目最多为100个，因此在输入房间数目时应输入少于100整数。
2.输入开门方向时，如果门是从001号房间开向012号房间，则输入001012，两个房间之间用空格分开，不能用逗号或其她符号，并且房间号码也要输入整数，前面0可以写也可以不写。
3.当输入结束后，均以回车键结束。
参照文献
[1]王昆仑，李红.数据构造与算法.北京：
中华人民共和国铁道出版社，.
附录（完整源程序）
#include
#include
#defineMAX_VERTEX_NUM100
intflag=1;
intnum;
intvisited[MAX_VERTEX_NUM][MAX_VERTEX_NUM]；//visited二维数组用于判断每个房间与否都被访问过
typedefstructArcnode{//邻接表中结点构造类型定义
intadjvex;
Arcnode*nextarc;
}Arcnode;
typedefstruct{//邻接表表头结点构造类型定义
intvexdata;
Arcnode*firstarc；//指向第一种邻接点
}Vexnode;
typedefstruct{//邻接表类型定义
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;iscanf（"%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;
}
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;
}
}
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（"任意两个房间都可以互相相通！
"）;
else
printf（"任意两个房间都不可以相通！
"）;
}
voidmain（）{//主函数
ALGraphAlg;
Alg=create_AdjListGraph（）;
DFS_trave（Alg）;
}
升级会员 