I have an assignment to build a linked list which can insert items in a sorted order... however I haven't been fully successful. I can insert items at the beginning and the end with no problem, but the middle is proving more difficult.
I'm sure I know what the problem is and where it exist in the program... I'm just not sure of how to correct it. Currently, my code seems to find the correct place to insert the new node... but it puts the new node before the one being evaluated... I need it to place it after it instead. I'm sure it is something simple that I'm missing but its driving me crazy and i"m running out of time.
I must apologize ahead of time... I have quit a few unneeded print() statements... I left them there though so the problem can be a lil more easily seen when trying to run the program.
Below is all my code... any help would be appreciated. I'd like to understand where I went wrong.
The problem lies here in Week5-6Program.cpp
Code:
//-----------------------The problem lies here--------------------------------------------
if(ptr->data > newPtr->data){ // Item is > than ptr
newPtr->nextPtr = ptr->nextPtr; // Insert item after ptr
ptr->nextPtr = newPtr;
cout << "\n" << value << " belongs before " << ptr->data << " in middle of list\n";
print();
break;
}//end if
//----------------------------------------------------------------------------------------
list_node.h
Code:
// Exercise 21.6 Solution: ListNode.h
// ListNode class template definition
#ifndef LISTNODE_H
#define LISTNODE_H
template< typename T > class ABook; // forward declaration
template< typename NODETYPE >
class AddressNode
{
friend class ABook< NODETYPE >; // make ABook a friend
public:
AddressNode( const NODETYPE & ); // constructor
NODETYPE getData() const; // return the data in the node
// set nextPtr to nPtr
void setNextPtr( AddressNode *nPtr )
{
nextPtr = nPtr;
} // end function setNextPtr
// return nextPtr
AddressNode *getNextPtr() const
{
return nextPtr;
} // end function getNextPtr
private:
NODETYPE data; // data
AddressNode *nextPtr; // next node in the ABook
AddressNode *prevPtr; // points to node before
}; // end class AddressNode
// constructor
template< typename NODETYPE >
AddressNode< NODETYPE >::AddressNode( const NODETYPE &info )
{
data = info;
nextPtr = NULL;
prevPtr = NULL;
} // end constructor
// return a copy of the data in the node
template< typename NODETYPE >
NODETYPE AddressNode< NODETYPE >::getData() const
{
return data;
} // end function getData
#endif
Code:
#ifndef ABook_H
#define ABook_H
#include <iostream>
#include <new>
#include<string>
#include "list_node.h"
using namespace std;
template< typename NODETYPE >
class ABook
{
public:
ABook(); // default constructor
~ABook(); // destructor
void Insert( const NODETYPE & );//inserts at beginning of list
void SortedInsert( const NODETYPE & );//inserts in Acending order
bool Remove( NODETYPE & );//pops value from front of list and prints it to the screen
bool empty() const;//checks to see if a list contains any nodes
void print() const;//prints list
private:
AddressNode< NODETYPE > *topPtr; // pointer to first node
AddressNode< NODETYPE > *lastPtr; // pointer to last node
AddressNode< NODETYPE > *getNewNode( const NODETYPE & );// create new node
}; // end class template ABook
// default constructor
template< typename NODETYPE >
ABook< NODETYPE >::ABook()
{
topPtr = lastPtr = NULL;
} // end constructor
// destructor
template< typename NODETYPE >
ABook< NODETYPE >::~ABook()
{
if (!empty()){ // ABook is not empty
AddressNode< NODETYPE > *currentPtr = topPtr;
AddressNode< NODETYPE > *tempPtr;
while ( currentPtr != 0 ){ // delete remaining nodes
tempPtr = currentPtr;
cout << "Destroying: " << tempPtr->data << '\n';
currentPtr = currentPtr->nextPtr;
delete tempPtr;
}
}
cout << "\nDestructor Successful: All nodes destroyed\n\n";
system("pause");//shows that destructor was successful
} // end destructor
// Insert a node at the front of the list
template< typename NODETYPE >
void ABook< NODETYPE >::Insert( const NODETYPE &value )
{
AddressNode<NODETYPE> *newPtr = getNewNode( value );
if ( empty() ){
// checks to see if the list is empty if it is, inserts at front
topPtr = lastPtr = newPtr;
}
else{
//if its not empty insert at beginning and push everything else right
newPtr->nextPtr = topPtr;
topPtr = newPtr;
} // end else
} // end function Insert
//Insert a node in order
template< typename NODETYPE >
void ABook< NODETYPE >::SortedInsert( const NODETYPE &value )
{
AddressNode< NODETYPE > *newPtr = getNewNode(value);
cout << "\nAfter inserting: " << value << "";
if (empty()){
//if there is nothing on the list yet make it the first node
lastPtr = topPtr = newPtr;
cout << "\n" << value << " is first item on list\n";
print();
}
else if(newPtr->data < topPtr->data){
//if new data is less than first element, insert as first element and push everything else right (assumes list is sorted)
newPtr->nextPtr = topPtr;
topPtr = newPtr;
cout << "\n" << value << " belongs at front of List\n";
print();
}
else{
for( AddressNode< NODETYPE > *ptr = topPtr; ptr != NULL; ptr = ptr->nextPtr ){
//iterate through list till the proper place is found to insert the new item
//-----------------------The problem lies here--------------------------------------------
if(ptr->data > newPtr->data){ // Item is > than ptr
newPtr->nextPtr = ptr->nextPtr; // Insert item after ptr
ptr->nextPtr = newPtr;
cout << "\n" << value << " belongs before " << ptr->data << " in middle of list\n";
print();
break;
}//end if
//----------------------------------------------------------------------------------------
if( ptr->nextPtr == NULL ){
//If it is the greatest value in the list, place it at the end
lastPtr = ptr->nextPtr = newPtr; // Insert at end
newPtr->nextPtr = NULL;
cout << "\n" << value << " belongs at end of list\n";
print();
}
}//end for
}//end if
}//end sortedinsert
// Delete a node from the front of the ABook
template< typename NODETYPE >
bool ABook< NODETYPE >::Remove( NODETYPE &value )
{
if ( empty() ) // ABook is empty
return false; // delete unsuccessful
else
{
AddressNode< NODETYPE > *tempPtr = topPtr;
if ( topPtr == lastPtr )
topPtr = lastPtr = NULL;
else
topPtr = topPtr->nextPtr;
value = tempPtr->data; // data being removed
delete tempPtr;
return true; // delete successful
} // end else
} // end function remove
// Is the ABook empty?
template< typename NODETYPE >
bool ABook< NODETYPE >::empty() const
{
return topPtr == NULL;
} // end function isEmpty
// assigns pointer to a new node
template< typename NODETYPE >
AddressNode< NODETYPE > *ABook< NODETYPE >::getNewNode(const NODETYPE &value)
{
AddressNode< NODETYPE > *ptr = new AddressNode< NODETYPE >( value );
return ptr;
} // end function getNewNode
template< typename NODETYPE >
void ABook< NODETYPE >::print() const
{//Prints linked list
if ( empty() ){ // empty ABook
cout << "The ABook is empty\n";
return;
}
AddressNode< NODETYPE > *currentPtr = topPtr;
cout << "The ABook is:\n";
while ( currentPtr != NULL ){
// cycle through nodes until the end is reached
cout << currentPtr->data << '\n';
currentPtr = currentPtr->nextPtr;
}
} // end function print
#endif
//----------------------------Week5-6Program.cpp-------------------------------
int main()
{
ABook< string > Book; // storage for first ABook
string newName[4] = {"Ken","Eileen","Frank","Precious"};//this does
string nameToRemove[4] = {"Precious","Ken","Eileen","Frank"};//this doesn't use 4 names
cout << "input order: \n";
for(int i = 0; i < 4; i++)
cout << newName[i] << '\n';
cout << '\n';
Book.SortedInsert(newName[0]);
Book.SortedInsert(newName[1]);
Book.SortedInsert(newName[2]);
Book.SortedInsert(newName[3]);
Book.SortedInsert("Herman");
cout << "\nFinal list is: \n";
Book.print();
system("pause");
return 0; // indicates successful termination
} // end main