Теми рефератів
> Реферати > Курсові роботи > Звіти з практики > Курсові проекти > Питання та відповіді > Ессе > Доклади > Учбові матеріали > Контрольні роботи > Методички > Лекції > Твори > Підручники > Статті Контакти
Реферати, твори, дипломи, практика » Курсовые проекты » Реєстрація постояльців в готелі

Реферат Реєстрація постояльців в готелі





> укладений між 0 і 255.

unsigned char HashIndexType; Hash (char * str) {h=0; (* str) h +=* str ++; h;

}


VI. Виключає АБО для рядків змінної довжини ( розмір таблиці дорівнює 256 ). Цей метод аналогічний аддитивному, але успішно розрізняє схожі слова і анаграми (адитивний метод дасть одне значення для XY і YX).

VII. Метод, як легко здогадатися, полягає в тому, що до елементів рядка послідовно застосовується операція виключає або raquo ;. У наступне алгоритмі додається випадкова компонента, щоб ще поліпшити результат.


typedef unsigned char HashIndexType; char Rand8 [256]; Hash (char * str) {char h=0; (* str) h=Rand8 [h ^ * str ++];

return h;

}


Тут Rand8 - таблиця з 256 восьмибітових випадкових чисел. Їх точний порядок не критичний. Коріння цього методу лежать в криптографії; він виявився цілком ефективним.

VIII. Виключає АБО для рядків змінної довжини ( розмір таблиці lt;=65536 ). Якщо ми хешіруем рядок двічі, ми отримаємо хеш-значення для таблиці будь-якої довжини до 65536. Коли рядок хешіруется вдруге, до першого символу додається 1. Отримувані два 8-бітових числа об'єднуються в одне 16-бітове.


typedef unsigned short int HashIndexType; char Rand8 [256]; Hash (char * str) {h; char h1, h2; (* str == 0) return 0;=* str; h2=* str + 1; ++; (* str) {= Rand8 [h1 ^ * str];=Rand8 [h2 ^ * str]; ++;

}

/* h is in range 0.65535 * /=((HashIndexType) h1 lt; lt; 8) | (HashIndexType) h2;

/* use division method to scale */

return h% HashTableSize

}


Розмір хеш-таблиці повинен бути достатньо великим, щоб у ній залишалося розумно велике число порожніх місць. Чим менше таблиця, тим більше середній час пошуку ключа в ній. Хеш-таблицю можна розглядати як сукупність пов'язаних списків. У міру того, як таблиця росте, збільшується кількість списків і, відповідно, середнє число вузлів в кожному списку зменшується. Нехай кількість елементів дорівнює n . Якщо розмір таблиці дорівнює 1, то таблиця вироджується в один список довжини n . Якщо розмір таблиці дорівнює 2 і хешування ідеально, то нам доведеться мати справу з двома списками по n /100 елементів у кожному. Це сильно зменшує довжину списку, в якому потрібно шукати.


1.2 АВЛ-дерево


АВЛ-дерево - збалансоване по висоті двійкове дерево пошуку: для кожної його вершини висота її двох піддерев розрізняється не більше ніж на 1.

АВЛ-дерева названі за першими літерами прізвищ їх винахідників, Г.М. Адельсона-Бєльського і Е.М. Ландіса, які вперше запропонували використовувати АВЛ-дерева в 1962.

Загальні властивості

У АВЛ-дереві висоти h є не менше F h вузлів, де F h - число Фібоначчі. Оскільки


,


де - золотий перетин,

то маємо оцінку на висоту АВЛ-дерева h = O ( log ( n )), де n - число вузлів. Слід пам'ятати, що O ( log ( n )) - мажоранту, і її можна використовувати тільки для оцінки (Наприклад, якщо в дереві тільки два вузла, значить в дереві два рівні, хоча log (2)=1). Для точної оцінки глибини дерева слід використовувати налаштовувану підпрограму.

TreeDepth (Tree: TAVLTree): byte;

beginTree lt; gt; nil then:=1 + Max (TreeDepth (Tree ^. left), TreeDepth (Tree ^. right))

else:=0 ;;

Тип дерева можна описати так

TKey=LongInt;=LongInt;=- 1.1;=^ TAVLNode;=record, right: TAVLTree;

key: TKey ;: TInfo;

{Поле визначальне сбалансированность вершини}: TBalance ;;


Балансування

Щодо АВЛ-дерева балансуванням вершини називається операція, яка у разі різниці висот лівого і правого піддерев=2, змінює зв'язку предок-нащадок в поддереве даної вершини так, що різниця стає lt;=1, інакше нічого не змінює. Зазначений результат виходить обертаннями поддерева даної вершини.

Використовуються 4 типу обертань:

. Мале ліве обертання



Дане обертання використовуєть...


Назад | сторінка 4 з 19 | Наступна сторінка





Схожі реферати:

  • Реферат на тему: Побудова та аналіз взаємодії дерева цілей і дерева систем організації
  • Реферат на тему: Організація списку за допомогою двійкового дерева
  • Реферат на тему: Пошук вершини в графі між двома заданими вершинами
  • Реферат на тему: Суффіксние дерева пошуку
  • Реферат на тему: Коли працювати можна менше ...