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.