Основные алгоритмы работы со списками

Размещено на http://www.allbest.ru/

Содержание

Введение

1. Связные линейные списки

2. Машинное представление связных линейных списков

3. Структура двухсвязного списка

4. Реализация операций над связными линейными списками

5. Применение линейных списков

6. Мультисписки

7. Нелинейные разветвленные списки

8. Операции обработки списков

Заключение

Список литературы

Введение

Статическими величинами называются такие, память под которые выделяется во время компиляции и сохраняется в течение всей работы программы. В языках программирования (Pascal, C, др.) существует и другой способ выделения памяти под данные, который называется динамическим. В этом случае память под величины отводится во время выполнения программы. Такие величины будем называть динамическими. Раздел оперативной памяти, распределяемый статически, называется статической памятью; динамически распределяемый раздел памяти называется динамической памятью (динамически распределяемой памятью). Использование динамических величин предоставляет программисту ряд дополнительных возможностей. Во-первых, подключение динамической памяти позволяет увеличить объем обрабатываемых данных. Во-вторых, если потребность в каких-то данных отпала до окончания программы, то занятую ими память можно освободить для другой информации. В-третьих, использование динамической памяти позволяет создавать структуры данных переменного размера. Работа с динамическими величинами связана с использованием еще одного типа данных -- ссылочного типа. Величины, имеющие ссылочный тип, называют указателями. Указатель содержит адрес поля в динамической памяти, хранящего величину определенного типа. Сам указатель располагается в статической памяти. Благодаря многим преимуществам, которые дает использование динамических структур, такой способ хранения данных повсеместно используется в программировании. Данная тема является особенно актуальной, поскольку в настоящее время невозможно написание функциональных программ без использования динамических структур. Для построения программ, с оптимизированным использованием памяти, необходимо уметь легко оперировать с динамическими структурами и использовать правильный подход к выбору метода решения задачи. Всё это говорит о том, что изучение этой темы является необходимостью. Целью данной работы является изучение динамических структур данных на конкретном примере связных списков, научиться оперировать с типами данных, использующими динамическую память.

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

1. Связные линейные списки

Списком называется упорядоченное множество, состоящее из переменного числа элементов, к которым применимы операции включения, исключения. Список, отражающий отношения соседства между элементами, называется линейным. Если ограничения на длину списка не допускаются, то список представляется в памяти в виде связной структуры. Линейные связные списки являются простейшими динамическими структурами данных.

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

2. Машинное представление связных линейных списков

список алгоритм программа

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

Однако, обработка односвязного списка не всегда удобна, так как отсутствует возможность продвижения в противоположную сторону. Такую возможность обеспечивает двухсвязный список, каждый элемент которого содержит два указателя: на следующий и предыдущий элементы списка. Структура линейного двухсвязного списка приведена на рисунке где поле NEXT - указатель на следующий элемент, поле PREV - указатель на предыдущий элемент. В крайних элементах соответствующие указатели должны содержать nil, как и показано на рисунке.

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

3. Структура двухсвязного списка

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

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



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

4. Реализация операций над связными линейными списками

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

В программных примерах подразумеваются определенными следующие типы данных:

любая структура информационной части списка:

type data = ...;

элемент односвязного списка (sll - single linked list):

type

sllptr = ^slltype; { указатель в односвязном списке }

slltype = record { элемент односвязного списка }

inf : data; { информационная часть }

next : sllptr; { указатель на следующий элемент }

end;

элемент двухсвязного списка (dll - double linked list):

type

dllptr = ^dlltype; { указатель в двухсвязном списке }

dlltype = record { элемент односвязного списка }

inf : data; { информационная часть }

next : sllptr; { указатель на следующий элемент (вперед) }

prev : sllptr; { указатель на предыдущий элемент (назад) }

end;

Перебор элементов списка.

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

Алгоритм перебора для односвязного списка представляется программным примером

{==== Программный пример ====}

{ Перебор 1-связного списка }

Procedure LookSll(head : sllptr);

{ head - указатель на начало списка }

var cur : sllptr; { адрес текущего элемента }

begin

cur:=head; { 1-й элемент списка назначается текущим }

while cur <> nil do begin

< обработка c^.inf >

