实训5.3

无向图的邻接表存储方法

源程序：

#include <stdio.h>
#include <stdlib.h>
#define VNUM 100

//顶点的类型
typedef char VerType;
typedef struct arcnode
{
int adjvex; //下一条边的顶点编号
struct arcnode *nextarc; //指向下一条边的指针
int weight; //带权图的权值
}ArcNode;

typedef struct vexnode
{
VerType data; //顶点的数据
ArcNode *firstarc; //指向第一条边的指针
}VNode,AdjList[VNUM];

typedef struct gp
{
AdjList adjlist;
int vexnum,arcnum;//顶点数和边数
}Graph; //以上三个结构体，定义了邻接表的存储结构

//确定顶点位置
int LocateVex(Graph *G,VerType v)
{
int i;
for(i=0;i<(G->vexnum);i++)
{
if(G->adjlist[i].data==v)
return i;
}
}

//创建邻接表
int CreateAdjlist(Graph *G)
{
int i,j,k;
VerType v1,v2;
arcnode *p1,*p2;
printf("输入总顶点数和总边数：");
scanf("%d%d",&G->vexnum,&G->arcnum);
printf("输入各顶点的值：");
fflush(stdin); //回车缓冲
for(i=0;i<G->vexnum;i++)
{
scanf("%c",&G->adjlist[i].data);//输入各顶点的值
G->adjlist[i].firstarc=NULL;//初始化i的第一个邻接点为NULL
}

for(k=0;k<G->arcnum;k++)
{
printf("输入相连的两边:");
fflush(stdin);
scanf("%c %c",&v1,&v2);//输入弧尾和弧头
i=LocateVex(G,v1);
j=LocateVex(G,v2);
p1=(arcnode *)malloc(sizeof(arcnode));
p2=(arcnode *)malloc(sizeof(arcnode));
p1->adjvex=j;
p1->nextarc=G->adjlist[i].firstarc;
G->adjlist[i].firstarc=p1;
p2->adjvex=i;
p2->nextarc=G->adjlist[j].firstarc;
G->adjlist[j].firstarc=p2;
}
return 1;
}

//主函数
int main()
{
int i;
Graph G;
arcnode *p;
CreateAdjlist(&G);
for(i=0;i<G.vexnum;i++)
{
p=G.adjlist[i].firstarc;
printf("%c相连的顶点有：",G.adjlist[i].data);
while(p!=NULL)
{
printf("%c->",G.adjlist[p->adjvex].data);
p=p->nextarc;
}
printf(" ");
}
return 1;
}

 运行结果：