邻接表

@Author: 张海拔

@Update: 2014-01-11

@Link: http://www.cnblogs.com/zhanghaiba/p/3515294.html

  1 /*
  2  *Author: ZhangHaiba
  3  *Date: 2014-1-11
  4  *File: adj_list.c
  5  *
  6  *adjacency list
  7  */
  8 
  9 #include <stdio.h>
 10 #include <stdlib.h>
 11 
 12 typedef struct e_node* link;
 13 
 14 typedef struct e_node {
 15     int adjv;
 16     link next;
 17 }e_node;
 18 
 19 typedef struct v_node {
 20     char name;
 21     link next;
 22 }v_node;
 23 
 24 //public
 25 void init_adj_list(v_node*, int);
 26 void create_adj_list(v_node*, int, int);
 27 void show_adj_list(v_node*, int);
 28 void destory_adj_list(v_node*, int);
 29 //private
 30 static link head_insert_node(link, int);
 31 
 32 v_node list[512];
 33 
 34 int main(void)
 35 {
 36     int n, m;
 37 
 38     scanf("%d%d", &n, &m);
 39     init_adj_list(list, n);
 40     create_adj_list(list, n, m);
 41     show_adj_list(list, n);
 42     destory_adj_list(list, n);
 43     return 0;
 44 }
 45 
 46 void init_adj_list(v_node* a, int n)
 47 {
 48     int i;
 49 
 50     for (i = 0; i < n; ++i)
 51         a[i].next = NULL;
 52 }
 53 
 54 
 55 link head_insert_node(link h, int v)
 56 {
 57     link p = malloc(sizeof (e_node));
 58     p->adjv = v;
 59     link save = h;
 60     h = p;
 61     p->next = save;
 62     return h;
 63 }
 64 
 65 void create_adj_list(v_node* a, int n, int m)
 66 {
 67     int i;
 68 
 69     //input name
 70     for (i = 0; i < n; ++i)
 71         scanf("%s", &a[i].name);
 72 
 73     //input edge info: (x, y)
 74     int x, y;
 75 
 76     for (i = 0; i < m; ++i) {
 77         scanf("%d%d", &x, &y);
 78         a[x].next = head_insert_node(a[x].next, y);
 79         //if it is undirected graph add code as next line
 80         //a[y].next = head_insert_node(a[y].next, x);
 81     }
 82 }
 83 
 84 void show_adj_list(v_node* a, int n)
 85 {
 86     int i;
 87     link p;
 88 
 89     for (i = 0; i < n; ++i) {
 90         printf("%c: %d", a[i].name, i);
 91         for (p = a[i].next; p != NULL; p = p->next)
 92             printf("->%d", p->adjv);
 93         printf("
");
 94     }
 95 }
 96 
 97 void destory_adj_list(v_node* a, int n)
 98 {
 99     int i;
100     link p;
101 
102     for (i = 0; i < n; ++i)
103         for (p = a[i].next; p != NULL; p = p->next)
104             free(p);
105 }

测试用例

输入：

5 6
A B C D E
0 4
1 2
1 0
2 3
2 0
3 4

输出：
A: 0->4
B: 1->0->2
C: 2->0->3
D: 3->4
E: 4

邻接表，其实就是一个由顶点节点(v_node)的数组组成，而每个数组元素会连着一个链表（包括空链表）。

即每个顶点节点需要包含边节点的指针e_node *next，且初始化为空，而边节点(e_node)除了包含next指针指向下一节点，还需包含adjv存储邻接点。

因此，先声明了边节点的指针类型、边节点类型、顶点节点类型。

其次，创建邻接表用到了创建链表中的头插法。

另外，对于无向图有两次插入。不过插入的次序可能还需要结合具体要求，否则上面的代码会出现对不同的数组元素反复进行头插，显得比较乱。

最后注意，由于动态分配使用了堆内存，必须还有destory_adj_list()函数来销毁邻接表。

总结：邻接表的创建核心在于头插法，节点数据结构最好区分为两个：v_node和e_node

#返回上一级