2020-10-8 严蔚敏《数据结构》 图的存储结构：邻接表

//严蔚敏《数据结构》 //图的存储结构：邻接表 //自学中，加油！！ #include<iostream> #include<string> using namespace std; #define InfoType double #define VertexType string const int MaxVertexNum=40; typedef enum{DG,DN,UDG,UDN} GraphKind; typedef struct ArcNode { int adjvex;//邻接点位置下标 InfoType* info; struct ArcNode* nextarc; }ArcNode;//ArcNode 邻接点 typedef struct VNode { VertexType data; ArcNode* firstarc; }VNode,AdjList[MaxVertexNum];//VNode 顶点 | AdjList 邻接点位置下标（adjvex）的数组 typedef struct { AdjList vertices; int vexnum,arcnum; GraphKind kind; }ALGraph;//图 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; } int Locate_Vertices(ALGraph G,VertexType v)//返回v在G.vertices数组的位置下标 { for(int i=0;i!=G.vexnum;i++){ if(G.vertices[i].data==v) return i; } return -1; } bool CreatDG(ALGraph& G)//创建有向图的邻接表 { cout<<"输入有向图的顶点数和弧数:"; cin>>G.vexnum>>G.arcnum; cout<<"输入"<<G.vexnum<<"个顶点的信息（VertexType为string）\n"; for(int i=0;i!=G.vexnum;i++){ cin>>G.vertices[i].data; G.vertices[i].firstarc=nullptr; } VertexType v1,v2; int i,j; ArcNode* p; for(int k=0;k!=G.arcnum;k++){//输入所有弧的信息 cout<<"输入两个顶点信息:"; cin>>v1>>v2; i=Locate_Vertices(G,v1); j=Locate_Vertices(G,v2); p=new ArcNode; if(!p) return false; p->adjvex=j; p->info=nullptr; p->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p; } return true; } bool CreatDN(ALGraph& G)//创建有向网 { cout<<"输入有向网的顶点数和弧数:"; cin>>G.vexnum>>G.arcnum; cout<<"输入"<<G.vexnum<<"个顶点信息\n"; for(int i=0;i!=G.vexnum;i++){ cin>>G.vertices[i].data; G.vertices[i].firstarc=nullptr; } int i,j; VertexType v1,v2; ArcNode* p; InfoType w; for(int k=0;k!=G.arcnum;k++){//输入所有弧的信息 cout<<"输入两个顶点信息及权值:"; cin>>v1>>v2>>w; i=Locate_Vertices(G,v1); j=Locate_Vertices(G,v2); p=new ArcNode; if(!p) return false; p->adjvex=j; p->info=new InfoType;//刚开始我的113-114行代码为p->info=&w 十分危险，w会随着该函数的结束而回收 *p->info=w;//而之后的p->info指向被回收的空间 危险！！！ //发现该问题后，将113行代码改为*p->info=w 十分危险，虽分配了p的空间，但p->info并未分配空间 //*p->info就找不到，直接导致运行窗口崩溃 p->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p; } return true; } bool CreatUDG(ALGraph& G)//创建无向图 { cout<<"输入无向图的顶点数和边数:"; cin>>G.vexnum>>G.arcnum; cout<<"输入"<<G.vexnum<<"个顶点信息\n"; for(int i=0;i!=G.vexnum;i++){ cin>>G.vertices[i].data; G.vertices[i].firstarc=nullptr; } int i,j; VertexType v1,v2; ArcNode* p1,* p2; for(int k=0;k!=G.arcnum;k++){//输入所有边的信息 cout<<"输入两个顶点信息:"; cin>>v1>>v2; i=Locate_Vertices(G,v1); j=Locate_Vertices(G,v2); p1=new ArcNode; if(!p1) return false; p1->adjvex=j; p1->info=nullptr; p1->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p1; p2=new ArcNode; if(!p2) return false; p2->adjvex=i; p2->info=nullptr; p2->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=p2; } return true; } bool CreatUDN(ALGraph& G)//创建无向网 { cout<<"输入无向网的顶点数和边数:"; cin>>G.vexnum>>G.arcnum; cout<<"输入"<<G.vexnum<<"个顶点信息\n"; for(int i=0;i!=G.vexnum;i++){ cin>>G.vertices[i].data; G.vertices[i].firstarc=nullptr; } int i,j; VertexType v1,v2; ArcNode* p1,* p2; InfoType w; for(int k=0;k!=G.arcnum;k++){//输入所有边的信息 cout<<"输入两个顶点信息及权值:"; cin>>v1>>v2>>w; i=Locate_Vertices(G,v1); j=Locate_Vertices(G,v2); p1=new ArcNode; if(!p1) return false; p1->adjvex=j; p1->info=new InfoType; *p1->info=w; p1->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p1; p2=new ArcNode; if(!p2) return false; p2->adjvex=i; p2->info=new InfoType; *p2->info=w; p2->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=p2; } return true; } bool Creat_ALGraph(ALGraph& G)//根据G.kind创建不同的图 { cout<<"输入图的类型\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; } void Output_ALGraph(ALGraph G)//输出图 { ArcNode* p; for(int i=0;i!=G.vexnum;i++){ cout<<"顶点信息:"<<G.vertices[i].data; p=G.vertices[i].firstarc; while(p){ cout<<"->邻接点位置下标:"<<p->adjvex; if(p->info) cout<<" 权值:"<<*p->info; p=p->nextarc; } cout<<endl; } } int main() { ALGraph G; if(Creat_ALGraph(G)) Output_ALGraph(G); return 0; }

