有向图的十字链表存储

 1 /**
 2     有向图的十字链表存储
 3 */
 4 #include <stdio.h>
 5 #include <malloc.h>
 6 #include <string.h>
 7 #define N 5
 8 #define MAX 50
 9 typedef struct _ArcBox{
10     int tailvex,headvex;///弧尾弧头顶点位置
11     struct _ArcBox* out,*in;///指向下一个有相同弧头弧尾的结点
12 }ArcNode;
13 typedef struct _VexBox{
14     char data[N];
15     ArcNode* firstin,* firstout;
16 }VexNode;
17 typedef struct _graph{
18     VexNode vex[MAX];
19     int nume,numv;
20 }Graph;
21 
22 int getIndex(Graph G,char s[]){
23     for(int i = 0; i < G.numv; i++){
24         if(strcmp(s,G.vex[i].data) == 0)
25             return i;
26     }
27     return -1;
28 }
29 
30 void create(Graph& G){
31     printf("输入顶点与弧的个数:
");
32     scanf("%d%d",&G.numv,&G.nume);
33     ///初始化并输入顶点信息
34     printf("输入顶点信息:
");
35     for(int i = 0; i < G.numv; i++){
36         G.vex[i].firstin = G.vex[i].firstout = NULL;
37         scanf("%s",G.vex[i].data);
38     }
39     printf("输入弧信息:
");
40     int u,v;
41     char s[N],e[N];
42     for(int i = 0; i < G.nume; i++){
43         ArcNode* p = (ArcNode*)malloc(sizeof(ArcNode));
44         p->in = p->out = NULL;
45         scanf("%s%s",s,e);
46         u = getIndex(G,s);
47         v = getIndex(G,e);
48         p->tailvex = u;
49         p->headvex = v;
50         p->out = G.vex[u].firstout;
51         p->in = G.vex[v].firstin;
52         G.vex[u].firstout = p;
53         G.vex[v].firstin = p;
54     }
55 }
56 
57 void output(Graph G){
58     ArcNode* p;
59     for(int i = 0; i < G.numv; i++){
60         printf("%4s ",G.vex[i].data);
61         printf(" out:");
62         p = G.vex[i].firstout;
63         while(p != NULL){
64 //            printf("%d %d ",p->tailvex,p->headvex);
65             printf("%4s%4s",G.vex[p->tailvex].data,G.vex[p->headvex].data);
66             p = p->out;
67         }
68         printf(" in:");
69         p = G.vex[i].firstin;
70         while(p != NULL){
71 //            printf("%d %d ",p->tailvex,p->headvex);
72             printf("%4s%4s",G.vex[p->tailvex].data,G.vex[p->headvex].data);
73             p = p->in;
74         }
75         printf("
");
76     }
77 }
78 
79 int main(void){
80     Graph G;
81     create(G);
82     output(G);
83     return 0;
84 }