收藏 分销(赏)

数据结构实验图的基本操作.doc

上传人:a199****6536 文档编号:3895603 上传时间:2024-07-23 格式:DOC 页数:19 大小:120KB
下载 相关 举报
数据结构实验图的基本操作.doc_第1页
第1页 / 共19页
数据结构实验图的基本操作.doc_第2页
第2页 / 共19页
点击查看更多>>
资源描述
浙江大学城市学院实验报告 课程名称 数据结构 实验项目名称 实验十三/十四 图的基本操作 学生姓名 专业班级 学号 实验成绩 指导老师(签名 ) 日期 2014/06/09 一. 实验目的和要求 1、掌握图的主要存储结构。 2、学会对几种常见的图的存储结构进行基本操作。 二. 实验内容 1、 图的邻接矩阵定义及实现: 建立头文件test13_AdjM.h,在该文件中定义图的邻接矩阵存储结构,并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时建立一个验证操作实现的主函数文件test13.cpp(以下图为例),编译并调试程序,直到正确运行。 0 1 2 4 6 5 3 2、图的邻接表的定义及实现: 建立头文件test13_AdjL.h,在该文件中定义图的邻接表存储结构,并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时在主函数文件test13.cpp中调用这些函数进行验证(以下图为例)。 00 11 22 33 4 3、填写实验报告,实验报告文件取名为report13.doc。 4、上传实验报告文件report13.doc到BB。 注: 下载p256_GraphMatrix.cpp(邻接矩阵)和p258_GraphAdjoin.cpp(邻接表)源程序,读懂程序完成空缺部分代码。 三. 函数的功能说明及算法思路 (包括每个函数的功能说明,及一些重要函数的算法实现思路) 四. 实验结果与分析 (包括运行结果截图、结果分析等) 五. 心得体会 程序比较难写,但是可以通过之前的一些程序来找到一些规律 (记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。) 【附录----源程序】 256: //p-255 图的存储结构以 数组邻接矩阵 表示, 构造图的算法。 #include <iostream.h> #include <stdio.h> #include <stdlib.h> #include <string.h> typedef char VertexType; //顶点的名称为字符 const int MaxVertexNum=10; //图的最大顶点数 const int MaxEdgeNum=100; //边数的最大值 typedef int WeightType; //权值的类型 const WeightType MaxValue=32767; //权值的无穷大表示 typedef VertexType Vexlist[MaxVertexNum]; //顶点信息,定点名称 typedef WeightType AdjMatrix[MaxVertexNum][MaxVertexNum]; //邻接矩阵 typedef enum{DG,DN,AG,AN} GraphKind; //有向图,有向网,无向图,无向网 typedef struct{ Vexlist vexs; // 顶点数据元素 AdjMatrix arcs; // 二维数组作邻接矩阵 int vexnum, arcnum; // 图的当前顶点数和弧数 GraphKind kind; // 图的种类标志 } MGraph; void CreateGraph(MGraph &G, GraphKind kd)// 采用数组邻接矩阵表示法,构造图G {//构造有向网G int i,j,k,q; char v, w; G.kind=kd; //图的种类 printf("输入要构造的图的顶点数和弧数:\n"); scanf("%d,%d",&G.vexnum,&G.arcnum); getchar();//过滤回车 printf("依次输入图的顶点名称ABCD...等等:\n"); for (i=0; i<G.vexnum; i++) scanf("%c",&G.vexs[i]);//构造顶点数据 getchar();//过滤回车 for (i=0; i<G.vexnum; i++) //邻接矩阵初始化 for (j=0; j<G.vexnum; 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<G.arcnum; k++){ //构造邻接矩阵 if(kd==DN||kd==AN) scanf("%c->%c,%d",&v,&w,&q); //输入弧的两个定点及该弧的权重 else scanf("%c->%c",&v,&w); getchar(); for(i=0;i<G.vexnum; i++) if(G.vexs[i]==v) break;//查找出v在vexs[]中的位置i if(i==G.vexnum) {cerr<<"vertex ERROR!";exit(1);} for(j=0;j<G.vexnum; j++) if(G.vexs[j]==w) break;//查找出v在vexs[]中的位置j if(j==G.vexnum) {cerr<<"vertex ERROR!";exit(1);} if(kd==AN)//无向网 { G.arcs[i][j]=q; //邻接矩阵对应位置置权值 G.arcs[j][i]=q; //无向图为对称矩阵 } else if(kd==DN)//有向网 G.arcs[i][j]=q; else if(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 | ∞ | Press any key to continue */ void PrintMGraph(MGraph &G) { int i,j; switch(G.kind) { case DG: for (i=0; i<G.vexnum; i++) { for (j=0; j<G.vexnum; j++) printf(" %2.d | ",G.arcs[i][j]); printf("\n"); } break; case DN: for (i=0; i<G.vexnum; i++) { for (j=0; j<G.vexnum; j++){ if(G.arcs[i][j]!=MaxValue) printf(" %2.d | ",G.arcs[i][j]); else printf(" ∞ | "); } printf("\n"); } break; case AG: for (i=0; i<G.vexnum; i++) { for (j=0; j<G.vexnum; j++){ printf(" %2.d | ",G.arcs[i][j]); } printf("\n"); } break; case AN: //********完成构造无向网**************** /* 请模仿编写无向网*/ for (i=0; i<G.vexnum; i++) { for (j=0; j<G.vexnum; j++){ if(G.arcs[i][j]!=MaxValue) printf(" %2.d | ",G.arcs[i][j]); else printf(" ∞ | "); } printf("\n"); } break; } } //*****************完成函数********************************** void countdig(MGraph G) //请完成计算图的入度或初度 { if(G.kind==DG||G.kind==DN) { //计算有向图或网的各个顶点的入度与出度 int outD,inD; int i,j; for(i=0;i<G.vexnum;i++){ outD=inD=0; for(j=0;j<G.vexnum;j++){ if(G.arcs[i][j]!=0&&G.arcs[i][j]!=MaxValue) outD++; } for(j=0;j<G.vexnum;j++){ if(G.arcs[j][i]!=0&&G.arcs[j][i]!=MaxValue) inD++; } printf("%c:出度是%d,入度是%d\n",G.vexs[i],outD,inD); } } else { // 计算无向图或网的度 int i,j; int Du; for(i=0;i<G.vexnum;i++){ Du=0; for(j=0;j<G.vexnum;j++){ if(G.arcs[i][j]!=0&&G.arcs[i][j]!=MaxValue) Du++; } printf("%c的度是%d\n",G.vexs,Du); } } } //************参照p265设计深度有限搜索*********** void DFSMatrix(MGraph G,int i,int n,bool*visited) { cout<<G.vexs[i]<<' '; visited[i]=true; for(int j=0;j<n;j++) if(G.arcs[i][j]!=0&&G.arcs[i][j]!=MaxValue&& !visited[j]) DFSMatrix(G,j,n,visited); } //************参照p268设计广度有限搜索*********** void BFSMatrix(MGraph G,int i, int n , bool*visited) { const int MaxSize=30; int q[MaxSize]={0}; int front=0,rear=0; cout<<G.vexs[i]<<' '; visited[i]=true; q[++rear]=i; while(front!=rear){ front=(front+1)%MaxSize; int k=q[front]; for(int j=0;j<n;j++){ if(G.arcs[i][j]!=0&&G.arcs[i][j]!=MaxValue&& !visited[j]){ cout<<G.vexs[j]<<' '; visited[j]=true; rear=(rear+1)%MaxSize; q[rear=j]; } } } } void main() { MGraph G; int k; printf("请选择图的种类:0:有向图,1:有向网,2:无向图,3:无向网. 请选择:"); scanf("%d",&k); switch(k) { //DG,DN,AG,AN case 0: printf("构造有向图\n"); CreateGraph(G,DG); // 采用数组邻接矩阵表示法,构造有向图 break; case 1: printf("构造有向网\n"); CreateGraph(G,DN); // 采用数组邻接矩阵表示法,构造有向网AGG break; case 2: printf("构造无向图\n"); CreateGraph(G,AG); // 采用数组邻接矩阵表示法,构造无向图AGG break; case 3: printf("构造无向网\n"); CreateGraph(G,AN); // 采用数组邻接矩阵表示法,构造无向网AGG break; } PrintMGraph(G); //打印图的邻接矩阵 bool*visited=new bool[G.vexnum]; int i; cout<<"按图的邻接矩阵得到的深度优先遍历序列"<<endl; for(i=0;i<G.vexnum;i++) visited[i]=false; DFSMatrix(G,0,G.vexnum,visited); cout<<"按图的邻接矩阵得到的广度优先遍历序列"<<endl; for(i=0;i<G.vexnum;i++) visited[i]=false; BFSMatrix(G,0,G.vexnum,visited); cout<<"度:"<<endl; 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 <iostream.h> #include <stdio.h> #include <stdlib.h> #include <string.h> typedef char VertexType; //顶点的名称为字符 const int MaxVertexNum =10; //图的最大顶点数 const int MaxEdgeNum =100; //边数的最大值 typedef int WeightType; //权值的类型 const WeightType MaxValue =32767; //权值的无穷大表示 typedef VertexType Vexlist [MaxVertexNum]; //顶点信息,定点名称 //邻接矩阵 typedef enum {DG,DN,AG,AN} GraphKind; //有向图,有向网,无向图,无向网 struct EdgeNode{ //链表边结点,表示弧 int adjvex; //存放与头结点顶点有关的另一个顶点在邻接表(数组)中的下标。 EdgeNode *next; //指向链表下一个结点 WeightType info; // 权重值,或为该弧相关信息 }; typedef struct VNode{ //邻接表,表示顶点 VertexType data; // 顶点数据,顶点名称 EdgeNode *firstarc; // 指向边结点链表第一个结点 } VNode, AdjList[MaxVertexNum]; typedef struct{ AdjList vertices; int vexnum, arcnum; // 图的当前顶点数和弧数 GraphKind kind; // 图的种类标志 } ALGraph; void CreateGraph_DG(ALGraph &G){//构造有向图G EdgeNode *p; int i,j,k; char v,w; G.kind=DG; //图的种类 printf("输入要构造的有向图的顶点数和弧数:\n"); scanf("%d,%d",&G.vexnum,&G.arcnum); getchar();//过滤回车 printf("依次输入图的顶点名称ABCD...等等:\n"); for (i=0; i<G.vexnum; i++) { scanf("%c",&G.vertices[i].data);//构造顶点数据 G.vertices[i].firstarc=NULL; //初始化指向链表指针 } getchar();//过滤回车 printf("按照: 尾顶点名->头顶点名 输入数据:如A->B \n"); for (k=0; k<G.arcnum; k++){ scanf("%c->%c",&v,&w); getchar(); for(i=0;i<G.vexnum; i++) if(G.vertices[i].data==v) break;//查找出v在vertices[]中的位置i if(i==G.vexnum) {cerr<<"vertex ERROR!";exit(1);} for(j=0;j<G.vexnum; j++) if(G.vertices[j].data==w) break;//查找出w在vertices[]中的位置i if(j==G.vexnum) {cerr<<"vertex ERROR!";exit(1);} p=(EdgeNode *)malloc(sizeof(EdgeNode));//申请弧结点 p->adjvex=j; //置入弧尾顶点号 p->info =MaxValue; //图的权值默认为无穷大 p->next=G.vertices[i].firstarc; //插入链表 G.vertices[i].firstarc=p; } } //////////////////////////////////////////////////////////////////////////////////////////////// void CreateGraph_DN(ALGraph &G)//构造有向网G { EdgeNode *p; int i,j,k; char v,w; WeightType q; G.kind=DN; //图的种类 printf("输入要构造的有向网的顶点数和弧数:\n"); scanf("%d,%d",&G.vexnum,&G.arcnum); getchar();//过滤回车 printf("依次输入图的顶点名称ABCD...等等:\n"); for (i=0; i<G.vexnum; i++) { scanf("%c",&G.vertices[i].data);//构造顶点数据 G.vertices[i].firstarc=NULL; //初始化指向链表指针 } getchar();//过滤回车 printf("按照: 尾顶点名->头顶点名,权值 输入数据:如A->B,8 \n"); for (k=0; k<G.arcnum; k++){ scanf("%c->%c,%d",&v,&w,&q); getchar(); for(i=0;i<G.vexnum; i++) if(G.vertices[i].data==v) break;//查找出v在vertices[]中的位置i if(i==G.vexnum) {cerr<<"vertex ERROR!";exit(1);} for(j=0;j<G.vexnum; j++) if(G.vertices[j].data==w) break;//查找出w在vertices[]中的位置i if(j==G.vexnum) {cerr<<"vertex ERROR!";exit(1);} p=(EdgeNode *)malloc(sizeof(EdgeNode));//申请弧结点 p->adjvex=j; //置入弧尾顶点号 p->info =q; //图的权值默认为无穷大 p->next=G.vertices[i].firstarc; //插入链表 G.vertices[i].firstarc=p; } } void CreateGraph_AG(ALGraph &G)//构造无向图G { EdgeNode *p; int i,j,k; char v,w; G.kind=AG; //图的种类 printf("输入要构造的有向图的顶点数和弧数:\n"); scanf("%d,%d",&G.vexnum,&G.arcnum); getchar();//过滤回车 printf("依次输入图的顶点名称ABCD...等等:\n"); for (i=0; i<G.vexnum; i++) { scanf("%c",&G.vertices[i].data);//构造顶点数据 G.vertices[i].firstarc=NULL; //初始化指向链表指针 } getchar();//过滤回车 printf("按照: 尾顶点名->头顶点名 输入数据:如A->B \n"); for (k=0; k<G.arcnum; k++){ scanf("%c->%c",&v,&w); getchar(); for(i=0;i<G.vexnum; i++) if(G.vertices[i].data==v) break;//查找出v在vertices[]中的位置i if(i==G.vexnum) {cerr<<"vertex ERROR!";exit(1);} for(j=0;j<G.vexnum; j++) if(G.vertices[j].data==w) break;//查找出w在vertices[]中的位置i if(j==G.vexnum) {cerr<<"vertex ERROR!";exit(1);} p=(EdgeNode *)malloc(sizeof(EdgeNode));//申请弧结点 p->adjvex=j; //置入弧尾顶点号 p->info =MaxValue; //图的权值默认为无穷大 p->next=G.vertices[i].firstarc; //插入链表 G.vertices[i].firstarc=p; //无向图和网的边结点依附于i,j两个顶点,两方均应添加边 p=(EdgeNode *)malloc(sizeof(EdgeNode));//申请弧结点 p->adjvex=i; //置入弧尾顶点号 p->info =MaxValue; //图的权值默认为无穷大 p->next=G.vertices[j].firstarc; //插入链表 G.vertices[j].firstarc=p; } } /////////////////////////////////////////////////////////////////////////////////////////// void CreateGraph_AN(ALGraph &G)//构造无向网G { EdgeNode *p; int i,j,k; char v,w; WeightType q; G.kind=AN; //图的种类 printf("输入要构造的无向网的顶点数和弧数:\n"); scanf("%d,%d",&G.vexnum,&G.arcnum); getchar();//过滤回车 printf("依次输入图的顶点名称ABCD...等等:\n"); for (i=0; i<G.vexnum; i++) { scanf("%c",&G.vertices[i].data);//构造顶点数据 G.vertices[i].firstarc=NULL; //初始化指向链表指针 } getchar();//过滤回车 printf("按照: 尾顶点名--头顶点名,权值 输入数据:如A--B,8 \n"); for (k=0; k<G.arcnum; k++){ scanf("%c--%c,%d",&v,&w,&q); getchar(); for(i=0;i<G.vexnum; i++) if(G.vertices[i].data==v) break;//查找出v在vertices[]中的位置i if(i==G.vexnum) {cerr<<"vertex ERROR!";exit(1);} for(j=0;j<G.vexnum; j++) if(G.vertices[j].data==w) break;//查找出w在vertices[]中的位置i if(j==G.vexnum) {cerr<<"vertex ERROR!";exit(1);} p=(EdgeNode *)malloc(sizeof(EdgeNode));//申请弧结点 p->adjvex=j; //置入弧尾顶点号 p->info =q; //图的权值默认为无穷大 p->next=G.vertices[i].firstarc; //插入链表 G.vertices[i].firstarc=p; //无向图和网的边结点依附于i,j两个顶点,两方均应添加边 p=(EdgeNode *)malloc(sizeof(EdgeNode));//申请弧结点 p->adjvex=i; //置入弧尾顶点号 p->info =q; //图的权值默认为无穷大 p->next=G.vertices[j].firstarc; //插入链表 G.vertices[j].firstarc=p; } } void dfsAdjoin(ALGraph G,int i,bool *visited) //深度优先搜索p266 { cout<<i<<':'<<G.vertices[i].data <<", "; visited[i]=true; EdgeNode *p=G.vertices[i].firstarc ; while(p!=NULL) { int j=p->adjvex; if(visited[j]==false) dfsAdjoin(G,j,visited); p=p->next ; } } void bfsAdjoin(ALGraph G,int i,bool *visited) //广度优先搜索p268 { const int MSize=30; int q[MSize]={0}; int front=0,rear=0; cout<<G.vertices[i].data<<' '; visited[i]=true; q[++rear]=i; while(front!=rear){ front=(front+1)%MSize; int k=q[front]; EdgeNode *p=G.vertices[k].firstarc; while(p!=NULL){ int j=p->adjvex; if(!visited[j]){ cout<<G.vertices[j].data<<' '; visited[j]=true; rear=(rear+1)%MSize; q[rear]=j; } p=p->next; } } } //*****************完成函数********************************** void countdig(ALGraph G) //请完成计算图的入度或初度 { if(G.kind==DG||G.kind==DN) { //计算有向图或网的个顶点的入度与初度 int outD,inD; EdgeNode *p,*k; int i,j; for(i=0;i<G.vexnum;i++){ outD=0; inD=0; p=G.vertices[i].firstarc; for(;p!=NULL;p=p->next){ outD++; } for(j=0;j<G.vexnum;j++){ k=G.vertices[j].firstarc; for(;k!=NULL;k=k->next){ if(G.vertices[k->adjvex].data==G.vertices[i].data) inD++; } } printf("%c:出度是%d,入度是%d\n",G.vertices[i].data,outD,inD); } } else { // 计算无向图或网的度 int Du; EdgeNode *p,*k; int i,j; for(i=0;i<G.vexnum;i++){ Du=0; p=G.vertices[i].firstarc; for(;p!=NULL;p=p->next){ Du++; } printf("%c:度是%d\n",G.vertices[i].data,Du); } } } void PrintALGraph(ALGraph &G){//打印邻接表 EdgeNode *p; int i; for (i=0; i<G.vexnum; i++) { if(G.vertices[i].firstarc!=NULL) //输出顶点名称 printf("%d | %c =>",i,G.vertices[i].data); else printf("%d | %c ^",i,G.vertices[i].data); p=G.vertices[i].firstarc; //输出依附上面顶点的各条边
展开阅读全文

开通  VIP会员、SVIP会员  优惠大
下载10份以上建议开通VIP会员
下载20份以上建议开通SVIP会员


开通VIP      成为共赢上传
相似文档                                   自信AI助手自信AI助手

当前位置:首页 > 包罗万象 > 大杂烩

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        抽奖活动

©2010-2025 宁波自信网络信息技术有限公司  版权所有

客服电话:4009-655-100  投诉/维权电话:18658249818

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :微信公众号    抖音    微博    LOFTER 

客服