By the way, if you look at the bottom of your output, you will see how long it took for your program to run with my driver. The average running time for the program was about 400 milliseconds (0.4 seconds). The fastest time was 200 ms. This number basically indicates the efficiency of your implementation. You didn't get any bonus points for being fast, I just wanted you to see that not all programs are equal. Sometimes it is important to do things in a more efficient manner.
//////////////////////////////////////////////////////////////////////////
// Student Name : Joe "Mama" Besser
// Student ID : 123-45-6789
// Course : CS 162
// Assignment : Lab #4
// Program File : strlist.cpp
// Due Date : 8/10/98
//
// Description : This implementation file contains member functions
// necessary to create and manipulate objects of a class
// named "StrList." Implementation is executed as a
// linked list of dynamic nodes. Each node is
// represented as a structure with two data members:
// a character array (named "word") and a pointer
// (named "next"). The private member of the class
// (named "head") is a pointer to the first node of the
// list of each object. Various manipulations will be
// performed on the objects, as detailed in specification
// file strlist.h. Manipulations include:
// o prepending a character string to the list
// o displaying the list
// o counting the number of items on the list
// o checking if the list is empty
// o appending a character string to the list
// o checking if a character string is present
// o returning a pointer to an item given its
// position in the list
// o removing a given item from the list
//
//
//////////////////////////////////////////////////////////////////////////
#include "strlist.h"
#include <iostream.h> // for cout
#include <stddef.h> // for NULL
#include <string.h> // for strncpy, strcmp
#include <assert.h> // for assert
struct Node
{
char word[MAX_LENGTH + 1];
Node* next;
};
const char NULL_CHAR = '\0';
/////////////////////////////////////////////////////////////////////
// Constructor (default)
//
// Creates an empty list by setting head to NULL.
//
// Inputs: None
//
// Outputs: None
//
StrList::StrList(void)
{
head = NULL;
}
/////////////////////////////////////////////////////////////////////
// Function: Prepend
//
// Adds an item at the head of the list. If the item to be prepended
// is NULL, it doesn't get added. No error message is printed. If
// the item is larger than MAX_LENGTH, it is truncated to fit.
//
// The Prepend function prepends the linked list by creating a new
// Node, copying the value of "item" into the data portion of the
// Node, setting the Node's link portion to the head of the list, and
// setting head to the new Node.
//
// Inputs: item - a NULL terminated string.
//
// Outputs: None.
//
void StrList::Prepend(const char *item)
{
int count = 0; // count variable
Node* newNodePtr = new Node; // creates a new Node
// assert that the new Node was created
assert(newNodePtr);
// checks for Null value in item
if (item)
{
// copies the value of item to the data portion of the Node,
// up to MAX_LENGTH characters
strncpy(newNodePtr->word, item, MAX_LENGTH);
// in case string was truncated, the last character is set to
// the Null character
newNodePtr->word[MAX_LENGTH] = NULL_CHAR;
// the new Node is linked to the current head position
newNodePtr->next = head;
// the head is re-set to the new Node
head = newNodePtr;
}
}
/////////////////////////////////////////////////////////////////////
// Function: Display
//
// Prints each item in the list to the screen. After the entire
// list has been printed, a new line is printed.
//
// The function accomplishes the above mentioned task by stepping
// through the list and printing each data item, until the temporary
// pointer is set to NULL at the end of the list.
// The function checks after each data item is printed to see if it
// should be printed on a separate line. If separateLine was false,
// a newline is printed once at the end.
//
// Inputs: separateLine - A Boolean that determines the format
// of the output as follows:
//
// TRUE - Each item is printed on its own line.
// FALSE - All items are printed on the same line; they
// are separated by a single space.
//
// Outputs: None
//
void StrList::Display(Boolean separateLine) const
{
Node* currPtr = head; // creates a new Node for walk through
// checks for NULL each iteration
while (currPtr != NULL)
{
// displays the data item
cout << currPtr->word << " ";
// checks for separateLine
if (separateLine)
cout << endl;
// increments currPtr to the next item in the list
currPtr = currPtr->next;
}
// returns at the end of the line if separateLine was false
if (!separateLine)
cout << endl;
}
/////////////////////////////////////////////////////////////////////
// Function: getCount
//
// Returns the number of items in the list by stepping through the
// list and incrementing count each time, until the currPtr is NULL.
//
// Inputs: None
//
// Outputs: The number of items in the list.
//
int StrList::getCount(void) const
{
int count = 0; // count variable
Node* currPtr = head; // creates a new Node for walk through
// checks for NULL each iteration
while(currPtr != NULL)
{
// increments the count each iteration
++count;
// increments currPtr
currPtr = currPtr->next;
}
// returns the number of items counted
return count;
}
/////////////////////////////////////////////////////////////////////
// Function: isEmpty
//
// Returns a Boolean indicating whether or not the list is empty by
// checking to see if head is NULL.
//
// Inputs: None
//
// Outputs: A Boolean value that means:
// TRUE - The list is empty
// FALSE - The list is NOT empty
//
Boolean StrList::isEmpty(void) const
{
return (head == NULL);
}
/////////////////////////////////////////////////////////////////////
// Destructor
//
// Deletes all items in the list by stepping through the list,
// deleting each item, and re-setting the head of the list.
//
// Inputs: None
//
// Outputs: None
//
StrList::~StrList(void)
{
Node* delPtr; // creates a Node pointer for Node deletion
// checks for an empty list
while(!isEmpty())
{
// sets the pointer to the 1st item
delPtr = head;
// sets the head to the 2nd item
head = head->next;
// deletes the 1st item
delete delPtr;
}
}
/////////////////////////////////////////////////////////////////////
// Function: Append
//
// Adds an item to the end of the list. If the item to be appended
// is NULL, nothing gets added. No error message is printed. If the
// item is larger than MAX_LENGTH, it is truncated to fit.
//
// The above-mentioned function is accomplished by creating a new
// Node, copying the value of "item" to the new Node, stepping
// through the list until currPtr is NULL, setting the new Node's
// pointer to NULL, and setting the previous pointer to the new Node.
//
// Inputs: item - a NULL terminated string to be added
//
// Outputs: None
//
void StrList::Append(const char *item)
{
int count = 0; // count variable
Node* newNodePtr; // creates a Node pointer for the new Node
Node* currPtr; // creates a Node pointer for walk through
Node* prevPtr; // creates a Node pointer for previous Node
// checks for passing of a NULL value
if (item)
{
// creates a new Node
newNodePtr = new Node;
// asserts that a new Node was created
assert(newNodePtr);
// copies the value passed in to the new Node up to MAX_LENGTH
// characters
strncpy(newNodePtr->word, item, MAX_LENGTH);
// in case the string was truncated, the last character is set
// to the Null character
newNodePtr->word[MAX_LENGTH] = NULL_CHAR;
// prevPtr is initialized to NULL
prevPtr = NULL;
// currPtr is initialized to the head
currPtr = head;
// checks for the end of the list
// loops through until the end of the list is reached
while(currPtr != NULL)
{
// increments prevPtr to currPtr's value
prevPtr = currPtr;
// increments currPtr to the next Node
currPtr = currPtr->next;
}
// sets the new Node's pointer to NULL (end of the list)
newNodePtr->next = currPtr;
// checks for NULL (only one item in the list), and if NULL
// points the head to the new Node
if(prevPtr == NULL)
head = newNodePtr;
// otherwise, the previous pointer is set to the new Node
else
prevPtr->next = newNodePtr;
}
}
/////////////////////////////////////////////////////////////////////
// Function: isPresent
//
// Determines whether or not a particular item is in the list. If
// the item to be found is NULL, no function returns FALSE.
//
// The above mentioned function accomplishes its task by stepping
// through the list and comparing the strings. Boolean value is
// initialized to FALSE, and only set to TRUE if a match is found
//
// Inputs: item - a NULL terminated string that will be searched
// for.
//
// Outputs: A Boolean value meaning:
// TRUE - the item is in the list
// FALSE - the item is NOT in the list
//
Boolean StrList::isPresent(const char *item) const
{
Boolean present = FALSE; // boolean variable initialized to FALSE
Node* searchPtr; // creates a Node pointer for searching
// checks for NULL passed in
if (item)
{
// sets the search pointer to the head
searchPtr = head;
// steps through the list. checks for end of the list or TRUE
while(searchPtr != NULL && present == FALSE)
{
// compares the 2 strings, checking for a match
present = (strcmp(searchPtr->word, item) == 0);
// increments the search pointer
searchPtr = searchPtr->next;
}
}
// returns the boolean value for present
return present;
}
/////////////////////////////////////////////////////////////////////
// Function: getItem
//
// Returns the string at the given position in the list. If the
// value of position is larger than the list or less than 1, the
// return value is NULL.
//
// The above-mentioned function accomplishes its task by stepping
// through the list, counting the nodes until the specified number is
// reached. The corresponding data value is returned.
//
// Inputs: position - an integer that represents a position in the
// the list
//
// Outputs: A pointer to the string in the list or NULL if position
// is invalid
//
/////////////////////////////////////////////////////////////////////
// Function: getItem
//
// Specification: Returns the string at the given position in the
// list. If the value of position is larger than the list or less
// than 1, the return value is NULL.
//
// Implementation: Return NULL if list is empty or client passes
// in an invalid position number. Else, step through the list to
// the position number passed in by client. Return pointer to
// the node's word array.
//
// Inputs: position - an integer that represents a position in the
// the list
//
// Outputs: A pointer to the string in the list or NULL if position
// is invalid
//
const char* StrList::getItem(int position) const
{
// if list empty, or client passes in number less than one, or
// client passes in a number greater than the number of nodes
// in the list, return NULL
if (head == NULL || position < 1 || position > (getCount()))
return NULL;
else
{
// set a new pointer to the first node
Node* currPtr = head;
// step through list with pointer until it is pointing
// to the position number passed in by client
for (int i = 1; i < position; i++)
currPtr = currPtr -> next;
// return a pointer to the item
return (currPtr -> word);
}
}
/////////////////////////////////////////////////////////////////////
// Function: Remove
//
// Removes an item from the list. If the item is in the list, it is
// removed. If the item is not in the list, nothing happens and
// there is NO error message.
//
// The above-mentioned function accomplishes its task by stepping
// through the list, comparing the private data string to the passed
// in string. Once there is a match, the corresponding Node is
// removed by pointing the Node before it to the Node after it, then
// deleting it.
//
// Inputs: item - a NULL terminated string that is searched for in
// the list.
//
// Outputs: None.
//
void StrList::Remove(const char *item)
{
Node* oldPtr; // Node pointer variable for Node removal
Node* ptr; // Node pointer variable for list walk through
// returns if empty list
if (isEmpty())
return;
// checks for match in head
if (strcmp(head->word, item) == 0)
{
// sets the old pointer to the head
oldPtr = head;
// sets the head pointer to the 2nd Node in the list
head = head->next;
// deletes the specified Node
delete oldPtr;
}
// for a match other than in the head position
else
{
// a pointer is initialized to the head
ptr = head;
// checks for end of the list
while (ptr->next)
{
// compares each Node's data to the passed-in item
if (strcmp(ptr->next->word, item) == 0)
{
// if there's a match, old pointer is set to the Node
// to be removed
oldPtr = ptr->next;
// the previous pointer is linked to the pointer after
// the one to be deleted
ptr->next = ptr->next->next;
// the specified Node is deleted
delete oldPtr;
// the function returns control to wherever it was
// called from
break;
}
// the pointer is incremented to the next Node so that the
// next Node's data can be checked
ptr = ptr->next;
}
}
}
Back to Outline