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

метки: Структура, Данные, Динамический, Паскаль, Компонент, Список, Ссылка, Значение

Министерство образования и науки Украины

Национальный технический университет Украины «КПИ»

Факультет Информатики и вычислительной техники

Курсовая робота:

ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ В ЯЗЫКЕ ПАСКАЛЬ

Киев

2011

1. Рекурсивные типы данных

Как уже упоминалось, структуры данных регулярного и комбинированного типов (array и record), называются фундаментальными. Описание этих данных фиксирует кардинальное число и однозначно определяет размер выделяемой для них памяти, в связи с чем их также называют статическими.

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

Для дальнейшего обсуждения механизма формирования динамических структур существенной оказывается аналогия между методами структурирования действий и данных.

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

Составной оператор и record — простейшие структуры, получаемые с помощью перечисления или следования. Обе эти структуры состоят из конечного количества явно перечисляемых различных компонент. Если все перечисляемые компоненты одинаковы и число их повторений известно, удобно использовать оператор цикла с параметром (for) и структуру данных типа array. Выбор из двух или более вариантов при ветвлениях выражается условным или выбирающим оператором и, соответственно, записью с вариантами. И, наконец, повторение неизвестного (потенциально бесконечного) количества компонент выражается операторами цикла while или repeat. Соответствующая им структура данных — последовательность (файл), т.е. простейший вид структуры, допускающей построение типов с бесконечным кардинальным числом.

В связи с этим, естественно, возникает вопрос о существовании структуры данных со свойствами, аналогичными рекурсивному вызову процедур. Тип данных, который можно назвать рекурсивным, должен содержать одну или более компонент того же типа, что и все значение (аналогия с процедурой, содержащей один или более вызовов самой себя).

Иерархическая модель данных. Структуры данных

... Иерархическая модель представляет собой связный неориентированный гpaф древовидной структуры, объединяющий сегменты. Иерархическая база данных состоит из упорядоченного набора деревьев. Организация данных в СУБД иерархического типа ... Количество деревьев в базе данных определяется числом корневых записей. К каждой записи базы данных существует только один (иерархический) путь от корневой записи. ...

Примером рекурсивно определяемого объекта может служить синтаксическая конструкция арифметического выражения. Рекурсия в данном случае отражает вложенность, т.е. использование заключенных в скобки подвыражений в качестве операндов в выражениях. Этот объект описывается, например, таким образом:

type

Expression = record

Op: Operator;

Opd1, Opd2: Term

end;

Term = record

case В : Boolean of

true : (Id : string);

False : (Subex : Experession)

end;

• При таком описании каждая переменная типа Term состоит из двух компонент: поля признака В и, если В истинно, то поля Id, иначе — поля Subex.

Описание типа иллюстрирует рекурсию, но недопустимо в языке Паскаль в связи с запрещением способа, при котором один тип определяется с помощью другого и наоборот.

Приведенное описание типа ниже иллюстрируется следующими четырьмя выражениями: 1. a +b; 2. a- (b*c); 3. (a +b)*(c -d): 4. (a*(b + c))/d.

Эти выражения можно представить рисунком (рис.1), на котором видна их вложенная, рекурсивная структура и, кроме того, возможное размещение этих выражений в памяти.

Другим примером рекурсивной информационной структуры является генеалогическое дерево, как частный случай бинарного графа-дерева.

Пусть генеалогическое дерево состоит из имени человека и двух генеалогических деревьев его родителей. Такое (рекурсивное) определение неизбежно приводит к бесконечной структуре. Реальные генеалогические деревья конечны, потому что на каком-то уровне сведения о предках отсутствуют. Этот факт можно учесть, используя приведенную ниже структуру описания типа:

type

Ped = record

case Known: Boolean of

true: (Name : string;

• Father, Mother : Ped);

False: ( )

end;

• Каждая переменная типа Ped (от pedigrec — «генеалогическое дерево») содержит по крайней мере одну компоненту — поле признака Known («известен»).

  Если его значение истинно (true далее обозначено как Т), то имеются еще три поля;

• иначе (false — F) полей больше нет. Отдельное значение x, определенное рекурсивным конструктором записи изображено на Рис.7.2 (поскольку рассматривается только одно определение типа, идентификатор ped перед каждым конструктором опущен).

X=(T,Ted,(T,Fred, (T,Adam,(F),(F)),F)),(T,Mary,(F),(T,Eva,(F),(F)))

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

Очевидно также и то, что рассматриваемая структура данных должна восприниматься как единый информационный объект с «вложенными» одна в другую компонентами, доступ к которым на практике сложно реализовать по аналогии с невозможностью вмешательства в процесс рекурсивного вызова процедур.

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

