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

Содержание

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

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

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

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

Лекция 10

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

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

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

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

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

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

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

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

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

АТД Стек

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

Мы уже знакомы со стеком. Хорошими примерами могут служить программный стек, колода карт или магазин автомата.
Т.о. стек следует представлять как стопку объектов, положенных один на другой. В каждый момент можно:

положить значение на вершину стека (Push, втолкнуть значение в стек)
посмотреть значение на вершине стека (Top)
снять значение с вершины стека (Pop)
проверить, пуст ли стек (IsEmpty)

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

Описывать стек будем в виде класса.

<xh4>Интерфейс класса Stack</xh4>

type 
  /// Шаблон класса Stack
  Stack<T> = class 
    constructor Create;
     
    /// Кладет элемент x на вершину стека
    procedure Push(x: T);

    /// Возвращает элемент типа T, снимая его с вершины стека
    function Pop: T;
    /// Возвращает значение элемента на вершине стека
    function Top: T;

    /// Возвращает истину, если стек пуст
    function IsEmpty: boolean;
  end;

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

Теперь, когда у нас есть интерфейс класса Stack , напишем клиентскую программу.
Задача. Вычислить выражение, записанное в обратной польской записи (ПОЛИЗ).

Пусть в строке a хранится выражение в обратной польской бесскобочной нотации, например:
a = '598+46**7+*'
Условимся, что каждый символ представляет собой либо цифру, являющуюся числом, либо знак, являющийся операцией.

<xh4> Алгоритм вычисления выражения в ПОЛИЗ </xh4>

Цикл по символам {
  если текущий символ — цифра, то
    положить её на стек
  иначе, если текущий символ — знак операции, то {
    снять со стека два последних числа
    совершить над ними указанную операцию
    поместить результат на стек
  }
}

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

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

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

uses Collections;

var 
  a: string := '598+46**7+*';
  s: Stack<real> := new Stack<real>;

begin
  for var i := 1 to a.Length do
    case a[i] of
      '0'..'9': s.Push(StrToInt(a[i]));
      '+': s.Push(s.Pop + s.Pop);
      '*': s.Push(s.Pop * s.Pop);
      '-': begin
             var minuend := s.Pop;
             var subtrahend := s.Pop;
             s.Push(minuend - subtrahend);
           end;
      '/': begin
             var dividend := s.Pop;
             var divisor := s.Pop;
             s.Push(dividend / divisor);
           end;
    end;
  writeln(s.Pop);
  Assert(s.IsEmpty);
end.

Замечание 1. Именно деление на интерфейс и реализацию позволило нам приступить к написанию клиентской программы, имея только интерфейс класса Stack и ничего не зная о его реализации.
Т.о. в большом проекте налицо разделение обязанностей:

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

При таком способе разделения обязанностей обычно используется следующий сценарий:

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

Замечание 2. Поскольку интерфейс впоследствии поменять практически нельзя (в отличие от реализации), разработка интерфейсов является важнейшим мероприятием на начальном этапе разработки проекта.

<xh4> Реализация стека на базе массива </xh4>

unit Collections;

interface

type
  /// Шаблон класса Stack
  Stack<T> = class
  private    // содержимое этой секции недоступно из клиентской программы  
    /// Массив элементов стека
    datas: array of T;
    /// Индекс первого пустого элемента
    tp: integer;  
   
  public     // содержимое этой секции открыто для клиентской программы
    constructor Create;

    /// Кладет элемент x на вершину стека
    procedure Push(x: T);

    /// Возвращает элемент типа T, снимая его с вершины стека
    function Pop: T;
    /// Возвращает значение элемента на вершине стека
    function Top: T;

    /// Возвращает истину, если стек пуст
    function IsEmpty: boolean;
  end;
   
implementation

/// Максимальный размер стека
const MAX_STACK = 1000;

constructor Stack<T>.Create;
begin
  tp := 0;
  SetLength(datas, MAX_STACK);
end;

{Кладет элемент x на вершину стека} 
procedure Stack<T>.Push(x: T);
begin
  Assert(tp < MAX_STACK);
  datas[tp] := x;
  tp += 1;
end;

{Возвращает элемент типа T, снимая его с вершины стека}
function Stack<T>.Pop: T;
begin
  Assert(not IsEmpty);
  result := datas[tp-1];
  tp -= 1;
end;

{Возвращает значение элемента на вершине стека}
function Stack<T>.Top: T;
begin
  Assert(not IsEmpty);
  result := datas[tp-1];
end;

{Возвращает истину, если стек пуст}
function Stack<T>.IsEmpty: boolean;
begin
  result := (tp <= 0);
end;

end.

<xh4> Реализация стека на базе односвязного линейного списка </xh4>

unit Nodes;

interface

type
  /// Узел с одним полем связи
  SingleNode<DataType> = class
    /// Значение
    data: DataType;
    /// Ссылка на следующий элемент
    next: SingleNode<DataType>;
    
    constructor (dt: DataType; nxt: SingleNode<DataType>);
    begin
      data := dt;
      next := nxt;
    end;
  end;

