图的遍历实现课程设计数据结构程序图.docx
《图的遍历实现课程设计数据结构程序图.docx》由会员分享，可在线阅读，更多相关《图的遍历实现课程设计数据结构程序图.docx（17页珍藏版）》请在冰点文库上搜索。
图的遍历实现课程设计数据结构程序图
数据结构课程设计
设计说明书
图的遍历的实现
学生姓名
英茜
学号
1１18064０33
班级
网络1101班
成 绩
指导教师
申静
数学与计算机科学学院
2０14年1月4日
课程设计任务书
2013—２０14学年第一学期
课程设计名称:
数据结构课程设计
课程设计题目:
图的遍历实现
完成期限：
自 2013年1２月23日至2014年１月4 日共2周
设计内容：
1.任务说明
（1） 采用邻接表存储结构创建一个图；
（２） 编程实现图的深度优先搜索（或广度优先搜索）遍历算法;
（3）输出遍历结果；
（4）给定具体数据调试程序。
２． 要求
１）问题分析和任务定义：
根据设计题目的要求,充分地分析和理解问题，明确问题要求做什么?
2）逻辑设计：
写出抽象数据类型的定义，各个主要模块的算法,并画出模块之间的调用关系图；
3）详细设计：
定义相应的存储结构并写出各函数的伪码算法。
4）程序编码：
把详细设计的结果进一步求精为程序设计语言程序。
5）程序调试与测试：
采用自底向上，分模块进行，即先调试低层函数。
6）结果分析:
程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。
算法的时间、空间复杂性分析;
7）编写课程设计报告。
3.参考资料
指导教师:
申静 教研室负责人：
余冬梅
课程设计评阅
评语：
指导教师签名：
年 月日
摘要
针对图问题中如何更好地实现图的遍历问题，以无向图为例,分别采用广度优先遍历和深度优先遍历的算法实现对各节点的遍历，以ＶＣ++为开发环境进行系统的设计和实现,其运行结果表明，系统能很好地完成遍历后节点的输出,实现了遍历的目的，系统界面友好,可操作性强。
关键词：
数据结构;存储结构；邻接矩阵
目 录
一 课题描述ﻩ１
二ﻩ设计目的与任务ﻩ２
2.1课程设计的目的2
２.2课程设计的任务2
3．1总体设计ﻩ３
3.2基本操作３
３.3详细设计ﻩ4
四运行调试结果ﻩ6
五结论与致谢９
六ﻩ附录ﻩ11
一 课题描述
数据结构是一门专业基础课，它对学习者的要求很明确:
学会分析、研究计算机加工的数据结构的特性,以便为应用设计所需的数据选择适当的逻辑结构、存储结构及其相应的算法,并初步掌握算法的时间分析和空间分析的技术。
其次,该课程的学习过程也是复杂程序设计的训练过程,要求学习者编写的程序结构或设计的程序结构体清楚、正确、易读，符合软件工程的规范。
图是一种较为复杂且重要的数据结构,其特殊性在于图形结构中结点之间的关系可以是任意的，图中任意两个数据元素之间都有可能相关。
就本课程设计而言应用图论的知识讨论如何在计算机上实现图的遍历的操作,主要解决图的遍历的几种方法的实现。
本设计采用目前最通用的程序设计语言之一—C语言作为数据结构和算法的描述语言。
二设计目的与任务
2.１课程设计的目的
进一步的了解图的遍历的问题，图的ＤFS,BFＳ的递归和非递归算法的实现,用无向图来实现图的遍历。
初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。
训练学生灵活应用所学数据结构的基本知识,熟练的完成问题分析、算法设计、编写程序,求解出指定的问题。
训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养严谨的科学态度和良好的工作作风。
提高综合运用所学的理论知识和方法独立分析和解决问题的能力。
2.２课程设计的任务
1）任务说明
用Ｃ/Ｃ++编写一个程序实现图的遍历的算法。
从键盘上输入一个图的基本信息（图用邻矩阵表示）。
图的DFS,BＦS的递归和非递归算法的实现;用有向图实现图的遍历；用无向图实现图的遍历;用邻接矩阵存储图；用邻接表存储图。
2）要求
１>首先输入图的结点数；
2>依次输入图的各条边（数据之间用空格隔开）；
3>输出的形式：
按用户选择的遍历方法给出遍历顺序,各字符间用->分隔;
4>程序所能达到的功能：
能够按要求输出所要的结果。
三设计方案和实施
３.1总体设计
采用邻接矩阵作为图的存储结构。
程序中主要用到以下抽象数据类型:
抽象数据类型的定义
typedｅfstruｃt{
cｈar ＊ｖexs； ﻩﻩﻩﻩﻩ//顶点向量
inｔaｒcs[ＭAX_VEX][MAX_VEX]; /／邻接矩阵
iｎtvexnuｍ,arcｎum； ﻩﻩ//图的当前顶点数和弧数
}Graph;
3.2基本操作
CrｅａｔeUDＮ（Grapｈ＆G）
操作结果:
用邻接矩阵创建带权无向网图。
DFＳ（GｒaｐhG,iｎt ｋ）
操作结果:
对已存在的图进行深度优先遍历。
BFS（ＧrａｐｈG）
操作结果：
对已存在的图进行广度优先遍历。
ｃhｏoｓe（ＧｒaｐhG）
操作结果:
对将要实现的操作步骤进行选择。
程序包含两个模块
主程序模块,其中主函数为
ｉｎtmaｉｎ｛
输入信息；
根据输入要求进行选择操作和输出;
输出结果；
}
选择操作模块—实现具体选择的对应操作及输出操作。
两模块之间关系如下图3.1所示
图3．1 模块关系图
3.3详细设计
程序流程图如图3.2所示
图3.2 程序流程图
函数设计程序设计中主要包括下列函数用邻接矩阵创建一个图:
voidCreaｔeUDＮ（Graｐｈ&G）{
用邻接矩阵创建一个带权无向网图;
输入顶点数和弧数;
输入各个顶点及各条弧;
}
递归方法实现图的遍历：
ｖoidDFS（GraphG,intk）
{
用递归的方法访问图中的结点;
对图进行深度优先遍历;
}
非递归方法实现图的遍历:
voiｄＢＦS（GraphG）
｛
用队列辅助访问图中的结点;
对图进行广度优先遍历;
}
选择输出需要的遍历方法:
vｏid choosｅ（GraphＧ）
{
给出程序运行的选项;
对相应的输入选项调用相应的函数以执行操作;
}
四运行调试结果
例:
遍历如下无向图（图４.１）（ａ,b,c,d,ｅ分别表示V1 V2 V３V４ V5五个顶点）
以图４．1为例
步骤一:
运行程序，按提示首先输入顶点数和弧数。
图４.2输入顶点数和弧数
步骤二：
输入顶点和弧
（1）输入顶点
图4.3输入各顶点
（2）输入弧
图4.３输入各条弧
步骤三：
选择便利方式以及选择后结果
选择1操作显示广度优先编历结果
图4．4 广度优先结果
选２操作显示深度优先遍历
图4.4深度优先遍历结果
五结论与致谢
在程序设计中我主要是解决的是给出一个图如何用多种方法完成图的遍历的问题,也包括如何创建一个图,深度优先遍历和广度优先遍历一个图，递归和非递归的方法实现图的遍历。
程序最终通过调试运行，初步实现了设计目标。
图是一种较为复杂且重要的数据结构,其特殊性在于图形结构中结点之间的关系可以是任意的,图中任意两个数据元素之间都有可能相关。
用邻接矩阵作为图的数据存储结构很好地解决了图的结构难点,借助于邻接矩阵容易判定任意两个顶点之间是否有边（或弧）相连，并容易求得各个顶点的度。
该程序通俗易懂且实用性强,并且该程序清单详细具体、全面、具有很强的可读性；系统整体上比较完美，可以从键盘获取输入元素，并且可以根据用户输入进行选择性地输出；整体输出画面效果整洁、大方。
这次课程设计也让我充分认识到《数据结构》这门课的重要性。
它给我们一个思想和大纲,让我们在编程时容易找到思路,不至于无章可循。
同时它也有广泛的实际应用。
最后，我还要特别感谢我们的辅导老师申静老师，在她的精心辅导和帮助下，我的设计才得以顺利完成。
对她为我们的设计所提出的宝贵意见表示忠心的感谢！
参考文献
［１]谭浩强.Ｃ程序设计[第三版].北京:
清华大学出版社.
[2]罗宇等.数据结构[M].北京邮电大学出版社.
[３]严藯敏.数据结构[C语言版]. 北京:
清华大学出版社.
[４］杨路明.Ｃ语言程序设计教程.北京邮电大学出版社．
[5]徐孝凯．数据结构课程实验. 清华大学出版社.
六ﻩ附录
源程序代码
/／程序功能：
采用递归和非递归算法,有向图和无向图,邻接矩阵和邻接表等多种结构存储实现图的遍历。
/／ 程序作者：
英茜
//最后修改日期：
20１4-1-3
＃ｉｎcｌude＂stdｉo.h＂
#inｃｌuｄe"stｄｌib.h＂
#dｅfineIＮFIＮIＴＹ3276７
#define MAX_VEＸ2０ ﻩﻩﻩ//最大顶点个数
#defｉne QUEUＥ＿ＳＩZＥ（ＭAX_ＶEＸ+1）ﻩﻩ//队列长度
ｂooｌ *ｖisｉｔed；ﻩﻩﻩ//访问标志数组
intz＝1; ﻩﻩﻩﻩﻩ／/图的邻接矩阵存储结构
ｔypeｄefstｒuct{
chａr*vexs; ﻩ//顶点向量
ｉntarｃs[MAX_ＶEX］［MAX_VEX];ﻩ//邻接矩阵
iｎtvexnum,aｒcnｕm;ﻩﻩ／/图的当前顶点数和弧数
}Gｒaph；
cｌasｓ Ｑuｅue{ ﻩﻩﻩﻩ//队列类
ｐublic:
void ＩnｉtQｕｅuｅ（）{
ｂase=（iｎｔ*）ｍaｌｌｏc（QUEUＥ＿ＳＩZE*sizeof（int））;
fｒont=ｒｅar=0；
}
vｏidEnＱｕeｕｅ（intｅ）｛
baｓe［rｅａｒ]=e；
reaｒ=（rear＋１）%ＱUEUＥ＿SIZE;
}
ｖoidDｅＱueｕe（inｔ ＆e）{
e=ｂａse[front];
froｎｔ=（fｒont＋1）%QＵEUE＿SＩＺE；
}
int＊baｓe；
inｔfrｏnt;
intreaｒ；
};
int Lｏcａte（GrａphG,ｃhar c）{ﻩﻩﻩﻩ//图Ｇ中查找元素c的位置
ｆor（inｔi=0;ｉif（G．veｘs[ｉ］==c）ｒetｕrｎi;
rｅturｎ-１；
}
voｉｄ CreateＵDN（Ｇｒaph&Ｇ）{ﻩﻩﻩ/／创建无向网
ｉnti,j，w,ｓ１,s２;
chaｒa,ｂ,c,ｔemp;
prｉnｔf（"输入顶点数和弧数（顶点数和弧数之间以空格隔开）:
"）;
ｓcａｎｆ（"％d%ｄ",＆G．vｅxｎum,&Ｇ.ａｒｃnum）;
temp=geｔchar（）; ﻩﻩﻩﻩ//接收回车
G.vexs=（ｃｈar＊）malｌoc（G.vｅxnum＊sizeof（chaｒ））;／／分配顶点数目
printf（＂输入%d个顶点.＼n"，Ｇ.vexnum）;
for（ｉ=0;ｉscaｎｆ（＂%c＂，&Ｇ.veｘs[i]）;
temp=getchar（）;ﻩﻩﻩ／／接收回车
}
ｆoｒ（ｉ=0;i＜G.vｅｘnum;ｉ++）ﻩﻩﻩ/／初始化邻接矩阵
fｏr（j=0;j<Ｇ.vｅxnｕｍ;j++）
Ｇ．arcs[i]［j]=ＩNＦINITY;
printf（"输入%ｄ条弧．\ｎ",Ｇ.ａｒcnｕｍ）;
ｆoｒ（i=０;iｐrintｆ（"输入弧%d:
",ｉ）;
ｓcanｆ（"%c%c%d%c＂,&a，&ｂ,&ｗ,&ｃ）； ﻩﻩ//输入一条边依附的顶点和权值
s1=Loｃate（G,a）;
s2=Ｌoｃａte（Ｇ,b）;
G.arcｓ[s1］[ｓ2］＝Ｇ.ａrcｓ［s２][s１]=w;
}
}
int FｉrｓtVex（ＧraphG,ｉnｔk）｛ﻩﻩﻩ//图G中顶点k的第一个邻接顶点
if（k＞=0 &＆ｋｆor（iｎｔ ｉ＝０；i<Ｇ.vexｎｕｍ；i+＋）
if（G．arcs［k][i]!
=INFINＩTＹ） ｒeｔurni；
}
reｔuｒn-1;
｝
/／图G中顶点i的第j个邻接顶点的下一个邻接顶点
ｉnｔＮextVeｘ（Gｒaph G,inｔi，int j）｛
if（i>=0＆&i=0 &&ｊfoｒ（inｔk=j＋1；kif（Ｇ.arcｓ[ｉ][k]!
=INFINＩTY）ｒetuｒｎ k；
}
reｔuｒn-１;
}
//深度优先遍历
voiｄDＦS（GｒapｈG,iｎtk）{
ｉnti;
if（ｋ==-1）｛ﻩﻩﻩﻩﻩ／/第一次执行DFS时,ｋ为-1
foｒ（i=0；iｉｆ（!
visiｔeｄ［i]） DＦS（G,i）;ﻩ//对尚未访问的顶点调用DFS
｝
eｌse{
viｓiｔeｄ[k］＝ｔruｅ；
if（z==1）
printf（"%c＂,G.vｅxs［ｋ]）;
ｅlseprintf（"->%c"，G．veｘs[k]）; ＋+z;／/访问第ｋ个顶点
if（（ｚ-１）％G.vexｎum==0）ｚ＝1;
ｆoｒ（i=FiｒｓtVｅx（G,k）;i>=０;i=NｅｘtVex（G,k,i））
if（！
visitｅd[ｉ］）DFS（Ｇ，i）；／/对ｋ的尚未访问的邻接顶点i递归调用DFS
}
｝
//广度优先遍历
ｖｏidBＦS（GrａphG）｛
iｎｔ ｋ;
Queｕe Ｑ;ﻩﻩﻩ /／辅助队列Q
Q．IniｔQueue（）;
fｏr（iｎti=0;iif（!
visiｔed［i]）{ﻩﻩﻩ//i尚未访问
vｉsiteｄ[i]＝true;
printf（＂％c",G.veｘs[i]）;
Ｑ.EnQｕeｕe（i）;ﻩﻩﻩﻩﻩﻩ／/i入列
ｗhile（Ｑ．ｆront！
=Q.rｅaｒ）{
Ｑ.ＤeQuｅue（k）;ﻩﻩﻩﻩﻩ//队头元素出列并置为k
ｆor（intｗ=ＦirstVex（Ｇ，ｋ）;ｗ>＝0;w=NｅｘtＶex（G,k，w））
if（!
vｉsitｅd[w]）{ﻩﻩﻩﻩ//ｗ为ｋ的尚未访问的邻接顶点
visitｅd［w]=ｔruｅ;
pｒintf（＂-＞%c ",G．ｖexｓ[ｗ]）;
Q.EｎQueuｅ（w）;
｝
}
}printf（＂\n请继续选择：
\n"）；
}
ｖoｉｄchｏoｓe（Grａｐh Ｇ）｛ﻩﻩﻩ/／对输入选项调用相应的函数执行操作
int ｉ，ｍ;
visｉted=（bｏol*）ｍalｌoc（G.vexｎum＊sizeof（ｂｏｏl））;
scanf（＂%d",＆m）；
sｗitch（ｍ）｛
case １:
prｉntf（"广度优先遍历:
＂）；
for（i=0；ivisited[i]＝fａｌse;
BFS（G）;chooｓe（G）;ｐrintf（"\n＂）;break;
case2:
prｉntf（"深度优先遍历:
"）;
ｆor（i=0；ｉｖｉsited[i]=false;
ＤＦＳ（Ｇ，-1）;
priｎｔf（＂\n 请继续选择:
＼n"）;cｈｏoｓe（G）;brｅak;
ｃaｓe3:
pｒiｎtｆ（"程序结束."）;ｂreak;
ｄefａult：
ｐrintf（"输入错误！
\n请在1-3中选择:
＼n"）;choose（G）;
}
}
//主函数
voｉd maiｎ（）{
ｉnti,m;
GraphG;
ＣｒeａｔｅUDN（Ｇ）;
prｉntｆ（＂有如下选项供选择:
\n"）;
printf（＂\n"）;
printf（"|＊| １:
广度优先遍历 ２：
深度优先遍历 3：
退出本程序！
|＊｜\ｎ＂）;
printｆ（"\n"）;
ｐrintf（"请选择（１－－3）:
\n＂）;
choose（G）;
}
升级会员 