ИСАУ: Алгоритмы операций над сцепленными списками и их программная реализация

Рассмотрим алгоритмы выполнения основных операций над списками и их программную реализацию. Проход по списку Под проходом по списку понимается процесс поочередного перебора всех элементов списка. Эта задача возникает очень часто при обработке списка. Например, при необходимости поиска по ключу элемента в списке, вывода списка, копирования списка, добавление нового элемента в упорядоченный список и т.д. typePTEl = ^Person; Person = record// Областьсвязи PNext :PTEl;// Указатель на последующий элемент PPrev :PTEl;// Указатель на предыдущий элемент // Информационная область Surname :string[30]; // Фамилия Name :string[20]; // Имя Patronymic :string[30]; // Отчество Age : byte; // Возраст Birthday :TDate; // Датарождения Salary :integer; // Зарплата end; Алгоритм прохода по списку весьма тривиален и основан на том, что каждый элемент списка содержит ссылку на следующий, а последний элемент не указывает ни на кого. Поэтому алгоритм может быть записан следующим образом.

• Определяем некоторую вспомогательную ссылку на текущий элемент списка и определяем ее значение как ссылку на первый элемент.
• Если вспомогательная ссылка не указывает ни на какой элемент, то завершение алгоритма.
• Выполнение требуемой обработки элемента, на который указывает вспомогательная ссылка.
• Выбираем из элемента, на который указывает вспомогательная ссылка, ссылку на следующий элемент, и помещаем ее во вспомогательную ссылку.

Переход к пункту 2. Приведем программную реализацию этого алгоритма. Пусть в качестве вспомогательной ссылки используется переменная PCur типа PTEl. Тогда программная реализация может выглядеть следующим образом: procedureAlongOfList(PList : PTEl); varPCur :PTEl; begin PCur := PList; // Помещение в PCur указателя на первый элемент whilePCur<>nildo// Цикл по элементам пока в PCur есть ссылка на текущий элемент begin Processing(PCur); // Обработка элемента, на который указывает PCur. PCur := PCur.PNext; // Выборка указателя на следующий элемент end; end; Вызов процедуры осуществляется следующим образом: AlongOfList(PBeg); Определение количества элементов в списке Алгоритм определения количества элементов в списке основан на алгоритме прохода по списку и может быть сформулирован следующим образом:

• Определяем значение счетчика количества элементов равным нолю.
• Используя алгоритм прохода по списку, при выборе каждого нового элемента увеличиваем значение счетчика на единицу.
• По завершению прохода по списку счетчик содержит искомую величину.

Программная реализация в этом случае выглядит следующим образом: functionNumberOfListElemets (PList : PTEl):integer; varPCur : PTEl; begin Result := 0; PCur :=PList; whilePCur<>nil   do begin Result := Result+1; PCur :=PCur.PNext; end; end; Создание копии списка Алгоритм создания копии списка также основан на алгоритме прохода по списку и алгоритме включения элемента в конец списка. Формулировка очевидна и поэтому ограничимся только программной реализацией алгоритма. procedureCoprolite (PListSrc, PListDst :PTEl); varPCur, PCopy : PTEl; begin PCur :=PListSrc; while    PCur<>nil        do begin PCopy :=CreateNewElement; //Копирование содержимого элемента PCur в элемент PCopyAddToEnd(PListDst, PCopy);  PCur :=PCur.PNext;  end; end; Поиск элемента в списке При включении элемента в линейный список различается три варианта: включение в начало списка, в середину списка, в конец списка. Алгоритмы обработки каждого из этих вариантов различны. Это обусловлено тем фактом, что первый и последний элементы отличны от остальных: на первый не ссылается ни один из элементов списка, а последний элемент не ссылается ни на один из элементов списка. Рассмотрим эти алгоритмы в предположении:

• имеется новый элемент, у которого заполнена информационная область;
• содержимое указателя PNext в области связи равно nil;
• новый элемент определен указателем, хранимым в переменной PNew. Включение элемента в начало списка

