图的邻接表表示法(C语言)

为什么邻接矩阵那么好，我们还不满意呢？

当然是因为空间问题啦~！这时我们自然就会想起学过的链表了。

顶点依然还是用一维数组储存，但是还需要增加一个指针，一个指向第一个邻接点的指针.邻接点很大可能不为一，那么就可以采用单链表的形式展开.

typedef char VertexType;//顶点数据类型由用户决定
typedef int EdgeType;//权值的储存类型也可由用户决定
typedef struct EdgeNode{
	int adjvex; //储存下标
	EdgeType weight; //权值
	struct EdgeNode *next; //指向下一个邻接点
	}EdgeNode;
typedef struct VertexNode{
	VertexType data;
	EdgeNode *firstedge; //边表的头指针,也就是第一个顶点的指向下一个的邻接点的指针
	}VertexNode,AdjList[MAXVEX];
typedef struct {
	AdjList adjList; //创建一个自用的小数组
	int numVerttexes.numEdges; //记录当前的顶点数和边数
	}GraphAdjList;

void CreateALGraph(GraphAdjList *G)
{
	int i, j, k;
	EdgeNode *e;//用来做工作指针
	printf("请输入顶点数和边数(用空格隔开):");
	scanf("%d %d",&G->numVertexes,G->numEdges);
	puts("接下里请输入所有顶点数据:");
	for(i=0; inumVertexes; ++i)
	{
		printf("第%d个:",i+1);
		fflush(stdin);//防止回车造成影响
		scanf("%c",G->adjList[i].data);
		G->adjList[i].firstedge=NULL;//头指针置空
		printf("n");//更加美观
	}
	for(k=0; knumEdges; ++k)//开始建立边表关系
	{
		printf("请输入(Vi,Vj)的顶点序列:n");
		scanf("%d %d",&i,&j);//分别对应尾下标和头下标
		e=(EdgeNode *)malloc(sizeof(EdgeNode));//为e申请动态空间
		
		//建立采用以下的代码
		e->adjvex=i;
		e->next=G->adjList[j].firstedge;
		G->adjList[j].firstedge=e;
	}
}