Вставка в Trie в C++

Question

Я делаю еще один проект для школы, который реализует согласование с абстрактным типом данных Trie. У меня все работает, кроме функции вставки. У меня проблемы с этим.

Иногда, когда я пытаюсь что-то вставить, он не вставлен. В других случаях возникает ошибка сегментации. Я не совсем уверен, где я ошибаюсь, так как большая часть кода для функции вставки пришла от моего профессора. Я знаю, что операции для стека правильны, поскольку это произошло из более раннего проекта.

Примечание: Нам было сказано использовать маркер конца, чтобы удерживать количество раз, когда слово появляется в согласии.

Заранее благодарен!

concordance.h

#ifndef CONCORDANCE_H 
#define CONCORDANCE_H 
#include "stack.h" 
#include <iostream> 
#include <cstdlib> 

const int MAX = 8;  // Maximum length of word 

class Concordance 
{ 
    public: 
     typedef char Item[MAX+1]; 

     // Constructor 
     Concordance() { root = NULL; } 

     // Destructor 
     ~Concordance(); 

     // Modification Member Functions 
     void insert(Item entry); 

     // Constant Member Functions 
     int length(); 
     void print(std::ostream& out_s); 

    private: 
     // Data Members 
     struct Node 
     { 
      int end_marker; 
      Node *children[26]; 
     }; 
     Node *root; 

     void help_insert(Node* &r, Item w, int pos); 
     int find_size(Node *r); 
     void help_print(std::ostream& out_s, Node *r, Stack &s); 
     void destroy(Node *r); 
}; 
#endif 

concordance.cpp

#include "concordance.h" 
#include <iostream> 
#include <iomanip> 
#include <cstring> 
using namespace std; 

// Destroy function and destructor 
void Concordance::destroy(Node *r) 
{ 
    if(r != NULL) 
    { 
     for(int i = 0; i < 26; ++i) 
      destroy(r -> children[i]); 
     delete r; 
    } 
} 

Concordance::~Concordance() 
{ 
    destroy(root); 
} 



// Functions to insert into the tree 
void Concordance::help_insert(Node* &r, Item w, int pos) 
{ 
    if (r == NULL) 
    { 
     r = new Node; 
     r -> end_marker = 0; 
     for(int i = 0; i < 26; ++i) 
      r -> children[i] = NULL; 
    } 
    if (w[pos] == '\0' && r -> end_marker > 0) 
     r -> end_marker = r -> end_marker + 1; 
    else if (w[pos] == '\0' && r -> end_marker == 0) 
     r -> end_marker = 1; 
    else 
     help_insert (r -> children[w[pos] - 'a'], w, pos + 1); 
} 

void Concordance::insert(Item entry) 
{ 
    help_insert(root, entry, 0); 
} 



// Functions to count the number of words in the tree 
int Concordance::find_size(Node *r) 
{ 
    int count = 0; 
    if (r == NULL) 
     return 0; 
    if (r -> end_marker > 0) 
     count = 1; 
    for(int i = 0; i < 26; ++i) 
     count += find_size(r -> children[i]); 
    return count; 
} 

int Concordance::length() 
{ 
    return find_size(root); 
} 



// Functions to print the tree to an output stream 
void Concordance::print(ostream& out_s) 
{ 
    Stack s; 
    help_print(out_s, root, s); 
} 

void Concordance::help_print(ostream& out_s, Node *r, Stack &s) 
{ 
    if (r != NULL) 
    { 
     if (r -> end_marker > 0) 
      s.st_print(out_s); 
     for (int i = 0; i < 26; ++i) 
     { 
      s.push(i + 'a'); 
      help_print(out_s, r -> children[i], s); 
      s.pop(); 
     } 
    } 
} 

Главная Программа

#include <iostream> 
#include <iomanip> 
#include <fstream> 
#include <cstring> 
#include "concordance.h" 
using namespace std; 

typedef char Word[MAX+1]; 

void read_word(ifstream& infile, Word array) 
{ 
    char ch; 
    int i = 0; 

    infile.get(ch); 

    while(!infile.eof() && isalpha(ch) && !isspace(ch) && !ispunct(ch)) 
    { 
     if(i > MAX-1) 
     { 
      while(!isspace(ch) && !ispunct(ch)) 
       infile.get(ch); 
      break; 
     } 

     ch = toupper(ch); 

     array[i] = ch; 
     i++; 
     infile.get(ch); 
    } 
    if(i != 0) 
     array[i] = '\0'; // Null Character 
} 

void make_list(ifstream& infile, Word& array) 
{ 
    Concordance concord; 
    int count = 1; 
    int length; 

    read_word(infile, array);    // Read a word 
    while(!infile.eof())     // While the file isn't empty... 
    { 
     concord.insert(array);    // Insert into concordance 
     read_word(infile, array);   // Read another word 
    } 

    concord.print(cout); 
    length = concord.length(); 

    cout << "The file contains " << length << " distinct words." << endl; 
} 

int main() 
{ 
    char file_name[100]; 
    typedef char Word[MAX+1]; 
    ifstream infile; 
    Word array; 

    cout << "Enter a file name: "; 
    cin >> file_name;    // Get file name 

    infile.open(file_name);   // Open file 
    if(!infile)      // If we couldn't open the file... 
    { 
     cout << "Failed to open file." << endl; 
     return 0; 
    } 

    make_list(infile, array);  // Make the concordance 

    infile.close();     // Close the input file 

    return 0; 
} 

Answer 1

Этот бит O е код переходит от родителей к ребенку, если предположить, что следующий символ нижний регистр:

help_insert (r -> children[w[pos] - 'a'], w, pos + 1); 

Однако преобразовать всю строку ввода в верхнем регистре здесь:

ch = toupper(ch); 

либо изменить trie, чтобы ожидать верхний регистр, или изменить свой код, чтобы передать строки в нижнем регистре. Два алфавита расположены в 32 положениях в ASCII, и поэтому вы индексируетесь за пределами массива children в узлах trie.