Массивы.

Указатели

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

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

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;

Динамическая память - это оперативная память ПК, предоставляемая программе при ее работе, за вычетом сегмента данных (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;

Списки

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

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

Пусть тип 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;
  { ... }

Стек

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

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

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

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

Очередь

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

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

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

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