題目描述
已知一有向圖，構建該圖對應的鄰接表。
鄰接表包含數組和單鏈表兩種數據結構，其中每個數組元素也是單鏈表的頭結點，數組元素包含兩個屬性，屬性一是頂點編號info，屬性二是指針域next指向與它相連的頂點信息。
單鏈表的每個結點也包含兩個屬性，屬性一是頂點在數組的位置下標，屬性二是指針域next指向下一個結點。
輸入
第1行輸入整數t，表示有t個圖
第2行輸入n和k，表示該圖有n個頂點和k條弧。
第3行輸入n個頂點。
第4行起輸入k條弧的起點和終點，連續輸入k行
以此類推輸入下一個圖
輸入樣例：
1
5 7
A B C D E
A B
A D
A E
B D
C B
C E
E D
輸出
輸出每個圖的鄰接表，每行輸出格式：數組下標 頂點編號-連接頂點下標-......-^，數組下標從0開始。
具體格式請參考樣例數據，每行最后加入“^”表示NULL。
輸出樣例：
0 A-1-3-4-^
1 B-3-^
2 C-1-4-^
3 D-^
4 E-3-^
代碼
#include <iostream>
using namespace std;struct Node{ //表中結點int adjvex;Node *next=NULL; //必要
};struct Header{ //表頭char info;Node *next=NULL;
};class List{
public:int n,k;Header *Array;List(){cin >> n >> k;Array = new Header[n];}void create(){for(int i = 0; i < n; i++){cin >> Array[i].info;}char c1,c2;int v=0; //標記處理的頂點for(int i = 0; i < k; i++){cin >> c1 >> c2;while(Array[v].info != c1){v++;}Node *t = new Node;t->adjvex = getIndex(c2);if(Array[v].next == NULL){ //當表頭next為空時Array[v].next = t;}else{ //不為空Node *s = Array[v].next;while(s->next != NULL){s = s->next;}s->next = t;}}}int getIndex(char c){ //獲取c2在表中的adjvexfor(int i = 0; i < n; i++){if(Array[i].info == c){return i;}}}void toPrint(){for(int i = 0; i < n; i++){cout << i << " " << Array[i].info << "-";Node *s = Array[i].next;while(s != NULL){cout << s->adjvex << "-";s = s->next;}cout << "^" << endl;}}
};int main()
{int t;cin >> t;while(t--){List list;list.create();list.toPrint();}return 0;
}
)
