#ifndef H_UnorderedLinkedList
#define H_UnorderedLinkedList
#include "linkedList.h"
using namespace std;
template <class Type>
class unorderedLinkedList : public linkedListType<Type>
{
public:
bool search(const Type& searchItem) const;
void insertFirst(const Type& newItem);
void insertLast(const Type& newItem);
void deleteNode(const Type& deleteItem);
void linkedSelectionSort();
private:
void selectionSortLinked(nodeType<Type>*& head);
void minLocation(nodeType<Type>*& trailSmall,
nodeType<Type>*& small);
};
template<class elemType>
void unorderedLinkedList<elemType>::linkedSelectionSort()
{
selectionSortLinked(first);
}
template<class elemType>
void unorderedLinkedList<elemType>::selectionSortLinked(nodeType<elemType>*& head)
{
nodeType<elemType>* lastInOrder;
nodeType<elemType>* small;
nodeType<elemType>* trailSmall;
if (head == NULL)
cout << "Cannot sort an empty list" << endl;
else
{
small = head;
minLocation(trailSmall, small);
if (small != head)
{
trailSmall->link = small->link;
small->link = head;
head = small;
}
lastInOrder = head;
while (lastInOrder->link != NULL)
{
small = lastInOrder->link;
minLocation(trailSmall, small);
if (small != lastInOrder->link)
{
trailSmall->link = small->link;
small->link = lastInOrder->link;
lastInOrder->link = small;
}
lastInOrder = lastInOrder->link;
}
}
}
template<class elemType>
void unorderedLinkedList<elemType>::minLocation
(nodeType<elemType>*& trailSmall,
nodeType<elemType>*& small)
{
nodeType<elemType>* trailCurrent;
nodeType<elemType>* current;
current = small->link;
trailCurrent = small;
while (current != NULL)
{
if (small->info > current->info)
{
trailSmall = trailCurrent;
small = current;
}
trailCurrent = current;
current = current->link;
}
}
template <class Type>
bool unorderedLinkedList<Type>::
search(const Type& searchItem) const
{
nodeType<Type>* current; //pointer to traverse the list
bool found = false;
current = first; //set current to point to the first
//node in the list
while (current != NULL && !found) //search the list
if (current->info == searchItem) //searchItem is found
found = true;
else
current = current->link; //make current point to
//the next node
return found;
}//end search
template <class Type>
void unorderedLinkedList<Type>::insertFirst(const Type& newItem)
{
nodeType<Type>* newNode; //pointer to create the new node
newNode = new nodeType<Type>; //create the new node
newNode->info = newItem; //store the new item in the node
newNode->link = first; //insert newNode before first
first = newNode;
count++; //increment count
if (last == NULL) //if the list was empty, newNode is also
//the last node in the list
last = newNode;
}//end insertFirst
template <class Type>
void unorderedLinkedList<Type>::insertLast(const Type& newItem)
{
nodeType<Type>* newNode; //pointer to create the new node
newNode = new nodeType<Type>; //create the new node
newNode->info = newItem; //store the new item in the node
newNode->link = NULL; //set the link field of newNode
//to NULL
if (first == NULL) //if the list is empty, newNode is
//both the first and last node
{
first = newNode;
last = newNode;
count++; //increment count
}
else //the list is not empty, insert newNode after last
{
last->link = newNode; //insert newNode after last
last = newNode; //make last point to the actual
//last node in the list
count++; //increment count
}
}//end insertLast
template <class Type>
void unorderedLinkedList<Type>::deleteNode(const Type& deleteItem)
{
nodeType<Type>* current; //pointer to traverse the list
nodeType<Type>* trailCurrent; //pointer just before current
bool found;
if (first == NULL) //Case 1; the list is empty.
cout << "Cannot delete from an empty list."
<< endl;
else
{
if (first->info == deleteItem) //Case 2
{
current = first;
first = first->link;
count--;
if (first == NULL) //the list has only one node
last = NULL;
delete current;
}
else //search the list for the node with the given info
{
found = false;
trailCurrent = first; //set trailCurrent to point
//to the first node
current = first->link; //set current to point to
//the second node
while (current != NULL && !found)
{
if (current->info != deleteItem)
{
trailCurrent = current;
current = current->link;
}
else
found = true;
}//end while
if (found) //Case 3; if found, delete the node
{
trailCurrent->link = current->link;
count--;
if (last == current) //node to be deleted
//was the last node
last = trailCurrent; //update the value
//of last
delete current; //delete the node from the list
}
else
cout << "The item to be deleted is not in "
<< "the list." << endl;
}//end else
}//end else
}//end deleteNode
#endif
The errors are:
unorderedLinkedList.h(210,28): error C3861: 'first': identifier not found
unorderedLinkedList.h(212,23): error C3861: 'first': identifier not found
unorderedLinkedList.h(231,21): error C3861: 'last': identifier not found
unorderedLinkedList.h(233,21): error C3861: 'last': identifier not found
