Основы программирования — второй семестр 08-09; Михалкович С.С.; V часть

АТД — Абстрактные Типы Данных

Что мы знаем о классах

1. Класс — это составной тип данных
2. Класс, как и запись, содержит поля и методы
3. Переменная типа класс и переменная типа запись по-разному хранятся в памяти (ссылочная и размерная организация данных)
4. Для создания объекта класса и связывания его с переменной класса вызывается специальная функция-метод, называемая конструктором
5. Можно создавать шаблоны классов, параметризованные одним или несколькими типами

Лекция 10

Абстрактные типы данных

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

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

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

Итак, абстрактный тип данных - это интерфейс, набор операций без реализации.

Класс является одной из возможных реализацией абстрактного типа данных (АТД).
Т.е. класс определяет интерфейс абстрактного типа данных и дает реализацию этого интерфейса (без которой использование АТД невозможно).

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

Более того, реализацию в классе принято скрывать от клиента специальными конструкциями.
Этот принцип называется принципом сокрытия реализации (или защитой доступа).

Рассмотрим пример абстрактного типа данных — стек.

АТД стек

Стек - это набор данных, устроенный по принципу LIFO (Last In First Out) - последним пришел - первым вышел.

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

Хорошим примером стека является колода карт и магазин автомата.

Опишем операции со стеком

1. Положить значение на вершину стека (Push, втолкнуть значение в стек)
2. Вернуть значение на вершине стека (Peek)
3. Взять значение с вершины стека и вернуть его (Pop, вытолкнуть значение из стека)
4. Пуст ли стек (IsEmpty)

Опишем интерфейс стека в виде класса:

type Stack = class
  procedure Push(i: integer);
  function Pop: integer;
  function Peek: integer;
  function IsEmpty: boolean;
end;

Воспользуемся им в клиентской программе

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

a='598+46**7+*' 

Каждый символ представляет собой или число из одной цифры или знак операции. Требуется найти значение выражения.

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

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

5 9 8 
+ 
5 17
5 17 4 6 
* 
5 17 24
* 
5 408
5 408 7 
+ 
5 415 
*
2075

Пусть класс Стек определен в модуле Collections. Код клиентской программы:

uses Collections;
var 
  a: string;
  s: Stack := new Stack;
begin
  read(a);
  for var i:=1 to Length(a) do
    case a[i] of
      '0'..'9': s.Push(StrToInt(a[i]));
      '+': s.Push(s.Pop+s.Pop);
      '*': s.Push(s.Pop*s.Pop);
    end;
  writeln(s.Pop);
  Assert(s.IsEmpty);
end.

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