Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Ідентифікатор мови: цифри та символи, довжиною не більше 32 символами.
Бінарне дерево. Існує метод побудови таблиць, при якому таблиця має форму бінарного дерева. Кожен вузол дерева являє собою елемент таблиці, причому кореневий вузол є першим елементом, зустрінутим при заповненні таблиці. Дерево називається бінарним, тому що кожна вершина в ньому може мати не більше двох віток. Для визначеності будемо називати дві вітки «права» і «ліва».
Перший ідентифікатор, як уже було сказано, міститься у вершині дерева. Усі подальші ідентифікатори попадають у дерево по алгоритму, наприклад: l, c, d, a, x.
|
l |
||
|
c |
x |
|
|
d |
||
|
a |
Середній час на елементи в дереві можна оцінити в такій спосіб: .
Для даного методу число необхідних порівнянь і форма дерева, що вийшла, багато в чому залежать від того порядку, у якому надходять ідентифікатори.
При роботі з таблицею ідентифікаторів хеш-функція повинна виконувати відображення імен ідентифікаторів на множину цілих додатніх чисел. Областю визначення хеш-функції буде множина усіх можливих імен
Процес відображення області визначення хеш-функції на безліч значень називається «хешуванням». При роботі з таблицею ідентифікаторів хеш-функція повинна виконувати відображення імен ідентифікаторів на множину цілих невід’ємних чисел. Областю визначення хеш-функції буде множина усіх можливих імен ідентифікаторів.
Хеш-адресація полягає у використанні значення, що повертається хеш-функцією, як адресу комірки з деякого масиву даних. Тоді розмір масиву даних повинний відповідати області значень використовуваної хеш-функції. Отже, у реальному компіляторі область значень хеш-функції ніяк не повинна перевищувати розмір доступного адресного простору комп'ютера.
Метод організації таблиць ідентифікаторів, заснований на використанні хеш-адресації, полягає в розміщенні кожного елемента таблиці в комірку, адресу якого повертає хеш-функція, обчислена для цього елемента. Тоді в ідеальному випадку для розміщення будь-якого елемента в таблиці ідентифікаторів досить тільки обчислити його хеш-функцію і звернутися до потрібної комірки масиву даних. Для пошуку елемента в таблиці необхідно обчислити хеш-функцію для шуканого елемента і перевірити, чи не є задана нею комірка масиву порожньою (якщо вона не порожня — елемент знайдений, якщо порожня — не знайдений).
Цей метод дуже ефективний — оскільки час розміщення елемента в таблиці і час його пошуку визначаються тільки часом, затрачуваним на обчислення хеш-функції, що у загальному випадку незрівнянно менше часу, необхідного на багаторазові порівняння елементів таблиці.
Метод має два очевидних недоліки. Перший з них – неефективне використання обсягу пам'яті під таблицю ідентифікаторів: розмір масиву для її збереження повинний відповідати області значень хеш-функції, у той час як реально збережених у таблиці ідентифікаторів може бути істотно менше. Другий недолік – необхідність відповідного розумного вибору хеш-функції.
Існують різні варіанти хеш-функцій. Одержання результату хеш-функції – «хешування» – звичайно досягається за рахунок виконання над ланцюжком символів деяких простих арифметичних і логічних операцій. Найпростішою хеш-функцією для символу є код внутрішнього представлення в комп’ютері літери символу. Цю хеш-функцію можна використовувати і для ланцюжка символів, вибираючи перший символ у ланцюжку. Так, якщо двійковим ASCII представленням символу А є двійковий код 001000012, то результатом хеджування ідентифікатора ATable буде код 001000012.
Хеш-функція, запропонована вище, очевидно незадовільна: при використанні такої хеш-функції виникне проблема – двом різним ідентифікаторам, що починаються з однієї і тієї ж букви, буде відповідати те саме значення хеш-функції. Тоді при хеш-адресації в одну комірку таблиці ідентифікаторів по тій самій адресі повинні бути поміщені два різних ідентифікатори, що явно неможливо. Така ситуація, коли двом чи більше ідентифікаторам відповідає те саме значення функції, називається колізією. Очевидно, що хеш-функція, яка допускає колізії, не може бути прямо використана для хеш-функції в таблиці ідентифікаторів.
Будь-яка таблиця символів складається з набору полів, кількість яких дорівнює числу ідентифікаторів програми. Кожне поле містить у собі повну інформацію про даний елемент таблиці. Під ідентифікаторами маються на увазі константи, змінні, імена процедур і функцій, формальні і фактичні параметри.
Найпростіший спосіб організації таблиці полягає в тому, щоб додавати елементи в порядку їхнього надходження. Пошук у цьому випадку вимагає порівняння з кожним елементом таблиці, поки не буде знайдений придатний. Для таблиці, що містить n елементів, у середньому буде виконане n2 порівнянь. Якщо n велике, то спосіб не є ефективним.
Пошук може бути виконаний більш ефективно, якщо елементи таблиці упорядковані (відсортовані) відповідно до деякого природного порядку. У нашому випадку, де пошук буде здійснюватися по імені ідентифікатора, найбільш природним буде розташувати елементи таблиці за абеткою. Ефективним методом пошуку в упорядкованому списку з n елементів є бінарний або логарифмічний пошук. Символ S, який потрібно знайти, порівнюється з елементом (n+1)/2 у середині таблиці. Якщо цей елемент не є необхідним, потрібно переглянути тільки блок елементів, пронумерованих від 1 до (n+1)2-1, або блок елементів від (n+1)/2+1 до n в залежності від того, менше шуканий елемент S чи більше того, з яким його порівняли. Потім дана процедура повторюється над блоком меншого розміру.
Маx значення хеш-функції = 121.
Мін значення хеш-функції = 49.
Перелік ідентифікаторів:
bf, cd, 01, fx, ab, hg, xy, bb, cc, km, od, 77, wd, sb, xx, ss, jd, ka, ee, qt.
Покрокове заповнення таблиці ідентифікаторів:
|
cd100 |
|
cd100 |
||
|
0149 |
|
cd100 |
fx120 |
||
|
0149 |
|
cd100 |
fx120 |
||
|
0149 |
|||
|
ab98 |
|
cd100 |
fx120 |
|||
|
0149 |
hg103 |
|||
|
ab98 |
|
cd100 |
fx120 |
||||
|
0149 |
hg103 |
xy121 |
|||
|
ab98 |
*p {bb}
|
cd100 |
fx120 |
||||
|
0149 |
hg103 |
xy121 |
|||
|
ab98 *p |
*p {bb}
|
cd100 |
fx120 |
||||
|
0149 |
hg103 |
xy121 |
|||
|
ab98 *p |
|||||
|
cc99 |
*p {bb}
|
cd100 |
fx120 |
|||||
|
0149 |
hg103 |
xy121 |
||||
|
ab98 *p |
km109 |
|||||
|
cc99 |
*p {bb, od}
|
cd100 *p |
fx120 |
|||||
|
0149 |
hg103 |
xy121 |
||||
|
ab98 *p |
km109 |
|||||
|
cc99 |
*p {bb, od}
|
cd100 *p |
fx120 |
|||||
|
0149 |
hg103 |
xy121 |
||||
|
ab98 *p |
km109 |
|||||
|
7755 |
cc99 |
*p {bb, od, wd}
|
cd100 *p |
fx120 |
|||||
|
0149 |
hg103 |
xy121 |
||||
|
ab98 *p |
km109 |
|||||
|
7755 |
cc99 |
*p {bb, sb, od, wd}
|
cd100 *p |
fx120 |
|||||
|
0149 |
hg103 |
xy121 |
||||
|
ab98 *p |
km109 |
|||||
|
7755 |
cc99 |
*p {bb, sb, od, wd}
|
cd100 *p |
fx120 |
||||||
|
0149 |
hg103 |
xy121 |
|||||
|
ab98 *p |
km109 |
xx120 |
|||||
|
7755 |
cc99 |
*p {bb, sb, od, wd}
|
cd100 *p |
fx120 |
|||||||
|
0149 |
hg103 |
xy121 |
||||||
|
ab98 *p |
km109 |
xx120 |
||||||
|
7755 |
cc99 |
ss115 |
*p {bb, sb, od, wd}
|
cd100 *p |
fx120 |
||||||||
|
0149 |
hg103 |
xy121 |
|||||||
|
ab98 *p |
km109 |
xx120 |
|||||||
|
7755 |
cc99 |
jk107 |
ss115 |
*p {bb, sb, od, wd}
|
cd100 *p |
fx120 |
||||||||||
|
0149 |
hg103 |
xy121 |
|||||||||
|
ab98 *p |
km109 |
xx120 |
|||||||||
|
7755 |
cc99 |
jk107 |
ss115 |
||||||||
|
ka97 |
*p {bb, sb, od, wd}
|
cd100 *p |
fx120 |
|||||||||||
|
0149 |
hg103 |
xy121 |
||||||||||
|
ab98 *p |
km109 |
xx120 |
||||||||||
|
7755 |
cc99 |
jk107 |
ss115 |
|||||||||
|
ka97 |
ee101 |
*p {bb, sb, od, wd}
|
cd100 *p |
fx120 |
|||||||||||
|
0149 |
hg103 |
xy121 |
||||||||||
|
ab98 *p |
km109 |
xx120 |
||||||||||
|
7755 |
cc99 |
jk107 |
ss115 |
|||||||||
|
ka97 |
ee101 |
qt116 |