Witam,
mam dość dziwny problem pojawiający się przy dodawaniu słów do drzewa trie. Sam kod działa (moim zdaniem) bez zarzutu oprócz małego szczegółu. Gdy jako nowe słowo wpiszę ciąg znaków ze spacją między nimi (np. XX YY) to tak jak w założeniu do struktury zapisywana jest pierwsza część ciągu (XX) ale jakaś część tego stringa jest przypisywana do zmiennej "action" w menu głównym co powoduje wystąpienie komunikatu o błędnej wartości (warunek else w funkcji main).
I tutaj kieruję do wszystkich pytanie : skąd się to bierze i jak to naprawić ? Z góry dziękuję za pomoc.
KOD :
#include <iostream>
#include <cstdlib>
#include <string>
#define CONVERT 97
#define ALPHABET_SIZE 26
using namespace std;
class Element
{
public:
Element *parent;
Element *children[ALPHABET_SIZE];
bool exist;
};
class Trie
{
public:
Element *root;
Trie()
{
root = new(Element);
root->parent = NULL;
for(int i = 0;i<ALPHABET_SIZE;i++)
{
root->children[i] = NULL;
}
}
void add_word(Element *root , string word)
{
int index;
word = get_lower(word);
int word_length = word.length();
Element *temp = root;
int j;
for(int i=0;i<word_length;i++)
{
index = word[i]-CONVERT;
if(!temp->children[index])
{
Element *new_element = new(Element);
for(j=0;j<ALPHABET_SIZE;j++)
new_element->children[j]=NULL;
new_element->parent = temp;
temp->children[index] = new_element;
temp->exist = false;
}
if(!temp->children[index])
{
cout << "Nie udalo sie dodac wyrazu..." << endl;
return;
}
else
temp=temp->children[index];
}
temp->exist = true;
cout << "Pomyslnie dodano wyraz !" << endl;
}
void delete_word(Element *temp , string word)
{
int index , i;
int word_length = word.length();
word = get_lower(word);
for(i=0;i<word_length;i++) //Przejscie do
{ // ostatniej litery
index = word[i]-CONVERT;
if(temp->children[index] != NULL)
temp = temp->children[index];
}
if(temp->exist==true && i==word_length)
{
temp->exist = false;
if(is_leaf(temp)) // Jesli obiekt jest lisciem to nalezy go usunac
{
Element* del;
while(is_leaf(temp) && temp->parent)
{
index = word[--word_length] - CONVERT;
del = temp;
temp = temp->parent;
delete(del);
temp->children[index] = NULL;
}
cout << "Pomyslnie usunieto wyraz !" << endl; return;
}
else{cout << "Pomyslnie usunieto wyraz !" << endl; return;} // Jesli obiekt nie jest lisciem to wystarczy zmienic zmienna exist na false
}
else {cout <<"Nie znaleziono podanego wyrazu !"<<endl; return;}
return;
}
void delete_tree(Element *root)
{
for(int i=0;i<ALPHABET_SIZE;i++)
{
if(root->children[i])
{
delete_tree(root->children[i]);
}
}
Element* temp = root;
//root = temp;
for(int i=0;i<ALPHABET_SIZE;i++)
{temp->children[i] = NULL;}
if(temp->parent == NULL)return;
delete(temp);
}
void search_word(Element *root , string word)
{
Element *temp = root;
int index;
int word_length = word.length();
word = get_lower(word);
for(int i=0;i<word_length;i++)
{
index = word[i]-CONVERT;
if(temp->children[index]==NULL){cout << "Nie znaleziono zadanego slowa..." << endl;return;}
else temp=temp->children[index];
if(i==word_length-1 && temp->exist==true){cout << "Znaleziono zadane slowo !" << endl;return ;}
if(i==word_length-1){cout << "Podana fraza jest prefiksem innego slowa !" << endl; return;}
}
return;
}
void print_all(Element *root , string word)
{
if(root->exist==1){cout << word << endl;}
for(int i=0;i<ALPHABET_SIZE;i++)
{
if(root->children[i]!=NULL)
{
char X = (i+CONVERT);
print_all((root->children[i]) , word + X);
}
}
}
bool is_leaf(Element *root)
{
Element* temp = root;
for(int j=0;j<ALPHABET_SIZE;j++) // sprawdzanie czy ostatni obiekt posiada potomkow
{
if(temp->children[j]!=NULL)
{return false;}
}
return true;
}
inline string get_lower(string word)
{
for(int i=0;word[i];i++)
word[i] = tolower(word[i]);
return word;
}
};
int main()
{
Trie tree;
char action;
string word;
cout << "Program obslugujacy drzewo trie z 26 literowym alfabetem (a-z)." << endl
<< endl;
while(1)
{
cout<< "**********************************" << endl
<< " MENU GLOWNE " << endl
<< "**********************************" << endl
<< "#1 Dodaj slowo" << endl
<< "#2 Usun slowo " << endl
<< "#3 Wyswietl zawartosc drzewa" << endl
<< "#4 Wyszukaj slowo" << endl
<< "#5 Wyczysc zawartosc drzewa" << endl
<< "#0 Zakoncz dzialanie programu" << endl
<< " Wybierz operacje : ";
cin >> action;
if(action == '0')
{
system("cls");
break;
}
else if(action == '1')
{
system("cls");
cout << "Podaj slowo ktore zostanie wpisane do struktury : ";
cin >> word;
tree.add_word(tree.root , word);
word.clear();
}
else if(action == '2')
{
system("cls");
cout << "Podaj slowo ktore zostanie usuniete ze struktury : ";
cin >> word;
tree.delete_word(tree.root , word);
}
else if(action == '3')
{
system("cls");
cout << "Zawartosc drzewa : " << endl;
tree.print_all(tree.root , word);
}
else if(action == '4')
{
system("cls");
cout << "Podaj slowo : " ;
cin >> word;
tree.search_word(tree.root , word);
}
else if(action == '5')
{
system("cls");
tree.delete_tree(tree.root);
cout << endl << "Pomyslnie wyczyszczono zawartosc drzewa !" << endl;
}
else
{
system("cls");
cout << "Podano niepoprawna wartosc !" << endl;
}
} // GLOWNY WHILE
tree.delete_tree(tree.root);
delete(tree.root);
cout << "Zakonczono dzialanie programu..." << endl;
return 0;
}