Collections — различия между версиями
Материал из Вики ИТ мехмата ЮФУ
(→Collections) |
Juliet (обсуждение | вклад) м (Правки 87.117.60.143 (обсуждение) откачены к версии 195.208.237.241) |
||
Строка 79: | Строка 79: | ||
/// Stack — стек | /// Stack — стек | ||
/// Queue — очередь | /// Queue — очередь | ||
− | |||
unit Collections; | unit Collections; | ||
+ | // ===================================================================== INTERFACE ===================================================================== | ||
interface | interface | ||
Строка 107: | Строка 107: | ||
/// Вершина стека | /// Вершина стека | ||
fTop: SingleNode<DataType> := nil; // field Top | fTop: SingleNode<DataType> := nil; // field Top | ||
− | |||
public | public | ||
// ---------------------------- Стандартные методы --------------------------- | // ---------------------------- Стандартные методы --------------------------- | ||
− | + | /// Стандартный конструктор | |
constructor Create; | constructor Create; | ||
+ | /// Конструктор. | ||
/// Создает стек, заполненный элементами, переданными в качестве параметров | /// Создает стек, заполненный элементами, переданными в качестве параметров | ||
− | constructor Create(params | + | constructor Create(params datas: array of DataType); |
/// Кладет элемент x на вершину стека | /// Кладет элемент x на вершину стека | ||
Строка 121: | Строка 121: | ||
/// Возвращает значение элемента на вершине стека | /// Возвращает значение элемента на вершине стека | ||
function Top: DataType; | function Top: DataType; | ||
− | |||
/// Возвращает истину, если стек пуст | /// Возвращает истину, если стек пуст | ||
− | function IsEmpty: boolean; | + | function IsEmpty: boolean; |
// ----------------------------- Вывод содержимого --------------------------- | // ----------------------------- Вывод содержимого --------------------------- | ||
/// <summary> | /// <summary> | ||
Строка 148: | Строка 147: | ||
/// Хвост очереди | /// Хвост очереди | ||
tail: SingleNode<DataType>; | tail: SingleNode<DataType>; | ||
− | |||
public | public | ||
// ---------------------------- Стандартные методы --------------------------- | // ---------------------------- Стандартные методы --------------------------- | ||
− | /// | + | /// Стандартный конструктор |
constructor Create; | constructor Create; | ||
+ | /// Конструктор. | ||
/// Создает очередь, заполненную элементами, переданными в качестве параметров | /// Создает очередь, заполненную элементами, переданными в качестве параметров | ||
− | constructor Create(params | + | constructor Create(params datas: array of DataType); |
− | |||
/// Добавляет элемент x в хвост очереди | /// Добавляет элемент x в хвост очереди | ||
procedure Enqueue(x: DataType); | procedure Enqueue(x: DataType); | ||
Строка 161: | Строка 159: | ||
function Dequeue: DataType; | function Dequeue: DataType; | ||
/// Возвращает истину, если очередь пуста | /// Возвращает истину, если очередь пуста | ||
− | |||
function IsEmpty: boolean; | function IsEmpty: boolean; | ||
// ----------------------------- Вывод содержимого --------------------------- | // ----------------------------- Вывод содержимого --------------------------- | ||
Строка 174: | Строка 171: | ||
end; | end; | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
// ================================================================= IMPLEMENTATION =================================================================== | // ================================================================= IMPLEMENTATION =================================================================== | ||
Строка 263: | Строка 183: | ||
fTop := nil; | fTop := nil; | ||
end; | end; | ||
− | {Создает стек, заполненный элементами, переданными в качестве параметров} | + | {Конструктор. |
− | constructor Stack<DataType>.Create(params | + | Создает стек, заполненный элементами, переданными в качестве параметров} |
+ | constructor Stack<DataType>.Create(params datas: array of DataType); | ||
begin | begin | ||
fTop := nil; | fTop := nil; | ||
− | for var i := 0 to | + | for var i := 0 to datas.Length - 1 do |
− | Push( | + | Push(datas[i]); |
end; | end; | ||
Строка 344: | Строка 265: | ||
// ---------------------------- Стандартные методы --------------------------- | // ---------------------------- Стандартные методы --------------------------- | ||
− | { | + | {Конструктор} |
constructor Queue<DataType>.Create; | constructor Queue<DataType>.Create; | ||
begin | begin | ||
Строка 350: | Строка 271: | ||
tail := nil; | tail := nil; | ||
end; | end; | ||
− | {Создает очередь, заполненную элементами, переданными в качестве параметров} | + | {Конструктор. |
− | constructor Queue<DataType>.Create(params | + | Создает очередь, заполненную элементами, переданными в качестве параметров} |
+ | constructor Queue<DataType>.Create(params datas: array of DataType); | ||
begin | begin | ||
head := nil; | head := nil; | ||
tail := nil; | tail := nil; | ||
− | for var i := 0 to | + | for var i := 0 to datas.Length - 1 do |
− | Enqueue( | + | Enqueue(datas[i]); |
end; | end; | ||
Строка 435: | Строка 357: | ||
end; | end; | ||
end; | end; | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
end; | end; | ||
end. | end. | ||
</source> | </source> |
Версия 11:03, 19 апреля 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;
prev := pPrev;
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);
/// Кладет элемент 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---------------------------------------------
const
/// Сообщение о пустоте очереди
EMPTY_QUEUE = 'Очередь пуста';
type
/// Шаблон класса Queue [Очередь]
Queue<DataType> = class
private
/// Голова очереди
head: SingleNode<DataType>;
/// Хвост очереди
tail: SingleNode<DataType>;
public
// ---------------------------- Стандартные методы ---------------------------
/// Стандартный конструктор
constructor Create;
/// Конструктор.
/// Создает очередь, заполненную элементами, переданными в качестве параметров
constructor Create(params datas: array of DataType);
/// Добавляет элемент x в хвост очереди
procedure Enqueue(x: DataType);
/// Возвращает элемент типа DataType, убирая его из головы очереди
function Dequeue: 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;
// ================================================================= 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;
{Кладет элемент 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;
{Конструктор.
Создает очередь, заполненную элементами, переданными в качестве параметров}
constructor Queue<DataType>.Create(params datas: array of DataType);
begin
head := nil;
tail := nil;
for var i := 0 to datas.Length - 1 do
Enqueue(datas[i]);
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);
if result then
Assert(tail = nil);
end;
// ----------------------------- Вывод содержимого ---------------------------
{Выводит подряд содержимое очереди от головы к хвосту
delim — разделитель между элементами в строке
elemsInLine — количество элементов, выводимых в одной строке}
procedure Queue<DataType>.Print(delim: string; elemsInLine: integer);
begin
if IsEmpty then
writeln(EMPTY_QUEUE)
else
begin
var elemsInd := 1; // индекс элемента стека
// нужен для вывода по строкам
var curElem := head;
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 Queue<DataType>.Println;
begin
if IsEmpty then
writeln(EMPTY_QUEUE)
else
begin
var curElem := head;
while curElem <> nil do
begin
writeln(curElem.data:PRINT_FIELD_WIDTH);
curElem := curElem.next;;
end;
end;
end;
end.