Collections — различия между версиями
Материал из Вики ИТ мехмата ЮФУ
Juliet (обсуждение | вклад) |
(→Collections) |
||
Строка 362: | Строка 362: | ||
interface | interface | ||
− | uses Nodes; | + | uses Nodes; // для использования типа SingleNode<DataType> — |
+ | // узла с одним полем связи | ||
type | type | ||
Строка 523: | Строка 524: | ||
interface | interface | ||
− | uses Nodes; | + | uses Nodes; // для использования типа SingleNode<DataType> — |
+ | // узла с одним полем связи | ||
type | type |
Версия 15:57, 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; // для использования типа 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;
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; // для использования типа 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;
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.