CIS Logo SVC Logo

   Computing & Information Science
   Department

 

Outlook Blackboard Facebook          Search CIS Site       Tutorials

Software Design Using C++



Advanced Linked Lists



A List-Based Table


A fairly sophisticated use of a list is to use it to create a table. As an abstract data type, a table is thought of as a (normally) unordered collection of like data items, with typical operations of creating a table, inserting a new data item into the table, retrieving a data item from the table, and checking to see if a table is empty. The data items are often records, containing a key field along with other data fields. The key field is the one upon which to base data lookup (retrieval). In implementing a table one could use a linked list to actually hold the data items. Of course, other implementations are possible.

The list of files below gives the complete code for creating a list-based table class, named LstTableClass as well as a test program to try out such a table. The test program can be found in the last file and is fairly easy to follow, though the for loop that is used to insert data into the table should be examined carefully.
The first file above does essentially two things: First, it includes the iostream header, not that it is really needed in this file, but so that it will be available in all of the other files of this project. Second, it sets up ItemType as a structure containing fields KeyField and DataField. The first is a long integer, and the second is a float. Note that overloaded operators for equals and greater than are provided. (Overloaded operators can be supplied for either objects or structures.) These are used to tell us whether or not two of our structures are equal, or the first greater than the second, all judged according to their KeyField values. The actual code for these operators is in the second file listed above.

The third through the sixth files in the list above are the same ones that we used in the previous program to give us the classes ListNodeClass and ListClass. Thus we can move on to examine the table.h file. This file declares a class called RamTableBaseClass, which is said to be an abstract base class.

The term base class is used to indicate that we plan to derive a new class from this class. An abstract base class cannot be used to create objects at all. It's only use is in deriving a new class, from which objects can be built. Thus an abstract base class is even closer to our abstract data type idea than an ordinary class. It gives the outline of what functions can be used, but any implementation is left to a derived class. The class declaration for our abstract base class is shown below:


class RamTableBaseClass
   {
   public:
      virtual bool Insert(const ItemType & Item) = 0;
      virtual bool Retrieve(KeyFieldType SearchKey, ItemType & Item) = 0;
      virtual bool Empty(void) const = 0;
   };

It is clear that we expect any table type of class derived from this to have functions called Insert, Retrieve, and Empty with the parameters shown above. But what does the word virtual mean? This indicates that these are virtual functions, the type of functions that support dynamic (run-time) binding. Without the word virtual static binding would be used. With static binding, all function calls have to be figured out at compile time. Suppose that class One and derived class Two each have a different Print function with no parameters. With static binding a call of the form A.Print() is figured out at compile time based on the class that A belongs to. However, if we use a pointer P, it is possible that P->Print() cannot be figured out at compile time since the type of object pointed to may not be known until the program is executed. Thus dynamic binding is needed so that the type of object pointed to can be discovered at run time, and the appropriate version of Print can be called. It may be that we will never need dynamic binding in the type of programs that we will write, but it is safer to allow for that possibility.

What about the unusual = 0 at the end of each function? This indicates that these are pure virtual functions, functions with no code attached. A base class containing at least one pure virtual function is called an abstract base class. Since there is no code (for at least one of the class functions), objects of such a class cannot be created.

We use our abstract base class to derive the new class LstTableClass which implements a list-based table that follows the outline given by RamTableBaseClass. See lsttable.h and lsttable.cpp for the details. The declaration for LstTableClass is shown below as well.


class LstTableClass: public RamTableBaseClass
   {
   public:
      bool Insert(const ItemType & Item);
      bool Retrieve(KeyFieldType SearchKey, ItemType & Item);
      bool Empty(void) const;
   private:
      ListClass List;   // an embedded List object
   };

The new class is derived by public inheritance from RamTableBaseClass. In addition, the three functions are listed so that we can change them to now have associated code. Finally, there is one private data field: a ListClass object. Here is where the table's data will actually be held. Note that it is perfectly legal to embed one object (here a list) inside of another (in this case a table).

There is no constructor or destructor mentioned for this class. That is because there is nothing special that has to be done to create or destroy a LstTableClass object. The automatic constructor and destructor (which allocate and free up space for the object) are fine. Of course, the embedded List object will use its constructor (with the special initialization code that we wrote) when a LstTableClass object is created. Similarly, the destructor for the embedded List object will be called by the automatic LstTableClass destructor.

The code for the three public functions is easy. All that is needed is to call the appropriate list functions to do the dirty work. For example, the Empty function just checks List.Empty(), and the Insert function uses InsertFront on the embedded List object. (Since our table is unordered, it does not matter where we insert the new item into the list.)

The Retrieve function is shown below as it is a little more complex. It places the search key that we are looking for into a structure (record) called Target, but leaves the other field of the structure with garbage data in it. The Find function then does the dirty work of locating this search key in the embedded List. If a match is found, the GetInfo function from class ListNodeClass is used to extract the matching data record from the node pointed to by NodePtr.


/* Given:  Searchkey   A KeyFieldType value to look up.
   Task:   To look for SearchKey in the table given as the implicit object.
   Return: Item        The structure found that contains Searchkey.
           In the function name, returns true if SearchKey was found,
           false otherwise.
*/
bool LstTableClass::Retrieve(KeyFieldType SearchKey, ItemType & Item)
   {
   ListNodePtr NodePtr;
   ItemType Target;

   Target.KeyField = SearchKey;
   NodePtr = List.Find(Target);

   if (NodePtr == NULL)
      return false;
   else
      {
      NodePtr->GetInfo(Item);
      return true;
      }
   }

The following type of drawing is sometimes used to see the overall design in terms of the classes used and how they relate to each other. First, it shows which class is derived from another via inheritance. Second, it shows that a LstTableClass object contains a ListClass object. This is sometimes called aggregation or composition. Finally, it shows that objects of some classes contain pointers to objects of other (or even the same) classes. This is similar to containment, but not quite the same since the object pointed to is outside of the first object. Note that similar drawings are sometimes used in the field of artificial intelligence for general knowledge representation.

[table design drawing]

In the section of these Web pages that discusses binary search trees there is an example of a binary search tree based table. It uses many of the same ideas as in the above program, including the use of an abstract base class.

Related Items

Back to the main page for Software Design Using C++

Author: Br. David Carlson with contributions by Br. Isidore Minerd
Last updated: August 27, 2009
Disclaimer