Информатика и информационные технологии

TYPE TreeLink = ^Tree;

Tree = record;

Inf: <тип данных>;

Left, Right: TreeLink;

End.

22. Примеры реализации операций

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

Рекурсивный алгоритм построения:

1) первый узел берется в качестве корня дерева;

2) тем же способом строится левое поддерево из nl узлов;

3) тем же способом строится правое поддерево из nr узлов;

nr = n - nl - 1

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

Function Tree(n: Byte): TreeLink;

Var t: TreeLink; nl,nr,x: Byte;

Begin

If n = 0 then Tree:= nil

Else

Begin

nl:= n div 2;

nr = n - nl - 1;

writeln('Введите номер вершины);

readln(x);

new(t);

t^.inf:= x;

t^.left:= Tree(nl);

t^.right:= Tree(nr);

Tree:= t;

End;

{Tree}

End.

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

Procedure Search(x: Byte; var t: TreeLink);

Begin

If t = nil then

Begin

New(t);

t^inf:= x;

t^.left:= nil;

t^.right:= nil;

End

Else if x < t^.inf then

Search(x, t^.left)

Else if x > t^.inf then

Search(x, t^.right)

Else

Begin

{обработка найденного элемента}

…

End;

End.

23. Понятие графа. Способы представления графа

Граф - пара G = (V,E), где V - множество объектов произвольной природы, называемых вершинами, а E - семейство пар ei = (vil, vi2), vijOV, называемых ребрами. В общем случае множество V и (или) семейство E могут содержать бесконечное число эле-ментов, но мы будем рассматривать только конечные графы, т. е. графы, у которых как V, так и E конечны. Если порядок элементов, входящих в ei, имеет значение, то граф называется ориентированным, сокращенно - орграф, иначе - неориентированным. Ребра орграфа называются дугами.

Если e = <u,v>, то вершины v и и называются концами ребра. При этом говорят, что ребро e является смежным (инцидентным) каждой из вершин v и и. Вершины v и и также называются смежными (инцидентными). В общем случае допускаются ребра вида e = <v, v>; такие ребра называются петлями.

Степень вершины графа - это число ребер, инцидентных данной вершине, причем петли учитываются дважды.

Вес вершины - число (действительное, целое или рациональное), поставленное в соответствие данной вершине (интерпретируется как стоимость, пропускная способность и т. д.).

Путем в графе (или маршрутом в орграфе) называется чередующаяся последовательность вершин и ребер (или дуг - в орграфе) вида v0, (v0,v1), v1, …, (vn -1,vn), vn. Число n называется длиной пути. Путь без повторяющихся ребер называется цепью, без повторяющихся вершин - простой цепью. Замкнутый путь без повторяющихся ребер называется циклом (или

контуром в орграфе); без повторяющихся вершин (кроме первой и последней) - простым циклом.

Граф называется связным, если существует путь между любыми двумя его вершинами, и несвязным - в противном случае.

Существуют различные способы представления графов.

1. Матрица инцидентности.

Это прямоугольная матрица размерности n ч m, где n - количество вершин, а m - количество ребер.

2. Матрица смежности.

Это квадратная матрица размерности n ч n, где n - количество вершин.

3. Список смежности (инцидентности). Представляет собой структуру данных, которая

для каждой вершины графа хранит список смежных с ней вершин. Список представляет собой массив указателей, i-ый элемент которого содержит указатель на список вершин, смежных с i-ой вершиной.

4. Список списков.

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



24. Различные представления графа

Для реализации графа в виде списка инцидентности можно использовать следующий тип:

Type List = ^S;

S = record;

inf: Byte;

next: List;

end;

Тогда граф задается следующим образом:

Var Gr: array[1..n] of List;

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

На языке Pascal процедура обхода в глубину будет выглядеть следующим образом:

Procedure Obhod(gr: Graph; k: Byte);

Var g: Graph; l: List;

Begin

nov[k]:= false;

g:= gr;

While g^.inf <> k do

g:= g^.next;

l:= g^.smeg;

While l <> nil do begin

If nov[l^.inf] then Obhod(gr, l^.inf);

l:= l^.next;

End;

End;

Представление графа списком списков

Граф можно определить с помощью списка списков следующим образом:

Type List = ^Tlist;

Tlist = record

inf: Byte;

next: List;

end;

Graph = ^TGpaph;

TGpaph = record

inf: Byte;

smeg: List;

next: Graph;

end;

При обходе графа в ширину мы выбираем произвольную вершину и просматриваем сразу все вершины, смежные с ней.

Приведем процедуру обхода графа в ширину на псевдокоде:

Procedure Obhod2(v);

Begin

queue = O;

queue <= v;

nov[v] = False;

While queue <> O do

Begin

p <= queue;

For u in spisok(p) do

If nov[u] then

Begin

nov[u]:= False;

queue <= u;

End;

End;

End;

25. Объектный тип в Pascal Понятие объекта, его описание и использование

Объектно-ориентированный язык программирования характеризуется тремя основными свойствами:

1) инкапсуляцией. Комбинирование записей с процедурами и функциями, манипулирующими полями этих записей, формирует новый тип данных - объект;

2) наследованием. Определение объекта и его дальнейшее использование для построения иерархии порожденных объектов с возможностью для каждого порожденного объекта, относящегося к иерархии, доступа к коду и данным всех порождающих объектов;

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

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

Объектный тип может наследовать компоненты другого объектного типа. Если тип T2 наследует от типа T1, то тип T2 является потомком типа Г, а сам тип Г, является родителем типа Г2.

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

type

Point = object

X, Y: integer;

end;

Rect = object

A, B: TPoint;

procedure Init(XA, YA, XB, YB: Integer);

procedure Copy(var R: TRectangle);

procedure Move(DX, DY: Integer);

procedure Grow(DX, DY: Integer);

procedure Intersect(var R: TRectangle);

procedure Union(var R: TRectangle);

function Contains(P: Point): Boolean;

end;

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

Тип компоненты файлового типа не может иметь объектный тип или любой структурный тип, содержащий компоненты объектного типа.



26. Наследование

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

Тип-потомок, при этом, называется наследником или порожденным (дочерним) типом. А тип, которому наследует дочерний тип, называется порождающим (родительским) типом.

Наследуемые поля и методы можно использовать в неизменном виде или переопределять (модифицировать).

Н. Вирт в своем языке Паскаль стремился к максимальной простоте, поэтому он не стал его усложнять введением отношения наследования. Поэтому типы в Паскале не могут наследовать.

Однако Turbo Pascal 7.0 расширяет этот язык для поддержки наследования. Одним из таких расширений является новая категория структуры данных, связанная с записями, но значительно более мощная. Типы данных в этой новой категории определяются с помощью нового зарезервированного слова Object. Синтаксис при этом очень похож на синтаксис определения записей:

Type

<имя типа> = Object [(<имя типа родителя>)]

([<область действия>]

<описание полей и методов>)+

end;

Знак "+" после синтаксической конструкции в круглых скобках означает, что эта конструкция должна встречаться один или более раз в данном описании.

Область действия есть одно из следующих ключевых слов:

- Private;

- Protected;

- Public.

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

Подробнее об областях действия компонент рассказано в вопросе № 28.

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

27. Создание экземпляров объектов

Экземпляр объекта создается посредством описания переменной или константы объектного типа или путем применения стандартной процедуры New к переменной типа «указатель на объектный тип». Результирующий объект называется экземпляром объектного типа.

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

Присваивание экземпляра объектного типа не подразумевает инициализации экземпляра. Объект инициализируется кодом, генерируемым компилятором, который выполняется между вызовом конструктора и моментом когда выполнение фактически достигает первого оператора в блоке кода конструктора.

