Collections — различия между версиями

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск
Строка 2: Строка 2:
 
== Вспомогательные модули ==
 
== Вспомогательные модули ==
 
=== Nodes ===
 
=== Nodes ===
<h4> I </h4>
 
 
<source lang="Delphi">
 
<source lang="Delphi">
 
/// Модуль содержит шаблоны классов
 
/// Модуль содержит шаблоны классов
Строка 13: Строка 12:
 
type
 
type
  
//-----------------------------------------------------SINGLE_NODE-----------------------------------------------------\\
+
//-------------------------------------------SINGLE_NODE-------------------------------------------
 
   /// Узел с одним полем связи
 
   /// Узел с одним полем связи
 
   SingleNode<DataType> = class
 
   SingleNode<DataType> = class
   
 
    /// Значение узла
 
    data: DataType;
 
    /// Ссылка на следующий элемент
 
    next: SingleNode<DataType>;
 
   
 
   
 
    /// <summary>
 
    /// Конструктор
 
    /// </summary>
 
    /// <param name="pData">Значение узла</param>
 
    /// <param name="pNext">Ссылка на следующий элемент</param>
 
    constructor Create(pData: DataType; pNext: SingleNode<DataType>);
 
 
  end;
 
//- - - - - - - - - - - - - - - - - - - - - - - - - END of SingleNode - - - - - - - - - - - - - - - - - - - - - - - - -\\
 
 
 
// -----------------------------------------------------DOUBLE_NODE----------------------------------------------------\\ 
 
  /// Узел с двумя полями связи
 
  DoubleNode<DataType> = class
 
   
 
    /// Значение узла
 
    data: DataType;
 
    /// Ссылка на следующий элемент
 
    next: DoubleNode<DataType>;
 
    /// Ссылка на предыдущий элемент
 
    prev: DoubleNode<DataType>;
 
   
 
   
 
    /// <summary>
 
    /// Конструктор
 
    /// </summary>
 
    /// <param name="pData">Значение узла</param>
 
    /// <param name="pNext">Ссылка на следующий элемент</param>
 
    /// <param name="pPrev">Ссылка на предыдущий элемент</param>
 
    constructor Create(pData: DataType; pPrev, pNext: DoubleNode<DataType>);
 
 
  end;
 
//- - - - - - - - - - - - - - - - - - - - - - - - - END of DoubleNode - - - - - - - - - - - - - - - - - - - - - - - - -\\
 
 
implementation
 
 
//-----------------------------------------------------SINGLE_NODE-----------------------------------------------------\\
 
{Конструктор
 
    pData — значение узла
 
    pNext — cсылка на следующий элемент}
 
constructor SingleNode<DataType>.Create(pData: DataType; pNext: SingleNode<DataType>);
 
begin
 
  data := pData;
 
  next := pNext;
 
end;
 
//- - - - - - - - - - - - - - - - - - - - - - - - - END of SingleNode - - - - - - - - - - - - - - - - - - - - - - - - -\\
 
 
 
// -----------------------------------------------------DOUBLE_NODE----------------------------------------------------\\
 
{Конструктор
 
    pData — значение узла
 
    pNext — cсылка на следующий элемент
 
    pPrev — ссылка на предыдущий элемент}
 
constructor DoubleNode<DataType>.Create(pData: DataType; pPrev, pNext: DoubleNode<DataType>);
 
begin
 
  data := pData;
 
  next := pNext;
 
  next := pNext;
 
end;
 
//- - - - - - - - - - - - - - - - - - - - - - - - - END of DoubleNode - - - - - - - - - - - - - - - - - - - - - - - - -\\
 
 
 
end.
 
</source>
 
 
<h4> II </h4>
 
<source lang="Delphi">
 
/// Модуль содержит шаблоны классов
 
///  SingleNode — узла с одним полем связи
 
///  DoubleNode — узла с двумя полями связи
 
unit Nodes;
 
 
 
// ========================================================================================= INTERFACE ========================================================================================= \\
 
interface
 
 
type
 
 
 
//-----------------------------------------------------SINGLE_NODE-----------------------------------------------------\\
 
  /// Узел с одним полем связи
 
  SingleNode<DataType> = class
 
   
 
    /// Значение узла
 
    data: DataType;
 
    /// Ссылка на следующий элемент
 
    next: SingleNode<DataType>;
 
   
 
   
 
    /// <summary>
 
    /// Конструктор
 
    /// </summary>
 
    /// <param name="pData">Значение узла</param>
 
    /// <param name="pNext">Ссылка на следующий элемент</param>
 
    constructor Create(pData: DataType; pNext: SingleNode<DataType>);
 
   
 
  end;
 
//- - - - - - - - - - - - - - - - - - - - - - - - - END of SingleNode - - - - - - - - - - - - - - - - - - - - - - - - -\\
 
 
/// Установка узла с одним полем связи sNode на следующий элемент
 
procedure SetNext<DataType>(var sNode: SingleNode<DataType>);
 
 
 
// -----------------------------------------------------DOUBLE_NODE----------------------------------------------------\\
 
type 
 
  /// Узел с двумя полями связи
 
  DoubleNode<DataType> = class
 
   
 
 
     /// Значение узла
 
     /// Значение узла
     data: DataType;
+
     data : DataType;
 
     /// Ссылка на следующий элемент
 
     /// Ссылка на следующий элемент
     next: DoubleNode<DataType>;
+
     next : SingleNode<DataType>;
    /// Ссылка на предыдущий элемент
 
    prev: DoubleNode<DataType>;
 
   
 
 
      
 
      
 
     /// <summary>
 
     /// <summary>
Строка 143: Строка 25:
 
     /// <param name="pData">Значение узла</param>
 
     /// <param name="pData">Значение узла</param>
 
     /// <param name="pNext">Ссылка на следующий элемент</param>
 
     /// <param name="pNext">Ссылка на следующий элемент</param>
    /// <param name="pPrev">Ссылка на предыдущий элемент</param>
+
     constructor Create(pData : DataType; pNext : SingleNode<DataType>);
     constructor Create(pData: DataType; pPrev, pNext: DoubleNode<DataType>);
 
   
 
 
   end;
 
   end;
//- - - - - - - - - - - - - - - - - - - - - - - - - END of DoubleNode - - - - - - - - - - - - - - - - - - - - - - - - -\\
 
 
/// Установка узла с двумя полями связи dNode на следующий элемент
 
procedure SetNext<DataType>(var dNode: DoubleNode<DataType>);
 
 
/// Установка узла с двумя полями связи dNode на предыдущий элемент
 
procedure SetPrev<DataType>(var dNode: DoubleNode<DataType>);
 
 
 
// ====================================================================================== IMPLEMENTATION ======================================================================================= \\
 
implementation
 
 
//-----------------------------------------------------SINGLE_NODE-----------------------------------------------------\\
 
{Конструктор
 
    pData — значение узла
 
    pNext — cсылка на следующий элемент}
 
constructor SingleNode<DataType>.Create(pData: DataType; pNext: SingleNode<DataType>);
 
begin
 
  data := pData;
 
  next := pNext;
 
end;
 
//- - - - - - - - - - - - - - - - - - - - - - - - - END of SingleNode - - - - - - - - - - - - - - - - - - - - - - - - -\\
 
 
{Установка узла с одним полем связи sNode на следующий элемент}
 
procedure SetNext<DataType>(var sNode: SingleNode<DataType>);
 
begin
 
  Assert(sNode <> nil);
 
  sNode := sNode.next
 
end;
 
 
 
// -----------------------------------------------------DOUBLE_NODE----------------------------------------------------\\
 
{Конструктор
 
    pData — значение узла
 
    pNext — cсылка на следующий элемент
 
    pPrev — ссылка на предыдущий элемент}
 
constructor DoubleNode<DataType>.Create(pData: DataType; pPrev, pNext: DoubleNode<DataType>);
 
begin
 
  data := pData;
 
  next := pNext;
 
  next := pNext;
 
end;
 
//- - - - - - - - - - - - - - - - - - - - - - - - - END of DoubleNode - - - - - - - - - - - - - - - - - - - - - - - - -\\
 
 
{Установка узла с двумя полями связи dNode на следующий элемент}
 
procedure SetNext<DataType>(var dNode: DoubleNode<DataType>);
 
begin
 
  Assert(dNode <> nil);
 
  dNode := dNode.next;
 
end;
 
 
{Установка узла с двумя полями связи dNode на предыдущий элемент}
 
procedure SetPrev<DataType>(var dNode: DoubleNode<DataType>);
 
begin
 
  Assert(dNode <> nil);
 
  dNode := dNode.prev;
 
end;
 
  
 
+
// -------------------------------------------DOUBLE_NODE------------------------------------------   
end.
 
</source>
 
 
 
<h4> III </h4>
 
<source lang="Delphi">
 
/// Модуль содержит шаблоны классов
 
///  SingleNode — узла с одним полем связи
 
///  DoubleNode — узла с двумя полями связи
 
unit Nodes;
 
 
 
 
 
// ========================================================================================= INTERFACE ========================================================================================= \\
 
interface
 
 
 
type
 
 
 
//-----------------------------------------------------SINGLE_NODE-----------------------------------------------------\\
 
  /// Узел с одним полем связи
 
  SingleNode<DataType> = class
 
   
 
    /// Значение узла
 
    data: DataType;
 
    /// Ссылка на следующий элемент
 
    next: SingleNode<DataType>;
 
   
 
   
 
    /// <summary>
 
    /// Конструктор
 
    /// </summary>
 
    /// <param name="pData">Значение узла</param>
 
    /// <param name="pNext">Ссылка на следующий элемент</param>
 
    constructor Create(pData: DataType; pNext: SingleNode<DataType>);
 
 
 
  end;
 
//- - - - - - - - - - - - - - - - - - - - - - - - - END of SingleNode - - - - - - - - - - - - - - - - - - - - - - - - -\\
 
 
 
/// Установка узла с одним полем связи sNode на следующий элемент.
 
/// Если не удалось, возвращает ложь.
 
function SetNext<DataType>(var sNode: SingleNode<DataType>): boolean;
 
 
 
