Sorted List Implemented as an array in C++
Interface (Header) File defining the list class
//---------------------------------------------------------------
// File: Code107_List.h
// Purpose: Header file for a demonstration of a sorted list
// implemented as an array.
// Programming Language: C++
// Author: Dr. Rick Coleman
//---------------------------------------------------------------
#ifndef CODE107_LIST_H
#define CODE107_LIST_H
#include <iostream>
using namespace std;
// Define a structure to use as the list item
struct ListItem
{
int key;
float theData;
};
#define MAX_SIZE 50 // Define maximum length of the list
class Code107_List
{
private:
int head; // Index to head of the list
ListItem theList[MAX_SIZE]; // The list
public:
Code107_List(); // Class constructor
~Code107_List(); // Class destuctor
void ClearList(); // Remove all items from the list
int Insert(int key, float f); // Add an item to the list
int Delete(int key); // Delete an item from the list
int Search(int key, float *retVal); // Search for an item in the list
int ListLength(); // Return number of items in list
int isEmpty(); // Return true if list is empty
int isFull(); // Return true if list is full
void PrintList(); // Print all items in the list
};
// Define TRUE and FALSE if they have not already been defined
#ifndef FALSE
#define FALSE (0)
#endif
#ifndef TRUE
#define TRUE (!FALSE)
#endif
#endif // End of list header
Implementation (.cpp) File defining the list class
//---------------------------------------------------------------
// File: Code107_List.cpp
// Purpose: Implementation file for a demonstration of a sorted
// list implemented as an array.
// Programming Language: C++
// Author: Dr. Rick Coleman
// Date: January 7, 2002
//---------------------------------------------------------------
#include "Code107_List.h"
//--------------------------------------------
// Function: Code107_List()
// Purpose: Class constructor
// Returns: void
//--------------------------------------------
Code107_List::Code107_List()
{
head = -1;
}
//--------------------------------------------
// Function: Code107_List()
// Purpose: Class destructor
// Returns: void
//--------------------------------------------
Code107_List::~Code107_List()
{
// Nothing to do here since the memory used
// for the list is freed automatically.
}
//--------------------------------------------
// Function: ClearList()
// Purpose: Remove all items from the list
// Returns: void
//--------------------------------------------
void Code107_List::ClearList()
{
head = -1; // Reset count to start over
}
//--------------------------------------------
// Function: Insert()
// Purpose: Insert an item into the list in
// the next open slot.
// Returns: TRUE if insertion was successful
// or FALSE if the insertion failed.
//--------------------------------------------
int Code107_List::Insert(int key, float f)
{
int idx, i;
// Check to see if the list is full
if(isFull()) return FALSE;
// Locate where to insert this item in the list
idx = 0;
while((idx <= head) && (theList[idx].key < key)) idx++;
// Move all other items up 1 in list to make room for the
// new item to be inserted in the correct place
head++; // Increment head index
for(i=head; i>idx; i--)
theList[i] = theList[i-1];
// Insert the item into the list
theList[idx].key = key;
theList[idx].theData = f;
return TRUE;
}
//--------------------------------------------
// Function: Delete()
// Purpose: Delete an item from the list and
// move all others up to close up the
// empty space.
// Returns: TRUE if deletion was successful
// or FALSE if the deletion failed.
//--------------------------------------------
int Code107_List::Delete(int key)
{
int i, d = 0;
// Check for empty list
if(isEmpty()) return FALSE;
// Search the list for the item to delete
while((d <= head) && (key != theList[d].key))
{
d++;
}
// Check to see if the item was found
if(d > head) return FALSE; // Not found so return FALSE
else
{
// Move all other items toward the front of the array
// This also overwrites and "deletes" the task searched for
for(i = d; i < head; i++)
{
theList[i] = theList[i+1]; // Using whole structure copy
}
head--; // Reset head
}
return TRUE;
}
//--------------------------------------------
// Function: Search()
// Purpose: Search for an item by key and copy
// the value into the variable pointed to
// by *retVal.
// Returns: TRUE if search was successful
// or FALSE if the search failed.
//--------------------------------------------
int Code107_List::Search(int key, float *retVal)
{
int s = 0;
while((s <= head) && (key != theList[s].key))
{
s++;
}
// If item not found return FALSE
if(s > head) return FALSE;
else
*retVal = theList[s].theData; // Copy the data
return TRUE;
}
//--------------------------------------------
// Function: ListLength()
// Purpose: Return the number of items in the
// list.
// Returns: Number of items in list.
// Note: head is the index of the last filled
// slot. To get the number of items you must
// add 1 to the last filled index.
//--------------------------------------------
int Code107_List::ListLength()
{
return head+1;
}
//--------------------------------------------
// Function: isEmpty()
// Purpose: Return true if the list is empty
// Returns: TRUE if empty, otherwise FALSE
// Note: C has no boolean data type so we use
// the defined int values for TRUE and FALSE
// instead.
//--------------------------------------------
int Code107_List::isEmpty()
{
return (head == -1);
}
//--------------------------------------------
// Function: isFull()
// Purpose: Return true if the list is full
// Returns: TRUE if full, otherwise FALSE
// Note: C has no boolean data type so we use
// the defined int values for TRUE and FALSE
// instead.
//--------------------------------------------
int Code107_List::isFull()
{
return (head >= MAX_SIZE);
}
//--------------------------------------------
// Function: PrintList()
// Purpose: Print all items in the list with
// their priority.
// Returns: void
//--------------------------------------------
void Code107_List::PrintList()
{
int i;
cout << "\n\nItems in the List\n";
cout << "-----------------------------------------------------------\n";
cout << "Key\t\tData\n";
cout << "-----------------------------------------------------------\n";
for(i=0; i<=head; i++)
{
cout << theList[i].key << "\t\t" << theList[i].theData << "\n";
}
cout << "-----------------------------------------------------------\n\n";
}
Main file used to test the list class
//---------------------------------------------------------------
// File: ListMain.cpp
// Purpose: Main file with tests for a demonstration of a sorted
// list implemented as an array.
// Programming Language: C++
// Author: Dr. Rick Coleman
// Date: January 7, 2002
//---------------------------------------------------------------
#include "Code107_List.h"
int main(int argc, char **argv)
{
float f;
Code107_List *theList;
cout << "Simple List Demonstration\n";
cout << "(List implemented as an Array - Do not try this at home)\n\n";
cout << "Create a list and add a few tasks to the list";
theList = new Code107_List(); // Instantiate a list object
theList->Insert(5, 3.1f); // Note: The argument to the funtion should be a float
theList->Insert(1, 5.6f); // A constant real number like 3.1 is interpreted as
theList->Insert(3, 8.3f); // a double unless it is explicitly defined as a float
theList->Insert(2, 7.4f); // by adding an 'f' to the end of the number.
theList->Insert(4, 2.5f);
// Show what is in the list
theList->PrintList();
// Test the list length function
cout << "\nList now contains " << theList->ListLength() << "items.\n\n";
// Test delete function
cout << "Testing delete of last item in list.\n";
theList->Delete(5);
theList->PrintList();
// Test delete function
cout << "Testing delete of first item in list.\n";
theList->Delete(1);
theList->PrintList();
// Test delete function
cout << "Testing delete of a middle item in list.\n";
theList->Delete(3);
theList->PrintList();
// Test delete function with a known failure argument
cout << "Testing failure in delete function.\n";
if(theList->Delete(5))
cout << "Oops! Should not have been able to delete.\n\n";
else
cout << "Unable to locate item to delete.\n\n";
// Test search (known failure)
cout << "Testing Search function. Search for key 3\n";
if(theList->Search(3, &f))
cout << "Search result: theData = " << f << "\n\n";
else
cout << "Search result: Unable to locate item in list\n\n";
// Test search (known success)
cout << "Testing Search function. Search for key 2\n";
if(theList->Search(2, &f))
cout << "Search result: theData = " << f << "\n";
else
cout << "Search result: Unable to locate item in list\n";
cout << "\n\nEnd list demonstration...";
return 0;
}