欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

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

程序员文章站 2022-03-08 15:50:41
#include#include#include#include#include#include#include#include#include#define debug(a) cout<<#a<<"="<<....
#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