// -----------------------------------------------------DOUBLE_NODE----------------------------------------------------\\
 
type  
 
 
   /// Узел с двумя полями связи
 
   /// Узел с двумя полями связи
 
   DoubleNode<DataType> = class
 
   DoubleNode<DataType> = class
   
 
 
     /// Значение узла
 
     /// Значение узла
     data: DataType;
+
     data : DataType;
 
     /// Ссылка на следующий элемент
 
     /// Ссылка на следующий элемент
     next: DoubleNode<DataType>;
+
     next : DoubleNode<DataType>;
 
     /// Ссылка на предыдущий элемент
 
     /// Ссылка на предыдущий элемент
     prev: DoubleNode<DataType>;
+
     prev : DoubleNode<DataType>;
   
 
 
      
 
      
 
     /// <summary>
 
     /// <summary>
Строка 265: Строка 44:
 
     /// <param name="pNext">Ссылка на следующий элемент</param>
 
     /// <param name="pNext">Ссылка на следующий элемент</param>
 
     /// <param name="pPrev">Ссылка на предыдущий элемент</param>
 
     /// <param name="pPrev">Ссылка на предыдущий элемент</param>
     constructor Create(pData: DataType; pPrev, pNext: DoubleNode<DataType>);
+
     constructor Create(pData : DataType; pPrev, pNext : DoubleNode<DataType>);
 
 
 
   end;
 
   end;
//- - - - - - - - - - - - - - - - - - - - - - - - - END of DoubleNode - - - - - - - - - - - - - - - - - - - - - - - - -\\
 
  
/// Установка узла с двумя полями связи dNode на следующий элемент.
 
/// Если не удалось, возвращает ложь.
 
function SetNext<DataType>(var dNode: DoubleNode<DataType>): boolean;
 
 
/// Установка узла с двумя полями связи dNode на предыдущий элемент.
 
/// Если не удалось, возвращает ложь.
 
function SetPrev<DataType>(var dNode: DoubleNode<DataType>): boolean;
 
 
 
// ====================================================================================== IMPLEMENTATION ======================================================================================= \\
 
 
implementation
 
implementation
  
//-----------------------------------------------------SINGLE_NODE-----------------------------------------------------\\
+
//-------------------------------------------SINGLE_NODE-------------------------------------------
 
{Конструктор
 
{Конструктор
 
     pData — значение узла
 
     pData — значение узла
 
     pNext — cсылка на следующий элемент}
 
     pNext — cсылка на следующий элемент}
constructor SingleNode<DataType>.Create(pData: DataType; pNext: SingleNode<DataType>);
+
constructor SingleNode<DataType>.Create(pData : DataType; pNext : SingleNode<DataType>);
 
begin
 
begin
 
   data := pData;
 
   data := pData;
 
   next := pNext;
 
   next := pNext;
 
end;
 
end;
//- - - - - - - - - - - - - - - - - - - - - - - - - END of SingleNode - - - - - - - - - - - - - - - - - - - - - - - - -\\
 
  
{Установка узла с одним полем связи sNode на следующий элемент.
+
// -------------------------------------------DOUBLE_NODE------------------------------------------
Если не удалось, возвращает ложь.}
 
function SetNext<DataType>(var sNode: SingleNode<DataType>): boolean;
 
begin
 
  if sNode = nil then
 
    result := false
 
  else
 
  begin
 
    sNode := sNode.next;
 
    result := true;
 
  end;
 
end;
 
 
 
 
 
// -----------------------------------------------------DOUBLE_NODE----------------------------------------------------\\
 
 
{Конструктор
 
{Конструктор
 
     pData — значение узла
 
     pData — значение узла
 
     pNext — cсылка на следующий элемент
 
     pNext — cсылка на следующий элемент
 
     pPrev — ссылка на предыдущий элемент}
 
     pPrev — ссылка на предыдущий элемент}
constructor DoubleNode<DataType>.Create(pData: DataType; pPrev, pNext: DoubleNode<DataType>);
+
constructor DoubleNode<DataType>.Create(pData : DataType; pPrev, pNext : DoubleNode<DataType>);
 
begin
 
begin
 
   data := pData;
 
   data := pData;
 
   next := pNext;
 
   next := pNext;
 
   next := pNext;
 
   next := pNext;
end;
 
//- - - - - - - - - - - - - - - - - - - - - - - - - END of DoubleNode - - - - - - - - - - - - - - - - - - - - - - - - -\\
 
 
{Установка узла с двумя полями связи dNode на следующий элемент.
 
Если не удалось, возвращает ложь.}
 
function SetNext<DataType>(var dNode: DoubleNode<DataType>): boolean;
 
begin
 
  if dNode = nil then
 
    result := false
 
  else
 
  begin
 
    dNode := dNode.next;
 
    result := true;
 
  end;
 
 
end;
 
end;
 
{Установка узла с двумя полями связи dNode на предыдущий элемент.
 
Если не удалось, возвращает ложь.}
 
function SetPrev<DataType>(var dNode: DoubleNode<DataType>): boolean;
 
begin
 
  if dNode = nil then
 
    result := false
 
  else
 
  begin
 
    dNode := dNode.prev;
 
    result := true;
 
  end;
 
end;
 
 
  
 
end.
 
end.
Строка 351: Строка 75:
  
 
== Collections ==
 
== Collections ==
=== I ===
 
 
<source lang="Delphi">
 
<source lang="Delphi">
 
/// Модуль содержит шаблоны классов
 
/// Модуль содержит шаблоны классов
Строка 359: Строка 82:
  
  
// ========================================================================================= INTERFACE ========================================================================================= \\
+
// ===================================================================== INTERFACE =====================================================================
 
interface
 
interface
  
 
uses Nodes;  // для использования типа SingleNode<DataType> —  
 
uses Nodes;  // для использования типа SingleNode<DataType> —  
 
               // узла с одним полем связи
 
               // узла с одним полем связи
 +
 +
const
 +
  /// Ширина поля вывода
 +
  PRINT_FIELD_WIDTH = 5;
 +
  /// Разделитель при выводе элементов
 +
  DELIMETR = '  ';
 +
  /// Количество элементов, выводимых в одной строке при выводе
 +
  ELEMS_IN_LINE = 5;
 +
 +
// ----------------------------------------------STACK---------------------------------------------
 +
const
 +
  /// Сообщение о пустоте стека
 +
  EMPTY_STACK = 'Стек пуст';
  
 
type
 
type
 
// --------------------------------------------------------STACK-------------------------------------------------------\\
 
 
   /// Шаблон класса Stack [Стек]
 
   /// Шаблон класса Stack [Стек]
 
   Stack<DataType> = class
 
   Stack<DataType> = class
 
 
 
   private  
 
   private  
 
     /// Вершина стека
 
     /// Вершина стека
     fTop: SingleNode<DataType> := nil;  // field Top
+
     fTop : SingleNode<DataType> := nil;  // field Top
   
 
 
   public  
 
   public  
    /// Конструктор
+
// ---------------------------- Стандартные методы ---------------------------
 +
  /// Стандартный конструктор
 
     constructor Create;
 
     constructor Create;
 +
    /// Конструктор.
 +
    /// Создает стек, заполненный элементами, переданными в качестве параметров
 +
    constructor Create(params datas : array of DataType);
 +
    {/// <summary>
 +
    /// Конструктор.
 +
    /// Создает стек, заполненный случайными данными
 +
    /// </summary>
 +
    /// <param name="count">Количество элементов</param>
 +
    /// <param name="GenerateRandom">Функция, генерирующая случайный объект</param>
 +
    constructor Create(count : integer; GenerateRandom : function : DataType);}
 
      
 
      
 
     /// Кладет элемент x на вершину стека
 
     /// Кладет элемент x на вершину стека
     procedure Push(x: DataType);
+
     procedure Push(x : DataType);
 
 
 
     /// Возвращает элемент типа DataType, снимая его с вершины стека
 
     /// Возвращает элемент типа DataType, снимая его с вершины стека
     function Pop: DataType;
+
     function Pop : DataType;
 
     /// Возвращает значение элемента на вершине стека
 
     /// Возвращает значение элемента на вершине стека
     function Top: DataType;
+
     function Top : DataType;
   
 
 
     /// Возвращает истину, если стек пуст
 
     /// Возвращает истину, если стек пуст
     function IsEmpty: boolean;
+
     function IsEmpty : boolean;
      
+
// ----------------------------- Вывод содержимого ---------------------------
 +
     /// <summary>
 +
    /// Выводит подряд содержимое стека
 +
    /// </summary>
 +
    /// <param name="delim">Разделитель между элементами в строке</param>
 +
    /// <param name="elemsInLine">Количество элементов, выводимых в одной строке</param>
 +
    procedure Print(delim : string := DELIMETR; elemsInLine : integer := ELEMS_IN_LINE);
 +
    /// Выводит содержимое стека в каждой строке
 +
    procedure Println;
 
   end;
 
   end;
//- - - - - - - - - - - - - - - - - - - - - - - - - - END of Stack- - - - - - - - - - - - - - - - - - - - - - - - - - -\\
 
  
 
+
// ----------------------------------------------QUEUE---------------------------------------------
// --------------------------------------------------------QUEUE-------------------------------------------------------\\
+
type 
 
   /// Шаблон класса Queue [Очередь]
 
   /// Шаблон класса Queue [Очередь]
 
   Queue<DataType> = class
 
   Queue<DataType> = class
 
 
 
   private
 
   private
 
     /// Голова очереди
 
     /// Голова очереди
     head: SingleNode<DataType>;
+
     head : SingleNode<DataType>;
 
     /// Хвост очереди
 
     /// Хвост очереди
     tail: SingleNode<DataType>;
+
     tail : SingleNode<DataType>;
   
 
 
   public
 
   public
     /// Конструктор
+
// ---------------------------- Стандартные методы ---------------------------
 +
     /// Стандартный конструктор
 
     constructor Create;
 
     constructor Create;
   
 
 
     /// Добавляет элемент x в хвост очереди
 
     /// Добавляет элемент x в хвост очереди
     procedure Enqueue(x: DataType);
