图的封装（C++）

一. 问题说明1.问题的简单描述将图和网的的创建和基本操作分封装到class用来熟悉此种数据结构和基于这种数据结构上的基本算法采用VS2010编译环境2.工作安排二. 源代码1.文件stdafx.h1 #pragma once2 #include "targe...

weixin_30641999

171人浏览 · 2018-05-05 12:07:00

weixin_30641999 · 2018-05-05 12:07:00 发布

一. 问题说明

1.问题的简单描述

将图和网的的创建和基本操作分封装到class

用来熟悉此种数据结构和基于这种数据结构上的基本算法

采用VS2010编译环境

2.工作安排

二. 源代码

1.文件stdafx.h

 1 #pragma once
 2 #include "targetver.h"
 3 #include <stdio.h>
 4 #include <tchar.h>
 5 #include<iostream>
 6 #include<string>
 7 #include<string.h>
 8 using namespace std;
 9 /*
10     以下完成图的存储结构
11     (
12         关键在于结构体的组合
13     )
14 */
15 #define INFINITY   INT_MAX // 用整形最大值代替∞
16 const int MAX_VERTEX_NUM=26;// 最大顶点个数
17 #define VRType  int  //顶点关系类型
18 #define InfoType  string//弧相关信息
19 #define VertexType string//顶点类型
20 enum GraphKind{DG,DN,UDG,UDN};// 有向图，有向网，无向图，无向网
21 typedef struct 
22 {
23     VRType  adj; //adjacency  邻接
24                  // 对图来说1(是)，0(否)表示相邻关系
25                  // 对网来说为权值
26     InfoType info;   //Info 信息
27                       //该弧相关信息的指针
28 }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
29       //Arc  弧（边）
30 struct MGraph
31 {
32     VertexType vex[MAX_VERTEX_NUM];   //顶点向量
33     AdjMatrix arcs;   //邻接矩阵
34     int vexnum,arcnum ;
35     GraphKind kind;   //图的种类
36 };
37 class Graph
38 {  
39 private:
40     MGraph G;
41 public:
42     Graph();
43     void CreateUDG();//创建无向图
44     void CreateUDN();//创建无向网
45     void CreateDG(); //创建有向图
46     void CreateDN(); //创建有向网
47     void CreateUDG_BYFile();//创建无向图,通过文件
48     void CreateUDN_BYFile();//创建无向网,通过文件
49     void CreateDG_BYFile(); //创建有向图,通过文件
50     void CreateDN_BYFile(); //创建有向网,通过文件
51     int LocateVex(VertexType u); //以顶点名称确定其邻接矩阵中的位置
52     void  Display();//展示图或网的顶点向量，和邻接矩阵
53 };

