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

Материал из Вики ИТ мехмата ЮФУ
Версия от 17:14, 1 мая 2009; Juliet (обсуждение | вклад) (→‎Стандартные контейнерные классы библиотеки .NET и пространство имен System.Collections.Generic)

Перейти к: навигация, поиск

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

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

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

Лекция 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> 

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

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

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

ε (пусто)
5
5 9
5 9 8 

5 9 8 
   + 
5 17

5 17 4 
5 17 4 6 

5 17 4 6
      * 
5 17 24

5 17 24
    * 
5 408

5 408 7 

5 408 7
     + 
5 415 

5 415
 *
2075

Запрограммируем этот алгоритм.
Пусть класс 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_BEFORE_NEW = 1;
  /// Максимальное время до прихода нового клиента
  MAX_BEFORE_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_BEFORE_NEW, MAX_BEFORE_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.

Лекция 12

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

Задача.

  • Реализовать АТД DynArray, который хранит данные одного типа, доступные по индексу;
  • Индекс — единственный, целочисленный, нумеруется с нуля;
  • В процессе работы программы объекты класса DynArray должны автоматически уметь менять размер памяти, отведенной под массив;
Уже ясно, что этот АТД — не просто array of T.
Назовем array of T встроенным типом динамического массива.

Уточнение спецификации.

Будем строить класс динамический массив на базе встроенного динамического массива.
Для автоматического изменения размера при выполнении программы обеспечим следующее поведение:
  • под массив выделяется некоторая память размера Capacity (емкость)
  • однако, данная память будет заполнена лишь на Count <= Capacity (*) элементов, где Count — количество элементов, размер массива.
Как только, при некоторой операции, неравенство (*) перестает выполняться, то есть Count > Capacity, мы увеличим емкость Capacity, сделав её, например, Count * 2.
При изменении размера массива все старые данные должны сохраняться.
По возможности, необходимо обеспечивать, чтобы емкость массива была немного больше размера для дальнейших расширений.

<xh4> Реализация ДМ в виде шаблона класса </xh4> 

unit Collections;
 
interface
 
uses Nodes;
 
type
  // Здесь описан шаблон класса Stack
 
  // Здесь описан шаблон класса Queue

const
  /// Минимальная емкость, устанавливаемая при создании массива
  MIN_CAP = 4;
  /// Коэффициент увеличения емкости массива при её нехватке
  INC_CAP_FACTOR = 2;

type
  /// Шаблон класса DynArray [Динамический массив с автоконтролем памяти]
  DynArray<DataType> = class
  private
    /// Встроенный динамический массив, содержащий данные
    data: array of DataType;
    /// Размер массива
    size: integer;
    /// Емкость массива
    cap: integer;
    
  public
    /// Создает массив размера pSize
    constructor Create(pSize: integer := 0);
    
    /// Выделяет новую память. Емкость увеличивается до newCap
    /// (Если newCap меньше текущей емкости, ничего не происходит)
    procedure Reserve(newCap: integer);
    /// Устанавливает размер массива равным newSize
    procedure Resize(newSize: integer);
    
    /// Добавляет элемент x в конец массива
    procedure Add(x: DataType);

    /// Устанавливает элемент с индексом ind равным x
    procedure SetElem(ind: integer; x: DataType);
    /// Возвращает элемент массива с индексом ind
    function GetElem(ind: integer): DataType;
    
    /// Возвращает индекс первого элемента массива равного x
    /// или -1, если такого элемента нет
    function Find(x: DataType): integer;
  
    /// Вставляет в позицию pos элемент x 
    procedure Insert(pos: integer; x: DataType);
    /// Удаляет элемент из позиции pos
    procedure Delete(pos: integer);
  end; 

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

// Здесь реализованы методы шаблона класса Queue
 
{Создает массив размера pSize}
constructor DynArray<DataType>.Create(pSize: integer);
begin
  size := pSize;
  cap := INC_CAP_FACTOR*pSize + MIN_CAP; // Устанавливаем емкость "с запасом"
  SetLength(data, cap);
end;

{Выделяет новую память. Емкость увеличивается до newCap
 (Если newCap меньше текущей емкости, ничего не происходит)}
procedure DynArray<DataType>.Reserve(newCap: integer);
begin
  if newCap > cap then 
  begin
    SetLength(data, newCap);
    cap := newCap;
  end;
end;

{Устанавливает размер массива равным newSize}
procedure DynArray<DataType>.Resize(newSize: integer);
begin
  if newSize <= cap then
    size := newSize
  else
  begin
    Reserve(INC_CAP_FACTOR * newSize);
    for var i := size to newSize - 1 do // явным образом заполняем новые элементы
      data[i] := default(DataType);
    size := newSize;
  end;
end;

{Добавляет элемент x в конец массива}
procedure DynArray<DataType>.Add(x: DataType);
begin
  Resize(size + 1);
  data[size-1] := x;
end;

{Устанавливает элемент с индексом ind равным x}
procedure DynArray<DataType>.SetElem(ind: integer; x: DataType);
begin
  Assert((0 <= ind) and (ind <= size-1));
  data[ind] := x;
end;

{Возвращает элемент массива с индексом ind}
function DynArray<DataType>.GetElem(ind: integer): DataType;
begin
  Assert((0 <= ind) and (ind <= size-1));
  result := data[ind];
end;

{Возвращает индекс первого элемента массива равного x
 или -1, если такого элемента нет}
function DynArray<DataType>.Find(x: DataType): integer;
begin
  result := -1;
  for var i := 0 to size - 1 do
    if data[i] = x then
    begin
      result := i;
      exit;
    end;
end;

{Вставляет в позицию pos элемент x}
procedure DynArray<DataType>.Insert(pos: integer; x: DataType);
begin
  Assert((0 <= pos) and (pos <= size-1));
  Resize(size + 1);
  for var i := size - 2 downto pos do
    data[i+1] := data[i];
  data[pos] := x;
end;

{Удаляет элемент из позиции pos}
procedure DynArray<DataType>.Delete(pos: integer);
begin
  Assert((0 <= pos) and (pos <= size-1));
  for var i := pos to size - 2 do
    data[i] := data[i+1];
  Resize(size - 1);
end;


end.

Свойства класса

Создадим объект-динамический массив: 

var dyn := new DynArray<integer>(5);

Что делать, если мы хотим увеличить его размер на единицу?
Мы можем сделать это только так: 

dyn.Resize(6);

Как хотелось бы: 

dyn.size := dyn.size + 1;

Однако, мы не можем этого сделать, благодаря защите доступа. Иначе мы были бы не защищены, например, от присваивания размеру отрицательного(!) значения.

Как мы сделаем:
Станет возможно писать вот так: 

dyn.Count := dyn.Count + 1;

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

dyn.Resize(dyn.size + 1);

Count — это свойство класса («интеллектуальное поле»).
В записи 

dyn.Count := dyn.Count + 1;

справа к dyn.Count обеспечивается доступ на чтение, а слева — доступ на запись.
Оба доступа могут быть реализованы специальными методами: метод доступа на запись называется Setter, а метод доступа на чтение — Getter.

В роли метода доступа на запись для свойства Count выступает процедура Resize, меняющая значение приватного поля size.
Вместо метода доступа на чтение можно использовать непосредственно обращение к полю size.

<xh4> Как оформить свойство Count </xh4> В интерфейс класса нужно добавить: 

property Count: integer write Resize read size;

Свойство — это конструкция языка, позволяющая использовать синтаксис, идентичный обращению к полю класса, но при попытке записи в это поле приводящая к вызову метода-setter'а, а при попытке чтения — getter'а.

Аналогично можем описать свойство «ёмкость»: 

property Capacity: integer read cap write Reserve;

<xh4> Семантика </xh4> Первый вариант: 

property A: PropType read aa write SetA
aa: имя поля типа PropType
SetA: procedure SetA(x: PropType) (процедура с одним параметром типа PropType)

Второй вариант: 

property A: PropType read GetA write SetA
GetA: function GetA: PropType (функция без параметров, возвращающая значение типа PropType)
SetA: как и в первом случае, procedure SetA(x: PropType)


