aja_list.c

C++的电子教程

//程序实例8_2
//图的邻接表表示
#include<stdio.h>
#include<stdlib.h>
#define Max 50

typedef struct e_node               //定义边结点的数据类型
{	int adjvex;
	int weight;
	struct e_node *next;
}E_node;

typedef struct v_node              //定义顶点结点的数据类型
{	int vertex;
	E_node *link;
}V_node;

V_node head[Max];                  //定义顶点结点的数组

//邻接表的建立
void adjl(V_node head[],int v[][2],int w[],int n,int e,int t)
{
	int i,k,m=0;
	E_node *p;

	for(i=1;i<=n;i++)       //顶点结点初始化
	{	head[i].link=NULL;	//////////////////////////////////
		head[i].vertex=i;   //顶点信息设为顶点编号
	}

	for(k=1;k<=e;k++)
	{
		p=(E_node *)malloc(sizeof(E_node));  //新结点存放w
		p->adjvex=v[m][1];    //终点为w的边结点链到第v个链表
		p->next=head[v[m][0]].link;
		head[v[m][0]].link=p;
		if(t==0)        //无向图
		{	
			p=(E_node *)malloc(sizeof(E_node));  //新结点存放v
			p->adjvex=v[m][0];  //终点为v的边结点链到第w个链表
			p->next=head[v[m][1]].link;
			head[v[m][1]].link=p;
		}
		if(t==2)        //带权有向图
			p->weight=w[m];   //赋权值

		m++;
	}
}

//输出邻接表
void Print(V_node head[],int n,int t)
{	int i;
	E_node *p;
	for(i=1;i<=n;i++)
	{	printf("\nhead[%d]",i);
		if(head[i].link)
		{	p=head[i].link;
			while(p)
			{	printf("->[%d]",p->adjvex);
			    if (t==2)      //带权有向图
					printf("[%d]",p->weight);  //输出权值
				p=p->next;
			}
		}
		printf("\n");
	}
	printf("\n");
}

//主函数
void main()
{
	int n,e,t;//无向图、有向图、带权有向图的t分别为0、1、2
	int d1[][2]={{1,2},{1,3},{1,5},{2,4},{2,6},{3,6},{5,6}};
	int d2[][2]={{1,2},{1,3},{2,4},{3,2},{4,6},{5,1},{6,3},{6,4},{6,5}};
	int d3[][2]={{1,2},{2,3},{2,5},{4,1},{4,3},{5,4}};
	int w[Max],w3[]={10,8,15,5,2,23};


	printf("\n图8.1.1无向图G1的邻接表:\n");
	n=6; e=7; t=0;
	adjl(head, d1, w, n, e, t);
	Print(head,n,t);

	printf("\n图8.1.2有向图G2的邻接表:\n");
	n=6; e=9; t=1;
	adjl(head,d2, w, n, e, t);
	Print(head,n,t);

	printf("\n图8.1.8带权有向图G3的邻接表:\n");
	n=5; e=6; t=2;
	adjl(head,d3, w3, n, e, t);
	Print(head,n,t);
}