pex14_7.cpp

数据结构C++代码,经典代码,受益多多,希望大家多多支持

#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
#pragma hdrstop

#include "strclass.h"
#include "strfreq.h"

#include "list.h"
#include "iterator.h"

// records in the open probe table
template <class T>
struct TableRecord
{
	// entry available (True or False)
	int available;
	T data;
};

template <class T>
class OpenProbeIterator;

template <class T>
class OpenProbe: public List<T>
{
	protected:
		// dynamically created open probe table
		// and its size
		TableRecord<T> *table;
		int tableSize;
		
		// hash function
		unsigned long (*hf)(T key);

		// index of last table element accessed
		int lastIndex;
	public:
		// constructor, destructor
		OpenProbe(int tabsize,unsigned long hashf(T key));
		~OpenProbe(void);

		// standard list handling methods
		virtual void Insert(const T& key);
		// not actually implemented
		virtual void Delete(const T& key);
		virtual int Find(T& key);
		virtual void ClearList(void);

		// update last table entry accessed
		void Update(const T& key);

		friend class OpenProbeIterator<T>;
};
		
// initialize the hash table. assign the table size and the hash
// function from the parameter list. lastIndex should be -1 to
// indicate that we have not yet located ourselves at a data value.
// dynamically allocate the hash table with tabsize entries and
// clear it by assigning each available field to True(1).
template <class T>
OpenProbe<T>::OpenProbe(int tabsize,unsigned long hashf(T key)):
		tableSize(tabsize), hf(hashf), lastIndex(-1) 
{
	table = new TableRecord<T> [tableSize];
	if (table == NULL)
	{
		cerr << "Not enough memory available for the hash table." << endl;
		exit(1);
	}
	ClearList();
}

// destructor. delete memory for the hash table
template <class T>
OpenProbe<T>::~OpenProbe(void)
{
	delete [] table;
}
		
// insert key into the hash table
template <class T>
void OpenProbe<T>::Insert(const T& key)
{
	// compute the hash index
	int index = int(hf(key) % tableSize), origindex;
	
	// save the original hash index
	origindex = index;

	// cycle through the table until an empty slot is found, a data
	// match occurs or we come back to origindex.
	do
	{
		// test whether the table slot is empty or the key matches
		// the data field of the table entry
		if (table[index].available == 1 || key == table[index].data)
		{
			// in either case, assign key to the data field
			table[index].data = key;
			// if the slot was emtpy, mark it full and the base class
			// data value size
			if (table[index].available == 1)
			{
				table[index].available = 0;
				size++;
			}
			// update lastIndex to our current location and return
			lastIndex = index;
			return;
		}
		// we are not yet successful. move to the next table slot
		index = (index+1) % tableSize;
	} while (index != origindex);
	
	// we have gone around the table and could not insert or update
	// the data. the table is full!. terminate the program
	cerr << "OpenProbe: table full" << endl;
	exit(1);
}

template <class T>
void OpenProbe<T>::Delete(const T&)
{
	cerr << "OpenProbe: Delete is not implemented" << endl;
}

// search for key in the hash table
template <class T>
int OpenProbe<T>::Find(T& key)
{
	// compute the hash index
	int index = int(hf(key) % tableSize), origindex;
	
	// save the original hash index 
	origindex = index;

	// cycle through the table until we locate the data item,
	// find any emtpy slot or search every slot
	do
	{
		// hit an empty slot. return False
		if (table[index].available == 1)
			return 0;
		else
		if (table[index].data == key)
		{
			// found a match. update the data and lastIndex
			// and return True
			key = table[index].data;
			lastIndex = index;
			return 1;
		}
		// advance forward
		index = (index+1) % tableSize;
	} while (index != origindex);

	// every table slot is occupied and we did not
	// find the data item
	return 0;
}
			