+
     procedure Enqueue(x : DataType);
   
 
 
     /// Возвращает элемент типа DataType, убирая его из головы очереди
 
     /// Возвращает элемент типа DataType, убирая его из головы очереди
     function Dequeue: DataType;
+
     function Dequeue : DataType;
   
 
 
     /// Возвращает истину, если очередь пуста
 
     /// Возвращает истину, если очередь пуста
     function IsEmpty: boolean;
+
     function IsEmpty : boolean;
 
 
 
   end;
 
   end;
//- - - - - - - - - - - - - - - - - - - - - - - - - - END of Queue- - - - - - - - - - - - - - - - - - - - - - - - - - -\\
 
  
  
// ====================================================================================== IMPLEMENTATION ======================================================================================= \\
+
// ================================================================= IMPLEMENTATION ===================================================================
 
implementation
 
implementation
  
// --------------------------------------------------------STACK-------------------------------------------------------\\
+
// ----------------------------------------------STACK---------------------------------------------
{Конструктор}
+
 
 +
// ---------------------------- Стандартные методы ---------------------------
 +
{Стандартный конструктор}
 
constructor Stack<DataType>.Create;
 
constructor Stack<DataType>.Create;
 
begin
 
begin
 
   fTop := nil;
 
   fTop := nil;
 
end;
 
end;
 +
{Конструктор.
 +
Создает стек, заполненный элементами, переданными в качестве параметров}
 +
constructor Stack<DataType>.Create(params datas : array of DataType);
 +
begin
 +
  fTop := nil;
 +
  for var i := 0 to datas.Length - 1 do
 +
    Push(datas[i]);
 +
end;
 +
{Конструктор.
 +
Создает стек, заполненный случайными данными
 +
    count — количество элементов
 +
    GenerateRandom — функция, генерирующая случайный объект}
 +
{constructor Stack<DataType>.Create(count : integer; GenerateRandom : function : DataType);
 +
begin
 +
  fTop := nil;
 +
  for var i := 1 to count do
 +
    Push(GenerateRandom);
 +
end;}
  
 
{Кладет элемент x на вершину стека}  
 
{Кладет элемент x на вершину стека}  
procedure Stack<DataType>.Push(x: DataType);
+
procedure Stack<DataType>.Push(x : DataType);
 
begin
 
begin
 
   fTop := new SingleNode<DataType>(x, fTop);
 
   fTop := new SingleNode<DataType>(x, fTop);
 
end;
 
end;
 
  
 
{Возвращает элемент типа DataType, снимая его с вершины стека}
 
{Возвращает элемент типа DataType, снимая его с вершины стека}
function Stack<DataType>.Pop: DataType;
+
function Stack<DataType>.Pop : DataType;
 
begin
 
begin
 
   Assert(not IsEmpty);
 
   Assert(not IsEmpty);
 
 
 
   result := fTop.data;
 
   result := fTop.data;
 
   fTop := fTop.next;  // элемент снимается с вершины стека
 
   fTop := fTop.next;  // элемент снимается с вершины стека
Строка 449: Строка 209:
  
 
{Возвращает значение элемента на вершине стека}
 
{Возвращает значение элемента на вершине стека}
function Stack<DataType>.Top: DataType;
+
function Stack<DataType>.Top : DataType;
 
begin
 
begin
 
   Assert(not IsEmpty);
 
   Assert(not IsEmpty);
 
 
 
   result := fTop.data;
 
   result := fTop.data;
 
end;
 
end;
 
  
 
{Возвращает истину, если стек пуст}
 
{Возвращает истину, если стек пуст}
function Stack<DataType>.IsEmpty: boolean;
+
function Stack<DataType>.IsEmpty : boolean;
 
begin
 
begin
 
   result := (fTop = nil);
 
   result := (fTop = nil);
 
end;
 
end;
//- - - - - - - - - - - - - - - - - - - - - - - - - - END of Stack- - - - - - - - - - - - - - - - - - - - - - - - - - -\\
 
  
 
+
// ----------------------------- Вывод содержимого ---------------------------
// --------------------------------------------------------QUEUE-------------------------------------------------------\\
+
{Выводит подряд содержимое стека
constructor Queue<DataType>.Create;
+
    delim — разделитель между элементами в строке
 +
    elemsInLine — количество элементов, выводимых в одной строке}
 +
procedure Stack<DataType>.Print(delim : string; elemsInLine : integer);
 
begin
 
begin
   head := nil;
+
   if IsEmpty then
  tail := nil;
+
    writeln(EMPTY_STACK)
 +
  else
 +
  begin
 +
    var elemsInd := 1;  // индекс элемента стека
 +
                        // нужен для вывода по строкам
 +
    var curElem := fTop;
 +
    while curElem <> nil do
 +
    begin
 +
      if (elemsInd mod elemsInLine) <> 0 then
 +
        write(curElem.data:PRINT_FIELD_WIDTH, delim)
 +
      else              // вывели требуемое количество элементов в строке
 +
        writeln(curElem.data:PRINT_FIELD_WIDTH, delim);
 +
       
 +
      curElem := curElem.next;
 +
      elemsInd += 1;
 +
    end;
 +
  end;
 