implementation

end.

unit Collections;

interface

uses Nodes;

type
  /// Шаблон класса Stack
  Stack<T> = class
  private    // содержимое этой секции недоступно из клиентской программы  
    /// Указатель на вершину стека
    tp: SingleNode<T> := nil;  
    
  public     // содержимое этой секции открыто для клиентской программы
    constructor Create;
    
    /// Кладет элемент x на вершину стека
    procedure Push(x: T);

    /// Возвращает элемент типа T, снимая его с вершины стека
    function Pop: T;
    /// Возвращает значение элемента на вершине стека
    function Top: T;
    
    /// Возвращает истину, если стек пуст
    function IsEmpty: boolean; 
  end;

implementation

constructor Stack<T>.Create;
begin
  tp := nil;
end;

{Кладет элемент x на вершину стека} 
procedure Stack<T>.Push(x: T);
begin
  tp := new SingleNode<T>(x, tp);
end;

{Возвращает элемент типа T, снимая его с вершины стека}
function Stack<T>.Pop: T;
begin
  Assert(not IsEmpty);
  result := tp.data;
  tp := tp.next;
end;

{Возвращает значение элемента на вершине стека}
function Stack<T>.Top: T;
begin
  Assert(not IsEmpty);
  result := tp.data;
end;

{Возвращает истину, если стек пуст}
function Stack<T>.IsEmpty: boolean;
begin
  result := (tp = nil);
end;

end.

Лекция 11

АТД и класс Очередь

Очередь — это набор данных, устроенный по принципу FIFO (First In First Out) — первым пришел — первым вышел.

В каждый момент можно:

добавить значение в хвост очереди (Enqueue)
убрать значение из головы очереди (Dequeue)
проверить, пуста ли очередь (IsEmpty)

Оформим АТД «очередь» в виде шаблона класса.

<xh4> Интерфейс класса Queue </xh4>

type  
  /// Шаблон класса Queue
  Queue<T> = class
    constructor Create;
    
    /// Добавляет элемент x в хвост очереди
    procedure Enqueue(x: T);
    
    /// Возвращает элемент типа T, убирая его из головы очереди
    function Dequeue: T;
    
    /// Возвращает истину, если очередь пуста
    function IsEmpty: boolean; 
  end;

<xh4> Реализация очереди на базе односвязного линейного списка </xh4>

unit Collections;

interface

uses Nodes;

type
  // Здесь описан шаблон класса Stack

  /// Шаблон класса Queue
  Queue<T> = class
  private
    /// Голова очереди
    head: SingleNode<T>;
    /// Хвост очереди
    tail: SingleNode<T>;
    
  public
    constructor Create;
    
    /// Добавляет элемент x в хвост очереди
    procedure Enqueue(x: T);
    
    /// Возвращает элемент типа T, убирая его из головы очереди
    function Dequeue: T;
    
    /// Возвращает истину, если очередь пуста
    function IsEmpty: boolean;
  
  end;

implementation

// Здесь реализованы методы шаблона класса Stack

constructor Queue<T>.Create;
begin
  head := nil;
  tail := nil;
end;

{Добавляет элемент x в хвост очереди} 
procedure Queue<T>.Enqueue(x: T);
begin
  if IsEmpty then
  begin
    head := new SingleNode<T>(x, nil);
    tail := head;
  end
  else  // if not IsEmpty
  begin
    tail.next := new SingleNode<T>(x, nil);
    tail := tail.next;
  end;
end;

{Возвращает элемент типа T, убирая его из головы очереди}
function Queue<T>.Dequeue: T;
begin
  Assert(not IsEmpty);
  
  result := head.data;
  head := head.next;
  if head = nil then
    tail := nil;
end;

{Возвращает истину, если очередь пуста}
function Queue<T>.IsEmpty: boolean;
begin
  result := (head = nil);
end;
  
end.

<xh4> Примеры использования АТД Queue </xh4> Задача 1.

Вводятся натуральные числа, конец ввода - 0

Вывести: количество четных, количество нечетных, все четные в прямом порядке, все нечетные — в обратном.

Например, введены числа:

1  2  5  7  4  6  9  0

Должно быть выведено следующее:

3 // количество четных
4 // количество нечетных
2  4  6 // все четные в прямом порядке
3  7  5 // все нечетные в обратном порядке

Решение:
Эта задача имеет несколько решений, но, очевидно, самым удобным является использование изученных нами АТД — стека и очереди.
Очередь организована по принципу FIFO, а значит подходит для вывода чисел в прямом порядке, в то время как для обратного вывода надо воспользоваться стеком, организованным по принципу LIFO.

uses Collections;

var
  /// для хранения четных чисел
  q: Queue<integer>;  
  /// для хранения нечетных чисел
  s: Stack<integer>;
  
  /// количество четных чисел
  cEven: integer;
  /// количество нечетных чисел
  cOdd: integer;
  
