Тема 11. Динамические данные

Указатели 

Все данные программы размещаются операционной системой ЭВМ по соответствующим адресам оперативной памяти. Поэтому в TURBO PASCAL определен адресный тип переменной - Pointer (указатель):
  var p: Pointer;
которые содержат адрес какого-либо элемента программы и занимают  4  байта, при этом адрес хранится как два слова, одно из них определяет сегмент памяти, где записан данный элемент, а второе – его смещение относительно начала этого сегмента.
Переменную типа указатель можно описать другим способом:
 type NameType= ^T;
 var p: NameType;
Здесь p - переменная типа указатель, связанная с типом Т с помощью имени типа NameType.  Описать переменную типа указатель можно  непосредственно в разделе описания переменных:
 var p: ^T;
Необходимо различать  переменную  типа указатель и переменную,  на которую этот указатель ссылается.  Например, если p - ссылка на  переменную типа Т, то p^ - обозначение этой самой переменной.
Для переменных  типа  указатель  введено стандартное значение NIL, которое означает,  что указатель не ссылается ни  к  какому  объекту.
Константа NIL используется для любых указателей.
Над указателями не определено никаких операций,  кроме проверки на равенство и неравенство.
Переменные типа указатель могут быть записаны в левой части оператора присваивания,  при этом в правой  части  может  находиться  либо функция определения адреса Addr(X), либо выражение @ X, где @ - унарная операция взятия адреса,  X - имя переменной любого типа,   в  том числе процедурного.
Переменные типа указатель не могут быть элементами списка ввода - вывода.

Динамические переменные

Статической переменной (статически размещенной) называется описанная явным образом в программе переменная, обращение к ней осуществляется по имени.  Место в памяти для размещения статических  переменных определяется при компиляции программы.
В отличие от таких статических переменных в программах, написанных на языке ПАСКАЛЬ,  могут быть созданы динамические переменные. Основное свойство динамических переменных заключается в том,  что они создаются, и   память  для  них выделяется во время выполнения программы.
Размещаются динамические переменные  в  динамической  области  памяти (heap - области).
Динамическая переменная не указывается явно в описаниях переменных и к ней нельзя обратиться по имени. Доступ к таким переменным осуществляется, как раз, с помощью указателей и ссылок.
Работа с динамической областью памяти в TURBO PASCAL реализуется с помощью процедур и функций New,  Dispose,  GetMem,   FreeMem,   Mark, Release, MaxAvail, MemAvail, SizeOf.
Процедура New(var p: Pointer) выделяет место в динамической области памяти  для  размещения  динамической переменной p^ и ее адрес присваивает указателю p.
Процедура Dispose(  var p:  Pointer )  освобождает участок памяти, выделенный для размещения динамической переменной процедурой  New,  и значение указателя p становится неопределенным.
Процедура GetMem( var p:  Pointer; size:  Word )  выделяет участок памяти в   heap - области,  присваивает адрес его начала указателю p, размер участка в байтах задается параметром size.
Процедура FreeMem( var p:  Pointer; size: Word ) освобождает участок памяти,  адрес начала которого определен указателем p, а размер - параметром size. Значение указателя p становится неопределенным.
Процедура Mark( var p:  Pointer )  записывает в указатель p  адрес начала участка свободной динамической памяти на момент ее вызова.
Процедура Release( var p: Pointer ) освобождает участок динамической памяти, начиная с адреса,  записанного в указатель p процедурой Mark,  то-есть,  очищает ту динамическую память,  которая была занята после вызова процедуры Mark.
Функция MaxAvail: Longint возвращает длину в байтах самого длинного свободного участка динамической памяти.
Функция MemAvail:  Longint полный объем свободной динамической памяти в байтах.
Вспомогательная функция SizeOf( X ):  Word возвращает объем в байтах, занимаемый  X, причем X может быть либо именем переменной любого типа, либо именем типа.
Рассмотрим некоторые примеры работы с указателями.
var
  p1, p2: ^Integer;
