ХЕ(Э)ШИРОВАНИЕ С ПОМОЩЬЮ ЛЕСА. define N 10 //Количество элементов массива.. Инициализация хэш-списка.. cin >> klutch;. если нужно задавать значения ключей с клавиатуры.

ХЕ(Э)ШИРОВАНИЕ С ПОМОЩЬЮ ЛЕСА

В моногpафии [2] есть упражнение, которое звучит так:

"Рассмотрите предложения о решении проблемы скопления с помощью деревьев переполнения вместо списков переполнения, т.е. организации тех ключей, которые вступают в конфликт, в виде дерева. Следовательно, каждый вход в рассеянную таблицу можно рассматривать как корень (возможно, пустого) дерева (древовидная расстановка)".

Вначале схематически изобразим структуру данных:

где Деpево1, Деpево2, ..., ДеpевоN - бинарные деревья поиска, а затем построим программу для разрешения поставленной проблемы.

#define N 10 //Количество элементов массива.

struct node

{

int Key;

int Count;

node *Left;

node *Right;

};

class Spisok {

private:

node *UkStr[N];

void Search (int, node**);

void PrintTree (node *, int);

void U_d (node **,node **);

public:

Spisok ();

void BuildTree();

void Sodergimoe();

node** GetTree (unsigned i) {return &(UkStr[i]);}

void Udaldr (node** d, int k);

};

Spisok::Spisok()

{

//Инициализация хэш-списка.

for (int i=0;i<N;i++) UkStr[i] = NULL;

}

void Spisok::BuildTree()

{

int klutch;

unsigned hash;

cout << "\nВведите значение ключа...";

//cin >> klutch;

//Закомментируйте следующие три строки,

//если нужно задавать значения ключей с клавиатуры.

randomize();

klutch = random(31);

cout << klutch;

while (klutch!=0)

{

hash = klutch % 10; //Вычисление значения хэш-функции.

Search (klutch,&UkStr[hash]);

cout << "\nВведите значение ключа...";

//cin >> klutch;

klutch = random(31);

cout << klutch;

}

void Spisok::Search(int X, node **p)

{

if (*p==NULL)

{ //Узла нет в деpеве; включить его.

*p = new (node);

(**p).Key = X;

(**p).Count = 1;

(**p).Left = (**p).Right = NULL;

}

else

if (X<(**p).Key) Search (X, &((**p).Left));

else if (X > (**p).Key) Search (X, &((**p).Right));

else (**p).Count += 1;

}

void Spisok::Sodergimoe()

{

for(int i=0;i<N;i++)

{

cout << " "<< i <<"... ";

if (UkStr[i]==NULL) cout << "Деpево пусто...\n";

else

{

cout << endl;

PrintTree (UkStr[i],0);

}

cout << "------------------------------------------" << endl;

}

void Spisok::PrintTree (node *w, int l)

{

if (w!=NULL)

{

PrintTree ((*w).Right,l+1);

cout << " ";

for (int i=1;i<=l;i++) cout <<" ";

cout << (*w).Key << endl;

PrintTree ((*w).Left,l+1);

}

void Spisok::Udaldr (node** d, int k)

{ //Удаление узла с ключом k из деpева d.

node** q;

if (*d==NULL) cout << "Узел с заданным ключом в деpеве не найден...\n";

12 Следующая ⇒