c语言实现数据结构中的图加注释

/*
* 图的邻接表存储结构实现
*/

#include <stdio.h>
#include <stdlib.h>

#define MaxVertexNum 100 // 最大顶点数
#define INFINITY 65535 // 无穷大

typedef int Vertex; // 顶点下标
typedef int WeightType; // 权重类型
typedef char DataType; // 数据类型

/* 边的定义 */
typedef struct ENode *PtrToENode;
struct ENode {
Vertex V1, V2; // 有向边<V1, V2>
WeightType Weight; // 权重
};
typedef PtrToENode Edge;

/* 邻接点的定义 */
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode {
Vertex AdjV; // 邻接点下标
WeightType Weight; // 权重
PtrToAdjVNode Next; // 指向下一个邻接点的指针
};

/* 顶点表头节点的定义 */
typedef struct Vnode {
PtrToAdjVNode FirstEdge; // 指向第一个邻接点的指针
DataType Data; // 存储节点数据
} AdjList[MaxVertexNum];

/* 图的定义 */
typedef struct GNode *PtrToGNode;
struct GNode {
int Nv; // 顶点数
int Ne; // 边数
AdjList G; // 邻接表
};
typedef PtrToGNode LGraph;

/* 初始化图 */
LGraph CreateGraph(int VertexNum) {
Vertex V;
LGraph Graph;

Graph = (LGraph) malloc(sizeof(struct GNode));
Graph->Nv = VertexNum;
Graph->Ne = 0;

// 初始化邻接表头节点
for (V = 0; V < Graph->Nv; V++) {
Graph->G[V].FirstEdge = NULL;
}

return Graph;
}

/* 插入边 */
void InsertEdge(LGraph Graph, Edge E) {
PtrToAdjVNode NewNode;

// 插入边<V1, V2>
NewNode = (PtrToAdjVNode) malloc(sizeof(struct AdjVNode));
NewNode->AdjV = E->V2;
NewNode->Weight = E->Weight;

// 将V2插入V1的表头节点的邻接表中
NewNode->Next = Graph->G[E->V1].FirstEdge;
Graph->G[E->V1].FirstEdge = NewNode;

// 若为无向图，还需插入边<V2, V1>
NewNode = (PtrToAdjVNode) malloc(sizeof(struct AdjVNode));
NewNode->AdjV = E->V1;
NewNode->Weight = E->Weight;
NewNode->Next = Graph->G[E->V2].FirstEdge;
Graph->G[E->V2].FirstEdge = NewNode;
}

/* 构建图 */
LGraph BuildGraph() {
LGraph Graph;
Edge E;
Vertex V;
int Nv, i;

printf("请输入顶点数:");
scanf("%d", &Nv);
Graph = CreateGraph(Nv);

printf("请输入边数:");
scanf("%d", &(Graph->Ne));
if (Graph->Ne != 0) {
E = (Edge) malloc(sizeof(struct ENode));
printf("请输入边<V1, V2>的权重:\n");
for (i = 0; i < Graph->Ne; i++) {
scanf("%d %d %d", &E->V1, &E->V2, &E->Weight);
InsertEdge(Graph, E);
}
}

// 如果顶点有数据的话，读入数据
for (V = 0; V < Graph->Nv; V++) {
scanf(" %c", &(Graph->G[V].Data));
}

return Graph;
}

/* 打印图 */
void PrintGraph(LGraph Graph) {
Vertex V;
PtrToAdjVNode W;

for (V = 0; V < Graph->Nv; V++) {
printf("%c: ", Graph->G[V].Data);
W = Graph->G[V].FirstEdge;
while (W != NULL) {
printf("%c(%d) ", Graph->G[W->AdjV].Data, W->Weight);
W = W->Next;
}
printf("\n");
}
}

int main() {
LGraph G = BuildGraph();
PrintGraph(G);

return 0;
}