?? bo7-1.c
字號:
/* bo7-1.c 圖的數組(鄰接矩陣)存儲(存儲結構由c7-1.h定義)的基本操作(20個) */
int LocateVex(MGraph G,VertexType u)
{ /* 初始條件:圖G存在,u和G中頂點有相同特征 */
/* 操作結果:若G中存在頂點u,則返回該頂點在圖中位置;否則返回-1 */
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vexs[i])==0)
return i;
return -1;
}
Status CreateFAG(MGraph *G)
{ /* 采用數組(鄰接矩陣)表示法,由文件構造沒有相關信息的無向圖G */
int i,j,k;
char filename[13];
VertexType va,vb;
FILE *graphlist;
printf("請輸入數據文件名(f7-1.dat)：");
scanf("%s",filename);
graphlist=fopen(filename,"r");
fscanf(graphlist,"%d",&(*G).vexnum);
fscanf(graphlist,"%d",&(*G).arcnum);
for(i=0;i<(*G).vexnum;++i) /* 構造頂點向量 */
fscanf(graphlist,"%s",(*G).vexs[i]);
for(i=0;i<(*G).vexnum;++i) /* 初始化鄰接矩陣 */
for(j=0;j<(*G).vexnum;++j)
{
(*G).arcs[i][j].adj=0; /* 圖 */
(*G).arcs[i][j].info=NULL; /* 沒有相關信息 */
}
for(k=0;k<(*G).arcnum;++k)
{
fscanf(graphlist,"%s%s",va,vb);
i=LocateVex(*G,va);
j=LocateVex(*G,vb);
(*G).arcs[i][j].adj=(*G).arcs[j][i].adj=1; /* 無向圖 */
}
fclose(graphlist);
(*G).kind=AG;
return OK;
}
Status CreateDG(MGraph *G)
{ /* 采用數組(鄰接矩陣)表示法,構造有向圖G */
int i,j,k,l,IncInfo;
char s[MAX_INFO],*info;
VertexType va,vb;
printf("請輸入有向圖G的頂點數,弧數,弧是否含其它信息(是:1,否:0): ");
scanf("%d,%d,%d",&(*G).vexnum,&(*G).arcnum,&IncInfo);
printf("請輸入%d個頂點的值(<%d個字符):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i) /* 構造頂點向量 */
scanf("%s",(*G).vexs[i]);
for(i=0;i<(*G).vexnum;++i) /* 初始化鄰接矩陣 */
for(j=0;j<(*G).vexnum;++j)
{
(*G).arcs[i][j].adj=0; /* 圖 */
(*G).arcs[i][j].info=NULL;
}
printf("請輸入%d條弧的弧尾 弧頭(以空格作為間隔): \n",(*G).arcnum);
for(k=0;k<(*G).arcnum;++k)
{
scanf("%s%s%*c",va,vb); /* %*c吃掉回車符 */
i=LocateVex(*G,va);
j=LocateVex(*G,vb);
(*G).arcs[i][j].adj=1; /* 有向圖 */
if(IncInfo)
{
printf("請輸入該弧的相關信息(<%d個字符): ",MAX_INFO);
gets(s);
l=strlen(s);
if(l)
{
info=(char*)malloc((l+1)*sizeof(char));
strcpy(info,s);
(*G).arcs[i][j].info=info; /* 有向 */
}
}
}
(*G).kind=DG;
return OK;
}
Status CreateDN(MGraph *G)
{ /* 采用數組(鄰接矩陣)表示法,構造有向網G */
int i,j,k,w,IncInfo;
char s[MAX_INFO],*info;
VertexType va,vb;
printf("請輸入有向網G的頂點數,弧數,弧是否含其它信息(是:1,否:0): ");
scanf("%d,%d,%d",&(*G).vexnum,&(*G).arcnum,&IncInfo);
printf("請輸入%d個頂點的值(<%d個字符):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i) /* 構造頂點向量 */
scanf("%s",(*G).vexs[i]);
for(i=0;i<(*G).vexnum;++i) /* 初始化鄰接矩陣 */
for(j=0;j<(*G).vexnum;++j)
{
(*G).arcs[i][j].adj=INFINITY; /* 網 */
(*G).arcs[i][j].info=NULL;
}
printf("請輸入%d條弧的弧尾 弧頭 權值(以空格作為間隔): \n",(*G).arcnum);
for(k=0;k<(*G).arcnum;++k)
{
scanf("%s%s%d%*c",va,vb,&w); /* %*c吃掉回車符 */
i=LocateVex(*G,va);
j=LocateVex(*G,vb);
(*G).arcs[i][j].adj=w; /* 有向網 */
if(IncInfo)
{
printf("請輸入該弧的相關信息(<%d個字符): ",MAX_INFO);
gets(s);
w=strlen(s);
if(w)
{
info=(char*)malloc((w+1)*sizeof(char));
strcpy(info,s);
(*G).arcs[i][j].info=info; /* 有向 */
}
}
}
(*G).kind=DN;
return OK;
}
Status CreateAG(MGraph *G)
{ /* 采用數組(鄰接矩陣)表示法,構造無向圖G */
int i,j,k,l,IncInfo;
char s[MAX_INFO],*info;
VertexType va,vb;
printf("請輸入無向圖G的頂點數,邊數,邊是否含其它信息(是:1,否:0): ");
scanf("%d,%d,%d",&(*G).vexnum,&(*G).arcnum,&IncInfo);
printf("請輸入%d個頂點的值(<%d個字符):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i) /* 構造頂點向量 */
scanf("%s",(*G).vexs[i]);
for(i=0;i<(*G).vexnum;++i) /* 初始化鄰接矩陣 */
for(j=0;j<(*G).vexnum;++j)
{
(*G).arcs[i][j].adj=0; /* 圖 */
(*G).arcs[i][j].info=NULL;
}
printf("請輸入%d條邊的頂點1 頂點2(以空格作為間隔): \n",(*G).arcnum);
for(k=0;k<(*G).arcnum;++k)
{
scanf("%s%s%*c",va,vb); /* %*c吃掉回車符 */
i=LocateVex(*G,va);
j=LocateVex(*G,vb);
(*G).arcs[i][j].adj=(*G).arcs[j][i].adj=1; /* 無向圖 */
if(IncInfo)
{
printf("請輸入該邊的相關信息(<%d個字符): ",MAX_INFO);
gets(s);
l=strlen(s);
if(l)
{
info=(char*)malloc((l+1)*sizeof(char));
strcpy(info,s);
(*G).arcs[i][j].info=(*G).arcs[j][i].info=info; /* 無向 */
}
}
}
(*G).kind=AG;
return OK;
}
Status CreateAN(MGraph *G)
{ /* 采用數組(鄰接矩陣)表示法,構造無向網G。算法7.2 */
int i,j,k,w,IncInfo;
char s[MAX_INFO],*info;
VertexType va,vb;
printf("請輸入無向網G的頂點數,邊數,邊是否含其它信息(是:1,否:0): ");
scanf("%d,%d,%d",&(*G).vexnum,&(*G).arcnum,&IncInfo);
printf("請輸入%d個頂點的值(<%d個字符):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i) /* 構造頂點向量 */
scanf("%s",(*G).vexs[i]);
for(i=0;i<(*G).vexnum;++i) /* 初始化鄰接矩陣 */
for(j=0;j<(*G).vexnum;++j)
{
(*G).arcs[i][j].adj=INFINITY; /* 網 */
(*G).arcs[i][j].info=NULL;
}
printf("請輸入%d條邊的頂點1 頂點2 權值(以空格作為間隔): \n",(*G).arcnum);
for(k=0;k<(*G).arcnum;++k)
{
scanf("%s%s%d%*c",va,vb,&w); /* %*c吃掉回車符 */
i=LocateVex(*G,va);
j=LocateVex(*G,vb);
(*G).arcs[i][j].adj=(*G).arcs[j][i].adj=w; /* 無向 */
if(IncInfo)
{
printf("請輸入該邊的相關信息(<%d個字符): ",MAX_INFO);
gets(s);
w=strlen(s);
if(w)
{
info=(char*)malloc((w+1)*sizeof(char));
strcpy(info,s);
(*G).arcs[i][j].info=(*G).arcs[j][i].info=info; /* 無向 */
}
}
}
(*G).kind=AN;
return OK;
}
Status CreateGraph(MGraph *G)
{ /* 采用數組(鄰接矩陣)表示法,構造圖G。算法7.1 */
printf("請輸入圖G的類型(有向圖:0,有向網:1,無向圖:2,無向網:3): ");
scanf("%d",&(*G).kind);
switch((*G).kind)
{
case DG: return CreateDG(G); /* 構造有向圖 */
case DN: return CreateDN(G); /* 構造有向網 */
case AG: return CreateAG(G); /* 構造無向圖 */
case AN: return CreateAN(G); /* 構造無向網 */
default: return ERROR;
}
}
void DestroyGraph(MGraph *G)
{ /* 初始條件: 圖G存在。操作結果: 銷毀圖G */
int i,j;
if((*G).kind<2) /* 有向 */
for(i=0;i<(*G).vexnum;i++) /* 釋放弧的相關信息(如果有的話) */
{
for(j=0;j<(*G).vexnum;j++)
if((*G).arcs[i][j].adj==1&&(*G).kind==0||(*G).arcs[i][j].adj!=INFINITY&&(*G).kind==1) /* 有向圖的弧||有向網的弧 */
if((*G).arcs[i][j].info) /* 有相關信息 */
{
free((*G).arcs[i][j].info);
(*G).arcs[i][j].info=NULL;
}
}
else /* 無向 */
for(i=0;i<(*G).vexnum;i++) /* 釋放邊的相關信息(如果有的話) */
for(j=i+1;j<(*G).vexnum;j++)
if((*G).arcs[i][j].adj==1&&(*G).kind==2||(*G).arcs[i][j].adj!=INFINITY&&(*G).kind==3) /* 無向圖的邊||無向網的邊 */
if((*G).arcs[i][j].info) /* 有相關信息 */
{
free((*G).arcs[i][j].info);
(*G).arcs[i][j].info=(*G).arcs[j][i].info=NULL;
}
(*G).vexnum=0;
(*G).arcnum=0;
}
VertexType* GetVex(MGraph G,int v)
{ /* 初始條件: 圖G存在，v是G中某個頂點的序號。操作結果: 返回v的值 */
if(v>=G.vexnum||v<0)
exit(ERROR);
return &G.vexs[v];
}
Status PutVex(MGraph *G,VertexType v,VertexType value)
{ /* 初始條件: 圖G存在，v是G中某個頂點。操作結果: 對v賦新值value */
int k;
k=LocateVex(*G,v); /* k為頂點v在圖G中的序號 */
if(k<0)
return ERROR;
strcpy((*G).vexs[k],value);
return OK;
}
int FirstAdjVex(MGraph G,VertexType v)
{ /* 初始條件: 圖G存在,v是G中某個頂點 */
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -