Segfault при рекурсивном поиске связанного списка в c ++

Question

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

class Header
{
protected:
 //Create the struct for the list
 struct ListNode {
   double x;
   ListNode *next;
   ListNode(double v1, ListNode *n1 = nullptr) {
     double x = v1;
     next = n1;}
 };
 ListNode *head;

public:
 Header()
 {head = nullptr;}

 //Add doubles to the list
 void add(double var) {
  if(head == nullptr)
  {head = new ListNode(var);}

  else {
    ListNode *nodePtr = head;

    while(nodePtr->next != nullptr)
    {nodePtr = nodePtr->next;}

    nodePtr->next = new ListNode(var);
  }
 }

 //Call the function that performs the recursive function
 void recursiveMember(double var) const 
 {recursiveMember(head, var);}

private:
 //This is where the issue is
 void recursiveMember(ListNode *aList, double var) {
   if(aList == nullptr)
   {cout << var << " is not in the list" << endl;}

   if(var != aList->x)
   {recursiveMember(aList->next, var);}

   else
   {cout << var << " is in the list" << endl;}
 }
};

int main()
{
  //Create the object
  Header vars;

  //Populate the object
  vars.add(1.1);
  vars.add(2.2);
  vars.add(3.3);

  //Call the recursive function
  vars.recursiveMember(1.1);
  vars.recursiveMember(.5);

  return 0;
}

Программа отображает

1.1 is in the list
.5 is not in the list
Segmentation fault (core dumped)

Это не обязательно будет проблемой, но есть некоторые другие функции, которые мне нужно выполнить после, и из-за segfault программа взломает sh перед выполнением этого.

Я использовал отладчик gdb для изоляции кода, вызывающего ошибку, а именно if(var != aList->x) для реализации рекурсивной функции.

Есть ли что-то в рекурсии, которую мне не хватает?

Answer 1

Вам необходимо вернуться из функции recursiveMember, если aList равно nullptr. В противном случае вы получаете доступ к недопустимым узлам.

if(aList == nullptr)
{
  cout << var << " is not in the list" << endl;
  return;
}

Эквивалентно, вы можете условно ввести вторую ветвь if

if(aList == nullptr)
{
  cout << var << " is not in the list" << endl;
}
else if(var != aList->x)
// ...

Кроме того, в конструкторе ListNode вы не назначаете данные правильно

ListNode(double v1, ListNode *n1 = nullptr) {
     double x = v1;   // this x is a local variable
     next = n1;
}

Вместо этого вам необходимо присвоить member x.

ListNode(double v1, ListNode *n1 = nullptr) {
     x = v1;   // this x is the member
     next = n1;
}

Answer 2

Для начала вы не можете вызывать непостоянную функцию-член из постоянной функции-члена. Таким образом, функция должна быть объявлена ​​как минимум как

void recursiveMember(ListNode *aList, double var) const;

Во-вторых, закрытая функция-член принимает в качестве аргумента указатель на головной узел, так как она должна быть объявлена ​​как stati c функция-член

static void recursiveMember(ListNode *aList, double var);

И в-третьих, обе функции private и publi c не должны выводить никаких сообщений. Вызывающая функция решает, выводить ли что-нибудь. Функция должна возвращать логическое значение.

Таким образом, первая функция должна быть объявлена ​​как

bool recursiveMember( double var ) const 
{
    return recursiveMember( head, var);
}

, а вторая функция должна быть объявлена ​​как

static bool recursiveMember( const ListNode *aList, double var);

Далее, Если текущее значение указателя aList равно nullptr, тем не менее, вы пытаетесь использовать его для доступа к памяти во втором операторе if

if(var != aList->x)
{recursiveMember(aList->next, var);}

То есть, нет возврата из функции в случай, когда aList равен nullptr.

if(aList == nullptr)
{cout << var << " is not in the list" << endl;}

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

static bool recursiveMember( const ListNode *aList, double var ) 
{
    if ( aList == nullptr )
    {
        return false;
    }
    else if ( a:ist->var != var )
    {
        return recursiveMember( aList->next, var );
    }
    else
    {
        return true;
    }
}

И в основном вы должны проверить возвращаемое значение Вызвать функцию и вывести соответствующее сообщение.

Обратите внимание на то, что в конструкторе вы используете локальную переменную x вместо члена данных x

   ListNode(double v1, ListNode *n1 = nullptr) {
     double x = v1;
     next = n1;}

Должно быть

   ListNode(double v1, ListNode *n1 = nullptr) {
     x = v1;
     next = n1;}