Инкапсуляция связных списков

Программа 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 управляет внутренней организацией связного списка. В нем находятся процедуры для добавления и удаления элементов, возвращения значения элемента по его индексу, числа элементов в списке, и очистки списка. Этот класс позволяет обращаться со связным списком почти как с массивом.

Это намного упрощает основную программу. Например, следующий код показывает, как программа LnkList2 удаляет элемент из списка. Только одна строка в программе в действительности отвечает за удаление элемента. Остальные отображают новый список. Сравните этот код с предыдущей процедурой:

 

Private sub CmdRemoveAfter_Click()

Llist.RemoveAfter SelectedIndex

 

SelectedItem SelectedList ‘ Снова выбрать элемент.

DisplayList

NewItem.SetFocus

CmdClearList.Enabled

End Sub

 

 

=====33

 

Доступ к ячейкам

Класс LinkedList, используемый программой LnkLst2, позволяет основной программе использовать список почти как массив. Например, подпрограмма Item, приведенная в следующем коде, возвращает значение элемента по его положению:

 

Function Item(ByVal position As Long) As Variant

Dim ptr As ListCell

 

If position < 1 Or position > m_NumItems Then

   ‘ Выход за границы. Вернуть NULL.

   Item = Null

   Exit Function

End If

 

‘ Найти элемент.

Set ptr = m_Sentinel

Do While position > 0

   position = position - 1

   Set ptr = ptr.NextCell

Loop

 

Item = ptr.Value

End Function

 

Эта процедура достаточно проста, но она не использует преимущества связной структуры списка. Например, предположим, что программе требуется последовательно перебрать все объекты в списке. Она могла бы использовать подпрограмму Item для поочередного доступа к ним, как показано в следующем коде:

 

Dim i As Integer

 

For i = 1 To LList.NumItems

   ‘ Выполнить какие‑либо действия с LList.Item(i).

      :

Next i

 

При каждом вызове процедуры Item, она просматривает список в поиске следующего элемента. Чтобы найти элемент I, программа должна пропустить I‑1 элементов. Чтобы проверить все элементы в списке из N элементов, процедура пропустит 0+1+2+3+…+N-1 =N*(N-1)/2 элемента. При больших N программа потеряет много времени на пропуск элементов.

Класс LinkedList может ускорить эту операцию, используя другой метод доступа. Можно использовать частную переменную m_CurrentCell для отслеживания текущей позиции в списке. Для возвращения значения текущего положения используется подпрограмма CurrentItem. Процедуры MoveFirst, MoveNext и EndOfList позволяют основной программе управлять текущей позицией в списке.

 

=======34

 

Например, следующий код содержит подпрограмму MoveNext:

 

Public Sub MoveNext()

‘ Если текущая ячейка не выбрана, ничего не делать.

If Not (m_CurrentCell Is Nothing) Then _

   Set m_CurrentCell = m_CurrentCell.NextCell

End Sub

 

При помощи этих процедур, основная программа может обратиться ко всем элементам списка, используя следующий код. Эта версия несколько сложнее, чем предыдущая, но она намного эффективнее. Вместо того чтобы пропускать N*(N-1)/2 элементов и опрашивать по очереди все N элементов списка, она не пропускает ни одного. Если список состоит из 1000 элементов, это экономит почти полмиллиона шагов.

 

LList.MoveFirst

 

Do While Not LList.EndOfList

‘ Выполнить какие‑либо действия над элементом LList.Item(i).

   :

LList.MoveNext

Loop

 

Программа LnkList3 использует эти новые методы для управления связным списком. Она аналогична программе LnkList2, но более эффективно обращается к элементам. Для небольших списков, используемых в программе, эта разница незаметна. Для программы, которая обращается ко всем элементам большого списка, эта версия класса LinkedList более эффективна.

Разновидности связных списков

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