Здесь p1 и p2 - указатели или переменные ссылочного типа.
  p1:=NIL;  p2:=NIL;
После выполнения этих операторов присваивания, указатели p1 и p2 не будут ссылаться ни на какой конкретный объект.
  New(p1);  New(p2);
Процедура New(p1) выполняет следующие действия:
-в памяти ЭВМ выделяется участок для  размещения  величины  целого типа;
-адрес этого участка присваивается переменной p1:
Аналогично, процедура New(p2)  обеспечит выделение участка памяти, адрес которого будет записан в p2:
После выполнения операторов присваивания
  p1^:=2;   p2^:=4;
в выделенные  участки  памяти  будут записаны значения 2 и 4 соответственно:
В результате выполнения оператора присваивания  p1^:=p2^; в  участок памяти,  на который ссылается указатель p1, будет записано значение 4:
  После выполнения оператора присваивания
  p2:=p1;
оба указателя будут содержать адрес первого участка памяти:
Переменные p1^, p2^ являются динамическими, так как память для них выделяется в процессе выполнения программы с помощью процедуры New.
Динамические переменные  могут входить в состав выражений,  например:
  p1^:=p1^+8;    Write('p1^=',p1^:3);
Пример. В результате выполнения программы:

  Program DemoPointer; 
    var p1,p2,p3:^Integer; 
  begin 
    p1:=NIL;  p2:=NIL;  p3:=NIL; 
    New(p1);  New(p2);  New(p3); 
    p1^:=2;  p2^:=4; 
    p3^:=p1^+Sqr(p2^); 
    writeln('p1^=',p1^:3,'   p2^=',p2^:3,'  p3^=',p3^:3); 
    p1:=p2; 
    writeln('p1^=',p1^:3,'   p2^=',p2^:3) 
  end. 
  

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

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

Описание этой компоненты дадим следующим образом:
type
  Pointer = ^Comp;
  Comp = record
  D:T;
  pNext:Pointer
end;
здесь T - тип данных.
Рассмотрим основные правила  работы  с  динамическими  структурами данных типа стек, очередь и список, базируясь на приведенное описание компоненты.

Стеки

Стеком называется динамическая структура данных, добавление компоненты в которую и исключение компоненты из  которой  производится  из одного конца, называемого вершиной стека. Стек работает по принципу
LIFO (Last-In, First-Out) - поступивший последним, обслуживается первым.
Обычно над стеками выполняется три операции:
- начальное формирование стека (запись первой компоненты);
- добавление компоненты в стек;
- выборка компоненты (удаление).
Для формирования стека и работы с ним необходимо иметь две переменные типа указатель, первая из которых определяет вершину стека, а вторая - вспомогательная. Пусть описание этих переменных имеет вид:
var pTop, pAux: Pointer;
где pTop - указатель вершины стека;
pAux - вспомогательный указатель.
Начальное формирование стека выполняется следующими операторами:
New(pTop);
  pTop^.pNext:=NIL;
  pTop^.sD:=sC
Последний оператор или группа операторов записывает  содержимое поля данных первой компоненты.
Добавление компоненты в стек призводится с использованием вспо-могательного указателя:
Procedure AddComp(var pTop: PComp; var sC: Alfa);
var pAux: PComp;
begin
  NEW(pAux);
  pAux^.pNext:=pTop;
  pTop:=pAux;
  pTop^.sD:=sC
end;
Добавление последующих компонент производится аналогично.
Пример.Составить программу,  которая формирует стек,  добавляет в него произвольное количество компонент, а затем читает все компоненты и выводит их на экран дисплея,  В качестве данных взять строку символов. Ввод данных - с клавиатуры дисплея, признак конца ввода - строка символов END.

  Program STACK; 
  uses Crt; 
  type 
   Alfa= String[10]; 
   PComp= ^Comp; 
   Comp= Record 
    sD: Alfa; 
    pNext: PComp 
   end; 
  var 
   pTop: PComp; 
   sC: Alfa; 
  Procedure CreateStack(var pTop: PComp; var sC: Alfa); 
  begin 
   New(pTop); 
   pTop^.pNext:=NIL; 
   pTop^.sD:=sC 
  end; 
  Procedure AddComp(var pTop: PComp; var sC: Alfa); 
  var pAux: PComp; 
  begin 
   NEW(pAux); 
   pAux^.pNext:=pTop; 
   pTop:=pAux; 
   pTop^.sD:=sC 
  end; 
  Procedure DelComp(var pTop: PComp; var sC:ALFA); 
  begin 
   sC:=pTop^.sD; 
   pTop:=pTop^.pNext 
  end; 
  begin 
   Clrscr; 
   writeln('  ВВЕДИ СТРОКУ '); 
   readln(sC); 
   CreateStack(pTop,sC); 
   repeat 
   writeln('  ВВЕДИ СТРОКУ '); 
   readln(sC); 
   AddComp(pTop,sC) 
   until sC='END'; 
   writeln('****** ВЫВОД   РЕЗУЛЬТАТОВ ******'); 
   repeat 
    DelComp(pTop,sC); 
    writeln(sC); 
   until pTop = NIL 
  end.

 Очереди

Очередью называется динамическая структура данных, добавление компоненты в которую производится в один конец, а выборка осуществляется с другого конца. Очередь работает по принципу:
  FIFO (First-In, First-Out) -
поступивший первым, обслуживается первым.
Для формирования очереди и работы с ней необходимо иметь три переменные типа указатель,  первая из которых определяет начало  очереди, вторая - конец очереди, третья - вспомогательная.
Описание компоненты очереди и переменных типа указатель дадим следующим образом:
type
 PComp=^Comp;
 Comp=record
  D:T;
  pNext:PComp
 end;
var
 pBegin, pEnd, pAux: PComp;
где pBegin - указатель начала очереди, pEnd - указатель конца  очереди, pAux - вспомогательный указатель. Тип Т определяет тип данных компоненты очереди.
Начальное формирование очереди выполняется следующими операторами:
Procedure CreateQueue(var pBegin,pEnd: PComp; var sC: Alfa);
begin
  New(pBegin);
  pBegin^.pNext:=NIL;
  pBegin^.sD:=sC;
  pEnd:=pBegin
end;
Добавление компоненты в очередь производится в конец очереди:
Procedure AddQueue(var pEnd:PComp; var sC:Alfa);
var pAux: PComp;
begin
  New(pAux);
  pAux^.pNext:=NIL;
  pEnd^.pNext:=pAux;
  pEnd:=pAux;
  pEnd^.sD:=sC
end;
Добавление последующих компонент производится аналогично.
Выборка компоненты  из  очереди  осуществляется из начала очереди, одновременно компонента исключается из очереди.
Пример. Составить программу,  которая формирует очередь, добавляет в нее произвольное количество компонент, а затем читает все компоненты и выводит их на экран дисплея. В качестве данных взять строку символов. Ввод    данных  - с клавиатуры дисплея,  признак конца ввода - строка символов END.

  Program QUEUE; 
  uses Crt; 
  type 
   Alfa= String[10]; 
   PComp= ^Comp; 
   Comp= record 
    sD:Alfa; 
    pNext:PComp 
   end; 
  var 
   pBegin, pEnd: PComp; 
   sC: Alfa; 
  Procedure CreateQueue(var pBegin,pEnd: PComp; var sC: Alfa); 
  begin 
   New(pBegin); 
   pBegin^.pNext:=NIL; 
   pBegin^.sD:=sC; 
   pEnd:=pBegin 
  end; 
  Procedure AddQueue(var pEnd:PComp; var sC:Alfa); 
  var pAux: PComp; 
  begin 
   New(pAux); 
   pAux^.pNext:=NIL; 
   pEnd^.pNext:=pAux; 
   pEnd:=pAux; 
   pEnd^.sD:=sC 
  end; 
  Procedure DelQueue(var pBegin: PComp; var sC: Alfa); 
  begin 
   sC:=pBegin^.sD; 
   pBegin:=pBegin^.pNext 
  end; 
  begin 
   Clrscr; 
   writeln(' ВВЕДИ СТРОКУ '); 
   readln(sC); 
   CreateQueue(pBegin,pEnd,sC); 
   repeat 
    writeln(' ВВЕДИ СТРОКУ '); 
    readln(sC); 
    AddQueue(pEnd,sC) 
   until sC='END'; 
   writeln(' ***** ВЫВОД РЕЗУЛЬТАТОВ *****'); 
   repeat 
    DelQueue(pBegin,sC); 
    writeln(sC); 
   until pBegin=NIL 
  end.

