Основы программирования. Указатели. Динамические структуры данных. Абстрактные типы данных. Классы. Методические указания для студентов 1 курса факультета математики, механики и компьютерных наук

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Федеральное государственное образовательное учреждение высшего профессионального образования «ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»

С.С. Михалкович

Основы программирования Указатели. Динамические структуры данных. Абстрактные типы данных. Классы

МЕТОДИЧЕСКИЕ УКАЗАНИЯ для студентов 1 курса факультета математики, механики и компьютерных наук

Ростов-на-Дону 2007 3

Аннотация Методические указания содержат лекции по темам «Указатели», «Динамические структуры данных», «Абстрактные типы данных» курса «Основы программирования» для студентов направления «Информационные технологии» факультета математики, механики и компьютерных наук Методические указания разработаны кандидатом физико-математических наук, доцентом кафедры алгебры и дискретной математики Михалковичем С.С.

Печатается в соответствии с решением кафедры алгебры и дискретной математики факультета математики, механики и компьютерных наук ЮФУ, протокол № 3 от 13 ноября 2006 г. 4

1 Указатели 1.1 Общие сведения Оперативная память компьютера может рассматриваться как массив байтов, индексируемый от нуля. Номер каждого байта в этом массиве называется его адресом. Адресом переменной называется адрес ее первого байта. Для получения адреса переменной в языке Pascal используется унарная операция @: @x – адрес переменной x. Переменные, в которых хранятся адреса, называются указателями. Любой указатель в 32-разрядной операционной системе занимает 4 байта. Это дает возможность адресовать 2 32 = 4 Гб ячеек памяти. С переходом на 64-битные системы объем адресуемой оперативной памяти станет практически безграничным. Для чего нужны указатели? Их использование повышает гибкость программирования и разграничивает обязанности: указатель знает лишь адрес переменной, сама переменная может менять свое значение независимо от наличия указателя на нее. Можно провести аналогию между указателями и справочной службой 09. Клиент обращается в справочную службу для того, чтобы узнать номер телефона абонента. Другими словами клиент обращается к указателю, который знает адрес объекта и, следовательно, может вернуть значение этого объекта (в данном случае – номер телефона). Гибкость такого способа очевидна: не следует помнить номера всех телефонов, достаточно знать номер телефона справочной. Кроме того, если номер телефона абонента будет изменен, то в справочной службе будет произведена оперативная корректировка информации, и при последующем обращении в службу клиент получит измененный номер телефона. Другой пример: несколько указателей (банкоматов) указывают на один объект (банковский счет). Посредством разных банкоматов можно снимать деньги с одного банковского счета. Третий пример: файловый указатель, который обращается всякий раз к текущему элементу файла, после чего перемещается на следующий. Это позволяет единым образом (через один указатель) работать с различными данными, находящимися в файле. В языке Delphi Pascal указатели делятся на типизированные и бестиповые. Если T – некоторый тип, то типизированный указатель на него описываются следующим образом: ^T (указатель на тип). Бестиповой указатель описывается с помощью типа pointer. Если типизированный указатель хранит адрес переменной заданного типа, то бестиповой хранит просто адрес некоторого участка памяти. Будем изображать тот факт, что указатель pa хранит адрес переменной a, следующим образом: pa

a

5

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

Типизированные указатели разных типов несовместимы по присваиванию. Однако типизированный и бестиповой указатель совместимы по присваиванию в обе стороны. Указатели одного типа, а также типизированный и бестиповой указатель можно сравнивать на равенство и неравенство. Далее приводятся примеры допустимых действий с указателями: var a: integer; r: real; pa,pa1: ^integer; p,p1: pointer; pr: ^real; begin pa:=@a; p:=@a; pa:=p; p:=pa; p:=nil; pa:=nil; if pa=pa1 then ; if pa<>p then ; ... Следующие действия, наоборот, являются недопустимыми и вызовут ошибку компиляции, поскольку выполняются над указателями, имеющими различный базовый тип: pr:=pa; // ошибка: несовместимые типы if pr=pa then; // ошибка: несовместимые типы Следует помнить, что в языке Pascal принята именная эквивалентность типов. Поэтому в следующем примере переменные pb и pb1 считаются принадлежащими к разным типам: var pb: ^integer; pb1: ^integer; begin pb:=pb1; // ошибка компиляции! if pb<>pb1 then ; // ошибка компиляции! ... 6

Чтобы можно было присваивать и сравнивать указатели на один и тот же тип, описанные в разных местах, а также передавать указатели как параметры подпрограмм, следует определить новый тип-указатель и описывать переменныеуказатели, используя этот тип: type pinteger=^integer; var pb: pinteger; pb1: pinteger; procedure pr(p: pinteger); begin ... end; ... pb:=pb1; // верно if pb<>pb1 then ; // верно pr(pb); // верно К типизированным указателям применима операция разыменовыния ^ : запись pa^ означает «объект, на который указывает pa» (под объектом здесь понимается область памяти, выделенная программой и трактуемая как переменная или константа определенного типа). В частности, если pa хранит адрес переменной a, то разыменованный указатель pa^ и имя переменной a эквивалентны, поскольку ссылаются на один объект. Вообще, ссылка на объект – это выражение, однозначно определяющее этот объект. В нашем примере имя переменной a и выражение pa^ являются ссылками на один и тот же объект в памяти. Нулевой указатель и указатель типа pointer разыменовывать нельзя. При разыменовании переменной-указателя, имеющей нулевое значение, произойдет ошибка времени выполнения, разыменование же указателя pointer приведет к ошибке компиляции. Если типизированный указатель хранит адрес записи или массива, то в Delphi Pascal при обращении через указатель к полю записи или элементу массива операцию разыменования можно не использовать. Например: type IArr = array [1..100] of integer; Rec = record i,j: real; end; var a: IArr; pa: ^IArr; r: Rec; pr: ^Rec; begin pa:=@a; pr:=@r; pa[1]:=2; // вместо pa^[1]:=2 pr.i:=3; // вместо pr^.i:=3 end. 7

1.2 Неявные указатели Указатели неявно встречаются во многих конструкциях языка программирования. Например, при передаче параметра по ссылке в подпрограмму на самом деле передается указатель. Сравним две реализации одной процедуры: procedure Mult2(var i: integer); begin i:=i*2; end; procedure Mult2P(pi: pinteger); begin pi^:=pi^*2; end; var a: integer; begin a:=3; Mult2(a); Mult2P(@a); ... Код, генерируемый для таких процедур, практически идентичен: в обоих случаях в процедуру передается адрес переменной, которую следует удвоить. Однако пользоваться первой версией процедуры с параметром, передаваемым по ссылке, гораздо удобнее: в теле процедуры не надо разыменовывать указатель и при вызове процедуры в качестве параметра надо указывать саму переменную, а не ее адрес. Из данного примера видно, что параметр, передаваемый по ссылке, можно трактовать как указатель, который при использовании неявно разыменовывается. Другой пример неявных указателей – процедурные переменные. Процедурная переменная хранит адрес процедуры или функции с соответствующей сигнатурой, либо же значение nil (напомним, что сигнатура подпрограммы определяется ее заголовком и включает количество и типы ее параметров, а для функций также и тип возвращаемого значения). Для присваивания процедурной переменной a адреса подпрограммы p с соответствующей сигнатурой знак операции @ использовать необязательно: записи a:=@p и a:=p равнозначны. Например: type proc = procedure (i: integer); func = function: real; var a: proc; b: func; procedure p(i: integer); begin ... end; 8

