图的邻接表存储 c实现

图的邻接表存储 c实2011-10-07
10:34 4047人阅读 评论(2) 收藏 举报

存储cstruct数据结构null编程

用到的数据结构是

一个是顶点表，包括顶点和指向下一个邻接点的指针

一个是边表， 数据结构跟顶点不同，存储的是顶点的序号，和指向下一个的指针

刚开始的时候把顶点表初始化，指针指向null。然后边表插入进来，是插入到前一个，也就是直接插入到firstedge指向的下一个，而后面的后移

[cpp] view
plaincopyprint?

1. #define  MaxVertexNum 100  
2.   
3. typedef char VertexType;  
4. typedef struct node   //边表节点  
5. {  
6.    int adjvex;  
7.    node* next;  
8. }EdgeNode;  
9.   
10. typedef struct     //顶点表节点  
11. {  
12.    VertexType vertex;  
13.    EdgeNode* firstedge;  
14. }VertexNode;  
15.   
16. typedef VertexNode AdjList[MaxVertexNum];  
17.   
18. typedef struct   
19. {   
20.     AdjList adjlist;  
21.     int n,e;  
22.   
23. }ALGraph;  

以下建立的是无向图的邻接表，有向图的更简单了

[cpp] view
plaincopyprint?

1. #include <stdio.h>  
2. #include <stdlib.h>  
3.   
4. #define  MaxVertexNum 100  
5.   
6. typedef char VertexType;  
7. typedef struct node   //边表节点  
8. {  
9.    int adjvex;  
10.    node* next;  
11. }EdgeNode;  
12.   
13. typedef struct     //顶点表节点  
14. {  
15.    VertexType vertex;  
16.    EdgeNode* firstedge;  
17. }VertexNode;  
18.   
19. typedef VertexNode AdjList[MaxVertexNum];  
20.   
21. typedef struct   
22. {   
23.     AdjList adjlist;  
24.     int n,e;  
25.   
26. }ALGraph;  
27.   
28. void create(ALGraph*);  
29.   
30. void main()  
31. {  
32.    ALGraph* G= (ALGraph*)malloc(sizeof(ALGraph));  
33.    create(G);  
34.    for (int i=0;i< G->n;i++)  
35.    {  
36.        printf("%d->",i);  
37.        while(G->adjlist[i].firstedge!=NULL)  
38.        {  
39.             printf("%d->",G->adjlist[i].firstedge->adjvex);  
40.             G->adjlist[i].firstedge=G->adjlist[i].firstedge->next;  
41.   
42.        }  
43.        printf("\n");  
44.    }  
45. }  
46. void create(ALGraph* G)  
47. {  
48.     int i,j,k,w,v;  
49.     EdgeNode *s;  
50.     printf("读入顶点数和边数");  
51.     scanf("%d,%d",&G->n,&G->e);  
52.   
53.     
54.    for (i=0;i<G->n;i++)  
55.    {  
56.        fflush(stdin);  
57.        printf("建立顶点表");  
58.        G->adjlist[i].vertex=getchar();  
59.        G->adjlist[i].firstedge=NULL;  
60.    }  
61.    printf("建立边表\n");  
62.    for (k=0;k<G->e;k++)  
63.    {  
64.        printf("读入(vi-vj)的顶点对序号");  
65.        scanf("%d,%d",&i,&j);  
66.        s=(EdgeNode*)malloc(sizeof(EdgeNode));  
67.        s->adjvex=j;  
68.        s->next=G->adjlist[i].firstedge;  //插入表头  
69.        G->adjlist[i].firstedge=s;  
70.        s=(EdgeNode*)malloc(sizeof(EdgeNode));  
71.        s->adjvex=i;  
72.        s->next=G->adjlist[j].firstedge;  
73.        G->adjlist[j].firstedge=s;  
74.   
75.    }  
76. }  

结果

自己也编程试试吧！

接下来图的遍历，深度优先遍历和广度优先遍历