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

Раздел Образование
/
Таблиці з довідниками

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

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

Таблиці з довідниками

Таблиці з довідниками - раздел Образование, ОПЕРАЦІЇ ЛОГІЧНОГО РІВНЯ Одним Із Способів Усунення Недоліку, Властивого Таблицям Прям...

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

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

– по-перше, якщо основна таблиця розташована на зовнішній пам'яті, то довідкова таблиця (чи значна її частина) може бути розміщена в оперативній пам'яті і пошук ключа, таким чином, буде виконуватися в оперативній пам'яті, що набагато швидше;

– по-друге, для однієї основної таблиці можуть бути побудовані декілька довідників, що забезпечують використання в якості ключа різні поля записів основної таблиці.

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

Развернуть

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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