cellspacing=0>
ar, h (ar) = 4
Початок
кінець
...
...
В
m
nil
nil
Алгоритми побудови та пошуку хеш таблиці.
Побудова:
В· Знаходимо значення хеш функції і по цьому значенню входимо в таблицю
В· Якщо вона порожня, то записуємо в неї ключ
В· Якщо вона зайнята, то порівнюємо ключ із заданим ключем:
1. якщо ключі збігаються, то обробляємо повторний ключ
2. інакше додаємо новий ключ в кінець списку
Пошук:
В· Знаходимо значення хеш функції для шуканого ключа і цьому значенню входимо в таблицю
В· Якщо осередок порожня, то пошук закінчується невдачею
В· Якщо вона не порожня, те виконуємо порівняння ключів:
1. Якщо ключі збігаються, то пошук закінчується за одне порівняння
2. Інакше організуємо перегляд допоміжного списку з позитивним чи негативним результатом.
Для даного методу велике значення має рівномірність розподілу ключів по хеш-таблиці, що гарантує короткі допоміжні списки і тим самим зменшує число порівнянь при пошуку. Найгіршим є випадок, коли для всіх ключів хеш-функція дає одне і теж значення, та всі елементи шикуються в один довгий лінійний список. p> Іншим фактором, що впливає на ефективність відкритого хешування, є розмір хеш-таблиці по відношенню до числа вхідних даних. Якщо ці величини рівні, то теоретично можна обійтися без лінійних списків, якщо між ключами немає конфліктів. На практиці рекомендують вибирати розмір хеш-таблиці рівним n/2. p align=center> 3. Основні поняття об'єктної технології
В
1. Об'єкти і класи.
Об'єкт - це будь-яка сутність, що має деякі набір властивостей і що має деяким поведінкою.
Властивість об'єкта описується як звичайні поля даних. У цих полях зберігаються значення відповідних властивостей.
Типи полів:
1. Найпростіші примітивні типи. p> 2. Структуровані типи.
3. Об'єктні властивості представляють із себе об'єкти тієї самої або іншої природи. (Наявність об'єктних властивостей є проявом одного з способів взаємодії об'єктів, а саме композицією об'єктів, яка використовується в курсової програмі)
Набір властивостей об'єкта створюється при описі об'єкта й надалі змінюється. Поведінка об'єкта описується набором методів. Кожен метод представляє з себе програмний код.
Об'єднання разом оброблюваних даних і програмного коду їх обробки називається ознакою інкапсуляції.
Можна виділити наступні типові методи об'єктів:
1. Конструктори, деструктори
Конструктор відповідає за створення нового об'єкту т. е за виділення йому пам'яті і практично завжди за початкову ініціалізацію цієї пам'яті. Конструктор викликається раніше всіх інших методів. Для створення одного і того ж об'єкта можна передбачити декілька різних конструкторів, які по-різному инициализируют характеристики створюваного об'єкта.
Деструкція відповідає за руйнування об'єкта т.е звільнення виділеної об'єкту пам'яті.
2. Методи, за допомогою яких можна дізнатися поточне значення тих чи інших властивостей. Зазвичай для кожної властивості створюється свій такий метод. Такі методи прийнято називати з префікса Get. (Приклад: GetFIO)
3. Методи, які змінюють значення одного або декількох властивостей. Такі методи прийнято називати з префікса Set. (Приклад: SetFIO). p> Використання Set і Get методів пояснюється наступним:
За принципами об'єктного підходу властивості об'єкта повинні бути закриті для стороннього прямого доступу. Доступ до властивостей дозволяється тільки через виклики Get і Set методів. Це є ще одним проявом принципу інкапсуляції: приховування інформації про об'єкт. У цьому випадки внутрішньо сховище даних об'єкта повністю закрите від посторенная впливу. Набір методів доступу утворюють відкритий інтерфейс об'єкта.
Крім перерахованих методів об'єкт може мати унікальні методи, що визначають його функціональність.
Клас представляє з себе шаблон опису однотипних об'єктів.
На основі одного класу можна створити будь-яке число об'єктів, званих екземплярами класів. Саме при описі класу перераховуються властивості та методи відповідних об'єктів. З опису класу починається написання будь об'єктної програми. br/>
2. Опис класів
Опис класів включає в себе:
1. Тема класу з ім'ям класу
Приклад: type MyMasClass = Class. p...