Замечание. Свойства не обладают всеми возможностями полей:

  • их нельзя передавать как var-параметры;
  • их нельзя использовать в таких операциях, как +=

Индексные свойства классов

Как же будет осуществляться доступ к элементам нашего динамического массива?

Как хотелось бы: 

dyn[3] := dyn[2] + 1;  // (1)

Как мы умеем: 

dyn.SetElem(3, dyn.GetElem(2) + 1);  // (2)

Нельзя ли сделать так, чтобы компилятор переводил запись (1) в (2)?
Можно.

Как это сделать: 

property Elem[i: integer]: DataType read GetElem write SetElem;

Теперь можно писать: 

dyn.Elem[3] := dyn.Elem[2] + 1;

А для корректности записи (1) необходимо сделать данное индексное свойство свойством по умолчанию. Для этого нужно использовать ключевое слово default: 

property Elem[i: integer]: DataType read GetElem write SetElem; default;

<xh4> Семантика </xh4> 

property Elem[i: IndType]: PropType read GetElem write SetElem
GetA: function GetElem(i : IndType): PropType
(функция с одним параметром, совпадающим по типу с индексом и возвращающая значение типа PropType)
SetA: procedure SetElem(i: IndType; x: PropType)
(процедура с первым параметром, совпадающим по типу с индексом, и вторым — типа PropType)
Реализация ДМ с учетом использования свойств  
unit Collections;
 
interface
 
uses Nodes;
 
type
  // Здесь описан шаблон класса Stack
 
  // Здесь описан шаблон класса Queue

const
  /// Минимальная емкость, устанавливаемая при создании массива
  MIN_CAP = 4;
  /// Коэффициент увеличения емкости массива при её нехватке
  INC_CAP_FACTOR = 2;

type
  /// Шаблон класса DynArray [Динамический массив с автоконтролем памяти]
  DynArray<DataType> = class
  private
    /// Встроенный динамический массив, содержащий данные
    data: array of DataType;
    /// Размер массива
    size: integer;
    /// Емкость массива
    cap: integer;
    
    /// Устанавливает элемент с индексом ind равным x
    procedure SetElem(ind: integer; x: DataType);
    /// Возвращает элемент массива с индексом ind
    function GetElem(ind: integer): DataType;

  public
    /// Создает массив размера pSize
    constructor Create(pSize: integer := 0);
    
    /// Выделяет новую память. Емкость увеличивается до newCap
    /// (Если newCap меньше текущей емкости, ничего не происходит)
    procedure Reserve(newCap: integer);
    /// Устанавливает размер массива равным newSize
    procedure Resize(newSize: integer);
    
    /// Добавляет элемент x в конец массива
    procedure Add(x: DataType);
    
    /// Возвращает индекс первого элемента массива равного x
    /// или -1, если такого элемента нет
    function Find(x: DataType): integer;
  
    /// Вставляет в позицию pos элемент x 
    procedure Insert(pos: integer; x: DataType);
    /// Удаляет элемент из позиции pos
    procedure Delete(pos: integer);

    /// Количество элементов (размер) массива
    property Count: integer read size write Resize;
    /// Емкость массива (отведенная память)
    property Capacity: integer read cap write Reserve;
    /// Позволяет обращаться к элементам массива по индексу 
    /// (например, apples[5])
    property Elem[index: integer]: DataType read GetElem write SetElem; default;
  end; 

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

// Здесь реализованы методы шаблона класса Queue
 
{Создает массив размера pSize}
constructor DynArray<DataType>.Create(pSize: integer);
begin
  size := pSize;
  cap := INC_CAP_FACTOR*pSize + MIN_CAP; // Устанавливаем емкость "с запасом"
  SetLength(data, cap);
end;

{Выделяет новую память. Емкость увеличивается до newCap
 (Если newCap меньше текущей емкости, ничего не происходит)}
procedure DynArray<DataType>.Reserve(newCap: integer);
begin
  if newCap > cap then 
  begin
    SetLength(data, newCap);
    cap := newCap;
  end;
end;

