рефераты конспекты курсовые дипломные лекции шпоры

Раздел Образование
/
Таблиці прямого доступу

Реферат Курсовая Конспект

Выберите учебное заведение

Таблиці прямого доступу

Таблиці прямого доступу - раздел Образование, ОПЕРАЦІЇ ЛОГІЧНОГО РІВНЯ Найпростішою Організацією Таблиці, Що Забезпечує Ідеально Шви...

Найпростішою організацією таблиці, що забезпечує ідеально швидкий пошук, є таблиця прямого доступу. У такій таблиці ключ є адресою запису в таблиці або може бути перетворений на адресу, причому таким чином, що ніякі два різних ключі не перетворяться в ту саму адресу. При створенні таблиці виділяється пам'ять для збереження всієї таблиці та заповнюється порожніми записами. Потім записи вносяться в таблицю – кожна на своє місце, що визначається ключем даного запису. При пошуку ключ використовується як адреса і за цією адресою вибирається запис. Якщо обраний запис порожній, то запису з таким ключем взагалі немає в таблиці. Таблиці прямого доступу дуже ефективні у використанні, але, на жаль, область їхнього застосування дуже обмежена.

Назвемо простором ключів множину усіх теоретично можливих значень ключів запису. Назвемо простором записів безліч тих слотів у пам'яті, що виділяються для збереження таблиці. Таблиці прямого доступу можуть бути застосовані тільки для таких задач, у яких розмір простору записів може дорівнювати розміру простору ключів. У більшості реальних задач, однак, розмір простору записів набагато менше, ніж простір ключів. Наприклад, якщо ключ використовується як прізвище, то, навіть обмеживши довжину ключа 10-ма символами, виходить 3310 можливих значень ключів. В обчислювальній системі не може бути виділений простір записів такого розміру. Навіть якщо ресурси обчислювальної системи і дозволять це, то значна частина цього простору буде заповнена порожніми записами, тому що в кожному конкретному заповненні таблиці фактична множина ключів не буде цілком покривати простір ключів.

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

ОПЕРАЦІЇ ЛОГІЧНОГО РІВНЯ

ОПЕРАЦІЇ ЛОГІЧНОГО РІВНЯ... НАД СТАТИЧНИМИ І СТРУКТУРАМИ R...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Таблиці прямого доступу

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Послідовний або лінійний пошук
Найпростішим методом пошуку елемента, що знаходиться в неупорядкованому наборі даних, за значенням його ключа є послідовний перегляд кожного елемента набору, що продовжується доти,

Пошук у таблиці
Пошук у масиві іноді називають пошуком у таблиці, якщо ключ сам є інтегрованим об'єктом, таким як масив чисел чи символів. Часто зустрічається саме останній випадок, коли масиви сим

Прямий пошук рядка в тексті
Часто доводиться зіштовхуватися зі специфічним пошуком, так названим пошуком рядка в тексті. Його можна визначити таким способом. Нехай заданий масив s з

КМП-алгоритм пошуку рядка в тексті
У 1970 р. Д. Кнут, Дж. Морріс і В. Пратт запропонували алгоритм пошуку рядка в тексті, так званий КМП-алгоритм або КМП-пошук, фактично потребуючий тільки N порівнян

БМ-алгоритм пошуку рядка в тексті
Схема КМП-пошуку дає справжній виграш тільки тоді, коли при порівнянні символів до розбіжності було деяке число збігів (>1). Лише в цьому випадку образ зміщується більш ніж на одиницю. На жаль,

Таблиці з довідниками
Одним із способів усунення недоліку, властивого таблицям прямого доступу, який полягає в тому, що вони вимагають пам'ять значних розмірів, є метод довідників. Основна табли

Хешовані таблиці та функції хешування
Як відзначалося вище, у кожній реальній таблиці фактична множина ключів є лише невеликою підмножиною множини всіх теоретично можливих ключів. З міркувань економії пам'яті доцільно призначати роз

Проблема колізій у хешованих таблицях
Колізії (друга назва - конфлікт) – основна проблема для хешованих таблиць. Вдало підібрана функція хешування може мінімізувати число колізій, але не може гарантувати їхньої повної в

Сортування
Для самого загального випадку задача сортування може формулюватися так: мається деяка неупорядкована вхідна множина ключів, необхідно одержати вихідну множину тих же ключів, упорядк

Сортування вибіркою
Сортування простою вибіркою. Даний метод реалізує практично "дослівно" сформульовану вище стратегію вибірки. Порядок алгоритму простої вибірки – O(N2

Сортування включенням
Сортування простими вставками. Цей метод – "дослівна" реалізація стратегії включення. У програмному прикладі 5.19 наведена підпрограма сортування простими вставками.

Сортування розподілом
Порозрядне цифрове сортування. Алгоритм вимагає представлення ключів сортованої послідовності у вигляді чисел у деякій системі обчислення P. Число

Сортування злиттям
Алгоритми сортувань злиттям, як правило, мають порядок O(N*log(N)), але відрізняються від інших алгоритмів більшою складністю і вимагають великого числа пересилань. Алгоритми злиття

Порівняння алгоритмів сортування масивів
Закінчуючи огляд методів сортування, порівняємо їх ефективність. В таблиці 5.3 подано дані (у секундах) для упорядкування довільного, упорядкованого й упорядкованого в зворотному порядку масивів з