用到的数据结构是
一个是顶点表，包括顶点和指向下一个邻接点的指针
一个是边表， 数据结构跟顶点不同，存储的是顶点的序号，和指向下一个的指针
刚开始的时候把顶点表初始化，指针指向null。然后边表插入进来，是插入到前一个，也就是直接插入到firstedge指向的下一个，而后面的后移
[cpp] view plain copy print ? #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;
以下建立的是无向图的邻接表，有向图的更简单了
[cpp] view plain copy print ? #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; } }结果