{Устанавливает размер массива равным newSize}
procedure DynArray<DataType>.Resize(newSize: integer);
begin
  if newSize <= cap then
    size := newSize
  else
  begin
    Reserve(INC_CAP_FACTOR * newSize);
    for var i := size to newSize - 1 do // явным образом заполняем новые элементы
      data[i] := default(DataType);
    size := newSize;
  end;
end;

{Добавляет элемент x в конец массива}
procedure DynArray<DataType>.Add(x: DataType);
begin
  Resize(size + 1);
  data[size-1] := x;
end;

{Устанавливает элемент с индексом ind равным x}
procedure DynArray<DataType>.SetElem(ind: integer; x: DataType);
begin
  Assert((0 <= ind) and (ind <= size-1));
  data[ind] := x;
end;

{Возвращает элемент массива с индексом ind}
function DynArray<DataType>.GetElem(ind: integer): DataType;
begin
  Assert((0 <= ind) and (ind <= size-1));
  result := data[ind];
end;

{Возвращает индекс первого элемента массива равного x
 или -1, если такого элемента нет}
function DynArray<DataType>.Find(x: DataType): integer;
begin
  result := -1;
  for var i := 0 to size - 1 do
    if data[i] = x then
    begin
      result := i;
      exit;
    end;
end;

{Вставляет в позицию pos элемент x}
procedure DynArray<DataType>.Insert(pos: integer; x: DataType);
begin
  Assert((0 <= pos) and (pos <= size-1));
  Resize(size + 1);
  for var i := size - 2 downto pos do
    data[i+1] := data[i];
  data[pos] := x;
end;

{Удаляет элемент из позиции pos}
procedure DynArray<DataType>.Delete(pos: integer);
begin
  Assert((0 <= pos) and (pos <= size-1));
  for var i := pos to size - 2 do
    data[i] := data[i+1];
  Resize(size - 1);
end;


end.


Лекция 13

Использование классов библиотеки .NET

Классы .NET хранятся в специальных внешних .dll.

mscorlib.dll —
библиотека в которой содержатся основные классы .NET;
подключается к PascalABC.NET автоматически.

Замечание. В .NET все типы являются классами.

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

Пространство имен —
область программы, в которой не может находиться двух объектов с одинаковыми именами (исключая имена перегруженных подпрограмм).

В Pascal'е существует:

  • глобальное пространство имен
  • пространство имен, связанное с подпрограммой
  • классом (или записью)
  • модулем

В библиотеках .NET дополнительно можно вводить именованные пространства имен:
C# 

namespace System
{
    ...
}

В PascalABC.NET нельзя определять свои пространства имен, но можно пользоваться пространствами имен .NET.
Самым важным пространством имен .NET является System.

Для подключения пространств имен .NET к основной программе используется тот же синтаксис, что и для модулей: 

uses System;

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

uses System;

var t: DateTime; // класс DateTime определен определен внутри пространства имен System

Кроме этого, можно не подключать пространство имен явно, а использовать полное имя класса, предваряя его именем пространства имен: 

var t: System.DateTime;

Генерация собственных исключений

Замечание. В большинстве языков программирования вызовы процедур Assert убираются из программного кода компилятором, если компилируется так называемая Release (релиз) версия. Это делается для скорости выполнения.
Т.о. вызовы Assert'ов работают только в Debug-версии (т.е. версии для разработчиков).
Однако, и в релиз-версии продукта возможно возникновение ошибок, которые необходимо контролировать. Для этого генерируют собственные исключения.

Все генерируемые исключения, перехватываемые в блоке 

try
...
except
...
end;

являются объектами класса System.Exception.
В нем находится конструктор, одна из версий которого имеет следующий вид: 

constructor(message: string);

Для генерации собственного исключения используется оператор raise: 

raise <переменная исключения: System.Exception>

Например: 

raise new System.Exception('Выход за границы диапазона');


Уточним, как можно модифицировать метод SetElem класса DynArray: 

...
uses System; // Чтобы писать Exception вместо System.Exception
...

procedure SetElem(ind: integer; x: DataType);
begin
  if (ind < 0) or (i >= size) then
    raise new Exception(
    IntToStr(ind) + ': Выход за границы диапазона [0..' + IntToStr(size - 1) + ']');
  ...
end;

<xh4> Как обработать свое исключение </xh4> Когда мы генерируем свое исключение, создается переменная e — объект класса System.Exception. Её то и можно отлавливать в охранном блоке: 

try
  var d := new DynArray<integer<(10);
  d[10] := 666;
except
  on e: Exception do
    writeln(e);
end;

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

<xh4> Интерфейс </xh4> 

  Add(x: DataType)
      Добавляет элемент x ко множеству, если его там еще нет

  Remove(x: DataType);
      Удаляет элемент x из множества, если он там есть

  Contains(x: DataType): boolean;
      Возвращает истину, если элемент x содержится во множестве

<xh4> Реализация </xh4> Реализуем класс SimpleSet<DataType> на базе класса DynArray<DataType>.

Замечание. Мы впервые создаем один АТД на базе другого. 

unit Collections;
 
interface
 
// Здесь описан шаблон класса Stack
// Здесь описан шаблон класса Queue
// Здесь описан шаблон класса DynArray

// ------------------------------------------- SIMPLE_SET -----------------------------------------
type 
  /// Шаблон класса SimpleSet [Простое множество]
  SimpleSet<DataType> = class 
  private
    /// Элементы множества
    data := new DynArray<DataType>;
 
  public
    /// <summary>
    /// Добавляет элемент во множество, если его там еще нет
    /// </summary>
    /// <param name="x">Добавляемый элемент</param>    
    procedure Add(x: DataType);
    /// <summary>
    /// Удаляет элемент из множества, если он там есть
    /// </summary>
    /// <param name="x">Удаляемый элемент</param>
    procedure Remove(x: DataType);
 
    /// <summary>
    /// Возвращает истину, если множество содержит элемент
    /// </summary>
    /// <param name="x">Искомый элемент</param>          
    function Contains(x: DataType): boolean;   
end;
 
 
implementation

// Здесь реализованы методы шаблона класса Stack
// Здесь реализованы методы шаблона класса Queue
// Здесь реализованы методы шаблона класса DynArray 
 
// ------------------------------------------- SIMPLE_SET -----------------------------------------
 
{Добавляет элемент x во множество, если его там еще нет}     
procedure SimpleSet<DataType>.Add(x: DataType);
begin
  if data.Find(x) = -1 then 
    data.Add(x);
end;
 
{Удаляет элемент x из множества, если он там есть}
procedure SimpleSet<DataType>.Remove(x: DataType);
begin
  var xPos := data.Find(x);
  if xPos <> -1 then
    data.Remove(xPos);
end;
 
{Возвращает истину, если множество содержит элемент x}    
function SimpleSet<DataType>.Contains(x: DataType): boolean;
begin
  result := (data.Find(x) <> -1);
end;
 
end.


Если класс для реализации своих методов вызывает методы объекта другого класса, который является полем этого внешнего класса, то такой вызов называется делегированием.

Объект класса SimpleSet<DataType> делегирует выполнение действий своему подобъекту data, который и выполняет основные действия.
Внешний класс совершает лишь базовые проверки, и его код крайне компактен.

АТД и класс Ассоциативный массив

Ассоциативный массив — это массив, у которого в качестве индексов могут фигурировать объекты произвольного типа.

Будем считать, что ассоциативный массив уже реализован. Посмотрим, что с ним можно делать: 

uses Collections;

var Zoo: AssocArray<string, integer>;

begin
  Zoo := new AssocArray<string, integer>;

  Zoo['бегемот'] := 2;
  Zoo['жираф'] := Zoo['жираф'] + 1;
  write(Zoo['крокодил']);
end.

Ассоциативные массивы реализуются в виде набора параметров 

(ключ, значение)

После выполнения нашей программы массив Zoo будет иметь вид: 

('бегемот', 2)
('жираф', 1)
('крокодил', 0)

Будем реализовывать наш ассоциативный массив в виде двух динамических массивов — для ключей и для значений. 

unit Collections;
 
interface
 
// Здесь описан шаблон класса Stack
// Здесь описан шаблон класса Queue
// Здесь описан шаблон класса DynArray
// Здесь описан шаблон класса SimpleSet
 