function f: real; begin ... end; begin a:=@p; b:=f; // равноценно b:=@f a(5); // вызов процедуры через процедурную переменную a writeln(b); // вызов функции через процедурную переменную b end.

1.3 Указатели pointer Бестиповые указатели pointer хранят адрес памяти, не связанный с объектом определенного типа, и не могут быть разыменованы. Чтобы воспользоваться данными по этому адресу, бестиповой указатель следует преобразовать к указателю на конкретный тип. Например: type pinteger = ^integer; preal =^real; var i: integer; r: real; p: pointer; begin p:=@i; pinteger(p)^:=5; writeln(pinteger(p)^); p:=@r; preal(p)^:=3.14; writeln(preal(p)^); end. Рассмотрим запись pinteger(p)^ подробнее. Здесь перед доступом к данным по указателю p мы вначале преобразуем его к указателю на integer, а потом разыменовываем. Поскольку перед обращением к pinteger(p)^ было выполнено присваивание p:=@i, то выражение pinteger(p)^ становится синонимом имени i и может быть использовано как в левой, так и в правой части оператора присваивания. Гибкость указателей pointer имеет обратную сторону: их применение потенциально опасно и может приводить к ошибкам, причину которых сложно установить. Например, в результате выполнения кода 9

p:=@i; preal(p)^:=3.14; мы обратимся к участку памяти, по которому расположено значение целой переменной i, как к вещественной переменной. Поскольку данные вещественного типа занимают в памяти 8 байт (в Delphi), а данные целого типа – всего 4 байта, то последнее присваивание не только изменит 4 байта, занимаемые переменной i, но и запишет оставшиеся 4 байта в область памяти, следующую за переменной i. Поскольку обычно память под глобальные переменные выделяется подряд в порядке их описания, то оставшиеся 4 байта запишутся в область памяти, отведенную под переменную r (именно она описана вслед за i), то есть в результате последнего присваивания значение переменной r будет испорчено. Подобная ошибка не будет выявлена на стадии компиляции, а при выполнении программы проявится не при данном ошибочном присваивании, а позже, когда мы захотим воспользоваться значением переменной r. Именно поэтому рекомендуется либо отказаться от использования бестиповых указателей, либо при их использовании проявлять предельную аккуратность. Приведем пример, в котором использование указателей pointer оправдано. Пример. Внутреннее представление значения real. Зададимся целью посмотреть, как хранится в памяти переменная типа real. Для этого запишем ее адрес в указатель pointer, после чего преобразуем его в указатель на массив байтов и выведем этот массив на экран. const sz = sizeof(real); type Arr=array [1..sz] of byte; PArr=^Arr; var r: real; p: pointer; pb: PArr; i: integer; begin readln(r); p:=@r; pb:=p; for i:=1 to sz do write(pb^[i],’ ’); end. Отметим одну особенность операции взятия адреса @. В Delphi ее результат зависит от директивы компиляции {$T} («typed @ operator»). По умолчанию установлена директива компиляции {$T-}: это означает, что результат операции @ имеет тип pointer. Если же установлена директива компиляции {$T+}, то результат операции @ – типизированный указатель, базовым типом для которого 10

выступает тип операнда. Кроме того, можно получить адрес переменной, воспользовавшись стандартной функцией Addr(x), которая всегда возвращает значение типа pointer. Особенностью операции @ можно воспользоваться, чтобы упростить последнее решение. Для этого поставим в начале программы директиву компиляции {$T-}, что позволит нам заменить присваивания p:=@r; pb:=p на pb:=@r и исключить из программы описание переменной p. Подчеркнем, что в режиме {$T+} последнее присваивание приведет к ошибке несоответствия типов, поскольку @r будет возвращать значение типа ^real. Впрочем, в режиме {$T+} можно воспользоваться явным приведением типов (pb:=PArr(@r)) или функцией Addr (pb:=Addr(r)):

1.4 Динамическая память и динамические переменные Память, отводимая под данные программы, делится на статическую, автоматическую и динамическую. Статическая память выделяется до начала работы программы под глобальные переменные и константы и освобождается только при завершении программы. Автоматическая память выделяется на программном стеке под локальные переменные при вызове подпрограммы, а после завершения подпрограммы автоматически освобождается. При этом статическая память инициализируется нулевыми значениями, а автоматическая – не инициализируется (это делается для ускорения вызова подпрограммы). Поскольку как программный стек, так и область статической памяти, выделяются заранее в момент начала работы программы, статическая и автоматическая память имеют фиксированный размер. Однако во многих задачах в разные моменты работы программы требуется существенно различное количество памяти. Отводить для этого фиксированный максимально необходимый размер памяти – расточительство. С данной проблемой мы уже сталкивались при работе с массивами: при описании массива указывается его максимально возможный размер, текущая же заполненность массива, как правило, меньше его размера. Динамическая память, называемая также кучей, выделяется явно по запросу программы из ресурсов операционной системы и контролируется указателем. Она не инициализируется автоматически и должна быть явно освобождена. В отличие от статической и автоматической памяти динамическая память практически не ограничена (ограничена лишь размером оперативной памяти) и может динамически меняться в процессе работы программы. Недостатки динамической памяти являются продолжением ее достоинств. Во-первых, поскольку она контролируется указателем, доступ к ней осуществляется несколько дольше, чем для статической и автоматической памяти. Во-вторых, программист сам должен заботиться о выделении и освобождении памяти, что чревато большим количеством потенциальных ошибок. 11

1.5 Процедуры New и Delete Для выделения динамической памяти, контролируемой типизированным указателем, используется стандартная процедура New, для освобождения – стандартная процедура Dispose. Если pt – указатель на тип T, то вызов New(pt) распределяет в динамической памяти переменную типа T и записывает в pt адрес этой переменной: динамическая память

pt^ pt динамическая переменная

Переменная, распределенная в динамической памяти, называется динамической переменной. Она не имеет своего имени и для доступа к ней используется разыменованный указатель pt^. После работы с динамической переменной занимаемая ею память должна быть освобождена вызовом стандартной процедуры Dispose, например: Dispose(pt). Таким образом, динамическая переменная существует между вызовами New и Dispose: var pt: ^real; begin New(pt); pt^:=2.8; pt^:=pt^*2; ... Dispose(pt); end. Выделение и освобождение динамической памяти выполняется специальной подсистемой программы, называемой менеджером кучи. Менеджер кучи хранит список всех незанятых блоков в динамической памяти. При вызове New менеджер кучи ищет незанятый блок подходящего размера, выделяет в нем память и модифицирует список незанятых блоков. При вызове Dispose блок вновь помечается как свободный. После завершения программы вся выделенная для нее динамическая память автоматически возвращается назад системе. Если динамическая память выделяется в подпрограмме для решения локальных задач данной подпрограммы, то она должна быть освобождена в конце работы этой подпрограммы. Исключение составляют так называемые «создающие» подпрограммы, основным предназначением которых является вернуть объект, созданный в динамической памяти. Например:

12

