<![CDATA[//******************************************************************
// IMPLEMENTATION FILE (slist2.cpp)
// This file implements the SortedList2 class member functions
// List representation: a linked list of dynamic nodes
//******************************************************************
#include "slist2.h"
#include <iostream>
#include <cstddef> // For NULL
using namespace std;
typedef NodeType* NodePtr;
struct NodeType
{
ComponentType component;
NodePtr link;
};
// Private members of class:
// NodePtr head; External pointer to linked list
//******************************************************************
SortedList2::SortedList2()
// Constructor
// Postcondition:
// head == NULL
{
head = NULL;
}
//******************************************************************
SortedList2::SortedList2( const SortedList2& otherList )
// Copy-constructor
// Postcondition:
// IF otherList.head == NULL (i.e., the other list is empty)
// head == NULL
// ELSE
// head points to a new linked list that is a copy of
// the linked list pointed to by otherList.head
{
NodePtr fromPtr; // Pointer into list being copied from
NodePtr toPtr; // Pointer into new list being built
if (otherList.head == NULL)
{
head = NULL;
return;
}
// Copy first node
fromPtr = otherList.head;
head = new NodeType;
head->component = fromPtr->component;
// Copy remaining nodes
toPtr = head;
fromPtr = fromPtr->link;
while (fromPtr != NULL)
{
toPtr->link = new NodeType;
toPtr = toPtr->link;
toPtr->component = fromPtr->component;
fromPtr = fromPtr->link;
}
toPtr->link = NULL;
}
//******************************************************************
SortedList2::~SortedList2()
// Destructor
// Postcondition:
// All linked list nodes have been deallocated from free store
{
ComponentType temp; // Temporary variable
while ( !IsEmpty() )
DeleteTop(temp);
}
//******************************************************************
bool SortedList2::IsEmpty() const
// Postcondition:
// Function value == true, if head == NULL
// == false, otherwise
{
return (head == NULL);
}
//******************************************************************
void SortedList2::Print() const
// Postcondition:
// component members of all nodes (if any) in linked list
// have been output
{
NodePtr currPtr = head; // Loop control pointer
while (currPtr != NULL)
{
cout << currPtr->component << endl;
currPtr = currPtr->link;
}
}
//******************************************************************
void SortedList2::InsertTop( /* in */ ComponentType item )
// Precondition:
// component members of list nodes are in ascending order
// && item < component member of first list node
// Postcondition:
// New node containing item is at top of linked list
// && component members of list nodes are in ascending order
{
NodePtr newNodePtr = new NodeType; // Temporary pointer
newNodePtr->component = item;
newNodePtr->link = head;
head = newNodePtr;
}
//******************************************************************
void SortedList2::Insert( /* in */ ComponentType item )
// Precondition:
// component members of list nodes are in ascending order
// && item is assigned
// Postcondition:
// New node containing item is in its proper place
// in linked list
// && component members of list nodes are in ascending order
{
NodePtr currPtr; // Moving pointer
NodePtr prevPtr; // Pointer to node before *currPtr
NodePtr newNodePtr; // Pointer to new node
// Set up node to be inserted
newNodePtr = new NodeType;
newNodePtr->component = item;
// Find previous insertion point
prevPtr = NULL;
currPtr = head;
while (currPtr != NULL && item > currPtr->component)
{
prevPtr = currPtr;
currPtr = currPtr->link;
}
// Insert new node
newNodePtr->link = currPtr;
if (prevPtr == NULL)
head = newNodePtr;
else
prevPtr->link = newNodePtr;
}
//******************************************************************
void SortedList2::DeleteTop( /* out */ ComponentType& item )
// Precondition:
// Linked list is not empty (head != NULL)
// && component members of list nodes are in ascending order
// Postcondition:
// item == component member of first list node at entry
// && Node containing item is no longer in linked list
// && component members of list nodes are in ascending order
{
NodePtr tempPtr = head; // Temporary pointer
item = head->component;
head = head->link;
delete tempPtr;
}
//******************************************************************
void SortedList2::Delete( /* in */ ComponentType item )
// Precondition:
// item == component member of some list node
// && component members of list nodes are in ascending order
// Postcondition:
// Node containing first occurrence of item is no longer in
// linked list
// && component members of list nodes are in ascending order
{
NodePtr delPtr; // Pointer to node to be deleted
NodePtr currPtr; // Loop control pointer
// Check if item is in first node
if (item == head->component)
{
// Delete first node
delPtr = head;
head = head->link;
}
else
{
// Search for node in rest of list
currPtr = head;
while (currPtr->link->component != item)
currPtr = currPtr->link;
// Delete *(currPtr->link)
delPtr = currPtr->link;
currPtr->link = currPtr->link->link;
}
delete delPtr;
}
]]>