#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];//頂點(diǎn)向量
adjmatrixarcs; //鄰接矩陣
int vexnum,arcnum; //圖的當(dāng)前頂點(diǎn)數(shù)和邊數(shù)
// GraphType kind;
}MGraph;
typedef struct ArcNode
{
intadjvex; //鄰接點(diǎn)在頭結(jié)點(diǎn)數(shù)組中的位置(下標(biāo))
struct ArcNode * nextarc;//指向下一個(gè)表結(jié)點(diǎn)
DataType * date;
}ArcNode;
//頂點(diǎn)結(jié)點(diǎn)
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("創(chuàng)建有向圖的鄰接矩陣\n");
printf("請(qǐng)輸入當(dāng)前的頂點(diǎn)數(shù)和弧數(shù)(vexarc): \n");
fflush(stdin); //清空輸入緩沖區(qū)，確保不影響后面的數(shù)據(jù)讀取
scanf("%d %d",&G->vexnum,&G->arcnum);
for(i = 0; i< G->vexnum; i++)
{
printf("請(qǐng)輸入第%d個(gè)頂點(diǎn)(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("請(qǐng)輸入頂點(diǎn)和權(quán)值<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("請(qǐng)輸入當(dāng)前頂點(diǎn)數(shù)和弧數(shù)(vexarc):\n");
fflush(stdin);
scanf("%d %d",&G->vexnum,&G->arcnum);
printf("首先輸入頂點(diǎn):\n");
for(i = 0; i< G->vexnum; i++)
{
printf("請(qǐng)輸入頂點(diǎn)%d,回車輸入下一個(gè)頂點(diǎn)\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("請(qǐng)輸入弧%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");
}
}
//鄰接表轉(zhuǎ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("圖的頂點(diǎn)向量如下:\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);
}
