邻接表：构造只有顶点没有边的图

太过爱你忘了你带给我的痛 2023-09-28 08:57 13阅读 0赞

## 新的一关------邻接表 ##

题目

目的：使用C++模板设计并逐步完善图的邻接表抽象数据类型（ADT）。
    
    内容：（1）请参照图的邻接矩阵模板类原型，设计并逐步完善图的邻接表ADT。（由于该环境目前仅支持单文件的编译，故将所有内容都集中在一个源文件内。在实际的设计中，推荐将抽象类及对应的派生类分别放在单独的头文件中。）
    
    （2）使用构造函数，构造一个只有结点没有边的图。
    
    注意：DG（有向图）, DN（有向网）, UDG（无向图）, UDN（无向网）
    
    参考函数原型：
    
    //构造函数构造一个只有结点没有边的图。3个参数的含义：图的类型、结点数、结点值 
    
    template<class TypeOfVer, class TypeOfEdge>
    
    adjlist_graph<TypeOfVer, TypeOfEdge>::adjlist_graph( const string &kd, int vSize, const TypeOfVer d[]);
    
    //图的邻接表模板类原型参考如下：
    /* 边表的结点定义 */
    template<class TypeOfEdge>
    struct edgeNode{
        
        int data;
        TypeOfEdge weight;
        edgeNode<TypeOfEdge> *next;
        edgeNode(const int &d, edgeNode<TypeOfEdge> *ptr = NULL) //构造函数，用于构造其他结点（无权图） 
        //函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面
        {
        
    
            next = ptr;
    
            data = d;
    
        }
    
        edgeNode(const int &d, const TypeOfEdge &w, edgeNode<TypeOfEdge> *ptr = NULL) //构造函数，用于构造其他结点（带权图） 
    
        //函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面
    
        {
        
    
            next = ptr;
    
            data = d;
    
            weight = w;
    
        }
    
        int getData(){
         return data;}  //取得结点的序号（顶点集） 
    
        TypeOfEdge getWeight(){
         return weight;}  //取得边集中对应边的权值 
    
        void SetLink( edgeNode<TypeOfEdge> *link ){
         next = link; }  //修改结点的next域 
    
        void SetData( int value ){
         data = value; }   //修改结点的序号（顶点集） 
    
        void SetWeight(TypeOfEdge value ){
         weight = value; }   //修改边集中对应边的权值   
    
    };
    
    
    
    //图的邻接表类
    
    template<class TypeOfVer, class TypeOfEdge>
    
    struct verNode
    
    {
        
    
        TypeOfVer ver;
    
        edgeNode<TypeOfEdge> *head;
    
        
    
        verNode(edgeNode<TypeOfEdge> *h = NULL){
        head = h;} 
    
        TypeOfVer getVer(){
         return ver;}  //取得结点值（顶点集） 
    
        edgeNode<TypeOfEdge> *getHead(){
         return head;}  //取得对应的边表的头指针 
    
        void setVer(TypeOfVer value){
         ver = value;}  //设置结点值（顶点集） 
    
        void setHead(edgeNode<TypeOfEdge> *value){
         head = value;}  //设置对应的边表的头指针
    
    
    
    };
    
    
    
    template <class TypeOfVer, class TypeOfEdge>
    
    class adjlist_graph{
        
    
        private:
    
           int Vers;           //顶点数 
    
           int Edges;          //边数 
    
           verNode<TypeOfVer,TypeOfEdge> *verList;
    
           
    
           string GraphKind;     //图的种类标志 
    
           
    
           bool Delete_Edge( int u, int v ); 
    
           bool DFS(int u, int &num, int visited[]); //DFS遍历（递归部分）
    
    
    
        public:
    
           adjlist_graph( const string &kd, int vSize, const TypeOfVer d[]); //构造函数构造一个只有结点没有边的图。 
    
           adjlist_graph( const string &kd, int vSize, int eSize, const TypeOfVer d[], int **e); 构造函数构造一个无权图。5个参数的含义：图的类型、结点数、边数、结点集和边集 
    
           adjlist_graph( const string &kd, int vSize, int eSize, const TypeOfVer d[], int **e, const TypeOfEdge w[]); //构造函数构造一个有权图。
    
           bool GraphisEmpty() {
         return Vers == 0; }  //判断图空否
    
           string GetGraphKind(){
         return GraphKind; }
    
           bool GetVer(int u, TypeOfVer &data); //取得G中指定顶点的值 
    
           int GetFirstAdjVex(int u, int &v); //返回G中指定顶点u的第一个邻接顶点的位序（顶点集）。若顶点在G中没有邻接顶点，则返回-1
    
           int GetNextAdjVex(int u, int v, int &w); //返回G中指定顶点u的下一个邻接顶点（相对于v）的位序（顶点集）。若顶点在G中没有邻接顶点，则返回false
    
           bool PutVer(int u, TypeOfVer data); //对G中指定顶点赋值 
    
           bool InsertVer(const TypeOfVer &data); //往G中添加一个顶点 
    
           int LocateVer(TypeOfVer data); //返回G中指定顶点的位置 
    
           bool ExistEdge(int u, int v);
    
           bool PrintVer();  //输出顶点集 
    
           bool PrintAdjList();  //输出邻接矩阵 
    
           int GetVerNum(){
         return Vers;}    //取得当前顶点数 
    
           int GetEdgeNum(){
         return Edges;}  //取得当前边数 
    
           bool Insert_Edge(int u, int v); //无权图插入一条边
    
           bool Insert_Edge(int u, int v, TypeOfEdge w); //有权图插入一条边
    
           bool DeleteVer(const TypeOfVer &data); //往G中删除一个顶点 
    
           bool DeleteEdge( int u, int v ); //删除边 (外壳：有向（删除1条边）， 无向（删除2条边））
    
           void DFS_Traverse(int u); //DFS遍历（外壳部分）
    
           void BFS_Traverse(int u); //BFS遍历
    
           ~adjlist_graph(); //析构函数 
    
    };

