Sorted List Implemented as an array in C
Interface (Header) File defining the list class
//---------------------------------------------------------------
// File: Code106_List.h
// Purpose: Header file for a demonstration of a sorted list
// implemented as an array.
// Programming Language: C
// Author: Dr. Rick Coleman
//---------------------------------------------------------------
#ifndef CODE106_LIST_H
#define CODE106_LIST_H
#include <stdio.h>
// 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
// List Function Prototypes
void InitList(); // Initialize the list
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 (.c) File defining the list
//---------------------------------------------------------------
// File: Code106_List.c
// 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 "Code106_List.h"
// Declare these as static so no code outside of this source
// can access them.
static int head; // Declare global index to head of the list
static struct ListItem theList[MAX_SIZE]; // The list
//--------------------------------------------
// Function: InitList()
// Purpose: Initialize list to empty.
// Returns: void
//--------------------------------------------
void InitList()
{
head = -1;
}
//--------------------------------------------
// Function: ClearList()
// Purpose: Remove all items from the list
// Returns: void
//--------------------------------------------
void 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 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 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 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 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 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 isFull()
{
return (head >= MAX_SIZE);
}
//--------------------------------------------
// Function: PrintList()
// Purpose: Print all items in the list with
// their priority.
// Returns: void
//--------------------------------------------
void PrintList()
{
int i;
printf("\n\nItems in the List\n");
printf("-----------------------------------------------------------\n");
printf("Key\t\tData\n");
printf("-----------------------------------------------------------\n");
for(i=0; i<=head; i++)
{
printf("%d\t\t%f\n", theList[i].key, theList[i].theData);
}
printf("-----------------------------------------------------------\n\n");
}
Main file used to test the list
//---------------------------------------------------------------
// File: ListMain.c
// 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 "Code106_List.h"
int main(int argc, char **argv)
{
float f;
printf("Simple List Demonstration\n");
printf("(List implemented as an Array - Do not try this at home)\n\n");
printf("Create a list and add a few tasks to the list");
InitList();
Insert(5, 3.1f); // Note: The argument to the funtion should be a float
Insert(1, 5.6f); // A constant real number like 3.1 is interpreted as
Insert(3, 8.3f); // a double unless it is explicitly defined as a float
Insert(2, 7.4f); // by ading an 'f' to the end of the number.
Insert(4, 2.5f);
// Show what is in the list
PrintList();
// Test the list length function
printf("\nList now contains %d items.\n\n", ListLength());
// Test delete function
printf("Testing delete of last item in list.\n");
Delete(5);
PrintList();
// Test delete function
printf("Testing delete of first item in list.\n");
Delete(1);
PrintList();
// Test delete function
printf("Testing delete of a middle item in list.\n");
Delete(3);
PrintList();
// Test delete function with a known failure argument
printf("Testing failure in delete function.\n");
if(Delete(3))
printf("Oops! Should not have been able to delete.\n\n");
else
printf("Unable to locate item to delete.\n\n");
// Test search (known failure)
printf("Testing Search function. Search for key 3 (known failure)\n");
if(Search(3, &f))
printf("Search result: theData = %f\n\n", f);
else
printf("Search result: Unable to locate item in list\n\n");
// Test search (known success)
printf("Testing Search function. Search for key 2 (known success)\n");
if(Search(2, &f))
printf("Search result: theData = %f\n", f);
else
printf("Search result: Unable to locate item in list\n");
printf("\n\nEnd list demonstration...");
return 0;
}