算法功能：采用邻接表存储结构建立无向图

.

//算法功能：采用邻接表存储结构建立无向图

#include #include

#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;

1 / 3'.

.

return i; }

//构造邻接链表

Status CreateUDN(ALGraph &G) {

int j;

ArcNode *s, *t;

printf(\输入无向图顶点数: \ scanf(\.vexnum); printf(\输入无向图边数: \ scanf(\.arcnum); getchar();

for(int i = 0; i < G.vexnum; i++) {

printf(\输入第%d个顶点信息:\

scanf(\ //构造顶点向量 G.vertices[i].firstarc = NULL; getchar(); }

char v1, v2;

for(int k = 0; k < G.arcnum; k++) {

printf(\输入第 %d 条边依附的顶点v1: \ scanf(\ getchar();

printf(\输入第 %d 条边依附的顶点v2: \ scanf(\ 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;

2 / 3'.

.

t->adjvex = i; //该边所指向的顶点的位置为j t->nextarc = G.vertices[j].firstarc; G.vertices[j].firstarc =t; }

return OK; }

Status PrintAdjList(ALGraph &G) {

ArcNode *p;

printf(\编号\顶点\相邻边编号\ for(int i = 0; i < G.vexnum; i++) {

printf(\.vertices[i].data);

for(p = G.vertices[i].firstarc; p; p = p->nextarc) printf(\ printf(\ }

return OK; }

int main() {

ALGraph G; CreateUDN(G); rintAdjList(G); return 0; }

3 / 3'.