图的邻接表存储 c实现 （转载）

用到的数据结构是

一个是顶点表，包括顶点和指向下一个邻接点的指针

一个是边表， 数据结构跟顶点不同，存储的是顶点的序号，和指向下一个的指针

刚开始的时候把顶点表初始化，指针指向null。然后边表插入进来，是插入到前一个，也就是直接插入到firstedge指向的下一个，而后面的后移

#define  MaxVertexNum 100

typedef char VertexType;

typedef struct node   //边表节点

{

   int adjvex;

   node* next;

}EdgeNode;

typedef struct     //顶点表节点

{

   VertexType vertex;

   EdgeNode* firstedge;

}VertexNode;

typedef VertexNode AdjList[MaxVertexNum];

typedef struct

{

	AdjList adjlist;

	int n,e;

}ALGraph;

以下建立的是无向图的邻接表，有向图的更简单了

#include <stdio.h>

#include <stdlib.h>

#define  MaxVertexNum 100

typedef char VertexType;

typedef struct node   //边表节点

{

   int adjvex;

   node* next;

}EdgeNode;

typedef struct     //顶点表节点

{

   VertexType vertex;

   EdgeNode* firstedge;

}VertexNode;

typedef VertexNode AdjList[MaxVertexNum];

typedef struct

{

	AdjList adjlist;

	int n,e;

}ALGraph;

void create(ALGraph*);

void main()

{

   ALGraph* G= (ALGraph*)malloc(sizeof(ALGraph));

   create(G);

   for (int i=0;i< G->n;i++)

   {

	   printf("%d->",i);

	   while(G->adjlist[i].firstedge!=NULL)

	   {

			printf("%d->",G->adjlist[i].firstedge->adjvex);

			G->adjlist[i].firstedge=G->adjlist[i].firstedge->next;

	   }

	   printf("\n");

   }

}

void create(ALGraph* G)

{

    int i,j,k,w,v;

    EdgeNode *s;

	printf("读入顶点数和边数");

    scanf("%d,%d",&G->n,&G->e);

   for (i=0;i<G->n;i++)

   {

	   fflush(stdin);

	   printf("建立顶点表");

	   G->adjlist[i].vertex=getchar();

	   G->adjlist[i].firstedge=NULL;

   }

   printf("建立边表\n");

   for (k=0;k<G->e;k++)

   {

	   printf("读入(vi-vj)的顶点对序号");

	   scanf("%d,%d",&i,&j);

	   s=(EdgeNode*)malloc(sizeof(EdgeNode));

	   s->adjvex=j;

	   s->next=G->adjlist[i].firstedge;  //插入表头

	   G->adjlist[i].firstedge=s;

	   s=(EdgeNode*)malloc(sizeof(EdgeNode));

	   s->adjvex=i;

	   s->next=G->adjlist[j].firstedge;

	   G->adjlist[j].firstedge=s;

   }

}