end;
 
end;
  
{Добавляет элемент x в хвост очереди}  
+
{Выводит содержимое стека в каждой строке}
procedure Queue<DataType>.Enqueue(x: DataType);
+
procedure Stack<DataType>.Println;
 
begin
 
begin
 
   if IsEmpty then
 
   if IsEmpty then
 +
    writeln(EMPTY_STACK)
 +
  else
 
   begin
 
   begin
     head := new SingleNode<DataType>(x, nil);
+
     var curElem := fTop;
     tail := head;
+
    while curElem <> nil do
  end
+
     begin
  else  // if not IsEmpty
+
      writeln(curElem.data:PRINT_FIELD_WIDTH);
  begin
+
      curElem := curElem.next;;
    tail.next := new SingleNode<DataType>(x, nil);
+
    end;
    tail := tail.next; // элемент убирается из хвоста очереди
 
                        // (т.е. хвостом становится следующий элемент)
 
 
   end;
 
   end;
 
end;
 
end;
  
 +
// ----------------------------------------------QUEUE---------------------------------------------
  
{Возвращает элемент типа DataType, убирая его из головы очереди}
+
// ---------------------------- Стандартные методы ---------------------------
function Queue<DataType>.Dequeue: DataType;
 
begin
 
  Assert(not IsEmpty);
 
  result := head.data;
 
 
 
  head := head.next;  // элемент убирается из головы очереди
 
                      // (т.е. головой становится следующий элемент)
 
  if head = nil then
 
    tail := nil;
 
end;
 
 
 
 
 
{Возвращает истину, если очередь пуста}
 
function Queue<DataType>.IsEmpty: boolean;
 
begin
 
  result := (head = nil);
 
  Assert(tail = nil);
 
end;
 
//- - - - - - - - - - - - - - - - - - - - - - - - - - END of Queue- - - - - - - - - - - - - - - - - - - - - - - - - - -\\
 
 
 
end.
 
</source>
 
 
 
=== II ===
 
<source lang="Delphi">
 
/// Модуль содержит шаблоны классов
 
///  Stack — стек
 
///  Queue — очередь
 
unit Collections;
 
 
 
 
 
// ========================================================================================= INTERFACE ========================================================================================= \\
 
interface
 
 
 
uses Nodes;  // для использования типа SingleNode<DataType> —
 
              // узла с одним полем связи
 
 
 
type
 
 
 
// --------------------------------------------------------STACK-------------------------------------------------------\\
 
  /// Шаблон класса Stack [Стек]
 
  Stack<DataType> = class
 
 
 
  private
 
    /// Вершина стека
 
    fTop: SingleNode<DataType> := nil;  // field Top
 
   
 
  public
 
    /// Конструктор
 
    constructor Create;
 
   
 
    /// Кладет элемент x на вершину стека
 
    procedure Push(x: DataType);
 
 
 
    /// Возвращает элемент типа DataType, снимая его с вершины стека
 
    function Pop: DataType;
 
    /// Возвращает значение элемента на вершине стека
 
    function Top: DataType;
 
   
 
    /// Возвращает истину, если стек пуст
 
    function IsEmpty: boolean;
 
   
 
  end;
 
//- - - - - - - - - - - - - - - - - - - - - - - - - - END of Stack- - - - - - - - - - - - - - - - - - - - - - - - - - -\\
 
 
 
 
 
// --------------------------------------------------------QUEUE-------------------------------------------------------\\
 
  /// Шаблон класса Queue [Очередь]
 
  Queue<DataType> = class
 
 
 
  private
 
    /// Голова очереди
 
    head: SingleNode<DataType>;
 
    /// Хвост очереди
 
    tail: SingleNode<DataType>;
 
   
 
  public
 
    /// Конструктор
 
    constructor Create;
 
   
 
    /// Добавляет элемент x в хвост очереди
 
    procedure Enqueue(x: DataType);
 
   
 
    /// Возвращает элемент типа DataType, убирая его из головы очереди
 
    function Dequeue: DataType;
 
   
 
    /// Возвращает истину, если очередь пуста
 
    function IsEmpty: boolean;
 
 
 
  end;
 
//- - - - - - - - - - - - - - - - - - - - - - - - - - END of Queue- - - - - - - - - - - - - - - - - - - - - - - - - - -\\
 
 
 
 
 
// ====================================================================================== IMPLEMENTATION ======================================================================================= \\
 
implementation
 
 
 
// --------------------------------------------------------STACK-------------------------------------------------------\\
 
 
{Конструктор}
 
{Конструктор}
constructor Stack<DataType>.Create;
 
begin
 
  fTop := nil;
 
end;
 
 
{Кладет элемент x на вершину стека}
 
procedure Stack<DataType>.Push(x: DataType);
 
begin
 
  fTop := new SingleNode<DataType>(x, fTop);
 
end;
 
 
 
{Возвращает элемент типа DataType, снимая его с вершины стека}
 
function Stack<DataType>.Pop: DataType;
 