{обрабатывается информационная часть того эл-та,

на который указывает cur.

Обработка может состоять в:

· печати содержимого инф.части;

· модификации полей инф.части;

· сравнения полей инф.части с образцом при поиске по ключу;

· подсчете итераций цикла при поиске по номеру;

cur:=cur^.next;

{ из текущего эл-та выбирается указатель на следующий эл-т и для следующей итерации следующий эл-т становится текущим; если текущий эл-т был последний, то его поле next содержит пустой указатель и, т.обр. в cur запишется nil, что приведет к выходу из цикла при проверке условия while } end; end;

В двухсвязном списке возможен перебор как в прямом направлении (он выглядит точно так же, как и перебор в односвязном списке), так и в обратном. В последнем случае параметром процедуры должен быть tail - указатель на конец списка, и переход к следующему элементу должен осуществляться по указателю назад: cur:=cur^.prev;

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

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

{==== Программный пример ====}

{ Вставка элемента в середину 1-связного списка }

Procedure InsertSll(prev : sllptr; inf : data);

{ prev - адрес предыдущего эл-та; inf - данные нового эл-та }

var cur : sllptr; { адрес нового эл-та }

begin

{ выделение памяти для нового эл-та и запись в его инф.часть }

New(cur); cur^.inf:=inf;

cur^.next:=prev^.next; { эл-т, следовавший за предыдущим теперь

будет следовать за новым }

prev^.next:=cur; { новый эл-т следует за предыдущим }

end;

Рисунок представляет вставку в двухсвязный список.

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

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

{==== Программный пример ====}

{ Вставка элемента в любое место 1-связного списка }

Procedure InsertSll

var head : sllptr; { указатель на начало списка, может измениться в

процедуре, если head=nil - список пустой }

prev : sllptr; { указатель на эл-т, после к-рого делается вставка,

если prev-nil - вставка перед 1-ым эл-том }

inf : data { - данные нового эл-та }

var cur : sllptr; { адрес нового эл-та }

begin

{ выделение памяти для нового эл-та и запись в его инф.часть }

New(cur); cur^.inf:=inf;

if prev <> nil then begin { если есть предыдущий эл-т - вставка в

середину списка, см. прим.5.2 }

cur^.next:=prev^.next; prev^.next:=cur;

end

else begin { вставка в начало списка }

cur^.next:=head; { новый эл-т указывает на бывший 1-й эл-т списка;

если head=nil, то новый эл-т будет и последним эл-том списка }

head:=cur; { новый эл-т становится 1-ым в списке, указатель на

начало теперь указывает на него }

end; end;

Удаление элемента из списка.

Удаление элемента из односвязного списка показано на рисунке



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

{==== Программный пример ====}

{ Удаление элемента из любого места 1-связного списка }

Procedure DeleteSll(

var head : sllptr; { указатель на начало списка, может

измениться в процедуре }

del : sllptr { указатель на эл-т, к-рый удаляется } );

var prev : sllptr; { адрес предыдущего эл-та }

begin

if head=nil then begin { попытка удаления из пустого списка

асценивается как ошибка (в последующих примерах этот случай

учитываться на будет) }

Writeln('Ошибка!'); Halt;

end;

if del=head then { если удаляемый эл-т - 1-й в списке, то

следующий за ним становится первым }

head:=del^.next

else begin { удаление из середины списка }

{ приходится искать эл-т, предшествующий удаляемому; поиск производится перебором списка с самого его начала, пока не будет найдет эл-т, поле next к-рого совпадает с адресом удаляемого элемента }

prev:=head^.next;

while (prev^.next<>del) and (prev^.next<>nil) do

prev:=prev^.next;

if prev^.next=nil then begin

{ это случай, когда перебран весь список, но эл-т не найден, он отсутствует в списке; расценивается как ошибка (в последующих примерах этот случай учитываться на будет) }

Writeln('Ошибка!'); Halt;

end;

prev^.next:=del^.next; { предыдущий эл-т теперь указывает

на следующий за удаляемым }

end;

{ элемент исключен из списка, теперь можно освободить

занимаемую им память }

Dispose(del);

end;

Удаление элемента из двухсвязного списка требует коррекции большего числа указателей, как показано на рисунке.

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

Перестановка элементов списка.

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

{==== Программный пример ====}

{ Перестановка двух соседних элементов в 1-связном списке }

Procedure ExchangeSll(

prev : sllptr { указатель на эл-т, предшествующий

переставляемой паре } );

var p1, p2 : sllptr; { указатели на эл-ты пары }

begin

p1:=prev^.next; { указатель на 1-й эл-т пары }

p2:=p1^.next; { указатель на 2-й эл-т пары }

p1^.next:=p2^.next; { 1-й элемент пары теперь указывает на

следующий за парой }

p2^.next:=p1; { 1-й эл-т пары теперь следует за 2-ым }

prev^.next:=p2; { 2-й эл-т пары теперь становится 1-ым }

end;

В процедуре перестановки для двухсвязного списка (рис.5.10.) нетрудно учесть и перестановку в начале/конце списка.

Копирование части списка.

При копировании исходный список сохраняется в памяти, и создается новый список. Информационные поля элементов нового списка содержат те же данные, что и в элементах старого списка, но поля связок в новом списке совершенно другие, поскольку элементы нового списка расположены по другим адресам в памяти. Существенно, что операция копирования предполагает дублирование данных в памяти. Если после создания копии будут изменены данные в исходном списке, то изменение не будет отражено в копии и наоборот.

Копирование для односвязного списка показано в программном примере.

{==== Программный пример ====}

{ Копирование части 1-связного списка. head - указатель на

начало копируемой части; num - число эл-тов. Ф-ция возвращает

указатель на список-копию }

Function CopySll ( head : sllptr; num : integer) : sllptr;

var cur, head2, cur2, prev2 : sllptr;

begin

if head=nil then { исходный список пуст - копия пуста }

CopySll:=nil

else begin

cur:=head; prev2:=nil;

{ перебор исходного списка до конца или по счетчику num }

while (num>0) and (cur<>nil) do begin

{ выделение памяти для эл-та выходного списка и запись в него

информационной части }

New(cur2); cur2^.inf:=cur^.inf;

{ если 1-й эл-т выходного списка - запоминается указатель на

начало, иначе - записывается указатель в предыдущий элемент }

if prev2<>nil then prev2^.next:=cur2 else head2:=cur2;

prev2:=cur2; { текущий эл-т становится предыдущим }

cur:=cur^.next; { продвижение по исходному списку }

num:=num-1; { подсчет эл-тов }

end;

cur2^.next:=nil; { пустой указатель - в последний эл-т

выходного списка }

CopySll:=head2; { вернуть указатель на начало вых.списка }

end; end;

Слияние двух списков.

Операция слияния заключается в формировании из двух списков одного - она аналогична операции сцепления строк. В случае односвязного списка, показанном в примере

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

{==== Программный пример ====}

{ Слияние двух списков. head1 и head2 - указатели на начала

списков. На результирующий список указывает head1 }

Procedure Unite (var head1, head2 : sllptr);

var cur : sllptr;

begin { если 2-й список пустой - нечего делать }

if head2<>nil then begin

{ если 1-й список пустой, выходным списком будет 2-й }

if head1=nil then head1:=head2

else { перебор 1-го списка до последнего его эл-та }

begin cur:=head1;

while cur^.next<>nil do cur:=cur^.next;

{ последний эл-т 1-го списка указывает на начало 2-го }

cur^.next:=head2;

end; head2:=nil; { 2-й список аннулируется }

end; end;

5. Применение линейных списков

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

В программном примере показана организация стека на односвязном линейном списке. Стек представляется как линейный список, в котором включение элементов всегда производятся в начала списка, а исключение - также из начала. Для представления его нам достаточно иметь один указатель - top, который всегда указывает на последний записанный в стек элемент. В исходном состоянии (при пустом стеке) указатель top - пустой. Процедуры StackPush и StackPop сводятся к включению и исключению элемента в начало списка. Обратите внимание, что при включении элемента для него выделяется память, а при исключении - освобождается. Перед включением элемента проверяется доступный объем памяти, и если он не позволяет выделить память для нового элемента, стек считается заполненным. При очистке стека последовательно просматривается весь список и уничтожаются его элементы. При списковом представлении стека оказывается непросто определить размер стека. Эта операция могла бы потребовать перебора всего списка с подсчета числа элементов. Чтобы избежать последовательного перебора всего списка мы ввели дополнительную переменную stsize, которая отражает текущее число элементов в стеке и корректируется при каждом включении/исключении.

{==== Программный пример====}

{ Стек на 1-связном линейном списке }

unit Stack;

Interface

type data = ...; { эл-ты могут иметь любой тип }

Procedure StackInit;

Procedure StackClr;

Function StackPush(a : data) : boolean;

Function StackPop(Var a : data) : boolean;

Function StackSize : integer;

Implementation

type stptr = ^stit; { указатель на эл-т списка }

stit = record { элемент списка }

inf : data; { данные }

next: stptr; { указатель на следующий эл-т }

end;

Var top : stptr; { указатель на вершину стека }

stsize : longint; { размер стека }

{** инициализация - список пустой }

Procedure StackInit;

begin top:=nil; stsize:=0; end; { StackInit }

{** очистка - освобождение всей памяти }

Procedure StackClr;

var x : stptr;

begin { перебор эл-тов до конца списка и их уничтожение }

while top<>nil do

begin x:=top; top:=top^.next; Dispose(x); end;

stsize:=0;

end; { StackClr }

Function StackPush(a: data) : boolean; { занесение в стек }

var x : stptr;

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

if MaxAvail < SizeOf(stit) then StackPush:=false

else { выделение памяти для эл-та и заполнение инф.части }

begin New(x); x^.inf:=a;

{ новый эл-т помещается в голову списка }

x^.next:=top; top:=x;

stsize:=stsize+1; { коррекция размера }

StackPush:=true;

end;

end; { StackPush }

Function StackPop(var a: data) : boolean; { выборка из стека }

var x : stptr;

begin

{ список пуст - стек пуст }

if top=nil then StackPop:=false

else begin

a:=top^.inf; { выборка информации из 1-го эл-та списка }

{ 1-й эл-т исключается из списка, освобождается память }

x:=top; top:=top^.next; Dispose(top);

stsize:=stsize-1; { коррекция размера }

StackPop:=true;

end; end; { StackPop }

Function StackSize : integer; { определение размера стека }

begin StackSize:=stsize; end; { StackSize }

END.

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

Линейные связные списки иногда используются также для представления таблиц - в тех случаях, когда размер таблицы может существенно изменяться в процессе ее существования. Однако, то обстоятельство, что доступ к элементам связного линейного списка может быть только последовательным, не позволяет применить к такой таблице эффективный двоичный поиск, что существенно ограничивает их применимость. Поскольку упорядоченность такой таблицы не может помочь в организации поиска, задачи сортировки таблиц, представленных линейными связными списками, возникают значительно реже, чем для таблиц в векторном представлении. Однако, в некоторых случаях для таблицы, хотя и не требуется частое выполнение поиска, но задача генерации отчетов требует расположения записей таблицы в некотором порядке. Для упорядочения записей такой таблицы применимы любые алгоритмы из описанных нами в разделе 3.9. Некоторые алгоритмы, возможно, потребуют каких-либо усложнений структуры, например, быструю сортировку Хоара целесообразно проводить только на двухсвязном списке, в цифровой сортировке удобно создавать промежуточные списке для цифровых групп и т.д. Мы приведем два простейших примера сортировки односвязного линейного списка. В обоих случаях мы предполагаем, что определены типы данных:

type lptr = ^item; { указатель на элемент списка }

item = record { элемент списка }

key : integer; { ключ }

inf : data; { данные }

next: lptr; { указатель на элемент списка }

end;

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

Указатель newh является указателем на начало выходного списка, исходно - пустого. Во входном списке ищется максимальный элемент. Найденный элемент исключается из входного списка и включается в начало выходного списка. Работа алгоритма заканчивается, когда входной список станет пустым. Обратим внимание читателя на несколько особенностей алгоритма. Во-первых, во входном списке ищется всякий раз не минимальный, а максимальный элемент. Поскольку элемент включается в начало выходного списка ,элементы с большими ключами оттесняются к концу выходного списка и последний, таким образом, оказывается отсортированным по возрастанию ключей. Во-вторых, при поиске во входном списке сохраняется не только адрес найденного элемента в списке, но и адрес предшествующего ему в списке эле- мента - это впоследствии облегчает исключение элемента из списка.

{==== Программный пример====}

{ Сортировка выборкой на 1-связном списке }

Function Sort(head : lptr) : lptr;

var newh, max, prev, pmax, cur : lptr;

begin newh:=nil; { выходной список - пустой }

while head<>nil do { цикл, пока не опустеет входной список }

begin max:=head; prev:=head; { нач.максимум - 1-й эл-т }

cur:=head^.next; { поиск максимума во входном списке }

while cur<>nil do begin

if cur^.key>max^.key then begin

{ запоминается адрес максимума и адрес предыдущего эл-та }

max:=cur; pmax:=prev;

end; prev:=cur; cur:=cur^.next; { движение по списку }

end; { исключение максимума из входного списка }

if max=head then head:=head^.next

else pmax^.next:=max^.next;

{ вставка в начало выходного списка }

max^.next:=newh; newh:=max;

end; Sort:=newh;

end;

В программном примере - иллюстрации сортировки вставками - из входного списка выбирается (и исключается) первый элемент и вставляется в выходной список "на свое место" в соответствии со значениями ключей.

{==== Программный пример ====}

{ Сортировка вставками на 1-связном списке }

type data = integer;

Function Sort(head : lptr) : lptr;

var newh, cur, sel : lptr;

begin

newh:=nil; { выходной список - пустой }

while head <> nil do begin { цикл, пока не опустеет входной список }

sel:=head; { эл-т, который переносится в выходной список }

head:=head^.next; { продвижение во входном списке }

if (newh=nil) or (sel^.key < newh^.key) then begin

{выходной список пустой или элемент меньше 1-го-вставка в начало}

sel^.next:=newh; newh:=sel; end

else begin { вставка в середину или в конец }

cur:=newh;

{ до конца выходного списка или пока ключ следующего эл-та не будет

больше вставляемого }

while (cur^.next <> nil) and (cur^.next^.key < sel^.key) do

cur:=cur^.next;

{ вставка в выходной список после эл-та cur }

sel^.next:=cur^.next; cur^.next:=sel;

end; end; Sort:=newh;

end;

6. Мультисписки

В программных системах, обрабатывающих объекты сложной структуры, могут решаться разные подзадачи, каждая из которых требует, возможно, обработки не всего множества объектов, а лишь какого-то его подмножества. Так, например, в автоматизированной системе учета лиц, пострадавших вследствие аварии на ЧАЭС, каждая запись об одном пострадавшем содержит более 50 полей в своей информационной части. Решаемые же автоматизированной системой задачи могут потребовать выборки, например:

участников ликвидации аварии;

переселенцев из зараженной зоны;

лиц, состоящих на квартирном учете;

лиц с заболеваниями щитовидной железы;

и т.д., и т.п.

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

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

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

7. Нелинейные разветвленные списки

Основные понятия

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

В обработке нелинейный список определяется как любая последовательность атомов и списков (подсписков), где в качестве атома берется любой объект, который при обработке отличается от списка тем, что он структурно неделим.

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

(a,(b,c,d),e,(f,g))

((a))

Первый список содержит четыре элемента: атом a, список (b,c,d) (содержащий в свою очередь атомы b,c,d), атом e и список (f,g), элементами которого являются атомы f и g. Второй список не содержит элементов, тем не менее нулевой список, в соответствии с нашим определением является действительным списком. Третий список состоит из одного элемента: списка (a), который в свою очередь содержит атом а.

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

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

Порядок. Над элементами списка задано транзитивное отношение, определяемое последовательностью, в которой элементы появляются внутри списка. В списке (x,y,z) атом x предшествует y, а y предшествует z. При этом подразумевается, что x предшествует z. Данный список не эквивалентен списку (y,z,x). При представлении списков графическими схемами порядок определяется горизонтальными стрелками. Горизонтальные стрелки истолковываются следующим образом: элемент из которого исходит стрелка,предшествует элементу, на который она указывает.

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

Длина - это число элементов уровня 1 в списке.

Пример применения разветвленного списка - представление последнего алгебраического выражения в виде списка. Алгебраическое выражение можно представить в виде последовательности элементарных двухместных операций вида: < операнд 1 > < знак операции > < операнд 2 >

Выражение:

(a+b)*(c-(d/e))+f

будет вычисляться в следующем порядке:

a+b

d/e

c-(d/e)

(a+b)*(c-d/e)

(a+b)*(c-d/e)+f



При представлении выражения в виде разветвленного списка каждая тройка "операнд-знак-операнд" представляется в виде списка, причем, в качестве операндов могут выступать как атомы - переменные или константы, так и подсписки такого же вида. Скобочное представление нашего выражения будет иметь вид: (((a,+,b),*,(c,-,(d,/,e)),+,f)

Глубина этого списка равна 4, длина - 3.

Представление списковых структур в памяти.

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

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

Поле type содержат признак атом/узел, оно может быть 1-битовым. Такой формат элемента удобен для списков, атомарная информация которых занимает небольшой объем памяти. В этом случае теряется незначительный объем памяти в элементах списка, для которых не требуется поля data. В более общем случае для атомарной информации необходим относительно большой объем памяти.

В этом случае указатель down указывает на данные или на подсписок. Поскольку списки могут составляться из данных различных типов, целесообразно адресовать указателем down не непосредственно данные, а их дескриптор, в котором может быть описан тип данных, их длина и т.п. Само описание того, является ли адресуемый указателем данных объект атомом или узлом также может находиться в этом дескрипторе. Удобно сделать размер дескриптора данных таким же, как и элемента списка. В этом случае размер поля type может быть расширен, например, до 1 байта и это поле может индицировать не только атом/подсписок, но и тип атомарных данных, поле next в дескрипторе данных может использоваться для представления еще какой-то описательной информации, например, размера атома. На рисунке показано представление элементами такого формата списка: (КОВАЛЬ,(12,7,53),d). Первая (верхняя) строка на рисунке представляет элементы списка, вторая - элементы подсписка, третья - дескрипторы данных, четвертая - сами данные. В поле type каждого элемента мы использовали коды: n - узел, S - атом, тип STRING, I - атом, тип INTEGER, C - атом, тип CHAR.

8. Операции обработки списков

Базовыми операциями при обработке списков являются операции (функции): car, cdr, cons и atom.

Операция car в качестве аргумента получает список (указатель на начало списка). Ее возвращаемым значением является первый элемент этого списка (указатель на первый элемент). Например:

· если X - список (2,6,4,7), то car(X) - атом 2;

· если X - список ((1,2),6), то car(X) - список (1,2);

· если X - атом то car(X) не имеет смысла и в действительности не определено.

Операция cdr в качестве аргумента также получает список. Ее возвращаемым значением является остаток списка - указатель на список после удаления из него первого элемента. Например:

· если X - (2,6,4), то cdr(X) - (6,4);

· если X - ((1,2),6,5), то cdr(X) - (6,5);

· если список X содержит один элемент, то cdr(X) равно nil.

Операция cons имеет два аргумента: указатель на элемент списка и указатель на список. Операция включает аргумент-элемент в начало аргумента-списка и возвращает указатель на получившийся список. Например:

· если X - 2, а Y - (6,4,7), то cons(X,Y) - (2,6,4,7);

· если X - (1,2), Y - (6,4,7), то cons(X,Y) - ((1,2),6,4,7).

Операция atom выполняет проверку типа элемента списка. Она должна возвращать логическое значение: true - если ее аргумент является атомом или false - если ее аргумент является подсписком.

В программном примере приведена реализация описанных операций как функций языка PASCAL. Структура элемента списка, обрабатываемого функциями этого модуля определена в нем как тип litem и полностью соответствует рисунку .Помимо описанных операций в модуле определены также функции выделения памяти для дескриптора данных - NewAtom и для элемента списка - NewNode. Реализация операций настолько проста, что не требует дополнительных пояснений.

{==== Программный пример ====}

{ Элементарные операции для работы со списками }

Unit ListWork;

Interface

type lpt = ^litem; { указатель на элемент списка }

litem = record

typeflg : char; { Char(0) - узел, иначе - код типа }

down : pointer; { указатель на данные или на подсписок }

next: lpt; { указатель на текущем уровне }

end;

Function NewAtom(d: pointer; t : char) : lpt;

Function NewNode(d: lpt) : lpt;

Function Atom(l : lpt) : boolean;

Function Cdr(l : lpt) : lpt;

Function Car(l : lpt) : lpt;

Function Cons(l1, l : lpt) : lpt;

Function Append(l1,l : lpt) : lpt;

Implementation

{*** создание дескриптора для атома }

Function NewAtom(d: pointer; t : char) : lpt;

var l : lpt;

begin New(l);

l^.typeflg:=t; { тип данных атома }

l^.down:=d; { указатель на данные }

l^.next:=nil; NewAtom:=l;

end;

{*** создание элемента списка для подсписка }

Function NewNode(d: lpt) : lpt;

var l : lpt;

begin

New(l);

l^.typeflg:=Chr(0); { признак подсписка }

l^.down:=d; { указатель на начало подсписка }

l^.next:=nil;

NewNode:=l;

end;

{*** проверка элемента списка: true - атом, false - подсписок }

Function Atom(l : lpt) : boolean;

begin { проверка поля типа }

if l^.typeflg=Chr(0) then Atom:=false

else Atom:=true;

end;

Function Car(l : lpt) : lpt; {выборка 1-го элемента из списка }

begin Car:=l^.down; { выборка - указатель вниз } end;

Function Cdr(l : lpt) : lpt;{исключение 1-го элемента из списка}

begin Cdr:=l^.next; { выборка - указатель вправо } end;

{*** добавление элемента в начало списка }

Function Cons(l1,l : lpt) : lpt;

var l2 : lpt;

begin l2:=NewNode(l1); { элемент списка для добавляемого }

l2^.next:=l; { в начало списка }

Cons:=l2; { возвращается новое начало списка }

end;

{*** добавление элемента в конец списка }

Function Append(l1,l : lpt) : lpt;

var l2, l3 : lpt;

begin

l2:=NewNode(l1); { элемент списка для добавляемого }

{ если список пустой - он будет состоять из одного эл-та }

if l=nil then Append:=l2

else begin { выход на последний эл-т списка }

l3:=l; while l3^.next <> nil do l3:=l3^.next;

l3^.next:=l2; { подключение нового эл-та к последнему }

Append:=l; { функция возвращает тот же указатель }

end; end;

END.

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

{==== Программный пример ====}

{ Вторичные функции обработки списков }

Unit ListW1;

Interface

uses listwork;

Function Append(x, l : lpt) : lpt;

Function ListRev(l, q : lpt) : lpt;

Function FlatList(l, q : lpt) : lpt;

Function InsList(x, l : lpt; m : integer) : lpt;

Function DelList(l : lpt; m : integer) : lpt;

Function ExchngList(l : lpt; m : integer) : lpt;

Implementation

{*** добавление в конец списка l нового элемента x }

Function Append(x, l : lpt) : lpt;

begin

{ если список пустой - добавить x в начало пустого списка }

if l=nil then Append:=cons(x,l)

{ если список непустой

- взять тот же список без 1-го эл-та - cdr(l);

- добавить в его конец эл-т x;

- добавить в начало 1-й эл-т списка }

else Append:=cons(car(l),Append(x,cdr(l)));

end; { Function Append }

{*** Реверс списка l; список q - результирующий, при первом

вызове он должен быть пустым }

Function ListRev(l, q : lpt) : lpt;

begin

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

if l=nil then ListRev:=q

{ иначе: - добавить 1-й эл-т вх.списка в начало вых.списка,

- реверсировать, имея вх. список без 1-го эл-та, а вых.список

- с добавленным эл-том }

else ListRev:=ListRev(cdr(l),cons(car(l),q));

end; { Function ListRev }

{*** Превращение разветвленного списка l в линейный; список q

- результирующий, при первом вызове он должен быть пустым }

Function FlatList(l, q : lpt) : lpt;

begin

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

if l=nil then FlatList:=q

else

{ если 1-й эл-т вх. списка - атом, то

- сделать "плоской" часть вх. списка без 1-го эл-та;

- добавить в ее начало 1-й эл-т }

if atom(car(l)) then

FlatList:=cons(car(l),FlatList(cdr(l),q))

{ если 1-й эл-т вх. списка - подсписок, то

- сделать "плоской" часть вх.списка без 1-го эл-та;

- сделать "плоским" подсписок 1-го эл-та }

else FlatList:=FlatList(car(l),FlatList(cdr(l),q));

end; { Function FlatList }

{*** вставка в список l элемента x на место с номером m

( здесь и далее нумерация эл-тов в списке начинается с 0 ) }

Function InsList(x, l : lpt; m : integer) : lpt;

begin

{ если m=0, эл-т вставляется в начало списка }

if m=0 then InsList:=cons(x,l)

{ если список пустой, он и остается пустым }

else if l=nil then InsList:=nil

{ - вставить эл-т x на место m-1 в список без 1-го эл-та;

- в начало полученного списка вставить 1-й эл-т }

else InsList:=cons(car(l),InsList(x,cdr(l),m-1));

end; { Function InsList }

{*** удаление из списка l на месте с номером m }

Function DelList(l : lpt; m : integer) : lpt;

begin

{ если список пустой, он и остается пустым }

if l=nil then DelList:=nil

{ если m=0, эл-т удаляется из начала списка }

else if m=0 then DelList:=cdr(l)

{ - удалить эл-т x на месте m-1 в список без 1-го эл-та;

- в начало полученного списка вставить 1-й эл-т }

else DelList:=cons(car(l),DelList(cdr(l),m-1));

end; { Function DelList }

{*** перестановка в списке l эл-тов местах с номерами m и m+1 }

Function ExchngList(l : lpt; m : integer) : lpt;

begin { если список пустой, он и остается пустым }

if l=nil then ExchngList:=nil

else if m=0 then

{если m=0, а следующего эл-та нет, список остается без изменений}

if cdr(l)=nil then ExchngList:=l

{ если m=0 ( обмен 0-го и 1-го эл-тов):

- берется список без двух 1-ых эл-тов - cdr(cdr(l));

- в его начало добавляется 0-й эл-т;

- в начало полученного списка добавляется 1-й эл-т - car(cdr(l))}

else ExchngList:= cons(car(cdr(l)),cons(car(l),cdr(cdr(l))))

else ExchngList:=cons(car(l),ExchngList(cdr(l),m-1));

end; { Function ExchngList }

END.

Функция Append добавляет элемент x в конец списка 1 .

Поскольку аргумент-список не пустой, выполняется ветвь else. Она содержит оператор:

Append:=cons(car(l),Append(x,cdr(l)));

Важно точно представить себе последовательность действий по выполнению этого оператора:

· car(l) = 1;

· cdr(l) = (2,3);

· Append(4,(2,3))) - при этом рекурсивном вызове выполнение вновь пойдет по ветви else, в которой:

o car(l) = 2;

o cdr(l) = (3);

o Append(4,(3))) - выполнение вновь пойдет по ветви else, в которой:

§ car(l) = 3;

§ cdr(l) = nil;

§ Append(4,nil) - в этом вызове список-аргумент пустой, поэтому выполнится Append:=cons(4,nil) и вызов вернет список: (4);

§ cons(car(l),Append(x,cdr(l))) - значения аргументов функции cons - для этого уровня вызовов: cons(3,(4)) = (3,4);

§ на этом уровне Append возвращает список (3,4);

§ cons(car(l),Append(x,cdr(l))) - на этом уровне: cons(2,(3,4)) = (2,3,4);

§ на этом уровне Append возвращает список (2,3,4);

§ cons(car(l),Append(x,cdr(l))) - на этом уровне: cons(1,(2,3,4)) = (1,2,3,4);

§ на этом уровне Append возвращает список (1,2,3,4).

Функция ListRev выполняет инвертирование списка - изменения порядка следования его элементов на противоположный. При обращении к функции ее второй аргумент должен иметь значение nil. Пример: ListRev(1,(2,3),4),nil).

Входной список не пустой, поэтому выполнение идет по ветви else, где:

ListRev:=ListRev(cdr(l),cons(car(l),q));

Последовательность действий:

· cdr(l) = ((2,3),4);

· car(l) = 1;

· cons(car(l),q) = (1) - список q при этом - пустой;

· рекурсивный вызов ListRev( ((2,3),4), (1)):

o cdr(l) = (4);

o car(l) = (2,3);

o cons(car(l),q) = ((2,3),1) - список q - (1);

o рекурсивный вызов ListRev((4), ((2,3),1)):

§ cdr(l) = nil;

§ car(l) = 4;

§ cons(car(l),q) = (4,(2,3),1);

§ рекурсивный вызов ListRev(nil, (4,(2,3),1)):

§ поскольку исходный список пустой, вызов возвращает список: (4,(2,3),1);

§ вызов возвращает список: (4,(2,3),1);

o вызов возвращает список: (4,(2,3),1);

· вызов возвращает список: (4,(2,3),1).

Функция Creat_Lst преобразует исходную строку в список. В функции поэлементно анализируются символы строки. Различаемые символы: левая круглая скобка, правая скобка, знаки операций и цифры. Цифровые символы накапливаются в промежуточной строке. Когда встречается символ-разделитель - правая скобка или знак операции накопленная строка преобразуется в число, для него создается атом с типом 'I' и включается в конец списка. Для знака операции создается атом с типом 'C' и тоже включается в конец списка. Левая скобка приводит к рекурсивному вызову Creat_Lst. Этот вызов формирует список для подвыражения в скобках, формирование списка заканчивается при появлении правой скобки. Для сформированного таким образом списка создается узел, и он включается в основной список как подсписок.

