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

Материал из Вики ИТ мехмата ЮФУ
Версия от 13:17, 2 мая 2014; Admin (обсуждение | вклад) (Новая страница: «=== Класс Динамический массив === ''<u>Задача</u>.'' :* Реализовать АТД <tt>'''DynArray'''</tt>, который хра…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

Задача.

  • Реализовать АТД 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.

Класс Граф

(в скане лекций)

Стандартные контейнерные классы библиотеки .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> — ассоциативный массив на базе динамического массива

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

Stack<T> 

  Push(x: T);
  Pop: T;
  Peek: T;
  Clear;
  ToString: string;
  property Count: integer;

Queue<T> 

  Enqueue(x: T);
  Dequeue: T;
  Peek: T;
  Clear;
  ToString: string;
  property Count: integer;

List<T> 

  Add(x: T);
  Clear;
  Contains(x: T): boolean;
  IndexOf(x: T): integer;
  Insert(ind: integer; x: T);
  LastIndexOf(x: T): integer;
  Remove(x: T): boolean;
  RemoveAt(ind: integer);
  RemoveRange(ind,count: integer);
  Reverse();
  Reverse(from,count: integer);
  Sort();
  ToString: string;
  property Count: integer;
  property Capacity: integer;
  property Item[ind: integer]: T;
  Find(function(x: T): boolean): T;
  FindIndex(function(x: T): boolean): integer;
  FindAll(function(x: T): boolean): List<T>;
  ForEach(procedure (x: T));
  RemoveAll(function(x: T): boolean);
  TrueForAll(function(x: T): boolean): boolean;

LinkedListNode<T> 

  property Next: LinkedListNode<T> read
  property Prev: LinkedListNode<T> read
  property Value: T read write

LinkedList<T> 

  AddFirst(x: T);
  AddLast(x: T);
  AddAfter(n: LinkedListNode<T>; x: T);
  AddBefore(n: LinkedListNode<T>; x: T);
  Clear; 
  Contains(x: T): boolean;
  Find(x: T): LinkedListNode<T>;
  FindLast(x: T): LinkedListNode<T>;
  Remove(LinkedListNode<T>);
  RemoveFirst;
  RemoveLast;
  ToString: string;
  property Count: integer;
  property First: LinkedListNode<T>;
  property Last: LinkedListNode<T>;

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

  Add(k: Key; v: Value);
  Clear; 
  ContainsKey(k: Key): boolean;
  ContainsValue(v: Value): boolean;
  Remove(k: Key): boolean;
  TryGetValue(k: Key; var v: Value): boolean;
  ToString: string;
  property Count: integer;
  property Item[k: Key]: Value;

Примеры использования

Пример 1. Foreach по контейнерам 

uses System.Collections.Generic;

begin
  // Стек
  var s := new Stack<integer>;
  s.Push(1);
  s.Push(3);
  s.Push(5);
  
  foreach i: integer in s do
    write(i, ' ');
  writeln();
  
  // Очередь
  var q := new Queue<integer>;
  q.Enqueue(1);
  q.Enqueue(3);
  q.Enqueue(5);
  
  foreach i: integer in q do
    write(i, ' ');
  writeln();
  
  // Динамический массив
  var l := new List<integer>;
  l.Add(1);
  l.Add(3);
  l.Add(5);
  
  foreach i: integer in l do
    write(i, ' ');
  writeln();
  
  // Ассоциативный массив
  var m := new SortedDictionary<string, integer>;
  m['Крокодил'] := 3;
  m.Add('Бегемот', 2);
  
  {В отличие от «нашего» ассоциативного массива, в .NET:
      если ключа в ассоциативном массиве нет, то геттер
      для индексного свойства сгенерирует исключение,
      а  сеттер добавит соответствующую пару.
   Поэтому строка:
      m['Обезьяна'] := m['Кашалот'] + 1;
      вызовет исключение.
   Чтобы этого не случилось, выполним проверку:}
   
  if m.ContainsKey('Кашалот') then
    m['Обезьяна'] := m['Кашалот'] + 1;
    
  foreach k: KeyValuePair<string, integer> in m do
    writeln(k.Key, ' ', k.Value);
end.

Пример 2. Частотный словарь слов в файле. 

uses System.Collections.Generic, System;

var 
  // частотный словарь
  m := new SortedDictionary<string, integer>;
  f: TextFile;

begin
  Assign(f, 'a.txt');
  Reset(f);
  
  try
    while not Eof(f) do
    begin
      var s: string;
      readln(f, s);
      
      // разделители слов в тексте
      var delims: array of char := (' ', '.', ',', ':', ';', '!', '?', '-', '"', '(', ')');
      // слова строки s
      var words: array of string := s.Split(
        delims,
        // не включает в массив слов пустые
        StringSplitOptions.RemoveEmptyEntries);
        
      foreach w: string in words do
        if m.ContainsKey(w) then
          m[w] := m[w] + 1
        else
          m.Add(w, 1);
    end;
  finally
    Close(f);
  end;
  
  foreach k: KeyValuePair<string, integer> in m do
    writeln(k.Key, ' ', k.Value);
end.

Пример 3.
Дан массив чисел.
Вывести все четные в прямом порядке, а все нечетные в обратном. 

uses System.Collections.Generic;

function Even(x: integer): boolean;
begin
  result := (x mod 2 = 0);  
end;

begin
  var l := new List<integer>;
  l.Add(3);
  l.Add(4);
  l.Add(5);
  l.Add(6);
  
  var evenElems: List<integer> := l.FindAll(Even);
  
  l.RemoveAll(Even);
  l.Reverse;
  
  foreach i: integer in evenElems do
    write(i, ' ');
  writeln();
  foreach i: integer in l do
    write(i, ' ');
end.

Функция l.FindAll(predicate: function(x: T): boolean) возвращает список, состоящий из элементов списка l типа T, удовлетворяющих условию predicate.
Процедура l.RemoveAll(predicate: function(x: T): boolean) удаляет элементы списка l типа T, удовлетворяющие условию predicate.

Пример 4. Многоступенчатая фильтрация. 

function Less7(x: integer): boolean;
begin
  result := (x < 7);
end;

l := l.FindAll(Even).FindAll(Less7);

Пример 5. Использование процедурных переменных, хранящих ссылки на методы объектов класса.
Что делать, если, например, нужно фильтровать элементы по значению, которое определяется во время выполнения программы?

Использовать функцию 

function Less(x, maxValue: integer): boolean;

мы не можем, т.к. предикат функции FindAll должен быть типа 

type CompType = function(x: integer): boolean;

Может быть сделать глобальную(!) переменную, с которой и сравнивать x в функции Less, меняя её значение?
Нет, это очень плохое решение!

Есть другое решение.
Опишем класс, полем которого будет значение, с которым нужно сравнивать x, а методом — собственно функция сравнения: 

type
  Selector = class
    a: integer := 7;
    
    function Less(x: integer): boolean;
    begin
      result := (x < a);
    end;
  end;

  CompType = function(x: integer): boolean;

var
  c: CompType;

...

var s := new Selector;
c := s.Less;

writeln(c(5));

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

<имя объекта>.<имя метода>

При этом, в процедурной переменной c по существу запоминаются два значения: объект, вызывающий метод, и ссылка на метод, вызывающийся объектом.

Примечание. Код 

writeln(c(5));

компилятор заменит на 

writeln(s.Less(5));

Используем теперь эту возможность для фильтрации: 

var l := new List<integer>;
// наполнение l
s.a := 9;
var ll := l.FindAll(s.Less);

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

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

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