#include<stdio.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM20
#defineOK1
#defineERROR0
typedef int InfoType;/* 该弧相关信息的指针类型 */
typedef char VertexType;/* 顶点的类型 */
typedef struct ArcNode/* 弧结点的结构 */
{
intadjvex;/* 该弧所指向的顶点的位置 */
struct ArcNode*nextarc;/* 指向下一条弧的指针 */
InfoType*info;/* 该弧相关信息的指针（觉得应该是记录某些备注信息）如权值 */
}ArcNode;
typedef struct VNode/* 顶点结点的结构 */
{
VertexTypedata;/* 顶点信息 */
ArcNode*firstarc;/* 指向第一条依附该顶点的弧的指针 */
}VNode, AdjList[MAX_VERTEX_NUM];
typedef struct/* 图的邻接表结构定义 */
{
AdjListvertices;/* 存放顶点的数组 */
intvexnum, arcnum;/* 图的当前顶点数和弧数 */
intkind;/* 图的种类标志 */
}ALGraph;
int CreateUDG(ALGraph &G)/* 邻接表建立无向图 */
{
int i,s,d;
ArcNode *p, *q;
scanf("%d%d",&G.vexnum,&G.arcnum);/* 输入结点数目和边数 */
getchar();
for(i=1; i<=G.vexnum; i++)/* 输入顶点 */
{
scanf("%c",&G.vertices[i].data);/* 输入顶点 */
getchar();
G.vertices[i].firstarc = NULL;/* 首先初始化为NULL */
}
for(i=1; i<=G.arcnum; i++)
{
scanf("%d%d",&s,&d);/* 输入一条边依附的起点序号和终点序号 */
getchar();
p = (struct ArcNode *)malloc(sizeof(struct ArcNode));
q = (struct ArcNode *)malloc(sizeof(struct ArcNode));
p->adjvex = d; /* 保存该弧所指向的顶点位置 */
q->adjvex = s; /* 保存该弧所指向的顶点位置 */
p->nextarc = G.vertices[s].firstarc;
G.vertices[s].firstarc = p;
q->nextarc = G.vertices[d].firstarc;
G.vertices[d].firstarc = q;
}
return OK;
}
int CreateUDN(ALGraph &G)/* 邻接表建立无向网 */
{
int i,s,d,w;
ArcNode *p, *q;
scanf("%d%d",&G.vexnum,&G.arcnum);/* 输入结点数目和边数 */
getchar();
for(i=1; i<=G.vexnum; i++)/* 输入顶点 */
{
scanf("%c",&G.vertices[i].data);/* 输入顶点 */
getchar();
G.vertices[i].firstarc = NULL;/* 首先初始化为NULL */
}
for(i=1; i<=G.arcnum; i++)
{
scanf("%d%d%d",&s,&d,&w);/* 输入一条边依附的起点序号和终点序号 */
getchar();
p = (struct ArcNode *)malloc(sizeof(struct ArcNode));
q = (struct ArcNode *)malloc(sizeof(struct ArcNode));
p->info = (InfoType *)malloc(sizeof(InfoType));
q->info = (InfoType *)malloc(sizeof(InfoType));
p->adjvex = d; /* 保存该弧所指向的顶点位置 */
q->adjvex = s; /* 保存该弧所指向的顶点位置 */
*(p->info) = w; /* 保存权值到一个结点里 */
*(q->info) = w; /* 保存权值到一个结点里 */
p->nextarc = G.vertices[s].firstarc;
G.vertices[s].firstarc = p;
q->nextarc = G.vertices[d].firstarc;
G.vertices[d].firstarc = q;
}
return OK;
}
int CreateDG(ALGraph &G)/* 邻接表建立有向图 */
{
int i,s,d;
ArcNode *p;
scanf("%d%d",&G.vexnum,&G.arcnum);/* 输入结点数目和边数 */
getchar();
for(i=1; i<=G.vexnum; i++)/* 输入顶点 */
{
scanf("%c",&G.vertices[i].data);/* 输入顶点 */
getchar();
G.vertices[i].firstarc = NULL;/* 首先初始化为NULL */
}
for(i=1; i<=G.arcnum; i++)
{
scanf("%d%d",&s,&d);/* 输入一条边依附的起点序号和终点序号 */
getchar();
p = (struct ArcNode *)malloc(sizeof(struct ArcNode));
p->adjvex = d;/* 保存该弧所指向的终点位置 */
/* 这两句代码相当于单链表的插入操作 */
p->nextarc = G.vertices[s].firstarc;/* 保存顶点所对应的终点位置 */
G.vertices[s].firstarc = p;
}
return OK;
}
int CreateDN(ALGraph &G)/* 邻接表建立有向网 */
{
int i,s,d,w;
ArcNode *p;
scanf("%d%d",&G.vexnum,&G.arcnum);/* 输入结点数目和边数 */
getchar();
for(i=1; i<=G.vexnum; i++)/* 输入顶点 */
{
scanf("%c",&G.vertices[i].data);/* 输入顶点 */
getchar();
G.vertices[i].firstarc = NULL;/* 首先初始化为NULL */
}
for(i=1; i<=G.arcnum; i++)
{
scanf("%d%d%d",&s,&d,&w);/* 输入一条边依附的起点序号和终点序号 */
getchar();
p = (struct ArcNode *)malloc(sizeof(struct ArcNode));
p->adjvex = d;/* 保存该弧所指向的终点位置 */
p->info = (InfoType*)malloc(sizeof(InfoType));
*(p->info) = w;
/* 这两句代码相当于单链表的插入操作 */
p->nextarc = G.vertices[s].firstarc;/* 保存顶点所对应的终点位置 */
G.vertices[s].firstarc = p;
}
return OK;
}
int PrintALGraphUDG(ALGraph *G)/* 打印无向图每个结点的单链表 */
{
int i;
printf("打印无向图/n");
for(i = 1 ; i <= G->vexnum ; i++)
{
printf("%c: ",G->vertices[i].data);
while(G->vertices[i].firstarc->nextarc != NULL)
{
printf("%d ",G->vertices[i].firstarc->adjvex);
G->vertices[i].firstarc = G->vertices[i].firstarc->nextarc;
}
printf("%d/n",G->vertices[i].firstarc->adjvex);
}
return OK;
}
int PrintALGraphUDN(ALGraph *G)/* 打印无向网每个结点的单链表 */
{
int i, j;
printf("打印无向网/n");
for(i = 1 ; i <= G->vexnum ; i++)
{
while(G->vertices[i].firstarc->nextarc)
{
printf("%c --> ",G->vertices[i].data);
j = G->vertices[i].firstarc->adjvex;
printf("%c",G->vertices[j].data);
printf("/tweight: %d/n",*(G->vertices[i].firstarc->info));
G->vertices[i].firstarc = G->vertices[i].firstarc->nextarc;
}
printf("%c --> ",G->vertices[i].data);
j = G->vertices[i].firstarc->adjvex;
printf("%c",G->vertices[j].data);
printf("/tweight: %d/n",*(G->vertices[i].firstarc->info));
printf("------------------------------------------/n");
}
return OK;
}
int PrintALGraphDG(ALGraph *G)/* 打印有向图每个结点的单链表 */
{
int i;
printf("打印有向图/n");
for(i = 1 ; i <= G->vexnum ; i++)
{
printf("%c: ",G->vertices[i].data);
if(G->vertices[i].firstarc == NULL)
{
printf("/n");
continue;
}
while(G->vertices[i].firstarc)
{
printf("%d ",G->vertices[i].firstarc->adjvex);
G->vertices[i].firstarc = G->vertices[i].firstarc->nextarc;
}
printf("/n");
}
return OK;
}
int PrintALGraphDN(ALGraph *G)/* 打印有向网每个结点的单链表 */
{
int i, j;
printf("打印有向网/n");
for(i = 1 ; i <= G->vexnum ; i++)
{
while(G->vertices[i].firstarc)
{
printf("%c --> ",G->vertices[i].data);
j = G->vertices[i].firstarc->adjvex;/* 取得终点的位置 */
printf("%c",G->vertices[j].data);
printf("/tweight = %d/n",*(G->vertices[i].firstarc->info));
G->vertices[i].firstarc = G->vertices[i].firstarc->nextarc;
}
}
return OK;
}
void main()
{
ALGraph G;
//CreateUDG(G);/* 建立无向图 */
//PrintALGraphUDG(&G);/* 打印无向图 */
//CreateDG(G);/* 建立有向图 */
//PrintALGraphDG(&G);/* 打印有向图 */
//CreateUDN(G);/* 建立无向网 */
//PrintALGraphUDN(&G);/* 打印无向网 */
CreateDN(G);/* 建立有向网 */
PrintALGraphDN(&G);/* 打印有向网 */
}
图 的测试数据为：5 4 a b c d e 1 2 1 3 1 5 4 5
网 的测试数据为：5 4 a b c d e 1 2 10 1 3 15 1 5 20 4 5 30
提示：粘贴进控制台按回车运行！
如果觉得《邻接表-建立无向图 无向网 有向图 有向网》对你有帮助，请点赞、收藏，并留下你的观点哦！
