题目描述
已知一有向图，构建该图对应的邻接表。
邻接表包含数组和单链表两种数据结构，其中每个数组元素也是单链表的头结点，数组元素包含两个属性，属性一是顶点编号info，属性二是指针域next指向与它相连的顶点信息。
单链表的每个结点也包含两个属性，属性一是顶点在数组的位置下标，属性二是指针域next指向下一个结点。
输入
第1行输入整数t，表示有t个图
第2行输入n和k，表示该图有n个顶点和k条弧。
第3行输入n个顶点。
第4行起输入k条弧的起点和终点，连续输入k行
以此类推输入下一个图
输出
输出每个图的邻接表，每行输出格式：数组下标 顶点编号-连接顶点下标-......-^，数组下标从0开始。
具体格式请参考样例数据，每行最后加入“^”表示NULL。
输入样例1
1 5 7 A B C D E A B A D A E B D C B C E E D
输出样例1
0 A-1-3-4-^ 1 B-3-^ 2 C-1-4-^ 3 D-^ 4 E-3-^
思路分析
需要两个结构体，一个是顶点，一个是连接的点。
关键在于这个插入边的函数。
首先得写一个函数，用来获取顶点对应的下标。
有了下标之后，我们来实现插入的操作，这里要注意是有顺序的插入，如果头节点为空或者当前需要插入的下标小于头节点的下标，那么插入到头节点的后面，如果不是，那么乖乖循环去找恰当的位置插入。
嗯，等等，判断头节点的那一步是不是多余的？我去掉了好像不行，噢，这是不带头节点的链表。
AC代码
代码语言：javascript复制#include<iostream>
using namespace std;
struct Node{
int index;
Node*next=NULL;
};
struct Vertex{
char data;
Node*head=NULL;
};
class Map{
int vertex_number=0,arc_number=0;
Vertex*vertex=NULL;
public:
Map(){
cin>>vertex_number>>arc_number;
vertex=new Vertex[vertex_number];
for(int i=0;i<vertex_number;i )
cin>>vertex[i].data;
for(int i=0;i<arc_number;i ){
char tail,head;
cin>>tail>>head;
Insert(GetIndex(tail), GetIndex(head));
}
}
~Map(){
if(vertex)
delete[] vertex;
}
void Insert(int tail,int head){
Node*new_one=new Node();
new_one->index=head;
new_one->next=NULL;
if(vertex[tail].head==NULL||head<vertex[tail].head->index)
{
new_one->next=vertex[tail].head;
vertex[tail].head= new_one;
}else{
Node*cur=vertex[tail].head;
while(cur->next&&cur->next->index<head)
cur=cur->next;
new_one->next=cur->next;
cur->next=new_one;
}
}
int GetIndex(char data){
for(int i=0;i<vertex_number;i )
if(vertex[i].data==data)
return i;
}
void Traverse(){
for(int i=0;i<vertex_number;i ){
cout<<i<<' '<<vertex[i].data<<'-';
Node*cur=vertex[i].head;
while(cur){
cout<<cur->index<<'-';
cur=cur->next;
}
cout<<'^'<<endl;
}
}
};
int main() {
int t;
cin>>t;
while(t--){
Map test;
test.Traverse();
}
return 0;
}