Если экземпляр объекта не инициализируется и проверка диапазона включена (директивой {$R+}), то первый вызов виртуального метода экземпляра объекта дает ошибку этапа выполнения. Если проверка диапазона выключена директивой {$R--}), то первый вызов виртуального метода неинициализированного объекта может привести к непредсказуемому поведению.

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

var

Comment: array [1..5] of TStrField;

I: integer;

begin

for I:= 1 to 5 do

Comment [I].Init (1, I + 10, 40, 'первое_имя');

.

.

.

for I:= 1 to 5 do Comment [I].Done;

end;

Для динамических экземпляров инициализация, как правило, связана с размещением, а очистка - с удалением, что достигается благодаря расширенному синтаксису стандартных процедур New и Dispose. Например:

var

SP: StrFieldPtr;

begin

New (SP, Init (1, 1, 25, 'первое_имя');

SP^.Put ('Владимир');

SP^.Display;

.

.

.

Dispose (SP, Done);

end.

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

28. Компоненты и область действия

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

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

Рассмотрим следующую схему описания типа, содержащего компоненты всех допустимых областей действия:

Type

<имя типа> = Object [(<имя типа родителя>)]

Private

<частные описания полей и методов>

Protected

<защищенные описания полей и методов>

Public

<общедоступные описания полей и методов>

end;

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

Защищенные поля и методы, то есть описанные в разделе Protected, видимы в модуле, где определяется тип, и потомкам данного типа.

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

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

29. Методы

Описание метода внутри объектного типа соответствует опережающему описанию метода (forward). Таким образом, где-нибудь после описания объектного типа, но внутри той же самой области действия, что и область действия описания объектного типа, метод должен реализоваться путем определения его описания.

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

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

Виртуальные методы

По умолчанию методы являются статическими, однако они могут, за исключением конструкторов, быть виртуальными (посредством включения директивы virtual в описание метода). Компилятор разрешает ссылки на вызовы статических методов во время процесса компиляции, тогда как вызовы виртуальных методов разрешаются во время выполнения. Это иногда называют поздним связыванием.

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

Динамические методы

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

Описание динамического метода эквивалентно описанию виртуального метода, но описание динамического метода должно включать в себя индекс динамического метода, который указывается непосредственно за ключевым словом virtual. Индекс динамического метода должен быть целочисленной константой в диапазоне от 1 до 656535 и должен быть уникальным среди индексов других динамических методов, содержащихся в объектном типе или его предках. Например:

procedure FileOpen(var Msg: TMessage); virtual 100;

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

30. Конструкторы и деструкторы

Конструкторы и деструкторы являются специализированными формами методов. Используемые в связи с расширенным синтаксисом стандартных процедур New и Dispose конструкторы и деструкторы обладают способностью размещения и удаления динамических объектов. Кроме того, конструкторы имеют возможность выполнить требуемую инициализацию объектов, содержащих виртуальные методы. Как и все другие методы, конструкторы и деструкторы могут наследоваться, а объекты могут содержать любое число конструкторов и деструкторов.

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

Приведем несколько примеров конструкторов:

constructor Field.Copy(var F: Field);

begin

Self:= F;

end;

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

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

Примечание

Деструктор может быть виртуальным и часто является таковым. Деструктор редко имеет параметры. Приведем несколько примеров деструкторов:

destructor Field.Done;

begin

FreeMem(Name, Length (Name^) + 1);

end;

destructor StrField.Done;

begin

FreeMem(Value, Len);

Field.Done;

end;

Деструктор дочернего типа, такой как указанный выше TStrField. Done, обычно сначала удаляет введенные в порожденном типе поля указателей, а затем в качестве последнего действия вызывает соответствующий сборщик-деструктор непосредственного родителя для удаления унаследованных полей указателей объекта.



31. Деструкторы

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

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

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

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

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

Полиморфические объекты - это те объекты, которые были присвоены родительскому типу благодаря правилам совместимости расширенных типов Borland Pascal. Термин «полиморфический» является подходящим, так как код, обрабатывающий объект, «не знает» точно во время компиляции, какой тип объекта ему придется в конце концов обработать. Единственное, что он знает, - это то, что этот объект принадлежит иерархии объектов, являющихся потомками указанного типа объекта.

Сам по себе метод деструктора может быть пуст и выполнять только эту функцию:

destructor AnObject.Done;

begin

end;

То, что делается полезного в этом деструкторе, не является достоянием его тела, однако при этом компилятором генерируется код эпилога в ответ на зарезервированное слово destructor. Это напоминает модуль, который ничего не экспортирует, но который осуществляет некоторые невидимые действия за счет выполнения своей секции инициализации перед стартом программы. Все действия происходят «за кулисами».

32. Виртуальные методы

Метод становится виртуальным, если за его объявлением в типе объекта стоит новое зарезервированное слово virtual. Если объявляется метод в родительском типе как virtual, то все методы с аналогичными именами в дочерних типах также должны объявляться виртуальными во избежание ошибки компилятора.

Ниже приведены объекты из примера платежной ведомости, должным образом виртуализированные:

tyрe

PEmрloyee = ^TEmployee;

TEmployee = object

Name, Title: string[25];

Rate: Real;

constructor Init (AName, ATitle: String; ARate: Real);

function GetPayAmount: Real; virtual;

function GetName: String;

function GetTitle: String;

function GetRate: Real;

рrocedure Show; virtual;

end;

PHourly = ^THourly;

THourly = object(TEmployee);

Time: Integer;

constructor Init (AName, ATitle: String; ARate: Real;

Time: Integer);

function GetPayAmount: Real; virtual;

function GetTime: Integer;

end;

PSalaried = ^TSalaried;

TSalaried = object(TEmployee);

function GetPayAmount: Real; virtual;

end;

PCommissioned = ^TCommissioned;

TCommissioned = object(Salaried);

Commission: Real;

SalesAmount: Real;

constructor Init (AName, ATitle: String; ARate,

ACommission, ASalesAmount: Real);

function GetPayAmount: Real; virtual;

end;

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

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

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

33. Поля данных объекта и формальные параметры метода

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

procedure CrunchIt(Crunchee: MyDataRec, Crunchby,

ErrorCode: integer);

var

A, B: char;

ErrorCode: integer;

begin

.

.

.

end;

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

Локальные переменные процедуры и ее формальные параметры совместно используют общую область действия и поэтому не могут быть идентичными. Будет получено сообщение «Error 4: Duplicate identifier» (Ошибка 4; Повторение идентификатора), если попытаться компилировать что-либо подобное. Та же ошибка возникает при попытке присвоить формальному параметру метода имени поля объекта, которому данный метод принадлежит.

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

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



34. Инкапсуляция

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

Например, объекты TEmployee и THourly написаны таким образом, что совершенно исключена необходимость прямого обращения к их внутренним полям данных:

type

TEmployee = object

Name, Title: string[25];

Rate: Real;

procedure Init (AName, ATitle: string; ARate: Real);

function GetName: String;

function GetTitle: String;

function GetRate: Real;

function GetPayAmount: Real;

end;

THourly = object(TEmployee)

Time: Integer;

procedure Init(AName, ATitle: string; ARate:

Real, Atime: Integer);

function GetPayAmount: Real;

end;

Здесь присутствуют только четыре поля данных: Name, Title, Rate и Time. Методы GetName и GetTitle выводят фамилию работающего и его должность соответственно. Метод GetPayAmount использует Rate, а в случае работающего THourly и Time для вычисления суммы выплат работающему. Здесь уже нет необходимости обращаться непосредственно к этим полям данных.

Предположив существование экземпляра AnHourly типа THourly, мы могли бы использовать набор методов для манипулирования полями данных AnHourly, например:

with AnHourly do

begin

Init (Aleksandr Petrov, Fork lift operator' 12.95, 62);

{Выводит на экран фамилию, должность и сумму

выплат}

Show;

end;

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

35. Расширяющиеся объекты

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

Определим дочерний по отношению к TEmployee тип, представляющий работника, которому платится часовая ставка, в следующем примере:

const

PayPeriods = 26; { периоды выплат }

OvertimeThreshold = 80; { на период выплаты }

OvertimeFactor = 1.5; { почасовой коэффициент }

type

THourly = object(TEmployee)

Time: Integer;

procedure Init(AName, ATitle: string; ARate:

Real, Atime: Integer);

function GetPayAmount: Real;

end;

procedure THourly.Init(AName, ATitle: string;

ARate: Real, Atime: Integer);

begin

TEmployee.Init(AName, ATitle, ARate);

Time:= ATime;

end;

function THourly.GetPayAmount: Real;

var

Overtime: Integer;

begin

Overtime:= Time - OvertimeThreshold;

if Overtime > 0 then

GetPayAmount:= RoundPay(OvertimeThreshold * Rate

+

Rate OverTime * OvertimeFactor

* Rate)

else

GetPayAmount:= RoundPay(Time * Rate)

end;

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

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

36. Совместимость типов объектов

Наследование до некоторой степени изменяет правила совместимости типов в Borland Pascal. Потомок наследует совместимость типов всех своих предков.

Эта расширенная совместимость типов принимает три формы:

1) между реализациями объектов;

2) между указателями на реализации объектов;

