trie.cpp

来自「数据结构与程序设计教材源码 数据结构与程序设计教材源码」· C++ 代码 · 共 156 行

 
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;
}
 
Trie::Trie()
{
   root = NULL;
}
 
bool Trie::empty()
{
   return root == NULL;
}
 
void recursive_inorder(Trie_node *root, void (*visit)(Record *))
/* 
 
Post: The subtrie referenced by
      root is traversed, in order.  The operation
      *visit is applied to all records of the trie.
 
*/
{
   if (root != NULL) {
      (*visit)(root->data);
      for (int i = 0; i < num_chars; i++) recursive_inorder(root->branch[i], visit);
   }
}
 
void Trie::inorder(void (*visit)(Record *))
/* 
 
Post: The Trie is traversed, in order, and the operation
      *visit is applied to all records of the trie.
 
*/
{
   recursive_inorder(root, visit);
}
 
int recursive_size(Trie_node *root)
{
   if (root != NULL) {
      int answer = 0;
      if (root->data != NULL) answer = 1;
      for (int i = 0; i < num_chars; i++) answer += recursive_size(root->branch[i]);
      return answer;
   }
   else return 0;
}
 
int Trie::size()
{
   return recursive_size(root);
}
 
int recursive_height(Trie_node *root)
{
   if (root != NULL) {
      int max = 0, answer;
      for (int i = 0; i < num_chars; i++) {
         answer = recursive_height(root->branch[i]);
         if (answer > max) max = answer;
      }
      return max + 1;
   }
   else return 0;
}
 
int Trie::height()
{
   return recursive_height(root);
}
 
void recursive_clear(Trie_node *&root)
{
   if (root != NULL) {
      for (int i = 0; i < num_chars; i++)
         recursive_clear(root->branch[i]);
      if (root->data != NULL) delete root->data;
      delete root;
      root = NULL;
   }
}
 
void Trie::clear()
{
   recursive_clear(root);
}
 
Trie::~Trie()
{
   clear();
}