I,j,n,m:word;
ptrstr:array[1..nn] of pointer; {статический массив указателей на строки по m элементов в строке}
s:real;
type
realpoint=^real;
{функция возвращающая указатель на вещественное число по адресу его сегмента и смещения }
function addrR(i,j:word):realpoint;
begin
addrR:=ptr(seg(ptrstr[i]^),ofs(ptrstr[i]^)+(j-1)*sizeof(real))
end;
{ пользовательская функция обработки ошибок}
{$F+}
function heapfunc(size:word):integer;
begin heapfunc:=1; end;
{$F-}
begin randomize;
heaperror:=@heapfunc;{подключение пользовательской функции обработки ошибок}
writeln('Введите n,m');
readln(n,m);
for i:=1 to n do
begin getmem(ptrstr[i],m*sizeof(real));{запрос на память под строку вещественных чисел}
if ptrstr[i]=nil then begin {если памяти не хватает то выйти }
writeln(' Нет места в "куче"');
for j:=1 to i-1 do
freemem(ptrstr[j],m*sizeof(real)); {освободить уже выделенную память}
halt(2); end;
for j:=1 to m do addrR(i,j)^:=random; {если память есть заполнить массив случайными числами}
end;
s:=0;
for i:=1 to n do
for j:=1 to m do
s:=s+addrR(i,j)^;
writeln('Значение суммы =',s:15:10);
writeln('Среднее значение =',s/(n*m):15:10);
for i:=1 to n do
freemem(ptrstr[i],m*sizeof(real)); {освободить использованную память }
end.
Динамические структуры данных.
Наиболее часто переменные ссылочного типа используются при создании динамических структур данных. Самыми распространенными из таких структур в Паскале являются списковые структуры, которые представляют собой совокупность элементов, количество которых заранее не известно. Оно определяется в процессе работы программы или программистом.
Элементом списка называется переменная типа запись, в качестве одного или нескольких полей которой определена переменная ссылочного типа - указатель на запись, в которой он описан. Остальные поля содержат информацию, подлежащую обработке и могут быть описаны как переменные любого допустимого типа, в том числе другого ссылочного.
Например:
TYPE ukzap = ^element; {ссылочный тип - указатель на запись}
element = record {новый тип - элемент, представляет собой запись о студенте}
name: string[16]; {фамилия}
b1,b2,b3: 2..5; {три отметки по экзаменам}
p: ^real; {указатель на вещественное число - размер стипендии}
next: ukzap; {переменная ссылочного типа ukzap - указатель на след. элемент}
end;
В зависимости от количества полей ссылочного типа, указывающих на записи этого же типа и описанных в элементе списочной структуры различают:
Односвязные списки. (Однонаправленные списки) Каждый элемент такого списка содержит только одно поле ссылочного типа Указатель, определенный с помощью этого поля, предназначен для хранения адреса расположения в памяти следующего элемента списка. На приведенной ниже схеме представлена структура однонаправленного списка.
Элемент
такого списка можно описать, как в ранее
описанном примере:
TYPE ukzap = ^element;
element = record
name: string[16];
telefon:string[7];
next: ukzap;
end;
Однонаправленный список может содержать любое количество элементов, которое регламентируется целями задачи и доступной памятью. Последний элемент такого списка должен содержать признак конца списка. В качестве признака конца служит значение поля указателя последнего элемента равное nil. Адрес первого элемента однонаправленного списка запоминается в переменной ссылочного типа, которая используется для идентификации списка и работы с ним. Иногда можно хранить не только адрес первого но и последнего элемента, что облегчает работу со списком по некоторым алгоритмам.
2.Двусвязные списки. (Двунаправленные списки). Каждый элемент такого списка содержит два поля ссылочного типа Указатели, определенные с помощью этих полей, предназначены для хранения адресов расположения в памяти соответственно предыдущего и последующего элементов списка. На приведенной ниже схеме представлена структура двунаправленного списка.
Элемент такого списка можно описать, используя ранее введенное определение:
TYPE ukzap = ^element;
element = record
name: string[16];
telefon:string[7];
next: ukzap;
pred:ukzap;
end;
В этом описании элемента списка указатель pred (указ.1 на схеме ) содержит адрес предыдущего элемента, указатель next (указ.2 на схеме ) содержит адрес последующего элемента.
Двунаправленный список характеризуется тем, что
а.) у первого элемента списка указатель на предыдущий элемент должен отсутствовать, так как такового у первого элемента нет и поэтому указатель pred устанавливается равным nil.
б ) у последнего элемента списка указатель на последующий элемент должен отсутствовать, так как такового у него нет и поэтому указатель next устанавливается равным nil.
N - связные списки. Каждый элемент такого списка содержит n полей ссылочного типа Указатели, определенные с помощью этих полей, предназначены для хранения адресов расположения в памяти элементов списка. Элемент такого списка можно описать следующим образом:
TYPE ukzap = ^element;
element = record
name: string[16];
telefon:string[7];
uk1: ukzap;
uk2:ukzap;
..................
ukn: ukzap;
end;
Приемы работы со списочными структурами зависят от типа организации списковой структуры, которая определяется тем, как осуществляется добавление нового элемента и удаление очередного. По этим признакам различают дисциплины обслуживания списков. По дисциплинам обслуживания различают: очереди, стеки и деки.
Очередь -динамический список (односвязный или двусвязный), добавление нового элемента в который осуществляется только в конец списка, а удаление - только из начала списка. При этом, поступивший в очередь первым, выбирается первым для обслуживания и удаляется из очереди.
Стек - динамический список (односвязный или двусвязный), и добавление нового элемента в который, и удаление очередного элемента списка осуществляется только с первого элемента списка. При этом первый элемент принято называть вершиной стека. Это позиция, в которой находится последний по времени поступления в стек элемент. Он же является тем элементом, который можно выбрать из стека. Выбранный элемент удаляется из стека, а в его вершине оказывается элемент, который был занесен в стек перед выбранным из него элементом.
Дек - динамический список (односвязный или двусвязный), и добавление нового элемента в который, и удаление очередного элемента списка осуществляется как с первого элемента списка, так и с последнего. При этом оказывается не важным, каким по счету поступил элемент в дек. Выбранным для обслуживания может оказаться как вошедший последним, так и первым.
Кроме выше перечисленных типов списков следует отметить кольцевой список. Такой список получается, если в указатель на последующий элемент последнего элемента однонаправленного списка записать адрес первого элемента. При использовании двунаправленного списка, кроме записи в последний элемент, в указатель на предыдущий элемент первого элемента списка вместо указателя nil необходимо занести адрес последнего элемента списка. При этом, для организации работы с таким списком следует хранить в отдельном указателе адрес начала списка.
Наиболее интересными манипуляциями со списками являются:
1.Добавление
нового элемента в середину списка.
Для этой операции необходимо, после
определения места вставки., а затем
переопределить все необходимые указатели.
Пусть необходимо вставить новый элемент
после второго элемента списка. После
включения список будет выглядеть для
односвязного списка, как представлено
на схеме слева. Для двузвязного списка
подключение элемента выглядит как на
схеме справа
2.Удаление
элемента из середины списка.
Для этой операции необходимо, после
определения места, где располагается
удаляемый элемент, а затем переопределить
все необходимые указатели и удалить
элемент. Пусть необходимо удалить второй
элемент списка. После удаления список
будет выглядеть для односвязного списка,
как представлено на схеме слева. Для
двузвязного списка схема удаления
элемента представлена справа.
Рассмотрим примеры формирования списковых структур и работы с ними на примере стека и очереди и кольцевого списка. В примерах очередь формируется с помощью однонаправленного и двунаправленного списков.
Пример 2.Программа формирует однонаправленный список в виде очереди. При этом добавление нового элемента происходит в конец списка. Программа создает список целых чисел случайным образом, выводит список на печать, а затем вычеркивает из него все числа кратные введенному с клавиатуры числу l.
program ex_ochered;
type ukp=^cpisel; {указатель на элемент списка}
cpisel= record { запись типа «элемент списка»}