Реалізація пов'язаних списків на базі масивів

Чуриков Костянтин, Донбаський державний технічний університет

Визначення лінійних списків

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

З реалізаціями лінійних списків в імперативних мовах програмування можуть виконуватися такі операції:

отримання доступу до деякого елементу списку для перевірки та/або зміни вмісту його полів;

вставка нового елемента відразу перед або після довільного елемента;

видалення довільного елемента;

об'єднання в одному списку двох (або більше) лінійних списків;

розбиття лінійного списку на два (або більше) списку;

створення копії лінійного списку;

визначення кількості елементів в списку;

сортування елементів списку;

пошук елементів із заданим значенням.

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

Внутрішнє подання лінійних списків

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

Послідовне зберігання лінійних списків розглянуто в безлічі джерел і не становить предмету даної статті [1]. Також широко розглянуто пов'язане зберігання лінійних списків, але в переважній більшості випадків така реалізація заснована на посилальної реалізації [2]. У той Водночас існує витончена, але мало відома широкому колу молодих програмістів реалізація зв'язкового зберігання лінійних списків на базі масивів. Досить докладний, хоч і вельми специфічне опис такої реалізації дано в [3]. Цьому способу і присвячена ця стаття.        

ПРИМІТКА   

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

Реалізація пов'язаного списку на базі масивів

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

на початку списку (тобто перед першим елементом списку);

в кінці списку (тобто за останнім елементом списку);

між елементами списку.

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

Основна ідея цієї реалізації полягає у відділенні інформації про вміст елементів списку від інформації про порядок їх проходження. Графічно ця ідея представлена на малюнку 1.

Малюнок 1.

Далі посилання будемо зображати стрілками, як показано на малюнку 2.

Малюнок 2.

Природно, що для роботи зі списком одних тільки посилань між елементами недостатньо - треба знати, наприклад, де розташований перший елемент списку, і відрізняти останній елемент від всіх інших (адже за ним вже ніяких елементів немає). Для цих цілей можна було б ввести два змінні, які містили б індекси початку і кінця списку. Ми, однак, цього робити не будемо, а скористаємося прийомом «згортання в кільце» -- «Звернемо» список, ввівши спеціальний уявний елемент NULL, який завжди будемо мати у своєму розпорядженні в елементі з індексом NullElem (який має значення 0) масиву, використовуваного для зберігання посилань на елементи списку (назвемо його Refs). На малюнку 3 показано графічне представлення цієї моделі.

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

Малюнок 3.

пустому списку відповідає ситуація, коли у кільці ніяких елементів, крім NullElem, немає, тобто, осередок масиву посилань з індексом NullElem посилається сама на себе.

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

Тепер пов'язаний список зімітував повністю. Незрозумілим залишається тільки наступні питання:

Як визначати наявність або відсутність вільного місця в масиві елементів (назвемо його Elems)?

Як знаходити вільний елемент в масиві елементів при імітації додавання елемента до списку?

Щоб не гадати, які елементи Elems вільні, а які зайняті, приймемо рішення, зберігати крім списку зайнятих елементів так само список вільних. Елементи цього списку також будуть з'єднані в кільце, що починається з службового елемента зберігається в елементі з індексом NullFreeSpace (рівним одиниці) масиву посилань (Refs). Графічне представлення що вийшла моделі зображено на малюнку 4.

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

На малюнку 4 чорним кольором позначений Автоматичне виведення пов'язаний список, а червоним - список вільних елементів.

Малюнок 4.

У програмній реалізації списку присвоювання посиланню з індексом virtualIndex значення realIndex виділимо в окрему підпрограму. Крім того, в окремі підпрограми виділимо всі дії, пов'язані з роботою з вільним місцем.        

ПРИМІТКА   

У прикладі описується створення списку   для зберігання дійсних чисел. Щоб створити список елементів іншого типу   потрібно відповідним чином змінити оголошення типу елементів масиву   Elems (), типу параметра element у процедурі AddItem () і типу що повертається   значення у функції ReadItem (). Мається на увазі, що наведений код оформлений у   вигляді окремого модуля або класу, що краще. Крім того, хоча в   статті розглянуто обмежений список, у реалізації передбачена можливість   динамічного збільшення довжини списку в разі потреби.     

З урахуванням усіх зауважень вищесказаних реалізація односвязного лінійного списку на Visual Basic 6.0 може мати вигляд, наведений нижче.

Клас MyLinkedList:        

'номер комірки Refs,   що вказує на перший елемент списку   

Const NullElem = 0   

'номер комірки Refs,   що вказує на перший елемент з "вільного місця"   

Const NullFreeSpace =   1      

Dim Elems () As Double 'Масив для зберігання елементів списку   

Dim Refs () As Integer 'Масив для зберігання посилань   

Dim AFTER As Integer 'Покажчик попереднього   елемента   

Dim BEFORE As Integer 'Покажчик наступного елемента   

Dim Count As Integer 'Кількість елементів у списку      

'Створення списку для   зберігання capacity елементів   

'1-а осередок Refs вказує   на перший елемент списку   

'2-я осередок Refs вказує   на 1-й елемент Х з "вільного місця"   

'capacity - максимально   допустиму кількість елементів у списку.   

Sub CreateLinkedList (capacity As Integer)   

ReDim Elems (capacity + 1)   

ReDim Refs (capacity + 1)   

ClearList   

End Sub      

'Очищення списку   

Sub ClearList ()   

