Книги → Delphi. Готовые алгоритмы → Глава 2. Списки
Метки играют важную роль во многих сложных алгоритмах. Они позволяют программе обрабатывать особые случаи, например начало списка, как обычные.
В табл. 2.1 сравнивается сложность выполнения некоторых типичных операций при использовании списков на базе массивов со «сборкой мусора» и связанных списков.
Обычно связанные списки удобнее, но списки на базе массивов имеют одно существенное преимущество - они используют меньше памяти. Для связанного списка необходимо добавить к каждому элементу поле NextCell. Каждый из этих указателей занимает дополнительные четыре байта памяти. Для очень больших массивов могут потребоваться очень большие ресурсы памяти.
Программа LListl демонстрирует простой связанный список с меткой. Введите значение в текстовое поле и щелкните мышью по элементу списка или по метке. Затем нажмите кнопку Add After (Добавить после), и программа добавит новый элемент после указанного. Для удаления элемента выделите его и щелкните по кнопке Remove After (Удалить после).
Доступ к ячейкам
Класс TLinkedList, используемый программой LListl, позволяет главной программе обрабатывать список так же, как массив. Например, функция Item, приведенная в следующем фрагменте кода, возвращает значение элемента, заданного его позицией:
Function TLinkedList.Item(index : longint) : string;
var
cell_ptr t PLinkedListCell;
begin
// Нахождение ячейки. cell_ptr := Sentinel.NextCell; while (index>l) do begin
index := index-1;
cell_ptr := cell„ptr".NextCell;
end;
Item := се11_р!гЛ.Value;
end;
Эта процедура достаточно проста, но у нее нет преимуществ связанной структуры списка. Например, программа должна последовательно перебрать все элементы списка. Она может использовать процедуру Item, чтобы обращаться к элементам по порядку, как показано в следующем коде:
var
i : Integer;
begin
for i := 1 to the_list.Count do
begin
// Какие-то действия с the_list^Item(i).
end;
При каждом вызове процедура Item циклически исследует список в поиске следующего элемента. Чтобы найти элемент I в списке, программа должна пропустить 1-1 элементов. Чтобы проверить все элементы в списке из N элементов, она исследует 0 + 1+ 2 + 3.+ ... + N-1"N*(N-1)/ 2 элемента. При больших значениях N пропуск элементов займет очень много времени.
| ← предыдущая | следующая → |
Страницы раздела: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24