Динамические структуры данных

Односвязные списки

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

Рис. 1. Односвязный список из трёх элементов

Слово «односвязный» в названии этой структуры данных означает, что на каждый из его элементов указывает один указатель; впрочем, с тем же успехом можно отметить, что каждый элемент имеет одно поле, предназначенное для сохранения связности списка. Наконец, можно сказать, что в списке выстроена одна цепочка связей из указателей и списать «односвязность» на этот факт. Как мы увидим позже, все эти утверждения эквивалентны.

Пример односвязного списка из трёх элементов, содержащих целые числа 25,36,49, показан на рис.1. Для создания такого списка нам потребуется запись, состоящая из двух полей: первое будет хранить целое число, второе — адрес следующего звена списка. Здесь в Паскале имеется некая хитрость: использовать имя описываемого типа при описании его собственных полей нельзя, то есть мы не можем написать вот так:

type
  item = record
    data: integer;
    next: ^item;
  end;

При этом можно описать указательный тип, используя такое имя типа, которое пока еще не введено; как следствие, мы можем дать отдельное имя типу указателя на item до того, как опишем сам тип item, а при описании item воспользоваться этим именем, например:

type
  itemptr = ^item;
  item = record
    data: integer;
    next: itemptr;
  end;

Такое описание никаких возражений у компилятора не вызовет. Имея типы item и itemptr, мы можем описать указатель для работы со списком:

var
  first: itemptr;

ну а сам список, показанный на рисунке, можно создать, например так:

new(first);
first^.data := 25;
new(first^.next);
first^.next^.data := 36;
new(first^.next^.next);
first^.next^.next^.data := 49;
first^.next^.next^.next := nil;

Рис. 2. Навигация в односвязном списке

С непривычки конструкции вроде first^.next^.data могут напугать; это вполне нормальная реакция, но здесь нет ничего необычного, разберём что тут написано. Так как у нас указатель на первый элемент называется first, то выражение first^ будет обозначать весь этот элемент целиком. Поскольку сам этот элемент представляет собой запись из двух полей, доступ к полям, как и для любой записи, производится через точку и имя поля; таким образом, first^.data – это поле первого элемента, в котором содержится целое число (на рисунке это число 25), а first^.next – это указатель на следующий (второй) элемент списка. В свою очередь first^.next^ — это сам второй элемент списка, и так далее (см. рис. 2).

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

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

Написать программу, которая читает целые числа из потока стандартного ввода до возникновения ситуации «конец файла», после чего печатает все введённые числа в обратном порядке. Количество чисел заранее неизвестно, вводить явные ограничения на это количество запрещается.

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

Написать программу, которая читает целые числа из потока стандартного ввода до возникновения ситуации «конец файла», после чего печатает все введённые числа в том порядке, в котором они были введены. Количество чисел заранее неизвестно, вводить явные ограничения на это количество запрещается.

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

Добавление элемента в начало односвязного списка производится в три этапа. Сначала, используя вспомогательный указатель, мы создаём (в динамической памяти) новый элемент списка. Затем мы заполняем этот элемент; в частности, мы делаем так, чтобы его указатель на следующий элемент стал указывать на тот элемент списка, который сейчас (пока) является первым, а после добавления нового станет вторым, следующим после нового. Нужный адрес находится в указателе на первый элемент списка, его-то мы и присвоим полю next в новом элементе. Наконец, третий шаг — признать новый элемент новым первым элементом списка; это делается занесением его адреса в указатель, хранящий адрес первого элемента.

Схематически происходящее показано на рис. 3 на примере все того же списка целых чисел, состоящего из элементов типа item, причём адрес первого элемента списка хранится в указателе first. Сначала в этом списке находятся элементы, хранящие числа 36 и 49 (рис. 3 a)), и нам нужно занести в его начало новый элемент, содержащий число 25. Для этого вводим дополнительный указатель, который будет называться tmp от английского temporary “временный”:

var
  tmp: itemptr;

На первом шаге мы создаём новый элемент:

new(tmp);

Получившаяся после этого ситуация показана на рис. 3, b). Со списком еще ничего не произошло, созданный новый элемент никак его не затрагивает. Сам элемент пока остаётся «недоделанным»: в обоих его полях находится непонятный мусор, что показано на рисунке символом «?!». Пора делать второй шаг — заполнять поля нового элемента. В поле data нам нужно будет занести искомое число 25, тогда как поле next должно указывать на тот элемент, который станет следующим после нового; это собственно, тот элемент, который сейчас пока в списке первый, то есть его адрес хранится в указателе first, его-то мы и присвоим полю next:

tmp^.data := 25;
tmp^.next := first;

Рис. 3. Занесение нового элемента в начало односвязного списка

Состояние нашей структуры данных после этих присваиваний показано на рис. 3, c). Осталось лишь объявить новый элемент — первым элементом списка, присвоив его адрес указателю first; поскольку этот адрес хранится в tmp, всё оказывается совсем просто:

first := tmp;

Финальная ситуация показана на рис. 3, d). Забыв про наш временный указатель и про то, что первый элемент списка только что был «новым», мы получаем ровно то состояние списка, к которому стремились.

С этой трёхшаговой процедурой добавления нового элемента в начало связано одно замечательное свойство: для случая пустого списка последовательность действий по добавлению первого элемента полностью совпадает с последовательностью действий по добавлению нового элемента в начало списка, уже содержащего элементы. Соответствующая последовательность состояний структуры данных показана на рис. 4: вначале список пуст a); на первом шаге мы создаём новый элемент b); на втором шаге заполняем его c); последним действием делаем этот новый элемент первым элементом списка d). Всё это работает только при условии, что мы не забыли перед началом работы со списком сделать его корректным, занеся значение nil в указатель first!

Рис. 4. Работа процедуры занесения в начало при исходно пустом списке

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

program Numbers1;
type
  itemptr = ^item;
  item = record
    data: integer;
    next: itemptr;
  end;

var
  first, tmp: itemptr;
  n: integer;
begin
  {Когда вы закончите набирать файл, нажмите на новой строке Ctrl-Z и Enter.
  Это признак конца файла в Windows, аналог Ctrl-D в UNIX'е}
  first := nil; // делаем список корректно пустым!

  while not SeekEof do begin // цикл чтения чисел, SeekEof-ситуация "конец файла" для чтения последовательности чисел
    read(n);
    new(tmp); // создали
    tmp^.data := n; // заполняем
    tmp^.next := first;
    first := tmp; // включаем в список
  end;

  { Распечатка результата }
  tmp := first; // проходим по списку сначала
  while tmp <> nil do begin // до конца
    writeln(tmp^.data);
    tmp := tmp^.next; // переход к следующему элементу
  end;
  {$ifdef windows}readln;{$endif}
end.

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

while first <> nil do begin
  tmp := first^.next; // запоминаем адрес следующего
  dispose(first); // уничтожаем первый элемент
  first := tmp; // список теперь начинается со следующего
end;

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

while first <> nil do begin
  tmp := first; // запоминаем адрес первого
  first := first^.next; // исключаем его из списка
  dispose(tmp); //удаляем его из памяти
end;

На рис. 5 первый способ показан слева, второй — справа. Какой из них лучше, можете решить для себя сами; по эффективности между ними никакой разницы нет.

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

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

Если односвязный список предполагается увеличивать «с конца», обычно для этого хранят не один указатель, как в предыдущих примерах, а два: на первый элемент списка и на последний. Когда список пуст, оба указателя должны иметь значение nil. Процедура занесения нового элемента в такой список (в его конец) выглядит даже проще, чем только что рассмотренная процедура занесения в начало. Если указатель на последний элемент назовём например, last, то мы можем создать новый элемент сразу где надо, то есть занести его адрес в last^.next, затем сдвинуть указатель last на новоиспечённый последний элемент и уже после этого заполнить его поля; если нам нужно занести в список число 49, это можно сделать так (см. рис. 6):

new(last^.next);
last := last^.next;
last^.data := 49;
last^.next := nil;

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

new(first); // создаём первый элемент списка
last := first; // объявляем его же последним
last^.data := 49; // заполняем
last^.next := nil;

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

if first = nil then begin
  new(first);
  last := first;
end
else begin
  new(last^.next);
  last := last^.next;
end;
last^.data := n;
last^.next := nil;

Рис. 6. Добавление нового элемента в конец списка

Стек и очередь

В некоторых учебниках по информатике можно встретить утверждение, что «стек» и «очередь» — это такие структуры данных; стеком в таких случаях обычно называют ту сущность, которую мы в предыдущем разделе называли односвязным списком. Но остаётся лишь призвать обучающихся не верить в подобные антинаучные высказывания. На самом деле как стек, так и очередь могут быть реализованы совершенно разными структурами данных: списками, массивами, разными комбинациями того и другого. Ту же очередь часто реализуют с помощью кольцевого буфера. Больше того, значения даже не обязательно хранить в оперативной памяти, части приходится использовать файлы на диске. Сами по себе стек и очередь определяются не тем, какова реализующая их структура данных, а тем, каковы доступные пользователю операции и как эти операции работают.

Как стек, так и очередь представляют собой некий абстрактный «объект», обеспечивающий (неважно как) хранение значений определённого типа, причём для этого объекта определены две базовые операции: добавление нового значения и извлечение значения. Разница в том, в каком порядке происходит извлечение: из очереди значения извлекаются в том же порядке, в каком их туда занесли, а стек — в обратном. По английски очередь обычно обозначают аббревиатурой FIFO (first in, first out, т.е. «первым вошёл — первым вышел»), а стеки аббревиатурой LIFO (last in, first out, «последним вошёл — первым вышел»).

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

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

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

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

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

Основные операции над стеком по традиции обозначаются словами push (добавление значения в стек) и pop (извлечение значения из стека). Обе эти операции реализуем в виде подпрограмм. Заметим еще, что занесение нового элемента в стек всегда проходит удачно, тогда как извлечение из стека, если он пуст, успешным считаться не может. Поэтому Push у нас будет процедурой, получающей на вход два параметра — сам стек и число, которое в него нужно занести (причём стек будет передаваться как параметр-переменная, а число — как простой параметр), тогда как Pop будет оформлена в виде логической функции, возвращающей истину в случае успеха и ложь при неудаче; параметров у неё тоже будет два — переменная — стек и переменная типа longint, в которую (в случае успеха) будет записываться результат.

Мы почти закончили придумывать интерфейс. Добавим для удобства еще функцию IsEmpty, получающую в качестве параметра стек и возвращающую истину, если он пуст, и ложь в противном случае. Наконец, вспомним, что переменная может, если ей ничего не присвоить, содержать произвольный мусор, и добавим процедуру, превращающую вновь описанную переменную в корректный пустой стек; назовём её Init.

Ниже приводится пример реализации стека:

type
LongItemPtr = ^LongItem;
LongItem = record
  data: longint;
  next: LongItemPtr;
end;

type
StackOfLongints = LongItemPtr;

procedure SOLInit(var stack: StackOfLongints);
begin
  stack := nil; //корректный пустой стек
end;

procedure SOLPush(var stack: StackOfLongints; n: longint);
var
  tmp: LongItemPtr;
begin
  new(tmp);
  tmp^.data := n;
  tmp^.next := stack;
  stack := tmp;
end;

function SOLPop(var stack: StackOfLongints; var n: longint): boolean;
var
  tmp: LongItemPtr;
begin
  if stack = nil then
    exit(false);
  n := stack^.data;
  tmp := stack;
  stack := stack^.next;
  dispose(tmp);
  SOLPop := true;
end;

function SOLIsEmpty(var stack: StackOfLongints): boolean;
begin
  SOLIsEmpty := stack = nil;
end;

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

var
  s: StackOfLongints;
  n: longint;
begin
  SOLInit(s);
  while not eof do begin
    readln(n);
    SOLPush(s, n);
  end;

  while not SOLIsEmpty(s) do begin
    SOLPop(s, n);
    writeln(n);
  end;
end.

Второй цикл можно записать еще короче:

while SOLPop(s, n) do 
writeln(n);

Попробуем применить ту же методику к очереди. Ясно, что какая-то переменная нам для организации точно понадобится; назовём её тип QueueOfLongints. Основные операции над очередью, в отличие от стека, обычно называют put и get. Как и для стека, для очереди будут нужны процедура инициализации и функция, позволяющая узнать, не пуста ли очередь.

Ниже приводится пример реализации очереди:

type
LongItemPtr = ^LongItem;
LongItem = record
  data: longint;
  next: LongItemPtr;
end;

type
QueueOfLongints = record
  first, last: LongItemPtr;
end;

{ Инициализировать очередь }
procedure QOLInit(var queue: QueueOfLongints);
begin
  queue.first := nil;
  queue.last := nil;
end;

{ Добавить элемент n в конец очереди }
procedure QOLPut(var queue: QueueOfLongints; n: longint);
begin
  if queue.first = nil then begin
    new(queue.first);
    queue.last := queue.first;
  end
  else begin
    new(queue.last^.next);
    queue.last := queue.last^.next;
  end;

  queue.last^.data := n;
  queue.last^.next := nil;
end;

{ Извлечь элемент сначала очереди }
function QOLGet(var queue: QueueOfLongints; var n: longint): boolean;
var
  tmp: LongItemPtr;
begin
  if queue.first = nil then
    exit(false);
  n := queue.first^.data;
  tmp := queue.first;
  queue.first := queue.first^.next;
  if queue.first = nil then
    queue.last := nil;
  dispose(tmp);
  QOLGet := true;
end;

function QOLIsEmpty(var queue: QueueOfLongints): boolean;
begin
  QOLIsEmpty := queue.first = nil;
end;

С использованием этих процедур решение задачи о выдаче введённой последовательности чисел в порядке их поступления, может выглядеть так:

var
  s: QueueOfLongints;
  n: longint;
begin
  QOLInit(s);
  while not eof do begin
    readln(n);
    QOLPut(s, n);
  end;
  while QOLGet(s, n) do writeln(n);
end.

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

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

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

Рис. 1. Двусвязный список из трёх элементов

Построить двусвязный список можно из звеньев, описанных, например, так:

type
PItem2 = ^TItem2;
TItem2 = record
  data: TItemData;
  prev,next: PItem2;
end;

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

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

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

Добавить комментарий