function NewInteger(i: integer): pinteger; begin New(Result); Result^:=i; end; var pi: pinteger; begin pi:= NewInteger(5); ... При своем вызове функция NewInteger возвращает указатель на динамическую переменную, которая должна быть впоследствии освобождена. Основная проблема состоит в том, что NewInteger не является стандартной функцией, и при ее вызове можно забыть, что она выделяет динамическую память. Один из способов «напомнить» об этом программисту – дать функции имя, свидетельствующее о ее «создающей» способности. Например, имя такой функции может начинаться с префикса New или Create. Пример. Массив указателей на переменные разных типов. В некоторых задачах возникает необходимость хранить в массиве данные различных типов. Пусть в массиве требуется хранить данные типа integer, real и shortstring. Приведем вначале решение, не использубщее указатели. Решение 1. Используем записи с вариантами. Опишем следующие типы: type TVar=(tInt,tReal,tStr); Variant = record case t: TVar of tInt: (i: integer); tReal: (r: real); tStr: (s: shortstring); end; Теперь опишем массив записей Variant и добавим в него несколько значений: var A: array [1..10] of Variant; begin A[1].t:=tInt; A[1].i:=5; A[2].t:=tReal; A[2].r:=3.14; A[3].t:=tStr; A[3].s:='Delphi'; end. Для вывода содержимого массива, очевидно, следует воспользоваться циклом for i:=1 to 3 do case A[i].t of tInt: writeln(A[i].i); 13

tReal: writeln(A[i].r); tStr: writeln(A[i].s); end; Такое решение имеет важный недостаток: каждый элемент массива имеет размер, определяемый самым большим типом shortstring, что расточительно. Решение 2. В вариантной части записи Variant будем хранить не значения соответствующих типов, а указатели на них: type TVar=(tInt,tReal,tStr); pinteger=^integer; preal=^integer; pshortstring=^shortstring; Variant = record t: TVar; case t: TVar of tInt: (pi: pinteger); tReal: (pr: preal); tStr: (ps: pshortstring); end; Будем добавлять в такой массив указатели на переменные разных типов: var A: array [1..10] of Variant; begin A[1].t:=tInt; New(A[1].pi); A[1].pi^:=5; A[2].t:=tReal; New(A[2].pr); A[2].pr^:=3.14; A[3].t:=tStr; New(A[3].ps); A[3].ps^:='Delphi'; Для вывода содержимого такого массива воспользуемся следующим циклом: for i:=1 to 3 do case A[i].t of tInt: writeln(pinteger(A[i].p)^); tReal: writeln(preal(A[i].p)^); tStr: writeln(pstring(A[i].p)^); end; В данном решении суммарный объем данных определяется не размером максимального типа данных, а реальным содержимым в момент выполнения программы. По окончании работы с массивом A динамическую память, занимаемую его элементами, следует освободить. Поскольку параметр процедуры Delete имеет тип pointer, то для освобождения занимаемой памяти можно передать любое из полей-указателей, например, pi: for i:=1 to 3 do Delete(A[i].pi); 14

1.6 Процедуры GetMem и FreeMem Для выделения/освобождения динамической памяти, контролируемой бестиповым указателем, используется другая пара процедур: GetMem и FreeMem. Если p – указатель любого типа (в частности, типа pointer), то вызов GetMem(p,nb) выделяет в динамической памяти участок размера nb байтов и записывает адрес его начала в указатель p. Вызов FreeMem(p) освобождает динамическую память, контролируемую указателем p. Следует обратить внимание, что при вызове FreeMem не указывается размер освобождаемой памяти, поскольку в каждом выделенном блоке хранится его размер, и FreeMem пользуется этой информацией. В большинстве ситуаций использования типизированных указателей и процедур New и Dispose оказывается достаточно. Процедуры GetMem и FreeMem применяются там, где требуется более гибкое управление памятью. Пример. Динамический массив. Динамическим будем называть массив, размер которого задается в процессе работы программы. В Delphi (начиная с версии 4) динамические массивы реализованы средствами языка: var dyn: array of integer; n: integer; begin read(n); Assert(n>0); SetLength(dyn,n); dyn[0]:=5; ... Однако, динамические массивы нетрудно создать и с помощью обычных массивов с помощью процедур GetMem и FreeMem: const sz=MaxInt div sizeof(integer); type Arr: array [0..sz-1] of integer; var dyn: ^Arr; n: integer; begin read(n); Assert(n>0); GetMem(dyn,n*sizeof(integer)); dyn^[0]:=5; // можно dyn[0]:=5 ... Идея подобной реализации динамического массива состоит в следующем. Описывается тип массива с большим количеством элементов и переменная dyn, 15

являющаяся указателем на этот тип. С помощью GetMem выделяется нужное количество памяти, определяемое в процессе работы программы; адрес выделенной памяти записывается в переменную dyn. С этого момента можно обращаться к элементам массива, используя запись вида dyn^[0]. Операцию разыменования в Delphi можно опускать, поэтому с dyn можно обращаться как с обычным массивом: dyn[0]. В конце работы с таким массивом следует вызвать FreeMem(dyn). Отметим, что при включенном режиме проверки выхода за границы диапазона {$R+} нельзя выделять под массив память, превосходящую его размер, то есть должно выполняться условие n<=sz. Поэтому следует задавать размер массива sz максимально возможным. В Delphi память, занимаемая переменной любого типа, не должна превосходить 2 Гб, т.е. MaxInt байт. Поскольку элементы массива имеют тип integer, то в качестве sz выбрано максимально возможное значение MaxInt div sizeof(integer).

1.7 Ошибки при работе с динамической памятью Как было отмечено, при работе с динамической памятью можно совершить большое количество ошибок, которые имеют различные последствия и различную степень тяжести. Большинство этих ошибок проявляется не сразу, а через некоторое время в процессе выполнения программы. Следовательно, такие ошибки труднонаходимы и потому особенно опасны. Используя принцип «предупрежден – значит, вооружен», перечислим наиболее часто встречающиеся варианты ошибок при работе с динамической памятью. 1. Попытка воспользоваться неинициализированным указателем. var pi: ^integer; i: integer; begin pi^:=5; Если pi – глобальная переменная, то она автоматически инициализируется нулевым значением, т.е. имеет значение nil. Разыменование нулевого указателя приводит к ошибке времени выполнения. Если pi – локальная переменная, то она по умолчанию не инициализируется, а поэтому содержит непредсказуемое значение. Это значение трактуется как адрес целой переменной, к которой осуществляется доступ. Как правило, в этой ситуации возникает исключение Access Violation (нарушение защиты доступа), но по чистой случайности может оказаться, что указатель pi содержит истинный адрес переменной программы, тогда переменная будет изменена, выполнение программы продолжится дальше, а факт изменения переменной непредсказуемым образом повлияет на дальнейшее выполнение программы. 16

2. «Висячие» указатели. После освобождения динамической памяти указатель продолжает указывать на старое место. Такие указатели называются «висячими». Попытка записи по такому указателю не приводит к немедленной ошибке. Однако память, на которую он указывает, могла быть уже выделена другой динамической переменной, и попытка записи приведет к порче этой переменной. var pi: ^integer; begin New(pi); pi^:=5; Dispose(pi); // указатель становится "висячим" ... pi^:=6; // ошибка! Если после Dispose(pi) сразу написать pi:=nil, то в дальнейшем при попытке разыменовать нулевой указатель pi возникнет исключение, что является более предпочтительным, чем скрытая ошибка изменения другой переменной. Данный прием следует взять на вооружение и после освобождения динамической переменной обнулять указатель: Dispose(pi); pi:=nil; 3. «Утечка» памяти. Данная ошибка возникает, когда память не освобождается, но перестает контролироваться указателем. Подобную ошибку называют «утечкой» памяти, поскольку такую память невозможно освободить. Такая ошибка труднонаходима, поскольку практически не сказывается на работе приложения. Однако при систематических утечках программа требует все больше памяти у операционной системы, замедляя работу других приложений. Далее приводятся две распространенные ситуации, в которых возникает утечка памяти. Пример 1. Повторное выделение памяти. Если выделить память повторно для того же указателя, то ранее выделенная память «утечет»: var pi: ^integer; begin 5 pi New(pi); pi^:=5; New(pi); Пример 2. Выделение памяти под локальную переменную без освобождения. procedure pp; var pi: ^integer; 17

begin New(pi); end; Данная процедура составлена ошибочно: локальный указатель pi уничтожается после завершения работы процедуры, поэтому контролируемая им динамическая память «утекает». Особенно опасна подобная утечка при вызове такой процедуры в цикле: for i:=1 to MaxInt do pp; 4. Память, выделенная динамически для глобальных переменных-указателей, не возвращается явно в конце программы. Поскольку динамическая память автоматически освобождается в конце работы программы, отсутствие явного вызова Dispose или FreeMem для глобальных переменных-указателей на динамическую память не может считаться ошибкой и свидетельствует просто о неаккуратности программирования. Однако при переносе текста основной программы в процедуру мы получим ошибку утечки памяти, описанную в предыдущем пункте. 5. Попытка освободить динамическую память, не выделенную ранее. var pi: ^integer; begin Dispose(pi); Подобная ошибка приводит к немедленной генерации исключения, поэтому не принадлежит к числу опасных. Заметим, что в Delphi вызов процедуры Dispose для нулевого указателя просто игнорируется, не приводя к генерации исключения. 6. Попытка дважды освободить занимаемую память. var pi: ^integer; begin New(pi); ... Dispose(pi); Dispose(pi); При повторном вызове процедуры Dispose будет сгенерировано исключение. 7. Попытка освободить нединамическую память. var pi: ^integer; i: integer; begin pi:=@i; Dispose(pi); 18

При вызове Dispose для нединамической переменной будет сгенерировано исключение. 8. Выход за память, выделенную процедурой GetMem. Поскольку GetMem выделяет количество памяти, не зависящее от размера объекта, с которым связан указатель, она менее безопасна, чем New. Например, при реализации с помощью GetMem динамического массива можно предпринять попытку обратиться за границы выделенной памяти: GetMem(dyn,n*sizeof(integer)); dyn^[n+1]:=5; Обычно такая ошибка приводит к исключению Access Violation.

2 Динамические структуры данных 2.1 Общие сведения Данные могут объединяться в структуры. Примерами структур являются массивы и записи. Но эти структуры во время выполнения программы имеют постоянный размер, то есть являются статическими. Если же размер структуры меняется в процессе работы программы, то такая структура данных называется динамической. Один из способов создать динамическую структуру данных – составить ее из однотипных элементов-записей, каждая из которых, помимо полей данных, имеет поля связи, указывающие на другие элементы. В простейшем случае имеется одно поле связи, которое хранит адрес следующего элемента или nil, если следующий элемент отсутствует. Попытаемся описать тип элемента такой структуры: type Node=record data: integer; next: ^Node; // ошибка! end; Данное определение в Delphi Pascal ошибочно. Проблема состоит в том, что тип Node частично определяется через самого себя (рекурсия по данным) и к моменту определения поля next: ^Node тип Node еще не определен полностью. Проблема решается следующим образом: определяется тип PNode=^TNode, после чего определяется тип Node, в котором поле next имеет тип PNode: type PNode=^Node; Node=record data: integer; next: PNode; end; 19

Здесь действует следующее правило Паскаля: в секции type можно описывать указатель на еще не определенный тип при условии, что данный тип будет определен позднее в этой же секции. Как уже было сказано, элементы типа Node можно завязать в цепочку. Для этого полю next каждого элемента необходимо присвоить указатель на следующий, поле next последнего элемента следует присвоить значение nil (конец цепочки): data

next

dat a

next

dat a

next

Структура, изображённая на рисунке, называется линейным односвязным списком, а ее элементы часто называются узлами списка. Доступ к элементам такого списка – последовательный: нельзя обратиться к какому-то элементу, не перебрав предыдущие. Если поле next последнего элемента списка указывает на первый элемент, то такая структура называется кольцевым односвязным списком:

data

next

dat a

next

dat a

next

В отличие от линейного списка кольцевой не имеет явного начала и конца. Если у каждого элемента, помимо указателя на следующий, имеется указатель на предыдущий элемент prev: PNode, то такая структура называется линейным двусвязным списком: prev data next pr ev dat a next

pr ev dat a next

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

prev data next

2.2 Односвязные линейные списки Для удобства определим вспомогательную функцию NewNode, создающую в динамической памяти узел линейного односвязного списка, заполняющую его поля значениями data и next и возвращающую указатель на него: 20

function NewNode(data: integer; next: PNode): PNode; begin New(Result); Result^.data:=data; Result^.next:=next; end; Основными действиями с линейным односвязным списком являются вставка, удаление, поиск элементов, проход по списку и сортировка. Будем считать, что во всех приводимых операциях указатель p типа PNode хранит адрес текущего элемента списка. Если поле данных data элемента списка содержит значение x, то для простоты будем говорить, что элемент или узел имеет значение x. 1. Вставка элемента со значением x в начало списка. Пусть первый элемент является текущим (указатель p хранит адрес первого элемента): 3

5

7

p

Создадим новый элемент со значением x, поле next которого указывает на первый элемент, после чего сделаем этот элемент первым, присвоив его адрес указателю p: p:=NewNode(x,p); x

3

5

7

p

Отметим, что данная операция производит добавление также и в пустой список (p=nil). При многократном ее выполнении происходит заполнение списка, причем, элементы в списке будут располагаться в порядке, обратном порядку их включения. 2. Удаление элемента из начала непустого списка. 3

5

7

p

Запомним адрес первого элемента в переменной t, после чего переместим указатель на первый элемент вперед и освободим элемент, контролируемый указателем t:

21

t:=p; p:=t^.next; Dispose(t); 3 t

5

7

p

3. Вставка элемента со значением x после текущего. 3

5

7

p

Данная операция аналогична вставке в начало, но вместо p используется p.next: p^.next:=NewNode(x,p^.next); 3

5 p

7 x

4. Удаление элемента, следующего за текущим. 3

5

7

4

p

Данная операция аналогична удалению из начала, но вместо p используется p.next; если p.next=nil, то никаких действий не производится: t:=p^.next; if t<>nil then begin p^.next:=t^.next; Dispose(t); end; 3

5 p

7

4

t

5. Вставка элемента со значением x перед текущим. 3

5

7

p

Вставим после текущего элемента его копию, затем присвоим полю данных текущего элемента значение x и передвинем текущий элемент вперед: 22

