Бусыгин Б.С., Коротенко Г.М., Коротенко Л.М. Введение в современную информатику

Подождите немного. Документ загружается.

360

расположить эти диски в таком же порядке на третьем штырьке. Диски можно

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

1 2 3

Рис. 8.88. Вид игры «Ханойская башня»

Алгоритм решения головоломки следующий:

1.1. Переместить верхние n-1 дисков на 2-ой штырёк.

1.2. Нижний диск первого штырька переместить на третий.

1.3. Переместить n-1 дисков на третий штырёк, используя первый в

качестве вспомагательного.

1.4. Повторять, пока на третьем штырьке не будет сформирована новая

пирамида.

Конечная задача сводится к двум основным:

–нескольких о переносе (n-1)-го диска;

–одной задачи о переносе одного диска.

Естественно, что для n=1 необходимо всего одно перемещение.

2. Разработать программу с испоьзованием множеств для решения

следующей задачи: пользователю предлагается ввести одну из букв латинского

алфавита: A, L, P или T, причём всё равно на каком регистре – прописном или

строчном. Если то, что введёт пользователь, будет отлично от каждой из

введённых букв, программа должна напечатать сообщение, что приглашает к

повторному введению.

3. В текстовом файле содержатся длины сторон 20 прямоугольных

параллелепипедов. Вычислить объёмы этих параллелепипедов. Результаты

расчётов записать в файл в виде таблицы, содержащей следующие столбцы:

–длина первой стороны параллелепипеда;

–длина второй стороны параллелепипеда;

–длина третьей стороны параллелепипеда;

–объём параллелепипеда.

Позаботьтесь о соответствующих заголовках для столбцов.

Файл с выходными данными сформируйте с помощью текстового

редактора.

4. Трансформируйте текст программы о доставке пакетов в сети (рис. 8.87)

так, чтобы в процедуре глобальные параметры передавались через формальные

параметры.

361

8.27. Записи, ссылки, динамические переменные и структуры

8.27.1. Тип “запись” (record) и оператор присоединения with

Для компактного представления комбинаций разнотипных данных в Турбо

Паскале их можно объединять в структуры-записи. Каждая запись состоит из

объявленного числа полей и определяется конструкцией:

Var

InfRec : Record;

Поле1 : Тип_поля1;

Поле2 : Тип_поля2;

. . .

ПолеN : Тип_поляN

End;

Где Тип_поляN, это некоторый тип данных ТП. Обратите внимание на то,

что после служебного слова Var перед описанием типа данных

Record

ставится знак (:), а после Type – знак (=) (смотри следующий пример).

Если типы нескольких полей совпадают, то имена полей могут быть

просто перечислены, например – x,y :

Type

PointRecType = record x,y : Integer end;

Var

Point : PointRecType;

Px, Py : Integer;

. . .

{Обращение к полям записи:}

Px := Point.x;

Py := Point.y;

. . .

Так как имена полей «спрятаны» в средине типа, то они могут дублировать

«внешние» переменные и поля в других описаниях записей:

Type

PointRecType = record x, y : integer end;

ColorPointType = record

x, y : integer;

color : word

end;

Var

X, Y : integer;

Point : pointRecType;

ColorPoint : ColorPointRecType;

. . .

Обратите внимание также на то, что в этом примере x, Point.x и

ColorPoint.x – совсем разные значения.

362

Например, Вы можете разработать свои пользовательские типы данных

(рис. 8.89). Связь значения в операторе вариантной части записи с

соответствующими значениями компилятором никак не отслеживаются. Запись

с вариантами может использоваться, например, для чтения полей разных типов

из файлов базы данных в одну и ту же область памяти.

Переменная типа "запись" может участвовать только в операциях

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

относятся к типу этого поля. Для доступа к полям записи применяется

квалификационное имя (рис. 8.89):

Users[3].Processor

Для облегчения работы с полями записей вводится оператор

присоединения – With:

With <Имя_Переменной_Записи> do <Оператор>;

Внутри оператора With (он может быть составным) обращения к полям

записи производится прямо (рис. 8.90). Внутри области действия оператора

присоединения With могут указываться и переменные, не имеющие отношения

к записи, однако необходимо придерживаться следующих правил (рис. 8.91).

