2023年12月1日发(作者：魅蓝5s)

图的邻接表表⽰法（C语⾔）

邻接表

邻接表数据结构类型如下：

#define MaxVertices 100

typedef struct node{ //边表

int adjvex;

node* next;

}EdgeNode;

typedef struct{ //顶点表

对应的，我们得到如下的结构：

void CreateGraph(AdjMatrix* G)

{

int i,j,k,w,v;

EdgeNode *s;

printf("输⼊顶点数和边数（中间以空格分开）：");

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

printf("建⽴顶点表n");

for (i=0;in;i++)

{

//fflush(stdin);

//如果 stream 指向输⼊流（如 stdin），那么 fflush 函数的⾏为是不确定的。

//故⽽使⽤ fflush(stdin) 是不正确的。

getchar();

printf("请输⼊第%d个顶点的信息:",i+1);

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

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

}

//前插法

printf("建⽴边表n");

for (k=0;ke;k++)

{

printf("输⼊有连接的顶点序号：");

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

i-=1;j-=1; //①

//对于直接相连的进⾏编⼊(即对输⼊“0 1”时，在0对应的边表中编⼊1)

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

s->adjvex=j;//边表赋值

s->next=G->adjlist[i].edgenext;

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

//对于间接相连的进⾏编⼊(即对输⼊“0 1”时，在1对应的边表中编⼊0)

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

s->adjvex=i;

具体代码实现：

#include

#include

#define MaxVertices 100

typedef struct node{ //边表

int adjvex;

node* next;

}EdgeNode;

typedef struct{ //顶点表

int vertex;

EdgeNode* edgenext;

}VertexNode;

typedef VertexNode AdjList[MaxVertices];

typedef struct{

AdjList adjlist;

int n,e;

}AdjMatrix;

void CreateGraph(AdjMatrix* G)

{

int i,j,k,w,v;

EdgeNode *s;

printf("输⼊顶点数和边数（中间以空格分开）：");

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

printf("建⽴顶点表n");

for (i=0;in;i++)

{

//fflush(stdin);

//如果 stream 指向输⼊流（如 stdin），那么 fflush 函数的⾏为是不确定的。

//故⽽使⽤ fflush(stdin) 是不正确的。

getchar();

printf("请输⼊第%d个顶点的信息:",i+1);

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

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

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

while(1)

{