Методические указания для студентов 1 курса факультета математики, механики и компьютерных наук

Вид материала

Содержание

3Абстрактные типы данных и их реализация. Классы
Абстрактный тип данных
3.1АТД «Стек» и его реализация с помощью модуля
Реализация АТД «Стек» на базе массива
Вычисление постфиксного выражения
Реализация АТД «Стек» на базе линейного списка

Подобный материал:

1 2 3 4 5 6 7 8

3Абстрактные типы данных и их реализация. Классы

До сих пор мы сталкивались с конкретными типами данных, простыми или составными (массивы, записи, списки). Каждый тип данных характеризуется:

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

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

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

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

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

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

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 возвращает логическое значение: пуст ли стек. Очевидно, при выполнении операций 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]

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. После обработки всей строки результат лежит на вершине стека. Если после его снятия стек не пуст, значит, исходное выражение в постфиксной нотации являлось ошибочным.

Ниже приводится программа вычисления значения постфиксного выражения, использующая АТД «Стек», подключаемый в виде модуля 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;

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.

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

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

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