图——邻接表

图的邻接表表示法（有向图）

实现绿色的有向图

#define _CRT_SECURE_NO_WARNINGS 1
#include 
#include 

#define Max 100//顶点数量最大值

typedef struct ArcNode {//边信息
	int VNode_index;//顶点下标
	ArcNode* next;//下一条边
	int WeightValue;//边权值
}ArcNode;
typedef struct VNode {//顶点信息
	char name;//顶点名称
	ArcNode* next = NULL;//指向该顶点的第一条边
}VNode,AdjList[Max];
typedef struct ALGraph {//图信息
	AdjList vertices[Max];//顶点表
	int vexnum;//顶点数目
	int arcnum;//边数
}ALGraph;

void init(ALGraph* graph) {//初始化
	for (int i = 0; i < Max; i++){
		graph->vertices[i]->next = NULL;
	}
}
int find(ALGraph* graph,char target) {//查找顶点下表
	for (int i = 0; i < graph->vexnum; i++) {
		if (graph->vertices[i]->name == target) {
			return i;
		}
	}
	return -1;
}

ALGraph* creatALGraph(ALGraph* graph) {//创建表
	int weightValue;//边权值
	printf("请输入顶点个数\n");
	scanf_s("%d", &graph->vexnum);
	printf("请依次输入顶点\n");
	for (int i = 0; i <graph->vexnum; i++){//输入边信息
		getchar();//处理缓冲区回车键
		scanf_s("%c", &graph->vertices[i]->name);
	}
	printf("请输入边条数");
	scanf_s("%d", &(graph->arcnum));
	printf("请输入边信息 - “顶点A 顶点B 权值” \n");
	for (int i = 0; i < graph->arcnum; i++){//存储图结构
		//输入表信息
		char strA = NULL, strB = NULL;//顶点A，顶点B
		getchar();
		scanf("%c %c %d", &strA,&strB,&weightValue);
		int indexA = find(graph, strA);
		int indexB = find(graph, strB);
		//信息填入边节点
		ArcNode* arcNodeAB = (ArcNode*)malloc(sizeof(ArcNode));
		(arcNodeAB->VNode_index) = indexB;
		arcNodeAB->WeightValue = weightValue;
		//和A节点连接（头插法）
		ArcNode* step = graph->vertices[indexA]->next;
		graph->vertices[indexA]->next = arcNodeAB;
		(graph->vertices[indexA])->next->next = step;
	}
	return graph;
}

void show(ALGraph* graph) {//打印图新信息
	printf("图的信息如下  “节点 --（权值）相连节点--”\n");
	for (int i = 0; i < graph->vexnum; i++) {
		printf("顶点%c", graph->vertices[i]->name);
		ArcNode* p = graph->vertices[i]->next;
		while (p!=NULL){
			printf("--%c(%d)",
				graph->vertices[p->VNode_index]->name,
				p->WeightValue);
			p = p->next;
		}
		printf("\n");
	}
}

int main() {

	ALGraph* graph = (ALGraph*)malloc(sizeof(ALGraph));
	//创建表
	init(graph);
	graph = creatALGraph(graph);
	show(graph);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90