数据结构实验图的基本操作复习过程.docx
- 文档编号:10389419
- 上传时间:2023-05-25
- 格式:DOCX
- 页数:27
- 大小:89.20KB
数据结构实验图的基本操作复习过程.docx
《数据结构实验图的基本操作复习过程.docx》由会员分享,可在线阅读,更多相关《数据结构实验图的基本操作复习过程.docx(27页珍藏版)》请在冰点文库上搜索。
数据结构实验图的基本操作复习过程
浙江大学城市学院实验报告
课程名称数据结构
实验项目名称实验十三/十四图的基本操作
学生姓名专业班级学号
实验成绩指导老师(签名)日期2014/06/09
一.实验目的和要求
1、掌握图的主要存储结构。
2、学会对几种常见的图的存储结构进行基本操作。
二.实验内容
1、图的邻接矩阵定义及实现:
建立头文件test13_AdjM.h,在该文件中定义图的邻接矩阵存储结构,并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。
同时建立一个验证操作实现的主函数文件test13.cpp(以下图为例),编译并调试程序,直到正确运行。
2、图的邻接表的定义及实现:
建立头文件test13_AdjL.h,在该文件中定义图的邻接表存储结构,并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。
同时在主函数文件test13.cpp中调用这些函数进行验证(以下图为例)。
3、填写实验报告,实验报告文件取名为report13.doc。
4、上传实验报告文件report13.doc到BB。
注:
下载p256_GraphMatrix.cpp(邻接矩阵)和p258_GraphAdjoin.cpp(邻接表)源程序,读懂程序完成空缺部分代码。
三.函数的功能说明及算法思路
(包括每个函数的功能说明,及一些重要函数的算法实现思路)
四.实验结果与分析
(包括运行结果截图、结果分析等)
5.心得体会
程序比较难写,但是可以通过之前的一些程序来找到一些规律
(记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。
)
【附录----源程序】
256:
//p-255图的存储结构以数组邻接矩阵表示,构造图的算法。
#include
#include
#include
#include
typedefcharVertexType;//顶点的名称为字符
constintMaxVertexNum=10;//图的最大顶点数
constintMaxEdgeNum=100;//边数的最大值
typedefintWeightType;//权值的类型
constWeightTypeMaxValue=32767;//权值的无穷大表示
typedefVertexTypeVexlist[MaxVertexNum];//顶点信息,定点名称
typedefWeightTypeAdjMatrix[MaxVertexNum][MaxVertexNum];//邻接矩阵
typedefenum{DG,DN,AG,AN}GraphKind;//有向图,有向网,无向图,无向网
typedefstruct{
Vexlistvexs;//顶点数据元素
AdjMatrixarcs;//二维数组作邻接矩阵
intvexnum,arcnum;//图的当前顶点数和弧数
GraphKindkind;//图的种类标志
}MGraph;
voidCreateGraph(MGraph&G,GraphKindkd)//采用数组邻接矩阵表示法,构造图G
{//构造有向网G
inti,j,k,q;
charv,w;
G.kind=kd;//图的种类
printf("输入要构造的图的顶点数和弧数:
\n");
scanf("%d,%d",&G.vexnum,&G.arcnum);
getchar();//过滤回车
printf("依次输入图的顶点名称ABCD...等等:
\n");
for(i=0;i getchar();//过滤回车 for(i=0;i for(j=0;j if(kd==DN||kd==AN) G.arcs[i][j]=MaxValue;//网,初始值为无穷大 else G.arcs[i][j]=0;//图,初始为0 if(kd==DN||kd==AN) printf("按照: 尾顶点名->头顶点名,权值输入数据: 如A->B,23\n"); else printf("按照: 尾顶点名->头顶点名输入数据: A->B\n"); for(k=0;k if(kd==DN||kd==AN) scanf("%c->%c,%d",&v,&w,&q);//输入弧的两个定点及该弧的权重 else scanf("%c->%c",&v,&w); getchar(); for(i=0;i if(G.vexs[i]==v)break;//查找出v在vexs[]中的位置i if(i==G.vexnum){cerr<<"vertexERROR! ";exit (1);} for(j=0;j if(G.vexs[j]==w)break;//查找出v在vexs[]中的位置j if(j==G.vexnum){cerr<<"vertexERROR! ";exit (1);} if(kd==AN)//无向网 { G.arcs[i][j]=q;//邻接矩阵对应位置置权值 G.arcs[j][i]=q;//无向图为对称矩阵 } elseif(kd==DN)//有向网 G.arcs[i][j]=q; elseif(kd==AG)//无向图 { G.arcs[i][j]=1;//对称矩阵 G.arcs[j][i]=1; } else//有向图 G.arcs[i][j]=1; //getchar(); } }//CreateGraph /*注意输入格式,按以下方式输入 构造有向网 输入要构造的网的顶点数和弧数: 4,5 依次输入网的顶点名称ABCD...等等: abcd 按照: 尾顶点名->头顶点名,权值输入数据: 如A->B,23 a->b,5 a->c,8 c->b,7 a->d,4 d->c,3 输出邻接矩阵 ∞|5|8|4| ∞|∞|∞|∞| ∞|7|∞|∞| ∞|∞|3|∞| Pressanykeytocontinue */ voidPrintMGraph(MGraph&G) { inti,j; switch(G.kind) { caseDG: for(i=0;i { for(j=0;j printf("%2.d|",G.arcs[i][j]); printf("\n"); } break; caseDN: for(i=0;i { for(j=0;j if(G.arcs[i][j]! =MaxValue)printf("%2.d|",G.arcs[i][j]); elseprintf("∞|"); } printf("\n"); } break; caseAG: for(i=0;i { for(j=0;j printf("%2.d|",G.arcs[i][j]); } printf("\n"); } break; caseAN: //********完成构造无向网**************** /*请模仿编写无向网*/ for(i=0;i { for(j=0;j if(G.arcs[i][j]! =MaxValue)printf("%2.d|",G.arcs[i][j]); elseprintf("∞|"); } printf("\n"); } break; } } //*****************完成函数********************************** voidcountdig(MGraphG)//请完成计算图的入度或初度 { if(G.kind==DG||G.kind==DN) { //计算有向图或网的各个顶点的入度与出度 intoutD,inD; inti,j; for(i=0;i outD=inD=0; for(j=0;j if(G.arcs[i][j]! =0&&G.arcs[i][j]! =MaxValue) outD++; } for(j=0;j if(G.arcs[j][i]! =0&&G.arcs[j][i]! =MaxValue) inD++; } printf("%c: 出度是%d,入度是%d\n",G.vexs[i],outD,inD); } } else { //计算无向图或网的度 inti,j; intDu; for(i=0;i Du=0; for(j=0;j if(G.arcs[i][j]! =0&&G.arcs[i][j]! =MaxValue) Du++; } printf("%c的度是%d\n",G.vexs,Du); } } } //************参照p265设计深度有限搜索*********** voidDFSMatrix(MGraphG,inti,intn,bool*visited) { cout< visited[i]=true; for(intj=0;j if(G.arcs[i][j]! =0&&G.arcs[i][j]! =MaxValue&&! visited[j]) DFSMatrix(G,j,n,visited); } //************参照p268设计广度有限搜索*********** voidBFSMatrix(MGraphG,inti,intn,bool*visited) { constintMaxSize=30; intq[MaxSize]={0}; intfront=0,rear=0; cout< visited[i]=true; q[++rear]=i; while(front! =rear){ front=(front+1)%MaxSize; intk=q[front]; for(intj=0;j if(G.arcs[i][j]! =0&&G.arcs[i][j]! =MaxValue&&! visited[j]){ cout< visited[j]=true; rear=(rear+1)%MaxSize; q[rear=j]; } } } } voidmain() { MGraphG; intk; printf("请选择图的种类: 0: 有向图,1: 有向网,2: 无向图,3: 无向网.请选择: "); scanf("%d",&k); switch(k){//DG,DN,AG,AN case0: printf("构造有向图\n"); CreateGraph(G,DG);//采用数组邻接矩阵表示法,构造有向图 break; case1: printf("构造有向网\n"); CreateGraph(G,DN);//采用数组邻接矩阵表示法,构造有向网AGG break; case2: printf("构造无向图\n"); CreateGraph(G,AG);//采用数组邻接矩阵表示法,构造无向图AGG break; case3: printf("构造无向网\n"); CreateGraph(G,AN);//采用数组邻接矩阵表示法,构造无向网AGG break; } PrintMGraph(G);//打印图的邻接矩阵 bool*visited=newbool[G.vexnum]; inti; cout<<"按图的邻接矩阵得到的深度优先遍历序列"< for(i=0;i DFSMatrix(G,0,G.vexnum,visited); cout<<"按图的邻接矩阵得到的广度优先遍历序列"< for(i=0;i BFSMatrix(G,0,G.vexnum,visited); cout<<"度: "< countdig(G); } 258: //p-258图的存储结构以邻接表表示,构造图的算法。 //已完成若干函数,对尚未完成的请补全 //请注意输入格式,按以下方式构建一个图 /* 请选择图的种类: 0: 有向图,1: 有向网,2: 无向图,3: 无向网.请选择: 0 构造有向图 输入要构造的有向图的顶点数和弧数: 4,5 依次输入图的顶点名称ABCD...等等: abcd 按照: 尾顶点名->头顶点名输入数据: 如A->B a->b a->c a->d c->b d->c */ #include #include #include #include typedefcharVertexType;//顶点的名称为字符 constintMaxVertexNum=10;//图的最大顶点数 constintMaxEdgeNum=100;//边数的最大值 typedefintWeightType;//权值的类型 constWeightTypeMaxValue=32767;//权值的无穷大表示 typedefVertexTypeVexlist[MaxVertexNum];//顶点信息,定点名称 //邻接矩阵 typedefenum{DG,DN,AG,AN}GraphKind;//有向图,有向网,无向图,无向网 structEdgeNode{//链表边结点,表示弧 intadjvex;//存放与头结点顶点有关的另一个顶点在邻接表(数组)中的下标。 EdgeNode*next;//指向链表下一个结点 WeightTypeinfo;//权重值,或为该弧相关信息 }; typedefstructVNode{//邻接表,表示顶点 VertexTypedata;//顶点数据,顶点名称 EdgeNode*firstarc;//指向边结点链表第一个结点 }VNode,AdjList[MaxVertexNum]; typedefstruct{ AdjListvertices; intvexnum,arcnum;//图的当前顶点数和弧数 GraphKindkind;//图的种类标志 }ALGraph; voidCreateGraph_DG(ALGraph&G){//构造有向图G EdgeNode*p; inti,j,k; charv,w; G.kind=DG;//图的种类 printf("输入要构造的有向图的顶点数和弧数: \n"); scanf("%d,%d",&G.vexnum,&G.arcnum); getchar();//过滤回车 printf("依次输入图的顶点名称ABCD...等等: \n"); for(i=0;i scanf("%c",&G.vertices[i].data);//构造顶点数据 G.vertices[i].firstarc=NULL;//初始化指向链表指针 } getchar();//过滤回车 printf("按照: 尾顶点名->头顶点名输入数据: 如A->B\n"); for(k=0;k scanf("%c->%c",&v,&w); getchar(); for(i=0;i if(G.vertices[i].data==v)break;//查找出v在vertices[]中的位置i if(i==G.vexnum){cerr<<"vertexERROR! ";exit (1);} for(j=0;j if(G.vertices[j].data==w)break;//查找出w在vertices[]中的位置i if(j==G.vexnum){cerr<<"vertexERROR! ";exit (1);} p=(EdgeNode*)malloc(sizeof(EdgeNode));//申请弧结点 p->adjvex=j;//置入弧尾顶点号 p->info=MaxValue;//图的权值默认为无穷大 p->next=G.vertices[i].firstarc;//插入链表 G.vertices[i].firstarc=p; } } //////////////////////////////////////////////////////////////////////////////////////////////// voidCreateGraph_DN(ALGraph&G)//构造有向网G { EdgeNode*p; inti,j,k; charv,w; WeightTypeq; G.kind=DN;//图的种类 printf("输入要构造的有向网的顶点数和弧数: \n"); scanf("%d,%d",&G.vexnum,&G.arcnum); getchar();//过滤回车 printf("依次输入图的顶点名称ABCD...等等: \n"); for(i=0;i scanf("%c",&G.vertices[i].data);//构造顶点数据 G.vertices[i].firstarc=NULL;//初始化指向链表指针 } getchar();//过滤回车 printf("按照: 尾顶点名->头顶点名,权值输入数据: 如A->B,8\n"); for(k=0;k scanf("%c->%c,%d",&v,&w,&q); getchar(); for(i=0;i if(G.vertices[i].data==v)break;//查找出v在vertices[]中的位置i if(i==G.vexnum){cerr<<"vertexERROR! ";exit (1);} for(j=0;j if(G.vertices[j].data==w)break;//查找出w在vertices[]中的位置i if(j==G.vexnum){cerr<<"vertexERROR! ";exit (1);} p=(EdgeNode*)malloc(sizeof(EdgeNode));//申请弧结点 p->adjvex=j;//置入弧尾顶点号 p->info=q;//图的权值默认为无穷大 p->next=G.vertices[i].firstarc;//插入链表 G.vertices[i].firstarc=p; } } voidCreateGraph_AG(ALGraph&G)//构造无向图G { EdgeNode*p; inti,j,k; charv,w; G.kind=AG;//图的种类 printf("输入要构造的有向图的顶点数和弧数: \n"); scanf("%d,%d",&G.vexnum,&G.arcnum); getchar();//过滤回车 printf("依次输入图的顶点名称ABCD...等等: \n"); for(i=0;i scanf("%c",&G.vertices[i].data);//构造顶点数据 G.vertices[i].firstarc=NULL;//初始化指向链表指针 } getchar();//过滤回车 printf("按照: 尾顶点名->头顶点名输入数据: 如A->B\n"); for(k=0;k scanf("%c->%c",&v,&w); getchar(); for(i=0;i if(G.vertices[i].data==v)break;//查找出v在vertices[]中的位置i if(i==G.vexnum){cerr<<"vertexERROR! ";exit (1);} for(j=0;j if(G.vertices[j].data==w)break;//查找出w在vertices[]中的位置i if(j==G.vexnum){cerr<<"vertexERROR! ";exit (1)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 基本 操作 复习 过程