Наиболее простым является алгоритм включения элемента в начало двусвязного списка:

• Если список пустой, то занести ссылку на новый элемент в указатель на начало списка. Завершить алгоритм.
• Занести в новый элемент ссылку на текущий первый элемент, взяв ее из указателя на начало списка.
• Занести в указатель на начало списка ссылку на новый элемент. Завершить алгоритм. Приведем программную реализацию этого алгоритма.

procedureAddToBegining(varPList:PTEl; PNewEl:PTEl); begin ifPList=nil then begin PList := PNewEl; exit; end; PNewEl.PNext     := PList; PList                     :=PNewEl; end; Вызов этой процедуры осуществляется следующим образом: AddToBegining(PBeg, PNew); Приведенный алгоритм располагает новые элементы в начале списка. Получаемый порядок элементов является обратным порядку их «поступления». Включение элемента в конец списка Немногим более сложен алгоритм включения нового элемента в конец списка. Отличие его состоит в том, что прежде чем вставлять новый элемент необходимо найти в списке последний элемент. Алгоритм для двусвязного списка можно сформулировать следующим образом:

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

procedureAddToEnd(VarPList:PTEl; PNewEl:PTEl); var PEl   : PTEl; begin ifPList=nil then begin PList := PNewEl; exit; end; PEl :=PList; whilePEl.PNext<>nil do PEl := PEl.PNext; PEl.PNext := PNewEl; PNewEl.PPrev := PEl; end; Приведенный алгоритм имеет недостаток, обусловленный необходимостью прохода по всему списку при добавлении нового элемента. Если список большой, то это приводит к большим временным затратам. Простой путь избежания этих затрат — введение и использование еще одной переменной — указателя списка PEnd, всегда указывающего на последний элемент. Этот метод используется практически всегда при работе со списками. Достоинства его очевидны. Единственный недостаток состоит в том, что первый включаемый в список элемент приходится обрабатывать иначе, чем остальные. Включение элемента в упорядоченный список Наиболее сложен алгоритм вставки нового элемента в середину списка. Обычно это требуется при создании упорядоченного списка. Предположим, что список упорядочен по возрастанию. Поэтому сначала производится поиск места в списке, в которое необходимо вставить новый элемент. После того, как поиск завершен возможны три варианта:

• вставка в начало списка;
• вставка в середину списка;
• вставка в конец списка.

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

• список двунаправленный;
• список однонаправленный.

Для двунаправленного списка алгоритм вставки нового элемента не представляет сложности т.к. мы имеем ссылку на предыдущий элемент из текущего элемента. Ниже приведенный рисунок иллюстрирует постановку задачи. Необходимо в существующий упорядоченный список вставить новый элемент со значением ключа равным 41. Алгоритм можно сформулировать следующим образом:

• В новом элементе: a. в ссылку на предыдущий элемент занести ссылку на предыдущий элемент, взятую из текущего элемента; b. в ссылку на последующий элемент занести ссылку на текущий элемент.
• В предыдущем элементе в качестве следующего занести ссылку на новый элемент.
• В текущем элементе в качестве ссылки на предыдущий занести ссылку на новый элемент.

Ниже приведенный рисунок иллюстрирует обсуждаемый алгоритм. Зеленым цветом указаны связи, которые должны быть установлены. Красным — удаляемые связи Программная реализация алгоритма может выглядеть следующим образом: procedureInsertBeforPCur(PList, PNewEl, PCur:PTEl); begin PNewEl.PNext  := PCur; PNewEl.PPrev  := PCur.PPrev; (PCur.PPrev).PNext     := PNewEl; PCur.PPrev             := PNewEl; end; В случае однонаправленного списка сложность решения поставленной задачи определяется тем, что у нас не имеется ссылки на предыдущий относительно PCur элемент. Можно, конечно, применить достаточно традиционный подход: при проходе по списку сохранять в специально зарезервированной переменной ссылку на предыдущий элемент. Тогда решение поставленной задачи очевидно. Но при таком подходе придется использовать относительно сложный алгоритм. В этом вы можете убедиться самостоятельно. Существует гораздо более элегантное решение проблемы средствами следующего алгоритма:

• Вставить новый элемент после (а не перед, как требуется) элемента PCur. В этом случае, у нас есть вся необходимая для этого информация. Для выполнения этого необходимо: 1.1. Занести в новый элемент ссылку на следующий за PCur, взяв ее из PCur. 1.2. Занести в элемент PCur ссылку на новый элемент.
• Теперь мы получили список, который отличается от упорядоченного тем, что у него переставлены местами элементы PCurи новый элемент. Следующее действие как раз и представляет изюминку алгоритма. 2.1. Поменяем местами информационные области элемента PCurи нового элемента. Это не составляет труда, т.к. мы имеем ссылки на оба элемента.

Ниже приведенный рисунок иллюстрирует обсуждаемый алгоритм. Зеленым цветом указаны связи, которые должны быть установлены. Красным — удаляемые связи. Синяя стрела обозначает обмен информационных областей элемента. Итак, приведем программную реализацию вставки нового элемента в упорядоченный по возрастанию список. ProcedureIsertElemetToList(PList, PNew : PTEL); varPCur :PTEl; begin// Проверка на то, что список не пустой ifPList=nil then begin // Списокпустой. AddToBegining(PList, PNew); exit;       // Завершениеалгоритма. end;// Поиск места включения нового элемента в список PCur := PList;         // Помещение в PСur указателя на первый элемент whilePCur<>nildo       // Проход по списку и поиск места вставки beginifPNew.Key>PCur.KeythenPCur := PCur.PNext // Следующий элемент elsebegin// надо вставлять в середину PNew.PNext := PCur.PNext; PCur.PNext := PNew;       // Обмен информационных полей PCurи PNew. exit; // Завершение алгоритма. end; end;// Новый элемент требуется включить в конец списка. AddToEnd(PList, PNew); end; Конкатенация (объединение) двух списков Алгоритм объединения двух списков основывается, практически, на двух рассмотренных выше алгоритмах: алгоритме прохода по списку и алгоритму добавления элемента в конец списка. Пусть у нас есть список 1 и список 2. Необходимо к списку 1 присоединить список 2. Рассматриваемый алгоритм можно сформулировать следующим образом: 1. Если список 1 пустой, то занести ссылку на первый элемент списка 2 в указатель списка 1. Завершить алгоритм. 2. Если список 2 пустой, то завершить алгоритм. 3. Используя алгоритм прохода по списку найти последний элемент в списке 1. 4. Использовать алгоритм включения элемента в конец списка 1. В качестве включаемого списка выбрать ссылку на первый элемент списка 2 из указателя на начало списка 2. 5. Если необходимо присвоить указателю на начало списка 2 значение nil. Программная реализация данного алгоритма может выглядеть следующим образом: Procedure ConcatLists(var PList1,PList2 :PTEl); varPCur : PTEl; begin if PList1=nil then begin PList1 := PList2; PList2 := nil; exit; end; if PList2=nil then exit; PCur     := PList1; while    PCur.PNext<>nil  do       PCur := PCur.PNext; AddToEnd(PList1, PCur); PList2 := nil; end; Удаление элемента Характерной особенностью при удалении элемента является то, что не достаточно просто исключить элемент из списка. Необходимо освободить память, зарезервированную для хранения этого элемента. Иначе, в общем случае, теряется сама возможность доступа к этому участку памяти, этот участок памяти остается захваченным и не сможет больше использоваться до завершения программы. При удалении элемента из линейного списка необходимо также как и при добавлении элемента учитывать относительное положение удаляемого элемента. Удаление элемента из начала списка При удалении элемента из начала списка необходимо в указатель на начало списка занести ссылку на элемент, следующий за первым и освободить память, отведенную для хранения удаляемого элемента. Алгоритм удаления элемента из начала списка выглядит следующим образом: 1. Если список пустой, то завершить алгоритм. 2. Выбрать из первого элемента ссылку на следующий и занести ее в указатель на начало списка. 3. Освободить память, зарезервированную под элемент, бывший первым. Приведем программную реализацию этого алгоритма. procedureDeleteOfBegining(varPList:PTEl); var  PCur     : PTEl; begin ifPList=nil      then     exit; PCur :=PList; PList         :=PCur.PNext; FreeMem(PCur); end; Следует обратить внимание на то, что если список состоит из одного элемента, то приведенный алгоритм корректен. Действительно, в этом случае ссылка из первого (и единственного) элемента на следующий содержит указание на то, что дальнейших элементов в списке нет. И именно эта ссылка помещается в указатель на начало списка. Следовательно, указатель на начало списка будет содержать указание на то, что дальнейших элементов в списке нет. А это и есть свидетельство факта, что список стал пустой. Удаление последнего элемента списка. Алгоритм удаления последнего элемента из двухсвязного списка не содержит никаких новых особенностей и поэтому нет смысла останавливаться на нем подробно. Немногим более сложен алгоритм удаления последнего элемента списка в случае односвязного списка. Особенность его состоит в том что, перебирая элементы последовательно, при достижении последнего элемента у нас отсутствует ссылка на предыдущий, который теперь должен стать последним. Существуют различные подходы к решению этой проблемы, но все из них основаны на том, чтобы тем или иным образом существовали ссылки на два последовательно расположенных элемента списка. Наиболее популярный среди начинающих является алгоритм, базирующийся на непосредственном сохранении ссылки на предыдущий элемент. Его недостаток в том, что в этом случае для первого элемента не существует предыдущего элемента и поэтому в алгоритм необходимо вводить особую обработку первого элемента, что, естественно, усложняет алгоритм. Приведем алгоритм лишенный указанного недостатка и основанный не на запоминании предыдущего элемента, а наоборот на «заглядывании» вперед на следующий элемент.

