Связные списки

Другая стратегия используется при управлении связанными списками. Связанный список хранит элементы в структурах данных или объектах, которые называются ячейками (cells). Каждая ячейка содержит указатель на следующую ячейку в списке. Так как единственный тип указателей, которые поддерживает Visual Basic — это ссылки на объекты, то ячейки в связном списке должны быть объектами.

В классе, задающем ячейку, должна быть определена переменная NextCell, которая указывает на следующую ячейку в списке. В нем также должны быть определены переменные, содержащие данные, с которыми будет работать программа. Эти переменные могут быть объявлены как открытые (public) внутри класса, или класс может содержать процедуры для чтения и записи значений этих переменных. Например, в связном списке с записями о сотрудниках, в этих полях могут находиться имя сотрудника, номер социального страхования, название должности, и т.д. Определения для класса EmpCell могут выглядеть примерно так:

Public EmpName As String

Public SSN As String

Public JobTitle As String

Public NextCell As EmpCell

Программа создает новые ячейки при помощи оператора New, задает их значения и соединяет их, используя переменную NextCell.

Программа всегда должна сохранять ссылку на вершину списка. Для того, чтобы определить, где заканчивается список, программа должна установить значение NextCell для последнего элемента списка равным Nothing (ничего). Например, следующий фрагмент кода создает список, представляющий трех сотрудников:

Dim top_cell As EmpCell

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,(для сетевой версии исключены, т.к. они многократно увеличивают размер загружаемого файла) чтобы помочь вам наглядно представить ситуацию там, где это возможно. Многие из алгоритмов, которые используют указатели, можно легко проиллюстрировать подобными рисунками.