11.cpp

《数据结构与程序设计》书本所有源代码！！！！

/* Program extracts from Chapter 11 of
   "Data Structures and Program Design in C++"
   by Robert L. Kruse and Alexander J. Ryba
   Copyright (C) 1999 by Prentice-Hall, Inc.  All rights reserved.
   Extracts from this file may be used in the construction of other programs,
   but this code will not compile or execute as given here. */


// Section 11.2:

class Trie {
public:  //  Add method prototypes here.

private:  //  data members
   Trie_node *root;
};


const int num_chars = 28;

struct Trie_node {
//    data members
   Record *data;
   Trie_node *branch[num_chars];
//    constructors
   Trie_node();
};


Error_code Trie::trie_search(const Key &target, Record &x) const
/*
Post: If the search is successful, a code of success is
      returned, and the output parameter x is set as a copy
      of the Trie's record that holds target.
      Otherwise, a code of not_present is returned.
Uses: Methods of class Key.
*/
{
   int position = 0;
   char next_char;
   Trie_node *location = root;
   while (location != NULL && (next_char = target.key_letter(position)) != ' ') {
         //  Terminate search for a NULL location or a blank in the target.
      location = location->branch[alphabetic_order(next_char)];
         //  Move down the appropriate branch of the trie.
      position++;
         //  Move to the next character of the target.
   }

   if (location != NULL && location->data != NULL) {
      x = *(location->data);
      return success;
   }
   else
      return not_present;
}


Error_code Trie::insert(const Record &new_entry)
/*
Post: If the Key of new_entry is already in the Trie,
      a code of duplicate_error is returned.
      Otherwise, a code of success is returned and
      the Record new_entry is inserted into the Trie.
Uses: Methods of classes Record and Trie_node.
*/
{
   Error_code result = success;
   if (root == NULL) root = new Trie_node;  //  Create a new empty Trie.
   int position = 0;                        //  indexes letters of new_entry
   char next_char;
   Trie_node *location = root;              //  moves through the Trie
   while (location != NULL &&
         (next_char = new_entry.key_letter(position)) != ' ') {
      int next_position = alphabetic_order(next_char);
      if (location->branch[next_position] == NULL)
         location->branch[next_position] = new Trie_node;
      location = location->branch[next_position];
      position++;
   }
   //  At this point, we have tested for all nonblank characters of new_entry.
   if (location->data != NULL) result = duplicate_error;
   else location->data = new Record(new_entry);
   return result;
}




// Section 11.3:

template <class Record, int order>
class B_tree {
public:  //  Add public methods.

private: //  data members
   B_node<Record, order> *root;
         //  Add private auxiliary functions here.
};


template <class Record, int order>
struct B_node {
//  data members:
   int count;
   Record data[order - 1];
   B_node<Record, order> *branch[order];
//  constructor:
   B_node();
};


template <class Record, int order>
Error_code B_tree<Record, order>::search_tree(Record &target)
/*
Post: If there is an entry in the B-tree whose key matches that in target,
      the parameter target is replaced by the corresponding Record from
      the B-tree and a code of success is returned.  Otherwise
      a code of not_present is returned.
Uses: recursive_search_tree
*/
{
   return recursive_search_tree(root, target);
}


template <class Record, int order>
Error_code B_tree<Record, order>::recursive_search_tree(
           B_node<Record, order> *current, Record &target)
/*
Pre:  current is either NULL or points to a subtree of the B_tree.
Post: If the Key of target is not in the subtree, a code of not_present
      is returned. Otherwise, a code of success is returned and
      target is set to the corresponding Record of the subtree.
Uses: recursive_search_tree recursively and search_node
*/
{
   Error_code result = not_present;
   int position;
   if (current != NULL) {
      result = search_node(current, target, position);
      if (result == not_present)
         result = recursive_search_tree(current->branch[position], target);
      else
         target = current->data[position];
   }
   return result;
}


template <class Record, int order>
Error_code B_tree<Record, order>::search_node(
   B_node<Record, order> *current, const Record &target, int &position)
/*
Pre:  current points to a node of a B_tree.
Post: If the Key of target is found in *current, then a code of
      success is returned, the parameter position is set to the index
      of target, and the corresponding Record is copied to
      target.  Otherwise, a code of not_present is returned, and
      position is set to the branch index on which to continue the search.
Uses: Methods of class Record.
*/
{
   position = 0;
   while (position < current->count && target > current->data[position])
      position++;         //  Perform a sequential search through the keys.
   if (position < current->count && target == current->data[position])
      return success;
   else
      return not_present;
}


template <class Record, int order>
Error_code B_tree<Record, order>::insert(const Record &new_entry)
/*
Post: If the Key of new_entry is already in the B_tree,
      a code of duplicate_error is returned.
      Otherwise, a code of success is returned and the Record new_entry
      is inserted into the B-tree in such a way that the properties of a B-tree
      are preserved.
Uses: Methods of struct B_node and the auxiliary function push_down.
*/
{
   Record median;
   B_node<Record, order> *right_branch, *new_root;
   Error_code result = push_down(root, new_entry, median, right_branch);

   if (result == overflow) {  //  The whole tree grows in height.
                              //  Make a brand new root for the whole B-tree.
      new_root = new B_node<Record, order>;
      new_root->count = 1;
      new_root->data[0] = median;
      new_root->branch[0] = root;
      new_root->branch[1] = right_branch;
      root = new_root;
      result = success;
   }
   return result;
}


