pex14_11.cpp

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

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

#include "keyval.h"
#include "ordlist.h"
#include "seqlist2.h"

template <class K, class T>
class OrderedDictionaryIterator;

// ordered dictionary class derived from an ordered list.
// NOTE! the implementation of this class 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 OrderedDictionary: public OrderedList< KeyValue<K,T> >
{
   // default value for creation of a dictionary entry.
   // used by index operator, InDictionary, and DeleteKey
   private:
      T defaultValue;

   public:
      // constructor
      OrderedDictionary(const T& defval);
      
      // index operator.
      T& operator[] (const K& index);
      
      // additional dictionary methods
      int InDictionary(const K& keyval);
      void DeleteKey(const K& keyval);

      friend class OrderedDictionaryIterator<K,T>;
};

// constructor. initialize base class and defaultValue
template <class K, class T>
OrderedDictionary<K,T>::OrderedDictionary(const T& defaultval):
      OrderedList< KeyValue<K,T> >(), defaultValue(defaultval)
{}

// index operator. here is where most of the work is done
template <class K, class T>
T& OrderedDictionary<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
   // base class SeqList data member llist is set at the data
   // value. llist.Data() is a reference to the data,
   // so rerturn llist.Data().value
   return llist.Data().value;
}

// see if KeyValue object exists with given key
template <class K, class T>
int OrderedDictionary<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 ordered list 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 OrderedDictionary<K,T>::DeleteKey(const K& keyval)
{     
   KeyValue<K,T> tmp(keyval,defaultValue);
   
   Delete(tmp);
}

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

// constructor. dict "is an" OrderedList object.
template <class K, class T>
OrderedDictionaryIterator<K,T>::OrderedDictionaryIterator
                         (OrderedDictionary<K,T>& dict):
             SeqListIterator< KeyValue<K,T> >(dict)
{}

// use the base class method SetList
template <class K, class T>
void OrderedDictionaryIterator<K,T>::SetList(OrderedDictionary<K,T>& dict)
{
	SeqListIterator< KeyValue<K,T> >::SetList(dict);
}

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

// 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;
    }
}

void main(void)
{
    // stream from which we read the data
    ifstream fin;
    String word, definition;
    // the dictionary
    OrderedDictionary<String,String> wordDictionary("");
  
    // 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 dictionary in order
    OrderedDictionaryIterator<String,String> dictIter(wordDictionary);

    // traverse dictionary. print each word and its definition(s)
    cout << "The dictionary is:" << endl << endl;
    for(dictIter.Reset();!dictIter.EndOfList();dictIter.Next())
    {
        PrintEntry(dictIter.Data());
        cout << endl;
    }
    
    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 of Program 14.5>

The 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.
*/