Segmentation Error in program... Cant Figure out why

[youngyou4]

This program is running and compiles, and prints out the information but its getting a segmentation fault somewhere in the program, i believe its in the insort1 and insort 2 but i'm not sure.

For this assignment, you will be creating a Linked List and Node class and coding a recursive insertion sort.
class Node

The definition for this class should be contained in a file called Node.h, while the implementation should be contained in a file called Node.cpp (or Node.cc if you prefer that extension).

The Link class (described below) is eventually going to need access to the private members of the Node class, therefore the Link class should be made a friend of the Node class. Before the definition for the Node class, put the line class Link; this just says that a class called Link exists. Inside of the class definition, indicate that the Link class is a friend of the Node class by putting the line friend class Link;.

For this class, you should have at least the following data members and constructor:
Data Members

This class should have two data members that are not available to the outside world. The first is an integer that represents the data field for a node. The second is a pointer to a Node object, which represents the link field for a node (the one that holds the address of the next Node in the linked list).
Constructor

This class should have one constructor. It takes two arguments: the first is an integer value that will be used to set the data field for the node, and the second is a pointer to a Node object that will be used to set the link field for the node. The second argument (the pointer) should have a default value of the null pointer.
class Link

The linked list class that is being created for this assignment is probably slightly different than the one discussed in class. Rather than inserting the nodes into the list in ascending/descending order based on a key field, the nodes in this list will be inserted based on a "subscript" value. Therefore there is no guarantee that the list will be sorted after a node has been inserted.

For this class, you should have at least the following data members and methods:
Data Members

This class should have two data members that are not available to the outside world. The first is an integer that represents the number of nodes contained in the list. The second is a pointer to a Node object that holds the address of the first node in the linked list.
Constructor

The constructor for this class takes no arguments. It should create an empty list by initializing the number of nodes to 0 and setting the pointer to the first node in the list to null.
Destructor

The destructor for this class should release the memory for every node in the list (NOT just the first node in the list).
Methods
size

This method returns the number of nodes in the linked list. It takes no arguments and returns an integer.
isEmpty

This method determines whether or not the linked list is empty. It takes no arguments and returns a boolean value: true if the linked list is empty or false if the linked list is not empty.
clear

This method is used to clear a linked list by releasing the memory for every node in the list and setting the number of nodes in the linked list to 0. It takes no arguments and returns nothing.
retrieve

This method is used to retrieve the value of a node located at a specific position. It takes two arguments: the first is an integer that indicates the position of the node (this is like a subscript for an array, therefore it is 0-based), the second argument is a reference to an integer, which will be used to pass back the value in the node at the specified position. It should return a boolean value that indicates whether or not a value was retrieved from the list.

If the list is empty, display an appropriate error message and do not retrieve any value.

If the specified position is invalid, display an appropriate error message and do not retrieve any value.

If the list is not empty and contains a node at the specified position, get the appropriate value from the list and pass it back using the second argument. To do this: create a pointer to a Node and initialize it to the beginning of the linked list; write a loop that will execute "position" number of times, where position is the first argument passed to the method. Inside of the loop, advance the pointer to the next node in the linked list. Using the second argument passed to the method, pass back the value at the current pointer position.

Don't forget to return the appropriate boolean value for each of the cases.
insert

This method is used to insert a value into the linked list at a specific position. It takes two arguments: the first is an integer that indicates the position to place the node (this is 0-based), the second is a reference to a constant integer, which is the value for the data field of the node to be inserted. It should return nothing.

If the position that is specified is invalid, then display an appropriate error message and do not alter the list.

If the position is valid, then create a Node that has a data field equal to the second argument. Now there are two cases that need to be handled. The first case is if the insert position is the 0th or first position in the linked list. In this case, insert the Node at the head of the list, making sure that the data member that holds the address of the first node is updated accordingly. The second case is if the node is going somewhere other than the first position of the linked this. For the second case, create two Node pointers (ptr and lagPtr) and initialize them to the beginning the linked list. lagptr will "lag" behind ptr to make insertion into the linked list easier. Write a loop that will execute "position" number of times, where position is the first argument passed to the method. Inside of the loop, set lagPtr to ptr and advance ptr to the next node in the linked list. Outside of the loop, insert the new Node between lagPtr and ptr.

Don't forget that the count of the number of nodes in the linked list also needs to be updated.
remove

This method is used to remove a node from the linked list. It takes two arguments: the first is an integer that indicates the position (0-based) of the node to remove from the list, the second is a reference to an integer, which will be used to pass back the value in the node that is being removed. It should return nothing.

If the list is empty, display an appropriate error message and do not remove any value.

If the specified position is invalid, display an appropriate error message and do not alter the list.