База данных. Понятие базы данных. Виды баз данных. Объекты для ...

... типа: текстовые, графические, звуковые, мультимедийные; 3.Распределённая – база данных, разные части которой хранятся на различных компьютерах, объединённых в сеть; 4.Централизованная – база данных, хранящихся на одном компьютере; 5.Реляционная – база данных с табличной организацией данных. ... отведённые поля подчинённой таблицы и тем самым, задавая ссылку, обеспечиваем связь двух записей – записи в ...

2. Ссылки

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

Например, генеалогическое дерево, изображенное на Pис.7.2, можно представить в виде отдельных (не обязательно рядом расположенных в памяти) записей. Эти записи связываются с помощью адресов, находящихся в соответствующих полях fat (от father — отец) и mot ( от mother -мать»).

Графически это изображено стрелками (Pис.7.3).

Использование ссылок для реализации рекурсивных структур — только технический прием. В общем случае память под вновь размещаемую компоненту может выделяться автоматически, но использование явных ссылок позволяет, во-первых, получить доступ к отдельным компонентам структуры данных и, во-вторых, строить более разнообразные структуры данных по отношению к тем, которые можно задать только с помощью рекурсивных определений. В частности, явные ссылки позволяют определять «бесконечные» (циклические) структуры или произвольные графы, а также ссылаться на одну и ту же подструктуру из разных мест, т. е. относить ее к нескольким разным структурам.

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

Тип ссылки в языке Паскаль определяется как type t = T. Его значениями являются ссылки на данные типа Т (стрелка здесь читается как «ссылка на»).

Существенно, что тип данных, на которые ссылаются значения типа t, задан в его определении( тип t оказывается жестко связанным с Т).

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

type

Tp =T;

• Tq = Т1;

var

P,P1 : Tp;

• Q : Tq;
• В этом случае оператор присваивания P:=P1 допустим, а P:=Q — нет, поскольку переменные P и P связаны с различными типами.

Значения ссылочных типов создаются всякий раз, когда динамически размещается какой-либо элемент данных. Для динамического размещения данных в языке Паскаль используется стандартная процедура New. Если в разделе переменных описана ссылочная переменная P, то оператор New(P) выделяет память для переменной типа Т, создает ссылку типа T на эту новую переменную и присваивает значение этой ссылки переменной р (см. Рис.7.4).

Теперь сама ссылка обозначается как P. В отличие от этого через р обозначается переменная, на которую указывает P. Значение этой переменной до инициализации не определено.

Все типы данных, описанные таким образом, представляют собой структуру, подобную изображенной на Pис.7.3. Недостаток такой структуры — наличие ссылок на элементы, состоящие только из одного поля признака, т. е. не содержащие никакой существенной информации.

Но именно явная манипуляция ссылками обеспечивает экономию памяти, поскольку позволяет включить информацию о поле признака в значение самой ссылки. Для этого достаточно расширить область значений типа t значением, которое не ссылается ни на какой элемент. В языке Паскаль это специальный символ nil. Такое расширение значений типа ссылки позволяет создавать конечные структуры без явного использования условий в рекурсивных описаниях.

Новая формулировка описания типа данных, основанная на явном использовании ссылок, приведена ниже. В ней отсутствует вариант, поскольку P.Known = False выражается как P = nil :

type

Ancestor = Ped;

Ped = record

Name : string;

Fat,Mot : Ancestor

end;

или иначе:

type

Ped = record

Name: string;

Fat,Mot: Ped

end;

— Теперь вместо того, чтобы рассматривать данную структуру как нечто целое, а затем выделять в ней подструктуры и их компоненты, следует обращать внимание в первую очередь на компоненты, поскольку их взаимосвязь (основанная на ссылках) из любого фиксированного описания становится неочевидной, а “окончание” структуры определяется с помощью проверки истинности условия равенства ссылки значению nil.

Следует отметить, что компоненты динамической структуры данных всегда относятся к комбинированному типу (reсord), поскольку кроме смысловой информации должны обязательно содержать хотя бы одно поле ссылочного типа (на рисунке их два).

Структура данных, показанная на Рис.7.2 и 7.3, вновь изображена на Рис.7.5, где ссылки на неизвестных родителей обозначены как nil. Очевидно, что при этом достигается значительная экономия памяти и появляются дополнительные возможности.

Если предположить, например, что Фред и Мэри — родные брат и сестра, т.е. имеют общих отца и мать, то такой случай легко выразить. Для этого достаточно заменить значения nil на соответствующие значения полей двух записей (mot — у Фреда и fat — у Мэри).

Реализация, при которой концепция ссылок скрыта или используются другие приемы управления памятью, вынуждала бы представить записи Адама и Евы по два раза каждую.

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

Завершая аналогию между структурами действий и данных, следует еще раз отметить, что “чисто” рекурсивные структуры данных можно рассматривать как структуры, соответствующие оператору процедуры, тогда как введение ссылок можно сравнить с использованием операторов безусловного перехода. Так же, как с помощью оператора goto можно строить любые схемы действий (включая циклы), так и с помощью ссылок можно создавать структуры данных любого вида (в том числе циклические).

Рассмотренное выше соответствие между структурами действий и данных иллюстрируется Таблицей 7.1.

Таблица 7.1. Соответствие между структурами действий и данных

Схема построения	Оператор	Тип данных
Атомарный элемент	Присваивание	Скалярный тип
Перечисление	Составной оператор
Известное число повторений	Оператор цикла c параметром
Выбор	Условный оператор	Record с вариантами
Неизвестное число повторений	Оператор цикла с пред или постусловием	Последовательность (файл)
Рекурсия	Оператор процедуры	Рекурсивный тип данных
Универсальная форма представления графов	Оператор безусловного перехода	Структура, связанная явными ссылками

3. Линейные списки

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

Пусть каждая компонента списка есть переменная некоторого типа item, представляющего собой запись с полем идентифицирующего ключа (key) и, возможно, другими полями, характеризующими некоторый информационный объект (существенным для рассматриваемых примеров здесь является только поле key, а упоминание об остальных полях просто свидетельствуют о том, что объект может быть достаточно сложным):

typ

Item=record

Key : Integer;

• . . {другие поля записи}

end;

Тогда список можно было бы представить, например, в виде массива, тип которого определяется как:

Vector=array [1 ..SizeArray] of Item.

Однако, такое представление повлечет за собой определенные неудобства. Во-первых, требуется заранее знать или определить количество компонент списка для того, чтобы указать в описании значение SizeArray. Во-вторых, добавлять новые компоненты можно только в конец списка. В третьих, исключать компоненты неудобно из-за того, что в массиве остаются «дыры», которые нужно каким-то образом отмечать или устранять.

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

При использовании динамических структур теряется такое достоинство фундаментальных структур, как возможность прямого доступа к отдельным компонентам.

Тип Item в этом случае должен быть определен как:

typ

Referenc=^Item;

Item=record

Key : Integer;

Next : Reference

end;

— На Рис.7.6. изображена структура данных, построенная на основе одиночной ссылочной переменной P и компонент типа Item, представляющая собой связанный список (для упрощения здесь и далее другие информационные поля опускаются и рассматривается только поле Key).

Формирование списка. Самое простое действие, которое можно выполнить с уже сформированным списком, это вставить в его начало новую компоненту (в начало потому, что известна ссылка только на первую компоненту).

Для этого необходимо разместить новую компоненту в памяти с помощью процедуры New(q), где q — ссылка на адрес компоненты, а затем выполнить операторы присваивания q next := p; p := q. Порядок операторов нельзя менять, так как это приведет к “потере” адреса начала списка, а, следовательно, и списка в целом.

Таким образом, сформировать список проще всего последовательным дополнением элементов в его начало, естественно, начиная с “пустого” списка. Приведенная ниже программа иллюстрирует процесс формирования списка. При этом порядок компонент в списке противоположен порядку их поступления.

program Prim7_1;

type

Ref=Item;

Item=record

Key : Integer;

Next : Ref

end;

var

N : Integer;

• P,Q : Ref;

begin

Write (`введите количество компонент списка’);

• Read (N);
• P := nil; {начало пустого списка}

while N >0 do

begin

New(Q);

• Q. Next := P;
• P :=Q;
• Read (Q.Key); {ввод значения очередного поля Key}

N := N-1

end

end. { prim7_1}

В некоторых случаях обратный порядок связывания элементов в список нежелателен. Тогда элементы приходится включать в конец списка. Конец списка можно определить с помощью последовательного просмотра уже имеющихся компонент (это дополнительные затраты), или сохраняя значение ссылки на последнюю компоненту, что иллюстрирует Pис.7.7. Если имя этой ссылки есть R то следующий фрагмент программы позволит формировать список, включая новые компоненты в его конец:

var

I,N : Integer;

• P,R,Q : Ref;

begin

Write (`введите количество компонент списка’);

• Read (N);
• New(P); {формирование начала списка}

P.Key :=1;

• P. Next :=nil;
• R := P; {сохранение ссылки на “последний” элемент}

I:=2;

• while I <=N do

begin

New(Q);

• R. Next :=Q;
• Q.Key :=I; {значения .key соответствуют порядку поступления}

Q.Next :=nil;

• R :=Q; {сохранение ссылки на последний элемент}

I :=I+1

end;

• end;

— Неудобства, возникающие при таком способе формирования списка очевидны: используется лишняя ссылка, начало списка формируется не так, как его последующая часть, и включение новой компоненты требует дополнительной операции для сохранения указывающей на нее ссылки.

К элементарным действиям со списками, как и с любыми другими структурами данных, можно также отнести включение и удаление элементов списка (так называемые выборочные изменения и операцию просмотра списка).

Включение в список. Пусть компоненту, на которую указывает ссылка r, необходимо включить в список после компоненты, на которую указывает ссылка Q. Необходимые для этого действия иллюстрируются Pис.7.8.а и сводятся к выполнению операторов

R.Next :=Q.Next;

• Q.Next :=R.

Включение компоненты перед той, на которую указывает ссылка q сопряжено с определенными трудностями, поскольку значение ссылки на нее неизвестно и может быть определено только с помощью просмотра списка вплоть до этой компоненты. Однако желаемый результат можно получить включением новой компоненты после той, на которую указывает q и последующего обмена значений Q.Key и Q.Next.Key (Pис.7.8.б).

Включение в список иллюстрируется фрагментами программ, которые оформлены как процедуры InsertNext и InsertBefore.

procedure InsertNext(var Q : Ref);

begin

R.Next :=Q.Next;

Q.Next :=R

end; { InsertNext}

procedure InsertBefore(var Q : Ref);

var

Buf : Integer;

begin

R.Next :=Q.Next;

• Q.Next :=R;
• Buf := Q.Key;
• Q.Key :=R.Key;

R.Key :=Buf

end; { InsertBefore}

Удаление из списка. Операция удаления из списка компоненты, расположенной после Q, относится к самым простым. Для ее выполнения достаточно уничтожить соответствующую ссылку, т. е. присвоить полю Q.Next значение ссылки на компоненту, которая следует за удаляемой, например, с помощью присваивания Q.Next :=Q.Next.Next (Pис.7.9.а):

• procedure DelitеNext(var Q : Ref);

begin

Q.Next := Q.Next.Next

end; { DelitеNext}

Сложнее удалить саму компоненту Q, так как место расположения предыдущей ссылки без предварительного просмотра списка недоступно. Однако, в этом случае можно предварительно присвоить полю Q.Key значение поля Key следующей компоненты (Q.Next.Key), после чего можно удалить следующую компоненту (Pис.7.9.б).

Процедура Delitе в этом случае имеет вид:

• procedure Delitе( var Q : Ref);

begin

Q^.Key := Q^.Next^.Key;

• Q^.Nexi := Q^.Next^.Next

end; { Delitе}

Прием нельзя применять к последней компоненте списка — ее поля не с чем обменивать.

Просмотр связанного списка. Первая компонента списка всегда доступна, поскольку ссылка на нее есть P. Доступ к следующей компоненте очевиден — ссылка на нее находится в поле Next предыдущей (в данном случае первой) компоненты и может быть выражена, как P.Next. В соответствии с этим ссылка на третюю компоненту определяется как P.Next.Next и т. д.

Можно продолжить этот процесс, но для доступа к компонентам длинного списка такой метод совершенно непригоден и, скорее, просто отражает рекурсивный характер данных. Его можно существенно упростить, используя тот факт, что если Q ссылается на некоторую компоненту списка, то после выполнения оператора присваивания Q :=Q.next значение Q будет ссылкой на компоненту, следующую в списке за данной. Выполнение этого оператора можно продолжать до тех пор, пока значение Q.Next не станет равным nil, т.е. пока не будет достигнут конец списка. В соответствии с этим, алгоритм просмотра списка будет выглядеть так:

• Q := P;
• while Q<>
• nil do

begin

• . . ; {действия, выполняемые со значащими полями q}

Q := Q^.Next

end;

• Из определения оператора цикла с предусловием и списковой структуры данных следует, что действия, выполняемые со значащими полями Q будут выполнены для всех элементов связного списка и ни для каких других.

Поиск в списке компоненты с заданным значением поля Key также относится к простым операциям со связным списком. Операция заканчивается если компонента найдена или достигнут конец списка. С учетом того, что X — искомое значение поля Key, фрагмент программы поиска мог бы иметь вид:

• while (Q<>
• nil) and(Q^.Key <>
• X) do Q := Q^.Next;
• ,

но в этом случае при Q<> nil не существует Q и вычисление условия окончания может потребовать обращения к несуществующей переменной (именно несуществующей, а не к переменной с неопределенным значением), что неизбежно приведет к ошибке времени выполнения. Последнее справедливо не всегда. Если в системе программирования предусмотрено прерывание цикла после вычисления только части условия. которая однозначно определяет его истинность (в рассматриваемом примере равенство Q<> nil=False сразу делает ложным все условие), то проблемы не существует. Если она все же есть, то ситуацию можно исправить, используя оператор аварийного выхода из цикла (в Borland- версиях — это оператор break):

• while (Q<>
• nil) do

if Q^.Key =X

then

Break

else

Q :=Q.next;

— При отсутствии такого оператора условный выход обеспечивается оператором goto и соответствующей меткой. Для этих целей можно также использовать “флажок” — вспомогательную булевскую переменную, которая отмечает, найдена или нет нужная компонента:

• F :=true; {инициализация флажка}

while (Q<> nil) and F do

if Q.Key = X

then

F :=False

else

Q := Q.Next;

4. Очереди

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

Хорошим примером использования характерных свойств динамических структур данных являются информационные объекты, называемые очередью. С понятием очереди обычно связано понятие дисциплины обслуживания. Дисциплины обслуживания могут быть достаточно сложными, однако две из них, т. е. последний пришел — первый вышел (Last Input- First Output, LIFO), и первый пришел — первыйй вышел (First Input — First Output, FIFO) или, наиболее часто употребимы. Соответствующую дисциплине LIFO структуру данных называют стеком (stac) или, если есть риск появления неоднозначности, LIFO-стеком.

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

Очереди FIFO соответствует структура, у которой доступна лишь компонента, находящаяся в этой очереди наибольшее время. Вместо термина “очередь FIFO” часто используется термин «очередь» (queue), по аналогии с очередями, организуемыми людьми, где последний присоединившийся человек встает в конец очереди, а обслуживается тот, кто в данный момент оказался в начале. Такую структуру представляет собой рассмотренный ранее вариант связанного списка с дополнительной ссылкой на последнюю компоненту. При этом новая компонента дожна помещаться в конец списка, а исключаться — первая компонента.

5. Двусвязные кольца

Несколько изменив структуру списка, можно избавиться от необходимости особой обработки специальных случаев. Для этого достаточно в каждой компоненте списка хранить две ссылки — одну на предыдущую компоненту, а другую — на следующую. Модифицированное описание списка будет иметь вид:

type

Ref=^Item;

Item=record

Key : Integer;

• Next : Ref;

Preced : Ref

end;

— где Next — ссылка на следующую компоненту списка или ссылка вперед, а Preced — ссылка на предыдущую компоненту или ссылка назад. Для полной симметрии можно связать первую и последнюю компоненты списка между собой. В результате получится двусвязное кольцо, которое изображено на Pис.7.10.а. При этом вырожденное или пустое кольцо определяется как кольцо, состоящее из фиктивной компоненты, которая ссылается сама на себя (рис.7.10.б).

Ниже приведены процедуры, производящие вставку и исключение компонент кольца:

• procedure InsertNext (Q,R :Ref);

begin

Q^.Next :=R^.Next;

• R^.Next :=Q;
• Q^.

Preced :=Q^.Next^.Preced;

• Q^.Next^.Preced :=Q

end; { InsertNext)

procedure InsertBefore (Q,R :Ref);

begin

Q^.Preced :=R^.Preced;

• R^.preced :=Q;
• D^.Next := R^.Preced^.Next;

• R^.Preced^.Next := Q

end; {InsertBefore)

procedure DelNext(var Q : Ref);

begin

Q^.Next := Q^.Next^.Next;

• Q^.Preced^.Preced := Q^.Preced

end; {DelNext}

Эти процедуры универсальны. В общем случае, понятия “перед” и “после” здесь теряют свой смысл, поскольку зависят от того, какую из ссылок использовать для их определения. Таким образом, двусвязное кольцо представляет собой достаточно гибкую структуру. При выполнении операций над кольцами сокращается количество последовательных просмотров и устраняется необходимость обработки “специальных” случаев.

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

• procedure PreView (Start : Ref); {Start определяет “вход” в кольцо}

begin

Ring := Start^.Next;

while Ring =Start do

begin

• . . ; {операции над “значащими” полями}

Ring :=Ring ^.Next

end

end;

— Операции над “значащими” полями будут выполняться по одному разу для каждой компоненты кольца. В момент их выполнения переменная Ring будет указывать на текущую компоненту. Операции не будут выполняться вовсе, если кольцо вырождено (в смысле Pис.7.10.б.).

Просмотр кольца будет идти в обратном направлении при замене в тексте процедуры ссылки next на preced.

6. Распределение памяти

паскаль ссылка память очередь

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

В системах программирования Borland Pascal функции распределения памяти реализуются с помощью модуля System на основе так называемой сегментной адресации. Для каждой отдельно протранслированной программы (файла .exe) дисковая операционная система строит префикс программного сегмента — PSP. Эта область памяти длинной 256 байт представляет собой совокупность данных, определяющих адресацию и управление программой и данными во время ее выполнения.

Процессор 80286 и более поздние процессоры поддерживают два режима операций: защищенный режим и реальный режим. Реальный режим совместим с работой процессора 8086 и позволяет прикладной программе адресоваться к памяти объемом до одного мегабайта. Защищенный режим расширяет диапазон адресации до 16 мегабайт. Основное отличие между реальным и защищенным режимом заключается в способе преобразования процессором логических адресов в физические. Логические адреса — это адреса, используемые в прикладной программе. Как в реальном, так и в защищенном режиме логический адрес есть 32-разрядное значение, состоящее из 16-битового селектора (адреса сегмента) и 16-битового смещения. Физические адреса — это адреса, которые процессор использует для обмена данными с компонентами системной памяти. В реальном режиме физический адрес представляет собой 20-битовое значение, а в защищенном режиме — 24-битовое.

Когда процессор обращается к памяти (для выборки инструкции или переменной), логический адрес преобразуется в физический на основе информации, содержащейся в PSP. В реальном режиме генерация физического адреса состоит из сдвига селектора (адреса сегмента) на 4 бита влево (это означает умножение на 16) и прибавления смещения. Полученный в результате 20-разрядный адрес используется затем для доступа к памяти.

Чтобы получить физический адрес в защищенном режиме, селекторная часть логического адреса используется в качестве индекса таблицы дескрипторов. Запись в таблице дескрипторов содержит 24-битовый базовый адрес, к которому затем для образования физического адреса прибавляется смещение логического адреса.

Доступ к PSP, вообще говоря, возможен из исходного кода прикладной программы. Более того, для облегчения доступа к нему в языке предусмотрена зарезервированная переменная PrefixSeg размерности word, значениями которой могут быть адреса сегмента PSP (обычно этот адрес указывается в шестнадцатиричном формате с префиксом <S>

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

Сегментная адресация позволяет при компиляции каждому логическому блоку поставить в соответствие свой сегмент памяти. Вполне оправданным с этой точки зрения выглядит такое разбиение памяти, когда каждому модулю программы, данным и самой программе выделяется по сегменту. Первым из таких сегментов является сама таблица префикса программного сегмента. За PSP следует код программы, далее в порядке, орбратном тому, который был указан в вызове Uses, располагаются подключенные к исхдному коду модули, после которых размещается сегмент модуля System (библиотеки времени выполнения).

Для наглядности ниже, в таблице 7.2. показана карта распределения памяти, на которой последовательные сегменты программы расположены снизу вверх (в сторону увеличения адресов).

Таблица 7.2. Карта распределения памяти.

Верхняя граница памяти
Список записей, регистрирующий наличие свободного пространства в Heap-области	FreePtr
Свободная память	HeapPtr
Область памяти Heap, которая распределяется, начиная с HeapOrg, в сторону увеличения адресов. Управление распределением Heap ведется через список свободных областей	HeapOrg
Область памяти для загрузки оверлеев
Область памяти для сегмента стека, распределение в сторону уменьшения адресов	Sseg: Sptr
Глобальные переменные, сегмент данных и типизированные константы	Sseg:0000 Dseg: 0000
Сегмент кода модуля System
Сегмент кода модуля “А”
Сегмент кода модуля “B”
Сегмент кода модуля “C”
. .
Сегмент кода основной программы
Префикс программного сегмента (PSP)	PrefixSeg

Все приведенные на полях таблицы символические имена имеют в языке четко определенный смысл. Более того, они доступны в исходном коде, поскольку управление переменными с такими именами производится модулем System, который по умолчанию “подключается” к любому исходному коду.

Понятие “оверлей” и оверлейная организация программ в связи с ограничением объема книги выходит за рамки рассматриваемых инструментальных средств языка.

После сегмента модуля System в памяти машины располагается сегмент данных. В него включаются все типизированные константы, объявленные в разделе Const с явно определенным типом, и все переменные, объявленные в разделе var уровня основной программы и подключаемых к ней с помощью инструкции Uses модулей. Объем сегмента данных, как и любого сегмента вообще, по умолчанию не может превышать 65536 байт (это значение возвращает стандартная функция Dseg).

В связи с этим, например, при компиляции следующего фрагмента программы появится сообщение об ошибке времени компиляции:

• unit MyUnit;

interface

var

Buffer : [1..$FFF0] of Char;

{ Объявление массива критического для сегмента размера}

implementation

begin

end. {MyUnit}

uses Crt, MyVar;

var

St : String; { строка 256 байт по умолчанию}

begin

end.

Сообщение об ошибке “выход за пределы памяти” (out of memory) будет вызвано тем, что в модуле MyVar размер объявленной переменной окажется критическим для сегмента данных, и общий размер этой переменной и строки длинной 255 байт превысит максимально допустимую величину.

Сегмент данных в Borland Pascal используется только для размещения статических переменных. Динамические структуры данных располагаются в Неар -области (“куче”), что позволяет “растянуть” реально используемую для задачи память. Более того, ранее определенное понятие ссылки, связанное с рекурсивными типами данных, в Borland Pascal существенно изменено по отношению к Стандарту. Ссылка рассматривается как некоторый универсальный указатель (Pointer) на адрес в куче.

Тип pointer

Встроенный тип pointer обозначает нетипизированный указатель, то есть указатель, который в отличие от понятия ссылки в динамических структурах, не связан с ни с каким определеннм типом данных. Кардинальное число типа Pointer соответвует 4 байтам и включает значение nil. При этом указатели, если они не являются полем в рекурсивных структурах данных, размещаются там же, где и статические переменные, т. е. в сегменте данных.

Переменные типа Pointer описываются так же, как ссылки с указанием символа перед указанием типа той переменной, которая должна распределяться в куче, например:

type

DynType=array [1..$FFF0] of Char;

var

BufferPtr : ^ DynType; {массив критического для сегмента размера

теперь будет размещаться в Heap-области}

StrPtr : String;

— Перед использованием переменных типа pointer их, естественно, нужно инициализировать, т. е. выделить память для распределения значения соответствующего типа данных (полная аналогия с формированием новой компоненты динамических структур данных).

Для этих целей используется уже известная процедура new с единственным параметром в виде переменной- указателя:

• New(BufferPtr);
• New(StrPtr);

В соответствии с ранее описанными для ссылки правилами, обращение к таким переменным должно иметь вид:

• BufferPtr^[3] :=`a’;
• StrPtr :=`Иванов’;
• В таком контексте динамические переменные ничем не отличаются от обычных переменных соответствующих типов: к ним применимы все допустимые над типом операции.

Процедура Dispose. Кроме процедуры New для работы с динамическими переменными в Borland Pascal зарезервирована процедура Dispose с тем же параметром. Она предназначена для освобождения памяти в Heap, выделенной процедурой New. Так после вызовов:

• Dispose(BufferPtr);
• Dispose(StrPtr);

— указатели перестанут быть связаны с конкретными адресами памяти (в этом случае иногда говорят, что они “разименованы”), а попытка присваивания несуществующим переменным каких-либо значений приведет к нарушению нормальной работы программы (такое обращение не контролируется транслятором) или к “зависанию” операционной системы. Поэтому во время работы с динамическими переменными следует придерживаться определенной последовательности действий, укладывающихся в схему:

• выделение памяти (инициализация с помощью New);
• работа с соответствующей переменной;
• освобождение памяти с помощью Dispose.

Описанная семантика процедур New и Dispose этим не ограничивается и дополнительно расширена по отношению к динамическим объектам (см. раздел 9).

Ее “функциональная” форма могут использоваться по отношению к любым динамически размещаемым переменным.

Процедуры Mark и Release. Существует еще один способ динамического размещения переменных. Его основу составляет несколько иной подход к выделению памяти в Неар. Для области Неар в модуле System выделено несколько ключевых переменных-указателей (см. таблицу): HeapOrg, HeapPtr и HeapEnd. Переменная HeapOrg всегда указывает на начало области Неар, переменная HeapEnd указывает на конец области, а переменная HeapPtr содержит указатель на начало нераспределенной памяти в Неар. Естественно, если значение HeapPtr равно значению HeapOrg, то это говорит о том, что область Неар пуста, а если HeapPtr равно HeapEnd, то полностью занята. Любое выделение памяти в Неар приводит к увеличению значения HeapPtr.

Процедура Mark(var P:Pointer) записывает текущее значение HeapPtr в переменную-указатель Р, тем самым фиксируя текущее состояние Неар. С помощью процедуры Release(var P:Pointer) в области Неар автоматически освобождаются все динамические переменные, распределенные выше указателя Р. При этом текущее значение HeapPtr станет равным Р. Вызов процедуры Mark всегда должен предшествовать вызову процедуры Release. В примере использования Mark и Release задействованно обращение к функции MemAvail, которая возвращает размер свободной памяти в Неар.

var

HeapTop : ^Word;

begin

Mark(HeapTop);

• WriteLn(`Размер памяти в Heap:’,MemAvail);
• New(RealP);
• New(NameStrP);
• Release(HeapTop);

WriteLn(`Heap после Release:’,MemAvail)

end.

Процедуры GetMem и FreeMem. Для динамического распределения памяти в Неар служат еще две тесно взаимосвязанные процедуры. Подобно New и Dispose, они во время вызова выделяют и освобождают память для одной динамической переменной. Процедура GetMem(var P: Pointer; Size: Word) создает в Неар новую динамическую переменную Р^ с определенным размером Size. Переменная-указатель Р может указывать на любой допустимый тип. Процедура FreeMem(var P: Pointer; Size: Word) освобождает динамическую переменную заданого размера.

Если в программе используется этот способ распределения памяти, то вызовы GetMem и FreeMem должны соответствовать друг другу, а значения Size при обращении к одной и той же переменной-указателю должны совпадать. Обращения к GetMem и FreeMem могут полностью соответствовать вызовам New и Dispose. При этом удобно использовать функцию Sizeof, которая возвращает размер памяти, требуемый для размещения значения заданного типа:

• New(NameStr);
• Dispose(NameStr);
• GetMem(NameStrP,Sizeof(NameStr)); {будет тот же результат,}

FreeMem(NameStrP,Sizeof(NameStr)); {что для New и Dispose.}

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

• GetMem(HeapTop, 40); {выделено 40 байт памяти для HeapTop}

FreeMem(HeapTop, 40);

• GetMem(HeapTop, 2000); {выделено 2000 байт памяти для HeapTop}

FreeMem(HeapTop, 2000);

Операции со ссылками

Операциями, допустимыми применительно к переменными ссылочного типа в Стандарте языка, являются операция присваивания, т.е. настройка ссылки на некоторый объект (или настройка на фиктивный объект, если ссылке дается значение nil) и операции отношения. Такой подход представляется разумным, поскольку другие операции над ссылками в контексте рекурсивных структур данных бессмысленны. Однако с учетом введения в средства языка стандартного типа pointer, этот набор расширен операцией взятия адреса -@.

Операция @ возвращает адрес переменной, т. е. строит значение-указатель, ссылающееся на эту переменную, например:

type

TChar = array[0..1] of Char;

var

Int: Integer;

• TCharPtr : ^TChar;

тогда оператор

TCharPtr := @ Int ;

• приводит к тому, что значением TCharPtr становится значение адреса переменной Int, несмотря на объявление TCharPtr : ^TChar.

Тип получаемого в результате применения операции @ указателя управляется директивой компилятора $T: в состоянии $T- (по умолчанию) типом результата будет pointer, т. е. нетипизированный указатель, совместимый со всеми другими типами указателей. В состоянии $T+ типом результата будет ^T, где T — тип ссылки на переменную (тип результата будет совместим со всеми другими указателями на тип этой переменной).

Использование операции @ применительно к переменным процедурного типа имеет некоторую специфику (см. раздел 8).

этим событием), “отправляется” по кольцу влево и “занимает свое место” в списке событий в соответствии с меткой времени его обработки, а текущее событие обрабатывается и затем удаляется из списка. Например, элемент списка для задачи моделирования потока пассажирского транспорта можно представить в виде:

type

Ref=^Item;

Item = record

NumberTr, NumberSt :=Integer;

• Time : Integer;

Ntxt,Preced : Ref

end;

— Поля NumberTr, NumberSt соответсевуют номеру транспортного средства на маршруте и номеру остановки, на которой оно находится, а поле Time определяет время прибытия (или отправления) на очередную остановку. Попробуйте написать програму, моделирующую потока транспорта, задавая в качестве исходных данных количество остановок, транспортных средств на маршруте и интервалы времени движения между остановками и стоянки. Программа, построенная на основе такого представления данных подробно описана в [6].

3. Отдельным и достаточно обширным разделом программирования как дисциплины является обработка древовидных структур данных (деревьев), для которых наиболее приемлемыми являются рекурсивные структуры данных, поскольку само определение древовидной структуры рекурсивно. Действительно, например, двоичный граф-дерево можно определить таким образом:

О есть дерево (называемое пустым деревом)

если D ₁ и D₂ — деревья, то О есть дерево

D ₁ D₂

Подобная структура легко описывается с помощью линейного списка, состоящего из элементов, которые имеют поле Key и, возможно, другие смысловые поля, а также две ссылки на следующие вершины графа. Напишите программу поиска пути в двоичном графе-дереве, предполагая, что ключи не упорядочены (при этом нужно помнить, что искомого пути может и не быть. Приемы обработки произвольных и двоичных деревьев подробно рассматриваются в[7,8].