Все о динамических структурах данных. Опции

[Altair]

Содержание:

• Указатели
• Списки
  + Модуль для работы со списками. + Двусвязные списки
  
• Стеки
  + Модуль для работы со стеками.
• Очереди
  + Модуль для работы с очередями.
• Деки (двусторонние очереди)
  + Модуль для работы с деками.
• Деревья
  + Модуль для работы с деревьями.
• Сортировка стека
• Сортировка очереди
• Демонстрационные программы с ДСД
• Двусвязные списки

Есть материал по теме? высылайте! ваша информация будет размещена здесь!

[Altair]

Указатель - это переменная, которая в качестве своего значения содержит адрес ячейки памяти.

Указатель связанный с некоторым типом данных, называется типизированным.
Для объявления типизированного указателя используется значок ^, который помещается перед типом:

var 
  p1:^integer; { p1 может хранить адрес целого числа }
  p2:^real; { p2 может хранить адрес вещественного числа }

Также можно объявлять указатель, не связывая его при этом с конкретным типом данных. Для этого существует стандартный тип Pointer:

var 
  pp:pointer;

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

var 
  pp: pointer;
  p1,p2: ^integer;
  p3: ^real;
 { ... }
Begin
 { ... }
 { связь указателей одного типа данных (разрешено) }
 p1:=p2;

 { попытка присваивания разнотипных указателей (запрещено)}
 p1:=p3;

 { с нетипизированными указателями таких ограничений не существует.}
 pp:=p3; p1:=pp;

Казалось бы, а стоило ли вводить ограничения (нельзя присваивать разнотипные указатели), и тут же давать средство для обхода этого ограничения (обмен значений через дополнительную НЕтипизированную переменную)? Стоило !!! Дело в том, что использование обмена через переменную типа Pointer придает языку дополнительную гибкость, но это также требует от программиста дополнительных усилий, и свидетельствует о вполне осознанном действии, а не случайной ошибке.
Volvo

Динамическая память - это оперативная память ПК, предоставляемая программе при ее работе, за вычетом сегмента данных (64КБ), стека, и тела программы.

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

HEAРORG — начало кучи хранится в этой переменной.
HEAPEND — конец кучи.
HEAPPTR — текущая граница незанятой динамической памяти.

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

var 
  i:^integer;
  j:^real;
begin
  new(i);

После выполнения этого фрагмента указатель i приобретает значение, которое перед этим имел указатель кучи HEAPPTR, а сам HEAPPTR увеличивает свое значение на 2, так как внутреннее представление типа integer, с которым связан указатель i, составляет 2 байта.

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

i^:=2;{в область памяти i помещено значение 2}.

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

Чтобы вернуть байты обратно в кучу, используется процедура DISPOSE.

DISPOSE(i) — возвращает в кучу 2 байта, которые ранее были выделены указателем i.

Для работы с нетипизированными указателями используются процедуры:
GETMEM(P,SIZE) — резервирование памяти.
FREEMEM(P,SIZE) — освобождение памяти.

Указательная переменная Р может быть в 3-х состояниях:

• Содержать адрес какой-либо переменной, память под которую уже выделена.
• Содержать постоянный пустой адрес nil.
• Находится в неопределенном состоянии.

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

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

Type 
  TPtr = ^Telem;
  Telem = record
    Inf: Real;
    Link: TPtr
  End;

[Altair]

Списки

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

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

Пусть тип point описан следующим образом:

Код

Type
  point = ^item;
  item = record
    number: integer;
    next: point
  end;

Каждая переменная типа point состоит из двух компонентов: индентифицирующего номера и указателя на следующий элемент. Из этих переменных, связав их указателями, можно создать линейный список.

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

Процесс формирования списка из n элементов:

Код

  First: = nil; {начало с пустого списка}
  While n>0 do
    begin
      New(r);
      r^.Next:=first;
      r^.Number:=n;
      First:=r;
      n := n-1
    end;

Основные операции со списками

Просмотр списка
Процедура, которая выводит на экран значение поля number элементов списка.

Код

procedure Print (first: point);
Var r: point
Begin
  R: = first;
  While r<>nil do
    begin
      Writeln ('number = ' ,r^.Number);
      R:=r^.Next;
    end;

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

Код

Procedure Search (first: point; x: integer; var q: point);
{
  q - возвращает указатель на найденный элемент;
  q - nil, если элемента с ключем X в списке нет
}
var
  r: point;
  ok: boolean;
begin
  r: = first;
  ok: = true;
  while (r<>nil) and ok do
    if r^.Number=x then ok:=false else r:=r^.Next;
  q: = r
