1 #include<stdio.h>
2 #include<stdlib.h>
3 #define OK 1
4 #define NO 0
5 #define TRUE 1
6 #define FALSE 0
7 #define ERROR -1
8 #define MAX_VERTEX_NUM 20
//最大顶点个数
9 typedef
int Status;
10
11 typedef
struct ArcBox
12 {
13 int tailvex,headvex;
//该弧的头结点和尾结点 尾--->头
14 struct ArcBox *hlink,*tlink;
//分别指向具有相同弧头和相同弧尾的链域
15
16 }ArcBox;
17
18 typedef
char VertexType_OL;
//有向图的顶点类型
19 typedef
struct VexNode
20 {
21 VertexType_OL data;
22 ArcBox *firstin,*firstout;
//指向第一条入弧和出弧
23
24 }VexNode;
25
26 typedef
struct
27 {
28 VexNode xlist[MAX_VERTEX_NUM+
1];
//表头向量
29 int vexnum,arcnum;
30 }OLGraph;
31
32 Status CreateDG_OL(OLGraph *
G);
33
34
35 int LocateVex_AL(OLGraph G,VertexType_OL u);
36
37 void OutputOLGraph(OLGraph G);
38
39 int main(
int argc,
char**
argv)
40 {
41 OLGraph G;
42 printf(
"1\n函数CreateDG_OL等测试..\n");
43 {
44 printf(
"初始化有向图G..\n");
45 CreateDG_OL(&
G);
46 printf(
"\n");
47
48 }
49 printf(
"15\n函数OutputOLGraph 测试..\n");
50 {
51 printf(
"输出有向图的十字链表 G=\n");
52 OutputOLGraph(G);
53 printf(
"\n");
54 }
55
56
57
58
59 return 0;
60 }
61
62 Status CreateDG_OL(OLGraph *
G){
63 int i,j,k;
64 VertexType_OL v1,v2;
65 ArcBox *
p;
66 printf(
"输入顶点数 ");
67 scanf(
"%d",&(G->
vexnum));
68 printf(
"输入弧数 ");
69 scanf(
"%d",&(G->
arcnum));
70 printf(
"输入各个顶点值 ");
71 getchar();
72 for(i=
1;i<=G->vexnum;i++
)
73 {
74 scanf(
"%c",&(G->
xlist[i].data));
75 G->xlist[i].firstin=
NULL;
76 G->xlist[i].firstout=
NULL;
77 }
78
79 printf(
"读取各边，构造十字链表\n");
80 for(k=
1;k<=G->arcnum;k++
)
81 {
82 getchar();
83 printf(
"输入相邻结点（添加弧的信息）");
84 scanf(
"%c%c",&v1,&
v2);
85 i=LocateVex_AL(*G,v1);
//第i个结点的链表相连
86 j=LocateVex_AL(*
G,v2);
87 p=(ArcBox*)
malloc(
sizeof(ArcBox));
88 if(!
p)
89 exit(ERROR);
90 p->tailvex=
i;
91 p->headvex=
j;
92 p->hlink=G->xlist[j].firstin;
//把p插到第一个结点中去
93 G->xlist[j].firstin=
p;
94
95 p->tlink=G->
xlist[i].firstout;
96 G->xlist[i].firstout=
p;
97
98 }
99
100 return OK;
101
102
103
104 }
105
106
107 int LocateVex_AL(OLGraph G,VertexType_OL u)
108 {
109 int i;
110 for(i=
1;i<=G.vexnum;i++
)
111 {
112 if(G.xlist[i].data==
u)
113 return i;
114 }
115 return 0;
116
117 }
118
119 void OutputOLGraph(OLGraph G){
120 int i,j;
121 ArcBox *
p;
122 if(!G.arcnum&&!
G.vexnum)
123 printf(
"空图！！\n");
124 else
125 {
126 for(i=
1;i<=G.vexnum;i++
)
127 {
128 printf(
"%c-> ",G.xlist[i].data);
129 p=
G.xlist[i].firstout;
130 j=
1;
131 while(p)
132 {
133 while(p->headvex!=j)
//已经确定尾部都是i因此找到所有的头部存在的弧就好,另一端弧的head从小到大，因为输入的时候就是从大到小
134 {
135 printf(
" ");
136 j++
;
137 }
138 printf(
"(%c,%c)",G.xlist[p->tailvex].data,G.xlist[p->
headvex].data);
139 p=p->
tlink;
140 j++
;
141
142 }
143 printf(
"\n");
144
145 }
146
147
148
149 }
150
151
152
153 }
转载于:https://www.cnblogs.com/lovecodepql/p/7732691.html
