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

После изучения стеков и очередей, основанных на связных списках и массивах, вы, наверное, задали себе вопрос: "Какой тип лучше использовать?" Тесты на контроль времени в различных версиях Delphi (16- и 32-разрядных) показали, что в большинстве случаев быстрее оказывается версия, основанная на массиве. Ее и лучше использовать. Исключением является случай, когда в Delphi 1 количество элементов в стеке или очереди превышает 16000 - это максимальное значение для Delphi 1. Поэтому, если в вашем стеке или очереди будет больше 16000 элементов, в Delphi 1 потребуется работать со связными списками.

Поиск

Поиск - это действие, заключающееся в просмотре набора элементов и выделении из этого набора интересующего элемента. Наверное, все вы знакомы с одной из функций поиска - Pos из модуля SysUtils, которая предназначена для поиска подстроки в строке.

Эта и следующая главы, посвященные поиску, довольно-таки тесно связаны между собой. Часто поиск элемента приходится осуществлять в уже отсортированном контейнере. И если контейнер отсортирован, можно воспользоваться эффективным алгоритмом для поиска позиции вставки нового элемента, чтобы и после вставки контейнер оказался отсортированным. Тем не менее, поиск не ограничивается просмотром отсортированных списков. Мы, помимо прочих, рассмотрим простейший тип поиска - алгоритмы, которые кажутся почти очевидными и не заслуживают специального названия.

Кроме того, настоящая глава служит мостом между простыми фундаментальными контейнерами, массивами и связными списками, и более сложными, например, бинарными деревьями, списками пропусков и хеш-таблицами. Эффективный поиск зависит от сложности контейнера, в котором находятся элементы, поэтому мы приводим алгоритмы как для массивов, так и для связных списков. В последующих главах при рассмотрении более сложных контейнеров мы всегда будем говорить об оптимальной стратегии писка для обсуждаемых структур данных.

Очереди на основе массивов || Оглавление || Процедуры сравнения


Фундаментальные алгоритмы и структуры данных в Delphi



Новости за месяц

  • Апрель
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс