双链表中的指针无法正常工作

Question

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

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

头部和尾部节点都在主要到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;
    }
}