A Sorted String List

This is the code that I showed in class on Monday night. I encourage students to compile and run this example as it will lend insight into the power and efficiency of inheritance.

strlist.h

#include "bool.h"

#ifndef STRLIST_H

  #define STRLIST_H
  struct Node;
  const int MAX_STR_LENGTH = 30;

  class StrList
  {
    public:
      StrList(void);
      ~StrList(void);

      void Append(const char* item);
      void Prepend(const char* item);
      void Remove(const char* item);

      void Display(Boolean separateLine = TRUE) const;
      int getCount(void) const;
      Boolean isEmpty(void) const;
      Boolean isPresent(const char* item) const;
      const char* getItem(int position) const;

    protected:
      Node* head;
  };

#endif

sstrlist.h

#include "strlist.h"

#ifndef SSTRLIST_H

  #define SSTRLIST_H

  class SortedStrList : public StrList
  {
    public:
      SortedStrList(void);
      void Insert(const char* item);
  };

#endif

sstrlist.cpp

#include "sstrlist.h"
#include <string.h>

struct Node
{
  char word[MAX_STR_LENGTH + 1];
  Node* next;
};

SortedStrList::SortedStrList(void) : StrList()
{
}

void SortedStrList::Insert(const char* item)
{
  if (!item)
    return;

  Node* currPtr;
  Node* prevPtr;
  Node* newNodePtr;

  newNodePtr = new Node;
  strncpy(newNodePtr->word, item, MAX_STR_LENGTH);
  newNodePtr->word[MAX_STR_LENGTH] = NULL;
       
  prevPtr = NULL;
  currPtr = head;

  while (currPtr != NULL && (strcmp(item, currPtr->word) > 0))
  {
    prevPtr = currPtr;
    currPtr = currPtr->next;
  }

  newNodePtr->next = currPtr;
  if (prevPtr == NULL)
    head = newNodePtr;
  else
    prevPtr->next = newNodePtr;
}

This is client code, perhaps driver.cpp

#include "sstrlist.h"
#include <iostream.h>

void main(void)
{
  SortedStrList list;

  list.Insert("One");
  list.Insert("Two");
  list.Insert("Three");
  list.Insert("Four");
  list.Insert("Five");
  list.Insert("Six");
  list.Display();
  cout << endl;

  list.Remove("Four");
  list.Display();
  cout << endl;

  list.Append("Apple");
  list.Prepend("Zero");
  list.Display();
}

Output:

Five
Four
One
Six
Three
Two

Five
One
Six
Three
Two

Zero
Five
One
Six
Three
Two
Apple

To compile this example on PCC's AIX compiler and have an executable named testsort, use this command line:

xlC -o testsort driver.cpp strlist.cpp sstrlist.cpp

Back to Outline