图——邻接表

图——邻接表

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

实现绿色的有向图

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <corecrt_malloc.h>#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，顶点Bgetchar();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;
}