Ошибка сегмента: функция вставки узла связанного списка [C ++] - PullRequest
Новая
       39

Ошибка сегмента: функция вставки узла связанного списка [C ++]

0 голосов
/ 26 июня 2019

Я создал функцию «Вставить» для вставки нового узла в связанный список.Он принимает значение и головной узел для вставки.Когда я сам добавляю узлы вручную, программа запускается, как и ожидалось, однако у меня возникает ошибка сегментации, когда я использую функцию для добавления узла.

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

Я выполняю настройку: 

Change Line 26 to: A->next = NULL;
Change Line 17 to: while(temp->next != NULL)

«Ошибка сегментации» возникает в строке 20 (когда настройка не выполнена): 

Line 20 ----->  temp->next = addTo;

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

Я приложил полный код ниже: 

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

struct ListNode {
int data;
ListNode *next;
};

void Insert(int x , ListNode* head)
{
    ListNode* addTo = new ListNode();
    addTo->data = x;
    addTo->next = NULL;

    ListNode* temp;
    temp = head;
    while(temp != NULL)
    temp = temp->next;

    temp->next = addTo;
}

int main()
{
    ListNode* A;
    A = NULL;

    //Inserting A Node Manually
    // ListNode* first = new ListNode();
    // first->data = 9;
    // first->next = NULL;
    // while(A != NULL)
    // A = A->next;
    //     A = first;

    //Inserting using Insert function.
   Insert(2,A);Insert(3,A);Insert(6,A);Insert(7,A);

    //Printing
    ListNode* temp = A;
    while(temp != NULL)
    {
        cout << temp->data << " ";
        temp = temp->next;
    }
    return 0;
}

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

Любая помощь / понимание этого очень помогло бы.

Спасибо.

1 Ответ

4 голосов
/ 26 июня 2019

Задача 1: 

while(temp != NULL)
temp = temp->next;

temp->next = addTo;

Гарантирует, что temp будет NULL при выходе while(temp != NULL). это означает, что нет temp, чтобы получить next от.

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

Задача 2: 

void Insert(int x , ListNode* head)

не оставляет возможности обновить вызывающего, если head изменяется в функции Insert. Вы можете изменить объект, на который указывает head, но head сам по себе является просто копией адреса. Если вы измените эту копию, чтобы она указывала на другой адрес, звонящий не будет знать.

Это означает, что каждый раз, когда вы звоните Insert(<number>, A);, A всегда будет NULL.

Решение:

Передайте head в Insert по ссылке, чтобы его можно было обновить. 

void Insert(int x , ListNode*& head)
                             ^ reference to pointer
Работа

head - указывать на первый элемент в списке. Это означает, что он делает то же самое, что и любой указатель next: он указывает на следующий элемент. Разница только в названии. Мы можем избавиться от этой разницы, добавив дополнительную косвенную ссылку, указатель на head. 

ListNode ** temp = &head;

Обратите внимание, что здесь мы не можем использовать ссылку (ListNode *& temp), поскольку после инициализации ссылки для ссылки на объект ее нельзя изменить для ссылки на другой объект. Указатель, который вы можете изменить, позволяя нам перебирать список и всегда указывать temp на следующий next.

Теперь head или любой next - это просто temp. Это делает head точно таким же, как и для любой другой переменной next, и особых случаев не требуется. 

void Insert(int x , ListNode*& head)   
{
    ListNode* addTo = new ListNode(); 
    addTo->data = x;
    addTo->next = NULL; // consider making a smarter ListNode constructor that makes 
                        // it impossible to forget to set next.

    ListNode ** temp = &head; // we can now manipulate the address in head through temp

    while(*temp != NULL) // note the dereference to get the pointed at pointer
                         // temp won't be null, but it could be pointing at a pointer 
                         // that is null, and that is the end of the list
    { // I always use the optional braces. They prevent confusion.
        temp = &(*temp)->next; //get pointer to the next next pointer
                               // we can now manipulate it exactly the same as head. 
    }
    // we exit the loop with a pointer to the next pointer that we wish to point at 
    // the new list item regardless of whether it's head or the next of some later
    // link in the list
    *temp = addTo; // update the pointed at pointer with the new Node.
}

Сообщество Добавление первого ответа Как правильно удалить узлы связанного списка в C ++ демонстрирует, как использовать один и тот же трюк указатель-указатель, чтобы упростить удаление узлов.

...