A symbol table is a data structure of items with keys that supports two basic operations
Also known as dictionaries sometimes.
Operations of interest in the implementations are
Additionally we might also want a standard construct,test if empty , destroy and copy. for example, a search-and-insert operation is often attractive in some implementation.
Symbol Tables are so important to so many computer application that they are available as high-level abstraction in many environments. The C library has bsearch, an implementation of binary search, C++ STL offers a large variety of symbol tables, called “associative containers”.
Instead of talking about specific container we will use items and keys and overload == and < to compare the keys
Sample implementation for item ADT
#include <stdlib.h>
#include <iostream.h>
static int maxKey = 1000;
typedef int Key;
class Item
{
private:
Key keyval;
float info;
public:
Item()
{keyval = maxKey;}
Key key()
{return keyval;}
int null()
{return keyval == maxKey;}
void rand()
{keybal = 1000*::rand()[/]RAND_MAX;
info = 1.0*::rand()[/]RAND_MAX; }
int scan(istream& is = cin)
{return (is>>keyval>>info)!=0;}
void show(ostream& os = cout)
{os<<keyval<<" "<<info <<endl;}
}
ostream& operator<<(ostream& os, Item& x)
{x.show(os); return os;}
Symbol-table abstract data type
template <class Item, class Key>
class ST
{
private:
//Implemenatation-dependent code
public:
ST(int);
int count();
Item search(Key);
void insert(Item);
void remove(Item);
Item select(Item);
void show(ostream&);
};
Example of a symbol-table client
#include <iostream.h>
#include <stdlib.h>
#include "Item.cxx"
#include "ST.cxx"
int main (int argc, char *argv[])
{
int N, maxN=atoi(argv[1]),sw = atoi(argv[2]);
ST<Item, Key> st(maxN);
for( N =0 ; N<maxN; N++){
Item v;
if(sw) v.rand(); else if (!v.scan()) break;
if(!(st.search(v.key())).null()) continue;
st.insert(v);
}
st.show(cout); cout<<endl;
cout<<N<<" keys"<<endl;
cout<<st.count() <<" distinct keys"<<endl;
}