p^.next:=NewNode(p^.data,p^.next); p^.data:=x; p:=p^.next; 3

x

7 5 p

6. Удаление текущего элемента. 3

5

7

4

p

Для быстрого выполнения этого действия требуется, чтобы существовал элемент, следующий за текущим. Скопируем поле данных и поле next из следующего элемента в текущий, после чего освободим следующий: t:=p^.next; p^.data:=t^.data; p^.next:=t^.next; Dispose(t); 3

7 p

7

4

t

7. Проход по списку. 3

5

7

p

Пусть над всеми элементами списка необходимо выполнить некоторую операцию Oper, заданную процедурой с одним ссылочным параметром, например: procedure Oper(var i: integer); begin i:=i*2; end; Установим указатель на его первый элемент и, пока значение указателя не равно nil, будем выполнять операцию Oper и передвигаться на следующий элемент: while p<>nil do begin Oper(p^.data); p:=p^.next; end; 23

Очевидно, во время прохода по списку можно не только менять элементы, но и выводить их или производить вычисления: например, подсчитывать сумму или количество элементов, удовлетворяющих некоторому условию. 8. Поиск элемента со значением x. x p

Проход по списку здесь надо совершать либо до конца списка, либо до момента, когда текущий элемент будет иметь значение x. Если после цикла текущий элемент не нулевой, то он содержит первое найденное значение x. while (p<>nil) and (p^.data<>x) do p:=p^.next; found:=p<>nil; Следует обратить внимание на то, что порядок следования операндов в операции and важен и для корректной работы последнего алгоритма в Delphi должен быть установлен ключ компиляции сокращенного вычисления логических выражений {$B-}. 9. Разрушение списка. 3

5

7

p

При разрушении мы удаляем элементы из начала списка до тех пор, пока список не станет пустым: while p<>nil do begin t:=p; p:=p^.next; Dispose(t); end; 10. Вставка элемента в упорядоченный список с сохранением упорядоченности. Пусть список не пуст и его элементы упорядочены по возрастанию. Чтобы вставить элемент со значением x с сохранением упорядоченности, найдем первый элемент с большим значением и произведем вставку перед ним. Для вставки перед элементом будем «заглядывать» на один элемент вперед, используя вместо переменной p выражение p^.next. Оформим данную операцию в виде процедуры:

24

procedure SortedListAdd(p: PNode; x: integer); begin while (p<>nil) and (p^.next^.data<=x) do p:=p^.next; p^.next:=NewNode(x,p^.next); end; 3

5

7

p 4

Отметим, что наш алгоритм осуществляет добавление после элемента, на который указывает p, поэтому он не может добавить в начало списка. Для решения указанной проблемы поместим в начало списка барьерный элемент, поле данных которого содержит самое маленькое число (-MaxInt). Список при этом сохранит свою упорядоченность, и теперь любой элемент будет добавляться после барьерного. Например, вот как выглядит заполнение упорядоченного списка n случайными числами с последующим его выводом: readln(n); p:=NewNode(-MaxInt,nil); // барьер for i:=1 to n do SortedListAdd(p,Random(1000)); t:=p; while t<>nil do begin write(t^.data); t:=t^.next; end; По существу, приведенный код реализует алгоритм сортировки вставками. Поскольку при вставке одного элемента в список длины n может потребоваться n операций (в случае прохода по всему списку), то для вставки n элементов требуемое количество операций пропорционально n 2 .

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

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

2.4 Двусвязные линейные списки Двусвязный линейный список состоит из элементов, каждый из которых хранит адреса следующего и предыдущего. Для удобства работы со списком поддерживаются указатели first и last на первый и последний элемент соответственно:

last

first

В структуру Node добавляется указатель prev на предыдующий элемент списка: type PNode=^Node; Node=record data: integer; prev,next: PNode; end; Вспомогательная функция NewNode при этом изменяется очевидным образом: function NewNode(data: integer; prev, next: PNode): PNode; begin New(Result); Result^.data:=data; Result^.next:=next; Result^.prev:=prev; end; Рассмотрим основные операции с двусвязным списком, реализация которых отличается от односвязного. После выполнения каждой операции first и last 26

должны по-прежнему оставаться указателями на начало и конец списка, а если список пуст, то получать нулевое значение. 1. Инициализация. При инициализации список пуст: first:=nil; last:=nil; 2. Добавление элемента со значением x в начало. Осуществляется аналогично добавлению в односвязный список. Если список был пустым, то last также должен указывать на добавленный элемент. first:=NewNode(x,nil,first); if last=nil then last:=first; 3. Добавление элемента со значением x в конец. Симметрично добавлению в начало: last:=NewNode(x,last,nil); if first=nil then first:=last; 4. Вставка элемента со значением x перед текущим. Пусть указатель p хранит адрес текущего элемента.

first

p

last

Создадим новый элемент, поле next которого указывает на текущий, поле prev – на предыдущий. При этом поле prev текущего элемента и поле next предыдущего должны указывать на вставляемый. Если же предыдущего элемента нет, то осуществляется вставка в начало, и требуется скорректировать указатель на первый элемент: t:=NewNode(x,p^.prev,p); p^.prev:=t; if p^.prev<>nil then p^.prev^.next:=t else first:=t; t

first

last

p

Аналогично производится вставка после текущего элемента.

27

5. Удаление текущего элемента. Пусть указатель p хранит адрес текущего элемента.

first

last

p

Перед освобождением памяти под текущий элемент следует перенаправить указатель next у предыдущего элемента на следующий, а у следующего указатель prev –на предыдущий. Если же следующего элемента нет, то необходимо удалить последний элемент и скорректировать переменную last. Аналогично если предыдущего элемента нет, то удаляется первый, и необходимо скорректировать first. if p^.prev<>nil then p^.prev^.next:=p^.next else first:=p^.next; if p^.next<>nil then p^.next^.prev:=p^.prev else last:=p^.prev; Dispose(p);

first

last

p

Заметим, что если удаляется единственный элемент, то указатели first и last получают значение nil, т.е. список становится пустым. В заключение приведем пример, иллюстрирующий высокую эффективность списков в некоторых задачах. Пример. Объединение списков. Имеется два списка, заданные указателями на начало и конец. ...

last1

first1 ...

last2

first2

Требуется добавить содержимое второго списка в конец первого, очистив при этом второй список. 28

...

first1 ...

last1

Для решения указанной задачи достаточно выполнить всего пять операторов присваивания: last1^.next:=first2; first2^.prev:=last1; last1:=last2; first2:=nil; last2:=nil; Заметим, что решение аналогичной задачи для массива требует использования цикла с числом итераций, равным размеру добавляемого массива.