begin
 
  Assert(not IsEmpty);
 
 
 
  result := fTop.data;
 
  SetNext(fTop);  // элемент снимается с вершины стека
 
                  // (т.е. вершиной становится следующий элемент)
 
end;
 
 
{Возвращает значение элемента на вершине стека}
 
function Stack<DataType>.Top: DataType;
 
begin
 
  Assert(not IsEmpty);
 
 
 
  result := fTop.data;
 
end;
 
 
 
{Возвращает истину, если стек пуст}
 
function Stack<DataType>.IsEmpty: boolean;
 
begin
 
  result := (fTop = nil);
 
end;
 
//- - - - - - - - - - - - - - - - - - - - - - - - - - END of Stack- - - - - - - - - - - - - - - - - - - - - - - - - - -\\
 
 
 
// --------------------------------------------------------QUEUE-------------------------------------------------------\\
 
 
constructor Queue<DataType>.Create;
 
constructor Queue<DataType>.Create;
 
begin
 
begin
Строка 635: Строка 274:
  
 
{Добавляет элемент x в хвост очереди}  
 
{Добавляет элемент x в хвост очереди}  
procedure Queue<DataType>.Enqueue(x: DataType);
+
procedure Queue<DataType>.Enqueue(x : DataType);
 
begin
 
begin
 
   if IsEmpty then
 
   if IsEmpty then
Строка 645: Строка 284:
 
   begin
 
   begin
 
     tail.next := new SingleNode<DataType>(x, nil);
 
     tail.next := new SingleNode<DataType>(x, nil);
     SetNext(tail);  // элемент убирается из хвоста очереди
+
     tail := tail.next;  // элемент убирается из хвоста очереди
                    // (т.е. хвостом становится следующий элемент)
+
                        // (т.е. хвостом становится следующий элемент)
 
   end;
 
   end;
 
end;
 
end;
 
  
 
{Возвращает элемент типа DataType, убирая его из головы очереди}
 
{Возвращает элемент типа DataType, убирая его из головы очереди}
function Queue<DataType>.Dequeue: DataType;
+
function Queue<DataType>.Dequeue : DataType;
 
begin
 
begin
 
   Assert(not IsEmpty);
 
   Assert(not IsEmpty);
 
   result := head.data;
 
   result := head.data;
 
    
 
    
   SetNext(head);  // элемент убирается из головы очереди
+
   head := head.next;  // элемент убирается из головы очереди
                  // (т.е. головой становится следующий элемент)
+
                      // (т.е. головой становится следующий элемент)
 
   if head = nil then
 
   if head = nil then
 
     tail := nil;
 
     tail := nil;
 
end;
 
end;
 
  
 
{Возвращает истину, если очередь пуста}
 
{Возвращает истину, если очередь пуста}
function Queue<DataType>.IsEmpty: boolean;
+
function Queue<DataType>.IsEmpty : boolean;
 
begin
 
begin
 
   result := (head = nil);
 
   result := (head = nil);
 
   Assert(tail = nil);
 
   Assert(tail = nil);
 
end;
 
end;
//- - - - - - - - - - - - - - - - - - - - - - - - - - END of Queue- - - - - - - - - - - - - - - - - - - - - - - - - - -\\
 
 
    
 
    
 
end.
 
end.
 
</source>
 
</source>

Версия 19:56, 16 апреля 2009

Вспомогательные модули

Nodes

/// Модуль содержит шаблоны классов
///   SingleNode — узла с одним полем связи
///   DoubleNode — узла с двумя полями связи
unit Nodes;

interface

type

//-------------------------------------------SINGLE_NODE-------------------------------------------
  /// Узел с одним полем связи
  SingleNode<DataType> = class
    /// Значение узла
    data : DataType;
    /// Ссылка на следующий элемент
    next : SingleNode<DataType>;
    
    /// <summary>
    /// Конструктор
    /// </summary>
    /// <param name="pData">Значение узла</param>
    /// <param name="pNext">Ссылка на следующий элемент</param>
    constructor Create(pData : DataType; pNext : SingleNode<DataType>);
  end;

// -------------------------------------------DOUBLE_NODE------------------------------------------  
  /// Узел с двумя полями связи
  DoubleNode<DataType> = class
    /// Значение узла
    data : DataType;
    /// Ссылка на следующий элемент
    next : DoubleNode<DataType>;
    /// Ссылка на предыдущий элемент
    prev : DoubleNode<DataType>;
    
    /// <summary>
    /// Конструктор
    /// </summary>
    /// <param name="pData">Значение узла</param>
    /// <param name="pNext">Ссылка на следующий элемент</param>
    /// <param name="pPrev">Ссылка на предыдущий элемент</param>
    constructor Create(pData : DataType; pPrev, pNext : DoubleNode<DataType>);
  end;

implementation

//-------------------------------------------SINGLE_NODE-------------------------------------------
{Конструктор
    pData — значение узла
    pNext — cсылка на следующий элемент}
constructor SingleNode<DataType>.Create(pData : DataType; pNext : SingleNode<DataType>);
begin
  data := pData;
  next := pNext;
