邻接表：构造只有顶点没有边的图（DHU---oj）

题目

目的：使用C++模板设计并逐步完善图的邻接表抽象数据类型（ADT）。

内容：（1）请参照图的邻接矩阵模板类原型，设计并逐步完善图的邻接表ADT。（由于该环境目前仅支持单文件的编译，故将所有内容都集中在一个源文件内。在实际的设计中，推荐将抽象类及对应的派生类分别放在单独的头文件中。）

（2）使用构造函数，构造一个只有结点没有边的图。

注意：DG（有向图）, DN（有向网）, UDG（无向图）, UDN（无向网）

参考函数原型：

//构造函数构造一个只有结点没有边的图。3个参数的含义：图的类型、结点数、结点值 

template

adjlist_graph::adjlist_graph( const string &kd, int vSize, const TypeOfVer d[]);

//图的邻接表模板类原型参考如下：

template
struct edgeNode{
    int data;
    TypeOfEdge weight;
    edgeNode *next;
    edgeNode(const int &d, edgeNode *ptr = NULL) //构造函数，用于构造其他结点（无权图） 
    //函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面
    {

        next = ptr;

        data = d;

    }

    edgeNode(const int &d, const TypeOfEdge &w, edgeNode *ptr = NULL) //构造函数，用于构造其他结点（带权图） 

    //函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面

    {

        next = ptr;

        data = d;

        weight = w;

    }

    int getData(){ return data;}  //取得结点的序号（顶点集） 

    TypeOfEdge getWeight(){ return weight;}  //取得边集中对应边的权值 

    void SetLink( edgeNode *link ){ next = link; }  //修改结点的next域 

    void SetData( int value ){ data = value; }   //修改结点的序号（顶点集） 

    void SetWeight(TypeOfEdge value ){ weight = value; }   //修改边集中对应边的权值   

};



//图的邻接表类

template

struct verNode

{

    TypeOfVer ver;

    edgeNode *head;

    

    verNode(edgeNode *h = NULL){head = h;} 

    TypeOfVer getVer(){ return ver;}  //取得结点值（顶点集） 

    edgeNode *getHead(){ return head;}  //取得对应的边表的头指针 

    void setVer(TypeOfVer value){ ver = value;}  //设置结点值（顶点集） 

    void setHead(edgeNode *value){ head = value;}  //设置对应的边表的头指针



};



template 

class adjlist_graph{

    private:

       int Vers;           //顶点数 

       int Edges;          //边数 

       verNode *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
#include
#include
#include
#include
#include
#include
using namespace std;
string b[10001];//用来存放顶点集
//DG（有向图）  DN（有向网）  UDG（无向图） UDN（无向网）

//图的邻接表模板类原型参考如下：

template//这个就是在边上的结点定义
struct edgeNode{
    int data;
    TypeOfEdge weight;
    edgeNode *next;
    //构造函数，用于构造其他结点（无权图）
    //函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面
    edgeNode(int d,edgeNode *ptr=NULL){ data=d;next=ptr; }
    //构造函数，用于构造其他结点（带权图）
    //函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面
    edgeNode(int d,TypeOfEdge w,edgeNode *ptr=NULL){
        data=d; weight=w; next=ptr;
    }
    int getData(){ return data; }//取得结点的序号（顶点集）
    TypeOfEdge getWeight(){ return weight; }//取得边集中对应边的权值
    void SetLink(edgeNode *link ){ next=link; }//修改结点的next域
    void SetData(int value){ data=value; }//修改结点的序号（顶点集）
    void SetWeight(TypeOfEdge value){ weight=value; }//修改边集中对应边的权值
};

//图的邻接表类    这个结构体是存储顶点的结构体，里面包括顶点和它的下一个指针
template
struct verNode{
    TypeOfVer ver;//存放结点信息
    edgeNode *head;//顶点的指针
    verNode(edgeNode *h=NULL){ head=h; }
    TypeOfVer getVer(){ return ver; }//取得结点值（顶点集）
    edgeNode *getHead(){ return head; }//取得对应的边表的头指针
    void setVer(TypeOfVer value){ ver=value; }//设置结点值（顶点集）
    void setHead(edgeNode *value){ head=value; }//设置对应的边表的头指针
};

template//顶点类型  边的类型
class adjlist_graph{
    private:
       int Vers;//顶点数
       int Edges;//边数
       verNode *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 [Vers];
            for(int i=0;i 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
                if(i==0)
                    cout<
            for(int i=0;i
                cout<nullptr"<
void shuchu(adjlist_graph &tu,int n){
    cout<
    string str;//图的类型
    getline(cin,str);
    int n,m;//顶点数和边数
    cin>>n;
    for(int i=0;i>b[i];//顶点集合
    adjlist_graph tu(str,n,b);
    shuchu(tu,n);
    return 0;
}

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

第一个结构体是edgeNode，这个代表

图片里圈红色的那个，代表一个顶点的所有邻接顶点构成的链表上的结点。
data代表的应该是相邻顶点的下标，weight是网的权值，next是指向下一个结点的指针。

第二个结构体是verNode，它代表顶点的信息

绿色圈圈里面的，它有储存顶点的ver,和指向第一个边结点的指针。

类就是指邻接表的类了

就是整个这个表。
因为表的内部有顶点的信息还有边结点的信息，所以要先把前2个都结构体都定义好，之后再写邻接表这个类才完整。