声明: 代码中有大量的注释,所以此处就不再作出大量的解释了。
一 :邻接矩阵存储结构
1.首先是各种类型与宏的定义:
1 #include <iostream> 2 using namespace std; 3 //无穷大 4 #define infinity int_max 5 //最大顶点个数 6 #define max_vertex_num 20 7 //顶点类型 8 typedef char vertextype; 9 typedef int vrtype; 10 typedef char infotype; 11 //图的四种类型 12 typedef enum {dg = 1, dn, udg, udn} graphkind; 13 14 //弧的结构体定义 15 typedef struct arccell 16 { 17 // 对于网来说是权值;对于图来说就是0或1 18 vrtype adj; 19 //该弧相关信息的指针(现在暂且可以理解为字符指针) 20 infotype* info; 21 }arccell, adjmatrix[max_vertex_num][max_vertex_num]; 22 23 //图的结构体定义 24 typedef struct 25 { 26 vertextype vexs[max_vertex_num]; 27 //arcs可以先简单地理解为一个数组名 28 adjmatrix arcs; 29 //当前图中的顶点数和弧数 30 int vexnum, arcnum; 31 //图的种类标志 32 graphkind kind; 33 }mgraph;
2.接下来是函数声明及main函数:
void creategraph(mgraph &g); void createudn(mgraph &g); int locatevex(mgraph g , int v1); void createudg(mgraph &g); void createdg(mgraph &g); void createdn(mgraph &g); void print(mgraph g); int main(void) { mgraph g; creategraph(g); return 0; }
3.最后就是各种自定义函数的定义了:
void creategraph(mgraph &g) { cout << "1、有向图" << endl; cout << "2、有向网" << endl; cout << "3、无向图" << endl; cout << "4、无向网" << endl; cout << "你需要创建哪一种类型的图?" << endl; //此处运用了强转(不能直接从键盘上给枚举变量赋值) cin >> (int&)g.kind; switch (g.kind) { case 1: return createdg(g); break; case 2: return createdn(g); break; case 3: return createudg(g); break; case 4: return createudn(g); break; } } //创建有向网 void createdn(mgraph &g) { cout << "该图有多少顶点以及多少条弧?" << endl; cin >> g.vexnum >> g.arcnum; cout << "请输入顶点:" << endl; for(int i = 0; i < g.vexnum; i++) { //cin相当于c里面的scanf函数 cin >> g.vexs[i]; } for(int i = 0; i < g.vexnum; i++) { for(int j = 0; j < g.vexnum; j++) { //先假设每两个点之间都没有边 g.arcs[i][j].adj = infinity; } } cout << "请输入各弧的两个端点及其权值" << endl; vertextype v1, v2; //用于暂时存储每条弧的权值 vrtype temp; int i, j; //有向网不具备对称性 for(int k = 0; k < g.arcnum; k++) { cin >> v1 >> v2 >> temp; //利用存储顶点所用的一维数组中对应点的下标 i = locatevex(g, v1), j = locatevex(g, v2), g.arcs[i][j].adj = temp; } print(g); } //创建有向图 void createdg(mgraph &g) { cout << "该图有多少顶点以及多少条边?" << endl; cin >> g.vexnum >> g.arcnum; cout << "请输入顶点:" << endl; for(int i = 0; i < g.vexnum; i++) { cin >> g.vexs[i]; } for(int i = 0; i < g.vexnum; i++) { for(int j = 0; j < g.vexnum; j++) { //先假定图中没有弧 g.arcs[i][j].adj = 0; } } cout << "请输入各弧的两个端点" << endl; vertextype v1, v2; //用于暂时存储每条弧的'权值'(存在即为1,否则为0) //因为temp的取值只能为1或0,所以不需要再输入 vrtype temp = 1; int i, j; //有向图不具备对称性 for(int k = 0; k < g.arcnum; k++) { cin >> v1 >> v2; i = locatevex(g, v1), j = locatevex(g, v2), g.arcs[i][j].adj = temp; } print(g); } //创建无向图(对称) void createudg(mgraph &g) { cout << "该图有多少顶点以及多少条边?" << endl; cin >> g.vexnum >> g.arcnum; cout << "请输入顶点:" << endl; for(int i = 0; i < g.vexnum; i++) { cin >> g.vexs[i]; } for(int i = 0; i < g.vexnum; i++) { for(int j = 0; j < g.vexnum; j++) { //先假设每两个点之间都没有边 g.arcs[i][j].adj = 0; } } cout << "请输入各弧的两个端点(下三角)" << endl; vertextype v1, v2; vrtype temp = 1; int i, j; //考虑到无向图具有对称性(先只输入(邻接矩阵)下三角里存在的边) for(int k = 0; k < g.arcnum; k++) { cin >> v1 >> v2; i = locatevex(g, v1), j = locatevex(g, v2), g.arcs[i][j].adj = temp; //将上三角里的每条弧同样添加上权值 g.arcs[j][i].adj = g.arcs[i][j].adj; } print(g); } //创建无向网(对称) void createudn(mgraph &g) { cout << "该图有多少顶点以及多少条边?" << endl; cin >> g.vexnum >> g.arcnum; cout << "请输入顶点:" << endl; for(int i = 0; i < g.vexnum; i++) { cin >> g.vexs[i]; } for(int i = 0; i < g.vexnum; i++) { for(int j = 0; j < g.vexnum; j++) { //先假设每两个点之间都没有边(无穷远) g.arcs[i][j].adj = infinity; } } cout << "请输入各弧的两个端点及其权值(下三角)" << endl; vertextype v1, v2; vrtype temp; int i, j; //考虑到无向图具有对称性(先只输入(邻接矩阵)下三角里存在的边) for(int k = 0; k < g.arcnum; k++) { cin >> v1 >> v2 >> temp; i = locatevex(g, v1), j = locatevex(g, v2), g.arcs[i][j].adj = temp; //将上三角里的每条弧同样添加上权值 g.arcs[j][i].adj = g.arcs[i][j].adj; } print(g); } //返回该顶点在一维数组中的下标(当然每一个人创建的一维数组可以是不同的) int locatevex(mgraph g , int v1) { for(int i = 0; i < g.vexnum; i++) { if(g.vexs[i] == v1) return i; } } void print(mgraph g) { cout << "存储的一维数组如下:" << endl; for(int i = 0; i < g.vexnum; i++) { cout << g.vexs[i] << 't'; } cout << endl; cout << "邻接矩阵如下:" << endl; for(int i = 0; i < g.vexnum; i++) { for(int j = 0; j < g.vexnum; j++) { cout << g.arcs[i][j].adj << 't'; } cout << endl; } }
二 :邻接表存储结构
1 #include <iostream> 2 #include <string> 3 using namespace std; 4 using std :: string; 5 typedef string infortype; 6 //顶点类型 7 typedef char vertextype; 8 typedef int status; 9 typedef enum {udg = 1, dg, udn, dn} graphkind; 10 //最大顶点个数 11 #define max_vertex_num 20 12 #define error -1 13 #define ok 1 14 //表节点的定义 15 typedef struct arcnode 16 { 17 //该弧所指向的顶点的位置(相对地址) 18 int adjvex; 19 //指向下一条弧的指针 20 struct arcnode* nextarc; 21 //该弧相关信息的指针(例如权值) 22 infortype info; 23 }arcnode; 24 //头节点的定义 25 typedef struct vnode 26 { 27 //顶点信息 28 vertextype data; 29 //指向第一条依附该顶点的弧的指针 30 arcnode* firstarc; 31 }vnode, adjlist[max_vertex_num]; 32 //图的定义 33 typedef struct 34 { 35 //存放头节点的一维数组 36 adjlist vertices; 37 //图的当前顶点数和弧数 38 int vexnum, arcnum; 39 //图的种类标志 40 graphkind kind; 41 }algraph; 42 void creategraph(algraph& g); 43 status createudn(algraph& g); 44 status createudg(algraph& g); 45 status createdg(algraph& g); 46 status createdn(algraph& g); 47 int locatevex(vnode vertices[], int vexnum, vertextype e); 48 void print(const algraph& g); 49 int main(void) 50 { 51 algraph g; 52 creategraph(g); 53 return 0; 54 } 55 void creategraph(algraph& g) 56 { 57 int reply; 58 cout << "1. 无向图" << endl; 59 cout << "2. 有向图" << endl; 60 cout << "3. 无向网" << endl; 61 cout << "4. 有向网" << endl; 62 //其实逆与正是差不多的,根本上还是取决于用户的输入 63 cout << "5. 逆有向网" << endl; 64 cout << "6. 逆有向图" << endl; 65 cout << "你想创建哪一种类型的图?" << endl; 66 cin >> reply; 67 switch(reply) 68 { 69 case 1: 70 createudg(g); 71 break; 72 case 2: 73 createdg(g); 74 break; 75 case 3: 76 createudn(g); 77 break; 78 case 4: 79 createdn(g); 80 break; 81 case 5: 82 createdn(g); 83 break; 84 case 6: 85 createdg(g); 86 break; 87 default: 88 exit(-1); 89 } 90 } 91 //构造无向网 92 status createudn(algraph& g) 93 { 94 vertextype e; 95 int num; 96 cout << "该图共有多少个顶点、多少条弧?" << endl; 97 cin >> g.vexnum >> g.arcnum; 98 cout << "请输入各顶点:" << endl; 99 for(int i = 0; i < g.vexnum; i++) 100 { 101 //注意存储结构 102 cin >> g.vertices[i].data; 103 //先将头节点的指针域设为空 104 g.vertices[i].firstarc = null; 105 } 106 for(int i = 0; i < g.vexnum; i++) 107 { 108 //(强调引用) 109 //注意ptr是节点的指针(是节点类型的一部分)而不是‘指向’节点的指针 110 //所以接连各节点不想以前那样简单了 111 arcnode* &ptr = g.vertices[i].firstarc; 112 cout << "请问以顶点" << g.vertices[i].data << "为起点的弧一共有多少条?" << endl; 113 cin >> num; 114 if(num > 0) 115 { 116 int index; 117 arcnode* p = null; 118 cout << "请将这些顶点及弧所带信息依次输入:" << endl; 119 //先处理一个节点(为了方便后面的操作) 120 ptr = new arcnode; 121 if(ptr) 122 { 123 cin >> e; 124 //输入弧上的信息 125 cin >> ptr->info; 126 index = locatevex(g.vertices, g.vexnum, e); 127 p = ptr; 128 p->adjvex = index; 129 p->nextarc = null; 130 } 131 else 132 return error; 133 for(int j = 1; j < num; j++) 134 { 135 arcnode* ptr2 = new arcnode; 136 if(ptr2) 137 { 138 //注意各变量的类型,不要搞混了 139 cin >> e; 140 //输入弧上的信息 141 cin >> ptr2->info; 142 index = locatevex(g.vertices, g.vexnum, e); 143 ptr2->adjvex = index; 144 ptr2->nextarc = null; 145 //注意此处的连接节点与以前写的有点不同(ptr‘一直’为空) 146 p->nextarc = ptr2; 147 p = p->nextarc; 148 } 149 else 150 return error; 151 } 152 } 153 } 154 print(g); 155 return ok; 156 } 157 //构造无向图 158 status createudg(algraph& g) 159 { 160 vertextype e; 161 int num; 162 cout << "该图共有多少个顶点、多少条弧?" << endl; 163 cin >> g.vexnum >> g.arcnum; 164 cout << "请输入各顶点:" << endl; 165 for(int i = 0; i < g.vexnum; i++) 166 { 167 //注意存储结构 168 cin >> g.vertices[i].data; 169 //先将头节点的指针域设为空 170 g.vertices[i].firstarc = null; 171 } 172 for(int i = 0; i < g.vexnum; i++) 173 { 174 //(强调引用) 175 //注意ptr是节点的指针(是节点类型的一部分)而不是‘指向’节点的指针 176 //所以接连各节点不想以前那样简单了 177 arcnode* &ptr = g.vertices[i].firstarc; 178 cout << "请问以顶点" << g.vertices[i].data << "为起点的弧一共有多少条?" << endl; 179 cin >> num; 180 if(num > 0) 181 { 182 int index; 183 arcnode* p = null; 184 cout << "请将这些顶点依次输入:" << endl; 185 //先处理一个节点(为了方便后面的操作) 186 ptr = new arcnode; 187 if(ptr) 188 { 189 cin >> e; 190 index = locatevex(g.vertices, g.vexnum, e); 191 p = ptr; 192 p->adjvex = index; 193 p->nextarc = null; 194 } 195 else 196 return error; 197 for(int j = 1; j < num; j++) 198 { 199 //注意各变量的类型,不要搞混了 200 cin >> e; 201 index = locatevex(g.vertices, g.vexnum, e); 202 arcnode* ptr2 = new arcnode; 203 if(ptr2) 204 { 205 ptr2->adjvex = index; 206 ptr2->nextarc = null; 207 //注意此处的连接节点与以前写的有点不同(ptr‘一直’为空) 208 p->nextarc = ptr2; 209 p = p->nextarc; 210 } 211 else 212 return error; 213 } 214 } 215 } 216 print(g); 217 return ok; 218 } 219 //构造有向图 220 status createdg(algraph& g) 221 { 222 vertextype e; 223 int num; 224 cout << "该图共有多少个顶点、多少条弧?" << endl; 225 cin >> g.vexnum >> g.arcnum; 226 cout << "请输入各顶点:" << endl; 227 for(int i = 0; i < g.vexnum; i++) 228 { 229 //注意存储结构 230 cin >> g.vertices[i].data; 231 //先将头节点的指针域设为空 232 g.vertices[i].firstarc = null; 233 } 234 for(int i = 0; i < g.vexnum; i++) 235 { 236 //(强调引用) 237 //注意ptr是节点的指针(是节点类型的一部分)而不是‘指向’节点的指针 238 //所以接连各节点不想以前那样简单了 239 arcnode* &ptr = g.vertices[i].firstarc; 240 cout << "请问以顶点" << g.vertices[i].data << "为起点的弧一共有多少条?" << endl; 241 cin >> num; 242 if(num > 0) 243 { 244 int index; 245 arcnode* p = null; 246 cout << "请将这些顶点依次输入:" << endl; 247 //先处理一个节点(为了方便后面的操作) 248 ptr = new arcnode; 249 if(ptr) 250 { 251 cin >> e; 252 index = locatevex(g.vertices, g.vexnum, e); 253 p = ptr; 254 p->adjvex = index; 255 p->nextarc = null; 256 } 257 else 258 return error; 259 for(int j = 1; j < num; j++) 260 { 261 //注意各变量的类型,不要搞混了 262 cin >> e; 263 index = locatevex(g.vertices, g.vexnum, e); 264 arcnode* ptr2 = new arcnode; 265 if(ptr2) 266 { 267 ptr2->adjvex = index; 268 ptr2->nextarc = null; 269 //注意此处的连接节点与以前写的有点不同(ptr‘一直’为空) 270 p->nextarc = ptr2; 271 p = p->nextarc; 272 } 273 else 274 return error; 275 } 276 } 277 } 278 print(g); 279 return ok; 280 } 281 //构造有向网 282 status createdn(algraph& g) 283 { 284 vertextype e; 285 int num; 286 cout << "该图共有多少个顶点、多少条弧?" << endl; 287 cin >> g.vexnum >> g.arcnum; 288 cout << "请输入各顶点:" << endl; 289 for(int i = 0; i < g.vexnum; i++) 290 { 291 //注意存储结构 292 cin >> g.vertices[i].data; 293 //先将头节点的指针域设为空 294 g.vertices[i].firstarc = null; 295 } 296 for(int i = 0; i < g.vexnum; i++) 297 { 298 //(强调引用) 299 //注意ptr是节点的指针(是节点类型的一部分)而不是‘指向’节点的指针 300 //所以接连各节点不想以前那样简单了 301 arcnode* &ptr = g.vertices[i].firstarc; 302 cout << "请问以顶点" << g.vertices[i].data << "为起点的弧一共有多少条?" << endl; 303 cin >> num; 304 if(num > 0) 305 { 306 int index; 307 arcnode* p = null; 308 cout << "请将这些顶点及弧所带信息依次输入:" << endl; 309 //先处理一个节点(为了方便后面的操作) 310 ptr = new arcnode; 311 if(ptr) 312 { 313 cin >> e; 314 //输入弧上的信息 315 cin >> ptr->info; 316 index = locatevex(g.vertices, g.vexnum, e); 317 p = ptr; 318 p->adjvex = index; 319 p->nextarc = null; 320 } 321 else 322 return error; 323 for(int j = 1; j < num; j++) 324 { 325 arcnode* ptr2 = new arcnode; 326 if(ptr2) 327 { 328 //注意各变量的类型,不要搞混了 329 cin >> e; 330 //输入弧上的信息 331 cin >> ptr2->info; 332 index = locatevex(g.vertices, g.vexnum, e); 333 ptr2->adjvex = index; 334 ptr2->nextarc = null; 335 //注意此处的连接节点与以前写的有点不同(ptr‘一直’为空) 336 p->nextarc = ptr2; 337 p = p->nextarc; 338 } 339 else 340 return error; 341 } 342 } 343 } 344 print(g); 345 return ok; 346 } 347 //定位顶点在一维数组中的位置 348 int locatevex(vnode vertices[], int vexnum, vertextype e) 349 { 350 int i; 351 for(i = 0; i < vexnum; i++) 352 { 353 if(vertices[i].data == e) 354 break; 355 } 356 return i; 357 } 358 //打印图 359 void print(const algraph& g) 360 { 361 cout << "您所创建的图用邻接表存储结构展示如下:" << endl; 362 for(int i = 0; i < g.vexnum; i++) 363 { 364 cout << "[" << g.vertices[i].data << "]"; 365 arcnode* ptr = g.vertices[i].firstarc; 366 while(ptr) 367 { 368 //打印出下标(从零开始) 369 cout << "—>" << ptr->adjvex; 370 ptr = ptr->nextarc; 371 } 372 cout << endl; 373 } 374 }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/602446.html