На головну

інвертовані списки

  1. Багаторівневі списки
  2. Завдання 2. Редагування. Форматування. Абзаци. Списки. Додавання візуального ефекту.
  3. лінійні списки
  4. лінійні списки
  5. Маркери.
  6. марковані списки

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

Наприклад, нехай основний список показаний в таблиці 23. Відповідні індекси показані в таблицях 38 - 40:

Таблиця 38 Таблиця 39 Таблиця 40

 № п / п  Шифр навчальної групи  посилання    № п / п  дисципліна  посилання    № п / п  оцінка  посилання
 01-АС    Інформатика  1,3  
 01-ІЕ  1,3,5    програмування  2,4    2,5
 02-ВТ    фізика    1,4

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

Розглянемо, як виконується завдання перегляду.

Приклад 16. Нехай треба переглянути список всіх студентів, які здавали інформатику, т. Е qперегляд = (дисципліна = Інформатика, ПІБ студента), Де Кдоступ = Інформатика. Пошук здійснюється послідовним виконанням кроків:

1. за індексом для ключа дисципліна(Таблиця 39) знаходиться відповідний елемент: це перший елемент у списку;

2. вибираються посилання для цього елемента: це безліч {1, 3};

3. по основного списку(Таблиця 23) вибираються послідовно елементи з номерами 1 і 3 і виводиться вміст поля ПІБ студента для цих елементів; отримуємо список - Іванов І.І. і Сидоров С. С. Робота алгоритму закінчена.

Розглянемо, як вирішується завдання додавання.

Приклад 17. Нехай до основного списку треба додати елемент зі структурою:

 ПІБ студента  Шифр навчальної групи  дисципліна  оцінка
 Ковальов К. К.  02-ВТ  програмування

т. е qдодавання = (ПІБ студента= Ковальов К. К., Шифр навчальної групи = 02-ВТ, дисципліна = Програмування, оцінка = 2), де Кдоступ = Ковальов К. До.

Модифікований основний список показаний в таблиці 41, а три індексу - в таблицях 42 - 44. Змінені значення посилань, а також новий елемент в одному з індексів виділені заливкою; новий елемент в основному списку виділений напівжирним шрифтом:

Таблиця 41

 № п / п  ПІБ студента  Шифр навчальної групи  дисципліна  оцінка
 Іванов І. І.  01-ІЕ  Інформатика
 Ковальов К. К.  02-ВТ  програмування
 Петров П. П.  02-ВТ  програмування
 Сидоров С. С.  01-ІЕ  Інформатика
 Федоров Ф. Ф.  01-АС  програмування
 Яковлєв Я. Я.  01-ІЕ  фізика

Таблиця 42 Таблиця 43 Таблиця 44

 № п / п  Шифр навчальної групи  посилання    № п / п  дисципліна  посилання    № п / п  оцінка  посилання
 01-АС    Інформатика  1,4  
 01-ІЕ  1,4,5    програмування  2,3,5  
 02-ВТ  2,3    фізика    3,6
                 1,5


Оптимізовані ланцюжка елементів | ієрархічні структури

Способи доступу по первинному ключу | блоковий спосіб | двійковий спосіб | Індексного-послідовний спосіб | Індексного-довільний спосіб | Розміщення елементів в упорядкованому списку | рандомизация | А б в г д е є ж з и й к л м н о п р с т у ф х ц ч ш щ ь ь и е ю я | Прізвище (ключ) Числове значення ключа | Елементи, пов'язані в ланцюг |

© um.co.ua - учбові матеріали та реферати