数据结构——图的存储（邻接表）

小半 • 2023年1月4日下午2:18 • 数据结构 • 阅读 96

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

#define MAX_VERTEX_NUM 20
#define MAX 20
const int error=-1;
const int ok=1;

//表节点
typedef struct ArcNode
{
	int adjvex;   //该弧所指向的顶点的位置
	struct ArcNode *nextarc; //指向下一条弧的指针
}ArcNode;

//头结点
typedef struct VNode
{
	char data[MAX];  //顶点信息
	ArcNode *firstarc;  //指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct
{
	AdjList vertices;
	int vexnum,arcnum; //图的当前顶点数和边数
}ALGraph;

//函数原型:
void CreateAL(ALGraph &G);
int LocatVex(ALGraph G,char v[MAX]);
void haha(ALGraph &G,int w,int z);
void show(ALGraph G);

int main()
{
	ALGraph G;
	CreateAL(G);
	return 0;
}

void CreateAL(ALGraph &G)
{
	int i,x,y;
	char v1[MAX],v2[MAX];
	printf("请输入顶点个数:");
	scanf("%d",&G.vexnum);
	printf("请输入连通的边数:");
	scanf("%d",&G.arcnum);
	for(i=0;i<G.vexnum;i++)
	{
		printf("请输入第%d个顶点的名称: ",i+1);
		scanf("%s",&G.vertices[i].data);
		G.vertices[i].firstarc=NULL;
	}
	for(i=0;i<G.arcnum;i++)
	{
		printf("请输入第一个顶点:");
		scanf("%s",&v1);
		x=LocatVex(G,v1);
		printf("请输入第二个顶点:");
		scanf("%s",&v2);
		y=LocatVex(G,v2);
		haha(G,x,y);
		haha(G,y,x);
	}
	show(G);
}

void haha(ALGraph &G,int w,int z)
{
	ArcNode *p;
	p=(ArcNode*)malloc(sizeof(ArcNode));
	p->adjvex=z;
	p->nextarc=G.vertices[w].firstarc;
	G.vertices[w].firstarc=p;
}

int LocatVex(ALGraph G,char v[MAX])
{
	int i;
	for(i=0;i<G.vexnum;i++)
	{
		if(strcmp(G.vertices[i].data,v)==0)
		{
			return i;
		}
	}
	return error;
}

//显示函数
void show(ALGraph G)
{
	int i;
	ArcNode *p;
	for(i=0;i<G.vexnum;i++)
	{
        p=G.vertices[i].firstarc;
		printf("%s : ",G.vertices[i].data);
		while(p!=NULL)
		{
			printf("%d -> ",p->adjvex);
			p=p->nextarc;
		}
		printf("\n");
	}
}

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/69345.html

数据结构——图的存储（邻接表）

相关推荐