3 Абстрактные типы данных и их реализация. Классы До сих пор мы сталкивались с конкретными типами данных, простыми или составными (массивы, записи, списки). Каждый тип данных характеризуется: • набором допустимых значений; • операциями, которые можно выполнять над данными этого типа; • внутренним представлением данных этого типа в оперативной памяти. В большинстве случаев для клиента, использующего тип данных, важны лишь первые два пункта. Например, при работе с данными вещественного типа обычно достаточно знать, что над ними можно производить арифметические операции, а также необходимо знать минимальное и максимальное положительное вещественное значение, представимое в памяти. Абстрактный тип данных (АТД) – это тип данных, доступ к которым осуществляется только через некоторый набор действий (операций, подпрограмм). Этот набор действий называется интерфейсом абстрактного типа данных. Чтобы абстрактный тип данных можно было использовать, необходимо дать реализацию всех операций, входящих в его интерфейс. Реализация при этом должна быть скрыта от клиента; данное правило называется принципом сокрытия реализации. Деление абстрактного типа данных на интерфейс и реализацию, а также сокрытие реализации, имеет несколько важных последствий. Во-первых, программист, использующий тип данных, может работать с ним только через его интерфейс, то есть вызывает только те операции, которые были предусмотрены разработчиком типа данных. Во-вторых, впоследствии разработчик абстрактного типа данных может поменять его реализацию без изменения интерфейса, что не 29

затронет клиентские программы. Тем самым обеспечивается независимость пользователя типа данных от его разработчика. Первый шаг реализации абстрактного типа данных – выбор его внутреннего представления. Если абстрактный тип данных достаточно сложен, то в качестве внутреннего представления выбирают некоторую структуру данных. Помимо структуры данных, для реализации АТД используются некоторые средства языка программирования, обеспечивающие отделение реализации от интерфейса и сокрытие реализации. В языке Паскаль такими языковыми средствами являются модули и классы. Далее мы приведем простой и часто используемый абстрактный тип данных, называемый стеком. Будут даны две его реализации: с использованием массива и односвязного списка. В качестве языковых средств будут вначале использованы модули, а затем классы.

3.1 АТД «Стек» и его реализация с помощью модуля Стек – это абстрактный тип данных, состоящий из последовательности элементов, которые можно добавлять и извлекать из этой последовательности только с одного конца, называемого вершиной стека. Кроме того, можно проверять стек на пустоту. Примером стека является колода карт, если для нее разрешено лишь добавлять или снимать карты с вершины колоды; действия с серединой колоды запрещены. Другой пример – магазин автомата, для которого также можно либо добавить патрон первым в магазин, либо убрать первый патрон из магазина.

Говорят, что стек реализует принцип LIFO – last in first out (последним пришел – первым вышел): элемент, положенный на стек последним, выходит из него первым. Будем считать, что стек хранит элементы целого типа и составим его интерфейс: procedure Push(i: integer); function Pop: integer; function Top: integer; function IsEmpty: boolean; Процедура Push кладет элемент i на вершину стека, функция Pop снимает элемент с вершины стека и возвращает его значение. Функция Top возвращает значение элемента на вершине стека, не снимая его (вместо имени Top часто используют также имя Peek). Функция IsEmpty возвращает логическое значение: пуст 30

ли стек. Очевидно, при выполнении операций Pop и Top стек должен быть непустым, что контролируется вызовом процедуры Assert. Реализация АТД «Стек» на базе массива

Реализуем АТД «Стек» в виде модуля. Модули являются удобным языковым средством для создания АТД, поскольку содержат секции интерфейса и реализации. Интерфейс стека поместим в интерфейсную секцию модуля, а реализацию – в секцию реализации модуля. Элементы стека будем хранить в целочисленном массиве, индексируемом от нуля. Индекс верхнего элемента стека будем хранить в переменной t. Если t=-1, то это означает, что стек пуст. Поскольку стек реализован на базе массива фиксированного размера, то при выполнении операции Push он может переполниться. Эта особая ситуация контролируется при помощи вызова процедуры Assert. Далее приводится текст модуля IntStack, реализующего стек целых чисел. unit IntStack; interface procedure Push(i: integer); function Pop: integer; function Top: integer; function IsEmpty: boolean; implementation const sz=1000; var a: array [0..sz-1] of integer; t: integer; procedure Push(i: integer); begin Inc(t); Assert(t<=sz); a[t]:=i; end; function Pop: integer; begin Assert(not IsEmpty); Result:=a[t]; Dec(t); end; function Top: integer; begin Assert(not IsEmpty); Result:=a[t] 31

end; function IsEmpty: boolean; begin Result := t=-1 end; initialization t:=-1; end; Отметим, что массив a, предназначенный для хранения элементов стека, и переменная t описаны в секции реализации модуля, поэтому они не видны из других модулей. Тем самым, обеспечивается принцип сокрытия реализации, позволяющий работать с абстрактным типом данных только через его интерфейс. Вычисление постфиксного выражения

Составим программу, вычисляющую значение выражения, записанного в постфиксной нотации. Для простоты договоримся, что в выражении могут присутствовать только знаки операций «+» и «*», целые однозначные числа и, возможно, пробелы. Например: 5 9 8 + 4 6 * * 7 + * Пусть выражение хранится в строке. Для его вычисления воспользуемся стеком целых чисел. Если встречено число, то кладем его на стек, если же знак операции, то снимаем со стека два последних числа, производим над ними указанную операцию и кладем результат на стек. Например, обработка операции сложения имеет вид: Push(Pop+Pop).

Проследим работу алгоритма для строки, приведенной выше. С этой целью выведем содержимое стека до и после обработки знака операции: 5 9 8 + 5 17 5 17 4 6 * 5 17 24 5 17 24 * 5 408 5 408 7 + 5 415 5 415 * 2075 (результат) Заметим, что при обработке знака операции в стеке должно быть как минимум два элемента, а после обработки знака операции количество элементов в стеке уменьшается на 1. После обработки всей строки результат лежит на вершине стека. Если после его снятия стек не пуст, значит, исходное выражение в постфиксной нотации являлось ошибочным. 32

Ниже приводится программа вычисления значения постфиксного выражения, использующая АТД «Стек», подключаемый в виде модуля IntStack: uses SysUtils,IntStack; var a: string; i: integer; begin read(a); for i:=1 to Length(a) do case a[i] of '0'..'9': Push(StrToInt(a[i])); '+': Push(Pop+Pop); '*': Push(Pop*Pop); end; Assert(IsEmpty); writeln(Pop); end. Несомненное достоинство данной реализации стека состоит в том, что она скрыта в модуле, и клиентская программа работает со стеком только через его интерфейс. Именно это обстоятельство позволяет нам поменять реализацию стека на более эффективную, не изменяя клиентскую программу. Избавимся от возможной ошибки переполнения стека. Для этого заменим массив, использующийся для хранения элементов стека, односвязным списком. Реализация АТД «Стек» на базе линейного списка

uses IntStack; ... // интерфейс остается тем же самым implementation type PNode=^Node; Node=record data: integer; next: PNode; end; var head: PNode; // указатель на вершину стека function NewNode(data: integer; next: PNode): PNode; begin New(Result); Result^.data:=data; Result^.next:=next; end; 33

procedure Push(i: integer); begin head:=NewNode(i,head); end; function Pop: integer; var v: PNode; begin Assert(not IsEmpty); v:=head; head:=head^.next; Result:=v^.data; Dispose(v); end; function Top: integer; begin Assert(not IsEmpty); Result:=head^.data; end; function IsEmpty: boolean; begin Result := head=nil; end; initialization head:=nil; finalization while not IsEmpty do Pop; end. Добавление элемента в стек и удаление элемента из стека осуществляются с использованием алгоритмов добавления и удаления из начала односвязного списка. Отметим еще раз, что клиентская программа в результате такой замены реализации стека не изменится. Реализация стека с помощью модулей имеет один большой недостаток: в программе можно использовать только один стек. Таким образом, с помощью модуля нельзя создать полноценный тип данных, позволяющий описывать несколько переменных этого типа. Для решения указанной проблемы в современных языках программирования введена особая языковая конструкция, называемая классом. Класс сочетает в себе свойства модуля и типа данных, позволяя описывать и использовать несколько переменных классового типа, называемых объектами. Использование классов при составлении программ называется программированием, ориентированным на 34

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

3.2 Классы: основные понятия АТД «Стек» на базе линейного односвязного списка (класс)

Оформим реализацию АТД «Стек» на базе линейного односвязного списка с помощью класса. После этого дадим определения основных понятий, связанных с классами. Далее приводится текст класса, реализующего стек целых чисел. type PNode=^Node; Node=record data: integer; next: PNode; end; Stack = class private head: PNode; public constructor Create; destructor Destroy; procedure Push(i: integer); function Pop: integer; function Top: integer; function IsEmpty: boolean; end; function NewNode(data: integer; next: PNode): PNode; begin New(Result); Result^.data:=data; Result^.next:=next; end; constructor Stack.Create; begin head:=nil; end; destructor Stack.Destroy; begin while not IsEmpty do 35

Pop; end; procedure Stack.Push(i: integer); begin head:=NewNode(i,head); end; function Stack.Pop: integer; var v: PNode; begin Assert(not IsEmpty); v:=head; head:=head^.next; Result:=v^.data; dispose(v); end; function Stack.IsEmpty: boolean; begin Result:= head=nil; end; function Stack.Top: integer; begin Assert(not IsEmpty); Result:=head^.data; end; Классы и объекты

Итак, что такое класс? Класс – это реализация абстрактного типа данных в языке программирования. Класс сочетает в себе свойства модуля и типа данных. С одной стороны, класс является модулем: он содержит интерфейс и реализацию, обеспечивает защиту данных. С другой стороны, класс является типом данных: можно описать любое количество переменных типа класс, эти переменные определенным образом хранятся в оперативной памяти, операции над переменными этого типа определяются в интерфейсе класса. Классовые переменные называются экземплярами класса, или объектами. По описанию класс похож на запись, однако, вместо зарезервированного слова record используется слово class. Описание класса состоит из описаний полей и заголовков методов – подпрограмм, осуществляющих доступ к полям. Разновидностями методов являются две особые подпрограммы – конструктор и деструктор, предназначенные для создания и разрушения объектов. Реализация методов должна быть дана позднее, при этом в заголовке метода перед его именем 36

указывается имя класса с последующей точкой. Совокупность методов образует интерфейс класса. Принцип объединения в одной оболочке полей и методов для доступа к этим полям и работы с ними называется инкапсуляцией (encapsulation, «как бы в капсуле»). Инкапсуляция предусматривает также защиту доступа: у класса имеется закрытая (private, приватная) и открытая (public, публичная) часть. Обычно в закрытую часть помещаются все поля и некоторые вспомогательные методы. Методы в открытой части образуют открытый интерфейс класса. Доступ к полям и методам из приватной части возможен только из методов этого класса. Например, в методе Push класса Stack осуществляется доступ к приватному полю head. Доступ к полям и методам из публичной части возможен отовсюду. В Delphi имеется небольшое ослабление правил доступа: к приватной части класса доступ возможен отовсюду из модуля, в котором данный класс определен. Поскольку, создавая класс, мы определяем новый тип данных общего пользования, то обычно классы описываются в модуле. При этом объявление класса помещается в секцию интерфейса модуля, а реализация его методов – в секцию реализации модуля. Заметим, что описания классов внутри подпрограмм в Delphi запрещены. Конструкторы и деструкторы

В состав любого класса входят два специальных метода – конструктор и деструктор. Их объявления аналогичны объявлению метода-процедуры, но вместо зарезервированного слова procedure используются зарезервированные слова constructor и destructor. Традиционно в Delphi конструктор принято именовать Create, а деструктор – Destroy. В классе может быть несколько конструкторов с разными наборами параметров, а деструктор, как правило, один и не имеет параметров. Конструктор выделяет место под объект в динамической памяти и возвращает адрес начала этого участка памяти, а также инициализирует поля созданного объекта. Этот адрес присваивается переменной-объекту. Вызов конструктора имеет следующий вид: ИмяОбъекта := ИмяКласса.ИмяКонструктора(параметры); Например, в результате создания объекта var s1: Stack; begin s1:=Stack.Create; мы получим следующую структуру в оперативной памяти:

37

Далее мы можем вызвать любой метод объекта, используя такую же точечную нотацию, что и при обращении к полю объекта: s1.Push(5); В результате структура в оперативной памяти изменится следующим образом:

Заметим, что хотя s1 и хранит адрес объекта, при доступе к объекту не требует использования операции разыменования ^, т.е. имя переменной класса является как бы разыменованным указателем. Таким образом, переменная-объект по существу представляет собой ссылку на объект в динамической памяти. Деструктор разрушает объект в динамической памяти, его вызов производится как вызов обычного метода: s1.Destroy;

До вызова конструктора и после вызова деструктора обращение к полям объекта и вызов его методов приводят к ошибке времени выполнения. Ссылочная природа объектов в языке Delphi Pascal приводит к следующим особенностям выполнения операций присваивания и сравнения объектов. При присваивании объектов (s1:=s2) в переменную s1 записывается тот адрес, который хранится в переменной s2, в результате чего s1 и s2 будут указывать на один и тот же объект в динамической памяти. Если требуется отметить, что переменная типа класс не связана ни с каким объектом в динамической памяти, ей присваивают значение nil: s1:=nil. При сравнении (s1=s2, s1<>s2) происходит сравнение адресов объектов, то есть две переменных-объекта считаются равными только тогда, когда они ссылаются на один и тот же объект в динамической памяти. Клиентская программа для АТД «Стек»

Задача. Дана последовательность целых положительных чисел, признаком ее завершения служит число 0. Вывести сначала все четные числа в обратном порядке, а затем все нечетные – также в обратном порядке. Решение. Воспользуемся двумя стеками; по мере считывания четные числа будем помещать в первый стек (s1), нечетные – во второй (s2). По окончании ввода выведем содержимое обоих стеков. 38

Пусть описание класса Stack помещено в модуль IntStack.pas. Далее приводится код программы, решающей поставленную задачу: uses IntStack; var s1,s2: Stack; x: integer; begin s1:=Stack.Create; // создание и инициализация s2:=Stack.Create; while True do // заполнение begin read(x) if x=0 then break; if Odd(x) then s2.Push(x) else s1.Push(x); end; while not s1.IsEmpty do // вывод write (s1.Pop,' '); while not s2.IsEmpty do write (s2.Pop,' '); writeln; s1.Destroy; // разрушение s2.Destroy; end. Переменная Self

Рассмотрим следующий код: function Stack.IsEmpty: boolean; begin Result := head=nil; end; Каким образом при вызове метода s1.IsEmpty осуществляется доступ к полю head именно объекта s1? Ведь нигде в теле метода имя s1 не указано! Оказывается, в каждый метод неявно первым параметром передается специальная переменная Self, являющаяся ссылкой на объект класса, вызвавшего данный метод. Кроме того, переменная Self неявно добавляется при обращении к полям и методам данного класса, используемым в теле метода. Таким образом, для компилятора метод IsEmpty имеет вид:

39

function Stack.IsEmpty(Self: IntStack): boolean; begin Result := Self.head=nil; end; При вызове s1.IsEmpty компилятор добавляет в качестве первого параметра объект, вызвавший метод: s1.IsEmpty(s1). Таким образом, переменная Self вводится внутри метода неявно (как и переменная Result внутри функции) и обозначает ссылку на объект, вызвавший метод, то есть ссылку на самого себя.

3.3 Класс «Очередь» Очередь – это абстрактный тип данных, состоящий из последовательности элементов, которые можно добавлять в конец, а извлекать из начала. Как и стек, очередь можно проверять на пустоту. Говорят, что очередь реализует принцип FIFO – first in first out (первым пришел – первым вышел): элемент, добавленный в очередь первым, будет извлечен из нее также первым. Составим открытый интерфейс класса, представляющего очередь целых чисел: type Queue = class public constructor Create; destructor Destroy; procedure Enqueue(i: integer); function Dequeue: integer; function First: integer; function IsEmpty: boolean; end; Процедура Enqueue добавляет элемент i в конец очереди, функция Dequeue извлекает из очереди первый элемент и возвращает его значение, функция First возвращает значение первого элемента, не извлекая его из очереди, и, наконец, функция IsEmpty возвращает логическое значение True, если очередь пуста, и False в противном случае. Очевидно, при выполнении операций Enqueue и First очередь должна быть непустой, что проверяется с помощью вызова процедуры Assert. Отметим, что иногда вместо имен Enqueue и Dequeue используются имена Push и Pop. Клиентская программа для класса «Очередь»

Задача. Дана последовательность целых положительных чисел, заканчивающаяся числом 0. Вывести сначала нечетные, а потом двузначные числа в том же порядке, что и в исходной последовательности. 40

Решение. Будем считать, что класс Queue, представляющий очередь целых, реализован в модуле IntQueue. При вводе будем записывать нечетные числа в первую очередь, а двузначные – во вторую. По окончании ввода выведем обе очереди. Далее приводится код решения: uses IntQueue; var q1,q2: Queue; x: integer; begin q1:=Queue.Create; q2:=Queue.Create; while True do begin read(x); if x=0 then break; if Odd(x) then q1.Enqueue(x); if (x>=10) and (x<=99) then q2.Enqueue(x); end; while not q1.IsEmpty do write(q1.Dequeue,' '); while not q2.IsEmpty do write(q2.Dequeue,' '); q1.Destroy; q2.Destroy; end; Заметим, что клиентская программа уже написана, а мы еще не приступали к реализации класса «Очередь». Данный подход иллюстрирует модификацию метода программирования сверху вниз применительно к абстрактным типам данных: вначале составляется интерфейс АТД, после чего можно писать клиентские программы, пользующиеся этим АТД. Реализация же АТД автора клиентской программы не интересует. Класс «Очередь» на базе линейного односвязного списка

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

f

l

Вначале список пуст: f=l=nil. 41

Добавление элемента будем проводить в конец очереди. Для этого вначале создадим новый узел и, если список не пуст, свяжем с ним поле next последнего элемента. Если же список пуст, то добавляемый элемент является первым, поэтому присвоим указателю f его адрес. В любом случае добавленный элемент является последним, поэтому присвоим указателю l адрес добавленного элемента: v:=NewNode(i,nil); if IsEmpty then f:=v else l^.next:=v; l:=v; Извлечение элемента будем проводить из начала очереди. Для этого сохраним адрес первого элемента во вспомогательном указателе, переместим указатель f на следующий элемент очереди и удалим элемент, адрес которого сохранен во вспомогательном указателе, предварительно вернув значение удаляемого элемента. Если удаляемый элемент является последним, то изменим также l на nil:

v

f

l

v:=f; f:=f^.next; if f=nil then l:=nil; Result:=v^.data; Dispose(v); Поместим реализацию класса «Очередь целых» в модуль IntQueue. Удобно также ввести имя для типа элементов очереди: type DataType=integer; Если теперь потребуется создать, скажем, очередь вещественных элементов, то следует скопировать содержимое файла IntQueue.pas в файл RealQuеue.pas и изменить в нем определение типа DataType: type DataType=real; Приведем код модуля IntQueue: unit IntQueue; interface type DataType = integer; Queue = class private f,l: PNode; 42

public constructor Create; destructor Destroy; procedure Enqueue(i: DataType); function Dequeue: DataType; function First: DataType; function IsEmpty: boolean; end; implementation constructor Queue.Create; begin f:=nil; l:=nil; end; destructor Queue.Destroy; begin while not IsEmpty do Dequeue; end; procedure Queue.Enqueue(i: DataType); var v: PNode; begin v:=NewNode(i,nil); if IsEmpty then f:=v else l^.next:=v; l:=v; end; function Queue.Dequeue: DataType; var v: PNode; begin Assert(not IsEmpty); v:=f; f:=f^.next; if f=nil then l:=nil; Result:=v^.data; Dispose(v); end; function Queue.IsEmpty: DataType; begin 43

Result:=f=nil; end; function Queue.First: DataType; begin Assert(not IsEmpty); Result:=f^.data; end; end. При выполнении операций Dequeue и First осуществляется проверка утверждения Assert(not IsEmpty), как и при выполнении аналогичных операций для стека. Одновременное использование очередей с разными типами элементов

При использовании в одной программе очередей с разными типами элементов перед именем типа Queue следует указывать имя модуля во избежание ошибки неоднозначности имени Queue во время компиляции. Например, вот как следует использовать в одной программе очередь целых и очередь вещественных: uses IntQueue, RealQueue; var q1: IntQueue.Queue; q2: RealQueue.Queue; begin q1:= IntQueue.Queue.Create; q2:= RealQueue.Queue.Create; ... Для удобства можно также в основной программе ввести другие имена для типов IntQueue.Queue и RealQueue.Queue: uses IntQueue,RealQueue; type IQueue=IntQueue.Queue; RQueue=RealQueue.Queue; var q1: IQueue; q2: RQueue; begin q1:= IQueue.Create; q2:= RQueue.Create; ... Разумеется, в модулях IntQueue и RealQueue можно сразу дать очередям разных типов имена IQueue и RQueue. Но такой способ менее удобен, поскольку потребует менять не только имя типа DataType, но и менять имя типа очереди по всему модулю (в частности, при определении всех методов). К сожалению, в языке Delphi Pascal отсутствует возможность создавать классы, параметризованные некоторым типом (например, Queue; такая воз44

можность имеется в C++ (шаблоны классов) и C# (generic-классы)). Это приводит к тому, что в Delphi Pascal для каждого типа элементов необходимо создавать модули и классы с идентичным содержимым, отличающимся только определением типа DataType.

Литература 1. Зеленяк О. Практикум программирования на Turbo Pascal / О. Зеленяк. – М.: DiaSoft, 2002. – 310 с. 2. Ставровский А. Турбо Паскаль 7.0 / А.Ставровский. – Киев: BHV, 2001. – 400 с. 3. Вирт Н. Алгоритмы и структуры данных / Н. Вирт. – М.: Мир, 1989. – 360 с.

45