Refs (NullElem) = NullElem 'кінець списку вказує сам на себе   

Dim i As Integer   

'Оскільки список порожній, то всі комірки   масиву позначаються   

'як "вільне місце".   

For i = NullFreeSpace To   UBound (Refs) - 1   

Refs (i) = i + 1   

Next i   

Refs (UBound (Refs)) =   NullFreeSpace 'закільцьовують "вільне місце".   

AFTER = 0   

BEFORE = 0   

Count = 0   

End Sub      

'Присвоєння віртуального індексом virtualIndex значення realIndex   

Private Sub Link (virtualIndex As Integer, realIndex As Integer)   

Refs (virtualIndex) = realIndex   

End Sub      

'Виділення місця для нових   елементів   

Private Function GetSpace () As Integer   

Dim i As Integer, OldLength As   Integer   

If IsListFull Then   

OldLength = UBound (Elems)   

ReDim Preserve   Elems (OldLength * 2) 'динамічне збільшення довжини   

ReDim Preserve   Refs (OldLength * 2) 'списку, якщо він вже повністю заповнений   

For i = OldLength + 1 To OldLength * 2 - 1   'додаються елементи позначаються   

Refs (i) = i + 1 'як вільне місце   

Next i   

Refs (NullFreeSpace) =   OldLength + 1   

Refs (OldLength * 2) =   NullFreeSpace   

End If   

i = Refs (NullFreeSpace)   

Link NullFreeSpace, Refs (i)   

GetSpace = i   

End Function      

'звільнення місця при   видалення елемента зі списку   

Private Sub PutSpace (i As Integer)   

Link i, Refs (NullFreeSpace)   

Link NullFreeSpace, i   

End Sub      

'додати element до списку   

Sub AddItem (element As Double)   

Dim i As Integer   

i = GetSpace () 'отримуємо вільне місце   

Link AFTER, i '   встановлюємо його в   

Link i, BEFORE 'потрібному місці списку   

BEFORE = i 'встановлюємо покажчик   

Elems (i) = element 'додаємо елемент   element до списку   

MoveNext   

Count = Count + 1 'збільшуємо лічильник кількості елементів   

End Sub      

'видалити елемент зі списку   

Sub RemoveItem ()   

Dim i As Integer   

If Count <> 0 Then   

i = BEFORE   

BEFORE = Refs (i)   

Link AFTER, BEFORE   

PutSpace i   

Count = Count - 1   

Else   

Err.Raise vbObjectError +   513,, "List is empty"   

End If   

End Sub      

'прочитати значення   елемента зі списку   

'якщо параметр Index   відсутній або   

'не є порядковим   номером еелемента списку   

'то повертається значення   елемента перед покажчиком   

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

'з порядковим номером Index   

Function ReadItem (Optional Index As Integer = -1) As Double   

If Not (Index> = 0 And   Index   

If IsEndOfList Then   

ReadItem = Elems (AFTER)   

Else   

ReadItem = Elems (BEFORE)   

End If   

Else   

Dim i As Integer, k As   Integer   

k = NullElem   

For i = 0 To Index   

k = Refs (k)   

Next i   

ReadItem = Elems (k)   

End If   

End Function      

'повернути кількість   елементів у списку   

Function GetCount () As Integer   

GetCount = Count   

End Function      

'визначити, чи є   вільне місце в списку   

Private Function IsListFull () As Boolean   

IsListFull = False   

If Refs (NullFreeSpace) =   NullFreeSpace Then IsListFull = True   

End Function      

'пересунути вказівник на   один елемент списку   

Sub MoveNext ()   

AFTER = BEFORE   

BEFORE = Refs (BEFORE)   

End Sub      

'пересунути покажчик в   початок списку   

Sub MoveFront ()   

AFTER = 0   

BEFORE = Refs (NullElem)   

End Sub      

'визначити, чи знаходиться   покажчик в кінці списку   

Function IsEndOfList () As Boolean   

IsEndOfList = False   

If Refs (AFTER) = NullElem Then   IsEndOfList = True   

End Function     

Приклад використання даної реалізації списку:        

Sub Test ()   

Dim i As Integer   

Dim list1 As MyLinkedList   

Set list1 = New MyLinkedList   

list1.CreateLinkedList 3   

'висновок кількості елементів   

Debug.Print "count of elems =",   list1.GetCount - 1   

'заповнення списку випадковими числами   

Randomize   

For i = 1 To 5   

list1.AddItem Rnd () * 100   

Next i   

'висновок вмісту списку   

list1.MoveFront   

Do Until list1.IsEndOfList   

Debug.Print   list1.ReadItem   

list1.MoveNext   

Loop   

'висновок кількості елементів   

Debug.Print "count of   elems = ", list1.GetCount - 1   

'видалення першого елемента   

list1.MoveFront   

list1.RemoveItem   

'висновок вмісту списку   

list1.MoveFront   

Do Until list1.IsEndOfList   

Debug.Print   list1.ReadItem   

list1.MoveNext   

Loop   

'висновок вмісту 2-го елемента   

Debug.Print list1.ReadItem (2)   

End Sub     

Список літератури

Д. Батіг. Мистецтво програмування. (3-е издание) Т.1.

А.Г. Кушніренко, Г.В. Лебедєв. Програмування для математиків. М: Наука. 1988, стор 202-210.

Для підготовки даної роботи були використані матеріали з сайту http://www.rsdn.ru/