题目描述
已知一有向图,构建该图对应的邻接表。
邻接表包含数组和单链表两种数据结构,其中每个数组元素也是单链表的头结点,数组元素包含两个属性,属性一是顶点编号info,属性二是指针域next指向与它相连的顶点信息。
单链表的每个结点也包含两个属性,属性一是顶点在数组的位置下标,属性二是指针域next指向下一个结点。
输入
第1行输入整数t,表示有t个图
第2行输入n和k,表示该图有n个顶点和k条弧。
第3行输入n个顶点。
第4行起输入k条弧的起点和终点,连续输入k行
以此类推输入下一个图
输出
输出每个图的邻接表,每行输出格式:数组下标 顶点编号-连接顶点下标-......-^,数组下标从0开始。
具体格式请参考样例数据,每行最后加入“^”表示NULL。
样例输入
1 5 7 A B C D E A B A D A E B D C B C E E D样例输出
0 A-1-3-4-^ 1 B-3-^ 2 C-1-4-^ 3 D-^ 4 E-3-^提示
#include<iostream> using namespace std; #define N 100 class ArcNode { public: int adjvex;///该弧所指向的顶点的位置 ArcNode *nextarc; int weight;///该弧对应的权值 ArcNode(int adj,ArcNode *next) { adjvex=adj; nextarc=next; } }; class VNode { public: string data;///顶点信息 ArcNode *firstarc;///指向第一条依附该顶点的弧 VNode() { data=""; } }; class ALGraph { public: VNode vertices[N]; ArcNode *pRow[N]; int vexnum,arcnum; ALGraph() { for(int i=0;i<N;i++) { vertices[i].firstarc=NULL; pRow[i]=NULL; } } int getindex(string v) { for(int i=0;i<vexnum;i++) { if(vertices[i].data==v) return i; } return -1; } void CreateALGraph() { string d; cin>>vexnum>>arcnum; for(int i=0;i<vexnum;i++) { cin>>d; vertices[i].data=d; } string v1,v2; for(int i=0;i<arcnum;i++) { cin>>v1>>v2; int index1=getindex(v1); int index2=getindex(v2); ArcNode *edge=new ArcNode(index2,NULL); if(vertices[index1].firstarc==NULL) { vertices[index1].firstarc=edge; } else { pRow[index1]->nextarc=edge; } pRow[index1]=edge; } } void display() { for(int i=0;i<vexnum;i++) { cout<<i<<" "; ArcNode *p=vertices[i].firstarc; cout<<vertices[i].data<<"-"; while(p!=NULL) { cout<<p->adjvex<<"-"; p=p->nextarc; } cout<<"^"<<endl; } } }; int main() { int T; cin>>T; while(T--) { ALGraph g; g.CreateALGraph(); g.display(); } return 0; }