Часть 2-Основы программирования (Delphi)

Function MulC (x,y: Complex): Complex; // Умножение комплексных чисел begin

Result.re := x.re * y.re - x.im * y.im; Result.im := x.re * y.im + x.im * y.re end; //MulC

Function DivC (x,y: Complex): Complex; // Деление комплексных чисел var z: Real;

begin

z := sqr(y.re) + sqr(y.im);

// Защищаем программу от краха в случае, когда z=0 try

Result.re := (x.re * у.re + x.im * y.im) / z; Result.im := (x.re * y.im - x.im * y.re) / z;

except

Result.re := l.le309; Result.im := l.le309;

end

end; //DivC

end.

Текст модуля следует сохранить в файле cmplx.pas: имя файла должно совпадать с именем модуля - только в этом случае Delphi сможет автоматически найти модуль и следить за его обновлением.

После создания модуля его имя нужно упомянуть в предложении uses того модуля, в котором будут использоваться вновь созданные подпрограммы, типы, константы (в нашем модуле - тип complex, подпрограммы AddC, SubC, MulC, DivC). Пусть, например, при каждом щелчке по кнопке Button1 учебной программы создается пара случайных комплексных чисел, над которыми осуществляются все четыре арифметических действия. Тогда обработчик Button1Click мог бы быть таким:

implementation uses Cmplx;

{$R *.DFM}

procedure TForm1.Button1Click(Sender: TObject); var

x,y,z: Complex;

procedure Output(Operation: Char);

//Осуществляет нужное действие и выводит результат в Memo1

var S: String; begin

case Operation of '+': z := AddC(x, y) ; '-': z := SubC(x, y) ; '*': z := MulC(x, y) ; '/': z := DivC(x, y) ; end;

S := '('+FormatFloat('+0.0000;-0.0000', x.re)+FormatFloat('+0.0000i;-0.0000i', x.im)+')' + Operation +'('+FormatFloat('+0.0000;-0.0000', у.re) +

FormatFloat('+0.0000i;-0.0000i', у.im) + '=' +FormatFloat('+0.0000;-0.0000', z.re) + FormatFloat('+0.0000i;-0.0000i', z.im);

Memo1.Lines.Add(S) ; end; //Output

begin /Button1Click

x.re := Random; x.im := Random; y.re := Random; y.im := Random;

Output('+'); Output('-'); Output ('*'); Output ('/'); Memo1.Lines.Add(' ');

end;

Обратите внимание на ссылку uses cmplx в самом начале исполняемой части - именно она делает доступными обработчику Button1Click объекты модуля Cmplx.

ТИПЫ МОДУЛЕЙ В DELPHI

Наиболее распространенным типом модуля в Delphi является форма - модуль со связанным с ним окном. Интерфейсная часть такого модуля обычно содержит объявление нового класса и автоматически обновляется Delphi в ходе конструирования окна. В интерфейсной части модуляформы содержится также объявление объекта для соответствующего оконного класса. Например, для учебной программы модуль содержит объявление класса TForm1 и объекта Form1. Большинство типовых модулей в хранилище содержат заготовки для создания диалоговых окон. Помимо форм в хранилище содержатся также не связанные с видимыми окнами модули. Кроме уже рассмотренного выше модуля общего назначения, к ним относятся модули данных, модули динамических библиотек, пакеты и модули потоков.

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

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

Windows динамически связываемых библиотек DLL (Dynamic-Link Libraries). DLL служат универсальным средством согласования подпрограмм, написанных на разных языках программирования. В Windows содержится множество DLL, написанных на языке Си или на языке ассемблера, что ничуть не мешает Delphi-программам использовать их. Модули динамических библиотек предназначены для разработки DLL с помощью Object Pascal. Такие DLL затем смогут использовать программы, созданные с помощью других языков программирования.

Пакеты - это особым образом откомпилированные DLL, оптимизированные для совместного использования Delphi-программами, или средой Delphi, или и программами, и средой. В отличие от DLL пакеты могут хранить и передавать программе типы (включая классы) и данные. Они разработаны специально для хранения компонентов, разного рода экспертов, редакторов сложных свойств и т. п. Например, в пакете VCL70.bpl содержатся основные компоненты Delphi 7.0.

Модули потоков предназначены для реализации так называемых потоков команд - фрагментов программы, которые исполняются параллельно с другими фрагментами, разделяя с ними время процессора и остальные системные ресурсы. К сожалению, потоки не могут связываться с собственными видимыми компонентами, так как библиотека визуальных компонентов VCL (Visual Component Library) не поддерживает работу с потоками. Вот почему модуль потока не имеет связанного с ним окна.

Глава . ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ

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

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

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

Указатели и динамическая память

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

Вся динамическая память в Object Pascal рассматривается как сплошной массив байтов, который называется кучей. Каждый из байтов имеет собственный номер. Эти номера называются адресами, они позволяют обращаться к любому байту памяти. Object Pascal предоставляет в

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

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

Простейшие действия с указателями

1. Выделение памяти

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

var a, b: ^Integer; begin

New(a);

New(b);

end;

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

2. Занесение информации

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

a := 2; // В область памяти A помещено значение 2 b := -10; // В область памяти

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

Динамически размещенные данные можно использовать в любом месте программы, где это допустимо для констант и переменных соответствующего типа, например: a^ := Sqr(a^) - 17;

Разумеется, недопустим оператор

a := Sqr(a^) - 17;

так как указателю a нельзя присвоить значение целочисленного выражения.

3. Копирование адреса

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

Если, например, var

p1,p2: ^Integer; p3: ^Real;

p: Pointer;

