pex14_12.cpp

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

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

#include "keyval.h"
#include "hash.h"

template <class K, class T>
class HashDictionaryIterator;

// unordered dictionary class derived from a hash table
// collection. NOTE! the Hashtable class uses the LinkedList
// class. this requires that a modified version of the
// LinkedList class be used. the original DeleteFront method
// declares a variable
//		T item;
// this cannot be done when T is KeyValue<K,T>, since
// there is no default constructor for the KeyValue class.
// the new class declares DeleteFront as follows:
//     T& DeleteFront(void);
// dynamic memory is initialized to contain the value
// at the front of the list and a reference to this
// memory is returned by DeleteFront. the modified class
// is in "link.h" with the remainder of the Chapter 14
// programs
template <class K, class T>
class HashDictionary: public HashTable< KeyValue<K,T> >
{
   // default value for creation of a dictionary entry.
   // used by index operator, InDictionary, and DeleteKey
   private:
      T defaultValue;

   public:
      // constructor
      HashDictionary(const T& defaultval,
			int nbuckets, unsigned long hashf(KeyValue<K,T> key));
      
      // index operator.
      T& operator[] (const K& index);
      
      // additional dictionary methods
      int InDictionary(const K& keyval);
      void DeleteKey(const K& keyval);

      friend class HashDictionaryIterator<K,T>;
};

// constructor. initialize base class and defaultValue
template <class K, class T>
HashDictionary<K,T>::HashDictionary(const T& defaultval,
	int nbuckets, unsigned long hashf(KeyValue<K,T> key)):
      HashTable< KeyValue<K,T> >(nbuckets,hashf), defaultValue(defaultval)
{}

// index operator. here is where most of the work is done
template <class K, class T>
T& HashDictionary<K,T>::operator[] (const K& index)
{
   // define a target KeyValue object with the default value
   KeyValue<K,T> targetKey(index,defaultValue);

   // search for key. if not found, insert targetKey
   if(!Find(targetKey))
      Insert(targetKey);
      
   // return reference to data value found or inserted. the
	// HashTable base class data member current points to
	// the selected key-value pair. return a reference to
	// the value field of the KeyValue object
   return current->value;
}

// see if KeyValue object exists with given key
template <class K, class T>
int HashDictionary<K,T>::InDictionary(const K& keyval)
{
   // define a target KeyValue object with the default value
   KeyValue<K,T> tmp(keyval,defaultValue);
   int retval = 1;
   
	// search for tmp in the hash table and return the result
   if(!Find(tmp))
      retval = 0;
   return retval;
}

// delete the KeyValue object with given key from dictionary
template <class K, class T>
void HashDictionary<K,T>::DeleteKey(const K& keyval)
{     
   KeyValue<K,T> tmp(keyval,defaultValue);
   
   Delete(tmp);
}

template <class K, class T>
class HashDictionaryIterator:
                        public HashTableIterator< KeyValue<K,T> >
{
   public:
      // constructor
      HashDictionaryIterator(HashDictionary<K,T>& dict);
      
      // begin iteration of a new dictionary
      void SetList(HashDictionary<K,T>& dict);
};

// constructor. dict "is a" HashTable object.
template <class K, class T>
HashDictionaryIterator<K,T>::HashDictionaryIterator
                         (HashDictionary<K,T>& dict):
             HashTableIterator< KeyValue<K,T> >(dict)
{}

// use the base class method SetList
template <class K, class T>
void HashDictionaryIterator<K,T>::SetList(HashDictionary<K,T>& dict)
{
	HashTableIterator< KeyValue<K,T> >::SetList(dict);
}

#include "strclass.h"   // both key and value fields are Strings

// hash function for use by HashTableDictionary
unsigned long hash(KeyValue<String,String> elem)
{
   unsigned long hashval = 0;
   String key = elem.Key();

   // shift hashval left three bits and add in next character
   for(int i=0;i< key.Length();i++)
      hashval = (hashval << 3) + key[i];
   return hashval;
}

// take a KeyValue object containing a word and
// its definition(s). print it
void PrintEntry(const KeyValue<String,String>& word)
{
    KeyValue<String,String> w = word;
    // word is followed by " - ", so word starts at print
    // position word length + 3
    int linepos = w.Key().Length() + 3;
    int i;
    
    // print word followed by " -". other blank from definition
    cout << w.Key() << " -";
    // print definition(s) on a sequence of 65 character lines
    while(!w.value.IsEmpty())
    {
        // determine if unprinted portion will fit within 65 char
        // line. compute index of the last character on the line
        if(w.value.Length() > 65-linepos)
        {
            // the string will not fit. move backward and find
            // first blank character. we will not split a word
            // between lines
            i = 64-linepos;
            while(w.value[i] != ' ')
                i--;
        }
        else
            // string fits on the line.
            i = w.value.Length()-1;
        // output the substring that fits on the line
        cout << w.value.Substr(0,i+1) << endl;
        // remove substring we just printed. prepare for new line
        w.value.Remove(0,i+1);
        linepos = 0;
    }
}