// ------------------------------------------- ASSOC_ARRAY ----------------------------------------
type
  /// Шаблон класса AssocArray [Ассоциативный массив]
  AssocArray<KeyType, ValueType> = class
  private
    /// Ключи
    keys: DynArray<KeyType> := new DynArray<KeyType>;
    /// Значения, соответствующие ключам
    values: DynArray<ValueType> := new DynArray<ValueType>;
 
    /// Устанавливает значение элемента с ключом key равным value
    procedure SetElem(key: KeyType; value: ValueType);
    /// Возвращает значение элемента с ключом key
    function GetElem(key: KeyType): ValueType;
 
  public
    // --------------------------------- Свойства --------------------------------
    /// Позволяет обращаться к элементам массива по ключу
    /// (Например, zoo['крокодил'])
    property Elem[key: KeyType]: ValueType read GetElem write SetElem; default;
  end;
 

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

// ------------------------------------------- ASSOC_ARRAY ----------------------------------------
 
// ---------------------------- Доступ к элементам ---------------------------
{Устанавливает значение элемента с ключом key равным value}
procedure AssocArray<KeyType, ValueType>.SetElem(key: KeyType; value: ValueType);
begin
  var ind := Keys.Find(key);
  if ind <> -1 then
    Values[ind] := value
  else
  begin
    Keys.Add(key);
    Values.Add(value);
  end;
end;
 
{Возвращает значение элемента с ключом key}
function AssocArray<KeyType, ValueType>.GetElem(key: KeyType): ValueType;
begin
  var ind := Keys.Find(key);
  if ind <> -1 then
    result := Values[ind]
  else
  begin
    Keys.Add(key);
    Values.Add(default(ValueType));
    result := default(ValueType);
  end;
end;

end.

АТД и класс Список (Linked List)

Структура данных двусвязный список обладает следующими важными преимуществами по сравнению с другими:

  • список занимает в памяти ровно столько места, каково количество его элементов;
  • операции вставки и удаления в начало(конец) и середину списка выполняются за время, не зависящее от длины списка;

Недостатки:

  • невозможность обращаться к элементу по индексу (отсутствие произвольного доступа, только последовательный);

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

<xh4> Проблемы при доступе к структуре данных «двусвязный список» </xh4> Поля Next и Prev легко изменить, «испортив» при этом список.

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

  • классов
  • защиты доступа
  • свойств

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

Вывод. Связанные классы следует помещать в один модуль.

Именно так мы и поступим с классами LinkedListNode и LinkedList: 

unit LinkedListUnit;
 
interface
 
uses System;  // для генерации исключений
 
// ========================================= LinkedListNode =======================================
type
  /// Узел с двумя полями связи
  LinkedListNode<DataType> = class
  private
    // ----------------------------------- Поля ----------------------------------
    /// Значение узла
    fData: DataType;
    /// Ссылка на предыдущий элемент
    fPrev: LinkedListNode<DataType>;
    /// Ссылка на следующий элемент
    fNext: LinkedListNode<DataType>;
 
  public
    // --------------------------------- Свойства --------------------------------
    /// Значение узла
    property Value: DataType read fData write fData;
    /// Ссылка на предыдущий элемент — только на чтение
    property Prev: LinkedListNode<DataType> read fPrev;
    /// Ссылка на следующий элемент — только на чтение
    property Next: LinkedListNode<DataType> read fNext;
 
    // ---------------------------- Стандартные методы ---------------------------
    /// <summary>
    /// Создает новый узел
    /// </summary>
    /// <param name="DataType">Значение узла</param>
    /// <param name="Prev">Ссылка на предыдущий элемент</param>
    /// <param name="Next">Ссылка на следующий элемент</param>
    constructor Create(Data: DataType; Prev, Next: LinkedListNode<DataType>);
  end;
 
 