3) между формальными и фактическими параметрами. Совместимость типов расширяется только от потомка к родителю.

Например, TSalaried является потомком TEmployee, а TCommissioned - потомком TSalaried. Рассмотрим следующие описания:

var

AnEmрloyee: TEmployee;

ASalaried: TSalaried;

PCommissioned: TCommissioned;

TEmployeePtr: ^TEmployee;

TSalariedPtr: ^TSalaried;

TCommissionedPtr: ^TCommissioned;

При данных описаниях справедливы следующие операторы присваивания:

AnEmрloyee:=ASalaried;

ASalaried:= ACommissioned;

TCommissionedPtr:= ACommissioned;

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

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

AnEmрloyee:= ACommissioned;

Только поля Name, Title и Rate из ACommissionedбудут скопированы в AnEmployee, так как только эти поля являются общими для TCommissioned и TEmployee. Совместимость типов работает также между указателями на типы объектов и подчиняется тем же общим правилам, что и для реализаций объектов. Указатель на потомка может быть присвоен указателю на родителя. Если дать предыдущие определения, то следующие присваивания указателей будут допустимыми:

TSalariedPtr:= TCommissionedPtr;

TEmployeePtr:= TSalariedPtr;

TEmployeePtr:= PCommissionedPtr;

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

procedure CalcFedTax(Victim: TSalaried);

