samedi 6 juillet 2019

accessing data within an array of linear linked lists leads to segfault

I am trying to understand why I am getting a segfault when the "removeTwoHelpList" function is called. I am trying to alter an array of linear linked lists recursively. The program runs fine until The "removeTwoHelpList" function is called. If the "curr" variable is accessed, the function exits with a segfault.

I have tried passing the Head pointer element by a temporary node pointer variable.

main file

int main()
{
    table object; 
    object.build(); //creates an array of LLL
    object.display(); //displays the array

    //PLEASE PUT YOUR CODE HERE to call the functions

    cout << "Sum of all Integers: " << object.sum() << endl;    

    cout << "After removing  all 2: " << endl << object.removeTwo() 
         << " 2's removed" << endl;

    object.display();  //display again afterward!    
    return 0;
}

arr.h file

#include <iostream>
#include <cstring>
#include <cctype>

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

class table
{
    public:
    /* These functions are already written */
       table();     //supplied
       ~table();    //supplied
       void build();    //supplied
       void display();  //supplied


    /* *****************YOUR TURN! ******************************** */
    //Write your function prototype here:
    int sum() const;        
    int removeTwo();

    private:
       node ** head;     //dynamically allocated array
       int size;     //the array size

    //private helper functions
    int sumHelp(int ind) const;
    int sumHelpList(node * curr) const;
    int removeTwoHelp(int ind);
    int removeTwoHelpList(node * curr, node * prev, int ind);
};

arr.cpp file

//remove two and helpers
int table::removeTwo()
{ 
    return removeTwoHelp(0);
}

int table::removeTwoHelp(int ind)
{
    //terminating
    if (size <= ind)
        return 0;

    if ( head[ind]  == nullptr)
    {
        return removeTwoHelp(ind + 1);
    }
    else
    {           
            return removeTwoHelpList(head[ind], nullptr, ind) + removeTwoHelp(ind + 1);
        }
    }
int table::removeTwoHelpList(node * curr, node * prev, int ind)
{
    //case end of list or empty
    if (curr = nullptr)
        return 0;
    /*ISSUE HERE accessing data of pointer*/
    cout << "curr data = " << curr->data << endl;
    return 1;
}

I expect to remove all 2's from the linear linked lists and output the number of nodes deleted, but I get a segfault.

==17576== Invalid read of size 4
==17576==    at 0x400E21: table::removeTwoHelpList(node*, node*, int) (in
/home/student/user/cs261/labs/lab2/Lab2)
==17576==    by 0x400D9A: table::removeTwoHelp(int) (in
/home/student/user/cs261/labs/lab2/Lab2)
==17576==    by 0x400CE6: table::removeTwo() (in
/home/student/user/cs261/labs/lab2/Lab2)
==17576==    by 0x400F20: main (in /home/student/user/cs261/labs/lab2/Lab2)
==17576==  Address 0x0 is not stack'd, malloc'd or (recently) free'd
==17576==
==17576==
==17576== Process terminating with default action of signal 11 (SIGSEGV)
==17576==  Access not within mapped region at address 0x0
==17576==    at 0x400E21: table::removeTwoHelpList(node*, node*, int) (in
/home/student/user/cs261/labs/lab2/Lab2)
==17576==    by 0x400D9A: table::removeTwoHelp(int) (in
/home/student/user/cs261/labs/lab2/Lab2)
==17576==    by 0x400CE6: table::removeTwo() (in
/home/student/user/cs261/labs/lab2/Lab2)
==17576==    by 0x400F20: main (in /home/student/user/cs261/labs/lab2/Lab2)

An interesting thing about this issue is that the sum function works great and I reused that code for data structure traversal for the problem function. Also note that I do not have the source code for the building of the data structure, my teacher gave use a .o file for that.

Code for working sum function

int table::sum() const
{
    return sumHelp(0);  
}
int table::sumHelp(int ind) const
{
    if(ind >= size)
        return 0;

    return sumHelpList(head[ind]) + sumHelp(ind +1);
}
int table::sumHelpList(node * curr) const
{
    if(curr == nullptr)
        return 0;
    if(curr->next == nullptr)
        return curr->data;

    return curr->data + sumHelpList(curr->next);
}

Aucun commentaire:

Enregistrer un commentaire