tablea.h

Data Abstraction & Problem Solving with C++源码

// Define MAX_TABLE before compilation

// *********************************************************
// Header file TableA.h for the ADT table. 
// Sorted array-based implementation.
// Assumption: A table contains at most one item with a 
//             given search key at any time.
// *********************************************************
#include "KeyedItem.h"  // definition of KeyedItem
                        // and KeyType
#include "TableException.h"
const int MAX_TABLE = maximum-size-of-table;

typedef KeyedItem TableItemType;
typedef void (*FunctionType)(TableItemType& anItem);

class Table
{
public:
   Table();  // default constructor
   // copy constructor and destructor are
   // supplied by the compiler

// Table operations:
// Precondition for all operations: 
// No two items of the table have the same search key.
// The table's items are sorted by search key.

   virtual bool tableIsEmpty() const;
   // Determines whether a table is empty.
   // Postcondition: Returns true if the table is empty;
   // otherwise returns false.

   virtual int tableLength() const;
   // Determines the length of a table.
   // Postcondition: Returns the number of items in the 
   // table.

   virtual void tableInsert(const TableItemType& newItem)
                            throw(TableException);
   // Inserts an item into a table in its proper sorted
   // order according to the item's search key.
   // Precondition: The item to be inserted into the table 
   // is newItem, whose search key differs from all search 
   // keys presently in the table.
   // Postcondition: If the insertion is successful, 
   // newItem is in its proper order in the table.
   // Exception: Throws TableException if the item cannot 
   // be inserted.


   virtual void tableDelete(KeyType searchKey)
                            throw(TableException);
   // Deletes an item with a given search key from a table.
   // Precondition: searchKey is the search key of the item 
   // to be deleted.
   // Postcondition: If the item whose search key equals
   // searchKey existed in the table, the item is deleted.
   // Exception: Throws TableException if the item does not 
   // exist.

   virtual void tableRetrieve(KeyType searchKey,
                            TableItemType& tableItem) const
                            throw(TableException);
   // Retrieves an item with a given search key from a 
   // table.
   // Precondition: searchKey is the search key of the item 
   // to be retrieved.
   // Postcondition: If the retrieval is successful,
   // tableItem contains the retrieved item. 
   // Exception: Throws TableException if the item 
   // does not exist.

   virtual void traverseTable(FunctionType visit);
   // Traverses a table in sorted search-key order, calling 
   // function visit() once for each item.
   // Precondition: The function represented by visit()
   // exists outside of the ADT implementation.
   // Postcondition: visit()'s action occurs once for each 
   // item in the table.
   // Note: visit() can alter the table.

protected:
   void setSize(int newSize);
   // Sets the private data member size to newSize.

   void setItem(const TableItemType& newItem, int index);
   // Sets items[index] to newItem.

   int position(KeyType searchKey) const;
   // Finds the position of a table item or its insertion 
   // point.
   // Precondition: searchKey is the value of the search key
   // sought in the table.
   // Postcondition: Returns the index (between 0 and 
   // size - 1) of the item in the table whose search key 
   // equals searchKey. If no such item exists, returns the 
   // position (between 0 and size) that the item would 
   // occupy if inserted into the table. The table is 
   // unchanged.

private:
   TableItemType items[MAX_TABLE];  // table items
   int           size;              // table size

   int keyIndex(int first, int last, KeyType searchKey) const;
   // Searches a particular portion of the private array 
   // items for a given search key by using a binary search.
   // Precondition: 0 <= first, last < MAX_TABLE, where
   // MAX_TABLE = max size of the array, and the array
   // items[first..last] is sorted in ascending order by 
   // search key.
   // Postcondition: If searchKey is in the array, returns
   // the index of the array element that contains 
   // searchKey; otherwise returns the index (between first 
   // and last) of the array element that the item would 
   // occupy if inserted into the array in its proper order.
   // The array is unchanged.
};  // end Table class
// End of header file.