то присваивание p1 := p2; вполне допустимо, в то время как p1 :=p3; запрещено, поскольку p1 и p3 указывают на разные типы данных. Это ограничение, однако, не распространяется на нетипизированные указатели, поэтому можно записать p := p3; p1 := p;

4. Освобождение памяти

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

Например, операторы

Dispose(a); Dispose(b);

вернут в кучу память, которая ранее была закреплена за указателями a и b. Процедура Dispose(p) не изменяет значения указателя p, а лишь

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

p := Nil;

Для работы с нетипизированными указателями используются процедуры GetMem и FreeMem:

GetMem(P, Size); // выделение памяти FreeMem(P, Size); // освобождение памяти

Здесь P – нетипизированный указатель; Size – размер в байтах требуемой или освобождаемой части кучи.

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

Несвязанные динамические данные

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

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

–в разделе Var объявляется не переменная требуемого типа, а указатель на этот тип;

–перед использованием необходимо вызвать процедуру New, а после использования – процедуру Dispose.

ПРИМЕР.

{Работа с простой динамической переменной целочисленного типа}

var Px: ^Integer; begin

new(Px); Px^ := 100;

...

dispose(Px); end;

Связанные динамические данные

Основные определения

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

–добавление элемента в начало (голову) списка;

–добавление элемента в конец (хвост) списка;

–вставка элемента между двумя любыми другими элементами списка;

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

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

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

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

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

Организация взаимосвязей в линейном односвязном списке

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

Схематично такую структуру данных можно показать следующим образом:

Соответствующее ей объявление может иметь такой вид:

Type TPtr = ^TElem; TElem = Record

Inf: Real;

Link: TPtr;

End;

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

Работа с линейным односвязным списком

Для работы с линейным односвязным списком требуются указатели:

–указатель на начало списка (возьмем идентификатор BegL);

–указатель на конец списка (возьмем идентификатор EndL);

–указатель на k-й элемент списка, где будут производиться действия: после которого (или перед которым) будет вставлен элемент или же который следует удалить (возьмем идентификатор Pk);

–временный указатель для выделения памяти под добавляемые элементы

идля освобождения памяти удаляемых элементов (возьмем идентификатор P).

Var BegL, EndL, Pk, P: TPtr;

Начальные установки указателей:

BegL := Nil; EndL := Nil;

Рассмотрим некоторые операции над линейными односвязными списками.

Создание списка (внесение первого элемента).

1) Выделение памяти под новый элемент списка и занесение в него информационного значения Val.

New(P); P^.inf := Val;

P^.link := Nil;

2) Установка указателей начала и конца списка на новый элемент.

BegL := P; EndL := P;

Добавление элемента в конец списка.

1) Выделение памяти под новый элемент списка и занесение в него информационного значения Val.

New(P); P^.inf := Val;

P^.link := Nil;

2)Установка связи между последним элементом списка и новым, а также перемещение указателя конца списка на новый элемент.

EndL^.link := P; EndL := P;

Вставка элемента в середину списка после заданного k-го элемента. Будем считать, что адрес k-го элемента уже известен и хранится в

указателе Pk.

1)Выделение памяти под новый элемент и занесение в него информационного значения Val.

New(P); P^.inf := Val;

2)Установка связи между новым и (k+1)-м элементом, а также перестановка связи k-го элемента на новый элемент.

P^.link := Pk^.link; Pk^.link := P;

Удаление элемента из начала списка.

1)Извлечение информации из удаляемого элемента в переменную Val и установка на него вспомогательного указателя P.

Val := BegL^.inf;

P := BegL;

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

BegL := P^.link; Dispose(P);

If BegL = Nil then EndL := Nil; {если удаляется

последний элемент списка}

Удаление k-го элемента списка.

Можно предварительно скопировать значение поля Inf «нужного» (k+1)- го элемента в поле Inf «ненужного» k-го и удалить (k+1)-й элемент вместо k-го.

1)Установка дополнительного указателя P на (k+1)-й элемент, извлечение информации в переменную Val из удаляемого k-го элемента и копирование информации из (k+1)-го элемента в k-й элемент.

P := Pk^.link; Val := Pk^.inf; Pk^.inf := P^.inf;

2)Установка связи между k-м и (k+2)-м элементами и освобождение памяти (k+1)-го элемента, который удаляется вместо k-го.

Pk^.link := P^.link; Dispose(P);

Установка указателя на k-й элемент списка.

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

P := BegL; i := 1;

While i < k do

Begin

P := P^.link; i := i + 1;

End;

ПРИМЕР.

unit Unit1;

{В данной программе создается динамический список из 10 элементов, значениями которых являются целые числа 1,2,3,...,10. Значения элементов списка выводятся в компонент Memo1, а список уничтожается. Процедуры, реализующие необходимые операции со списком, находятся в модуле Unit2.}

interface uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, Unit2;

type

TForm1 = class(TForm) Memo1: TMemo; Button1: TButton;

procedure Button1Click(Sender: TObject); private

{Private declarations } public

{Public declarations }

end;

var

Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject); //кнопка выполнения программы

var i:byte; v:real; begin

Initial; //инициализация списка

for i:=1 to 10 do InsEnd(i); //вставка элементов в список while BegL<>Nil do //извлечение значений элементов списка

//и уничтожение списка

begin

DelBeg(v);

Memo1.Lines.Add(floattostr(v)); end;

end; end.

unit Unit2;

{Модуль содержит процедуры, реализующие следующие операции с линейным динамическим списком: вставка элемента в конец списка и удаление элемента из начала списка.}

interface

//описание типа-указателя на элемент списка type TPtr=^TElem;