MyBooks.club
Все категории

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

На сайте mybooks.club вы можете бесплатно читать книги онлайн без регистрации, включая Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi. Жанр: Программирование издательство -,. Доступна полная версия книги с кратким содержанием для предварительного ознакомления, аннотацией (предисловием), рецензиями от других читателей и их экспертным мнением.
Кроме того, на сайте mybooks.club вы найдете множество новинок, которые стоит прочитать.

Название:
Фундаментальные алгоритмы и структуры данных в Delphi
Издательство:
-
ISBN:
-
Год:
-
Дата добавления:
17 сентябрь 2019
Количество просмотров:
229
Читать онлайн
Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi

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

Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi - описание и краткое содержание, автор Джулиан Бакнелл, читайте бесплатно онлайн на сайте электронной библиотеки mybooks.club
Книга "Фундаментальные алгоритмы и структуры данных в Delphi" представляет собой уникальное учебное и справочное пособие по наиболее распространенным алгоритмам манипулирования данными, которые зарекомендовали себя как надежные и проверенные многими поколениями программистов. По данным журнала "Delphi Informant" за 2002 год, эта книга была признана сообществом разработчиков прикладных приложений на Delphi как «самая лучшая книга по практическому применению всех версий Delphi».В книге подробно рассматриваются базовые понятия алгоритмов и основополагающие структуры данных, алгоритмы сортировки, поиска, хеширования, синтаксического разбора, сжатия данных, а также многие другие темы, тесно связанные с прикладным программированием. Изобилие тщательно проверенных примеров кода существенно ускоряет не только освоение фундаментальных алгоритмов, но также и способствует более квалифицированному подходу к повседневному программированию.Несмотря на то что книга рассчитана в первую очередь на профессиональных разработчиков приложений на Delphi, она окажет несомненную пользу и начинающим программистам, демонстрируя им приемы и трюки, которые столь популярны у истинных «профи». Все коды примеров, упомянутые в книге, доступны для выгрузки на Web-сайте издательства.

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

Фундаментальные алгоритмы и структуры данных в Delphi - читать книгу онлайн бесплатно, автор Джулиан Бакнелл

begin

{переместить курсор по его указателю Next, игнорировать попытку выхода за конечный узел списка}

if (FCursor <> nil) then begin

FParent := FCursor;

FCursor := FCursor^.slnNext;

inc(FCursorIx);

end;

end;


Вы, возможно, обратили внимание, что некоторые из приведенных методов пользуются полем объекта FCursorIx. Именно это поле позволяет обеспечить высокую эффективность методов, основанных на использовании индекса, поскольку в нем хранится индекс курсора (при этом первый узел имеет индекс 0, точно так же как в TList). Значение поля используется методом ellPositionAtNth, который оптимальным образом перемещает курсор в позицию с указанным индексом.

Листинг 3.10. Метод sllPositionAtNth


procedure TtdSingleLinkList.sllPositionAtNth(aIndex : longint);

var

WorkCursor : PslNode;

WorkParent : PslNode;

WorkCursorIx : longint;

begin

{проверить, корректно ли задан индекс}

if (aIndex < 0) or (aIndex >= Count) then

sllError(tdeListInvalidIndex, 'sllPositionAtNth');

{обработать наиболее простой случай}

if (aIndex = FCursorIx) then

Exit;

{—для повышения быстродействия использовать локальные переменные—}

{если заданный индекс меньше индекса курсора, переместить рабочий курсор в позицию перед всеми узлами}

if (aIndex < FCursorIx) then begin

WorkCursor := FHead;

WorkParent :=nil;

WorkCursorIx := -1;

end

{в противном случае поставить рабочий курсор в позицию текущего курсора}

else begin

WorkCursor :=FCursor;

WorkParent := FParent;

WorkCursorIx := FCursorIx;

end;

{пока индекс рабочего курсора меньше заданного индекса, передвинуть его на одну позицию вперед}

while (WorkCursorIx < aIndex) do

begin

WorkParent := WorkCursor;

WorkCursor := WorkCursor^.slnNext;

inc(WorkCursorIx);

end;

{установить реальный курсор равным рабочему курсору}