end;

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

Код

{включить элемент в середину списка перед q^}
Procedure Insert (Var q: point; x: integer);
{ х - значение информационного поля включаемого элемента }
Var
  r: point;
Begin
  New (r); {размещаем элемент в памяти}
  R^.Number:=x;
  {меняем ссылку}
  r^.next:=q^.Next;
  q^.Next:=r;
end;

Если требуется включить перед элементом q^, а не после него, то кажется, что однонаправленная цепочка связей создает трудность, поскольку нет “прохода” к элементам, предшествующим данному. Однако эту проблему можно решить, используя простой прием, который состоит в том, что новый элемент вставляется после q^, но затем происходит обмен значениями между новым элементом и q^.

Код

{включить элемент в середину списка перед q^}
Procedure insert_before (Var q: point; x: integer);
Var r: point;
Begin
  New(r); {размещаем элемент памяти}
  {включаем элемент после q^}
  r^.Next:=q^.Next;
  q^.Next:=r;
  {выполняем обмен значениями}
  r^.Number:=q^.Number;
  q^.Number:=x
end;

Удалить элемент из списка
Предположим, что надо удалить элемент, расположенный после элемента, на который указывает ссылка q.

Код

{удаление элемента из середины списка после q^}
Procedure Del (Var q: point);
Var r: point;
Begin
  r:=q^.Next;
  q^.Next:=q^.Next^.next;
  r^.Next:=nil
End;

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

Код

{удаление элемента q^}
Procedure Delete(Var q: point);
Var r: point;
Begin
  r:=q^.next;
  q^:=r^;
  r^.Next:=nil;
End;

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

Код

  { ... }
  Dispose(r);
  r:=nil;
  { ... }

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

[Altair]

Стек

Стек— это линейный список с определенной дисциплиной обслуживания, которая заключается в том, что элементы списка всегда включаются, выбираются и удаляются с одного конца, называемого вершиной стека. Доступ к элементам здесь происходит по принципу “последним пришел — первым ушел” (LIFO — last in first out), т.е. последний включенный в стек элемент первым из него удаляется.

Стеки моделируются на основе линейного списка.

Включение элемента вершины стека называется операцией проталкивания в стек,
а удаление элемента из вершины стека называется операцией выталкивания из стека.

Для работы со стеками необходимо иметь один основной указатель на вершину стека (Тор) и один дополнительный временный указатель (Р), который используется для выделения и освобождения памяти элементов стека.

В присоединенном файле содержится текст модуля для работы со стекоми и инструкция по использованию модуля (все в архиве)

[Altair]

Очередь

Очередь — это линейный список, в котором элементы включаются с одного конца, называемого хвостом, а выбираются и удаляются с другого конца, называемого вершиной.
Дисциплина обслуживания очереди — “первым пришел — первым вышел” (FIFO — First In First Out), т.е. первый включенный в очередь элемент первым из нее и удаляется.

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

Для создания очереди и работы с ней необходимо иметь как минимум два указателя:

• на начало очереди
• на конец очереди

В присоединенном файле модуль для работы с очередью.

[volvo]

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

С деком возможны следующие операции:

1. Добавление элемента в "голову" дека
   

   Procedure PushStart(Var Deq: TDeq; Ch: TData);

2. Добавление элемента в "хвост" дека
   

   Procedure PushFinish(Var Deq: TDeq; Ch: TData);

3. Изъятие элемента из "головы" дека
   

   Function PopStart(Var Deq: TDeq): TData;

4. Изъятие элемента из "хвоста" дека
   

   Function PopFinish(Var Deq: TDeq): TData;

В присоединенном файле содержится текст модуля для работы с деком.

Пример использования модуля:

Uses DeqUnit;
Var mD: TDeq;
Begin

  InitDeq(mD);
	PushStart(mD, 'A');
	PushStart(mD, 'B');
	PushFinish(mD, 'F');
	PushFinish(mD, 'G');
	PrintDeck(mD);

	While not isEmpty(mD) Do
	  WriteLn( PopFinish(mD) );

  DestroyDeq(mD);

End.

[volvo]

Обновленная версия модуля для работы с бинарными деревьями
Внимание: внешние ссылки

[volvo]

Реализация сортировки стека
В приведенной ниже программе содержимое стека mainStack переносится в отсортированном виде в resStack с использованием дополнительного стека tmpStack):

Исходный код

Const maxStack = 100;
Type
TType = Integer;
TStack = Record
stArr: Array[1 .. maxStack] Of TType;
currTop: Integer;
End;

Procedure Init(Var s: TStack);
Begin
s.currTop := 0
End;

