费富增E01214108图的邻接矩阵存储结构建立.docx
《费富增E01214108图的邻接矩阵存储结构建立.docx》由会员分享，可在线阅读，更多相关《费富增E01214108图的邻接矩阵存储结构建立.docx（13页珍藏版）》请在冰点文库上搜索。
费富增E01214108图的邻接矩阵存储结构建立
课程名称:
《数据结构》课程设计
课程设计题目:
7.1图的邻接矩阵存储结构建立
姓名:
费富增
院系:
计算机学院
专业:
计算机科学与技术
年级:
2012
学号:
E01214108
指导教师:
王爱平
2014年10月10日
目录
1课程的目的………………………………………………………………
2需求分析………………………………………………………………………
3课程设计报告内容……………………………………………………………
3.1概要设计……………………………………………………………………
3.2详细设计……………………………………………………………………
3.3调试分析……………………………………………………………………
3.4用户手册……………………………………………………………………
3.5测试结果……………………………………………………………………
3.6程序清单……………………………………………………………………
4小结…………………………………………………………………………
5参考文献………………………………………………………………
1.课程设计的目的
（1）熟练使用C语言编写程序，解决实际问题;
（2）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力;
（3）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;
（4）提高综合运用所学的理论知识和方法独立分析和解决问题的能力;
2.需求分析
建立图的邻接矩阵存储结构（以无向图为例），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后给出图的DFS,BFS次序。
3图的邻接矩阵存储结构建立的设计
3.1概要设计
1.函数
1.函数
①主函数：
main（）
②创建无向图：
CreateGraph（）
③深度优先遍历图：
DFS（）
④广度优先遍历图：
BFS（）
3.2详细设计
1.用邻接矩阵作为图的存储结构，程序中主要用到的抽象数据类型：
typedefstruct
{
charvexs[MAX];//顶点向量
intarcs[MAX][MAX];//邻接矩阵
intvexnum,arcnum;//图的当前顶点数和弧数
}Graph;
2.程序流程图：
源程序：
#include
#include
#defineMAX20
intvisited[MAX];
typedefstruct
{
charvexs[MAX];
intarcs[MAX][MAX];//邻接矩阵
intvexnum,arcnum;//图的当前顶点数和边数
}Graph;
typedefstructQnode
{
intdata;
structQnode*next;
}Qnode,*Queueptr;
typedefstruct
{
Queueptrfront;
Queueptrrear;
}Linkqueue;
voidInitQueue（Linkqueue&Q）
{
Q.front=Q.rear=（Queueptr）malloc（sizeof（Qnode））;
if（Q.front）
Q.front->next=NULL;
}
voidEnQueue（Linkqueue&Q,inte）
{
Queueptrp;
p=（Queueptr）malloc（sizeof（Qnode））;
if（p）
{
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
}
}
intDeQueue（Linkqueue&Q）
{
inte;
Queueptrp;
if（Q.rear!
=Q.front）
{
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if（Q.rear==p）
Q.rear=Q.front;
free（p）;
}
if（Q.front==p）
Q.rear=Q.front;
returne;
}
intLocatevex（GraphG,charv）//返回元素v的位置
{
inti;
for（i=0;iif（G.vexs[i]==v）
returni;
return-1;
}
voidCreateGraph（Graph&G）//创建无向图的邻接矩阵
{
inti,j,w,m,n;
chara,b,c;
printf（"请输入图G的顶点数和弧数:
"）;
scanf（"%d%d",&G.vexnum,&G.arcnum）;
getchar（）;
for（i=0;ivisited[i]=0;
for（i=0;i{printf（"请输入第%d个顶点信息:
",i+1）;
scanf（"%c",&G.vexs[i]）;
getchar（）;
}
for（i=0;ifor（j=0;jG.arcs[i][j]=0;
for（i=0;i{printf（"请输入第%d条弧依附的两个顶点及权值:
",i+1）;
scanf（"%c%c%d%c",&a,&b,&w,&c）;
m=Locatevex（G,a）;
n=Locatevex（G,b）;
G.arcs[m][n]=w;
G.arcs[n][m]=w;
}
}
voidPrintMatrix（GraphG）//输出邻接矩阵
{
inti,j;
printf（"\n由图G生成的邻接矩阵如下:
\n"）;
for（i=0;i{
for（j=0;jprintf（"%-2d",G.arcs[i][j]）;
printf（"\n"）;
}}
intFirstAdiVex（GraphG,intv）//图G中顶点v的第一个邻接顶点
{
inti;
if（v>=0&&v{
for（i=0;iif（G.arcs[v][i]!
=0）
returni;
}
return-1;
}
intNextAdVex（GraphG,inti,intj）//图G中顶点i的第j个邻接顶点的下一个邻接顶点
{
intk;
if（i>=0&&i=0&&j{
for（k=j+1;kif（G.arcs[i][k]!
=0）
returnk;
}
return-1;
}
voidDFS（GraphG,intv）
{
intu;
printf（"%2c",G.vexs[v]）;
visited[v]=1;
u=FirstAdiVex（G,v）;
while（u>=0）
{if（!
visited[u]）
DFS（G,u）;
u=NextAdVex（G,v,u）;
}}
voidBFS（GraphG）\
{
inti,w,k;
LinkqueueQ;
InitQueue（Q）;
for（i=0;ivisited[i]=0;
for（i=0;iif（!
visited[i]）
{
visited[i]=1;
printf（"%2c",G.vexs[i]）;
EnQueue（Q,i）;
while（Q.front!
=Q.rear）
{
k=DeQueue（Q）;
for（w=FirstAdiVex（G,k）;w>=0;w=NextAdVex（G,k,w））
if（!
visited[w]）
{visited[w]=1;
printf（"%2c",G.vexs[w]）;
EnQueue（Q,w）;
}}}}
intmain（）
{intm;
GraphG;
while
（1）
{printf（"----图的邻接矩阵存储结构建立----\n"）;
printf（"1.创建无向图\n"）;
printf（"2.图的深度优先遍历\n"）;
printf（"3.图的广度优先遍历\n"）;
printf（"请选择:
"）;
scanf（"%d",&m）;
if（m==1）
{
CreateGraph（G）;
PrintMatrix（G）;
}
elseif（m==2）
{
printf（"图G的深度递归优先遍历序列为:
\n"）;
DFS（G,0）;
printf（"\n"）;
}
elseif（m==3）
{
printf（"图G的广度非递归优先遍历序列为:
\n"）;
BFS（G）;
printf（"\n"）;
}
else
printf（"重新输入!
\n"）;
}
return0;
}3.3调试分析
编写这个程序完全可以变成三个小程序，分别为1.创建无向图2.图的深度优先遍历3.图的广度优先遍历。
程序的设计严格遵循结构化的程序设计思想，由简单到复杂，注意规范。
3.4用户手册（略）
3.5测试结果（略）
4总结
在对类似的几类不同的矩阵结构进行操作时，可以相互比较，在对比中编写可以减少不少时间，因为其相互都是相通的。
在编写程序是还要特别注意细节，最后调试发现有不少细节错误导致程序不通过，所以在调试时要注意细节，细节决定成败。
通过设计调试集合运算器的设计这个实验，懂得设计一个程序要首先有一个清晰的思路，构建清晰的思路后再完善各个小部分。
5、程序清单:
（见附录）
6、参考文献
1严蔚敏，吴伟民编著.数据结构（C语言版）--北京:
清华大学出版社，2007.2严蔚敏，吴伟民米宁编著.数据结构题集（C语言版）--北京:
清华大学出版社，2007.3网上搜索相关程序作为参考
7、程序运行结果
运行截图
升级会员 