测试图例：

输入图的类型 DG 输入有向图的顶点数和弧数:4 4 输入4个顶点的信息（VertexType为string） v1 v2 v3 v4 输入两个顶点信息:v1 v2 输入两个顶点信息:v1 v3 输入两个顶点信息:v3 v4 输入两个顶点信息:v4 v1 顶点信息:v1->邻接点位置下标:2->邻接点位置下标:1 顶点信息:v2 顶点信息:v3->邻接点位置下标:3 顶点信息:v4->邻接点位置下标:0 Process returned 0 (0x0) execution time : 34.759 s Press any key to continue. 输入图的类型 DN 输入有向网的顶点数和弧数:4 4 输入4个顶点信息 v1 v2 v3 v4 输入两个顶点信息及权值:v1 v2 1.1 输入两个顶点信息及权值:v1 v3 2.2 输入两个顶点信息及权值:v3 v4 3.3 输入两个顶点信息及权值:v4 v1 4.4 顶点信息:v1->邻接点位置下标:2 权值:2.2->邻接点位置下标:1 权值:1.1 顶点信息:v2 顶点信息:v3->邻接点位置下标:3 权值:3.3 顶点信息:v4->邻接点位置下标:0 权值:4.4 Process returned 0 (0x0) execution time : 21.797 s Press any key to continue. 输入图的类型 UDG 输入无向图的顶点数和边数:5 6 输入5个顶点信息 v1 v2 v3 v4 v5 输入两个顶点信息:v1 v2 输入两个顶点信息:v1 v4 输入两个顶点信息:v3 v4 输入两个顶点信息:v3 v2 输入两个顶点信息:v3 v5 输入两个顶点信息:v5 v2 顶点信息:v1->邻接点位置下标:3->邻接点位置下标:1 顶点信息:v2->邻接点位置下标:4->邻接点位置下标:2->邻接点位置下标:0 顶点信息:v3->邻接点位置下标:4->邻接点位置下标:1->邻接点位置下标:3 顶点信息:v4->邻接点位置下标:2->邻接点位置下标:0 顶点信息:v5->邻接点位置下标:1->邻接点位置下标:2 Process returned 0 (0x0) execution time : 24.102 s Press any key to continue. 输入图的类型 UDN 输入无向网的顶点数和边数:5 6 输入5个顶点信息 v1 v2 v3 v4 v5 输入两个顶点信息及权值:v1 v2 1.1 输入两个顶点信息及权值:v1 v4 2.2 输入两个顶点信息及权值:v3 v4 3.3 输入两个顶点信息及权值:v3 v5 4.4 输入两个顶点信息及权值:v3 v2 5.5 输入两个顶点信息及权值:v2 v5 6.6 顶点信息:v1->邻接点位置下标:3 权值:2.2->邻接点位置下标:1 权值:1.1 顶点信息:v2->邻接点位置下标:4 权值:6.6->邻接点位置下标:2 权值:5.5->邻接点位置下标:0 权值:1.1 顶点信息:v3->邻接点位置下标:1 权值:5.5->邻接点位置下标:4 权值:4.4->邻接点位置下标:3 权值:3.3 顶点信息:v4->邻接点位置下标:2 权值:3.3->邻接点位置下标:0 权值:2.2 顶点信息:v5->邻接点位置下标:1 权值:6.6->邻接点位置下标:2 权值:4.4 Process returned 0 (0x0) execution time : 32.979 s Press any key to continue.