图的广度遍历课程设计报告.docx
《图的广度遍历课程设计报告.docx》由会员分享，可在线阅读，更多相关《图的广度遍历课程设计报告.docx（19页珍藏版）》请在冰点文库上搜索。
图的广度遍历课程设计报告
1.需求分析1
问题描述1
系统功能1
2
流程图2
结构体、函数及说明3
3.详细设计4
遍历函数设计4
容错性方式设计4
生成邻接表设计5
邻接表遍历设计6
4.程序源代码7
5.调试分析和测试结果16
调试分析16
调试案例16
测试进程、结果截图：
17
容错性测试：
17
无向图（案例一）测试：
20
有向图（案例二）测试：
22
6.课程设计总结24
参考文献25
1.需求分析
问题描述
（1）对任意给定的图（极点数和边数自定），成立它的邻接表并输出。
（2）然后利用队列的五种大体运算（置空队列、进队、出队、取队头元素、判队空）实现图的广度优先搜索遍历。
（3）画出搜索顺序示用意。
系统功能
（1）第一输入图的类型，有向或无向图（因为遍历与权值无关，因此没有涉及带权图）。
然后输入图的极点数、边数和各条边，以后生成该图的邻接表并输出。
（2）再输入要遍历该图的起点，然后从所输入的点广度搜索该图的邻接表，并按遍历顺序输出极点内容。
以后决定是不是继续遍历该图或输入另一个需要遍历的图亦或是终止程序。
流程图
开始
输入图的类型
确定图的类型
输入无向图
输入有向图
输入从哪个顶点开始遍历该图
广度优先遍历该图
是否从其他顶点开始重新遍历该图
是
否
是否结束
否
是
结束
图2-1流程图
结构体、函数及说明
typedefstructArcNode细设计
遍历函数设计
voidBFSTraverse（ALGraphG,queueQ,boolvisited[],intm,intn,void（*Visit）（int））irstarc=newArcNode;irstarc->adjvex=n2;irstarc->nextarc=NULL;irstarc;irstarc==NULL）
return-1;
return[u].firstarc->adjvex;
}
intNextAdjVex（ALGraphG,intu,intw）irstarc;
while（w!
=p->adjvex）
p=p->nextarc;
if（p->nextarc==NULL）return-1;
returnp->nextarc->adjvex;
}
voidBFSTraverse（ALGraphG,queueQ,boolvisited[],intm,intn,void（*Visit）（int））irstarc=NULL;
}
if==1）
{
cout<<"\n请输入图的弧数:
";
for（;;）
{
gets_s（s）;
t=atoi（s）;
n=*/2;
if==1）
n+=n;
if（t>n||t<1）
cout<<"错误!
请输入一个大于0小于"<";
else
break;
}
=t;
cout<<"\n请别离输入图的"<<<<"条弧（弧尾，弧头）:
"<for（inti=0;i<;i++）
{
intn1,n2;
for（;;）
{
cout<<"弧"<\t";
gets_s（s）;
strcpy_s（c,s）;
t=atoi（c）;
strcpy_s（c,s+2）;
n=atoi（c）;
if（t>||t<1||n>||n<1||t==n）
cout<<"错误!
请别离输入两个大于0小于"<<+1<<"的数:
\n\n";
else
break;
}
n1=t-1;n2=n-1;
if（!
visited[n1]）
{
visited[n1]=true;
[n1].firstarc=newArcNode;
[n1].firstarc->adjvex=n2;
[n1].firstarc->nextarc=NULL;
}
else
{
ArcNode*p=[n1].firstarc;
while（（p->nextarc）!
=NULL）
p=p->nextarc;
p->nextarc=newArcNode;
p->nextarc->adjvex=n2;
p->nextarc->nextarc=NULL;
}
}
}
else
{
cout<<"\n请输入图的边数:
";
for（;;）
{
gets_s（s）;
t=atoi（s）;
n=*/2;
if==1）
n+=n;
if（t>n||t<1）
cout<<"错误!
请输入一个大于0小于"<";
else
break;
}
=t;
cout<<"\n请别离输入图的"<<<<"条边（极点1，极点2）:
"<for（inti=0;i<;i++）
{
intn1,n2;
for（;;）
{
cout<<"边"<\t";
gets_s（s）;
strcpy_s（c,s）;
t=atoi（c）;
strcpy_s（c,s+2）;
n=atoi（c）;
if（t>||t<1||n>||n<1||t==n）
cout<<"错误!
请别离输入两个大于0小于"<<+1<<"的数:
\n\n";
else
break;
}
n1=t-1;n2=n-1;
if（!
visited[n1]）
{
visited[n1]=true;
[n1].firstarc=newArcNode;
[n1].firstarc->adjvex=n2;
[n1].firstarc->nextarc=NULL;
}
else
{
ArcNode*p=[n1].firstarc;
while（（p->nextarc）!
=NULL）
p=p->nextarc;
p->nextarc=newArcNode;
p->nextarc->adjvex=n2;
p->nextarc->nextarc=NULL;
}
if（!
visited[n2]）
{
visited[n2]=true;
[n2].firstarc=newArcNode;
[n2].firstarc->adjvex=n1;
[n2].firstarc->nextarc=NULL;
}
else
{
ArcNode*p=[n2].firstarc;
while（（p->nextarc）!
=NULL）
p=p->nextarc;
p->nextarc=newArcNode;
p->nextarc->adjvex=n1;
p->nextarc->nextarc=NULL;
}
}
}
do{
cout<<"\n邻接表:
\n";
for（intj=0;j<;j++）
{
visited[j]=false;
cout<ArcNode*p=[j].firstarc;
while（p）
{
cout<<"-->"<adjvex+1;
p=p->nextarc;
}
cout<}
cout<<"\n\n请输入遍历的起点:
";
for（;;）
{
gets_s（s）;
t=atoi（s）;
if（t>||t<1）
cout<<"错误!
请输入一个大于0小于"<<+1<<"的数:
";
else
break;
}
t-=1;
cout<<"\n广度遍历顺序:
\n";
queueQ;
for（intj=0;j<;++j）
visited[j]=false;
BFSTraverse（G,Q,visited,t,,print）;
BFSTraverse（G,Q,visited,0,t,print）;
cout<<"\n\n是不是继续从其他极点遍历此图（Y/N）：
";
for（;;）
{
gets_s（s）;
if（s[0]!
='y'&&s[0]!
='Y'&&s[0]!
='n'&&s[0]!
='N'）
cout<<"错误!
请输入半角字母Y或N:
";
else
break;
}
if（s[0]=='Y'||s[0]=='y'）system（"cls"）;
}while（s[0]=='Y'||s[0]=='y'）;
cout<<"\n是不是继续输入其他图进行遍历（Y/N）：
";
for（;;）
{
gets_s（s）;
if（s[0]!
='y'&&s[0]!
='Y'&&s[0]!
='n'&&s[0]!
='N'）
cout<<"错误!
请输入半角字母Y或N:
";
else
break;
}
}while（s[0]=='Y'||s[0]=='y'）;
cout<system（"pause"）;
return0;
}
5.调试分析和测试结果
编译、运行及调试环境:
MicrosoftVisualStudio2020Ultimate
调试分析
一．在求图的第u个极点，与其相邻的一系列极点中，第w个极点的下一个极点点时，假设是求最后一个极点的下一个极点时，因为是空指针因此返回值为0，程序误以为是第一个极点，再求下一个极点时便报错。
缘故是判定条件没有写好，于是增加判定，当指针为空时返回-1。
修改判定条件后，函数正常运行。
二．在输入图信息的时候，假设输入非法字符，程序会异样终止。
例如程序要求输入一个整型，用户却输入了一个字母，这时会显现异样。
只是程序是不是健壮性的一个表现。
先用字符串接收字符，转换成整型后再判定是不是符合要求。
若是不符合便提示用户按要求从头输入。
还有其他一些类似的输入异样，都是采纳类似的处置方式。
三．作为一个完整的程序，友好的界面是必需的。
因次程序中适本地采纳系统中的清屏命令，使得界面加倍简练，明了。
测试案例：
1
2
3
4
5
6
7
8
3
1
4
2
6
5
图5-2-1案例一图5-2-2案例二
测试进程、结果截图：
容错性测试：
在输入字母、符号、或不符合要求的数字时，提示错误并要求从头正确输入。
（图5-3-1-1~图5-3-1-7）
图5-3-1-1
图5-3-1-2
图5-3-1-3
图5-3-1-4
图5-3-1-5
图5-3-1-6
图5-3-1-7
无向图（案例一）测试：
将测试案例一的数据输入程序，从第一个极点开始遍历，结果如图5-3-2-1所示。
图5-3-2-1
输入y表示要继续遍历该图后，程序清屏，再次打印邻接表，并要求再次输入遍历起点，如图5-3-2-2所示。
图5-3-2-2
输入2后，打印从第二个极点遍历的顺序，输入n停止继续遍历该图，如图5-3-2-3所示。
图5-3-2-3
有向图（案例二）测试：
输入y表示继续输入其他图进行遍历后，程序清屏，并要求再次输入一个图，将测试案例2的数据输入程序后，从第一个极点遍历，如图5-3-3-1所示。
图5-3-3-1
输入y表示要继续遍历该图后，程序清屏，再次打印邻接表，并要求再次输入遍历起点。
输入4后，打印从第四个极点遍历的顺序，输入n停止继续遍历该图。
再次输入n停止继续输入其他图进行遍历，程序终止，如图5-3-3-2所示。
图5-3-3-2
6.总结
做这次课程设计，需要对图的广度遍历有足够的熟悉与把握，如此才能熟练的运用，因此这次课程设计也使我对所学的知识进行了巩固和新的明白得，而且编程需要对C语言知识的扎实底子，这就需要温习C语言程序设计的知识。
因此，通过这一个课程设计，使我对图的广度优先遍历算法有了深度的了解。
在编程进程中也碰到了一些问题，在同窗的帮忙下大体上都一一解决了。
可是由于能力有限，程序中还有一些尚未解决的问题。
例如，如何能完全解决输入异样。
这说明尔后还需要继续尽力。
参考文献
[1]谭浩强·C语言程序设计·（第2版）·清华大学出版社，出版年：
2020引用部份起止页码：
50-51，248-258。
[2]陈维兴，林小茶·C++面向对象程序设计教程·（第3版）·清华大学出版社，出版年：
2020引用部份起止页码：
260-273。
[3]严蔚敏，吴伟民·数据结构·（C语言版）·清华大学出版社，出版年：
2020引用部份起止页码：
156-170。
[4]梁旭，谷晓琳，黄明·C语言课程设计·（第2版）·电子工业出版社，出版年：
2020引用部份起止页码：
21-24。
升级会员 