end;

// -------------------------------------------DOUBLE_NODE------------------------------------------  
{Конструктор
    pData — значение узла
    pNext — cсылка на следующий элемент
    pPrev — ссылка на предыдущий элемент}
constructor DoubleNode<DataType>.Create(pData : DataType; pPrev, pNext : DoubleNode<DataType>);
begin
  data := pData;
  next := pNext;
  next := pNext;
end;

end.

Collections

/// Модуль содержит шаблоны классов
///   Stack — стек
///   Queue — очередь
unit Collections;


// ===================================================================== INTERFACE =====================================================================
interface

uses Nodes;   // для использования типа SingleNode<DataType> — 
              // узла с одним полем связи

const
  /// Ширина поля вывода
  PRINT_FIELD_WIDTH = 5;
  /// Разделитель при выводе элементов
  DELIMETR = '   ';
  /// Количество элементов, выводимых в одной строке при выводе
  ELEMS_IN_LINE = 5;

// ----------------------------------------------STACK---------------------------------------------
const
  /// Сообщение о пустоте стека
  EMPTY_STACK = 'Стек пуст';

type
  /// Шаблон класса Stack [Стек]
  Stack<DataType> = class
  private 
    /// Вершина стека
    fTop : SingleNode<DataType> := nil;   // field Top
  public 
// ---------------------------- Стандартные методы --------------------------- 
   /// Стандартный конструктор
    constructor Create;
    /// Конструктор.
    /// Создает стек, заполненный элементами, переданными в качестве параметров
    constructor Create(params datas : array of DataType); 
    {/// <summary>
    /// Конструктор.
    /// Создает стек, заполненный случайными данными
    /// </summary>
    /// <param name="count">Количество элементов</param>
    /// <param name="GenerateRandom">Функция, генерирующая случайный объект</param>
    constructor Create(count : integer; GenerateRandom : function : DataType);}
    
    /// Кладет элемент x на вершину стека
    procedure Push(x : DataType);
    /// Возвращает элемент типа DataType, снимая его с вершины стека
    function Pop : DataType;
    /// Возвращает значение элемента на вершине стека
    function Top : DataType;
    /// Возвращает истину, если стек пуст
    function IsEmpty : boolean;
// ----------------------------- Вывод содержимого ---------------------------
    /// <summary>
    /// Выводит подряд содержимое стека
    /// </summary>
    /// <param name="delim">Разделитель между элементами в строке</param>
    /// <param name="elemsInLine">Количество элементов, выводимых в одной строке</param>
    procedure Print(delim : string := DELIMETR; elemsInLine : integer := ELEMS_IN_LINE);
    /// Выводит содержимое стека в каждой строке
    procedure Println;
  end;

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


// ================================================================= IMPLEMENTATION ===================================================================
implementation

// ----------------------------------------------STACK---------------------------------------------

// ---------------------------- Стандартные методы ---------------------------
{Стандартный конструктор}
constructor Stack<DataType>.Create;
begin
  fTop := nil;
end;
{Конструктор.
 Создает стек, заполненный элементами, переданными в качестве параметров}
constructor Stack<DataType>.Create(params datas : array of DataType); 
begin
  fTop := nil;
  for var i := 0 to datas.Length - 1 do
    Push(datas[i]);
end;
{Конструктор.
 Создает стек, заполненный случайными данными
    count — количество элементов
    GenerateRandom — функция, генерирующая случайный объект}
{constructor Stack<DataType>.Create(count : integer; GenerateRandom : function : DataType);
begin
  fTop := nil;
  for var i := 1 to count do
    Push(GenerateRandom);
end;}

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

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

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

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

// ----------------------------- Вывод содержимого ---------------------------
{Выводит подряд содержимое стека
    delim — разделитель между элементами в строке
    elemsInLine — количество элементов, выводимых в одной строке}
procedure Stack<DataType>.Print(delim : string; elemsInLine : integer);
begin
  if IsEmpty then
    writeln(EMPTY_STACK)
  else
  begin
    var elemsInd := 1;  // индекс элемента стека
                        // нужен для вывода по строкам
    var curElem := fTop;
    while curElem <> nil do
    begin
      if (elemsInd mod elemsInLine) <> 0 then
        write(curElem.data:PRINT_FIELD_WIDTH, delim) 
      else              // вывели требуемое количество элементов в строке
        writeln(curElem.data:PRINT_FIELD_WIDTH, delim);
        
      curElem := curElem.next;
      elemsInd += 1;
    end;
  end;
end;

{Выводит содержимое стека в каждой строке}
procedure Stack<DataType>.Println;
begin
  if IsEmpty then
    writeln(EMPTY_STACK)
  else
  begin
    var curElem := fTop;
    while curElem <> nil do
    begin
      writeln(curElem.data:PRINT_FIELD_WIDTH);
      curElem := curElem.next;;
    end;
  end;
end;

// ----------------------------------------------QUEUE---------------------------------------------

// ---------------------------- Стандартные методы ---------------------------
{Конструктор}
constructor Queue<DataType>.Create;
begin
  head := nil;
  tail := nil;
end;

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

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

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