数据结构-图-邻接表的创建

话不多说直接上代码

#include "pch.h"
#include <iostream>
#define MAX_VERTEX_NUM 20
typedef enum
{
	DG,DN,UDG,UDN
} GraphKind; // 图的类别
typedef char VertexType[4];
typedef struct ArcNode //边表结点
{
	int Adjvex;//弧指向的顶点
	struct ArcNode * nextarc;//指向下一条弧的指针
}ArcNode;

typedef struct VNode 
{
	VertexType data;//顶点信息
	ArcNode * firstarc;//指向依附于该顶点的第一个弧结点
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct
{
	int vexnum, arcnum;//图的当前顶点数目和弧数
	AdjList vertices;//顶点向量
	int kind;
} ALGraph;


int LocateVertex(ALGraph G, VertexType v)
//定位顶点的位置
{
	int i, j;
	for (i = 0; i < G.vexnum; i++)//遍历存储顶点的向量
	{
		if (strcmp(G.vertices[i].data, v) == 0)
			return i;
	}
}



void CreateALGraph(ALGraph *G)
/*创建邻解表*/
{
	G->kind = UDG;
	int i,k,j;
	VertexType v1, v2;
	ArcNode *NewNode, *FirstNode;
	printf("请输入顶点和弧的数目(以逗号隔开）：\n");
	scanf_s("%d,%d", &(G->vexnum), &(G->arcnum));
	printf("请输入顶点的值：\n");
	for (i = 0; i < G->vexnum; i++)
	{
		scanf_s("%s", &(G->vertices[i].data), sizeof(G->vertices[0].data));
		G->vertices[i].firstarc = NULL;//初始化
	}
	
	printf("输入所有的边：（以空格隔开）\n");
	for (k = 0; k < G->arcnum; k++)
	{
		scanf_s("%s %s", &v1,sizeof(v1), &v2,sizeof(v2));
		i = LocateVertex((*G), v1);
		j = LocateVertex((*G), v2);
		if (!(NewNode = (ArcNode*)malloc(sizeof(ArcNode))))//为弧申请一块内存
			exit(-1);
		NewNode->Adjvex = j;//弧指向的顶点下标
		FirstNode = G->vertices[i].firstarc;
		G->vertices[i].firstarc = NewNode;
		NewNode->nextarc = FirstNode;
		
		/*若为无向图，还需要以入边j为出边建立邻接表*/
		if (!(NewNode = (ArcNode*)malloc(sizeof(ArcNode))))//为弧申请一块内存
			exit(-1);
		NewNode->Adjvex = i;
		FirstNode = G->vertices[j].firstarc;
		G->vertices[j].firstarc = NewNode;
		NewNode->nextarc = FirstNode;

	}

}

void DisplayGraph(ALGraph G)
/*显示邻接表*/
{
	int i;
	ArcNode *p;

	printf("输出无向图%d个顶点：\n", G.vexnum);
	for (i = 0; i < G.vexnum; i++)
	{
		printf("%s ", G.vertices[i].data);

	}
	printf("输出无向图的%d条边", G.arcnum);
	for (i = 0; i < G.vexnum; i++)
	{
		p = G.vertices[i].firstarc;
		while (p)
		{
			printf("%s--->%s ", G.vertices[i].data, G.vertices[p->Adjvex].data);
			p = p->nextarc;
		}
		printf("\n");
	}
}


void DestroyGraph(ALGraph *G)
/*销毁邻接表*/
{
	int i;
	ArcNode *p,*q;
	for (i = 0; i < G->vexnum; i++)
	{
		p = G->vertices[i].firstarc;
		while (p)
		{
			q = p;
			p = p->nextarc;
			free(q);
		}

	}
	G->arcnum = G->vexnum = 0;

}


int main()
{
	ALGraph G;
	printf("创建邻接表:\n");
	CreateALGraph(&G);
	DisplayGraph(G);
	DestroyGraph(&G);

}

程序运行截图：