На головну

Елементи, пов'язані в ланцюг

  1. II. Правила орфографії, пов'язані з фонемно-графемно
  2. Аудиторські ризики, пов'язані з кваліфікацією облікового персоналу
  3. взаємопов'язані документи
  4. Види деформацій стержня і пов'язані з ними геометричні характеристики поперечних перерізів
  5. Вихідна допомога та інші компенсації, пов'язані зі звільненням
  6. Для визначення собівартості окремих видів продукції витрати, пов'язані з їх виробництвом і реалізацією, групуються за статтями витрат.

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

Приклад 11. Нехай основний лінійний список має вигляд таблиці 23:

Таблиця 23

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

Вторинними ключами є Шифр навчальної групи, дисципліна, оцінка. Побудуємо індекси для цих ключів (таблиці 24 - 26):

Таблиця 24 Таблиця 25 Таблиця 26

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

Як видно з таблиць 24 - 26, кожен індекс містить поле з усіма значеннями відповідного вторинного ключа з основного списку і поле (зветься Посилання), В якому вказується номер елемента основного списку, де вперше зустрічається відповідне значення вторинного ключа. Значення вторинних ключів в індексах впорядковані за зростанням, так що з індексами можна працювати як з впорядкованими лінійними списками (в ролі первинних ключів таких списків виступають вторинні ключі основних списків).

Модифікуємо також і основний список. Для зручності помістимо додаткові поля (вони виділені заливкою) праворуч від відповідного вторинного ключа. Отримаємо таблицю 27:

Таблиця 27

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

Розглянемо, наприклад, як сформовано поле Посиланнядля вторинного ключа Шифр навчальної групи:

1. елемент з номером 1 має посилання на елемент з номером 3: це наступний елемент основного списку зі значенням шифру групи 01-ІЕ;

2. елемент з номером 3 має посилання на елемент з номером 5: це наступний елемент основного списку зі значенням шифру групи 01-ІЕ;

3. елемент з номером 5 - останній в основному списку зі значенням вторинного ключа Шифр навчальної групи, Рівним 01-ІЕ. Тому він має порожню посилання «-»;

4. елемент з номером 2 - єдиний в основному списку зі значенням вторинного ключа 02-ВТ, тому він має порожню посилання «-»;

5. елемент з номером 4 - єдиний в основному списку зі значенням вторинного ключа 01-АС, тому він має порожню посилання «-».

Аналогічно можна простежити утворення посилань у інших вторинних ключів.

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

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

1. по індексомдля ключадисципліна визначається елемент зі значенням поля дисципліна, рівним Інформатика (Оскільки індекс - це упорядкований лінійний список, до нього застосовуються розглянуті раніше методи, наприклад, метод послідовного сканування, аналіз роботи яких в даному випадку не наводиться). Це перший елемент індексу;

2. по полю Посилання з'ясовується номер елемента основного списку з шуканим ключем доступу - це перший елемент;

3. в основному списку вибирається перший елемент. Виводиться прізвище та ініціали студента - це Іванов І. І .;

4. відповідно до значення поля Посиланнядля поля дисципліна визначається номер наступного елемента основного спискуз аналогічним значенням вторинного ключа - це елемент № 3;

5. вибирається третій елемент. Виводиться прізвище та ініціали студента - це Сидоров С. С .;

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

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

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

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

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

Оскільки процедури додавання докладно розглядалися раніше, простежимо, як в результаті модифікувалися основний список і три індексу (таблиці 28 - 31). Змінені значення посилань виділені заливкою; нові елементи в основному списку і в таблиці 31 виділені напівжирним шрифтом:

Таблиця 28

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

Таблиця 29 Таблиця 30 Таблиця 31

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


Прізвище (ключ) Числове значення ключа | Оптимізовані ланцюжка елементів

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

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