// =========================================== LinkedList =========================================
type
  /// Двусвязный линейный список
  LinkedList<DataType> = class
  private
    /// Первый элемент (голова)
    fFirst: LinkedListNode<DataType> := nil;
    /// Последний элемент (хвост)
    fLast: LinkedListNode<DataType> := nil;
 
  public
    // --------------------------------- Свойства --------------------------------
    /// Первый элемент (голова) — только на чтение
    property First: LinkedListNode<DataType> read fFirst;
    /// Последний элемент (хвост) — только на чтение
    property Last: LinkedListNode<DataType> read fLast;
 
    // ---------------------------- Стандартные методы ---------------------------
    /// <summary>
    /// Добавляет элемент x в начало списка
    /// </summary>
    /// <param name="x">Добавляемый элемент</param>
    procedure AddFirst(x: DataType);
    /// <summary>
    /// Добавляет элемент x в конец списка
    /// </summary>
    /// <param name="x">Добавляемый элемент</param>
    procedure AddLast(x: DataType);
 
    /// Удаляет первый элемент списка
    procedure RemoveFirst();
    /// Удаляет последний элемент списка
    procedure RemoveLast();
 
    /// <summary>
    /// Добавляет элемент x перед node
    /// </summary>
    /// <param name="node">Ссылка на элемент, перед которым нужно добавить новый</param>
    /// <param name="x">Добавляемый элемент</param>
    procedure AddBefore(node: LinkedListNode<DataType>; x: DataType); 
    /// <summary>
    /// Добавляет элемент x после node
    /// </summary>
    /// <param name="node">Ссылка на элемент, после которого нужно добавить новый</param>
    /// <param name="x">Добавляемый элемент</param>
    procedure AddAfter(node: LinkedListNode<DataType>; x: DataType);
 
    /// <summary>
    /// Удаляет элемент node
    /// </summary>
    /// <param name="node">Ссылка на элемент, который нужно удалить</param>
    procedure Remove(node: LinkedListNode<DataType>);
 
    // ---------------------------------- Вывод ----------------------------------
    /// Выводит содержимое списка на консоль
    procedure Println();
    /// Выводит содержимое списка на консоль в обратном порядке
    procedure ReversePrintln();
  end;
 
 
implementation
 
// ========================================= LinkedListNode =======================================
{Создает новый узел}
constructor LinkedListNode<DataType>.Create(Data: DataType; Prev, Next: LinkedListNode<DataType>);
begin
  fData := Data;
  fPrev := Prev;
  fNext := Next;
end;
 
 
// =========================================== LinkedList =========================================
 
// ---------------------------- Стандартные методы ---------------------------
{Добавляет элемент x в начало списка}
procedure LinkedList<DataType>.AddFirst(x: DataType);
begin
  var val := new LinkedListNode<DataType>(x, nil, fFirst);
  if fFirst <> nil then
    fFirst.fPrev := val;
 
  fFirst := val;
  if fLast = nil then
    fLast := fFirst;
end;
 
{Добавляет элемент x в конец списка}
procedure LinkedList<DataType>.AddLast(x: DataType);
begin
  var val := new LinkedListNode<DataType>(x, fLast, nil);
  if fLast <> nil then
    fLast.fNext := val;
 
  fLast := val;
  if fFirst = nil then
    fFirst := fLast;
end;
 
{Удаляет первый элемент списка}
procedure LinkedList<DataType>.RemoveFirst();
begin
  if fFirst = nil then
    raise new Exception(
    'Попытка удаления из пустого списка!');
 
  fFirst := fFirst.fNext;
  if fFirst = nil then
    fLast := nil
  else
    fFirst.fPrev := nil;
end;
 
{Удаляет последний элемент списка}
procedure LinkedList<DataType>.RemoveLast();
begin
  if fLast = nil then
    raise new Exception(
    'Попытка удаления из пустого списка!');
 
  fLast := fLast.fPrev;
  if fLast = nil then
    fFirst := nil
  else
    fLast.fNext := nil;
end;
 
{Добавляет элемент x перед node}
procedure LinkedList<DataType>.AddBefore(node: LinkedListNode<DataType>; x: DataType); 
begin
  if node = nil then
    raise new Exception(
    'Аргумент node метода является нулевой ссылкой!');
 
  if node = fFirst then
    AddFirst(x)
  else
  begin
    var val := new LinkedListNode<DataType>(x, node.fPrev, node);
    node.fPrev.fNext := val;
    node.fPrev := val;
  end;
end;
 
