Реалізація пов’язаних списків на базі масивів
Реалізація пов'язаних списків на базі масивів
Чуриков Костянтин, Донбаський державний технічний університет
Визначення лінійних списків
Списком називається впорядкована множина, що складається з змінного числа елементів, до яких застосовні операції включення, виключення. Список, що відображає відносини сусідства між елементами, називається лінійним.
З реалізаціями лінійних списків в імперативних мовах програмування можуть виконуватися такі операції:
отримання доступу до деякого елементу списку для перевірки та / або зміни вмісту його полів;
вставка нового елемента відразу перед або після довільного елемента;
видалення довільного елемента;
об'єднання в одному списку двох (або більше) лінійних списків;
розбиття лінійного списку на два (або більше) списку;
створення копії лінійного списку;
визначення кількості елементів в списку;
сортування елементів списку;
пошук елементів із заданим значенням.
В одній програмі вкрай рідко виникає необхідність використовувати всі дев'ять типів операцій. При цьому досить важко створити єдину реалізацію лінійних списків, при якій ефективно виконувалися б усі ці операції. Тому лінійні списки можуть бути реалізовані по-різному в залежності від класу операцій, які найбільш часто повинні з ними виконуватися в даній програмі, або найбільш критичних до часу виконання.
Внутрішнє представлення лінійних списків
Основні способи зберігання лінійних списків в пам'яті комп'ютера можна розділити на способи послідовного і пов'язаного зберігання. При послідовному зберіганні елементи списку розташовуються в пам'яті в послідовних комірках, при цьому один елемент слід відразу ж за іншим. Пов'язане зберігання являє собою більш гнучку схему, при якій кожен елемент списку містить зв'язок з наступним елементом, а їх взаємне розташування в пам'яті може бути довільним. Кожен спосіб має свої переваги і недоліки. При виборі способу зберігання в конкретній програмі слід враховувати, які операції і з якою інтенсивністю будуть виконуватися над лінійними списками, вартість їх виконання і обсяг необхідної пам'яті для зберігання списку.
Така реалізація зустрічається не так уже й рідко. Просто вона часто ховається за різними назвами - індексні масиви, масиви відповідності і т.п. Незважаючи на різницю в назвах, використовується один і той же алгоритм. - прим.ред.
Реалізація пов'язаного списку на базі масивів
Розглянемо цей спосіб на прикладі реалізації лінійного однозв'язного списку. Елементи такого списку лінійно впорядковані. Крім елементів у списку є навігатор, який може перебувати в наступних позиціях:
на початку списку (тобто перед першим елементом списку);
в кінці списку (тобто за останнім елементом списку);
між елементами списку.
Навігатор можна пересувати тільки від початку до кінця списку на один елемент за раз. Крім того, додавати елементи списку можна тільки в позиції, на яку посилається навігатор. А змінювати / видаляти / читати можна тільки елементи, які знаходяться в позиції, що передує тій, на яку посилається навігатор, тобто попереду по ходу його руху.
Основна ідея цієї реалізації полягає у відділенні інформації про вміст елементів списку від інформації про порядок їх проходження. Графічно ця ідея представлена на малюнку 1.
Далі посилання будемо зображати стрілками, як показано на малюнку 2.
Природно, що для роботи зі списком одних тільки посилань між елементами недостатньо - треба знати, наприклад, де розташований перший елемент списку, і відрізняти останній елемент від всіх інших (адже за ним вже ніяких елементів немає). Для цих цілей можна було б ввести дві змінні, які містили б індекси початку і кінця списку. Ми, однак, цього робити не будемо, а будемо використовувати прийомом «згортання в кільце» - «звернемо» список, ввівши спеціальний уявний елемент NULL, який завжди будемо мати у своєму розпорядженні в елементі з індексом NullElem (які мають значення 0) масиву, використовуваного для зберігання посилань на елементи списку (назвемо його Refs). На малюнку 3 показано графічне представлення цієї моделі.
Порожньому списку відповідає ситуація, коли в кільці ніяких елементів, крім NullElem, немає, тобто осередок масиву посилань з індексом NullElem посилається сама на себе.
Навігатор розташовується між елементами, тому реалізуємо його у вигляді двох змінних BEFORE і AFTER, де AFTER містить індекс елемента за пройденим, а BEFORE - індекс елемента ще не пройденого елемента. Положення навігатора на початку списку, таким чином, відповідає випадок, коли AFTER дорівнює NullElem, а положенню в кінці - коли це значення міститься в BEFORE.
Тепер пов'язаний список земітовано повністю. Незрозумілим залишається тільки наступні питання:
Як визначати наявність або відсутність вільного місця в масиві елементів (назвемо його Elems)?
Як знаходити вільний елемент в масиві елементів при імітації додавання елемента до списку?
Щоб не ворожити, які елементи Elems вільні, а які зайняті, приймемо рішення, зберігати крім списку зайнятих елементів так само список вільних. Елементи цього списку також будуть з'єднані в кільце, що починається зі службового елемента зберігається в елементі з індексом NullFreeSpace (рівним одиниці) масиву посилань (Refs). Графічне представлення моделі, що вийшла зображено на малюнку 4.
Таким чином, щоб визначити, чи є в списку вільне місце, треба подивитися значення елемента Refs (NullFreeSpace). Якщо це значення дорівнює NullFreeSpace (тобто показує на себе), то вільного місця немає. В іншому випадку це значення вказує на перший вільний елемент масиву елементів. При додаванні елемента до списку необхідно виключити індекс цього елемента зі списку вільних і включити його до основного списку. При видаленні елемента необхідно зробити зворотну операцію.
На малюнку 4 чорним кольором позначений Автоматичне виведення пов'язаний список, а червоним - список вільних елементів.
У програмній реалізації списку присвоювання посиланню з індексом virtualIndex значення realIndex виділимо в окрему підпрограму. Крім того, в окремі підпрограми виділимо всі дії, пов'язані з роботою з вільним місцем.
З урахуванням всіх вищесказаних зауважень реалізація однозв'язного лінійного списку на Visual Basic 6.0 може мати вигляд, наведений нижче.