template <class Record, int order>
Error_code B_tree<Record, order>::push_down(
                 B_node<Record, order> *current,
                 const Record &new_entry,
                 Record &median,
                 B_node<Record, order> *&right_branch)
/*
Pre:  current is either NULL or points to a node of a B_tree.
Post: If an entry with a Key matching that of new_entry is in the subtree
      to which current points, a code of duplicate_error is returned.
      Otherwise, new_entry is inserted into the subtree: If this causes the
      height of the subtree to grow, a code of overflow is returned, and the
      Record median is extracted to be reinserted higher in the B-tree,
      together with the subtree right_branch on its right.
      If the height does not grow, a code of success is returned.
Uses: Functions push_down (called recursively), search_node,
      split_node, and push_in.
*/
{
   Error_code result;
   int position;
   if (current == NULL) { //  Since we cannot insert in an empty tree, the recursion terminates.
      median = new_entry;
      right_branch = NULL;
      result = overflow;
   }
   else {   //   Search the current node.
      if (search_node(current, new_entry, position) == success)
         result = duplicate_error;
      else {
         Record extra_entry;
         B_node<Record, order> *extra_branch;
         result = push_down(current->branch[position], new_entry,
                            extra_entry, extra_branch);
         if (result == overflow) {  //  Record extra_entry now must be added to current
            if (current->count < order - 1) {
               result = success;
               push_in(current, extra_entry, extra_branch, position);
            }

            else split_node(current, extra_entry, extra_branch, position,
                            right_branch, median);
            //  Record median and its right_branch will go up to a higher node.
         }
      }
   }
   return result;
}


template <class Record, int order>
void B_tree<Record, order>::push_in(B_node<Record, order> *current,
   const Record &entry, B_node<Record, order> *right_branch, int position)
/*
Pre:  current points to a node of a B_tree.  The node *current is not full
      and entry belongs in *current at index position.
Post: entry has been inserted along with its right-hand branch
      right_branch into *current at index position.
*/
{
   for (int i = current->count; i > position; i--) {  //  Shift all later data to the right.
      current->data[i] = current->data[i - 1];
      current->branch[i + 1] = current->branch[i];
   }
   current->data[position] = entry;
   current->branch[position + 1] = right_branch;
   current->count++;
}


template <class Record, int order>
void B_tree<Record, order>::split_node(
   B_node<Record, order> *current,    //  node to be split
   const Record &extra_entry,          //  new entry to insert
   B_node<Record, order> *extra_branch,//  subtree on right of extra_entry
   int position,                  //  index in node where extra_entry goes
   B_node<Record, order> *&right_half, //  new node for right half of entries
   Record &median)                     //  median entry (in neither half)
/*
Pre:  current points to a node of a B_tree.
      The node *current is full, but if there were room, the record
      extra_entry with its right-hand pointer extra_branch would belong
      in *current at position position, 0 <= position < order.
Post: The node *current with extra_entry and pointer extra_branch at
      position position are divided into nodes *current and *right_half
      separated by a Record median.
Uses: Methods of struct B_node, function push_in.
*/
{
   right_half = new B_node<Record, order>;
   int mid = order/2;  //  The entries from mid on will go to right_half.
   if (position <= mid) {   //  First case:  extra_entry belongs in left half.
      for (int i = mid; i < order - 1; i++) {  //  Move entries to right_half.
         right_half->data[i - mid] = current->data[i];
         right_half->branch[i + 1 - mid] = current->branch[i + 1];
      }
      current->count = mid;
      right_half->count = order - 1 - mid;
      push_in(current, extra_entry, extra_branch, position);
   }
   else {  //  Second case:  extra_entry belongs in right half.
      mid++;      //  Temporarily leave the median in left half.
      for (int i = mid; i < order - 1; i++) {  //  Move entries to right_half.
         right_half->data[i - mid] = current->data[i];
         right_half->branch[i + 1 - mid] = current->branch[i + 1];
      }
      current->count = mid;
      right_half->count = order - 1 - mid;
      push_in(right_half, extra_entry, extra_branch, position - mid);
   }
      median = current->data[current->count - 1]; //  Remove median from left half.
      right_half->branch[0] = current->branch[current->count];
      current->count--;
}


template <class Record, int order>
Error_code B_tree<Record, order>::remove(const Record &target)
/*
Post: If a Record with Key matching that of target belongs to the
      B_tree, a code of success is returned and the corresponding node
      is removed from the B-tree.  Otherwise, a code of not_present
      is returned.
Uses: Function recursive_remove
*/
{
   Error_code result;
   result = recursive_remove(root, target);
   if (root != NULL && root->count == 0) {  //  root is now empty.
      B_node<Record, order> *old_root = root;
      root = root->branch[0];
      delete old_root;
   }
   return result;
}


template <class Record, int order>