2.文件Graph_Matrix.cpp

  1 #include "stdafx.h"
  2 Graph::Graph()
  3 {   
  4     cout<<"请输入图G的类型（ 有向图：0； 有向网：1； 无向图 ：2； 无向网 3；）"<<endl;
  5     scanf("%d",&G.kind);
  6     switch(G.kind)
  7     {
  8         case UDG: CreateUDG();
  9                   break;
 10         case UDN: CreateUDN();
 11                   break;
 12         case DG: CreateDG();
 13                   break;
 14         case DN: CreateDN();
 15                   break;
 16     }
 17 }
 18 void Graph::CreateUDG()
 19 {
 20     /*采用数组（邻接矩阵）表示法，构造无向图G
 21       以边为输入单位，即输入边的俩个顶点
 22       关键在于判断输入顶点是否存在，返回其位置
 23     */
 24     int i,j,IncInfo;//是否包含边或弧的相关信息
 25     VertexType  va,vb;
 26     cout<<"请输入无向图的顶点数，边数，变是否包含其他信息（是：1； 否；0；）"<<endl;
 27     cin>>G.vexnum;//顶点数
 28     cin>>G.arcnum;//边数
 29     cin>>IncInfo;//是否具有相关信息的判断条件
 30     cout<<"请输入"<<G.vexnum<<"个顶点的的值"<<endl;
 31     for(i=0; i<G.vexnum; i++)//构造顶点向量
 32     {
 33         cin>>G.vex[i];
 34     }
 35     for(i=0; i<G.vexnum; i++)//初始化邻接矩阵
 36     {
 37         for(j=0; j<G.vexnum; j++)
 38         {
 39             G.arcs[i][j].adj=0;//图
 40             G.arcs[i][j].info="NULL";//初始化为空串
 41         }
 42     }
 43     cout<<"请输入"<<G.arcnum<<"条边的顶点1，顶点2："<<endl;
 44     for(int k=0; k<G.arcnum; k++)//按边录入信息
 45     {
 46         cin>>va;
 47         i=LocateVex(va);//查询下标,va所在的行坐标
 48         cin>>vb;
 49         j=LocateVex(vb);//查询下标,vb所在的行坐标
 50         G.arcs[i][j].adj=1;  //表示va 与 vb 相连  无向图
 51         G.arcs[j][i].adj=1;  //表示va与vb相连     无向图
 52         if(IncInfo)
 53         {
 54             cout<<"请输入该边相关信息"<<endl;
 55             cin>>G.arcs[i][j].info;  //输入字符串
 56             G.arcs[j][i].info=G.arcs[i][j].info;//对称阵
 57         }
 58     }
 59     G.kind=UDG;  //创建成功
 60 }
 61 void Graph::CreateUDN()
 62 {
 63     /*
 64         原理和UDG相同，只是增加了权值的输入
 65     */
 66     int i,j,IncInfo;//是否包含边或弧的相关信息
 67     VertexType  va,vb;
 68     cout<<"请输入无向网的顶点数，边数，变是否包含其他信息（是：1； 否；0；）"<<endl;
 69     cin>>G.vexnum;//顶点数
 70     cin>>G.arcnum;//边数
 71     cin>>IncInfo;//是否具有相关信息的判断条件
 72     cout<<"请输入"<<G.vexnum<<"个顶点的的值"<<endl;
 73     for(i=0; i<G.vexnum; i++)//构造顶点向量
 74     {
 75         cin>>G.vex[i];
 76     }
 77     for(i=0; i<G.vexnum; i++)//初始化邻接矩阵
 78     {
 79         for(j=0; j<G.vexnum; j++)
 80         {
 81             G.arcs[i][j].adj=INFINITY;//网，无穷大表示不连接
 82             G.arcs[i][j].info="NULL";//初始化为空串
 83         }
 84     }
 85     for(int k=0; k<G.arcnum; k++)//按边录入信息
 86     {
 87         cout<<"请输入第"<<k+1<<"条边的顶点1，顶点2："<<endl;
 88         cin>>va;
 89         i=LocateVex(va);//查询下标,va所在的行坐标
 90         cin>>vb;
 91         j=LocateVex(vb);//查询下标,vb所在的行坐标
 92         cout<<"请输入权值"<<endl;
 93         cin>>G.arcs[i][j].adj;
 94         G.arcs[j][i].adj=G.arcs[i][j].adj;
 95         if(IncInfo)
 96         {
 97             cout<<"请输入该边相关信息"<<endl;
 98             cin>>G.arcs[i][j].info;  //输入字符串
 99             G.arcs[j][i].info=G.arcs[i][j].info;//对称阵
100         }
101     }
102     G.kind=UDN;  //创建成功
103 }
104 void Graph::CreateDG()
105 {
106     /*
107         原理与UDG相同，邻接矩阵略有区别
108     */
109     int i,j,IncInfo;//是否包含边或弧的相关信息
110     VertexType  va,vb;
111     cout<<"请输入有向图的顶点数，边数，变是否包含其他信息（是：1； 否；0；）"<<endl;
112     cin>>G.vexnum;//顶点数
113     cin>>G.arcnum;//边数
114     cin>>IncInfo;//是否具有相关信息的判断条件
115     cout<<"请输入"<<G.vexnum<<"个顶点的的值"<<endl;
116     for(i=0; i<G.vexnum; i++)//构造顶点向量
117     {
118         cin>>G.vex[i];
119     }
120     for(i=0; i<G.vexnum; i++)//初始化邻接矩阵
121     {
122         for(j=0; j<G.vexnum; j++)
123         {
124             G.arcs[i][j].adj=0;//图
125             G.arcs[i][j].info="NULL";//初始化为空串
126         }
127     }
128     cout<<"请输入"<<G.arcnum<<"条弧的弧头，弧尾："<<endl;
129     for(int k=0; k<G.arcnum; k++)//按边录入信息
130     {
131         cin>>va;
132         i=LocateVex(va);//查询下标,va所在的行坐标
133         cin>>vb;
134         j=LocateVex(vb);//查询下标,vb所在的行坐标
135         G.arcs[j][i].adj=1;  //表示vb(弧尾) 与 vb（弧头） 相连,也就是说vb可以到达va，反之不一定  有向图 vb——>va
136         if(IncInfo)
137         {
138             cout<<"请输入该弧相关信息"<<endl;
139             cin>>G.arcs[i][j].info;  //输入字符串
140             G.arcs[j][i].info=G.arcs[i][j].info;//对称阵
141         }
142     }
143     G.kind=DG; //创建成功
144 }
145 void Graph::CreateDN()
146 {
147     /*
148         原理和DG相同，只是增加了权值的输入
149     */
150     int i,j,IncInfo;//是否包含边或弧的相关信息
151     VertexType  va,vb;
152     cout<<"请输入有向网的顶点数，边数，变是否包含其他信息（是：1； 否；0；）"<<endl;
153     cin>>G.vexnum;//顶点数
154     cin>>G.arcnum;//边数
155     cin>>IncInfo;//是否具有相关信息的判断条件
156     cout<<"请输入"<<G.vexnum<<"个顶点的的值"<<endl;
157     for(i=0; i<G.vexnum; i++)//构造顶点向量
158     {
159         cin>>G.vex[i];
160     }
161     for(i=0; i<G.vexnum; i++)//初始化邻接矩阵
162     {
163         for(j=0; j<G.vexnum; j++)
164         {
165             G.arcs[i][j].adj=INFINITY;//网，无穷大表示不连接
166             G.arcs[i][j].info="NULL";//初始化为空串
167         }
168     }
169     for(int k=0; k<G.arcnum; k++)//按边录入信息
170     {
171         cout<<"请输入第"<<k+1<<"条弧的弧头，弧尾："<<endl;
172         cin>>va;
173         i=LocateVex(va);//查询下标,va所在的行坐标
174         cin>>vb;
175         j=LocateVex(vb);//查询下标,vb所在的行坐标
176         cout<<"请输入权值"<<endl;
177         cin>>G.arcs[j][i].adj;
178         if(IncInfo)
179         {
180             cout<<"请输入该弧相关信息"<<endl;
181             cin>>G.arcs[i][j].info;  //输入字符串
182             G.arcs[j][i].info=G.arcs[i][j].info;//对称阵
183         }
184     }
185     G.kind=DN;  //创建成功
186 }
187 int  Graph::LocateVex(VertexType u)//给定顶点值，返回顶点在顶点数组中的下标，方便按边录入信息
188 {
189     for(int i=0; i<G.vexnum; i++)
190     {
191         if(G.vex[i]==u)
192         {
193             return i;
194         }
195     }
196     return -1;
197 }
198 void Graph::Display()
199 {
200     cout<<"顶点向量"<<endl;
201     for(int i=0; i<G.vexnum; i++)
202     {
203         cout<<"顶点"<<G.vex[i]<<endl;
204     }
205     cout<<"邻接矩阵"<<endl;
206     for(int i=0; i<G.vexnum; i++)
207     {
208         for(int j=0;j<G.vexnum;j++)
209         {
210             cout<<G.arcs[i][j].adj<<"\t";
211         }
212         cout<<endl;
213     }
214     cout<<"顶点1  顶点2    信息"<<endl;
215     if(G.kind>1) //对于无向图或者无向网来说，邻接矩阵是对称的
216     {
217         for(int i=0; i<G.vexnum; i++)
218         {
219             for(int j=0;j<i;j++)
220             {
221                 if(G.arcs[i][j].adj!=0&&G.arcs[i][j].adj!=INFINITY)
222                 {
223                     cout<<G.vex[i]<<"\t";
224                     cout<<G.vex[j]<<"\t";
225                     cout<<G.arcs[i][j].info<<endl;
226                 }
227             }
228         }
229     }
230     else//对于有向图或者有向网来说，邻接矩阵必须要全部输出
231     {
232         for(int i=0; i<G.vexnum; i++)
233         {
234             for(int j=0;j<G.vexnum;j++)
235             {
236                 if(G.arcs[i][j].adj!=0&&G.arcs[i][j].adj!=INFINITY)
237                 {
238                     cout<<G.vex[i]<<"\t";
239                     cout<<G.vex[j]<<"\t";
240                     cout<<G.arcs[i][j].info<<endl;
241                 }
242             }
243         }
244     }
245 }
246 int _tmain(int argc, _TCHAR* argv[])
247 {   
248     Graph g;
249     g.Display();
250     return 0;
251 }