Реферат: Реализация связанных списков на базе массивов
Рисунок 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 - максимально допустимое количество элементов в списке. К-во Просмотров: 307
Бесплатно скачать Реферат: Реализация связанных списков на базе массивов
|