《資料結構》實驗三報告（無向圖鄰接表的構造）

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e3;
typedef int LL;
typedef struct LNode* ToNode;
typedef struct Graph* ToGraph;
typedef struct LNode{///單鏈表
    LL num;///頂點編號
    LL val;///表頭節點到直連點的邊權
    LL indegree;///表頭節點存下該點的入度
    LL outdegree;///表頭節點存下該點的出度
    ToNode Next;
}LNode;
typedef struct Graph{
    ToNode A[maxn];
    LL graphnodes;///圖的頂點數
    LL graphedges;///圖的邊數
}Graph;
void addnode(ToGraph &G,LL v1,LL v2){
    ToNode p=(ToNode)malloc(sizeof(LNode));
    p=(G->A[v1]);
    while( p->Next!=nullptr ){
        p=p->Next;
        if(p->num==v2) return;
        if(p==nullptr) break;
    }
    ToNode k=(ToNode)malloc(sizeof(LNode));
    p->Next=k;
    k->num=v2;
    k->Next=nullptr;
    return;
}
void find(ToGraph &G,LL v1,LL v2){
        if(G->A[v1]->num==v1){
            addnode(G,v1,v2);
            cout<<"找到"<<v1<<"頂點"<<endl;
            G->A[v1]->outdegree++;///該點出度++
        }
        if(G->A[v2]->num==v2){

            G->A[v2]->indegree++;///該點入讀++
            cout<<(G->A[v2]->indegree)<<endl;
        }
}
void CreateGraph(ToGraph& G,LL op){
    G=(ToGraph)malloc(sizeof(Graph));
    if(op==0) cout<<"要構建的無向圖的頂點數目:"<<endl;
    else if(op==1) cout<<"要構建的有向圖的點數目:"<<endl;
    cin>>(G->graphnodes);
    if(op==0) cout<<"要構建的無向圖的邊的數目:"<<endl;
    else if(op==1) cout<<"要構建的有向圖的邊數目:"<<endl;
    cin>>(G->graphedges);
    for(LL i=1;i<=(G->graphnodes);i++){
        LL v;
        cout<<"頂點為:";cin>>v;
        G->A[v]=(ToNode)malloc(sizeof(LNode));
        G->A[v]->num=v;
        G->A[v]->indegree=0;
        G->A[v]->outdegree=0;
        G->A[v]->Next=nullptr;
    }
    for(LL i=1;i<=(G->graphedges);i++){
        cout<<"請輸入邊(vi,vj)上的頂點資訊"<<endl;
        LL v1,v2;///v1<---->v2
        cin>>v1>>v2;
        if(op==0){
            find(G,v1,v2);
            find(G,v2,v1);
        }
        else if(op==1){
            find(G,v1,v2);
        }
    }
}
LL findnum(ToGraph& G,LL v){
    for(LL i=1;i<=G->graphnodes;i++){
        if(G->A[i]->num==v) return i;
    }
    return 0;
}
void showGraph(ToGraph& G){
    cout<<"所建立的鄰接表如下:"<<endl;
    for(LL i=1;i<=G->graphnodes;i++){
        ///LL v=findnum(G,i);///找標號為i的點
        cout<<"標號為"<<i<<"的點:";
        ToNode p=G->A[i];
        if(p->Next==nullptr){
            cout<<"該點沒有相連點";
        }
        else{
            while(p->Next!=nullptr){
                p=p->Next;
                cout<<" "<<p->num<<" ";
            }
        }
        cout<<endl;
    }
}
bool checkedge(ToGraph& G){
    LL v1,v2;
    cout<<"輸入邊的端點v1:";cin>>v1;
    cout<<"輸入邊的端點v2:";cin>>v2;
    ToNode p=G->A[v1];
    if(p->Next==nullptr) return 0;
    while(p->Next!=nullptr){
        p=p->Next;
        if(p->num==v2) return 1;
    }
    return 0;
}
void caldegree(ToGraph& G,LL op){///計算入度和出度
     if(op==1){
        for(LL i=1;i<=G->graphnodes;i++){
            cout<<"起點為"<<i<<":";
            cout<<"該點"<<i<<"的入度為:"<<G->A[i]->indegree<<endl;
            cout<<"該點"<<i<<"的出度為:"<<G->A[i]->outdegree<<endl;
            cout<<endl;
        }
     }
     else{
         for(LL i=1;i<=G->graphnodes;i++){
            cout<<"起點為"<<i<<":";
            cout<<"該點"<<i<<"的度數為:"<<G->A[i]->indegree<<endl;
            cout<<endl;
        }
     }
}
int main(void)
{
  ///cin.tie(0);std::ios::sync_with_stdio(false);
  ToGraph G;
  cout<<"選擇構建無向圖(輸入0)or有向圖(輸入1)"<<endl;
  LL op;cin>>op;
  if(op==0){
    CreateGraph(G,0);///無向圖
  }
  else if(op==1){
    CreateGraph(G,1);///有向圖
  }
  showGraph(G);
  cout<<"判斷邊是否存在"<<endl;
  if(checkedge(G)){
    cout<<"該邊存在"<<endl;
  }
  else cout<<"該邊不存在"<<endl;
  caldegree(G,op);
return 0;
}

