Вот класс, реализуеший алгоритм дерева поиска
| Код |
// ------------------------------------------------------------------
// Author: Fin
// Subject: Tample Trees of Find (FindTree)
// Version 1.0
// Date Begin 30/07/2005 End 02/08/2005
// ------------------------------------------------------------------
// int SetWord(char *ch, T *Date)
// Function Set word into Tree
// return value 0 - error, 1 - all OK
// ------------------------------------------------------------------
// int FindChar(char ch, T *Date)
// Function look for char in the tree and memory current point
// return value 0 - error, 1 - all OK
// ------------------------------------------------------------------
// int FindWord(char *ch, T *Date)
// Function look for word in the tree
// return value 0 - error, 1 - there is level on the tree
// 2 - there is word on the tree
// ------------------------------------------------------------------
// void SetNullPos(void)
// Erase current positon
// ------------------------------------------------------------------
// int DeleteWord(char *ch)
// Erase Date of word on the tree
// return value 0 - Date don't erase, 1 - all OK
// ------------------------------------------------------------------
#ifndef FINDTREES_H
#define FINDTREES_H
#include <windows.h>
// ------ FindTree --------------------------------------------------
template < class T >
class FindTree
{
private:
typedef struct List
{
List *Next;
List *Prev;
List *Level;
char ch;
T *Date;
};
List *Tree;
List *Current;
List *NewList(List *Dat)
{
List *temp = new List;
if (temp == NULL) return temp;
ZeroMemory(temp, sizeof(List));
if (Dat != NULL)
{
temp->Prev=Dat;
temp->Next=Dat->Next;
Dat->Next=temp;
if (temp->Next !=NULL) temp->Next->Prev=temp;
}
return temp;
}
void DeleteTree(List *Date)
{
List *temp=Date;
List *old;
while (temp != NULL)
{
if (temp->Date != NULL) delete temp->Date;
if (temp->Level != NULL) DeleteTree(temp->Level);
old=temp;
temp=temp->Next;
delete old;
}
}
public:
FindTree(void)
{
Tree=NULL;
Current=NULL;
}
~FindTree()
{
DeleteTree(Tree);
}
int SetWord(char *ch, T *Date)
{
int res=0;
if ((Date !=NULL) && (ch !=NULL) && (ch[0] != 0))
{
int i=0;
if (Tree == NULL)
{
Tree=NewList(NULL);
if (Tree==NULL) return res;
Tree->ch=ch[i];
}
List *temp=Tree;
while (ch[i] !=0)
{
while ((temp->ch != ch[i]) && (temp->Next != NULL)) temp=temp->Next;
if (temp->ch != ch[i])
{
temp=NewList(temp);
if (temp == NULL) return res;
temp->ch=ch[i];
}
i++;
if (ch[i] !=0)
{
if (temp->Level==NULL)
{
temp->Level=NewList(NULL);
if (temp->Level==NULL) return res;
temp->Level->ch=ch[i];
}
temp=temp->Level;
}
}
temp->Date=new T;
if (temp->Date == NULL) return res;
CopyMemory(temp->Date,Date, sizeof(T));
res=1;
}
return res;
}
int FindChar(char ch, T *Date)
{
int res=0;
if (Current == NULL) Current=Tree;
else Current=Current->Level;
if (Date == NULL) Current = NULL;
while ((Current != NULL) && (Current->ch != ch)) Current=Current->Next;
if (Current != NULL)
{
res=1;
if (Current->Date != NULL)
{
CopyMemory(Date, Current->Date, sizeof(T));
res=2;
}
}
return res;
}
int FindWord(char *ch, T *Date)
{
int res =-1;
Current=NULL;
int i=0;
if (ch != NULL)
{
while ((ch[i] !=0) && (res !=0))
{
res=FindChar(ch[i], Date);
i++;
}
}
if (res==-1) res=0;
return res;
}
void SetNullPos(void)
{
Current=NULL;
}
int DeleteWord(char *ch)
{
int res=0;
T *temp;
if (FindWord(ch, temp) == 2)
{
delete Current->Date;
Current->Date=NULL;
res=1;
}
return res;
}
};
// ------------------------------------------------------------------
#endif //FINDTREES_H
|
Определяеш структуру, в которой будеш хранить информацию по каждому ключу.
| Код |
struct IDENT
{
int id;
int TypeKey;
} ;
|
Предупреждение: не рекомендуется использовать динамические переменные.
Затем определяеш экземпляр дерева.
| Код |
FindTree<IDENT> Trees;
|
Заводиш все свои ключи.
| Код |
IDENT iden;
iden.id=1;
iden.TypeKey=2;
Trees.SetWord("Integer", &iden);
|
Ну и сам поиск
Можно искать сразу все слово
| Код |
Trees.FindWord("Integer", &iden);
|
При этом: Функция возвратит
0 - если слово не найдено.
1 - если сушествует ветка, но не сушествует данного индефикатора
2 - Если слово найдено.
Можно искать и по буквенно.
Вначале поиска нужно сбросить дерево в начальное положение поиска.
Затем уже вводить посимвольно каждую букву
| Код |
Trees.FindChar('I', &iden);
|
Возврат функции такой же, как и для всего слова. |
