?? bo7-1.cpp
字號:
// bo7-1.cpp 圖的數組(鄰接矩陣)存儲(存儲結構由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 + -