Реализация связанных списков на базе массивов
Категория реферата: Рефераты по информатике, программированию
Теги реферата: правовые рефераты, оформление доклада
Добавил(а) на сайт: Mstislava.
Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 | Следующая страница реферата
Далее ссылки будем изображать стрелками, как показано на рисунке 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, указывающей на первый элемент из "свободного места" Рекомендуем скачать другие рефераты по теме: дипломная работа по психологии, рефераты. Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 | Следующая страница реферата Поделитесь этой записью или добавьте в закладкиКатегории: |