c++ - 使用链表的图形表示

Question

在将边添加到某个配对顶点时，我在试图弄清楚如何正确获取指针时遇到了一些麻烦。

下面是一个关于在顶点和节点输入完成后链表应该是什么样子的简短想法。

我怎样才能保持邻居列表的顺序？如果当前顶点中已经存在顶点边，是否应该存在另一种情况？

这是我试图构建的结构化类：

class graph{
private:
    typedef struct node{
        char vertex;
        node * nodeListPtr;
        node * neighborPtr;

    }* nodePtr;
    nodePtr head;
    nodePtr curr;
public:
    graph();
    ~graph();

    void AddNode(char AddData);
    void AddEdge(char V, char E);
    void printList();
};

graph::graph(){
    head = NULL;
    curr = NULL;
}

// Adds a node to a linked list
void graph::AddNode(char AddData){
    nodePtr n = new node;
    n->nodeListPtr = NULL;
    n->vertex = AddData;

    if(head != NULL){
        curr = head;
        while(curr->nodeListPtr != NULL){
            curr = curr->nodeListPtr;
        }
        curr->nodeListPtr = n;
    }
    else{
        head = n;
    }
}

// takes 2 Parameters (V is pointing to E)
// I want to set it up where the neighborptr starts a double linked List basically
void graph::AddEdge(char V, char E){
    // New Node with data
    nodePtr n = new node;
    n->neighborPtr = NULL;
    n->vertex = E;
    // go to the first node in the nodeList and go through till you reach the Vertex V
    curr = head;
    while(curr->vertex != V){
        curr = curr->nodeListPtr;
    }
    //Once the Vertex V is found in the linked list add the node to the neighborPtr.
    curr->neighborPtr = n;

}

Answer 1

您当前遇到的一个问题是每个节点只能有一个“边缘”节点。在您的插图中，节点 A、C 和 D 都是可能的，但节点 B 并非没有做一些不同的事情。

问题发生在这里：

curr->neighborPtr = n;

每次调用 AddEdge() 到同一个顶点时，它都会简单地覆盖该顶点的neighborPtr。在找到空指针之前，您不会尝试遍历neighborPtrs。

考虑添加另一个 while 循环以递归地添加边：

while (curr->neighborPtr != null)
    curr = curr->neighborPtr;
curr->neighborPtr = n;

请注意，这不是代码中的唯一问题；你有几个地方应该防范空指针，而不是。例如：在 AddEdge() 中，如果找不到顶点 V 会发生什么？你是在它已经被创建的假设下行动的。如果没有，您最终会遇到一些空指针错误。如果您要尝试制作除功能之外还具有健壮性的代码，请记住这一点。