使用Linked-List的图表表示

Question

我在尝试找出如何在向某个配对顶点添加边缘时正确获取指针时遇到一些麻烦。

下面是关于在输入顶点和节点之后链表应如何显示的简短概念。

我怎样才能在neighborList上保持秩序？如果当前顶点中已存在顶点边缘，是否还有其他条件？

下面是我试图构建的结构化类：

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会发生什么？您的行为是基于它已经创建的假设。如果没有，最终会出现一些空指针错误。如果您尝试制作功能强大的代码，请记住这一点。