то допустимыми типами фактических параметров могут быть TSalaried или TCommissioned, но не тип TEmployee. Victim также может быть параметром-переменной. При этом выполняются те же правила совместимости.

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

37. Об ассемблере

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

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

По-настоящему решить проблемы, связанные с аппаратурой (или, даже более того, зависящие от аппаратуры, как, к примеру, повышение быстродействия программы), невозможно без знания ассемблера.

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

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

38. Программная модель микропроцессора

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

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

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

Чтобы собрать воедино все понятия, характеризующие компьютер с точки зрения его функциональных программно-управляемых свойств, существует специальный термин - архитектура ЭВМ.

Впервые понятие архитектура ЭВМ стало упоминаться с появлением машин 3-го поколения для их сравнительной оценки.

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

Данные регистры можно разделить на две большие группы:

1) 16 пользовательских регистров;

2) 16 системных регистров.

В программах на языке Ассемблера регистры используются очень интенсивно. Большинство регистров имеют определенное функциональное назначение.

Помимо перечисленных выше регистров, фирмы-разработчики процессоров внедряют в программную модель дополнительные регистры, предназначенные для оптимизации определенных классов вычислений. Так, в семействе процессоров Pentium Pro (MMX) корпорации Intel было внедрено MMX расширение от Intel. Оно включает в себя 8 (MM0-MM7) 64-битных регистров и позволяет производить целочисленные операции над парами нескольких новых типов данных:

