十字链表(有向图)的抽象数据结构
1 #define MAXVEX 20
2 typedef struct ArcNode
3 {
4 int tailvex;/*该弧尾顶点位置*/
5 int headvex;/*该弧头顶点位置*/
6 struct ArcNode* fristin;/*弧尾相同的弧的链域*/
7 struct ArcNode* fristout;/*弧头相同的弧的链域*/
8 }ArcNode;/*边表*/
9
10 typedef struct VertexNode
11 {
12 char vexdata;
13 ArcNode* tail;/*指向该顶点的第一条出弧*/
14 ArcNode* head;/*指向该顶点的第一条入弧*/
15 }VertexNode;/*顶点表*/
16
17 typedef struct
18 {
19 int vexnum;/*顶点数*/
20 int arcnum;/*弧数*/
21 VertexNode vertex[MAXVEX];/*顶点表组成的数组*/
22 }OrthList;/*十字链表(Orthogonal List)*/
创建十字链表(有向图)
1 void Create(OrthList* G)
2 {
3 int i = 1;
4 int j = 1;
5 int k = 1;
6 char tailvex = '\0';
7 char headvex = '\0';
8 ArcNode* P = NULL;
9 ArcNode* Pre = NULL;
10
11 printf("请输入顶点数和边数(逗号分隔)：");
12 scanf("%d%*c%d", &G->vexnum, &G->arcnum);
13 for (i = 1; i <= G->vexnum; i++)
14 {
15 printf("请输入第%d个顶点：", i);
16 scanf(" %c", &G->vertex[i].vexdata);/*%c均前有一空格用于吸收空白字符*/
17 G->vertex[i].tail = NULL;
18 G->vertex[i].head = NULL;
19 }
20 for (k = 1; k <= G->arcnum; k++)
21 {
22 printf("请输入第%d条边的弧尾和弧头(逗号分隔)：", k);
23 scanf(" %c%*c%c", &tailvex, &headvex);
24 i = LocateVex(G, tailvex);
25 j = LocateVex(G, headvex);
26 /*把弧信息链接到顶点表中*/
27 P = (ArcNode*)calloc(1, sizeof(ArcNode));
28 P->tailvex = i;
29 P->headvex = j;
30 P->fristin = NULL;
31 P->fristout = NULL;
32 /*链接以该顶点为弧头的顶点*/
33 if (G->vertex[i].tail == NULL)
34 {
35 G->vertex[i].tail = P;
36 }
37 else
38 {
39 Pre = G->vertex[i].tail;
40 while (Pre->fristout)
41 {
42 Pre = Pre->fristout;
43 }
44 Pre->fristout = P;
45 }
46 /*链接以该顶点为弧尾的顶点*/
47 if (G->vertex[j].head == NULL)
48 {
49 G->vertex[i].head = P;
50 }
51 else
52 {
53 Pre = G->vertex[j].head;
54 while (Pre->fristin)
55 {
56 Pre = Pre->fristin;
57 }
58 Pre->fristin = P;
59 }
60 }
61 }
View Code
LocateVex 函数
1 int LocateVex(OrthList* G, char vex)
2 {
3 int i = 1;
4 for (i = 1; i <= G->vexnum; i++)
5 {
6 if (G->vertex[i].vexdata == vex)
7 {
8 return i;
9 }
10 }
11 return 0;
12 }
View Code
统计顶点的出度和入度
1 void CountTDID(OrthList* G, char vex, int* td, int* id)
2 {
3 int i = 1;
4 /*初始化*/
5 (*td) = 0;
6 (*id) = 0;
7 ArcNode* P = NULL;
8 for (i = 1; i <= G->vexnum; i++)
9 {
10 if (G->vertex[i].vexdata == vex)
11 {
12 /*统计出度*/
13 P = G->vertex[i].tail;
14 while (P)
15 {
16 (*td)++;
17 P = P->fristout;
18 }
19 /*统计入度*/
20 P = G->vertex[i].head;
21 while (P)
22 {
23 (*id)++;
24 P = P->fristin;
25 }
26 }
27 }/*for循环*/
28 }
View Code
源代码
1 /****************************************************************************
2 * Name: 十字链表(有向图)
3 * Data: 2022.01.20
4 * Author: 吕辉
5 * Description: 十字链表(Orthogonal List)是有向图的另一种链式存储结构，
6 * 可以看成是邻接表和逆邻接表的结合。十字链表结构可以很
7 * 容易找到以某顶点为尾(或头)的弧，因而容易求得顶点的出度
8 * 和入度。
9 ****************************************************************************/
10 #define _CRT_SECURE_NO_WARNINGS
11 #include <stdio.h>
12 #include <stdlib.h>
13
14 #define MAXVEX 20
15 typedef struct ArcNode
16 {
17 int tailvex;/*该弧尾顶点位置*/
18 int headvex;/*该弧头顶点位置*/
19 struct ArcNode* fristin;/*弧尾相同的弧的链域*/
20 struct ArcNode* fristout;/*弧头相同的弧的链域*/
21 }ArcNode;/*边表*/
22
23 typedef struct VertexNode
24 {
25 char vexdata;
26 ArcNode* tail;/*指向该顶点的第一条出弧*/
27 ArcNode* head;/*指向该顶点的第一条入弧*/
28 }VertexNode;/*顶点表*/
29
30 typedef struct
31 {
32 int vexnum;/*顶点数*/
33 int arcnum;/*弧数*/
34 VertexNode vertex[MAXVEX];/*顶点表组成的数组*/
35 }OrthList;/*十字链表(Orthogonal List)*/
36
37 void Create(OrthList* G);
38 int LocateVex(OrthList* G, char vex);
39 void PrintArc(OrthList* G);
40 void CountTDID(OrthList* G, char vex, int* td, int* id);
41
42 int main(void)
43 {
44 int td = 0;/*顶点出度*/
45 int id = 0;/*顶点入度*/
46 char vex = '\0';/*顶点*/
47
48 OrthList G;
49 Create(&G);
50 PrintArc(&G);
51
52 printf("请输入要查询度的顶点：");
53 scanf(" %c", &vex);
54 CountTDID(&G, vex, &td, &id);
55 printf("顶点%c的度为%d，其中出度为%d，入度为%d\n", vex, td + id, td, id);
56
57 system("pause");
58 return 0;
59 }
60 /****************************************
61 * Name: Creat
62 * Call: LocateVex
63 * Called By: main
64 * Parameter: G 十字链表
65 * Description: 以十字链表结构来存储图
66 ****************************************/
67 void Create(OrthList* G)
68 {
69 int i = 1;
70 int j = 1;
71 int k = 1;
72 char tailvex = '\0';
73 char headvex = '\0';
74 ArcNode* P = NULL;
75 ArcNode* Pre = NULL;
76
77 printf("请输入顶点数和边数(逗号分隔)：");
78 scanf("%d%*c%d", &G->vexnum, &G->arcnum);
79 for (i = 1; i <= G->vexnum; i++)
80 {
81 printf("请输入第%d个顶点：", i);
82 scanf(" %c", &G->vertex[i].vexdata);/*%c均前有一空格用于吸收空白字符*/
83 G->vertex[i].tail = NULL;
84 G->vertex[i].head = NULL;
85 }
86 for (k = 1; k <= G->arcnum; k++)
87 {
88 printf("请输入第%d条边的弧尾和弧头(逗号分隔)：", k);
89 scanf(" %c%*c%c", &tailvex, &headvex);
90 i = LocateVex(G, tailvex);
91 j = LocateVex(G, headvex);
92 /*把弧信息链接到顶点表中*/
93 P = (ArcNode*)calloc(1, sizeof(ArcNode));
94 P->tailvex = i;
95 P->headvex = j;
96 P->fristin = NULL;
97 P->fristout = NULL;
98 /*链接以该顶点为弧头的顶点*/
99 if (G->vertex[i].tail == NULL)
100 {
101 G->vertex[i].tail = P;
102 }
103 else
104 {
105 Pre = G->vertex[i].tail;
106 while (Pre->fristout)
107 {
108 Pre = Pre->fristout;
109 }
110 Pre->fristout = P;
111 }
112 /*链接以该顶点为弧尾的顶点*/
113 if (G->vertex[j].head == NULL)
114 {
115 G->vertex[i].head = P;
116 }
117 else
118 {
119 Pre = G->vertex[j].head;
120 while (Pre->fristin)
121 {
122 Pre = Pre->fristin;
123 }
124 Pre->fristin = P;
125 }
126 }
127 }
128 /**************************************************
129 * Name: LocateVex
130 * Called By: Create
131 * Parameter: G 十字链表
132 * vex 顶点
133 * return: 若顶点表中存在vex则返回其在顶点表
134 * 中的位置下标，否则返回0
135 * Description: 查找并返回vex在顶点表中的位置
136 *****************************************************/
137 int LocateVex(OrthList* G, char vex)
138 {
139 int i = 1;
140 for (i = 1; i <= G->vexnum; i++)
141 {
142 if (G->vertex[i].vexdata == vex)
143 {
144 return i;
145 }
146 }
147 return 0;
148 }
149 /****************************************
150 * Name: PrintArc
151 * Called By: main
152 * Parameter: G 十字链表
153 * Description: 打印所有弧信息
154 ****************************************/
155 void PrintArc(OrthList* G)
156 {
157 int i = 1;
158 int j = 1;
159 char tailvex = '\0';
160 char headvex = '\0';
161 ArcNode* P = NULL;
162
163 printf("该有向图的全部弧：\n");
164 for (i = 1; i <= G->vexnum; i++)
165 {
166 P = G->vertex[i].tail;
167 while (P)
168 {
169 tailvex = G->vertex[P->tailvex].vexdata;
170 headvex = G->vertex[P->headvex].vexdata;
171 printf("%c--%c\n", tailvex, headvex);
172 P = P->fristout;
173 }
174 }/*for循环*/
175 free(P);
176 }
177 /************************************************************
178 * Name: CountTDID
179 * Called By: main
180 * Parameter: G 十字链表
181 * vex 顶点
182 * td 顶点的出度
183 * id 顶点的入度
184 * Description: 输入顶点，查找并通过参数传递其出度和入度
185 *************************************************************/
186 void CountTDID(OrthList* G, char vex, int* td, int* id)
187 {
188 int i = 1;
189 /*初始化*/
190 (*td) = 0;
191 (*id) = 0;
192 ArcNode* P = NULL;
193 for (i = 1; i <= G->vexnum; i++)
194 {
195 if (G->vertex[i].vexdata == vex)
196 {
197 /*统计出度*/
198 P = G->vertex[i].tail;
199 while (P)
200 {
201 (*td)++;
202 P = P->fristout;
203 }
204 /*统计入度*/
205 P = G->vertex[i].head;
206 while (P)
207 {
208 (*id)++;
209 P = P->fristin;
210 }
211 }
212 }/*for循环*/
213 }
View Code