// mark all table slots as available (empty) and
// assign size to 0 (emtpy list) and lastIndex to -1
// (no current data value)
template <class T>
void OpenProbe<T>::ClearList(void)
{
	for(int i=0;i < tableSize;i++)
		table[i].available = 1;
	size = 0;
	lastIndex = -1;
}

// update the item we last found or inserted
template <class T>
void OpenProbe<T>::Update(const T& key)
{		
	// if lastIndex is not -1 and the keys match, update
	// the data at lastIndex
	if (lastIndex != -1 && table[lastIndex].data == key)
			table[lastIndex].data = key;
	else
		// insert the data in the table
		Insert(key);
}

// traverse and OpenProbe object
template <class T>
class OpenProbeIterator: public Iterator<T>
{
	private:
		// points to the hash table that must be traversed
		OpenProbe<T> *hashTable;
		
		// index of current table slot
		int current;
	public:
		// constructor
		OpenProbeIterator(OpenProbe<T>& ht);

		// basic iterator methods
		virtual void Next(void);
		virtual void Reset(void);
		virtual T& Data(void);

		// arrange for the iterator to traverse another table
		void SetList(OpenProbe<T>& lst);
};

// constructor; initialize both the base class
// and hashTable. call Reset to get positioned
// at the first non-empty table slot	
template <class T>
OpenProbeIterator<T>::OpenProbeIterator(OpenProbe<T>& ht):
	Iterator<T>(), hashTable(&ht)
{
	Reset();
}

// move to the next data item in the table
template <class T>
void OpenProbeIterator<T>::Next(void)
{
	// move forward until we find a filled slot or get back
	// to table location 0
	do
	{
		current = (current+1) % hashTable->tableSize;
	} while (current != 0 && hashTable->table[current].available == 1);

	// the iteration is complete if we have come around the table
	// back to 0
	if (current == 0)
		iterationComplete = 1;
}

// get positioned at the first non-empty table slot
template <class T>
void OpenProbeIterator<T>::Reset(void)
{
	// if the table is empty, just return
	if ((iterationComplete = hashTable->ListEmpty()) != 0)
		return;
	// the table is not empty. start at index 0 and look
	// for an occupied table slot
	current = 0;
	while(hashTable->table[current].available == 1)
		current++;
}

// return the data value of the current data value
// in the iteration
template <class T>
T& OpenProbeIterator<T>::Data(void)
{
	// error if table empty or we have completed traversal
	if (iterationComplete)
	{
		cerr << "OpenProbeIterator: invalid data reference!" << endl;
		exit(1);
	}
	return hashTable->table[current].data;
}

// ready the object to travese another OpenProbe object
template <class T>
void OpenProbeIterator<T>::SetList(OpenProbe<T>& lst)
{
	hashTable = &lst;
	Reset();
}

void main(void)
{
	 // read the strings from stream fin
	 ifstream fin;
	 NameRecord rec;
	 String token;
	 OpenProbe<NameRecord> HF(101,hash);
	 
	 fin.open("strings.dat", ios::in | ios::nocreate);
	 if (!fin)
	 {
			cerr << "Could not open \"strings.dat\"!" << endl;
			exit(1);
	 }

	 while(fin >> rec.name)
	 {
			// look for string in table; if present, update count
			if (HF.Find(rec))
			{
				rec.count += 1;
				HF.Update(rec);
			}
			else
			{
				rec.count = 1;
				HF.Insert(rec);
			}
	 }
	 
	 // print the strings and their frequency
	 OpenProbeIterator<NameRecord> hiter(HF);
	 
	 for(hiter.Reset();!hiter.EndOfList();hiter.Next())
	 {
			rec = hiter.Data();
			cout << rec.name << ": " << rec.count << endl;
	 }
}

/*
<File "strings.dat">

Columbus Washington Napoleon Washington Lee Grant
Washington Lincoln Grant Columbus Washington

<Run>

Lee: 1
Washington: 4
Lincoln: 1
Napoleon: 1
Grant: 2
Columbus: 2
*/