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

загрузка...
загрузка...
На головну

Множинні посилання на породжені елементи

  1. I. Елементи лінійної алгебри та аналітичної геометрії.
  2. Б. Елементи теорії множин, операції над множинами, квантори
  3. НАЙВАЖЛИВІШІ ЕЛЕМЕНТИ УПРАВЛІНСЬКОГО ПРОЦЕСУ. Об'єкт І СУБ'ЄКТ УПРАВЛІННЯ

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

Обговоримо організацію зберігання елементів для дерева малюнка 7. Оскільки в цьому дереві є тільки два безлічі подібних елементів (навчальні групи і прізвища з ініціалами студентів), сформуємо для них два лінійних списку (таблиці 45, 46):

Таблиця 45 Таблиця 46

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

Тепер треба показати зв'язок між елементами, зазначені в дереві. Для цього, відповідно до розглянутого способом, сформуємо у списку з таблиці 45 додаткове поле посилання, В якому і зафіксуємо необхідні зв'язку. Отримаємо таблицю 47:

Таблиця 47

 № п / п  Шифр навчальної групи  посилання
 01-АС
 01-ІЕ  1,2,4

Як видно з таблиці 47, посилання для групи 01-АС відносяться до елементу з номером 3 з таблиці 46, в якому зберігається інформація про студента Федорова Ф. Ф., а посилання для групи 01-ІЕ відносяться до елементів з номерами 1, 2, 4 з тієї ж таблиці, де зберігається інформація про студентів, які навчаються в даній групі. Таким чином, сукупність таблиць 47 і 46 моделює дерево малюнка 7.

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

Таблиця 48 Таблиця 49

 № п / п  Шифр навчальної групи  ПІБ старости групи  посилання    № п / п  ПІБ студента  Домашня адреса
 01-АС  Федоров Ф. Ф.    Іванов І. І.  вул. Кірова, 3 - 4
 01-ІЕ  Яковлєв Я. Я.  1,2,4    Сидоров С. С.  пр. Миру, 5 - 4
           Федоров Ф. Ф.  вул. Рєпіна, 1 - 2
           Яковлєв Я. Я.  вул. Маркса, 2 - 2

Проте, в графічному зображенні дерева (див. Малюнок 7), як правило, елементи вказуються своїми ключовими полями.

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

Приклад 18. Нехай треба сформувати список студентів, які навчаються в групі 01-ІЕ (Це завдання подібна завданню пошуку по вторинному ключу для лінійних списків), т. Е qперегляд = (Шифр навчальної групи = 01-ІЕ, ПІБ студента), Де Кдоступ = 01-ІЕ. Елементи дерева мають структуру, показану в таблицях 48 і 49, а саме дерево має вид малюнка 7.

Завдання виконується в такий спосіб:

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

2. вибирають посилання - це безліч {1, 2, 4};

3. за лінійним списком з прізвищами студентів (таблиця 49) звертаються до елементів з номерами 1, 2 і 4. Отримують список студентів: Іванов І.І., Федоров Ф. Ф., Яковлєв Я. Я. Алгоритм закінчує роботу.

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

1. вибирається перший елемент у списку навчальних груп (таблиця 48). Це група з шифром 01-АС;

2. за значенням посилання звертаються до відповідного елементу (він має номер 3) списку студентів (таблиця 49);

3. порівнюють прізвище та ініціали студента з шуканої прізвища та ініціалів. Оскільки Федоров Ф. Ф. ? Іванов І. І., Управління повертається до перегляду таблиці 48;

4. в списку навчальних груп вибирають наступний (другий) елемент. Це група з шифром 01-ІЕ;

5. в списку посилань цієї групи вибирають перше посилання (це 1) і в списку студентів знаходять перший елемент;

6. прізвище та ініціали студента порівнюють з шуканої прізвища та ініціалів. Оскільки прізвища та ініціали збігаються, робиться висновок, що студент навчається в тій групі, для якої був обраний останній покажчик, т. Е в групі 01-ІЕ. Алгоритм закінчує роботу.

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

Приклад 20. Нехай в дерево малюнка 7 (воно описано в таблицях 46, 47) треба включити елемент зі структурою:

 ПІБ студента  Шифр навчальної групи
 Комаров К. К.  01-АС

т. е qдодавання = (ПІБ студента= Комаров К. К., Шифр навчальної групи = 01-АС), Де Кдоступ = Комаров К. К., 01-АС.

Очевидно, після включення цього елемента дерево малюнка 7 придбає інший вид (новий елемент виділений напівжирним шрифтом):

малюнок 8

Відповідні зміни виконані в таблицях 46 і 47, які набудуть вигляд таблиць 51 і 50, відповідно (нові та змінені дані виділені заливкою):

Таблиця 50 Таблиця 51

 № п / п  Шифр навчальної групи  посилання    № п / п  ПІБ студента
 01-АС  2,4    Іванов І. І.
 01-ІЕ  1,3,5    Комаров К. К.
         Сидоров С. С.
         Федоров Ф. Ф.
         Яковлєв Я. Я.


ієрархічні структури | Посилання на подібні і породжені елементи
загрузка...
© um.co.ua - учбові матеріали та реферати