// a list of KeyValue<String,String> objects is
// represented by an array of pointers. use the
// Shell sort algorithm to reorganize the pointers so
// the corresponding objects are in dictionary order
void ShellSort(Array< KeyValue<String,String> *>& A)
{
	int	i,j,k;
	KeyValue<String,String> *target;

	// select k from the increment sequence
	// ..., 1093, 364, 121, 40, 13, 4, 1. it can
	// be shown that the Shell sort does well with
	// this increment sequence. for 100 data values,
	// k will be 40
	for(k=1;k <= A.ListSize()/2;k = 3*k+1);
	
	for (;k >= 1;k /= 3)
	{
		// sort the sublists. locate *A[k] in the sublist
		// 0 .. k, locate *A[k+1] in the sublist 1..(k+1),
		// locate *A[k+2] in the sublist 2 .. (k+2), etc.
		// when we process i=n-1, all sublists will be sorted
		for(i = k; i < A.ListSize(); i++) 
		{
			target = A[i];
			// move the sublist value before A[j]
			j = i - k;
			// insert target in its sublist. same code as for
			// the insertion sort, except we are using decrement
			// k
			while (j >= 0 && *target < *A[j])
			{
				A[j + k] = A[j];
				j = j - k;
			}  
			A[j + k] = target;
		}
	}
}

void main(void)
{
    // stream from which we read the data
    ifstream fin;
    String word, definition;
    // the dictionary
    HashDictionary<String,String> wordDictionary("",101,hash);
  
    // open the file "defs.dat" of words and their definitions
    fin.open("defs.dat",ios::in | ios::nocreate);
    if (!fin)
    {
        cerr << "The file 'defs.dat' is not found." << endl;
        exit(1);
    }

    // read a word and then a definition. using index operator,
    // insert the word and the definition or update the existing
    // definition by concatenating the current one
    while(fin >> word)
    {
        if (fin.eof())
            break;
		// reads blank following word
        definition.ReadString(fin,'\n');
        wordDictionary[word] += definition;
    }
    
	 // declare an iterator to traverse the unordered dictionary
	 HashDictionaryIterator<String,String> dictIter(wordDictionary);
	 // declare an array of KeyValue<String,String> pointers. the
	 // pointers will be set to the address of KeyValue objects
	 // extracted by traversing the unordered dictionary. note that
	 // we deal with pointers, since we cannot declare an array of
	 // KeyValue objects here. there is no default constructor
	 Array< KeyValue<String,String> * >
	 			sortedList(wordDictionary.ListSize());
	 int i = 0;

	 // traverse dictionary. print each word and its definition(s)
	 // initialize the elements of sortedList
    cout << "The dictionary is:" << endl << endl;
    for(dictIter.Reset();!dictIter.EndOfList();dictIter.Next())
    {
        PrintEntry(dictIter.Data());
		  cout << endl;
        sortedList[i++] = new KeyValue<String,String> (dictIter.Data());
    }
    
    // sort the KeyValue objects by using their pointers
	 ShellSort(sortedList);

	 // print the sorted dictionary entries and delete them
	 cout << endl << "The sorted dictionary is:" << endl << endl;
	 for(i=0;i < sortedList.ListSize();i++)
	 {
		  PrintEntry(*sortedList[i]);
		  cout << endl;
		  delete sortedList[i];
	 }
    // clear the dictionary
	 wordDictionary.ClearList();
}

/*
<File "defs.dat">

program A list of the acts, speeches, pieces.
finish To bring to an end.
cause Anything producing an effect or result.
sextet A group of six performers. 
program A sequence of operations executed by a computer.
velocity Quickness of motion; swiftness.
cook To prepare by boiling, baking, frying, etc.
muff A cylindrical covering of fur to keep the hands warm.
banner A headline running across a newspaper page.
sextet A composition for six instruments.

<Run>

The dictionary is:

cook - To prepare by boiling, baking, frying, etc.

sextet - A group of six performers.  A composition for six
instruments.

velocity - Quickness of motion; swiftness.

program - A list of the acts, speeches, pieces. A sequence of
operations executed by a computer.

muff - A cylindrical covering of fur to keep the hands warm.

cause - Anything producing an effect or result.

banner - A headline running across a newspaper page.

finish - To bring to an end.


The sorted dictionary is:

banner - A headline running across a newspaper page.

cause - Anything producing an effect or result.

cook - To prepare by boiling, baking, frying, etc.

finish - To bring to an end.

muff - A cylindrical covering of fur to keep the hands warm.

program - A list of the acts, speeches, pieces. A sequence of
operations executed by a computer.

sextet - A group of six performers.  A composition for six
instruments.

velocity - Quickness of motion; swiftness.
*/