?? bo7-1.cpp
字號(hào):
// bo7-1.cpp 圖的鄰接矩陣存儲(chǔ)(存儲(chǔ)結(jié)構(gòu)由c7-1.h定義)的基本操作(17個(gè))，包括算法7.1，7.2
int LocateVex(MGraph G,VertexType u)
{ // 初始條件：圖G存在，u和G中頂點(diǎn)有相同特征(頂點(diǎn)名稱(chēng)相同)
// 操作結(jié)果：若G中存在頂點(diǎn)u，則返回該頂點(diǎn)在圖中位置(序號(hào))；否則返回-1
int i;
for(i=0;i<G.vexnum;++i) // 對(duì)于所有頂點(diǎn)依次查找
if(strcmp(u.name,G.vexs[i].name)==0) // 頂點(diǎn)與給定的u的頂點(diǎn)名稱(chēng)相同
return i; // 返回頂點(diǎn)序號(hào)
return -1; // 圖G中不存在與頂點(diǎn)u有相同名稱(chēng)的頂點(diǎn)
}
void CreateDG(MGraph &G)
{ // 采用數(shù)組(鄰接矩陣)表示法，構(gòu)造有向圖G
int i,j,k,IncInfo; // IncInfo為0則弧不含相關(guān)信息
VertexType v1,v2; // 頂點(diǎn)類(lèi)型
printf("請(qǐng)輸入有向圖G的頂點(diǎn)數(shù),弧數(shù),弧是否含相關(guān)信息(是：1 否：0)：");
scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&IncInfo);
printf("請(qǐng)輸入%d個(gè)頂點(diǎn)的值(名稱(chēng)<%d個(gè)字符)：\n",G.vexnum,MAX_NAME);
for(i=0;i<G.vexnum;++i) // 構(gòu)造頂點(diǎn)向量
Input(G.vexs[i]); // 根據(jù)頂點(diǎn)信息的類(lèi)型，輸入頂點(diǎn)信息，在func7-1.cpp中
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; // 無(wú)相關(guān)信息
}
printf("請(qǐng)輸入%d條弧的弧尾 弧頭：\n",G.arcnum);
for(k=0;k<G.arcnum;++k)
{ scanf("%s%s%*c",v1.name,v2.name); // %*c吃掉回車(chē)符
i=LocateVex(G,v1); // 弧尾的序號(hào)
j=LocateVex(G,v2); // 弧頭的序號(hào)
G.arcs[i][j].adj=1; // 有向圖
if(IncInfo) // 有相關(guān)信息
InputArc(G.arcs[i][j].info);
// 動(dòng)態(tài)生成存儲(chǔ)空間，輸入弧的相關(guān)信息，在func7-2.cpp中
}
G.kind=DG;
}
void CreateDN(MGraph &G)
{ // 采用數(shù)組(鄰接矩陣)表示法，構(gòu)造有向網(wǎng)G
int i,j,k,IncInfo; // IncInfo為0則弧不含相關(guān)信息
VRType w; // 頂點(diǎn)關(guān)系類(lèi)型
VertexType v1,v2; // 頂點(diǎn)類(lèi)型
printf("請(qǐng)輸入有向網(wǎng)G的頂點(diǎn)數(shù),弧數(shù),弧是否含相關(guān)信息(是：1 否：0)：");
scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&IncInfo);
printf("請(qǐng)輸入%d個(gè)頂點(diǎn)的值(名稱(chēng)<%d個(gè)字符)：\n",G.vexnum,MAX_NAME);
for(i=0;i<G.vexnum;++i) // 構(gòu)造頂點(diǎn)向量
Input(G.vexs[i]); // 根據(jù)頂點(diǎn)信息的類(lèi)型，輸入頂點(diǎn)信息，在func7-1.cpp中
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; // 無(wú)相關(guān)信息
}
printf("請(qǐng)輸入%d條弧的弧尾 弧頭 權(quán)值：\n",G.arcnum);
for(k=0;k<G.arcnum;++k)
{ scanf("%s%s%d%*c",v1.name,v2.name,&w); // %*c吃掉回車(chē)符
i=LocateVex(G,v1); // 弧尾的序號(hào)
j=LocateVex(G,v2); // 弧頭的序號(hào)
G.arcs[i][j].adj=w; // 有向網(wǎng)
if(IncInfo) // 有相關(guān)信息
InputArc(G.arcs[i][j].info);
// 動(dòng)態(tài)生成存儲(chǔ)空間，輸入弧的相關(guān)信息，在func7-2.cpp中
}
G.kind=DN;
}
void CreateUDG(MGraph &G)
{ // 采用數(shù)組(鄰接矩陣)表示法，構(gòu)造無(wú)向圖G
int i,j,k,IncInfo; // IncInfo為0則弧不含相關(guān)信息
VertexType v1,v2; // 頂點(diǎn)類(lèi)型
printf("請(qǐng)輸入無(wú)向圖G的頂點(diǎn)數(shù),邊數(shù),邊是否含相關(guān)信息(是：1 否：0)：");
scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&IncInfo);
printf("請(qǐng)輸入%d個(gè)頂點(diǎn)的值(名稱(chēng)<%d個(gè)字符)：\n",G.vexnum,MAX_NAME);
for(i=0;i<G.vexnum;++i) // 構(gòu)造頂點(diǎn)向量
Input(G.vexs[i]); // 根據(jù)頂點(diǎn)信息的類(lèi)型，輸入頂點(diǎn)信息，在func7-1.cpp中
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; // 無(wú)相關(guān)信息
}
printf("請(qǐng)輸入%d條邊的頂點(diǎn)1 頂點(diǎn)2：\n",G.arcnum);
for(k=0;k<G.arcnum;++k)
{ scanf("%s%s%*c",v1.name,v2.name); // %*c吃掉回車(chē)符
i=LocateVex(G,v1); // 頂點(diǎn)1的序號(hào)
j=LocateVex(G,v2); // 頂點(diǎn)2的序號(hào)
G.arcs[i][j].adj=1; // 圖
if(IncInfo) // 有相關(guān)信息
InputArc(G.arcs[i][j].info);
// 動(dòng)態(tài)生成存儲(chǔ)空間，輸入弧的相關(guān)信息，在func7-2.cpp中
G.arcs[j][i]=G.arcs[i][j]; // 無(wú)向，兩個(gè)單元的信息相同
}
G.kind=UDG;
}
void CreateUDN(MGraph &G)
{ // 采用數(shù)組(鄰接矩陣)表示法，構(gòu)造無(wú)向網(wǎng)G。算法7.2
int i,j,k,IncInfo; // IncInfo為0則弧不含相關(guān)信息
VRType w; // 頂點(diǎn)關(guān)系類(lèi)型
VertexType v1,v2; // 頂點(diǎn)類(lèi)型
printf("請(qǐng)輸入無(wú)向網(wǎng)G的頂點(diǎn)數(shù),邊數(shù),邊是否含相關(guān)信息(是：1 否：0)：");
scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&IncInfo);
printf("請(qǐng)輸入%d個(gè)頂點(diǎn)的值(名稱(chēng)<%d個(gè)字符)：\n",G.vexnum,MAX_NAME);
for(i=0;i<G.vexnum;++i) // 構(gòu)造頂點(diǎn)向量
Input(G.vexs[i]); // 根據(jù)頂點(diǎn)信息的類(lèi)型，輸入頂點(diǎn)信息，在func7-1.cpp中
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; // 無(wú)相關(guān)信息
}
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",v1.name,v2.name,&w); // %*c吃掉回車(chē)符
i=LocateVex(G,v1); // 頂點(diǎn)1的序號(hào)
j=LocateVex(G,v2); // 頂點(diǎn)2的序號(hào)
G.arcs[i][j].adj=w; // 網(wǎng)
if(IncInfo) // 有相關(guān)信息
InputArc(G.arcs[i][j].info);
// 動(dòng)態(tài)生成存儲(chǔ)空間，輸入弧的相關(guān)信息，在func7-2.cpp中
G.arcs[j][i]=G.arcs[i][j]; // 無(wú)向，兩個(gè)單元的信息相同
}
G.kind=UDN;
}
void CreateGraph(MGraph &G)
{ // 采用數(shù)組(鄰接矩陣)表示法，構(gòu)造圖G。修改算法7.1
printf("請(qǐng)輸入圖G的類(lèi)型(有向圖：0 有向網(wǎng)：1 無(wú)向圖：2 無(wú)向網(wǎng)：3)：");
scanf("%d",&G.kind);
switch(G.kind) // 根據(jù)圖G的類(lèi)型，調(diào)用不同的構(gòu)造圖的函數(shù)
{ case DG:CreateDG(G); // 構(gòu)造有向圖
break;
case DN:CreateDN(G); // 構(gòu)造有向網(wǎng)
break;
case UDG:CreateUDG(G); // 構(gòu)造無(wú)向圖
break;
case UDN:CreateUDN(G); // 構(gòu)造無(wú)向網(wǎng)
}
}
VertexType GetVex(MGraph G,int v)
{ // 初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)的序號(hào)。操作結(jié)果：返回v的值
if(v>=G.vexnum||v<0) // 圖G中不存在序號(hào)為v的頂點(diǎn)
exit(OVERFLOW);
return G.vexs[v]; // 返回該頂點(diǎn)的信息
}
Status PutVex(MGraph &G,VertexType v,VertexType value)
{ // 初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)。操作結(jié)果：對(duì)v賦新值value
int k=LocateVex(G,v); // k為頂點(diǎn)v在圖G中的序號(hào)
if(k<0) // 不存在頂點(diǎn)v
return ERROR;
G.vexs[k]=value; // 將新值賦給頂點(diǎn)v(其序號(hào)為k)
return OK;
}
int FirstAdjVex(MGraph G,int v)
{ // 初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)的序號(hào)
// 操作結(jié)果：返回v的第1個(gè)鄰接頂點(diǎn)的序號(hào)。若頂點(diǎn)在G中沒(méi)有鄰接頂點(diǎn)，則返回-1
int i;
VRType j=0; // 頂點(diǎn)關(guān)系類(lèi)型，圖
if(G.kind%2) // 網(wǎng)
j=INFINITY;
for(i=0;i<G.vexnum;i++) // 從第1個(gè)頂點(diǎn)開(kāi)始查找
if(G.arcs[v][i].adj!=j) // 是第1個(gè)鄰接頂點(diǎn)
return i; // 返回該鄰接頂點(diǎn)的序號(hào)
return -1; // 沒(méi)有鄰接頂點(diǎn)
}
int NextAdjVex(MGraph G,int v,int w)
{ // 初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)的序號(hào)，w是v的鄰接頂點(diǎn)的序號(hào)
// 操作結(jié)果：返回v的(相對(duì)于w的)下一個(gè)鄰接頂點(diǎn)的序號(hào)，
// 若w是v的最后一個(gè)鄰接頂點(diǎn)，則返回-1
int i;
VRType j=0; // 頂點(diǎn)關(guān)系類(lèi)型，圖
if(G.kind%2) // 網(wǎng)
j=INFINITY;
for(i=w+1;i<G.vexnum;i++) // 從第w+1個(gè)頂點(diǎn)開(kāi)始查找
if(G.arcs[v][i].adj!=j) // 是從w+1開(kāi)始的第1個(gè)鄰接頂點(diǎn)
return i; // 返回該鄰接頂點(diǎn)的序號(hào)
return -1; // 沒(méi)有下一個(gè)鄰接頂點(diǎn)
}
void InsertVex(MGraph &G,VertexType v)
{ // 初始條件：圖G存在，v和圖G中頂點(diǎn)有相同特征
// 操作結(jié)果：在圖G中增添新頂點(diǎn)v(不增添與頂點(diǎn)相關(guān)的弧，留待InsertArc()去做)
int i;
VRType j=0; // 頂點(diǎn)關(guān)系類(lèi)型，圖
if(G.kind%2) // 網(wǎng)
j=INFINITY;
G.vexs[G.vexnum]=v; // 將值v賦給新頂點(diǎn)
for(i=0;i<=G.vexnum;i++) // 對(duì)于新增行、新增列
{ G.arcs[G.vexnum][i].adj=G.arcs[i][G.vexnum].adj=j;
// 初始化新增行、新增列鄰接矩陣的值(無(wú)邊或弧)
G.arcs[G.vexnum][i].info=G.arcs[i][G.vexnum].info=NULL; // 初始化相關(guān)信息指針
}
G.vexnum++; // 圖G的頂點(diǎn)數(shù)加1
}
Status InsertArc(MGraph &G,VertexType v,VertexType w)
{ // 初始條件：圖G存在，v和w是G中兩個(gè)頂點(diǎn)
// 操作結(jié)果：在G中增添弧<v,w>，若G是無(wú)向的，則還增添對(duì)稱(chēng)弧<w,v>
int i,v1,w1;
v1=LocateVex(G,v); // 弧尾頂點(diǎn)v的序號(hào)
w1=LocateVex(G,w); // 弧頭頂點(diǎn)w的序號(hào)
if(v1<0||w1<0) // 不存在頂點(diǎn)v或w
return ERROR;
G.arcnum++; // 弧或邊數(shù)加1
if(G.kind%2) // 網(wǎng)
{ printf("請(qǐng)輸入此弧或邊的權(quán)值：");
scanf("%d",&G.arcs[v1][w1].adj);
}
else // 圖
G.arcs[v1][w1].adj=1;
printf("是否有該弧或邊的相關(guān)信息(0：無(wú) 1：有)：");
scanf("%d%*c",&i);
if(i)
InputArc(G.arcs[v1][w1].info); // 動(dòng)態(tài)生成存儲(chǔ)空間，輸入弧的相關(guān)信息，在func7-2.cpp中
if(G.kind>1) // 無(wú)向
G.arcs[w1][v1]=G.arcs[v1][w1]; // 有同樣的鄰接值，指向同一個(gè)相關(guān)信息
return OK;
}
Status DeleteArc(MGraph &G,VertexType v,VertexType w)
{ // 初始條件：圖G存在，v和w是G中兩個(gè)頂點(diǎn)
// 操作結(jié)果：在G中刪除弧<v,w>，若G是無(wú)向的，則還刪除對(duì)稱(chēng)弧<w,v>
int v1,w1;
VRType j=0; // 頂點(diǎn)關(guān)系類(lèi)型，圖
if(G.kind%2) // 網(wǎng)
j=INFINITY;
v1=LocateVex(G,v); // 弧尾頂點(diǎn)v的序號(hào)
w1=LocateVex(G,w); // 弧頭頂點(diǎn)w的序號(hào)
if(v1<0||w1<0) // 不存在頂點(diǎn)v或w
return ERROR;
if(G.arcs[v1][w1].adj!=j) // 有弧<v,w>
{ G.arcs[v1][w1].adj=j; // 刪除弧<v,w>
if(G.arcs[v1][w1].info) // 有相關(guān)信息
{ free(G.arcs[v1][w1].info); // 釋放相關(guān)信息
G.arcs[v1][w1].info=NULL; // 置相關(guān)信息指針為空
}
if(G.kind>=2) // 無(wú)向，刪除對(duì)稱(chēng)弧<w,v>
G.arcs[w1][v1]=G.arcs[v1][w1]; // 刪除弧，置相關(guān)信息指針為空
G.arcnum--; // 弧數(shù)-1
}
return OK;
}
Status DeleteVex(MGraph &G,VertexType v)
{ // 初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)。操作結(jié)果：刪除G中頂點(diǎn)v及其相關(guān)的弧
int i,j,k;
k=LocateVex(G,v); // k為待刪除頂點(diǎn)v的序號(hào)
if(k<0) // v不是圖G的頂點(diǎn)
return ERROR;
for(i=0;i<G.vexnum;i++)
DeleteArc(G,v,G.vexs[i]); // 刪除由頂點(diǎn)v發(fā)出的所有弧
if(G.kind<2) // 有向
for(i=0;i<G.vexnum;i++)
DeleteArc(G,G.vexs[i],v); // 刪除發(fā)向頂點(diǎn)v的所有弧
for(j=k+1;j<G.vexnum;j++)
G.vexs[j-1]=G.vexs[j]; // 序號(hào)k后面的頂點(diǎn)向量依次前移
for(i=0;i<G.vexnum;i++)
for(j=k+1;j<G.vexnum;j++)
G.arcs[i][j-1]=G.arcs[i][j]; // 移動(dòng)待刪除頂點(diǎn)之右的矩陣元素
for(i=0;i<G.vexnum;i++)
for(j=k+1;j<G.vexnum;j++)
G.arcs[j-1][i]=G.arcs[j][i]; // 移動(dòng)待刪除頂點(diǎn)之下的矩陣元素
G.vexnum--; // 更新圖的頂點(diǎn)數(shù)
return OK;
}
void DestroyGraph(MGraph &G)
{ // 初始條件：圖G存在。操作結(jié)果：銷(xiāo)毀圖G
int i;
for(i=G.vexnum-1;i>=0;i--) // 由大到小逐一刪除頂點(diǎn)及與其相關(guān)的弧(邊)
DeleteVex(G,G.vexs[i]);
}
void Display(MGraph G)
{ // 輸出鄰接矩陣存儲(chǔ)結(jié)構(gòu)的圖G
int i,j;
char s[7]="無(wú)向網(wǎng)",s1[3]="邊";
switch(G.kind)
{ case DG:strcpy(s,"有向圖");
strcpy(s1,"弧");
break;
case DN:strcpy(s,"有向網(wǎng)");
strcpy(s1,"弧");
break;
case UDG:strcpy(s,"無(wú)向圖");
case UDN:;
}
printf("%d個(gè)頂點(diǎn)%d條%s的%s。頂點(diǎn)依次是：",G.vexnum,G.arcnum,s1,s);
for(i=0;i<G.vexnum;++i)
Visit(GetVex(G,i)); // 根據(jù)頂點(diǎn)信息的類(lèi)型，訪(fǎng)問(wèn)第i個(gè)頂點(diǎn)，在func7-1.cpp中
printf("\nG.arcs.adj：\n");
for(i=0;i<G.vexnum;i++) // 輸出二維數(shù)組G.arcs.adj
{ for(j=0;j<G.vexnum;j++)
printf("%11d",G.arcs[i][j].adj);
printf("\n");
}
printf("G.arcs.info：\n"); // 輸出G.arcs.info
if(G.kind<2) // 有向
printf(" 弧尾 弧頭 該%s的信息：\n",s1);
else // 無(wú)向
printf("頂點(diǎn)1 頂點(diǎn)2 該%s的信息：\n",s1);
for(i=0;i<G.vexnum;i++)
if(G.kind<2) // 有向
{ for(j=0;j<G.vexnum;j++)
if(G.arcs[i][j].info)
{ printf("%5s %5s ",G.vexs[i].name,G.vexs[j].name);
OutputArc(G.arcs[i][j].info); // 輸出弧(邊)的相關(guān)信息，在func7-2.cpp中
}
} // 加括號(hào)為避免if-else對(duì)配錯(cuò)
else // 無(wú)向，輸出上三角
for(j=i+1;j<G.vexnum;j++)
if(G.arcs[i][j].info)
{ printf("%5s %5s ",G.vexs[i].name,G.vexs[j].name);
OutputArc(G.arcs[i][j].info); // 輸出弧(邊)的相關(guān)信息，在func7-2.cpp中
}
}
void CreateFromFile(MGraph &G,char* filename,int IncInfo)
{ // 采用數(shù)組(鄰接矩陣)表示法，由文件構(gòu)造圖或網(wǎng)G。IncInfo=0或1，表示弧(邊)無(wú)或有相關(guān)信息
int i,j,k;
VRType w=0; // 頂點(diǎn)關(guān)系類(lèi)型，圖
VertexType v1,v2; // 頂點(diǎn)類(lèi)型
FILE *f; // 文件指針類(lèi)型
f=fopen(filename,"r"); // 打開(kāi)數(shù)據(jù)文件，并以f表示
fscanf(f,"%d",&G.kind); // 由文件輸入G的類(lèi)型
if(G.kind%2) // 網(wǎng)
w=INFINITY;
fscanf(f,"%d",&G.vexnum); // 由文件輸入G的頂點(diǎn)數(shù)
for(i=0;i<G.vexnum;++i)
InputFromFile(f,G.vexs[i]); // 由文件輸入頂點(diǎn)信息，在func7-1.cpp中
fscanf(f,"%d",&G.arcnum); // 由文件輸入G的弧(邊)數(shù)
for(i=0;i<G.vexnum;++i) // 初始化二維鄰接矩陣
for(j=0;j<G.vexnum;++j)
{ G.arcs[i][j].adj=w; // 不相鄰
G.arcs[i][j].info=NULL; // 沒(méi)有相關(guān)信息
}
if(!(G.kind%2)) // 圖
w=1;
for(k=0;k<G.arcnum;++k) // 對(duì)于所有弧
{ fscanf(f,"%s%s",v1.name,v2.name); // 輸入弧尾、弧頭的名稱(chēng)
if(G.kind%2) // 網(wǎng)
fscanf(f,"%d",&w); // 再輸入權(quán)值
i=LocateVex(G,v1); // 弧尾的序號(hào)
j=LocateVex(G,v2); // 弧頭的序號(hào)
G.arcs[i][j].adj=w; // 權(quán)值
if(IncInfo) // 有相關(guān)信息
InputArcFromFile(f,G.arcs[i][j].info);
// 由文件動(dòng)態(tài)生成存儲(chǔ)空間，輸入弧的相關(guān)信息，在func7-2.cpp中
if(G.kind>1) // 無(wú)向
G.arcs[j][i]=G.arcs[i][j]; // 無(wú)向，兩個(gè)單元的信息相同
}
fclose(f); // 關(guān)閉數(shù)據(jù)文件
}
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -