Ссылочный тип данных

Все изученные ранее типы данных относятся к так называемым статическим типам. Это значит, что место в памяти под переменные компилятор отводит до запуска программы(во время компиляции).

Существуют так называемые динамические типы данных. Для переменных этого типа резервирование и очистка памяти производится во время работы программы.

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

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

1. В разделе описания типов.

type
 m=array[1..100] of real;

 m1:^m; {указатель — m1}

var
 a:^integer; {a — ссылка на переменную}
 b:^real;
 mas:m1;

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

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

Существует стандартная функция, которая уничтожает динамический объект при этом освобождая память машины, которую он занимал: DISPOSE(a).

Существует такое понятие, как переменная с указателем. Например: a^ — переменная с указателем, с ней можно обращаться также как с переменной указанного типа.

a^:=5;
a^ mod 5;
mas^[i]:=20;

Между указателями одного типа возможны операции сравнения:

<>,=

Динамические переменные обычно используют в связанных структурах данных. Простейшим способом описания связанных объектов является однонаправленный список(как очередь).

Существует 5 основных операций над списками:

1. Формирование списка.

type
 te=integer;
 ss=zveno;
var
 s:integer;
 u,p:ss; {u-ссылка на заглавное звено, p-указатель на текущее звено}
begin
 new(u); {выделяется место в памяти для заглавного звена}
 p:=u; {указатель текущего звена указывает на первое звено}
 u^.sled:=nil; {чтобы машина не повисла ,обнуляем}
 writeln('Введите список чисел');
 read(s);
 while s>0 do
  begin
   new(p^:sled); {организуется следующее звено}
   p:=p^:sled; {устанавливает указатель на ячейку p^:sled}
   p^.elem:=s; {записываем в ячейку число s}
   p^:sled:=nil; {означает, что у ячейки нет следующего адреса}
   read(s);
  end;
end;

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

Procedure VYVOD;
var
 p:ss;
begin
 p:=u^.sled; {устанавливаем на начало списка}
 while p<>nil do
  begin
   write(p^.elem);{считали}
    p:p^sled; {установили указатель на следующий адрес}
   end;
end;

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

Функция poisk=true, если элемент С принадлежит списку и false, если элемент С не принадлежит списку. Ещё функция ищет AD — адрес ссылки звена элемента С.

function POISK(c:te;var ad:ss);
var
 p:ss:
begin
 poisk:=false;
 ad:=nil; {если элемента в списке нет}
 p:=u^:sled;{установить указатель на заглавное звено}
 while (p<>nil) and (ad=nil) do
  begin
   if p^.elem:=c then
    begin
     poisk:=true;
     ad:=p;
    end;
   p:=p^.sled;
  end;
end.

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

5. Вставка элементов звена в списке.

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

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

procedure UDAL(k:ss);
var
 q:ss;
begin
 p:=k;
 if p<>nil then begin 
                 p:=p^.sled^.sled
                end;
end;

5. Вставка элементов звена в списке.

Будем вставлять новое звено q с элементом M, на которое указывает ссылка p.

procedure VSTAVKA(m:te;p:ss);
var
 q:ss;
begin
 new(q); {открываем новое звено}
 q^.elem:=m; {записали туда элемент}
 q^.sled:=p^.sled; {переадресовка}
 p^.sled:=q;
end;

Пример

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

137 123 2067 -1 входной файл

731 321 7602 -1 выходной файл

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

Program Lists(Imp,Out);
type
 Pointer=^DataSet;
DataSet=record
 Data:integer;
 Point:Pointer
end;
var
 R1,R2:pointer;
 I:integer;
 Imp,Out:file of integer;
begin
 reset(Inp);
 rewrite(Out);
 while not eof(Inp) do
  begin
   R1:=Nil;
   read(Inp, I);
   while I <>-1 do
     begin
      new(R2);
      R2^.data:=I;
      R2^.point:=R1;
      R1:=R2;
      Read(Imp, I)
     end;
   R2:=R1;
   while R2 <> Nil do 
    begin
      write(Out,R2^.data);
      R2:=R2^.point;
    end;
   write (Out, '-1')
end;
end.