庞贝贝1104040216课设报告7图的建立与遍历.docx
《庞贝贝1104040216课设报告7图的建立与遍历.docx》由会员分享，可在线阅读，更多相关《庞贝贝1104040216课设报告7图的建立与遍历.docx（13页珍藏版）》请在冰点文库上搜索。
庞贝贝1104040216课设报告7图的建立与遍历
试验报告七
课题名称：
图的建立与输出
班级：
信管112
姓名：
庞贝贝
学号：
1104040216
日期：
2013/7/17
一、需求分析
1、任务
建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。
二、概要设计
1、图的存储结构与结构体
图的存储结构有两种，一种是数组表示法，建立图的邻接矩阵，另一种是链式存储结构，建立图的邻接表。
常用的是邻接表存储，所以本算法采用邻接表存储图的结点。
图的邻接表存储表示如下：
#defineMAX_VERTEX_NUM20
typedefstructArcNode
{
intadjvex;//该弧所指向的顶点的位置
structArcNode*nextarc;//指向下一条弧的指针
InfoType*info;//该弧相关信息的指针
}ArcNode;
typedefstructVNode
{
VertexTypedata;//顶点信息
ArcNode*firstarc;//指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];
typedefstruct
{
AdjListvertices;
intvexnum,arcnum;//图的当前顶点数和弧数
intkind;//图的种类标志
}
2、构建无向图与有向图的算法思路
voidcreatAdj（AGraph&G）
{
输入图的边数和顶点数;
for（）
{输入顶点,赋值给图的每个顶点,并把顶点的firstarc置空;}
for（）
{输入边的起始结点,找到起始结点对应的存储地址,把地址赋值给边的adjvex域,如果是无向图还要多一步操作,把起始结点反过来作为另一条边进行操作;}
}
3、由图的邻接表建立图的邻接矩阵并输出
voidCreatMat（AGraphG）
{
申请二维数组a[20][20];
根据图的顶点数初始化矩阵,数组中a[0][0]-a[n-1][n-1]的每个值都赋值为0
由图的邻接表中边的信息修改已初始化的邻接矩阵中的值,存在改为1;
}
三、详细设计
#include
#include
1、图的结构体
#defineMAXV20
typedefcharElemType;
typedefintInfoType;
typedefstructArcNode//边的结点结构类型
{
intadjvex;//该边的终点位置
structArcNode*nextarc;//指向下条边的指针
InfoTypeinfo;//该边的相关信息
}ArcNode;
typedefstructVnode//邻接表头结点类型
{
ElemTypedata;//顶点信息
ArcNode*firstarc;//指向第一条边
}Vnode;
typedefVnodeAdjList[MAXV];//AdjList是邻接表类型
typedefstruct
{
AdjListadjlist;//邻接表
intn,e;//图的顶点数和边数
intkind;
}AGraph;//图的邻接表类型
2、构建无向图
voidCreatAdj1（AGraph&G）//构建无向图
{
cout<<"输入无向图的顶点数和边数";
cin>>G.n>>G.e;
G.kind=0;//kind为0，代表图为无向图
for（inti=0;i{
cout<<"输入图的第"<cin>>G.adjlist[i].data;
G.adjlist[i].firstarc=NULL;
}
for（i=1;i<=G.e;i++）
{
ArcNode*p;
cout<<"请输入第"<ElemTypeu,v;
cin>>u>>v;
intk=0;
while（G.adjlist[k].data!
=u）
k++;
intj=0;
while（G.adjlist[j].data!
=v）
j++;
p=newArcNode;
p->adjvex=j;
p->nextarc=G.adjlist[k].firstarc;
G.adjlist[k].firstarc=p;
p=newArcNode;
p->adjvex=k;
p->nextarc=G.adjlist[j].firstarc;
G.adjlist[j].firstarc=p;
}
}
3、构建有向图
voidCreatAdj2（AGraph&G）//构建有向图
{
cout<<"输入有向图的顶点数和边数";
cin>>G.n>>G.e;
G.kind=1;//kind为1，代表图为有向图
for（inti=0;i{
cout<<"输入图的第"<cin>>G.adjlist[i].data;
G.adjlist[i].firstarc=NULL;
}
for（i=1;i<=G.e;i++）
{
ArcNode*p;
cout<<"请输入第"<ElemTypeu,v;
cin>>u>>v;
intk=0;
while（G.adjlist[k].data!
=u）
k++;
intj=0;
while（G.adjlist[j].data!
=v）
j++;
p=newArcNode;
p->adjvex=j;
p->nextarc=G.adjlist[k].firstarc;
G.adjlist[k].firstarc=p;
}
}
4、由图的邻接表构建图的邻接矩阵
voidCreatMat（AGraphG）//构建图的邻接矩阵
{
inti,j,k;
ArcNode*p;
inta[20][20];
for（i=0;ifor（j=0;ja[i][j]=0;
for（i=0;iif（G.adjlist[i].firstarc!
=NULL）
{
p=G.adjlist[i].firstarc;
while（p!
=NULL）
{
k=p->adjvex;
a[i][k]=1;
p=p->nextarc;
}
}
cout<<"图的邻接矩阵为:
"<for（i=0;i{for（j=0;jcout<cout<}
}
5、主函数
voidmain（）
{
AGraphG;
inta,flag=1;
cout<<"***********************************欢迎使用本程序*******************************"<while（flag）
{
cout<<"请选择您要执行的命令:
1、构建无向图并输出图的邻接矩阵2、构建有向图并输出图的邻接矩阵3、退出"<cin>>a;
switch（a）
{
case1:
system（"cls"）;
{
CreatAdj1（G）;
CreatMat（G）;
};break;
case2:
system（"cls"）;
{CreatAdj2（G）;
CreatMat（G）;
};break;
case3:
system（"cls"）;{cout<<"谢谢使用;";flag=0;};break;
default:
{cout<<"您输入的选择序号有误，请重新输入:
"<}
}
}
函数调用关系图：
四、调试分析
1、本程序采用结构体的形式定义，为图设立结构体，又细分为结点信息结构体和边信息结构体，设置清晰，在图的存储时采用了常见的链表形式，便于边的删除与添加。
2、建图时遇到图的引用与直接读取问题，&符号只需要在函数申明和定义时使用，在调用时可以不加。
3、本程序的划分也十分的合理，根据题目的要求，划分为三块：
建有向图，建无向图，输出邻接矩阵。
在函数调用时分两块：
建有向图并输出图的邻接矩阵，建无向图并输出图的邻接矩阵。
4、算法时空分析，本算法基本上采用for循环语句和while循环语句以及if判读语句，实现简便，复杂度为O（n*m）。
五、用户手册
1、本程序的运行环境为windows7操作系统。
2、进入程序后显示界面。
选择要执行的命令，并按回车键，按照提示输入图的相关信息。
每次输入以回车键结束。
六、测试数据及测试结果
1、测试数据：
无向图：
有向图
2、测试结果
1）构建无向图，并输出其邻接矩阵
2）构建有向图并输出
3）退出
七、附录：
源文件名清单
iostream.h
stdlib.h
升级会员 