{Добавляет элемент x после node}
procedure LinkedList<DataType>.AddAfter(node: LinkedListNode<DataType>; x: DataType);
begin
  if node = nil then
    raise new Exception(
    'Аргумент node метода является нулевой ссылкой!');
 
  if node = fLast then
    AddLast(x)
  else
  begin
    var val := new LinkedListNode<DataType>(x, node, node.fNext);
    node.fNext.fPrev := val;
    node.fNext := val;
  end;
end;
 
{Удаляет элемент node}
procedure LinkedList<DataType>.Remove(node: LinkedListNode<DataType>);
begin
  if node = nil then
    raise new Exception(
    'Аргумент node метода является нулевой ссылкой!');
 
  if node = fFirst then
    RemoveFirst
  else if node = fLast then
    RemoveLast
  else
  begin
    node.fPrev.fNext := node.fNext;
    node.fNext.fPrev := node.fPrev;
  end;
end;
 
// ---------------------------------- Вывод ----------------------------------
{Выводит содержимое списка на консоль}
procedure LinkedList<DataType>.Println();
begin
  var cur := fFirst;
  while cur <> nil do
  begin
    write(cur.Value, ' ');
    cur := cur.Next;
  end;
  writeln();
end;
 
{Выводит содержимое списка на консоль в обратном порядке}
procedure LinkedList<DataType>.ReversePrintln();
begin
  var cur := fLast;
  while cur <> nil do
  begin
    write(cur.Value, ' ');
    cur :=cur.Prev;
  end;
  writeln();
end;
 
end.


Пример 1. Проход по списку. 

var l: LinkedList<integer> := new LinkedList<integer>;
l.AddLast(1100);
l.AddLast(1300);
  
var node := l.First;
while node <> nil do
begin
  node.Value := node.Value * 2;
  node := node.Next;
end;

Пример 2.
Наполнить список целых случайными элементами.
Удалить все элементы с четными номерами (нумерация с единицы). 

uses LinkedListUnit;

const
  MAX_RAN = 200;
  
/// Возвращает список из n случайных целых чисел
/// в диапазоне [-MAX_RAN, MAX_RAN]
function CreateRandomLinkedList(n: integer): LinkedList<integer>;
begin
  result := new LinkedList<integer>;
  for var i := 1 to n do
    result.AddLast(Random(-MAX_RAN, MAX_RAN));
end;

/// Удаляет из списка list все элементы с четными номерами
/// (элементы нумеруются с 1цы)
procedure RemoveEvenNumbers(list: LinkedList<integer>);
begin
  var cur := list.First;
  var i := 1;
  while cur <> nil do
  begin
    if (i mod 2 = 0) then
      list.Remove(cur);
    cur := cur.Next;
    i += 1;
  end;
end;

begin
  var l := CreateRandomLinkedList(15);
  l.Println;
  
  RemoveEvenNumbers(l);
  writeln('Список после удаления элементов с четными номерами:');
  l.Println;
end.

Стандартные контейнерные классы библиотеки .NET и пространство имен System.Collections.Generic

В пространстве имен System.Collections.Generic находятся все основные стандартные контейнерные классы библиотеки .NET:

  • Stack<T>
  • Queue<T>
  • List<T> — динамический массив
  • LinkedList<T> — класс двусвязного линейного списка
  • LinkedListNode<T>
  • Dictionary<Key, Value> — ассоциативный массив на базе хэш-таблицы (самые быстрые поиск и добавление, ключи не сортированы, неэкономичный по памяти)
  • SortedDictionary<Key, Value> — ассоциативный массив на базе БДП
  • SortedList<Key, Value> — ассоциативный массив на базе динамического массива

<xh4> Интерфейсы стандартных контейнерных классов .NET </xh4> 

Stack<T>


Queue<T>


List<T>


LinkedList<T>


LinkedListNode<T>


Dictionary<Key, Value>, SortedDictionary<Key, Value>, SortedList<Key, Value>

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

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

Источник — «http://it.mmcs.sfedu.ru/_wiki/index.php?title=Основы_программирования_—_второй_семестр_08-09;_Михалкович_С.С.;_V_часть&oldid=1927»