Предыдущая страница реферата | 13  14  15  16  17  18  19  20  21  22  23 | Следующая страница реферата

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

Рекомендуем скачать другие рефераты по теме: доклад по химии, конспект зима.





Предыдущая страница реферата | 13  14  15  16  17  18  19  20  21  22  23 | Следующая страница реферата