//严蔚敏《数据结构》
//图的存储结构：数组表示法（邻接矩阵）
//自学中，加油！
#include<iostream>
#include<string>
using namespace std;
const int MaxVertexnum=20;
const int Infinity=INT_MAX;
#define InfoType string
#define VRType double
#define VertexType char
typedef enum{DG,DN,UDG,UDN} GraphKind;//不能#define GrapKind enum{DG,DN,UDG,UDN}
typedef struct
{
VRType adj;
InfoType* info;
}ArcCell,AdjMatrix[MaxVertexnum][MaxVertexnum];
typedef struct
{
VertexType vers[MaxVertexnum];
AdjMatrix arcs;
int vernum,arcnum;
GraphKind kind;
}MGraph;
int LocateVex(MGraph G,VertexType v)//返回点v在G.vers中的下标
{
for(int i=0;i!=G.vernum;i++){
if(G.vers[i]==v)
return i;
}
return -1;
}
void CreatDG(MGraph& G)//创建有向图
{
cout<<"输入有向图的点和弧的数量:";
cin>>G.vernum>>G.arcnum;
cout<<"输入"<<G.vernum<<"个点（类型为char）\n";
for(int i=0;i!=G.vernum;i++)
cin>>G.vers[i];
for(int i=0;i!=G.vernum;i++){//初始化邻接矩阵
for(int j=0;j!=G.vernum;j++){
G.arcs[i][j].adj=0;
G.arcs[i][j].info=nullptr;
}
}
VertexType v1,v2;
int i,j;
for(int k=0;k!=G.arcnum;k++){
cout<<"输入两个点以及两个点的信息\n";
cin>>v1>>v2;
i=LocateVex(G,v1);j=LocateVex(G,v2);
G.arcs[i][j].adj=1;
}
}
void CreatDN(MGraph& G)//创建有向网
{
cout<<"输入有向网的点和弧的数量:";
cin>>G.vernum>>G.arcnum;
cout<<"输入"<<G.vernum<<"个点（类型为char）\n";
for(int i=0;i!=G.vernum;i++)
cin>>G.vers[i];
for(int i=0;i!=G.vernum;i++){//初始化邻接矩阵
for(int j=0;j!=G.vernum;j++){
G.arcs[i][j].adj=Infinity;
G.arcs[i][j].info=nullptr;
}
}
VertexType v1,v2;
VRType w;
int i,j;
for(int k=0;k!=G.arcnum;k++){
cout<<"输入两个点以及两个点之间的权值\n";
cin>>v1>>v2>>w;
i=LocateVex(G,v1);j=LocateVex(G,v2);
G.arcs[i][j].adj=w;
}
}
void CreatUDG(MGraph& G)//创建无向图
{
cout<<"输入无向图的点和边的数量:";
cin>>G.vernum>>G.arcnum;
cout<<"输入"<<G.vernum<<"个点（类型为char）\n";
for(int i=0;i!=G.vernum;i++)
cin>>G.vers[i];
for(int i=0;i!=G.vernum;i++){//初始化邻接矩阵
for(int j=0;j!=G.vernum;j++){
G.arcs[i][j].adj=0;
G.arcs[i][j].info=nullptr;
}
}
VertexType v1,v2;
int i,j;
for(int k=0;k!=G.arcnum;k++){
cout<<"输入两个点以及两个点的信息\n";
cin>>v1>>v2;
i=LocateVex(G,v1);j=LocateVex(G,v2);
G.arcs[i][j].adj=1;
G.arcs[j][i].adj=G.arcs[i][j].adj;
}
}
void CreatUDN(MGraph& G)//创建无向网
{
cout<<"输入无向网的点和边的数量:";
cin>>G.vernum>>G.arcnum;
cout<<"输入"<<G.vernum<<"个点（类型为char）\n";
for(int i=0;i!=G.vernum;i++)
cin>>G.vers[i];
for(int i=0;i!=G.vernum;i++){//初始化邻接矩阵
for(int j=0;j!=G.vernum;j++){
G.arcs[i][j].adj=Infinity;
G.arcs[i][j].info=nullptr;
}
}
VertexType v1,v2;
VRType w;
int i,j;
for(int k=0;k!=G.arcnum;k++){
cout<<"输入两个点以及两个点之间的权值\n";
cin>>v1>>v2>>w;
i=LocateVex(G,v1);j=LocateVex(G,v2);
G.arcs[i][j].adj=w;
G.arcs[j][i].adj=G.arcs[i][j].adj;
}
}
istream& operator>>(istream& is,GraphKind& k)//重载cin>>G.kind(G.kind为枚举量)
{
string kind;
cin>>kind;
int x;
if(kind=="DG")
x=0;
else if(kind=="DN")
x=1;
else if(kind=="UDG")
x=2;
else if(kind=="UDN")
x=3;
switch(x)
{
case 0:k=DG;break;
case 1:k=DN;break;
case 2:k=UDG;break;
case 3:k=UDN;break;
}
return is;
}
bool CreatGraph(MGraph& G)//创建图
{
cout<<"输入图G的类型(DG:有向图 DN:有向网 UDG:无向图 UDN:无向网)\n";
cin>>G.kind;
switch(G.kind)
{
case DG:CreatDG(G);break;
case DN:CreatDN(G);break;
case UDG:CreatUDG(G);break;
case UDN:CreatUDN(G);break;
default:return false;
}
return true;
}
ostream& operator<<(ostream& os,GraphKind k)//重载cout<<G.kind(G.kind为枚举量)
{
switch(k)
{
case DG:cout<<"有向图";break;
case DN:cout<<"有向网";break;
case UDG:cout<<"无向图";break;
case UDN:cout<<"无向网";break;
}
return os;
}
void Output_Graph(MGraph G)//输出图
{
cout<<"图的类型为"<<G.kind<<endl;
for(int i=0;i!=G.vernum;i++){
for(int j=0;j!=G.vernum;j++)
cout<<G.arcs[i][j].adj<<'\t';
cout<<endl;
}
cout<<"----"<<endl;
}
int main()
{
MGraph G;
if(CreatGraph(G))
Output_Graph(G);
return 0;
}
输入图G的类型(DG:有向图 DN:有向网 UDG:无向图 UDN:无向网)
UDN
输入无向网的点和边的数量:5 3
输入5个点（类型为char）
a b c d e
输入两个点以及两个点之间的权值
a c 1.1
输入两个点以及两个点之间的权值
b d 2.2
输入两个点以及两个点之间的权值
c e 3.3
图的类型为无向网
2.14748e+009 2.14748e+009 1.1 2.14748e+009 2.14748e+009
2.14748e+009 2.14748e+009 2.14748e+009 2.2 2.14748e+009
1.1 2.14748e+009 2.14748e+009 2.14748e+009 3.3
2.14748e+009 2.2 2.14748e+009 2.14748e+009 2.14748e+009
2.14748e+009 2.14748e+009 3.3 2.14748e+009 2.14748e+009
----
Process returned 0 (0x0) execution time : 22.931 s
Press any key to continue.
Processed:
0.008, SQL:
8