Procedure Push(Var s: TStack; x: TType);
Begin
If s.currTop <> maxStack Then
Begin
Inc(s.currTop); s.stArr[s.currTop] := x;
End;
End;

Function Pop(Var s: TStack): TType;
Begin
If s.currTop <> 0 Then
Begin
Pop := s.stArr[s.currTop]; Dec(s.currTop);
End;
End;

Function Top(Var s: TStack): TType;
Begin
Top := s.stArr[s.currTop];
End;

Function IsEmpty(Var s: TStack): Boolean;
Begin
IsEmpty := (s.currTop = 0)
End;

Procedure Print(Var s: TStack);
Var i: Integer;
Begin
For i := 1 To s.currTop Do
Write(s.stArr[i]:4);
WriteLn
End;


Const
n = 10;
arr: Array[1 .. n] Of TType =
(1, 2, 4, 5, 2, 6, 7, 0, 9, 2);

Var
mainStack, resStack, tmpStack: TStack;
i: integer;

begin
Init(mainStack);
Init(resStack);
Init(tmpStack);

For i := 1 To n Do
Push(mainStack, arr[i]);
Print(mainStack);

While not IsEmpty(mainStack) Do
Begin
If IsEmpty(resStack) or (Top(resStack) < Top(mainStack))
Then Push(resStack, Pop(mainStack))
Else
Begin
While (Top(resStack) > Top(mainStack)) and
(not IsEmpty(resStack)) Do
Push(tmpStack, Pop(resStack));
Push(resStack, Pop(mainStack));
While not IsEmpty(tmpStack) Do
Push(resStack, Pop(tmpStack))
End
End;
Print(resStack)
end.

В присоединенном файле - программа сортировки стека
 s_stack.pas ( 1.65 килобайт ) Кол-во скачиваний: 24907


Реализация сортировки очереди
В примере реализуется сортировка очереди (реализованной в виде объекта) без применения дополнительных очередей.

Исходный код

type
ttype = integer;

ptitem = ^titem;
titem = record
data: ttype;
next: ptitem;
end;

tqueue = object
head, tail: ptitem;

constructor init;
destructor done;

procedure put(x: ttype);
function get: ttype;

function empty: boolean;
procedure print;

function get_count: word;
end;


constructor tqueue.init;
begin
head := nil; tail := nil;
end;
destructor tqueue.done;
begin
while empty do get
end;

procedure tqueue.put(x: ttype);
var p: ptitem;
begin
new(p);
p^.data := x; p^.next := nil;
if empty then head := p
else tail^.next := p;
tail := p
end;

function tqueue.get: ttype;
var p: ptitem;
begin
if not empty then
begin
p := head;
head := head^.next;

get := p^.data;
dispose(p);
end
else
begin
writeln('reading from empty queue');
halt(102)
end;
end;

function tqueue.empty: boolean;
begin
empty := not assigned(head)
end;

procedure tqueue.print;
var p: ptitem;
begin
p := head;
write('(queue) <');
while assigned(p) do
begin
write(p^.data, ' ');
p := p^.next
end;
writeln('>')
end;

function tqueue.get_count: word;
var
count: word;
p: ptitem;
begin
p := head; count := 0;
while assigned(p) do
begin
inc(count);
p := p^.next
end;
get_count := count
end;

{ А вот и сама сортировка очереди }
procedure sort(var q: tqueue);
var
i, j, k,
it, it_next: integer;
len: word;
begin
len := q.get_count;
for i := 1 to len do begin
it := q.get;
for j := 1 to len - i do begin
it_next := q.get;
if it > it_next then begin
q.put(it); it := it_next;
end
else
q.put(it_next)
end;

for k := 1 to pred(i) do
q.put(q.get);

q.put(it);
end;
end;

const
test: array[1 .. 10] of integer =
(2, 5, 17, 7, 9, 3, 4, 6, 11, 71);

var
i: integer;
qint: tqueue;

begin
qint.init;

for i := 1 to 10 do
qint.put(test[i]);
qint.print;
sort(qint);
qint.print;

qint.done;
end.

[Altair]

Демонстрационные программы без модулей.
Рассматриваются операции с ДСД.

списки -  list.pas ( 8.78 килобайт ) Кол-во скачиваний: 26279


деки -  deck.pas ( 2.84 килобайт ) Кол-во скачиваний: 25288


деревья -  tree.pas ( 11.08 килобайт ) Кол-во скачиваний: 26498


AVL деревья -  avltree.pas ( 15.24 килобайт ) Кол-во скачиваний: 25295

[Altair]

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

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

