c++ - 双向链表中的指针无法正常工作

Question

我想生成一个由用户选择的固定长度的随机双向链表。

列表会在头部插入第一个值，然后在列表末尾插入所有其他值，但它没有正确调整指针。

头节点和尾节点都在 main 中初始化为 NULL。

随机值有效，问题出在指针上，因为在第二次迭代中，尾部与头部保持相同，这意味着列表没有增加。

void GenRandSeq(struct Node* &head, struct Node* &tail, int len){
    int i = 0;

    std::mt19937 rng;
    std::uniform_int_distribution<uint32_t> uint_dist(0,10000);

    while (i < len){
        Node* newNode = new Node();
        int new_el = uint_dist(rng);
        newNode->key = new_el;
        newNode->prev = NULL;
        newNode->next = NULL;

        if (head == NULL){

            tail = newNode;
            head = newNode;
        }

        else{

            if (tail != NULL){
                newNode->next = NULL;
                newNode->prev = tail;
                tail->next = newNode;
            }
            else
                tail = newNode;
        }
        i++;
    }
}

我没有看到我在代码中遗漏了什么。

Answer 1

您没有正确设置 tail。

当 head 和 tail 都不为空时(当列表不为空时应该始终为 true)，您没有更新 tail 指向新创建的节点。 tail 的赋值需要移出 else 语句。您正在将新节点附加到列表的末尾，因此tail必须在每个循环迭代中更新。

尝试更像这样的东西:

void GenRandSeq(Node* &head, Node* &tail, int len){
    std::mt19937 rng;
    std::uniform_int_distribution<uint32_t> uint_dist(0,10000);

    while (len > 0){
        Node* newNode = new Node;
        newNode->key = uint_dist(rng);
        newNode->prev = tail;
        newNode->next = nullptr;
        if (!head){
            head = newNode;
        }
        if (tail){
            tail->next = newNode;
        }
        tail = newNode;
        --len;
    }
}

然后可以通过消除循环内的 if 语句进一步简化:

void GenRandSeq(Node* &head, Node* &tail, int len){
    std::mt19937 rng;
    std::uniform_int_distribution<uint32_t> uint_dist(0,10000);

    Node **next = (tail) ? &(tail->next) : &head;

    while (len > 0){
        Node *newNode = new Node;
        newNode->key = uint_dist(rng);
        newNode->prev = tail;
        newNode->next = nullptr;
        *next = newNode;
        tail = newNode;
        next = &(newNode->next);
        --len;
    }
}