DS树+图综合练习--构建邻接表
程序员文章站
2022-03-03 11:18:00
...
题目描述
已知一有向图,构建该图对应的邻接表。
邻接表包含数组和单链表两种数据结构,其中每个数组元素也是单链表的头结点,数组元素包含两个属性,属性一是顶点编号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>
#include <string>
#include <queue>
using namespace std;
struct Node
{
int info;
string s;
struct Node *next;
};
class Map
{
private:
struct Node *m;
int N;
public:
void setMap(int n,int k);
void output();
};
void Map::setMap(int n,int k)
{
N=n;
m=new Node[n];
for(int i=0;i<n;i++)
{
cin>>m[i].s;
m[i].next=NULL;
}
string temp1,temp2;
int flag1,flag2;
struct Node *t,*p;
for(int i=0;i<k;i++)
{
cin>>temp1>>temp2;
for(int j=0;j<n;j++)
{
if(m[j].s==temp1)
flag1=j;
if(m[j].s==temp2)
flag2=j;
}
if(m[flag1].next==NULL)
{
p=new Node;
p->info=flag2;
p->next=NULL;
m[flag1].next=p;
p=NULL;
}
else
{
t=m[flag1].next;
while(t->next!=NULL)
{
t=t->next;
}
p=new Node;
p->info=flag2;
p->next=NULL;
t->next=p;
p=NULL;
}
}
}
void Map::output()
{
struct Node *t;
for(int i=0;i<N;i++)
{
cout<<i<<' ';
cout<<m[i].s;
t=m[i].next;
while(t)
{
cout<<'-'<<t->info;
t=t->next;
}
cout<<'-'<<'^'<<endl;
}
}
void test()
{
int n,k;
cin>>n>>k;
Map m;
m.setMap(n,k);
m.output();
}
int main()
{
int t;
cin>>t;
while(t--)
test();
return 0;
}
上一篇: 深度优先和广度优先
下一篇: 探讨python 3中的广度优先