Почему эта функция не может реверсировать связанный список?

Я хочу изменить связанный список, но когда я компилирую этот код, он неожиданно завершается.

#include <bits/stdc++.h>
using namespace std;

class node{
public:
    int data;
    node* next;

    node(int val){
    data=val;
    next=NULL;
        }
};

Для вставки элементов в связанный список

void insertattail(node* &head,int lol){
    node* n= new node(lol);
    if (head==NULL){
        head=n;
        return;
    }
    node* temp=head;
    while(temp->next!=NULL){
        temp=temp->next;
    }
    temp->next=n;
}

Функция отображения для печати связанного списка

void display(node* head){
    node* temp =head;
    do{
        cout<<temp->data<<"->";
        temp=temp->next;
    }
    while(temp!=NULL);
    cout<<"Null";

}

Функция для реверсирования связанного списка

node* reverseit(node* head){
    node* prevptr= NULL;
    node* currptr= head;
    node* nextptr= currptr->next;
    while(currptr!=NULL){
        currptr->next =prevptr;
        prevptr=currptr;
        currptr=nextptr;
        nextptr=currptr->next;
    }
    return prevptr;
}

Основная функция

int main()
{
    node* head= NULL;
    insertattail(head,1);
    insertattail(head,2);
    insertattail(head,3);
    insertattail(head,8);
    node* newhead= reverseit(head);
    display(newhead);
    return 0;
}

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

не заставляйте нас делать предположения о вашем коде. Вместо этого предположим, что мы ничего не знаем о коде, который вы нам не показываете, поэтому весь код, необходимый для воспроизведения проблемы, должен быть включен в вопрос. Читать о минимальный воспроизводимый пример

463035818_is_not_a_number 05.05.2022 14:17

Он немедленно терпит неудачу в пустом списке.

molbdnilo 05.05.2022 14:19

Нет, мы не можем считать, что «все остальные функции верны». Тот факт, что именно здесь программа дает сбой или сообщает об ошибке, не означает, что проблема именно в этом. С++ так не работает. Проблема может быть в другом месте, но после возникновения ошибки программа продолжает работать, пока не вылетит здесь. Вот почему центр помощи на stackoverflow.com требует, чтобы вы показали минимальный воспроизводимый пример, чтобы все остальные могли вырезать/вставить точно так, как показано, а затем скомпилировать, запустить и воспроизвести вашу проблему. См. Как спросить для получения дополнительной информации. Пока вы этого не сделаете, маловероятно, что кто-то сможет разобраться в вашей проблеме.

Sam Varshavchik 05.05.2022 14:19

Что тебе сказал отладчик?

Jabberwocky 05.05.2022 14:22

Кроме того, почему это помечено c++? Нет видимых функций C++.

Spencer 05.05.2022 14:23

Предположим, что nextptr — это нулевой указатель (то есть вы достигли последнего узла списка), а затем подумайте, что происходит в currptr=nextptr; nextptr=currptr->next;

molbdnilo 05.05.2022 14:25
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
6
50
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Функция вызывает неопределенное поведение.

Например, давайте сначала предположим, что список пуст. То есть указатель head равен nullptr. В этом случае использование этой строки перед циклом while внутри функции

node* nextptr= currptr->next;

обращается к памяти с помощью нулевого указателя.

Или рассмотрим другой пример, когда current->next равно nullptr. В этом случае nextptr будет равно nullptr и в цикле while эти операторы

    currptr=nextptr;
    nextptr=currptr->next;

снова получить доступ к памяти с помощью нулевого указателя.

И объявления многих указателей перед циклом while

node* prevptr= NULL;
node* currptr= head;
node* nextptr= currptr->next;

делает код менее читаемым и понятным.

Функция может быть определена следующим образом

node * reverseit( node *head )
{
    node *new_head = nullptr;

    for ( node *current = head; head != nullptr; head = current )
    {
        current = head->next;
        head->next = new_head;
        new_head = head;
    }

    return new_head;
}

Если на самом деле ваша программа написана на C, то вместо nullptr используйте NULL.

Также в main нет необходимости вводить новый указатель newhead

node* newhead= reverseit(head);

Вы могли бы просто написать

head = reverseit(head);

Функция display может снова вызвать неопределенное поведение, если переданный указатель на головной узел равен nullptr. А параметр функции должен иметь квалификатор const, потому что внутри функции сам список не изменяется.

Функция может быть определена следующим образом

std::ostream & display( const node *head, std::ostream &os = std::cout )
{
    for ( const node *current = head; current != nullptr; current =current->next )
    {
        os << current->data << " -> ";
    }

    return os << "Null";
}

И функция может быть вызвана как

display( head ) << '\n';
Ответ принят как подходящий

Ваша инициализация и «приращение» nextptr (потенциально/в конечном итоге) разыменовывают NULL значение currptr. Вы должны инициализировать nextptr на NULL и изменить его на «реальный» только в том случае, если currptr не NULL; таким образом, его (пере)назначение должно быть в Начало цикла, а не в конец:

node* reverseit(node* head){
    node* prevptr = nullptr;
    node* currptr = head;
    node* nextptr = nullptr; // Don't assume a non-NULL currptr
    while (currptr != nullptr) {
        nextptr = currptr->next; // Safe here: save next
        currptr->next = prevptr; // Do the reversal here
        prevptr = currptr;       // Step forward through
        currptr = nextptr;       // the list (prev/curr)
    //  nextptr = currptr->next; // WRONG HERE: currptr will be NULL at some point
    }
    return prevptr;
}

Итак, дело в том, что если наш currptr равен нулю, мы не можем сделать nextptr=currptr->next; Правильно?

Saransh Kumar 05.05.2022 14:50

@SaranshKumar Точно. Попытка разыменовать нулевой указатель является поведением undefined. Это почти всегда приводит к сбою программы.

Adrian Mole 05.05.2022 14:51

Другие вопросы по теме