Род Стивенс

Книги → 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

Публикация компанией Dropbox кода Zulip – средства общения для IT-разработчиков

20.11.2015
Одной из одобрительно встреченных программистами инициатив, реализующихся в рамках акции Hack Week, стала публикация исходного кода приложения Zulip – веб-приложения для общения между собой разработчиков в сфере IT-технологий.

Объединение ОС Android и Chrome

17.11.2015
Слухи об объединении двух крупнейших ОС компании Google, Android и Chrome, гуляют по Интернету уже более 5 лет, но до сих пор этого не случилось, хотя очевидно, что с течением времени эти ОС становятся всё более похожими: так, в последнее время появилось немало Android-устройств, к которым прилагаются клавиатуры, а Chrome OS «научилась» работать с сенсорными экранами.

Конференция Linux Piter 2015

15.11.2015
Уже почти через неделю в Санкт-Петербурге впервые в истории пройдёт конференция, посвящённая проблемам свободного программного обеспечения – Linux Piter 2015.