Тем не менее, использовать двусвязный список удобнее - потерять начало списка просто невозможно!

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

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

uses crt, dlist;
var
  l:tlist;
begin
 writeln('Программа,тестирующая модуль DList для работы с двусвязными списками');
 writeln('Добавляем первый элемент,список инициализируется автоматически...');
 InitListAndAddFirst(1,L);
 writeln('Теперь добавим элемент 2 после того,на который указывал L... (AddAfter)');
 AddAfter(2,l);
 writeln(' ... и перейдем к концу списка, чтобы добавлять после последнего...(GotoLast)');
 GotoLast(l);
 AddAfter(3,l); GotoLast(l); {...  }
 AddAfter(4,l); GotoLast(l); { ... }
 AddAfter(5,l); GotoLast(l); {  ...}
 writeln('Полученный список (после добавления в конец) (listprint)');
 ListPrint(L);
 writeln('... вставим после 4 элемент 6');
 writeln('Для этого идем в начало списка(GotoFirst) и ищем элемент 4 ... ');
 gotoFirst(l); {в начало}
 while (l^.data<>4)and (l^.next<>nil) do l:=l^.next; {ищем}
 writeln;
 writeln('Нашли, добавляем... ');
 addafter(6,l);
 writeln('...вот, что у нас получилось (ListPrint) :');
 ListPrint(L);
 writeln('Уничтожаем список, очищая память. (ListDestroy)');
 ListDestroy(L);
end.

Модуль:  DLIST.PAS ( 1.78 килобайт ) Кол-во скачиваний: 26089

[volvo]

Кольцевые (циклические) двухсвязные списки

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

Для описания элемента списка будем пользоваться следующей структурой:

type
   myType = integer;
   Ring = ^TRing;
   TRing = record
      info: myType;
      next: Ring;
      prev: Ring;
  end;

Добавление элемента

Добавляться новые элементы будут перед элементом, помеченным как first (то есть, перед "головой" списка) по следующему алгоритму:

1. Поскольку выделение памяти под новый элемент должно производиться независимо от того, пуст список или в нем уже есть элементы, то сделаем это в самом начале процедуры добавления, еще перед проверкой на пустоту списка.
2. В зависимости от того, пуст наш кольцевой список или уже частично заполнен, дальнейшее выполнение процедуры пойдет по одному из двух путей:
   
   2а) список пуст - устанавливаем указатели prev и next на новый элемент и "помечаем" его как первый (First)
   
   2б) список не пуст - действовать нужно по-другому:
   • поскольку добавляем в "конец" списка (перед элементом first), то поле next нового элемента указывает на "голову" списка, а поле prev - туда, куда раньше указывал prev "головы";
   • не забываем про "бывший последним" элемент (элемент на который раньше указывал first^.prev). Поле next этого элемента должно указывать на добавляемый элемент, поскольку новый добавляется после "последнего" (перед "первым");
   • ну, и наконец, "голова" списка должна теперь указывать prev-ом на новый элемент, он ведь находится в списке ПЕРЕД "головой"...
   .

procedure Append(var First: Ring; value: myType);
var p: Ring;
begin
   { 1 }
   new(p);
   p^.info := value;

   if first = nil then begin
      { 2а }
      p^.next := p;
      p^.prev := p;
      first := p;
   end
   else begin
      { 2б }
      p^.next := first; 
      p^.prev := first^.prev;
      first^.prev^.next := p;
      first^.prev := p;
   end;
end;

Удаление элемента

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

1. Список содержит один элемент: проверяем, нужно ли удалять этот элемент, и если нужно - просто удаляем его, и обнуляем First, нет элементов - нет "головы" списка.
2. Список содержит несколько элементов: переназначаем указатели prev^.next и next^.prev удаляемого элемента так, чтобы ни предыдущий ни последующий элементы больше на P не указывали. После этого проверяем, не удаляется ли "головной" элемент (First), и в случае положительного ответа "продвигаем" First на один элемент вперед (если этого не сделать, то после удаления элемента P указатель на "голову" станет невалидным и его использование приведет к получению неправильных результатов). И только после того, как все вышесказанное выполнено, можно удалять элемент списка, на который указывает P...

{ Удалить из списка, начинающегося с First, элемент, на который указывает P }
procedure RemoveItem(var First: Ring; p: Ring);
begin
   if (first^.next = first) and (p = first) then
   begin
      dispose(first);
      first := nil; exit;
   end;

   p^.prev^.next := p^.next;
   p^.next^.prev := p^.prev;
   if p = first then first := p^.next;
   dispose(p); p := nil;
end;

Продолжение следует...