1) восемь упакованных байт;

2) четыре упакованных слова;

3) два двойных слова;

4) учетверенное слово;

Другими словами, одной инструкцией MMX расширения программист может, например, сложить между собой два двойных слова. Физически никаких новых регистров добавлено не было. MM0-MM7 это мантиссы (младшие 64 бита) стека 80 битных FPU (floating point unit - сопроцессор) регистров.

Кроме того, на данный момент существуют следующие расширения программной модели - 3DNOW! от AMD; SSE, SSE2, SSE3, SSE4. Последние 4 расширения поддерживаются как процессорами фирмы AMD, так и процессорами корпорации Intel.

39. Пользовательские регистры

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

1) восемь 32-битных регистров, которые могут использоваться программистами для хранения данных и адресов (их еще называют регистрами общего назначения (РОН)):

- eax/ax/ah/al;

- ebx/bx/bh/bl;

- edx/dx/dh/dl;

- ecx/cx/ch/cl;

- ebp/bp;

- esi/si;

- edi/di;

- esp/sp.

2) шесть регистров сегментов:

- cs;

- ds;

- ss;

- es;

- fs;

- gs;

3) регистры состояния и управления:

- регистр флагов eflags/flags;

- регистр указателя команды eip/ip.

На следующем рисунке показаны основные регистры микропроцессора:

Регистры общего назначения

40. Регистры общего назначения

Все регистры этой группы позволяют обращаться к своим «младшим» частям. Использовать для самостоятельной адресации можно только младшие 16- и 8-битные части этих регистров. Старшие 16 бит этих регистров как самостоятельные объекты недоступны.

Перечислим регистры, относящиеся к группе регистров общего назначения. Так как эти регистры физически находятся в микропроцессоре внутри арифметико-логического устройства (АЛУ), то их еще называют регистрами АЛУ:

1) eax/ax/ah/al (Accumulator register) - аккумулятор. Применяется для хранения промежуточных данных. В некоторых командах использование этого регистра обязательно;

2) ebx/bx/bh/bl (Base register) - базовый регистр. Применяется для хранения базового адреса некоторого объекта в памяти;

3) ecx/cx/ch/cl (Count register) - регистр-счетчик. Применяется в командах, производящих некоторые повторяющиеся действия. Его использование зачастую неявно и скрыто в алгоритме работы соответствующей команды.

К примеру, команда организации цикла loop, кроме передачи управления команде, находящейся по некоторому адресу, анализирует и уменьшает на единицу значение регистра ecx/cx;

4) edx/dx/dh/dl (Data register) - регистр данных.

Так же, как и регистр eax/ax/ah/al, он хранит промежуточные данные. В некоторых командах его использование обязательно; для некоторых команд это происходит неявно.

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

1) esi/si (Source Index register) - индекс источника. Этот регистр в цепочечных операциях содержит текущий адрес элемента в цепочке-источнике;

2) edi/di (Destination Index register) - индекс приемника (получателя). Этот регистр в цепочечных операциях содержит текущий адрес в цепочке-приемнике.

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

1) esp/sp (Stack Pointer register) - регистр указателя стека. Содержит указатель вершины стека в текущем сегменте стека.

2) ebp/bp (Base Pointer register) - регистр указателя базы кадра стека. Предназначен для организации произвольного доступа к данным внутри стека.

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

41. Сегментные регистры

В программной модели микропроцессора имеется шесть сегментных регистров: cs, ss, ds, es, gs, fs.

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

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

Микропроцессор поддерживает следующие типы сегментов.

1. Сегмент кода. Содержит команды программы. Для доступа к этому сегменту служит регистр cs (code segment register) - сегментный регистр кода. Он содержит адрес сегмента с машинными командами, к которому имеет доступ микропроцессор (т. е. эти команды загружаются в конвейер микропроцессора).

2. Сегмент данных. Содержит обрабатываемые программой данные. Для доступа к этому сегменту служит регистр ds (data segment register) - сегментный регистр данных, который хранит адрес сегмента данных текущей программы.

3. Сегмент стека. Этот сегмент представляет собой область памяти, называемую стеком. Работу со стеком микропроцессор организует по следующему принципу: последний записанный в эту область элемент выбирается первым. Для доступа к этому сегменту служит регистр ss (stack segment register) - сегментный регистр стека, содержащий адрес сегмента стека.

4. Дополнительный сегмент данных. Не явно алгоритмы выполнения большинства машинных команд предполагают, что обрабатываемые ими данные расположены в сегменте данных, адрес которого находится в сегментном регистре ds. Если программе недостаточно одного сегмента данных, то она имеет возможность использовать еще три дополнительных сегмента данных. Но в отличие от основного сегмента данных, адрес которого содержится в сегментном регистре ds, при использовании дополнительных сегментов данных их адреса требуется указывать явно с помощью специальных префиксов переопределения сегментов в команде. Адреса дополнительных сегментов данных должны содержаться в регистрах es, gs, fs (extension data segment registers).

42. Регистры состояния и управления

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

1) регистр флагов eflags/flags;

2) регистр указателя команды eip/ip.

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

1. eflags/flags (flag register) - регистр флагов. Разрядность eflags/flags - 32/16 бит. Отдельные биты данного регистра имеют определенное функциональное назначение и называются флагами. Младшая часть этого регистра полностью аналогична регистру flags для i8086.

Исходя из особенностей использования флаги регистра eflags/flags можно разделить на три группы:

1) восемь флагов состояния.

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

2) один флаг управления.

Обозначается df (Directory Flag). Он находится в 10-м бите регистра eflags и используется цепочечными командами. Значение флага df определяет направление поэлементной обработки в этих операциях: от начала строки к концу (df = 0) либо наоборот, от конца строки к ее началу (df = 1). Для работы с флагом df существуют специальные команды: cld (снять флаг df) и std (установить флаг df).

Применение этих команд позволяет привести флаг df в соответствие с алгоритмом и обеспечить автоматическое увеличение или уменьшение счетчиков при выполнении операций со строками. 3) пять системных флагов.

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

2. eip/ip (Instraction Pointer register) - регистр-указатель команд. Регистр eip/ip имеет разрядность 32/16 бит и содержит смещение следующей подлежащей выполнению команды относительно содержимого сегментного регистра cs в текущем сегменте команд. Этот регистр непосредственно недоступен программисту, но загрузка и изменение его значения производятся различными командами управления, к которым относятся команды условных и безусловных переходов, вызова процедур и возврата из процедур. Возникновение прерываний также приводит к модификации регистра eip/ip.

43. Системные регистры микропроцессора

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

Системные регистры можно разделить на три группы:

1) четыре регистра управления;

В группу регистров управления входят 4 регистра:

- cr0;

- cr1;

- cr2;

- cr3;

2) четыре регистра системных адресов (которые также называются регистрами управления памятью);

К регистрам системных адресов относятся следующие регистры:

- регистр таблицы глобальных дескрипторов gdtr;

- регистр таблицы локальных дескрипторов Idtr;

- регистр таблицы дескрипторов прерываний idtr;

- 16-битовый регистр задачи tr;

3) восемь регистров отладки. К их числу относятся:

- dr0;

- dr1;

- dr2;

- dr3;

- dr4;

- dr5;

- dr6;

- dr7.

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



44. Регистры управления

В группу регистров управления входят четыре регистра: cr0, cr1, cr2, cr3. Эти регистры предназначены для общего управления системой. Регистры управления доступны только программам с уровнем привилегий 0.

Хотя микропроцессор имеет четыре регистра управления, доступными являются только три из них - исключается cr1, функции которого пока не определены (он зарезервирован для будущего использования).

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

Назначение системных флагов:

1) pe (Protect Enable), бит 0 - разрешение защищенного режима работы. Состояние этого флага показывает, в каком из двух режимов - реальном (pe = 0) или защищенном (pe = 1) - работает микропроцессор в данный момент времени;

2) mp (Math Present), бит 1 - наличие сопроцессора. Всегда 1;

3) ts (Task Switched), бит 3 - переключение задач. Процессор автоматически устанавливает этот бит при переключении на выполнение другой задачи;

4) am (Alignment Mask), бит 18 - маска выравнивания.

Этот бит разрешает (am = 1) или запрещает (am = 0) контроль выравнивания;

5) cd (Cache Disable), бит 30 - запрещение кеш-па-мяти.

С помощью этого бита можно запретить (cd = 1) или разрешить (cd = 0) использование внутренней кеш-памяти (кеш-памяти первого уровня);

6) pg (PaGing), бит 31 - разрешение (pg = 1) или запрещение (pg = 0) страничного преобразования.

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

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

В такой ситуации в микропроцессоре возникает исключительная ситуация с номером 14, и линейный 32-битный адрес команды, вызвавшей это исключение, записывается в регистр cr2. Имея эту информацию, обработчик исключения 14 определяет нужную страницу, осуществляет ее подкачку в память и возобновляет нормальную работу программы;

Регистр cr3 также используется при страничной организации памяти. Это так называемый регистр каталога страниц первого уровня. Он содержит 20-битный физический базовый адрес каталога страниц текущей задачи. Этот каталог содержит 1024 32-битных дескриптора, каждый из которых содержит адрес таблицы страниц второго уровня. В свою очередь, каждая из таблиц страниц второго уровня содержит 1024 32-битных дескриптора, адресующих страничные кадры в памяти. Размер страничного кадра - 4 Кбайта.

45. Регистры системных адресов

Эти регистры еще называют регистрами управления памятью.

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

1) глобальное - общее для всех задач;

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

1) регистра таблицы глобальных дескрипторов gdtr (Global Descriptor Table Register), имеющего размер 48 бит и содержащего 32-битовый (биты 16-47) базовый адрес глобальной дескрипторной таблицы GDT и 16-битовое (биты 0--15) значение предела, представляющее собой размер в байтах таблицы GDT;

2) регистра таблицы локальных дескрипторов ldtr (Local Descriptor Table Register), имеющего размер 16 бит и содержащего так называемый селектор дескриптора локальной дескрипторной таблицы LDT. Этот селектор является указателем в таблице GDT, который и описывает сегмент, содержащий локальную дескрипторную таблицу LDT;

3) регистра таблицы дескрипторов прерываний idtr (Interrupt Descriptor Table Register), имеющего размер 48 бит и содержащего 32-битовый (биты 16-47) базовый адрес дескрипторной таблицы прерываний IDT и 16-битовое (биты 0--15) значение предела, представляющее собой размер в байтах таблицы IDT;

4) 16-битового регистра задачи tr (Task Register), который подобно регистру ldtr, содержит селектор, т. е. указатель на дескриптор в таблице GDT. Этот дескриптор описывает текущий сегмент состояния задачи (TSS - Task Segment Status). Этот сегмент создается для каждой задачи в системе, имеет жестко регламентированную структуру и содержит контекст (текущее состояние) задачи. Основное назначение сегментов TSS - сохранять текущее состояние задачи в момент переключения на другую задачу.

46. Регистры отладки

Это очень интересная группа регистров, предназначенных для аппаратной отладки. Средства аппаратной отладки впервые появились в микропроцессоре i486. Аппаратно микропроцессор содержит восемь регистров отладки, но реально из них используются только шесть.

Регистры dr0, dr1, dr2, dr3 имеют разрядность 32 бита и предназначены для задания линейных адресов четырех точек прерывания. Используемый при этом механизм следующий: любой формируемый текущей программой адрес сравнивается с адресами в регистрах dr0 … dr3, и при совпадении генерируется исключение отладки с номером 1.

...