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

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск
(→‎Collections)
Строка 1: Строка 1:
 +
__TOC__
 
== Вспомогательные модули ==
 
== Вспомогательные модули ==
 
=== Nodes ===
 
=== Nodes ===

Версия 14:22, 16 апреля 2009

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

Nodes

<xh4> I </xh4> 

/// Модуль содержит шаблоны классов
///   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;
//- - - - - - - - - - - - - - - - - - - - - - - - - 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.

<xh4> II </xh4> 

/// Модуль содержит шаблоны классов
///   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;
    /// Ссылка на следующий элемент
    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 - - - - - - - - - - - - - - - - - - - - - - - - -\\

/// Установка узла с двумя полями связи 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;


end.

<xh4> III </xh4> 

/// Модуль содержит шаблоны классов
///   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
    
    /// Значение узла
    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 - - - - - - - - - - - - - - - - - - - - - - - - -\\

/// Установка узла с двумя полями связи dNode на следующий элемент.
/// Если не удалось, возвращает ложь.
function SetNext<DataType>(var dNode: DoubleNode<DataType>): boolean;

/// Установка узла с двумя полями связи dNode на предыдущий элемент.
/// Если не удалось, возвращает ложь.
function SetPrev<DataType>(var dNode: DoubleNode<DataType>): boolean;


// ====================================================================================== 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 на следующий элемент.
 Если не удалось, возвращает ложь.}
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 — значение узла
    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 на следующий элемент.
 Если не удалось, возвращает ложь.}
function SetNext<DataType>(var dNode: DoubleNode<DataType>): boolean;
begin
  if dNode = nil then
    result := false
  else
  begin
    dNode := dNode.next;
    result := true;
  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.

Collections

<xh4> I </xh4> 

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


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

uses Nodes;

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;
  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;
//- - - - - - - - - - - - - - - - - - - - - - - - - - END of Stack- - - - - - - - - - - - - - - - - - - - - - - - - - -\\


// --------------------------------------------------------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 of Queue- - - - - - - - - - - - - - - - - - - - - - - - - - -\\
  
end.

<xh4> II </xh4> 

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


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

uses Nodes;

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;
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);
    SetNext(tail);  // элемент убирается из хвоста очереди
                    // (т.е. хвостом становится следующий элемент)
  end;
end;


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


{Возвращает истину, если очередь пуста}
function Queue<DataType>.IsEmpty: boolean;
begin
  result := (head = nil);
  Assert(tail = nil);
end;
//- - - - - - - - - - - - - - - - - - - - - - - - - - END of Queue- - - - - - - - - - - - - - - - - - - - - - - - - - -\\
  
end.
Источник — «http://it.mmcs.sfedu.ru/_wiki/index.php?title=Collections&oldid=1618»