ADT表太长了，它原来给的格式我自己看不习惯，就不在题目中再改了，我在自己的代码中已经改好了。

> 输入说明：  
> 第一行：图的类型  
> 第二行：顶点数  
> 第三行：顶点集

> 输出说明：  
> 第一行：图的类型  
> 第二行：顶点集  
> 第三行：邻接表

> 输入范例：  
> UDG  
> 6  
> A B C D E F

> 输出范例：  
> UDG  
> A B C D E F  
> A->nullptr  
> B->nullptr  
> C->nullptr  
> D->nullptr  
> E->nullptr  
> F->nullptr

#include<iostream>
    #include<vector>
    #include<string>
    #include<sstream>
    #include<queue>
    #include<stack>
    #include<cmath>
    using namespace std;
    string b[10001];//用来存放顶点集
    //DG（有向图）  DN（有向网）  UDG（无向图） UDN（无向网）
    
    //图的邻接表模板类原型参考如下：
    /* 边表的结点定义 */
    template<class TypeOfEdge>//这个就是在边上的结点定义
    struct edgeNode{
        
        int data;
        TypeOfEdge weight;
        edgeNode<TypeOfEdge> *next;
        //构造函数，用于构造其他结点（无权图）
        //函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面
        edgeNode(int d,edgeNode<TypeOfEdge> *ptr=NULL){
         data=d;next=ptr; }
        //构造函数，用于构造其他结点（带权图）
        //函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面
        edgeNode(int d,TypeOfEdge w,edgeNode<TypeOfEdge> *ptr=NULL){
        
            data=d; weight=w; next=ptr;
        }
        int getData(){
         return data; }//取得结点的序号（顶点集）
        TypeOfEdge getWeight(){
         return weight; }//取得边集中对应边的权值
        void SetLink(edgeNode<TypeOfEdge> *link ){
         next=link; }//修改结点的next域
        void SetData(int value){
         data=value; }//修改结点的序号（顶点集）
        void SetWeight(TypeOfEdge value){
         weight=value; }//修改边集中对应边的权值
    };
    
    //图的邻接表类    这个结构体是存储顶点的结构体，里面包括顶点和它的下一个指针
    template<class TypeOfVer,class TypeOfEdge>
    struct verNode{
        
        TypeOfVer ver;//存放结点信息
        edgeNode<TypeOfEdge> *head;//顶点的指针
        verNode(edgeNode<TypeOfEdge> *h=NULL){
         head=h; }
        TypeOfVer getVer(){
         return ver; }//取得结点值（顶点集）
        edgeNode<TypeOfEdge> *getHead(){
         return head; }//取得对应的边表的头指针
        void setVer(TypeOfVer value){
         ver=value; }//设置结点值（顶点集）
        void setHead(edgeNode<TypeOfEdge> *value){
         head=value; }//设置对应的边表的头指针
    };
    
    template<class TypeOfVer,class TypeOfEdge>//顶点类型  边的类型
    class adjlist_graph{
        
        private:
           int Vers;//顶点数
           int Edges;//边数
           verNode<TypeOfVer,TypeOfEdge> *verList;
           string GraphKind;//图的种类标志
           bool Delete_Edge(int u,int v);
           bool DFS(int u,int num,int visited[]);//DFS遍历（递归部分）
        public:
           //构造函数构造一个只有结点没有边的图
           //3个参数的含义：图的类型、顶点数、结点值
           adjlist_graph(string kd,int vSize,TypeOfVer d[]){
        
                GraphKind=kd;
                Vers=vSize;
                verList=new verNode<TypeOfVer,TypeOfEdge> [Vers];
                for(int i=0;i<Vers;++i)
                    verList[i].ver=d[i];
           }
           //构造函数构造一个无权图
           //5个参数的含义：图的类型、结点数、边数、结点集和边集
           adjlist_graph(string kd,int vSize,int eSize,TypeOfVer d[],int **e);
           //构造函数构造一个有权图
           adjlist_graph(string kd,int vSize,int eSize,TypeOfVer d[],int **e,TypeOfEdge w[]);
           bool GraphisEmpty(){
         return Vers==0; }//判断图空否
           string GetGraphKind(){
         return GraphKind; }//返回图的类型
           int GetVerNum(){
         return Vers; }//取得当前顶点数
           int GetEdgeNum(){
         return Edges; }  //取得当前边数
           bool GetVer(int u,TypeOfVer &data){
        //取得G中指定顶点的值
    
           }
           int GetFirstAdjVex(int u,int v); //返回G中指定顶点u的第一个邻接顶点的位序（顶点集）。若顶点在G中没有邻接顶点，则返回-
           int GetNextAdjVex(int u,int v,int w); //返回G中指定顶点u的下一个邻接顶点（相对于v）的位序（顶点集）。若顶点在G中没有邻接顶点，则返回false
           bool PutVer(int u, TypeOfVer data); //对G中指定顶点赋值
           bool InsertVer(const TypeOfVer data); //往G中添加一个顶点
           int LocateVer(TypeOfVer data); //返回G中指定顶点的位置
           bool ExistEdge(int u,int v);
           //输出顶点集
           bool PrintVer(){
        
               for(int i=0;i<Vers;++i){
        
                    if(i==0)
                        cout<<verList[i].ver;
                    else
                        cout<<" "<<verList[i].ver;
               }
               cout<<endl;
           }
           //输出邻接表
           bool PrintAdjList(){
        
                for(int i=0;i<Vers;++i){
        
                    cout<<verList[i].ver<<"->nullptr"<<endl;
                    //if(verList[i].ver)
                }
           }
           bool Insert_Edge(int u,int v); //无权图插入一条边
           bool Insert_Edge(int u,int v,TypeOfEdge w);//有权图插入一条边
           bool DeleteVer(const TypeOfVer data);//往G中删除一个顶点
           bool DeleteEdge(int u,int v);//删除边 (外壳：有向（删除1条边）， 无向（删除2条边））
           void DFS_Traverse(int u);//DFS遍历（外壳部分）
           void BFS_Traverse(int u);//BFS遍历
           //~adjlist_graph(); //析构函数
    };
    
    template<class TypeOfVer,class TypeOfEdge>
    void shuchu(adjlist_graph<TypeOfVer,TypeOfEdge> &tu,int n){
        
        cout<<tu.GetGraphKind()<<endl;
        TypeOfVer x;
        //TypeOfEdge we;
        //we=tu.GetEdgeNum();//返回第一个边数
        tu.PrintVer();
        //cout<<endl<<we<<endl;
        tu.PrintAdjList();//输出邻接表
    }
    
    int main(){
        
        string str;//图的类型
        getline(cin,str);
        int n,m;//顶点数和边数
        cin>>n;
        for(int i=0;i<n;++i)
            cin>>b[i];//顶点集合
        adjlist_graph<string,int> tu(str,n,b);
        shuchu(tu,n);
        return 0;
    }