如果不是連續的就按照輸入順序輸出單鏈表

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e3;
typedef int LL;
typedef struct LNode* ToNode;
typedef struct Graph* ToGraph;
typedef struct LNode{///單鏈表
    LL num;///頂點編號
    LL val;///表頭節點到直連點的邊權
    LL indegree;///表頭節點存下該點的入度
    LL outdegree;///表頭節點存下該點的出度
    ToNode Next;
}LNode;
typedef struct Graph{
    ToNode A[maxn];
    LL graphnodes;///圖的頂點數
    LL graphedges;///圖的邊數
}Graph;
void addnode(ToGraph &G,LL _v1,LL _v2){
    ToNode p=(ToNode)malloc(sizeof(LNode));
    p=(G->A[_v1]);
    while( p->Next!=nullptr ){
        p=p->Next;
        if(p->num==G->A[_v2]->num) return;///重邊只有一次頂點
        if(p==nullptr) break;
    }
    ToNode k=(ToNode)malloc(sizeof(LNode));
    p->Next=k;
    k->num=G->A[_v2]->num;
    k->Next=nullptr;
    return;
}
LL findnum(ToGraph& G,LL v){
    for(LL i=1;i<=G->graphnodes;i++){
        if(G->A[i]->num==v) return i;
    }
    return 0;
}
void find(ToGraph &G,LL v1,LL v2){
        LL _v1=findnum(G,v1);
        LL _v2=findnum(G,v2);
      ///  debug(_v1);debug(_v2);
        if(G->A[_v1]->num==v1){
            addnode(G,_v1,_v2);
            cout<<"找到"<<v1<<"頂點"<<endl;
            G->A[_v1]->outdegree++;///該點出度++
        }
        if(G->A[_v2]->num==v2){
            G->A[_v2]->indegree++;///該點入讀++
        }
}
void CreateGraph(ToGraph& G,LL op){
    G=(ToGraph)malloc(sizeof(Graph));
    if(op==0) cout<<"要構建的無向圖的頂點數目:"<<endl;
    else if(op==1) cout<<"要構建的有向圖的點數目:"<<endl;
    cin>>(G->graphnodes);
    if(op==0) cout<<"要構建的無向圖的邊的數目:"<<endl;
    else if(op==1) cout<<"要構建的有向圖的邊數目:"<<endl;
    cin>>(G->graphedges);
    for(LL i=1;i<=(G->graphnodes);i++){
        LL v;
        cout<<"頂點為:";cin>>v;
        G->A[i]=(ToNode)malloc(sizeof(LNode));
        G->A[i]->num=v;
        G->A[i]->indegree=0;
        G->A[i]->outdegree=0;
        G->A[i]->Next=nullptr;
    }
    for(LL i=1;i<=(G->graphedges);i++){
        cout<<"請輸入邊(vi,vj)上的頂點資訊"<<endl;
        LL v1,v2;///v1<---->v2
        cin>>v1>>v2;
        if(op==0){
            find(G,v1,v2);
            find(G,v2,v1);
        }
        else if(op==1){
            find(G,v1,v2);
        }
    }
    cout<<"構造完成"<<endl;
}
void showGraph(ToGraph& G){
    cout<<"按輸入順序所建立的鄰接表如下:"<<endl;
    for(LL i=1;i<=G->graphnodes;i++){///按順序輸出單鏈表
        ///LL v=findnum(G,i);///找標號為i的點
        cout<<"標號為"<<G->A[i]->num<<"的點:";
        ToNode p=G->A[i];
        if(p->Next==nullptr){
            cout<<"該點沒有相連點";
        }
        else{
            while(p->Next!=nullptr){
                p=p->Next;
                cout<<" "<<p->num<<" ";
            }
        }
        cout<<endl;
    }
}
bool checkedge(ToGraph& G){
    LL v1,v2;
    cout<<"輸入邊的端點v1:";cin>>v1;
    cout<<"輸入邊的端點v2:";cin>>v2;
    LL _v1=findnum(G,v1);
    ToNode p=G->A[_v1];
    if(p->Next==nullptr) return 0;
    while(p->Next!=nullptr){
        p=p->Next;
        if(p->num==v2) return 1;
    }
    return 0;
}
void caldegree(ToGraph& G,LL op){///計算入度和出度
     if(op==1){
        for(LL i=1;i<=G->graphnodes;i++){
            cout<<"當前點為"<<G->A[i]->num<<":";
            cout<<"該點"<<G->A[i]->num<<"的入度為:"<<G->A[i]->indegree<<endl;
            cout<<"該點"<<G->A[i]->num<<"的出度為:"<<G->A[i]->outdegree<<endl;
            cout<<endl;
        }
     }
     else{
         for(LL i=1;i<=G->graphnodes;i++){
            cout<<"當前點為"<<G->A[i]->num<<":";
            cout<<"該點"<<G->A[i]->num<<"的度數為:"<<G->A[i]->indegree<<endl;
            cout<<endl;
        }
     }
}
int main(void)
{
  ///cin.tie(0);std::ios::sync_with_stdio(false);
  ToGraph G;
  cout<<"選擇構建無向圖(輸入0)or有向圖(輸入1)"<<endl;
  LL op;cin>>op;
  if(op==0){
    CreateGraph(G,0);///無向圖
  }
  else if(op==1){
    CreateGraph(G,1);///有向圖
  }
  cout<<"fuck"<<endl;
  showGraph(G);
  cout<<"判斷邊是否存在"<<endl;
  if(checkedge(G)){
    cout<<"該邊存在"<<endl;
  }
  else cout<<"該邊不存在"<<endl;
  caldegree(G,op);
return 0;
}