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

Тема в разделе "MS Visual C++", создана пользователем -, 13 дек 2006.

Статус темы:
Закрыта.
  1. Гость

    Если я буду добавлять слова в таком порядке: dog, do, doggy, caty, то слово doggy не будет найдено. Если сначала do, то все нормально. Много раз переделывала, но что-то не получается. В коде признаком завершения слова является пробел. Посмотрите, может кто-то что-то подскажет как исправить мою ошибку и вообще можно ли как-нибудь переделать/улучшить весь код.
    Код (Text):
    #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;
    }
     
Загрузка...
Похожие Темы - дерево цифрового поиска
  1. Hanja
    Ответов:
    0
    Просмотров:
    1.034
  2. MrSpoon
    Ответов:
    0
    Просмотров:
    1.054
  3. Maestresa
    Ответов:
    2
    Просмотров:
    1.666
  4. KalinaK
    Ответов:
    1
    Просмотров:
    1.689
  5. jaGGa
    Ответов:
    1
    Просмотров:
    1.420
Статус темы:
Закрыта.

Поделиться этой страницей