Ссылочный тип данных. Динамические объекты.

1. Природа динамических объектов и способы их реализации.

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

ВаСуществуют задачи, для которых характерно наличие данных: - фактическое появление которых возможно, но не обязательно; - время жизни этих объектов меньше времени исполнения программы. Такие объекты называют динамическими объектами.

ВаНапример, если нам надо выбрать из входного потока данных, совокупности данных, обладающих определенными свойствами. Встретим или нет мы такие совокупности это вопрос. Поэтому выделение ресурсов для их хранения заранее вряд ли разумно. Более того мы не знаем как велика будет такая совокупность. Затем, если собранную совокупность мы должны передать по линиям связи, например, на другую машину, то в нашей программе логично было бы ресурсы, занимаемые переданной совокупностью, освободить для других нужд. (Ресурсов не хватает всегда - это закон.)

ВаДля работы со статическими объектами в языках программирования используется хорошо известный механизм имен. Pascal здесь не исключение. Однако, этот механизм вряд ли нам подходит для представления и манипуляции динамическими объектами. Дело в том, что имя должно быт известно до выполнения программы - это во-первых. Во вторых, порождение всякого именованного объекта связано с выделением памяти. Раз объекты возникают динамически, то заранее мы не знаем сколько их будет. Следовательно не можем заранее выделить (породить, написать, придумать) нужное количество имен. Далее, не ясно чему соответствует в памяти имя не существующего объекта. Когда объект стал не нужен мы не можем уничтожить имя. Нет таких средств в языке. С другой стороны, уже при написании программы нам надо как-то описывать действия над динамическими объектами.

ВаДля решения этой проблемы в программировании был предложен механизм ссылок. Идея его состоит в том, что динамические объекты представлены не явно, а через некоторую статическую переменную, которая указывает на место расположения динамического объекта, если он существует, либо содержит специальное значение - объект отсутствует. Что значит указывает? Это значит что ее значение - "имя" динамического объекта. Это специальное имя, называемое ссылкой (саму переменную, при этом, часто называют указателем) и которое указывает где размещается, как найти объект и получить доступ к значению.

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

ВаК недостаткам такого решения можно отнести следующее. Если значение ссылочной переменной (ссылка на динамический объект) будет утеряно - этот объект будет безвозвратно утерян. Ведь его "имени" мы явно не знаем. Оно есть значение ссылочной переменной. Если несколько ссылочных переменных указывают на один и тот же объект и этот объект будет уничтожен с помощью одной из них, то все манипуляции с другими ссылочными переменными станут некорректными.

2. Описание ссылочных переменных и их семантика

Синтаксис задания ссылочного типа:

Ва<задание ссылочного типа>::= ^<имя типа>

^ - признак ссылочного типа; <имя типа> - имя стандартного либо описанного ранее типа. Это тип динамических объектов, которые может представлять переменная ссылочного типа. Надо подчеркнуть , что здесь может быть только имя типа.

ВаСами переменные ссылочного типа вводятся обычным образом.

type
ВаВаВаВа массив = array [1.100] of integer;
ВаВаВаВа массивссылок= array [1.100]of ^integer;
var
ВаВаВаВа q,p:^integer;
ВаВаВаВа c:^char;
ВаВаВаВа матрица:^массив;
ВаВаВаВа чудо:массивссылок;

ВаСвязь указателя (ссылочной переменной) с объектом графически можно проиллюстрировать так:

ВаЗначение ссылочной переменной, соответствующее отсутствию динамического объекта - nil (зарезервированное слово).

Следует уяснить, что описание вида

Ваvar v:^T;

лишь вводит статическую переменную (под которую отводится память). Однако, никакого объекта типа Т при этом не появляется. Для порождения объекта служит стандартная процедура new. Эта процедура имеет один фактический параметр - ссылочную переменную. В результате выполнения оператора процедуры new порождается динамический объект надлежащего типа, а ссылочной переменной-параметру присваивается ссылка на этот только что порожденный объект.

ВаПри этом созданному динамическому объекту никакого значения не присваивается. Поэтому конструкция new(v) равносильна описанию статической переменной типа Т.

ВаДля работы с динамическими объектами используется переменная с указателем:

<переменная с указателем>::=<ссылочная переменная>^

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

ВаНапример:

r^:=35; p^:=r^+p^div3; матрица^[p^+3]:=25; чудо[p^+3]^:=3

ВаВ примере матрица^[p^+3]:=25; происходит разименование ссылочной переменной матрица (выражение вида матрица^ часто называют разименованием, а операцию ^ - операцией разименования; эта операция есть во многих языках программирования). В случае чудо[p^+3]^:=3 происходит разименования не полной ссылочной переменной чудо, а лишь частичной переменной чудо[p^+3]. Операция разименование применима только к простым переменным ссылочного типа.

3. Действия над ссылками

ВаНад значениями ссылочного типа нет операций, которые бы давали значения ссылочного типа. Над значениями ссылочного типа определены только операции присваивания и сравнения на равенство и не равенство. В операторе присваивания вида p:=e ссылочным выражением может быть: - пустая ссылка nil; -ссылочная переменная; -ссылочная функция (т.е. функция чье значение - ссылка). Значения левой и правой частей должны ссылать на объекты одного и того же типа.

ВаПустьВа var p, g :^integer. Например, p:=q; приводит к тому что и p и q указывают на один и тот же объект, но если при этом объект, на который указывала ссылочная переменная p, будет утерян, то действия с q станут некорректными!

ВаНеправильно было бы написать p:=q^ т.к. слева переменная ссылочного типа, а справа значение целого типа; p^:=3.0 - опять несоответствие типов (integer и real); p^:=nil - слева переменная целого типа, справа - ссылочное значение.

ВаОтличия использования динамических переменных:

динамические переменный представлены через статические переменные ссылочного типа;

динамическая переменная должна порождаться явно с помощью процедуры new;

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

4. Пример.

ВаРассмотрим следующую задачу. Есть внешний файл, представляющий учреждение, состоящий из записей о служащих учреждения. О каждом служащем известно ФИО, пол, год рождения, должность (лаборант, техник, инженер, научный сотрудник, администратор, начотдела, замдиректора, директор), специальность (математик, программист, механик, электроник, экономист, юрист, физик, химик), номер отдела (1 . 32), где работает служащий, характеристика. Требуется определить отдел, где работает больше всего научных сотрудников. В отделе не более 50 сотрудников.

ВаСтруктура программы может быть описана так:

program выбор (учреждение, output);
begin
ВаВаВаВа for i:= 1 to 32 do
ВаВаВаВаВаВаВаВаВа begin{выбрать из файла всех сотрудников из одного отдела}
ВаВаВаВаВаВаВаВаВаВаВаВаВаВа {еслиВа числоВа нсВа вВа текущемВаВа отделеВаВа больше,ВаВа чемВаВа в
ВаВаВаВаВаВаВаВаВаВаВаВаВаВа результирующем,Ва тоВа взятьВа вВа качествеВа новогоВа значения
ВаВаВаВаВаВаВаВаВаВаВаВаВаВа результирующего массива значение текущего}
ВаВаВаВаВаВаВаВаВа end
ВаВаВаВаВаВа {вывод номера отдела}
end

ВаОчевидно, что эффективность этой программы будет значительно зависеть от того как мы реализуем "взять в качестве нового значения результирующего массива значение текущего". Простая "перекачка" была бы самым неудачным решением.

program выбор (учреждение, output);
const n=50;
type служащий = recordВаВа имя:packed array [1.20] of char;
ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа возраст: 1920.1980;
ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа пол:(М,Ж);
ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа должность:(лб,тх,инж,нс,адм,завотд,замдир,дир);
ВаВаВаВаВаВаВаВа ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаспециальность:(мтмтк,пргрммст,мхнк,элктрнк,
ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа экнмст,фзк,хмк,юрст);
ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа отдел: 1.32;
ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа характеристика:packed array[1.1024]of char
ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа end;
varВа отделтекущий, отделрезультат,R:^array [1.50] of служащий;
ВаВаВаВа номотдела,номрезотдела:1.32;
ВаВаВаВа сотрудник:служащий;
ВаВаВаВа числонс,maxнс,i,j:integer;
ВаВаВаВа учреждение:file of служащий;

begin maxнс:=0;
ВаВаВаВа {порождение динамических массивов}
ВаВаВаВа new(отделтекущий);new(отделрезультат);
ВаВаВаВа for i:= 1 to 32 do
ВаВаВаВаВаВаВаВаВа begin{выбрать из файла всех сотрудников из одного отдела}
ВаВаВаВаВаВаВаВаВаВаВаВаВаВа номотдела:=i;
ВаВаВаВаВаВаВаВаВа {подготовка файла учреждение к очередному просмотру}
ВаВаВаВаВаВаВаВаВаВаВаВаВаВа reset(учреждение) {установили режим чтения};
ВаВаВаВаВаВаВаВаВаВаВаВаВаВа j:=0; числонс:=0;
ВаВаВаВаВаВаВаВаВаВаВаВаВаВа while not eof(учреждение) do
ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа begin read(учреждение,сотрудник);j:=j+1;
ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа if сотрудник.отдел=i then
ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа begin отделтекущий^[j]:=сотрудник;
ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа if сотрудник.должность=нсthen числонс:=числонс+1
ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа end
ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа end;
ВаВаВаВа {если число нс в текущем отделе больше, чем вВаВа результирующем,Ва то
ВаВаВаВа взять в качестве нового значения результирующегоВа массиваВа значение
ВаВаВаВа текущего}
ВаВаВаВаВаВаВаВаВаВаВаВаВаВа if числонс>maxнс then
ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа begin {перестановка ссылок}
ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа maxнс:=числонс; номрезотдела:=номотдела;
ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа R:=отделрезультат;
ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа отделрезультат:=отделтекущий;
ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа отделтекущий:=R
ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа end
ВаВаВаВаВаВаВаВаВа end
ВаВаВаВаВаВа {вывод номера отдела}
ВаВаВаВаВаВаВаВаВа write(maxнс,номрезотдела); writeln
end.

ВаСледует обратить внимание в этой программе на

перестановку ссылок, что избавляет нас от необходимости перекачки значений, из одного массива в другой;

нельзя путать окно файла учреждение^ и ссылочную переменную на объекты типа служащий.

5. Уничтожение динамических объектов

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

Ваdispose (<имя ссылочной переменной>)

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

ВаС появлением процедуры dispose в Pascal становится реальная опасность, о которой мы говорили в начале лекции - уничтожение объекта, на который указывают несколько переменных.

new(p); p^:=3;

d:=p; dispose(p);

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

Список литературы

Для подготовки данной работы были использованы материалы с сайта http://" onclick="return false">

Вместе с этим смотрят:

"Инкарнация" кватернионов

* Алгебры и их применение

*-Алгебры и их применение

10 способов решения квадратных уравнений

Bilet