CountMax function

This is a discussion on CountMax function within the C++ Programming forums, part of the General Programming Boards category; I have this trie class that has a few methods I'm trying to add addtionally two more new methods. A ...

  1. #1
    Registered User
    Join Date
    Apr 2005
    Posts
    53

    CountMax function

    I have this trie class that has a few methods I'm trying to add addtionally two more new methods. A countMax() to count the number of words (x) such that no prefix with at least one letter of (x) is in the Trie. So if I had the words home, homework, tom, tad it would return a count of 3 because both homework and home start with same prefix. and I also tried to create fucntion called countSome where it counts words with exactly three vowels (a,e.i.o.u) each occurring exactly once. Here is what I have so far in the class:

    Code:
    #include <iostream>
    #include <string>
    const int TrieMaxElem = 26;
    const int StrMaxElem = 80;
    
    using namespace std;
    
    class Trie;
    
    class TrieNode {
    private:
        bool StrEnds;
        TrieNode *ptr[TrieMaxElem];
    public:
        TrieNode();
        void SetStrEnds(){StrEnds = true;}
        void UnSetStrEnds(){StrEnds = false;}
        bool GetStrEnds(){return StrEnds;}
        void SetPtr(int i, TrieNode* j){ptr[i]=j;}
        TrieNode* GetPtr(int i){return ptr[i];}
        
    };
    
    TrieNode::TrieNode(){
        StrEnds = false;
        for(int i=0; i<TrieMaxElem; i++)
           ptr[i] = 0;
    }
    
    class Trie {
    public:
        Trie() ;
        void Readlist();
        void Insert(char  x[]);
        bool Member(char  x[]);
        void Delete(char  x[]);
    private:
        TrieNode *root;
        bool Delete(char x[], int i, TrieNode *current );
        bool CheckTrieNodeEmpty(TrieNode *current);
    };
    
    Trie::Trie(){
        root = new TrieNode();
        root->SetStrEnds();
    }
    
    void Trie::Readlist(){
      int numtimes;
      char x[StrMaxElem];
      cout << endl;
      cout << "num of times" << endl;
      cin >> numtimes;
      for ( int i = 1 ; i <= numtimes ; i = i + 1 )
       { cout << "Input String" << endl;
         cin >> x;
         cout << x << endl;
         Insert( x );
       }
    }
    
    void Trie::Insert(char x[]) {
      TrieNode *current = root;
      int i = 0;
      while ( x[i] != '\0' )
       { int j = x[i] - 'a';
         if ( current->GetPtr(j) == 0 )
                  current->SetPtr(j, new TrieNode());
         current = current->GetPtr(j);
         i = i + 1;
       }
      current->SetStrEnds();
    }
    
    void Trie::Delete(char x[])
    {
      TrieNode *current = root;
      int i = 0;
      if (x[i] == '\0') return;
      bool j = Delete(x,i,current);
    }
    
    bool Trie::Delete(char x[], int i, TrieNode *current){
      if (current != 0)
         {if (x[i] == '\0')
               {current -> UnSetStrEnds();
                if (CheckTrieNodeEmpty(current))
                             {delete current; return true;} }
          else {if (Delete(x,i+1,current->GetPtr(x[i] - 'a')))
                   {current->SetPtr(x[i] - 'a', 0);
                   if (i != 0 && CheckTrieNodeEmpty(current))
                             {delete current; return true;} }
               }
         }
      return false;
    }
    
    bool Trie::CheckTrieNodeEmpty
                          (TrieNode *current)
    {
     if (current -> GetStrEnds()) return false;
     for(int i = 0; i<TrieMaxElem; i++)
         if (current->GetPtr( i )) return false;
     return true;
    }
    
    
    bool Trie::Member(char x[]) {
      TrieNode *current = root;
      int i = 0;
      while (x[i] != '\0')
        { int j = x[i] - 'a';
          if ( current->GetPtr(j) == 0 ) return false ;
               else current = current->GetPtr(j);
          i = i+1;
        }
      return  current->GetStrEnds() ;
    }
    
    main()
    { int numtests;
      char newelem[StrMaxElem];
    
      Trie t;
      t.Readlist();
    
      cout << endl;
      cout << "num of tests" << endl;
      cin >> numtests;
      for ( int i = 1 ; i <= numtests ; i = i + 1 )
        { if (i == (i/2)*2)
             { cout << "Input Test String" << endl;
               cin >> newelem;
               cout << newelem << "IS A MEMBER?" << t.Member(newelem) << endl;
             }
         else{ cout << "Delete Test String" << endl;
               cin >> newelem;
               t.Delete(newelem);
               cout << newelem << " Deleted" << endl;
             }
    
        }
    }

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    Do you have a question?

  3. #3
    Registered User
    Join Date
    Apr 2005
    Posts
    53
    I'm trying to add the countMax() function but I'm not sure how to properly check for prefixes.

    Code:
    int countMax(char x[])
    {
        TrieNode *current = root;
         int i = 0;
         if(Member(char x[]))
             //
             //
    
    
    }

  4. #4
    Registered User
    Join Date
    Apr 2005
    Posts
    53
    Anyone have an idea on how to start on this function?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Compiling sample DarkGDK Program
    By Phyxashun in forum Game Programming
    Replies: 6
    Last Post: 01-27-2009, 02:07 AM
  2. Seg Fault in Compare Function
    By tytelizgal in forum C Programming
    Replies: 1
    Last Post: 10-25-2008, 03:06 PM
  3. Another syntax error
    By caldeira in forum C Programming
    Replies: 31
    Last Post: 09-05-2008, 01:01 AM
  4. In over my head
    By Shelnutt2 in forum C Programming
    Replies: 1
    Last Post: 07-08-2008, 06:54 PM
  5. Including lib in a lib
    By bibiteinfo in forum C++ Programming
    Replies: 0
    Last Post: 02-07-2006, 01:28 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21