Линейные списки

В стеки или очереди компоненты можно добавлять только в  какой-либо один конец структуры данных, это относится и к извлечению компонент.
Связный (линейный) список является структурой данных, в произвольно выбранное место, которого могут включаться данные, а также изыматься оттуда.
Каждая компонента списка определяется ключом. Обычно ключ - либо число, либо строка символов. Ключ располагается в поле данных компоненты, он может занимать как отдельное поле записи, так и быть частью поля записи.
Основные отличия связного списка от стека и очереди следующие:
- для чтения доступна любая компонента списка;
- новые компоненты можно добавлять в любое место списка;
- при чтении компонента не удаляется из списка.
Над списками выполняются следующие операции:
- начальное формирование списка (запись первой компоненты);
- добавление компоненты в конец списка;
- чтение компоненты с заданным ключом;
- вставка компоненты в заданное место списка (обычно после  компоненты с заданным ключом);
- исключение компоненты с заданным ключом из списка.
Для формирования списка и работы с ним необходимо иметь пять переменных типа указатель, первая из которых определяет начало  списка, вторая - конец списка, остальные - вспомогательные.
Описание компоненты списка и переменных типа указатель дадим следующим образом:
   type
    PComp= ^Comp;
    Comp= record
           D:T;
           pNext:PComp
          end;
   var
    pBegin, pEnd, pCKey, pPreComp, pAux: PComp;
где pBegin - указатель начала списка, pEnd - указатель  конца списка, pCKey, pPreComp, pAux - вспомогательные указатели.
Начальное формирование списка, добавление компонент в конец списка выполняется так же, как и при формировании очереди.
  Procedure CreateLL(var pBegin,pEnd: PComp; var sC: Alfa);
   begin
    New(pBegin);
    pBegin^.pNext:=NIL;
    pBegin^.sD:=sC;
    pEnd:=pBegin
   end;
Для чтения  и вставки компоненты по ключу необходимо выполнить поиск компоненты с заданным ключом:
  pCKey:=pBegin;
  while (pCKey<>NIL) and (Key<>pCKey^.D) DO
   pCKey:=pCKey^.pNext;
Здесь Key - ключ, тип которого совпадает с типом данных компоненты.
После выполнения  этих операторов указатель pСKey будет определять компоненту с заданным ключом или такая компонента не будет найдена.
Пусть pCKey определяет компоненту с заданным ключом. Вставка новой компоненты выполняется следующими операторами:
  Procedure AddLL(var pEnd: PComp; var sC: Alfa);
   var pAux: PComp;
   begin
    New(pAux);
    pAux^.pNext:=NIL;
    pEnd^.pNext:=pAux;
    pEnd:=pAux;
    pEnd^.sD:=sC
   end;
Для удаления компоненты с заданным ключом необходимо при поиске нужной компоненты помнить адрес предшествующей:
  pCKey:=pBegin;
  while (pCKey<>NIL) and (Key<>pCKey^.D) do
   begin
    pPreComp:=pCKey;
    pCKey:=pCKey^.pNext
   end;