Функция - FormPrty - выделяет в отдельные подсписки операции умножения и деления, имеющие более высокий приоритет, и их операнды. Функция просматривает список и выделяет в нем последовательные тройки элементов "операнд-знак-операнд". Если один из операндов является подсписком, то он обрабатывается функцией FormPrty. Если знак является одним из приоритетных знаков, то из тройки формируется подсписок, который становится первым операндом для следующей тройки. Если знак не приоритетный, то второй операнд тройки становится первым для следующей тройки.

Функция Eval выполняет вычисления. Она во многом похожа на функцию FormPrty: в ней также выделяются тройки "операнд 1- 0знак-операнд". Если один или оба операнда являются подсписками, то сначала вычисляются эти подсписки и заменяются на атомы - результаты вычисления. Если оба операнда - атомы, то над ними выполняется арифметика, задаваемая знаком операции. Поскольку в первую очередь вычисляются подсписки, то подвыражения, обозначенные скобками в исходной строке, и операции умножения и деления выполняются в первую очередь.

Заключение

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

Список литературы

1. Сайт http://algolist.ru

2. Сайт http://informatics.mccme.ru/

3. «Программирование в среде Turbo Pascal 7.0» Авторы: А. М. Епанешников, В. А. Епанешников Год: 1995. Страниц: 288

4. «Программирование на языке Pascal» Авторы: Рапаков Г. Г., Ржеуцкая С. Ю. Год издания: 2004

5. «Динамическое программирование» Авторы: Беллман Р., Энджел Э.

6. «Алгоритмы и программы» Авторы: Порублев Илья Николаевич, Ставровский Андрей Борисович

7. «Turbo Pascal: Учебник для вузов» Автор: С. Немюгин

8. «Pascal 7.0. Практическое программирование. Решение типовых задач» Автор: Л. Климова

Размещено на Allbest.ru

...