В случае, если одно из полей записи само является записью и снова содержит

поля записи, оператор присоединения можно распространить на несколько

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

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

Type

OS = (MS_DOS, CPM, MPM, Unix);

CPU = (I8088, I8086, I80186, I80286, I80386);

Computer = Record

OperatingSystem : Array[1..4] of OS;

Processor : CPU;

Price : Real;

MadeIn : String[80];

End;

Var

Users : Array[1..50] of Computer;

Type

List = record

Name : String[40];

BirthDay : Word;

Case Citizen : Boolean Of

True : (BirthPlace : String[40]);

False: (Country : String[20];

Port : String[18];

ExitDate : Word;

EntryDate: Word);

end;

Рис. 8.89. Пример конструирования элементов типа “запись”

363

With ИмяЗаписи.Поле_Запись do

Begin

{Обращения к полям Поле_Запись, то есть к тем, которым предшествовала

конструкция “ИмяЗаписи.Поле_Запись”}

End; {With}

8.27.2. Система адресации MS-DOS

Адресуемое пространство памяти в MS-DOS организовано сегментами,

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

Если Вам известен сегмент, то дальнейшее уточнение адреса происходит по его

смещению, то есть номеру байта от начала сегмента. Таким образом, любая

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

{Два эквивалентных способа обращения к полям записи рис. 8.89}

{Перший:}

Users.OperatingSystem:=MS_DOS;

Users.Processor :=I80286;

Users.Price :=2250;

Users.MadeIn :=’Taiwan’;

{Другий:}

With Users Do

Begin

OperatingSystem:=MS_DOS;

Processor :=I80286;

Price :=2250;

MadeIn :=’Taiwan’;

End;

Рис. 8.90. Два эквивалентных способа обращения к полям записи

Program Main;

Var

X, y, z : integer;

RecXY : record x, y : Integer end;

Begin

X := 10; Y := 20;

With RecXY do

Begin

X := 3.14 * Main.X / Z; {«Main» - квалификатор}

Y := 3.14 * Main.Y / Z; {для «развязки» совпдающих

идентификаторов. Для Z не требуется}

End; {With}

. . .

End.

Рис. 8.91. Переменные, не имеющие отношения к записи в операторе

With

364

<СЕГМЕНТ> : <СМЕЩЕНИЕ>,

который занимает четыре байта: 2 байта <СЕГМЕНТ> и 2 байта

<СМЕЩЕНИЕ>. Такой способ позволяет адресовать большее пространство

оперативной памяти меньшими чис

лами. Чтобы Вам было проще это

представить, приведём такой пример. В некотором районе построенно 20 домов

по 99 квартир. Необходимо найти способ адресации, чтобы не выходить за

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

возможности представлять максимальное число:

20×99 = 1980,

которое занимает четыре разряда. Выход из такой ситуации состоит в

двойной адресации:

<ДОМ> : <КВАРТИРА>

Тогда любую квартиру Вы сможете найти по номеру дома и номеру

квартиры в этом доме. Например, дом 10, квартира 67:

<10> : <67>,

в то время, как при сквозной нумерации для хранения адреса объекта

понадобилось бы три разряда: 10×67 = 670.

8.27.3. Тип Pointer

Основным механизмом для организации динамических данных в ТП

является выделение в специальной области памяти, называемой «куча», участка

(блока) необходимого размера и сохранения адреса начала этого участка в

специальной переменной в формате <СЕГМЕНТ> : <СМЕЩЕНИЕ>.

Условимся называть далее указателем переменные, которые имеют

обобщённый тип Pointer – указатель. То есть можно объявлять переменные,

значениями которых будут адреса ячеек памяти:

Var

P : Pointer; {Переменная-указатель}

Значение этого типа занимают 4 байти памяти и содержат адрес начала

любого объекта ТП. Адрес сохраняется как два слова, то есть две переменные

типа Word (каждая из них занимает в памяти 2 байта): одно из них задаёт

сегмент, а другое – смещение. Значение указателя не может быть выведенным

на экран или на печать. Его нужно предварительно расшифровувать.

Имейте ввиду, что компилятор ТП всегда должен знать, какой объект

адресуется, чтобы корректно его обрабатывать. Вспомните, что переменная

типа Integer занимает в памяти 2 байта, переменная типа LongInt – 4 байта,

переменная типа Real – 6 байтов, переменная типа Byte занимает в памяти 1

байт и т.д (см. Приложение 7).

Ещё одна из тонкостей работы в ТП состоит в том, что Вы должны

соблюдать все правила «правописания» его конструкций. К примеру, когда Вы

пишете письмо к близкому человеку, то отступаетете все необходимые абзацы,

365

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

т.д. Так вот, программа, которую Вы пишете для транслятора, тоже должна

быть грамотно написана, чтобы он смог её правильно понять...

8.27.4. Средства работы с адресами

Для начала рассмотрим функции для работы с адресами разных объектов

ТП (табл.. 52).

Таблица 52

Функции для работы с адресами разных объектов ТП

Функция : Тип Возвращаемое значение

Addr(X) : Pointer

Ссылка на начало объекта X в памяти

Seg(X) : Word

Сегмент, в котором сохраняется объект X

Ofs(X) : Word

Смещение в сегменте для объекта X

Ptr(S, 0 : Word)

: Pointer

Ссылка на место в памяти, которое задано

значениями смещения 0 и сегмента S

SizeOf(X) : Word

Размер объекта X в байтах

Операция @X : Pointer

Возвращает ссылку на начало объекта X в памяти

(аналог функции Addr)

Функции Addr(X), Seg(X) и Ofs(X), а также оператор @ возвращают

адрес объекта X или компоненты этого адреса. Под переменной X можно

понимать любой объект: переенные встроенных типов ТП, пользовательских

типов, объекты, процедуры и функции (но не константы).

Функция Addr(X) и оператор @ возвращают значения типа Pointer –

адрес объекта X. Их действие одинаково:

Var

X : String;

p, q : Pointer;

. . .

p:=Addr(X);

q:=@X; {Теперь p=q , то есть их адреса равны: они указывают на один

и тот же объект}

Как Вы уже знаете, значения типа Pointer не может быть выведено на

экран. Но поскольку этот тип состоит из двух слов (Word), хранящих сегмент и

смещение, их можно вывести поодиночке, используя функции Seg и Ofs (обе

типа Word):

WriteLn(‘Сегмент ’, Seg(p), ‘ смещение ’, Ofs(p));

Функция Ptr(Seg, Ofs : Word) выполняет противоположную

функции Addr(X) работу: она организовывает ссылку на место в памяти

которое определено заданным сегментом и смещением. Необходимость в такой

функции может возникать, когда требуется наложить динамическую структуру

на системную область памяти. Так, например, известно, что образ текстового

366

экрана начинается с адреса $B000:$0000 и занимает 4 000 байт (цветной и

чорно-белый режимы, 80 столбцов на 25 строк), но можно “наложить” на него

некоторую структуру, например, массив, используя ссылку на такой массив и

функцию Ptr (рис. 8.92):

Функция SizeOf(X) : Word возвращает объём в байтах, который

занимает объект X. Причём X может быть не только переменной, но и

идентификатором типа (рис. 8.93):

Значение SizeOf(строка) всегда даёт максимальное значение длины

строки. Реальное значение даёт функция Legth.

8.27.5. Ссылочные переменные

Все ссылочные переменные имеют однаковый размер, равный 4-м байтам,

и содержат адреса начала участка оперативной памяти в ктором размещена

конкретная динамическая структура данных (Integer, Array, Record и т.д.),

например:

Type

VideoArray = Array[0..3999] of Byte;

Var

V : ^VideoArray; {Ссылка на структуру}

Begin

V:=Ptr($B000, 0); {Далее V^[i] обращается непосредственно к

ячейкам видеопамяти в текстовом режиме}

. . .

End.

Рис. 8.92. Использование функции

Ptr(Seg,Ofs : Word)

Program ObjectSizeOf;

Type

XType = Array [1..10,1..10] of Byte;

Const

L : LongInt = 123456;

Var

X : String;

Begin

WriteLn('Xtype =', SizeOf(XType):5,

' L = ', SizeOf(L):5,

' X = ',SizeOf(X));

ReadLn

End.

Результат работ программы:

Xtype = 100 L = 4 X = 256

Рис. 8.93. Використання функції SizeOf(X) : Word

367

. . .

Var

J : ^Integer; {Ссылочная переменная, указывающая на целое значение}

I : Integer; {Целая переменная}

. . .

J := 200;

I := 200;

. . .

Разница между целой переменной I (тип Integer) (рис. 8.94, а) и ссылочной

переменной J (^Integer) на целую переменную заключается в следующем

(см. рис. 8.94, б):

Чтобы ссылка ни на что не указывала, ей присваивается значение Nil:

J := Nil; {или nil}

Это определённая константа типа Pointer, соответствующая адресу

0000:0000.

Подытоживая всё вишесказанное можем сделать вывод, что для

определения ссылочной переменной в ТП необходимо описать её как

ссылочный тип:

Type

ИмяСсылочногоТипа = ^ИмяБазовогоТипа;

{Где ИмяБазовогоТипа – любой идентификатор типа (Real,

Integer и т.д.), это необходимо компилятору ТП для

организации работы программы}

В результате этого определения создаваемые затем ссылочные переменные

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

переменные базового типа:

I – адрес, где

содержится значение

200

значение

200

значення

200

адрес, где содержится значение

200 в формате:

<СЕГМЕНТ> : <СМЕЩЕНИЕ>

J – адрес, где

содержится адрес

числа 200

а)

б)

Рис. 8.94. Содержимое данных разного типа I и J

Ссылается

368

Type {БАЗОВЫЕ ТИПЫ ЯЗЫКА ТУРБО ПАСКАЛЬ}

DimType = Array [1..10000] of Real; {Массив}

RecType = record ... end; {Запись}

{ ССЫЛОЧНЫЕ ТИПЫ}

IntPtr = ^Integer; {Ссылка на целое значение}

Dim Ptr = ^DimType; { Ссылка на массив данных}

RecPtr = ^RecType; { Ссылка на запись}

XXXPtr = Pointer; { Ссылка «вообще» - указатель}

8.27.6. Операция разименования

Суть этой операции состоит в переходе от ссылочной переменной через

адрес, на который она ссылается к значению, на которое она указывает. При

этом следом за ссылочной переменной указывается символ "^":

. . .

Var

I, J : ^Integer;

. . .

I:=2;

J:=4;

J^:=I^; {Копируем содержимое I в J. Сейчас J указывает на значение 2

(рис. 8.95, а)}

J:=I; {Или можно так: идентификаторы I и J теперь тоже указывают на

значение 2 (рис. 8.95, б)}

Однако эти операции выполняются компилятором языка ТП по разному

(рис. 8.95, а, б).

Ячейка со значением 4 превращается в так называемый «мусор»,

поскольку к ней теперь нет доступа.

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

есть нет ошибки в присваивании:

DimPtr := RecPtr;

Однако после разименования начинается контроль типов объектов по

определённым адресам:

DimPtr^ := RecPtr^; {Даёт ошибку!!!}

Разименованные ссылки на структуры (массивы) индексируются или

разделяются на поля записи обычным образом:

DimPtr^[i] – доступ к элементу I динамического массива

RecPtr^.Поле – доступ к полю динамической записи

369

8.27.7. Размещение динамических переменных.

Процедуры New и GetMem

Размещение динамических переменных в ТП выполняется процедурами

New(Var P: Pointer) и GetMem(Var P: Pointer) (табл. 52).

Таблица 52.

Процедуры размещения динамических переменных

Процедуры и функции Назначение

New(Var P : Pointer) или

New(ТипСсылка) : Pointer

Отводит место для хранения

динамической переменной P^ и

присваивает её адрес ссылке P

GetMem(Var P: Pointer;

Size : Word)

Отводит место в Size (байт в куче)

(Heap), присваивая адресу его

начала указатель (ссылку) P

Как Вы уже знаете, в ТП имеется специальный не типизированный

указатель Pointer. Он объявляется стандартным образом:

. . .

Var

X : Pointer;

. . .

Не типизированному указателю может быть назначено значение любого

типизированного указателя или наоборот. Он выполняет роль своеобразного

буфера для сохранения адреса динамической переменной любого типа. Пусть

имеем описание:

I^ = <адрес 2>

J^ = <адрес 4>

I^ := J^;

I := J;

б)

а)

Рис. 8.95. Примеры операций разименования