1. Если список пустой, то завершить алгоритм.
2. Выбрать первый элемент в качестве текущего элемента.
3. Проверить ссылку в следующем элементе на то, что он не последний. 3.1. Если это не последний элемент, то выбрать в качестве текущего следующий элемент и перейти к пункту 3. 3.2. Если этот элемент последний, то: 3.2.1. Освободить память, занимаемую последним элементом. 3.2.2. Занести в ссылку текущего элемента на следующий признак окончания списка.

Программная реализация алгоритма может выглядеть следующим образом: procedureDeleteOfLastElement (PList : PTEl); var PEl   : PTEl; begin ifPList=nil               then     exit; ifPList.PNext=nil then begin DeleteOfBegining(PList); exit; end; PEl :=PList; while (PEl.PNext).PNext<>nil       do       PEl := PEl.PNext; FreeMem(PEl.PNext); PEl.PNext := nil; end; Удаление элемента из середины списка Удаление элемента из середины списка наиболее характерная операция при работе с упорядоченными списками. Поэтому рассмотрим алгоритм удаления элемента с заданным значением ключа из упорядоченного однонаправленного списка. Алгоритм является объединением фрагментов рассмотренных выше алгоритмов.

1. Если список пустой, то завершить алгоритм.
2. Выбрать первый элемент в качестве текущего элемента.
3. Сравнить значение заданного ключа с ключом текущего (первого) элемента. 3.1. Если значения ключей совпадают, то удалить текущий элемент в соответствии с алгоритмом удаления первого элемента. 3.2. Завершить работу алгоритма.
4. Если значения ключей не совпадают проверить, не является ли текущий элемент последним. 4.1. Если текущий элемент последний, то искомый элемент отсутствует в списке. 4.2. Завершить работу алгоритма.
5. Если текущий элемент не последний, сравнить значение ключа элемента следующего за текущим с заданным. 5.1. Если значения совпадают, то следующий элемент должен быть удален. Занести в текущий элемент в качестве ссылки на следующий ссылку, хранимую в следующем элементе. 5.2. Освободить зарезервированную память под следующий элемент. 5.3. Завершить работу алгоритма.
6. Выбрать следующий элемент в качестве текущего элемента. Перейти к пункту 4.

