вставить узел в n-ю позицию одного связанного списка - PullRequest
Новая
       7

вставить узел в n-ю позицию одного связанного списка

0 голосов
/ 23 сентября 2018

Я пытаюсь создать функцию insert_at_position для одного связанного списка, но получаю ошибку памяти для случая, когда я вставляю новый узел в конец списка.

Это мой код: 

#include <iostream>
#include <memory>
#include <utility>

struct Node {
    int data;
    std::unique_ptr<Node> next = nullptr;

     Node(const int& x, std::unique_ptr<Node>&& p = nullptr)
        : data(x)
        , next(std::move(p)) {}

};
std::unique_ptr<Node> head = nullptr;
Node* tail = nullptr;

void print() {
    auto temp = head.get();
    while (temp) {
        std::cout << temp->data << " ";
        temp = temp->next.get();
    }
    std::cout << "\n";
}

void push_back(const int& theData) {
    std::unique_ptr<Node> newNode = std::make_unique<Node>(theData);

    if (!head) {
        head = std::move(newNode);
        tail = head.get();
    }
    else {
        tail->next = std::move(newNode);
        tail = tail->next.get();
    }
}

void push_front(const int& theData) {
    std::unique_ptr<Node> newNode = std::make_unique<Node>(theData);
    newNode->next = std::move(head);
    head = std::move(newNode);

    if (!tail) {
        tail = head.get();
    }
}

void insert_at_position(int pos, const int& theData) {
    if (pos == 1) {
        push_front(theData);
        return;
    }

    auto newNode = std::make_unique<Node>(theData);
    auto current = head.get();

    for (int i = 1; i < pos; i++) {
        current = current->next.get();
    }

    if (current != nullptr) {
        newNode->next = std::move(current->next);
        current->next = std::move(newNode);
    }
    else {
        push_back(theData);
    }
}

void pop_front() {
    head = std::move(head->next);
}

void pop_back() {
    if (!head) return;

    auto current = head.get();
    Node* previous = nullptr;

    if (current->next != nullptr) {
        previous = current;
        current = current->next.get();
    }

    if (previous != nullptr) {
        previous->next = nullptr;
    }

    else {
        head = nullptr;
    }

    tail = previous;
    previous->next = nullptr;
}

void erase(int pos, const int& theData) {

}

int main() {

    push_back(2);
    push_back(4);
    push_back(6);
    print();

    push_front(1);
    print();

    pop_front();
    print();

    /*pop_back();
    print();*/

    insert_at_position(1, 1);
    print();

    insert_at_position(8, 4);
    print();

    //insert_at_position(3, 2);
    //print();
 //

    std::cin.get();

}

В этот момент возникает ошибка: insert_at_position(8, 4); Моя логика идет после последнего оператора if для обработки случая, когда я вставляю в какую-то случайную позицию впосередине списка я буду в конце и, таким образом, вызову функцию push_back.

1 Ответ

0 голосов
/ 24 сентября 2018

insert_at_position(8, 4) пытается вставить в позицию 8, в список, который намного короче.Цикл внутри не имеет защиты для этого, и к счастью разыменовывает нулевой указатель при достижении конца списка.

...