图的邻接表表示法（C语言）
邻接表
邻接表数据结构类型如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17#define MaxVertices 100
typedef struct node{ //边表
int adjvex;
node* next;
}EdgeNode;
typedef struct{ //顶点表
int vertex;
EdgeNode* edgenext;
}VertexNode;
typedef VertexNode AdjList[MaxVertices];//顶点表数组
typedef struct{
AdjList adjlist;
int n,e;
}AdjMatrix;
注：边表为链表结构，插入元素有头插法和尾插法两种，这里以头插法为例。
对应的，我们得到如下的结构：
我们以无向图为例：
写出相应的邻接矩阵：
邻接表生成函数：
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
37void CreateGraph(AdjMatrix* G)
{
int i,j,k,w,v;
EdgeNode *s;
printf("输入顶点数和边数（中间以空格分开）：");
scanf("%d%d",&G->n,&G->e);
printf("建立顶点表\n");
for (i=0;i<G->n;i++)
{
//fflush(stdin);
//如果 stream 指向输入流（如 stdin），那么 fflush 函数的行为是不确定的。
//故而使用 fflush(stdin) 是不正确的。
getchar();
printf("请输入第%d个顶点的信息:",i+1);
G->adjlist[i].vertex=getchar();
G->adjlist[i].edgenext=NULL;
}
//前插法
printf("建立边表\n");
for (k=0;k<G->e;k++)
{
printf("输入有连接的顶点序号：");
scanf("%d%d",&i,&j);
i-=1;j-=1; //①
//对于直接相连的进行编入(即对输入“0 1”时，在0对应的边表中编入1)
s=(EdgeNode*)malloc(sizeof(EdgeNode));
s->adjvex=j;//边表赋值
s->next=G->adjlist[i].edgenext;
G->adjlist[i].edgenext=s;
//对于间接相连的进行编入(即对输入“0 1”时，在1对应的边表中编入0)
s=(EdgeNode*)malloc(sizeof(EdgeNode));
s->adjvex=i;
s->next=G->adjlist[j].edgenext;
G->adjlist[j].edgenext=s;
}
}
邻接表打印函数：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21void DispGraph(AdjMatrix *G)
{
int i;
for (i=0;i<G->n;i++)
{
printf("%d->",i+1);
while(1)
{
if(G->adjlist[i].edgenext==NULL)
{
printf("^");
break;
}
printf("%d->",G->adjlist[i].edgenext->adjvex+1);
//②
G->adjlist[i].edgenext=G->adjlist[i].edgenext->next;
}
printf("\n");
}
}
注：①②处是由于边表的顺序是对应的是顶点表数组的顺序，所以起始数组为G->adjlist[0],但是按照人们的输入习惯，我们从1开始，所以对于每个输入的i，j进行减1处理存储，再对于输出的G->adjlist[i].edgenext->adjvex进行加1处理，保证输入输出的统一性
具体代码实现：
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#include <stdio.h>
#include <stdlib.h>
#define MaxVertices 100
typedef struct node{ //边表
int adjvex;
node* next;
}EdgeNode;
typedef struct{ //顶点表
int vertex;
EdgeNode* edgenext;
}VertexNode;
typedef VertexNode AdjList[MaxVertices];
typedef struct{
AdjList adjlist;
int n,e;
}AdjMatrix;
void CreateGraph(AdjMatrix* G)
{
int i,j,k,w,v;
EdgeNode *s;
printf("输入顶点数和边数（中间以空格分开）：");
scanf("%d%d",&G->n,&G->e);
printf("建立顶点表\n");
for (i=0;i<G->n;i++)
{
//fflush(stdin);
//如果 stream 指向输入流（如 stdin），那么 fflush 函数的行为是不确定的。
//故而使用 fflush(stdin) 是不正确的。
getchar();
printf("请输入第%d个顶点的信息:",i+1);
G->adjlist[i].vertex=getchar();
G->adjlist[i].edgenext=NULL;
}
//前插法
printf("建立边表\n");
for (k=0;k<G->e;k++)
{
printf("输入有连接的顶点序号：");
scanf("%d%d",&i,&j);
i-=1;j-=1;//①
//对于直接相连的进行编入(即对输入“0 1”时，在0对应的边表中编入1)
s=(EdgeNode*)malloc(sizeof(EdgeNode));
s->adjvex=j;//边表赋值
s->next=G->adjlist[i].edgenext;
G->adjlist[i].edgenext=s;
//对于间接相连的进行编入(即对输入“0 1”时，在1对应的边表中编入0)
s=(EdgeNode*)malloc(sizeof(EdgeNode));
s->adjvex=i;
s->next=G->adjlist[j].edgenext;
G->adjlist[j].edgenext=s;
}
}
void DispGraph(AdjMatrix *G)
{
int i;
for (i=0;i<G->n;i++)
{
printf("%d->",i+1);
while(1)
{
if(G->adjlist[i].edgenext==NULL)
{
printf("^");
break;
}
printf("%d->",G->adjlist[i].edgenext->adjvex+1);
//②
G->adjlist[i].edgenext=G->adjlist[i].edgenext->next;
}
printf("\n");
}
}
int main()
{
AdjMatrix* G= (AdjMatrix*)malloc(sizeof(AdjMatrix));
CreateGraph(G);
DispGraph(G);
}