FCursor := WorkCursor;

FParent := WorkParent;

FCursorIx := WorkCursorIx;

end;


Метод sllPositionAtNth для увеличения быстродействия использует локальные переменные. Вначале метод определяет, больше ли заданный индекс индекса курсора (в этом случае поиск узла начинается с позиции курсора) или же он меньше (поиск узла начинается с начала списка). Без знания позиции курсора мы всегда бы начинали поиск с начала списка.

Реализация остальных методов, основанных на использовании индекса, после написания кода метода sllPositionAtNth не представляет особых трудностей.

Листинг 3.11. Методы класса TtdSingleLinkList, основанные на использовании индекса


procedure TtdSingleLinkList.Delete(aIndex : longint);

begin

{установить курсор в позицию с заданным индексом}

sllPositionAtNth(aIndex);

{удалить элемент в позиции курсора}

DeleteAtCursor;

end;


function TtdSingleLinkList.First : pointer;

begin

{установить курсор на первый узел}

SllPositionAtNth(0);

{вернуть данные с позиции курсора}

Result := FCursor^.slnData;

end;


procedure TtdSingleLinkList.Insert(aIndex : longint; aItem : pointer);

begin

{установить курсор в позицию с заданным индексом}

sllPositionAtNth(aIndex);

{вставить элемент в позицию курсора}

InsertAtCursor(aItem);

end;


function TtdSingleLinkList.Last : pointer;

begin

{установить курсор в позицию с заданным индексом}

sllPositionAtNth(pred(Count));

{вернуть данные с позиции курсора}

Result := FCursor^.slnData;

end;


function TtdSingleLinkList.sllGetItem(aIndex : longint): pointer;

begin

{установить курсор в позицию с заданным индексом}

sllPositionAtNth(aIndex);

{вернуть данные с позиции курсора}

Result := FCursor^.slnData;

end;


procedure TtdSingleLinkList.sllSetItem(aIndex : longint; aItem : pointer);

begin

{установить курсор в позицию с заданным индексом}

sllPositionAtNth(aIndex);

{если возможно удалить заменяемые данные, удалить их}

if Assigned(FDispose) and (aItem <> FCursor^.sInData) then

FDispose(FCursor^.slnData);

{заменить данные}

FCursor^.slnData := aItem;

end;


Теперь нам осталось рассмотреть еще несколько методов, которые по разным причинам реализованы в соответствие с главными принципами. Метод Add добавляет элемент в конец связного списка. Код поиска последнего узла достаточно прост и имеет смысл реализовать его в коде самого метода. В эту группу входит и метод IndexOf. Поиск заданного элемента с помощью этого метода можно организовать только в коде самого метода. После написания кода метода IndexOf реализация Remove становиться предельно простой.

Листинг 3.12. Методы Add, IndexOf и Remove


function TtdSingleLinkList.Add(aItem : pointer): longint;

var

WorkCursor : PslNode;

WorkParent : PslNode;

begin

{для увеличения быстродействия используются локальные переменные}

WorkCursor :=FCursor;

WorkParent :=FParent;

{перешли в конец связного списка}

while (WorkCursor <> nil) do

begin

WorkParent := WorkCursor;

WorkCursor := WorkCursor^.slnNext;

end;

{перенести реальный курсор}

FParent := WorkParent;

FCursor := nil;

FCursorIx := Count;

Result := Count;

{вставить элемент в позицию курсора}

InsertAtCursor(aItem);

end;


function TtdSingleLinkList.IndexOf(aItem : pointer): longint;

var

WorkCursor : PslNode;

WorkParent : PslNode;

WorkCursorIx : longint;

begin

{установить рабочий курсор на первый узел (если таковой существует)}

WorkParent := FHead;

WorkCursor := WorkParent^.slnNext;

WorkCursorIx := 0;

{идти по списку в поисках требуемого элемента}

while (WorkCursor <> nil) do

begin

if (WorkCursor^.slnData = aItem) then begin

{требуемый элемент найден; записать результат; установить реальный курсор в позицию рабочего курсора}

Result := WorkCursorIx;

FCursor := WorkCursor;

FParent := WorkParent;