Здесь указатель pCKey определяет компоненту с заданным ключом, указатель pPreComp содержит адрес предыдущей компоненты.
Удаление компоненты с ключом Key выполняется оператором:
  Procedure DelComp(var sKey: Alfa; var pBegin: PComp);
   begin
    Find(sKey,pBegin,pCKey,pPreComp,bCond);
    pPreComp^.pNext:=pCKey^.pNext
   end;
Пример. Составить программу, которая формирует список, добавляет в него произвольное количество компонент,  выполняет вставку и удаление компоненты по ключу, а затем читает и выводит весь список на  экран дисплея. В    качестве данных взять строку символов. Ввод данных - с клавиатуры дисплея, признак конца ввода - строка символов END.

Program LISTLINKED; 
uses Crt; 
type 
 Alfa= String[10]; 
 PComp= ^Comp; 
 Comp= record 
  sD:Alfa; 
  pNext:PComp 
 end; 
 var 
  pBegin, pEnd, pAux, pCKey, pPreComp: PComp; 
  sC, sKey: Alfa; 
  bCond: Boolean; 
Procedure CreateLL(var pBegin,pEnd: PComp; var sC: Alfa); 
begin 
  New(pBegin); 
  pBegin^.pNext:=NIL; 
  pBegin^.sD:=sC; 
  pEnd:=pBegin 
end; 
Procedure AddLL(var pEnd: PComp; var sC: Alfa); 
var pAux: PComp; 
begin 
  New(pAux); 
  pAux^.pNext:=NIL; 
  pEnd^.pNext:=pAux; 
  pEnd:=pAux; 
  pEnd^.sD:=sC 
end; 
Procedure Find(var sKey: Alfa; var pBegin,pCKey,pPreComp: PComp; var bCond: Boolean); 
begin 
 pCKey:=pBegin; 
 while (pCKey <> NIL) and (sKey <> pCKey^.D) do begin 
  pPreComp:=pCKey; 
  pCKey:=pCKey^.pNext 
 end; 
 if (pCKey = NIL) and (sKey <> pCKey^.sD) then bCond:=FALSE 
 else bCond:=TRUE 
end; 
Procedure InsComp(var sKey,sC: Alfa); 
var pAux:PComp; 
begin 
 Find(sKey,pBegin,pCKey,pPreComp,bCond); 
 New(pAux); 
 pAux^.sD:=sC; 
 pAux^.pNext:=pCKey^.pNext; 
 pCKey^.pNext:=pAux 
end; 
Procedure DelComp(var sKey: Alfa; var pBegin: PComp); 
begin 
 Find(sKey,pBegin,pCKey,pPreComp,bCond); 
 pPreComp^.pNext:=pCKey^.pNext 
end; 
begin 
 ClrScr; 
 writeln('  ВВЕДИ СТРОКУ '); 
 readln(sC); 
 CreateLL(pBegin,pEnd,sC); 
 repeat 
  writeln('ВВЕДИ СТРОКУ '); 
  readln(sC); 
  AddLL(pEnd,sC) 
 until sC='END'; 
 writeln(' ***** ВЫВОД ИСХОДНОГО СПИСКА *****'); 
 pAux:=pBegin; 
 repeat 
  writeln(pAux^.sD); 
  pAux:=pAux^.pNext; 
 until pAux=NIL; 
 writeln; 
 writeln('ВВЕДИ КЛЮЧ ДЛЯ ВСТАВКИ СТРОКИ'); 
 readln(sKey); 
 writeln('ВВЕДИ ВСТАВЛЯЕМУЮ СТРОКУ'); 
 readln(sC); 
 InsComp(sKey,sC); 
 writeln; 
 writeln('ВВЕДИ КЛЮЧ УДАЛЯЕМОЙ СТРОКИ'); 
 readln(sKey); 
 DelComp(sKey,pBegin); 
 writeln; 
 writeln(' ***** ВЫВОД ИЗМЕНЕННОГО СПИСКА *****'); 
 pAux:=pBegin; 
 repeat 
  writeln(pAux^.sD); 
  pAux:=pAux^.pNext; 
 until pAux=NIL 
 end.