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

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

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

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

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

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

Например:

TYPE m=array[1..100] of real;
m1:^m; {указатель - m1}
Var A:^integer; {А - ссылка на переменную}
B:^real;
mas:m1;

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

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

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

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

Пример:

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

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

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

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

1. Формирование списка.
2. Просмотр элементов списка.
3. Поиск элементов в списке.
4. Удаление элементов звена в списке.
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. Удаление элементов звена в списке.

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

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.