//算法功能：采用邻接表存储结构建立无向图
#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define NULL 0
#define MAX_VERTEX_NUM 20 // 最大顶点数
typedef int Status; //函数的类型，其值是函数结果状态代码
typedef char VertexType;
typedef int VRType;
typedef int InforType;
typedef struct ArcNode
{
int adjvex; //该边所指的顶点的位置
struct ArcNode *nextarc; //指向下一条边的指针
int weight; //边的权
}ArcNode; //表的结点
typedef struct VNode
{
VertexType data; //顶点信息（如数据等）
ArcNode *firstarc; //指向第一条依附该顶点的边的弧指针}VNode, AdjList[MAX_VERTEX_NUM]; //头结点
typedef struct ALGraph
{
AdjList vertices;
int vexnum, arcnum; //图的当前顶点数和弧数
}ALGraph;
//返回顶点v在顶点向量中的位置
int LocateVex(ALGraph G, char v)
{
int i;
for(i = 0; v != G.vertices[i].data && i < G.vexnum; i++)
;
if(i >= G.vexnum)
return -1;
return i;
}
//构造邻接链表
Status CreateUDN(ALGraph &G)
{
int j;
ArcNode *s, *t;
printf("输入无向图顶点数: ");
scanf("%d", &G.vexnum);
printf("输入无向图边数: ");
scanf("%d", &G.arcnum);
getchar();
for(int i = 0; i < G.vexnum; i++)
{
printf("输入第%d个顶点信息:", i+1);
scanf("%c", &G.vertices[i].data); //构造顶点向量
G.vertices[i].firstarc = NULL;
getchar();
}
char v1, v2;
for(int k = 0; k < G.arcnum; k++)
{
printf("输入第%d 条边依附的顶点v1: ", k+1);
scanf("%c", &v1);
getchar();
printf("输入第%d 条边依附的顶点v2: ", k+1);
scanf("%c", &v2);
getchar();
int i = LocateVex(G, v1);
int j = LocateVex(G, v2); //确定v1 , v2在G中的位置
s = (ArcNode*) malloc (sizeof(ArcNode));
t = (ArcNode*) malloc (sizeof(ArcNode));
s->adjvex = j; //该边所指向的顶点的位置为j
s->nextarc = G.vertices[i].firstarc;
G.vertices[i].firstarc =s;
t->adjvex = i; //该边所指向的顶点的位置为j
t->nextarc = G.vertices[j].firstarc;
G.vertices[j].firstarc =t;
}
return OK;
}
Status PrintAdjList(ALGraph &G)
{
ArcNode *p;
printf("%4s%6s%12s\n", "编号", "顶点", "相邻边编号");
for(int i = 0; i < G.vexnum; i++)
{
printf("%4d%6c", i, G.vertices[i].data);
for(p = G.vertices[i].firstarc; p; p = p->nextarc)
printf("%4d", p->adjvex);
printf("\n");
}
return OK;
}
int main()
{
ALGraph G;
CreateUDN(G);
rintAdjList(G);
return 0;
}。