建立图邻接.cpp

这里面包括数据结构多数的算法

#include <stdio.h>
#include <stdlib.h>
#define MaxVertexNum 100			//最大顶点数，应由用户定义
typedef char VertexType;			//顶点类型应由用户定义

typedef struct node {				//边表结点
	int adjvex;						//邻接点域
	struct node *next;				//链域
	//若要表示边上的权，则应增加一个数据域
}EdgeNode;
typedef struct vnode {				//顶点表结点
	VertexType vertex;				//顶点域
	EdgeNode *firstedge;			//边表头指针
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum];
	//AdjList是邻接表类型
typedef struct {
	AdjList adjlist;				//邻接表
	int n,e;						//图中当前顶点数和边数
}ALGraph;
	//对于简单的应用，无须定义此类型，可直接使用AdjList类型

void main()
{
	void CreateALGraph(ALGraph *G);
	void PrintALGraph(ALGraph *G);
	ALGraph G;
	CreateALGraph(&G);
	PrintALGraph(&G);
}

void CreateALGraph(ALGraph *G)
{	//建立无向图的邻接表表示
	int i,j,k;
	EdgeNode *s;
	printf("请输出顶点数和边数：");
	scanf("%d%d",&G->n,&G->e);					//读入顶点数和边数
	printf("请输出顶点信息：");
	for(i=0;i<G->n;i++){						//建立顶点表
		while((G->adjlist[i].vertex=getchar())=='\n');	//读入顶点信息
		G->adjlist[i].firstedge=NULL;			//边表置为空表
	}
	for(k=0;k<G->e;k++){						//建立边表
		printf("\n请输出第%d边的起点、终点：",k+1);
		scanf("%d%d",&i,&j);					//读入边(vi,vj)的顶点对序号
		s=(EdgeNode *)malloc(sizeof(EdgeNode));	//生成边表结点
		s->adjvex=j;							//邻接点序号为j
		s->next=G->adjlist[i].firstedge;
		G->adjlist[i].firstedge=s;			//将新结点*s插入顶点vi的边表头部
		s=(EdgeNode *)malloc(sizeof(EdgeNode));
		s->adjvex=i;							//邻接点序号为i
		s->next=G->adjlist[j].firstedge;
		G->adjlist[j].firstedge=s;			//将新结点*s插入顶点vj的边表头部
	}
}

//打印邻接表：
void PrintALGraph(ALGraph *G)
{
	int i;
	EdgeNode *p;
	for(i=0;i<G->n;i++)
	{
		printf("%d %c:\t",i,G->adjlist[i].vertex);
		p=G->adjlist[i].firstedge;
		while(p)
		{
			printf("%d\t",p->adjvex);
			p=p->next;
		}
		printf("\n");
	}
}