Программная реализация алгоритма может выглядеть следующим образом: procedureDeleteOfElementFromList (varPList:PTEl; Key:integer); var PEl :PTEl; PElDel :PTEl; begin ifPList=nil then exit; PEl := PList; If PEl.Key=Key then begin DeleteOfBegining(PList); exit; end; while PEl.PNext<>nil do begin if (PEl.PNext).Key=Key then begin // Найден элемент для удаления PElDel :=PEl.PNext; PEl.PNext := PElDel.PNext; FreeMem(PElDel); Exit; end; PEl := PEl.PNext; end; end; Удаление части списка Алгоритм удаления части списка является суперпозицией выше описанных алгоритмов. Например, если задача сформулирована как удалить 3 элемента начиная с 5-го, то алгоритм может выглядеть следующим образом:

• Используя алгоритм прохода по списку найти третий элемент.
• Используя алгоритм удаления первого элемента удалить пять элементов.

В качестве указателя на начало списка используется элемент PNext третьего элемента. Программная реализация в этом случае не имеет никаких новых принципиальных особенностей и поэтому нет смысла не ней останавливаться. Удаление списка Алгоритм удаления списка может быть составлен из выше описанных алгоритмов. Например, удаление первого элемента списка до того момента, пока список не пустой. Разбиение списка на два различных списка Задача разбиения списка на два различных списка может быть сформулирована различными способами. Например, разделить упорядоченный список на два. В первом из них должны быть элементы со значением ключевого поля меньше заданного, а во втором оставшиеся элементы. Или разделить список на два списка, причем количество элементов в каждом из списков не должно отличаться больше чем на единицу. Или разделить список на два списка, так чтобы в первом количество элементов не превышало заданной величины. Можно еще придумать целый ряд подобных задач. Но давайте попытаемся выделить и формализовать некоторые общие положения. Видно, что во всех перечисленных задачах встречается такая операция как поиск элемента, начиная с которого последующие элементы должны быть помещены в новый список. Далее все последующие элементы перемещаются в новый список. Таким образом, во всех задачах существует подзадача определения граничного элемента, начиная с которого элементы должны быть перемещены во второй список. Отсюда вытекает следующий алгоритм:

• Используя алгоритм прохода по списку найти граничный элемент, являющийся последним для первого списка.
• Занести в указатель на начало второго списка ссылку на элемент, следующий за граничным элементом.
• Удалить ссылку на следующий элемент в граничном элементе.

Программная реализация не содержит никаких новых принципиальных решений по сравнению с разобранными ранее. Сортировка элементов списка Операция сортировки списков периодически встречается в практике. Обычно первое движение в этом случае начинающих программистов — подобрать алгоритм сортировки по аналогии с алгоритмами сортировки массивов. Наиболее часто высказываемое предложение — «Давайте используем алгоритм сортировки пузырьком». Но при этом упускается из внимания тот важнейший факт, что в массиве мы имеем прямой доступ к элементам, а в списке — последовательный. И это обстоятельство кардинально изменяет ситуацию в худшую сторону. Во-первых, сам алгоритм будет не очень простым, во-вторых, с возрастанием количества элементов в списке катастрофически возрастает время выполнения. Наиболее эффективный алгоритм сортировки элементов в списке состоит в создании нового списка из существующего. При этом новый список строится сразу же как упорядоченный. Т.е. алгоритм сортировки элементов является суперпозицией алгоритмов прохода по списку (исходного списка), включения элемента в упорядоченный список (создаваемый список) и удаление первого элемента из списка (исходного списка).