这个题可以看见，我写的输出邻接表就是每个直接输出顶点是啥，然后后面跟个箭头和nullptr。因为我还没搞明白这个题如果真正输出顶点后面的链表怎么输出，所以我就直接写的输出顶点和nullptr。  
这样写可以AC，因为毕竟可以电脑根据输入可以自己做出判断，但是有一些用暴力就解决的题目，那它的判断就是像机械一样的判断了，比如说打表，把所有可能的情况都列出来，只要答案正确，肯定会AC。  
所以我还是觉得如果人工智能没有发展到人类大脑的程度，那它就是人工制杖。但我还是希望人工智能不要发展到人的阶段，因为那样不知道未来会发生什么。我希望人类只是把人工智能作为自己的工具，只做到为人类服务就够了。

#### 对2个结构体和1个类的解释 ####

第一个结构体是edgeNode，这个代表  
![在这里插入图片描述][7f605ae5ff1546718760003618c998e7.png_pic_center]  
图片里圈红色的那个，代表一个顶点的所有邻接顶点构成的链表上的结点。  
data代表的应该是相邻顶点的下标，weight是网的权值，next是指向下一个结点的指针。

第二个结构体是verNode，它代表顶点的信息  
![在这里插入图片描述][5ffb83b82cfe44a2855ac3c9ffce1ea2.png_pic_center]  
绿色圈圈里面的，它有储存顶点的ver,和指向第一个边结点的指针。

类就是指邻接表的类了  
![在这里插入图片描述][c971d10fa759492689c0ea5bd3c8b52d.png_pic_center]  
就是整个这个表。  
因为表的内部有顶点的信息还有边结点的信息，所以要先把前2个都结构体都定义好，之后再写邻接表这个类才完整。

[7f605ae5ff1546718760003618c998e7.png_pic_center]: https://img-blog.csdnimg.cn/7f605ae5ff1546718760003618c998e7.png#pic_center
[5ffb83b82cfe44a2855ac3c9ffce1ea2.png_pic_center]: https://img-blog.csdnimg.cn/5ffb83b82cfe44a2855ac3c9ffce1ea2.png#pic_center
[c971d10fa759492689c0ea5bd3c8b52d.png_pic_center]: https://img-blog.csdnimg.cn/c971d10fa759492689c0ea5bd3c8b52d.png#pic_center