Dim cell1 As EmpCell
Dim cell2 As EmpCell
Dim cell3 As EmpCell
‘ Создание ячеек.
Set cell1 = New EmpCell
cell1.EmpName = "Стивенс”
cell1.SSN = "123-45-6789"
cell1.JobTitle = "Автор"
Set cell2 = New EmpCell
cell2.EmpName = "Кэтс”
cell2.SSN = "123-45-6789"
cell2.JobTitle = "Юрист"
Set cell3 = New EmpCell
cell3.EmpName = "Туле”
cell3.SSN = "123-45-6789"
cell3.JobTitle = "Менеджер"
‘ Соединить ячейки, образуя связный список.
Set cell1.NextCell = cell2
Set cell2.NextCell = cell3
Set cell3.NextCell = Nothing
‘ Сохранить ссылку на вершину списка.
Set top_cell = cell1
===============27
На рис. 2.2 показано схематическое представление этого связного списка. Прямоугольники представляют ячейки, а стрелки — ссылки на объекты. Маленький перечеркнутый прямоугольник представляет значение Nothing, которое обозначает конец списка. Имейте в виду, что top_cell, cell1 и cell2 – это не настоящие объекты, а только ссылки, которые указывают на них.
Следующий код использует связный список, построенный при помощи предыдущего примера для печати имен сотрудников из списка. Переменная ptr используется в качестве указателя на элементы списка. Она первоначально указывает на вершину списка. В коде используется цикл Do для перемещения ptr по списку до тех пор, пока указатель не дойдет до конца списка. Во время каждого цикла, процедура печатает поле EmpName ячейки, на которую указывает ptr. Затем она увеличивает ptr, указывая на следующую ячейку в списке. В конце концов, ptr достигает конца списка и получает значение Nothing, и цикл Do останавливается.
Dim ptr As EmpCell
Set ptr = top_cell ‘ Начать с вершины списка.
Do While Not (ptr Is Nothing)
‘ Вывести поле EmpName этой ячейки.
Debug.Print ptr.Empname
‘ Перейти к следующей ячейке в списке.
Set ptr = ptr.NextCell
Loop
После выполнения кода вы получите следующий результат:
Стивенс
Кэтс
Туле
@Рис. 2.2. Связный список
=======28
Использование указателя на другой объект называется косвенной адресацией (indirection), поскольку вы используете указатель для косвенного манипулирования данными. Косвенная адресация может быть очень запутанной. Даже для простого расположения элементов, такого, как связный список, иногда трудно запомнить, на какой объект указывает каждая ссылка. В более сложных структурах данных, указатель может ссылаться на объект, содержащий другой указатель. Если есть несколько указателей и несколько уровней косвенной адресации, вы легко можете запутаться в них
Для того, чтобы облегчить понимание, в изложении используются иллюстрации, такие как рис. 2.2,(для сетевой версии исключены, т.к. они многократно увеличивают размер загружаемого файла) чтобы помочь вам наглядно представить ситуацию там, где это возможно. Многие из алгоритмов, которые используют указатели, можно легко проиллюстрировать подобными рисунками.
Простой связный список, показанный на рис. 2.2, обладает несколькими важными свойствами. Во‑первых, можно очень легко добавить новую ячейку в начало списка. Установим указатель новой ячейки NextCell на текущую вершину списка. Затем установим указатель top_cell на новую ячейку. Рис. 2.3 соответствует этой операции. Код на языке Visual Basic для этой операции очень прост:
Set new_cell.NextCell = top_cell
Set top_cell = new_cell
@Рис. 2.3. Добавление элемента в начало связного списка
Сравните размер этого кода и кода, который пришлось бы написать для добавления нового элемента в начало списка, основанного на массиве, в котором потребовалось бы переместить все элементы массива на одну позицию, чтобы освободить место для нового элемента. Эта операция со сложностью порядка O(N) может потребовать много времени, если список достаточно длинный. Используя связный список, моно добавить новый элемент в начало списка всего за пару шагов.
======29
Так же легко добавить новый элемент и в середину связного списка. Предположим, вы хотите вставить новый элемент после ячейки, на которую указывает переменная after_me. Установим значение NextCell новой ячейки равным after_me.NextCell. Теперь установим указатель after_me.NextCell на новую ячейку. Эта операция показана на рис. 2.4. Код на Visual Basic снова очень прост:
Set new_cell.NextCell = after_me.NextCell
Set after_me.NextCell = new_cell
Удалить элемент из вершины связного списка так же просто, как и добавить его. Просто установите указатель top_cell на следующую ячейку в списке. Рис. 2.5 соответствует этой операции. Исходный код для этой операции еще проще, чем код для добавления элемента.
Set top_cell = top_cell.NextCell
Когда указатель top_cell перемещается на второй элемент в списке, в программе больше не останется переменных, указывающих на первый объект. В этом случае, счетчик ссылок на этот объект станет равен нулю, и система автоматически уничтожит его.
Так же просто удалить элемент из середины списка. Предположим, вы хотите удалить элемент, стоящий после ячейки after_me. Просто установите указатель NextCell этой ячейки на следующую ячейку. Эта операция показана на рис. 2.6. Код на Visual Basic прост и понятен:
after_me.NextCell = after_me.NextCell.NextCell
@Рис. 2.4. Добавление элемента в середину связного списка
=======30
@Рис. 2.5. Удаление элемента из начала связного списка
Снова сравним этот код с кодом, который понадобился бы для выполнения той же операции, при использовании списка на основе массива. Можно быстро пометить удаленный элемент как неиспользуемый, но это оставляет в списке ненужные значения. Процедуры, обрабатывающие список, должны это учитывать, и соответственно быть более сложными. Присутствие чрезмерного количества «мусора» также замедляет работу процедуры, и, в конце концов, придется проводить чистку памяти.
При удалении элемента из связного списка, в нем не остается пустых промежутков. Процедуры, которые обрабатывают список, все так же обходят список с начала до конца, и не нуждаются в модификации.
Можно предположить, что для уничтожения связного списка необходимо обойти весь список, устанавливая значение NextCell для всех ячеек равным Nothing. На самом деле процесс гораздо проще: только top_cell принимает значение Nothing.
Когда программа устанавливает значение top_cell равным Nothing, счетчик ссылок для первой ячейки становится равным нулю, и Visual Basic уничтожает эту ячейку.
Во время уничтожения ячейки, система определяет, что в поле NextCell этой ячейки содержится ссылка на другую ячейку. Поскольку первый объект уничтожается, то число ссылок на второй объект уменьшается. При этом счетчик ссылок на второй объект списка становится равным нулю, поэтому система уничтожает и его.
Во время уничтожения второго объекта, система уменьшает число ссылок на третий объект, и так далее до тех пор, пока все объекты в списке не будут уничтожены. Когда в программе уже не будет ссылок на объекты списка, можно уничтожить и весь список при помощи единственного оператора Set top_cell = Nothing.
@Рис. 2.6. Удаление элемента из середины связного списка
========31
Для добавления или удаления элементов из начала или середины списка используются различные процедуры. Можно свести оба этих случая к одному и избавиться от избыточного кода, если ввести специальную сигнальную метку (sentinel) в самом начале списка. Сигнальную метку нельзя удалить. Она не содержит данных и используется только для обозначения начала списка.
Теперь вместо того, чтобы обрабатывать особый случай добавления элемента в начало списка, можно помещать элемент после метки. Таким же образом, вместо особого случая удаления первого элемента из списка, просто удаляется элемент, следующий за меткой.
Использование сигнальных меток пока не вносит особых различий. Сигнальные метки играют важную роль в гораздо более сложных алгоритмах. Они позволяют обрабатывать особые случаи, такие как начало списка, как обычные. При этом требуется написать и отладить меньше кода, и алгоритмы становятся более согласованными и более простыми для понимания.
В табл. 2.1 сравнивается сложность выполнения некоторых типичных операций с использованием списков на основе массивов со «сборкой мусора» или связных списков.
Списки на основе массивов имеют одно преимущество: они используют меньше памяти. Для связных списков необходимо добавить поле NextCell к каждому элементу данных. Каждая ссылка на объект занимает четыре дополнительных байта памяти. Для очень больших массивов это может потребовать больших затрат памяти.
Программа LnkList1 демонстрирует простой связный список с сигнальной меткой. Введите значение в текстовое поле ввода, и нажмите на элемент в списке или на метку. Затем нажмите на кнопку Add After (Добавить после), и программа добавит новый элемент после указанного. Для удаления элемента из списка, нажмите на элемент и затем на кнопку Remove After (Удалить после).
@Таблица 2.1. Сравнение списков на основе массивов и связных списков
=========32
Программа LnkList1 управляет списком явно. Например, следующий код показывает, как программа удаляет элемент из списка. Когда подпрограмма начинает работу, глобальная переменная SelectedIndex дает положение элемента, предшествующего удаляемому элементу в списке. Переменная Sentinel содержит ссылку на сигнальную метку списка.
Private Sub CmdRemoveAfter_Click()
Dim ptr As ListCell
Dim position As Integer
If SelectedIndex < 0 Then Exit Sub
‘ Найти элемент.
Set ptr = Sentinel
position = SelectedIndex
Do While position > 0
position = position - 1
Set ptr = ptr.nextCell
Loop
‘ Удалить следуюший элемент.
Set ptr.NextCell = ptr.NextCell.NextCell
NumItems = NumItems - 1
SelectItem SelectedIndex ‘ Снова выбрать элемент.
DisplayList
NewItem.SetFocus
End Sub
Чтобы упростить использование связного списка, можно инкапсулировать его функции в классе. Это реализовано в программе LnkList2 . Она аналогична программе LnkList1, но использует для управления списком класс LinkedList.
Класс LinekedList управляет внутренней организацией связного списка. В нем находятся процедуры для добавления и удаления элементов, возвращения значения элемента по его индексу, числа элементов в списке, и очистки списка. Этот класс позволяет обращаться со связным списком почти как с массивом.