一个无向图G，五个顶点，8条边，用邻接表形式表示该图
那么该如何用C语言来表达呢？
首先看看我们的无向图的头文件ALGraph.h
其中最关键的是边表和顶点表
边表是关联顶点与其他顶点之间的关联
而顶点表是一个数组，保存所有的顶点，每个顶点内保存着顶点编号、权值 以及 边表头
聪明的你不难看出，这其实类似一个二维数组，只不过最里层的是一个不定长数组
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50#include <stdio.h> #include <stdlib.h> #include <string.h> #ifndef ALGRAPH_H_INCLUDED #define ALGRAPH_H_INCLUDED #define MAXVERTEXNUM 1000 //最大顶点数 //定义一个顶点类型 typedef unsigned char VertexType; typedef unsigned char WeightType; //边表结点 typedef struct EDGENODE { int adjVertex;//边编号 struct EDGENODE * nextNode; } EdgeNode; //顶点表结点 typedef struct VERTEXNODE { VertexType vertex; //顶点值 WeightType weight;//权值 EdgeNode * FirstEdge;//第一边结点 } VertexNode; //顶点表类型 typedef VertexNode AdjList[MAXVERTEXNUM]; //图 typedef struct ALGRAPH { AdjList adjlist; int VertexNum;//顶点数 int EdgeNum;//边数 } ALGraph; /** * 函数的定义 */ //图的初始化 int ALGraph_init(ALGraph ** pg); //创建图 int Create_ALGraph(ALGraph * g); //输出图结构 void Output_ALGraph(ALGraph *g); #endif // ALGRAPH_H_INCLUDED
接下来是源文件ALGraph.c，用于实现创建图等操作，重要地方都有注释，最后遍历邻接表的方法类似二维不定长数组的遍历
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109#include "ALGraph.h" //图的初始化 int ALGraph_init(ALGraph ** pg) { *pg = (ALGraph *)malloc(sizeof(ALGraph)); if(*pg==NULL)//内存分配失败 { return -1; } memset(*pg,0,sizeof(ALGraph));//内存内容全部填充为0 return 0; } //创建图 int Create_ALGraph(ALGraph * g) { if(g==NULL) { printf("创建图时发现错误，未完成初始化操作！n"); return -1; } printf("请输入顶点数: "); scanf("%d",&(g->VertexNum)); fflush(stdin); printf("请输入边数: "); scanf("%d",&(g->EdgeNum)); fflush(stdin); if(g->EdgeNum < g->VertexNum - 1) // N个结点至少需要N-1条边 { printf("边数的值不合法！n"); return -1; } //***************************************************************** printf("开始创建顶点表vertexlistn"); int n; for(n=0; n<g->VertexNum; n++) { fflush(stdin); printf("vertexlist 第%d项是V",n); scanf("%d",&(g->adjlist[n].vertex)); //取值范围为0-65535 g->adjlist[n].weight = 0; g->adjlist[n].FirstEdge = NULL; } printf("创建顶点表完成!n"); //***************************************************************** EdgeNode * p = NULL; printf("n开始创建边表edgelistn"); int i,j; for(n=0; n<g->EdgeNum; n++) { fflush(stdin); printf("请输入边（Vi,Vj）的顶点序号："); scanf("%d,%d",&i,&j); if(i<0 || j<0||i>(g->VertexNum)||j>(g->VertexNum)) { printf("输入的值存在非法，操作失败！n"); return -1; } //在g->adjlist[i]处建立与j的关系 p = (EdgeNode *)malloc(sizeof(EdgeNode)); if(p==NULL) { printf("初始化结构体EdgeNode变量p失败"); return -1; } p->adjVertex = j; p->nextNode = g->adjlist[i].FirstEdge; g->adjlist[i].FirstEdge = p; //在g->adjlist[j]处建立与i的关系 p = (EdgeNode *)malloc(sizeof(EdgeNode)); if(p==NULL) { printf("初始化结构体EdgeNode变量p失败"); return -1; } p->adjVertex = i; p->nextNode = g->adjlist[j].FirstEdge; g->adjlist[j].FirstEdge = p; } printf("创建边表完成!n"); return 0; } //输出图结构 void Output_ALGraph(ALGraph *g) { printf("n邻接表输出如下: n"); EdgeNode * p; int n; for(n=0 ; n<g->VertexNum ; n++) { printf("%d ",g->adjlist[n].vertex);//输出顶点值 p = g->adjlist[n].FirstEdge; while(p!=NULL) { printf("->"); printf("%d ",p->adjVertex); p = p->nextNode; } printf("n"); } }
我们最重要的main方法
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27#include "ALGraph.h" #include <stdio.h> #include <stdlib.h> int main(int argc, char *arg[]) { printf("尝试将一个无向图转为一个邻接表！nn"); int ret; ALGraph *g = NULL; ret = ALGraph_init(&g);//初始化邻接表内存区 if(ret<0) { perror("初始化图时发现错误：没有完成初始化操作n"); return -1; } ret = Create_ALGraph(g);//创建邻接表 if(ret<0) { printf("创建邻接表失败！n"); return -1; } Output_ALGraph(g);//输出邻接表 return 0; }
最后
以上就是等待世界最近收集整理的关于数据结构->图的邻接表存储(C语言)的全部内容，更多相关数据结构->图内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复