If the position is valid, then use the retrieve function to get the value at the specified position and pass it back using the second method argument. As with insertion, the same two cases need to be handled. If the first node is the one to be deleted, move the head pointer to the 2nd node in the linked list and delete the node that used to be first in the list (you'll need a pointer to a Node to be able to do this). For the second case, create two Node pointers (ptr and lagPtr) and initialize them to the beginning the linked list. lagPtr will "lag" behind ptr to make deletion from the linked list easier. Write a loop that will execute "position" number of times, where position is the first argument passed to the method. Inside of the loop, set lagPtr to ptr and advance ptr to the next node in the linked list. Once the loop has executed, ptr will have the address of the node to be removed from the linked list.

Don't forget that the count of the number of nodes in the linked list also needs to be updated.
void traverse(void (*funcptr) (int &, int), int numElements)

This method processes nodes in a linked list. It takes two arguments: the first (highlighted in blue above) is a pointer to a function that takes two arguments (a reference to an integer and an integer) and returns nothing, and the second (highlighted in red) is an integer, which represents the total number of nodes in the list that should be processed. The method returns nothing.

What is done to a node in the list is going to depend on the function that is passed in when traverse is called. The idea here is to write a generic function that will call another function to perform the work on a node. So this function should call the passed in function (using the pointer) numElements number of times.

To call the function using the function pointer:

(*funcptr)( ptr->data, numElements );

assuming that "ptr" is a pointer to a Node object and that "data" is the name of the integer data member in the Node class.
insort1

This method performs a recursive ASCENDING order insertion sort. It takes one argument, an integer that represents the number of nodes in the list to be sorted, and returns nothing.

If the number of nodes is greater than 1, then perform a recursive call passing a reduced size.

For the base case, remove the element from the list that is supposed to be placed in its sorted position (lets call it elementN) (keep in mind that when this starts executing, the number of elements will be 1 but the first value in the linked list is at position 0). Loop through the portion of the list that has already been sorted (ie. all of the values that were before elementN originally) until the correct position for elementN is found. Now insert elementN into the correct position.
insort2

This method is just like insort1 except that the size and contents of the portion of the list being sorted will be printed before removing elementN from the list. This will be done by calling traverse and passing it the address of the print_entry() function described below. This call will resemble:

traverse(print_entry, N);

where N is number of items in the portion of the list that is being processed. After inserting elementN into the correct position, call the traverse function a second time.

Note: make sure and put a prototype for the print_entry() function in the Link.cpp (or .cc) file so that it knows that it exists. But DO NOT implement print_entry() in Link.cpp (or .cc). It will be done in assign7.cpp (or .cc).


That is the program assignment...

When i tried to debug the program in Dev... It showed that the fault was coming from insert but that doesnt make any sense because the insert is working. I don't get it. If anyone can help or can see what i'm doing wrong it would help a lot. Been working on this program for way to long.

[youngyou4]

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <fstream>

#include "Link.h"

using namespace std;

void print_entry(int &, int);





Link::Link()
{
nodes = 0;
head = NULL;
}


Link::~Link()
{
clear();
}


int Link::size()
{
return nodes;
}



bool Link::isEmpty()
{
if(nodes == 0)
{
return true;
}
else
{
return false;
}
}


void Link::clear()
{
while(head)
{
Node *temp;

temp = head;
head = head->next;

delete temp;
}

}



bool Link::retrieve(int pos, int & val)
{
Node * temp;

if(isEmpty())
{
cout << "The List is empty" << endl;
return false;
}
else if(size() < pos || pos < 0)
{
cout << "Invalid Position" << endl;
return false;
}
else
{
temp = head;

for(int i = 0; i < pos; i++)
{
temp= temp->next;
}

val = temp->data;
return true;
}
}




void Link::insert(int pos, const int & val)
{
if(size() < pos || pos < 0)
{
cout << "Invalid Position" << endl;
}
else
{
Node * temp;

if(pos == 0)
{
temp = new Node(val);
temp->next = head;
head = temp;
nodes++;
}
else
{
Node * ptr = head;
Node * lagPtr = head;

temp = new Node(val);


for(int i = 0; i < pos; i++)
{
lagPtr = ptr;
ptr = ptr -> next;
}

lagPtr->next = temp;
temp->next = ptr;
nodes++;
}
}
}

void Link::remove(int pos, int & val)
{
if(isEmpty())
{
cout << "The List is Empty" << endl;
}
else if(size() < pos || pos < 0)
{
cout << "Invalid Position" << endl;
}
else
{
if(pos == 0)
{
retrieve(pos, val);
Node * temp;
temp = head;
head = temp->next;
delete temp;
}
else
{
Node * ptr = head;
Node * lagPtr = head;

for(int i = 0; i < pos; i++)
{
lagPtr = ptr;
ptr = ptr->next;
}

lagPtr = ptr->next;
delete ptr;
nodes--;
}
}
}



void Link::traverse(void(*funcptr)(int &, int), int numElements)
{
Node * temp = head;

for(int i = 0; i < numElements; i++)
{
(*funcptr)(temp->data, numElements);
temp = temp->next;
}
}



void Link::insort1(int num)
{

if ( num > 1 )
insort1 ( num -1);
int n, item, i;
remove(num-1, n);

for ( i = 0; i < num-1; i++)
{
retrieve( i, item);
if ( n < item)
break;
}
insert ( i, n);
}



void Link::insort2(int num)
{

if ( num > 1 )
insort1 ( num -1);
cout << "Size = " << num;
traverse (print_entry, num);
int n, item, i;
remove(num-1, n);

for ( i = 0; i < num-1; i++)
{
retrieve( i, item);
if ( n < item)
break;
}
insert ( i, n);

traverse ( print_entry, num);
cout << endl;
}

[monarch_dodra]

Did you try to run your program in the debugger?

Could you provide a compilable version of your program? As in one we can actually test? There's only so much we can do looking at the code. Right now, it is missing the declaration of Link, the Declaration/Definition of Node, and a main.

PS: Please use [CODE][/CODE] tags when you paste code, it keeps formatting.

[youngyou4]

Here is assign7.cpp

 #include <cstdlib>
#include <iostream>
#include <iomanip>
#include <fstream>

#include "Link.h"

using namespace std;

#define INPUT1 "/home/turing/abyrnes/input/cs241/fall10/input7-1"
#define INPUT2 "/home/turing/abyrnes/input/cs241/fall10/input7-2"
#define NUM 8

void print_entry(int &, int);

int main()
{
    int i = 0;
    int pos = 0;
    int nodes = 0;

    Link LinkList1;
    ifstream inFile;

    inFile.open(INPUT1);

 if(!inFile)
    {
         cerr << "Unable to open 'input7-1' file" << endl;
         exit(1);
    }

    inFile >> i;

    while(inFile)
    {
        LinkList1.insert(pos, i);
        pos++;
        nodes++;
        inFile >> i;
    }

    inFile.close();

    LinkList1.traverse(print_entry, nodes);
    LinkList1.insort1(nodes);
    LinkList1.traverse(print_entry, nodes);

    pos = 0;
    nodes = 0;

    Link LinkList2;

    inFile.open(INPUT2);
    if(!inFile)
    {
         cerr << "Unable to open 'input7-2' file" << endl;
         exit(1);
    }

    inFile >> i;
         
    while(inFile)
    {
        LinkList2.insert(pos, i);
        pos++;
        nodes++;
        inFile >> i;
    }

    inFile.close();

    LinkList2.traverse(print_entry, nodes);
    LinkList2.insort2(nodes);
    LinkList2.traverse(print_entry, nodes);

    return 0;
}

void print_entry(int & x, int y)
{
     static int z = 1;
     
     if(z%NUM == 0)
     {
        cout << x << "\n";
        z++;
     }
     else
     {
        cout << x << " ";
        z++;
     }
     if(z >= NUM)
     {
        z = 0;
     }
}

Here is my header file... Link.h

#ifndef LINK_H
#define LINK_H
#include "Node.h"
class Link
{
      private:
              int nodes;
              Node * head;

      public:
             Link();
             ~Link();
             int size();
             bool isEmpty();
             void clear();
             bool retrieve(int, int &);
             void insert(int, const int &);
             void remove(int, int &);
             void traverse(void(*funcptr)(int &, int), int);
             void insort1(int);
             void insort2(int);
};

#endif

Here is my Node.cc

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <fstream>

#include "Node.h"

using namespace std;
Node::Node(int num, Node * temp)
{
    data = num;
    next = temp;
}

Here is my Node HEader... Node.h

#ifndef NODE_H
#define NODE_H

class Link;

class Node
{
      private:
              int data;
              Node * next;

      public:
             Node(int, Node * = NULL);
             friend class Link;
};

#endif

Here is my Link.cc Again.

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <fstream>

#include "Link.h"

using namespace std;

void print_entry(int &, int);





Link::Link()
{
    nodes = 0;
    head = NULL;
}


Link::~Link()
{
    clear();
}


int Link::size()
{
    return nodes;
}



bool Link::isEmpty()
{
     if(nodes == 0)
     {
         return true;
     }
     else
     {
         return false;
     }
}


void Link::clear()
{
    while(head)
    {
        Node *temp;

        temp = head;
        head = head->next;

        delete temp;
    }

}



bool Link::retrieve(int pos, int & val)
{
     Node * temp;

     if(isEmpty())
     {
         cout << "The List is empty" << endl;
         return false;
     }
     else if(size() < pos || pos < 0)
     {
         cout << "Invalid Position" << endl;
         return false;
     }
     else
     {
         temp = head;

         for(int i = 0; i < pos; i++)
         {
            temp= temp->next;
         }

         val = temp->data;
         return true;
     }
}




void Link::insert(int pos, const int & val) 
{
     if(size() < pos || pos < 0)
     {   
         cout << "Invalid Position" << endl;
     }
     else
     {
         Node * temp;
            
         if(pos == 0)
         {
             temp = new Node(val);
             temp->next = head;
             head = temp;
             nodes++;
         }
         else
         {
             Node * ptr = head;
             Node * lagPtr = head;
   
             temp = new Node(val);


             for(int i = 0; i < pos; i++)
             {
                lagPtr = ptr;
                ptr = ptr -> next;
             }

             lagPtr->next = temp;
             temp->next = ptr;
             nodes++;
         }
     }
}

void Link::remove(int pos, int & val)
{
     if(isEmpty())
     {
         cout << "The List is Empty" << endl;
     }
     else if(size() < pos || pos < 0)
     {
          cout << "Invalid Position" << endl;
     }
     else
     {
         if(pos == 0)
         {
             retrieve(pos, val);
             Node * temp;
             temp = head;
             head = temp->next;
             delete temp;
         }
         else
         {
             Node * ptr = head;
             Node * lagPtr = head;

             for(int i = 0; i < pos; i++)
             {
                 lagPtr = ptr;
                 ptr = ptr->next;
             }
      
             lagPtr = ptr->next;
             delete ptr;
             nodes--;
         }
     }
}



void Link::traverse(void(*funcptr)(int &, int), int numElements)
{
     Node * temp = head;

     for(int i = 0; i < numElements; i++)
     {
         (*funcptr)(temp->data, numElements);
         temp = temp->next;
     }
}



void Link::insort1(int num)
{

 if ( num > 1 )
        insort1 ( num -1);
     int n, item, i;
        remove(num-1, n);

        for ( i = 0; i < num-1; i++)
        {
                retrieve( i, item);
                if ( n < item)
                break;
        }
        insert ( i, n);
}



void Link::insort2(int num)
{

          if ( num > 1 )
        insort1 ( num -1);
        cout << "Size = " << num;
        traverse (print_entry, num);
     int n, item, i;
        remove(num-1, n);

        for ( i = 0; i < num-1; i++)
        {
                retrieve( i, item);
                if ( n < item)
                break;
        }
        insert ( i, n);
 
        traverse ( print_entry, num);
        cout << endl;
}

The Program description is Here http://faculty.cs.niu.edu/~byrnes/cs...ms/241pgm7.htm

The Problem: IT runs and executes but after it prints out the first file, and it goes back to sort it says thats a Segmentation Fault. If anyone could help me it would be great

[GCDEF]

Your debugger will tell you exactly what's happening. Give it a try.

[Lindley]

else if(size() < pos || pos < 0)

I think you might have an off-by-1 in this check. What if pos == size(), should that work?

Also, check your remove() logic. I think I see a flaw there. Not related to what I see, but----why pass in the val parameter to remove() if you only use it in the pos==0 case? It isn't used in the else at all.

[youngyou4]

I ran the debugger, it is showing that its coming from my insert method but i dont see how. The ptr is right. The only thing that causes a segmentation error is when you try to access node when you cant or the ptr... I dont understand

[youngyou4]

else if(size() < pos || pos < 0)

I think you might have an off-by-1 in this check. What if pos == size(), should that work?

Also, check your remove() logic. I think I see a flaw there. Not related to what I see, but----why pass in the val parameter to remove() if you only use it in the pos==0 case? It isn't used in the else at all.

The segmentation error i believe is coming from the insert method, but i dont see anything wrong with it. A segmentation fault is only from a ptr being wrong or trying to access node when it is not allowing. What method is the else if(size() that needs to be changed? to pos == size

[youngyou4]

I've been playing around with it again, and i think my problems are in the remove method.

[Lindley]

It might help to draw the logic out on paper and then compare it to what you're doing.

[youngyou4]

I've checked the logic over and over again... But I'm still getting a **** segmentation fault. I dont understand what is wrong with it.

[Lindley]

             lagPtr = ptr->next;

This is wrong.

[youngyou4]

             lagPtr = ptr->next;

This is wrong.

I just saw that...

That should be

 ptr =lagPtr->next;

correct?

Also im only retrieving in pos 0 but when i place another one in the else statement it prints out -667 repeatedly...

[Lindley]

Well no, ptr already has the correct value at that point in the code. But you aren't modifying what you need to be modifying.

[youngyou4]

What exactly should i be modifying?