图的存储结构之邻接表

由上篇文章图的存储结构之邻接矩阵中，空间复杂度位n^2，我们能看到，对于顶点个数多，而边数少的图，我们创建邻接矩阵会造成很大的空间浪费，这就需要另外一种存储方式------邻接表。

1. 邻接表的顶点用一维数组存储，这和邻接矩阵是一致 的，并且方便读取和存储，当然你也能用链表来存储。
2. 每个顶点Vi的所有邻接点构成一个线性表，由于邻接点的个数不确定，所以要选择单链表存储。

代码伺候：用到了单链表的首元结点的插入以及单链表的遍历

// 图的存储结构之邻接表
//图是由顶点表和边表以及顶点个数和边数组成的，并且知道顶点表就能索引出表链表，所以一个图变量中只有顶点表和顶点个数以及边数就ok了
//首先定义边表结点，然后定义顶点表结点（包括数据域：顶点的名称呢，指针域存放的是边表结点指针）和顶点表，最后定义一个图。

#include "stdafx.h"
#include "stdio.h"
#include  "malloc.h"
#include "string.h"

#define vexmaxnum 100
#define DEBUG
typedef char vextype;
typedef int edgetype;

typedef struct edgenod {     //定义边表结点
	int adjvex;             //存储邻接顶点在顶点表中的下标
	edgetype weight;
	edgenod *next;
}edgenod;

typedef struct vexnode {    //定义顶点表结点
	vextype data[5];           //数据类型
	edgenod *next;          //存放的是边表结点的指针
}vexnode,vexlist[vexmaxnum];           //定义了结构体数组即是顶点表

typedef struct G {            //定义了一个图的基本组成
	vexlist list;             
	int vexnum, edgenum;      //顶点数和边数
}DGraph;                              

int local_vex(DGraph G, vextype *ch ) {
	int i;
	for ( i = 0; i < G.vexnum; i++)
	{
		if (!strcmp(ch, G.list[i].data))
			return i;
	}
	if (i >= G.vexnum) 
		return -1;
}

int  main()
{
	int i, k,loc1=-1,loc2=-1;
	DGraph Graph;
	printf("请输入图的顶点数和边数(中间用空格隔开)：");
	scanf_s("%d %d",&Graph.vexnum,&Graph.edgenum);
#ifdef DEBUG
	printf("测试打印图的顶点数和边数分别位：%d,%d
",Graph.vexnum, Graph.edgenum);
#endif // DEBUG
	printf("请输入各个顶点的名字并用空格隔开：");
	for ( i = 0; i < Graph.vexnum; i++)    //
	{
		scanf("%s",Graph.list[i].data); 
		Graph.list[i].next = NULL;
	}
	printf("
");

#ifdef DEBUG
	for (i = 0; i < Graph.vexnum; i++)    //
	{
		printf("测试打印图的顶点：%s
", Graph.list[i].data);
	}	
	printf("
");
#endif // DEBUG

	char ch1[5], ch2[5];
	edgetype weight=0;
	edgenod *e;

	for ( k = 0; k < Graph.edgenum; k++)
	{
	    printf("请输入边的两个顶点(并用空格隔开)：");
		scanf("%s %s",ch1,ch2);
		loc1 = local_vex(Graph,ch1);
		loc2 = local_vex(Graph,ch2);
		if (loc1==-1||loc2==-1)
		{
			printf("您输入顶点不存在，请重新输入两个顶点：");
			k--;
			continue;
		}

		printf("请输入相应的权值：");
		scanf("%d",&weight);

		e = (edgenod *)malloc(sizeof(edgenod));        
		e->adjvex = loc2;
		e->weight = weight;
		e->next = Graph.list[loc1].next;         
		Graph.list[loc1].next = e;

		e = (edgenod *)malloc(sizeof(edgenod));
		e->adjvex = loc1;
		e->weight = weight;
		e->next = Graph.list[loc2].next;
		Graph.list[loc2].next = e;
	}printf("网络初始化完成>>>>>
");

#ifdef DEBUG
	for ( i = 0; i < Graph.vexnum; i++)     //遍历每个结点对应的链表，n个顶点共有n条链表
	{
		printf("第%d个链表%s:	",i+1,Graph.list[i].data);
		edgenod *G = Graph.list[i].next;
		while (G)
		{
			printf("%s,%d	", Graph.list[G->adjvex].data,G->weight);
			G = G->next;
		}
		printf("
");
	}
#endif // DEBUG

	return 0;
}