#include
#include
#include
#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];//顶点向量
adjmatrixarcs; //邻接矩阵
int vexnum,arcnum; //图的当前顶点数和边数
// GraphType kind;
}MGraph;
typedef struct ArcNode
{
intadjvex; //邻接点在头结点数组中的位置(下标)
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("请输入当前的顶点数和弧数(vexarc): \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("请输入顶点和权值 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("请输入当前顶点数和弧数(vexarc):\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);
}
偶看新闻