FCursorIx := WorkCursorIx;

Exit;

end;

{перешли к следующему узлу}

WorkParent := WorkCursor;

WorkCursor := WorkCursor^.slnNext;

inc(WorkCursorIx);

end;

{требуемый элемент не найден}

Result := -1;

end;


procedure TtdSingleLinkList.Remove(aItem : pointer);

begin

if (IndexOf (aItem) <> -1) then

DeleteAtCursor;

end;


Полный код класса TtdSingleLinkList можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDLnlLst.pas.

Только что написанный нами класс обладает максимально возможной эффективностью. Узлы распределяются блоками. Определяющим фактором эффективности перехода от одного узла к другому, в общем случае, является скорость работы операционной системы по листанию страниц виртуальной памяти, но очевидно, что она будет зависеть от схемы использования связного списка. Если вставки и удаления элементов выполняются в случайном порядке, узлы будут разбросаны по различным страницам памяти. Как и в случае с классом TList, данные, на которые указывают ссылки каждого узла, будут находиться в разных участках памяти. Но здесь, к сожалению, мы ничего поделать не можем.

Двухсвязные списки

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


type

PSimpleNode = ^TSimpleNode;

TSimpleNode = record

Next : PSimpleNode;

Prior : PSimpleNode;

Data : SomeDataType;

end;


Таким образом, двухсвязный список позволяет двигаться по узлам не только вперед, по ссылкам Next, но и назад, по ссылкам Prior. Схематично двухсвязный список показан на рис. 3.4.


Рисунок 3.4. Двухсвязный список


Вставка и удаление элементов в двухсвязном списке

Каким образом вставлять новый узел в двухсвязный список? В односвязном списке для этого нужно было разорвать одну ссылку и вставить две новых, а для двухсвязного списка потребуется разорвать две ссылки и вставить четыре новых. Причем вставку можно выполнять как перед, так и после определенного элемента, поскольку указатель Prior позволяет проходить список в обратном направлении. Фактически операцию "вставить перед" можно запрограммировать как "перейти к предыдущему узлу и вставить после". Поэтому в главе мы рассмотрим только операцию "вставить после".

Ссылка Next нового узла устанавливается на узел, расположенный после заданного узла, а ссылка Next заданного узла устанавливается на новый узел. Для установки обратных ссылок ссылка Prior нового узла устанавливается на заданный узел, а ссылка Prior узла, следующего за новым, устанавливается на новый узел. В коде это выглядит следующим образом:


var

GivenNode, NewNode : PSimpleNode;

begin

• • •

New(NewNode);

.. задать значение поля Data ..

NewNode^.Next := GivenNode^.Next;

GivenNode^.Next := NewNode;

NewNode^.Prior := GivenNode;

NewNode^.Next^.Prior := NewNode;


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


Рисунок 3.5. Вставка нового узла в двухсвязный список


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


var

GivenNode, NodeToGo : PSimpleNode;

begin

• • •

NodeToGo := GivenNode^.Next;

GivenNode^.Next := NodeToGo^.Next;

NodeToGo^.Next^.Prior := GivenNode;

Dispose(NodeToGo);


Как и для односвязных списков, здесь для обеих операций существуют специальные случаи: вставка перед первым элементом списка (т.е. новый элемент становиться первым) и удаление первого элемента списка (т.е. первым становится другой элемент). Поскольку в наших рассуждениях первый элемент считается определяющим узлом всего списка, код для этих случаев потребуется написать отдельно.


Джулиан Бакнелл читать все книги автора по порядку

Джулиан Бакнелл - все книги автора в одном месте читать по порядку полные версии на сайте онлайн библиотеки mybooks.club.


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

Отзывы читателей о книге Фундаментальные алгоритмы и структуры данных в Delphi, автор: Джулиан Бакнелл. Читайте комментарии и мнения людей о произведении.

Прокомментировать
Подтвердите что вы не робот:*
Подтвердите что вы не робот:*
Все материалы на сайте размещаются его пользователями.
Администратор сайта не несёт ответственности за действия пользователей сайта..
Вы можете направить вашу жалобу на почту librarybook.ru@gmail.com или заполнить форму обратной связи.