Указатели в двусвязном списке работают некорректно - PullRequest
Новая
       19

Указатели в двусвязном списке работают некорректно

0 голосов
/ 27 апреля 2019

Я хочу создать случайный двусвязный список фиксированной длины, выбранный пользователем.

Список будет вставлять первое значение в заголовок, а затем все остальные значения в конец списка, но он не корректно корректирует указатели.

Головной и хвостовой узлы оба инициализируются в основном в 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++;
    }
}

Я не вижу, что мне не хватает в коде.

1 Ответ

2 голосов
/ 27 апреля 2019

Вы неправильно устанавливаете tail.

Когда head и tail оба не равны нулю (что всегда должно быть истиной, когда список не пуст), вы не обновляете 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;
    }
}
...