begin
  q := new Queue<integer>;
  cEven := 0;
  s := new Stack<integer>;
  cOdd := 0;
  
  while True do
  begin
    var x: integer;
    read(x);
    
    if x = 0 then
      break;
    Assert(x > 0);  // по условию задачи должны вводиться натуральные числа
    
    if Odd(x) then
    begin
      cOdd += 1;
      s.Push(x);
    end
    else  // if x is even
    begin
      cEven += 1;
      q.Enqueue(x);
    end;
  end;
  
  writeln('Количество четных = ', cEven);
  writeln('Количество нечетных = ', cOdd);

  write('Четные в прямом порядке: ');
  while not q.IsEmpty do
    write(q.Dequeue, '  ');
  writeln();
  
  write('Нечетные в обратном порядке: ');
  while not s.IsEmpty do
    write(s.Pop, '  ');
end.

Задача 2. Обслуживание клиентов в очереди (категория использование АТД при моделировании).
Спецификация задачи: Имеется очередь клиентов.
Первоначально она пуста.
В течение рабочего дня (7*60 минут) происходят следующие случайные события:

приход клиента;
обслуживание клиента в очереди;

Время перед приходом нового клиента TimeBeforeNewClient и время обслуживания текущего клиента ServeTime генерируются случайно.
Будем считать, что функция RandomClient возвращает нового клиента.

Решение:

uses Collections;

type
  /// Клиент
  Client = class
    /// Имя клиента
    name: string;
    /// Сумма денег
    money: integer;
    
    constructor (pName: string; pMoney: integer);
    begin
      name := pName;
      money := pMoney;
    end;
    
    procedure Println;
    begin
      write('Имя: ', name);
      writeln('  Наличные: ', money);
    end;
  end;

/// Возвращает случайного клиента  
function RandomClient: Client;
begin
  case Random(3) of
    0 : result := new Client('Иванов', Random(100, 1000));
    1 : result := new Client('Петрова', Random(1, 1000000));
    2 : result := new Client('Сидоров', Random(1000, 10000));
  end;
end;
  
const
  /// Количество часов рабочего дня
  WORKING_DAY = 7;
  /// Количество минут в часе
  MIN_IN_HOUR = 60;
  
  /// Минимальное время до прихода нового клиента
  MIN_BEFOR_NEW = 1;
  /// Максимальное время до прихода нового клиента
  MAX_BEFOR_NEW = 10;
  /// Минимальное время обслуживания клиента
  MIN_SERVE = 4;
  /// Максимальное время обслуживания клиента
  MAX_SERVE = 9;
 
/// Выводит время в часах и минутах  
procedure PrintTime(cMinutes : integer);
begin
  var hours := cMinutes div MIN_IN_HOUR;
  var minutes := cMinutes mod MIN_IN_HOUR;
  
  write(hours:2, ' : ', minutes:2);
end;

var 
  /// Очередь клиентов
  ClientQueue := new Queue<Client>;
  
  /// Время до обслуживания нового клиента
  TimeBeforeNewClient: integer;
  /// Врямя, требующееся на обслуживание клиента
  ServeTime: integer;
  
  
begin
  TimeBeforeNewClient := 0;
  ServeTime := 0;

  for var t := 1 to WORKING_DAY * MIN_IN_HOUR do
  begin
    if TimeBeforeNewClient = 0 then   // пришел новый клиент
    begin
      var rCl := RandomClient;
      ClientQueue.Enqueue(rCl);
      TimeBeforeNewClient := Random(MIN_BEFOR_NEW, MAX_BEFOR_NEW);
      
      PrintTime(t); write(' Пришел: ');
      rCl.Println;
    end;
    
    if (ServeTime = 0) and not ClientQueue.IsEmpty then  // подошло время обслуживать клиента
    begin
      var rCl := ClientQueue.Dequeue;
      ServeTime := Random(MIN_SERVE, MAX_SERVE);
      
      PrintTime(t); write(' Обслужен: ');
      rCl.Println;
    end;
    
    if TimeBeforeNewClient > 0 then
      TimeBeforeNewClient -= 1;
    if ServeTime > 0 then 
      ServeTime -= 1;
  end;
end.

Класс Динамический массив

Реализация на базе встроенного динамического массива

type DynArray<T> = class 
 constructor Create;
 constructor Create(n: T);
 procedure Reserve(newcap: integer);
 procedure Resize(newsz: integer);
 procedure Add(value: T);
 procedure SetItem(i: integer; value: T);
 function GetItem(i: integer): T;
 property Capacity: integer;
 property Count: integer;
 property Items[i: integer]: T; default;
end;

Класс Множество

Реализация на базе БДП

Класс Ассоциативный массив

Реализация на базе БДП

Пространства имен .NET и их использование в секции uses.

Основные контейнерные классы библиотеки .NET

Списки .NET, итерация по списку, понятие итератора

Перегрузка операций