#include <stdio.h>
#include <malloc.h>
#include <time.h>
#define MAX 100
typedef char DataType;
typedef int VectorRelationType;
typedef char VectorType;
typedef struct arcell
{
VectorRelationType adj;
//DataType * data;
}arcell, adjmatrix[MAX][MAX];
//邻接矩阵定义
typedef struct
{
VectorType vexs[MAX];
//顶点向量
adjmatrix
arcs;
//邻接矩阵
int vexnum,
arcnum; //图的当前顶点数和边数
// GraphType kind;
}MGraph;
typedef struct ArcNode
{
int
adjvex;
//邻接点在头结点数组中的位置(下标)
struct ArcNode * nextarc;
//指向下一个表结点
DataType * date;
}ArcNode;
//顶点结点
typedef struct VNode
{
VectorType vexdata;
ArcNode * firstarc;
}VNode, Adjlist[MAX];
//邻接表类型定义
typedef struct
{
Adjlist vexs;
int vexnum, arcnum;
//GraphType gtype;
}ALGraph;
//打印邻接表
void TraverseG(ALGraph G)
{
ArcNode * p;
int i;
printf("图的邻接表如下:\n");
for(i = 0; i
< G.vexnum; i++)
{
printf("%c ->", G.vexs[i].vexdata);
p = G.vexs[i].firstarc;
while(p)
{
printf("%d ->", p->adjvex);
p = p->nextarc;
}
printf("NULL\n");
}
}
//确定v在邻接矩阵中位置
int Locatevex(ALGraph * G, VectorType v)
{
int i;
for(i = 0; i
< G->vexnum; i++)
if(G->vexs[i].vexdata == v)
return (i);
return -1;
}
int locatevexM(MGraph * G, VectorType v)
{
int i;
for(i = 0; i
< G->vexnum; i++)
if(G->vexs[i] == v)
return (i);
return -1;
}
//建立邻接矩阵
void CreateMGraph(MGraph * G)
{
int i, j, k, w;
VectorType u, v;
printf("创建有向图的邻接矩阵\n");
printf("请输入当前的顶点数和弧数(vex
arc): \n");
fflush(stdin);
//清空输入缓冲区，确保不影响后面的数据读取
scanf("%d %d",
&G->vexnum,
&G->arcnum);
for(i = 0; i
< G->vexnum; i++)
{
printf("请输入第%d个顶点(vertex): \n", i+1);
fflush(stdin);
scanf("%c", &G->vexs[i]);
}
for(i = 0; i
< G->vexnum; i++)
{
for(j = 0; j < G->vexnum; j++)
{
G->arcs[i][j].adj = 0;
}
}
for(k = 0; k
< G->arcnum; k++)
{
printf("请输入顶点和权值<u v w): \n");
fflush(stdin);
scanf("%c %c %d", &u, &v,
&w);
i = locatevexM(G, u);
j = locatevexM(G, v);
G->arcs[i][j].adj = w;
}
}
void CreateALGraph(ALGraph * G)
{
int i, j, k;
ArcNode * s;
char u, v;
printf("请输入当前顶点数和弧数(vex
arc):\n");
fflush(stdin);
scanf("%d %d",
&G->vexnum,
&G->arcnum);
printf("首先输入顶点:\n");
for(i = 0; i
< G->vexnum; i++)
{
printf("请输入顶点%d,回车输入下一个顶点\n", i);
fflush(stdin);
scanf("%c",
&(G->vexs[i].vexdata));
G->vexs[i].firstarc = NULL;
}
printf("接下来输入弧:\n");
for(k = 0; k
< G->arcnum; k++)
{
printf("请输入弧%d, 回车输入下一条弧\n", k);
fflush(stdin);
scanf("%c %c", &u, &v);
i = Locatevex(G, u);
j = Locatevex(G, v);
s = (ArcNode *)malloc(sizeof(ArcNode));
s->adjvex = j;
s->nextarc = G->vexs[i].firstarc;
G->vexs[i].firstarc = s;
}
}
void Print_MGraph(MGraph * G)
{
int i, j;
printf("\n");
printf("邻接矩阵输入如下: \n");
printf("[]");
for(i = 0; i
< G->vexnum; i++)
printf("%c ", G->vexs[i]);
printf("\n");
for(i = 0; i
< G->vexnum; i++)
{
printf("%c ", G->vexs[i]);
for(j = 0; j < G->vexnum; j++)
printf("%d ", G->arcs[i][j].adj);
printf("\n");
}
}
//邻接表转换为邻接矩阵
void list_to_mat(ALGraph * AG, MGraph * MG)
{
int i, j;
ArcNode * p;
MG->vexnum =
AG->vexnum;
for(i = 0; i
< AG->vexnum; i++)
{
for(j = 0; j < AG->vexnum; j++)
{
MG->arcs[i][j].adj = 0;
}
}
for(i = 0; i
< AG->vexnum; i++)
{
MG->vexs[i] =
AG->vexs[i].vexdata;
}
printf("图的顶点向量如下:\n");
for(i = 0; i
< AG->vexnum; i++)
{
printf("%d %c\n", i, MG->vexs[i]);
}
for(i = 0; i
< AG->vexnum; i++)
{
p = AG->vexs[i].firstarc;
while(p != NULL)
{
MG->arcs[i][p->adjvex].adj = 1;
p = p->nextarc;
}
}
}
void main()
{
MGraph
MG;
ALGraph AG;
CreateALGraph(&AG);
TraverseG(AG);
list_to_mat(&AG, &MG);
Print_MGraph(&MG);
CreateMGraph(&MG);
Print_MGraph(&MG);
}
