дерево цифрового поиска

  • Автор темы -
  • Дата начала
Статус
Закрыто для дальнейших ответов.

Гость
#1
Если я буду добавлять слова в таком порядке: dog, do, doggy, caty, то слово doggy не будет найдено. Если сначала do, то все нормально. Много раз переделывала, но что-то не получается. В коде признаком завершения слова является пробел. Посмотрите, может кто-то что-то подскажет как исправить мою ошибку и вообще можно ли как-нибудь переделать/улучшить весь код.
Код:
#include "stdafx.h"
#include "windows.h"
#include <iostream>
#include<string>

using namespace std;
const int m=3,n=19;

struct elem{
char bukva;
elem *next;
elem *down;
};
class DigitalTree{
elem *tr;
public:
DigitalTree(){tr=NULL;};
~DigitalTree(){};
void add(char *str);
void remove(char *str);
int find(char *str);

};
string chtooem(string str)
{
char* buf=new char[str.size()+1];
CharToOem (str.c_str(),buf);
string res(buf);
delete[] buf;
return res;
}

int main(int argc, char* argv[])
{
char *s1="dog";
char *s2="doggy";
char *s3="do";
char *s4="caty";
DigitalTree tree;
tree.add(s1);
tree.add(s2);
tree.add(s3);
tree.add(s4);
cout<<chtooem("добавили слова:")<<endl<<s1<<endl<<s2<<endl<<s3<<endl<<s4<<endl;
cout<<endl;
if (tree.find(s1)==-1)
cout<< chtooem("слово ")<<s1<<chtooem(" не найдено\n");
else 
cout<<chtooem("слово ")<<s1<<chtooem(" найдено\n");
if (tree.find(s2)==-1)
cout<< chtooem("слово ")<<s2<<chtooem(" не найдено\n");
else 
cout<<chtooem("слово ")<<s2<<chtooem(" найдено\n");
if (tree.find(s3)==-1)
cout<< chtooem("слово ")<<s3<<chtooem(" не найдено\n");
else 
cout<<chtooem("слово ")<<s3<<chtooem(" найдено\n");
if (tree.find(s4)==-1)
cout<< chtooem("слово ")<<s4<<chtooem(" не найдено\n");
else 
cout<<chtooem("слово ")<<s4<<chtooem(" найдено\n");
cout<<chtooem("удаляем ")<</*s1<<" , "<<*/s2;
tree.remove(s2);
//	tree.remove(s3);
cout << endl;
if (tree.find(s2)==-1)
cout<< chtooem("слово ")<<s2<<chtooem(" не найдено\n");
else 
cout<<chtooem("слово ")<<s2<<chtooem(" найдено\n");
if (tree.find(s3)==-1)
cout<< chtooem("слово ")<<s3<<chtooem(" не найдено\n");
else 
cout<<chtooem("слово ")<<s3<<chtooem(" найдено\n");
if (tree.find(s1)==-1)
cout<< chtooem("слово ")<<s1<<chtooem(" не найдено\n");
else 
cout<<chtooem("слово ")<<s1<<chtooem(" найдено\n");	
return 0;
}

void DigitalTree::add(char *str)
{
char addword[n+1];
strcpy(addword, str);
strcat(addword, " ");
int size=strlen(addword);

elem *t;
if(tr==0){
t=new elem;
t->next=0;
t->down=0;
t->bukva=addword[0];
tr=t;
}
else {
for(t=tr; (t!=0)&&(t->bukva!=addword[0]); t=t->next);
if(t==0){
t=new elem;
t->next=tr;
t->down=0;
t->bukva=addword[0];
tr = t;			 
}
}

elem* temp;

for(int i=1; i<size; i++)
{
if(t->down==0)
{t->down=new elem;
(t->down)->next=0;
(t->down)->down=0;
(t->down)->bukva=addword[i];
}
else{
for(temp=t->down; (temp!=0)&&(temp->bukva!=addword[i]); temp=temp->next);
if(temp==0){
temp=new elem;
temp->next=t->down;
temp->down=0;
temp->bukva=addword[i];
t->down=temp;
}

}
t=t->down;
}

}

int DigitalTree::find(char *str)
{
char searchword[n+1];
strcpy(searchword, str);
strcat(searchword, " ");
int size=strlen(searchword);
elem *t;

for(t=tr; (t!=0) && (t->bukva!=searchword[0]); t=t->next);

for(int i=1; i<size; i++){
if(t==0)
{
return -1;
}
for(t=t->down; (t!=0) && (t->bukva!=searchword[i]); t=t->next);
if(t==NULL){
return -1;
}
}
return 1;

}
void DigitalTree::remove(char *str)
{
if(find(str)==-1)
return;
char delword[n+1];
strcpy(delword, str);
strcat(delword, " ");
int size=strlen(delword);
elem *u = NULL,*t = NULL;
for(int l=strlen(str);l>1;l--){
u = tr;
//поиск удаляемого элемента
for(int i=0;i<l;i++){
for(t = u;t->bukva!=delword[i];t=t->next){}
u=t->down;
}
//удаление символов с последнего по второй
if(u->bukva==delword[i]){
t->down=t->down->next;
delete u;
if(t->down!=NULL)
return;
}
else {
while(u->next->bukva!=delword[i])
u=u->next;
elem *p = u->next;
u->next = u->next->next;
delete p;
return;
}
}

//удаление первого символа 

if(tr->bukva==str[0]){
elem *p = tr;
tr = tr->next;
delete p;
return;
}
for(t = tr;t->next->bukva!=str[0];t=t->next){}
elem *p = t->next;
t->next = t->next->next;
delete p;
}
 
Статус
Закрыто для дальнейших ответов.