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