《数据结构》实验三报告（无向图邻接表的构造）

#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;
}

 

本文地址：https://blog.csdn.net/zstuyyyyccccbbbb/article/details/111937344