題目描述

已知一有向圖，構建該圖對應的鄰接表。鄰接表包含數組和單鏈表兩種數據結構，其中每個數組元素也是單鏈表的頭結點，數組元素包含兩個屬性，屬性一是頂點編號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-^ 創建一個nodearray來存放頭節點 在空間上就是豎的，對每個頭節點創建一個nodelist來存放與他相連的節點，在空間上就是水平的。 #include<iostream> using namespace std; struct Node {char name;int info;Node *next; };int main() {int t;cin>>t;while(t--){int n,k,i,j;cin>>n>>k;Node *nodearray[n];Node *nodelist[n];for(i=0;i<n;i++){nodearray[i]=new Node();nodelist[i]=new Node();cin>>nodearray[i]->name;nodearray[i]->info=i;nodelist[i]=nodearray[i];} for(i=0;i<k;i++){char ch1,ch2;cin>>ch1>>ch2;int info1,info2;for(j=0;j<n;j++){if(nodearray[j]->name==ch1)info1=nodearray[j]->info;if(nodearray[j]->name==ch2)info2=nodearray[j]->info;}Node *node=new Node();node->name=ch2;node->info=info2;node->next=NULL;nodelist[info1]->next=node;nodelist[info1]=node;}for(i=0;i<n;i++){cout<<i<<" ";Node *p=nodearray[i];cout<<p->name<<"-";p=p->next;while(p){cout<<p->info<<"-";p=p->next;}cout<<"^"<<endl;}} }

?

轉載于:https://www.cnblogs.com/Liu269393/p/10222599.html

總結

以上是生活随笔為你收集整理的DS树+图综合练习--构建邻接表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。