数据结构与算法图.docx
- 文档编号:14629487
- 上传时间:2023-06-25
- 格式:DOCX
- 页数:15
- 大小:51.92KB
数据结构与算法图.docx
《数据结构与算法图.docx》由会员分享,可在线阅读,更多相关《数据结构与算法图.docx(15页珍藏版)》请在冰点文库上搜索。
数据结构与算法图
实验报告
课程名称:
数据结构与算法
实验名称:
图
一、实验目的
1.掌握图的两种存储方法(数组表示法和邻接表表示法)
2.两种存储方式的相互转化
3.掌握邻接表表示法的基础上实现图的遍历
4.掌握图生成最小生成树的方法
5.掌握图的最短路径算法
二、实验内容
1、在文本文件中按照一定的格式存储图的数据
2、从文件中读入该信息,并且构造两种存储方式
3、输出两种存储方式,并进行转化,看是否得到了正确的结果
4、在邻接表的基础上实现图的遍历操作
5、编写图的最小生成树算法,并进行验证
6、编写最短路径算法,并对输入的图进行验证
三、实例
文本文件可如下:
第一行输入两个整数,分别表示顶点和边的数目
第二行开始每行输入一个顶点信息,图的顶点可自行编号
顶点信息输入完后,接着每行输入一个边的信息
33
1福州
2泉州
3莆田
12150
2380
1370
三、实验环境
硬件:
WindowsXP计算机、鼠标、键盘、显示器
开发环境:
MicrosoftVisualC++6.0
四、实验步骤
1、点击开始菜单中的程序-MicrosoftVisualC++6.0
点击菜单栏中的文件—新建—文件—C++SourceFile,在文件名(N)中写入7.cpp,再点击确定.
2、编写程序如下:
#include
#include
#include
#include
#defineINFINLY999//两点不可到达
#defineTRUE1
#defineFALSE0
#defineMAX999
#defineInfine10000
#defineMAX_VEX_NUM50
typedefenum{DG,AG,WDG,WAG}GraphKind;
typedefcharVertexType[20];/*定义VertexType为char数组类型*/
typedefintArcValType;
typedefcharArcInfoType[5];
typedefcharInfoType[20];
intvisited[MAX_VEX_NUM];
/*--------------------------------------邻接矩阵的存储--------------------------------------*/
typedefstructAdjType
{
ArcValTypeArcVal;//顶点关系类型,对无权图,用0和1,用来表示相邻与否
//对有权图,则为权值类型
ArcInfoTypeArcInfo;//弧相关的信息
}AdjType;
typedefstruct
{
intadjvex;/*顶点编号*/
VertexTypedata;/*顶点的信息*/
}VexType;/*顶点类型*/
typedefstruct
{
GraphKindkind;//图的种类
VexTypevexs[MAX_VEX_NUM];//顶点向量
boolmark[MAX_VEX_NUM];
AdjTypeadj[MAX_VEX_NUM][MAX_VEX_NUM];//邻接矩阵
intvexnum,arcnum;//顶点数
}AdjGraph;
/*--------------------------------------邻接表的存储-----------------------------------------*/
typedefstructLinkNode//边结点
{
intadjvex;
InfoTypeInfo;
structLinkNode*next;
}LinkNode;
typedefstructVexNode//表头结点
{
intnum;
VexTypevexdata;
LinkNode*first;
}VexNode;
typedefstruct
{
GraphKindkind;
intvexnum,arcnum;
VexNodeadjlist[MAX_VEX_NUM];
}ALGraph;
/*-------------------------------------图中顶点定位函数-------------------------------------*/
intLocateVex(AdjGraph*G,intvp)
{
inti;
for(i=0;i
if(G->vexs[i].adjvex==vp)
returni;
return-1;//图中无此顶点
}
/*-------------------------------------邻接矩阵的输出---------------------------------------*/
voidDispMatix(AdjGraph*G)//
{
inti,j;
printf("\n图的邻接矩阵:
\n\n");
for(i=0;i
{
for(j=0;j
printf("%5d",G->adj[i][j].ArcVal);
printf("\n");
}
}
/*------------------------------------邻接表的输出----------------------------------------*/
voidPUT(ALGraph*G2)
{
inti;
LinkNode*s;
s=(LinkNode*)malloc(sizeof(LinkNode));
for(i=0;i
{
printf("%3d:
-->",G2->adjlist[i].num);
if(G2->adjlist[i].first!
=NULL)
{
s=G2->adjlist[i].first;
while(s!
=NULL)
{
printf("%d-->",s->adjvex);
s=s->next;
}
}
printf("^\n");
}
}
/*----------------------------------邻接表基础上的深度优先遍历图-------------------------------*/
voidDFS(ALGraph*G2,inti)
{
LinkNode*p;
p=(LinkNode*)malloc(sizeof(LinkNode));
if(!
visited[i])
{
printf("%5d",G2->adjlist[i-1].num);
visited[i]=TRUE;
}
p=G2->adjlist[i-1].first;
while(p!
=NULL)
{
if(!
visited[p->adjvex])
DFS(G2,p->adjvex);
p=p->next;
}
}
/*---------------------------------邻接矩阵基础上的广度优先遍历图------------------------------*/
intBFS(AdjGraph*G,intu)
{
intj,i,k1=0,k2=0;
for(j=0;j
G->mark[j]=0;
intv=LocateVex(G,u);
intS[MAX_VEX_NUM],h;
printf("%5d",u);
G->mark[v-1]=1;
for(i=1;i<=G->vexnum;i++)
{
for(j=1;j<=G->vexnum-1;j++)
{
if(G->adj[v][j].ArcVal
{
printf("%5d",G->vexs[j]);
G->mark[j-1]=1;
S[k2++]=G->mark[j];
}
}
h=S[k1++];
v=LocateVex(G,h);
}
returnTRUE;
}
/*----------------------------------普里姆算法构造最小生成树-----------------------------------*/
/*每一步扫描数组lowcost,在V-U中找出离U最近的顶点,令其为k,并打印边(k,closest[k])*/
/*然后修改lowcost和closest,标记k已经假如U。
c表示图邻接矩阵,弱不存在边(i,j),则c[i][j]的值为一个大于任何权而小于无限打的阐述,这里用MAXCOST表示*/
voidprim(intc[MAX_VEX_NUM][MAX_VEX_NUM],intn)/*一直图的顶点为{1,2,...,n},c[i][j]为(i,j)的权,打印最小生成树的每条边*/
{
inti,j,k,min,lowcost[MAX_VEX_NUM],closest[MAX_VEX_NUM];
for(i=2;i<=n;i++)/*从顶点1开始*/
{
lowcost[i]=c[1][i];
closest[i]=1;
}
closest[1]=0;
for(i=2;i<=n;i++)/*从U之外求离U中某一顶点最近的顶点*/
{
min=Infine;
j=1;
k=i;
while(j<=n)
{
if(lowcost[j] =0) { min=lowcost[j]; k=j; } j++; } printf("(%d,%d)",closest[k],k);/*打印边*/ closest[k]=0;/*k假如到U中*/ for(j=2;j<=n;j++) if(closest[j]! =0&&c[k][j] { lowcost[j]=c[k][j]; closest[j]=k; } } } /*----------------------------------------狄克斯特拉算法-------------------------------------*/ typedefcharPath[20]; Pathpath[20]; voidDijstra(AdjGraph*G,intv,intdis[]) { intvset[MAX_VEX_NUM]; intMinDia,i,j,w; for(i=0;i { vset[i]=1; dis[i]=G->adj[v][i].ArcVal; strcpy(path[i],G->vexs[v].data); } vset[v]=0; for(i=1;i { MinDia=MAX; for(j=1;j if(vset[j]&&dis[j] { w=j; MinDia=dis[j]; } printf("顶点%d到%d的最短路径值为: %d\n",G->vexs[v].adjvex,G->vexs[w].adjvex,MinDia); vset[w]=0; for(j=1;j { if(vset[j]&&dis[w]+G->adj[w][j].ArcVal { dis[j]=dis[w]+G->adj[w][j].ArcVal; strcat(path[j],G->vexs[w].data); } } strcat(path[w],G->vexs[w].data); } printf("\n"); for(j=0;j { printf("经过的点为: %s\n",path[j]); } } /*----------------------------------主函数----------------------------------------------*/ voidmain() { inti,j,k; intc[MAX_VEX_NUM][MAX_VEX_NUM]; intdist[MAX_VEX_NUM]; AdjGraph*G; ALGraph*G2; G=(AdjGraph*)malloc(sizeof(AdjGraph));//申请空间 G2=(ALGraph*)malloc(sizeof(ALGraph));//申请空间 FILE*fp; fp=fopen("H: \\Graph.txt","r"); if(fp==NULL) { printf("filecannotopen! "); exit(0); } else//while(! feof(fp))//从磁盘文件上读入 { printf("从文件中读取的数据如下: \n"); fscanf(fp,"%d%d",&G->vexnum,&G->arcnum); printf("点数为: %d\n",G->vexnum); printf("边数为: %d\n",G->arcnum); for(i=0;i { fscanf(fp,"%d%s",&G->vexs[i].adjvex,&G->vexs[i].data); printf("%d%s\n",G->vexs[i].adjvex,G->vexs[i].data); for(j=0;j { if(j==i) G->adj[i][j].ArcVal=0; else G->adj[i][j].ArcVal=INFINLY; } } printf("各点间的关系为: \n"); for(j=0;j { intv1,v2,weight; fscanf(fp,"%d%d%d",&v1,&v2,&weight); i=LocateVex(G,v1); k=LocateVex(G,v2); G->adj[i][k].ArcVal=weight; G->adj[k][i].ArcVal=weight; printf("%d%d%d\n",i+1,k+1,G->adj[i][k].ArcVal); } G2->vexnum=G->vexnum; G2->arcnum=G->arcnum; for(i=0;i { G2->adjlist[i].num=G->vexs[i].adjvex; G2->adjlist[i].first=NULL; for(j=0;j { if((G->adj[i][j].ArcVal! =0)&&(G->adj[i][j].ArcVal! =INFINLY)) { LinkNode*p; p=(LinkNode*)malloc(sizeof(LinkNode)); p->adjvex=G->vexs[j].adjvex; p->next=G2->adjlist[i].first; G2->adjlist[i].first=p; } } } } fclose(fp); DispMatix(G); printf("\n转换成邻接表是: \n\n"); PUT(G2); printf("\n"); printf("在邻接表的基础上的深度遍历是: \n"); DFS(G2,1); printf("\n\n"); printf("在邻接矩阵的基础上的广度遍历是: \n"); BFS(G,1); printf("\n\n"); printf("最小生成树的每条边为: \n"); prim(c,G->vexnum); printf("\n\n"); printf("狄克斯特拉算法--最短路径: \n\n"); Dijstra(G,0,dist); printf("\n"); } 五、实验结果 实验结果如下图所示: 六、实验总结 1最主要的是要注意空间的申请 2第二点就是文件的输入,要注意格式,及相对应的变量。 3在做邻接矩阵的时候,要注意不可到达的两个点之间的值。 4在做邻接表的时候,要注意最后的指针要指向空 5在求最小生成树的时候,要注意修改lowcost和closest的值 6在做最短路径的时候,要注意strcat(path[j],G->vexs[w].data);这个函数的起点和终点。 7这次实验最大的不足,我个人认为是主函数太长了,本来可以分成几个文件,但是由于不熟悉,所以就先将就着吧。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 算法
![提示](https://static.bingdoc.com/images/bang_tan.gif)