Collections
Материал из Вики ИТ мехмата ЮФУ
Содержание
Вспомогательные модули
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.Составляющие классы
Stack
<xh4> Интерфейс </xh4>
Create
Создает пустой стек
Create(params xDatas: array of DataType)
Создает стек, заполненный элементами, переданными в качестве параметров
Push(x: DataType)
Кладет элемент x на вершину стека
Pop: DataType
Возвращает элемент типа DataType, снимая его с вершины стека
Top: DataType
Возвращает значение элемента на вершине стека
IsEmpty: boolean;
Возвращает истину, если стек пуст
Print(delim: string; elemsInLine: integer)
Выводит подряд содержимое стека
(delim — разделитель между элементами в строке,
elemsInLine — количество элементов, выводимых в одной строке)
Println
Выводит содержимое стека в каждой строке
<xh4> Реализация </xh4>
/// Модуль содержит шаблон класса
/// Stack — стек
unit StackUnit;
interface
uses Nodes; // для использования типа SingleNode<DataType> —
// узла с одним полем связи
const
/// Ширина поля вывода
PRINT_FIELD_WIDTH = 5;
/// Разделитель при выводе элементов
DELIMETR = ' ';
/// Количество элементов, выводимых в одной строке при выводе
ELEMS_IN_LINE = 5;
/// Сообщение о пустоте стека
EMPTY_STACK = 'Стек пуст';
type
/// Шаблон класса Stack [Стек]
Stack<DataType> = class
private
/// Вершина стека
fTop: SingleNode<DataType> := nil; // field Top
public
// ---------------------------- Стандартные методы ---------------------------
/// Создает пустой стек
constructor Create;
/// Создает стек, заполненный элементами, переданными в качестве параметров
constructor Create(params xDatas: 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;
// ================================================================= IMPLEMENTATION ===================================================================
implementation
// ---------------------------- Стандартные методы ---------------------------
{Стандартный конструктор}
constructor Stack<DataType>.Create;
begin
fTop := nil;
end;
{Создает стек, заполненный элементами, переданными в качестве параметров}
constructor Stack<DataType>.Create(params xDatas: array of DataType);
begin
fTop := nil;
for var i := 0 to xDatas.Length - 1 do
Push(xDatas[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;
end.Queue
<xh4> Интерфейс </xh4>
Create
Создает пустую очередь
Create(params xDatas: array of DataType)
Создает очередь, заполненную элементами, переданными в качестве параметров
Enqueue(x: DataType)
Добавляет элемент x в хвост очереди
Dequeue: DataType
Возвращает элемент типа DataType, убирая его из головы очереди
IsEmpty: boolean;
Возвращает истину, если очередь пуста
Print(delim: string; elemsInLine: integer)
Выводит подряд содержимое очереди от головы к хвосту
(delim — разделитель между элементами в строке,
elemsInLine — количество элементов, выводимых в одной строке)
Println
Выводит содержимое очереди от головы к хвосту в каждой строке
<xh4> Реализация </xh4>
/// Модуль содержит шаблон класса
/// Queue — очередь
unit QueueUnit;
interface
uses Nodes; // для использования типа SingleNode<DataType> —
// узла с одним полем связи
const
/// Ширина поля вывода
PRINT_FIELD_WIDTH = 5;
/// Разделитель при выводе элементов
DELIMETR = ' ';
/// Количество элементов, выводимых в одной строке при выводе
ELEMS_IN_LINE = 5;
/// Сообщение о пустоте очереди
EMPTY_QUEUE = 'Очередь пуста';
type
/// Шаблон класса Queue [Очередь]
Queue<DataType> = class
private
/// Голова очереди
head: SingleNode<DataType>;
/// Хвост очереди
tail: SingleNode<DataType>;
public
// ---------------------------- Стандартные методы ---------------------------
/// Создает пустую очередь
constructor Create;
/// Создает очередь, заполненную элементами, переданными в качестве параметров
constructor Create(params xDatas: 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
// ---------------------------- Стандартные методы ---------------------------
{Создает пустую очередь}
constructor Queue<DataType>.Create;
begin
head := nil;
tail := nil;
end;
{Создает очередь, заполненную элементами, переданными в качестве параметров}
constructor Queue<DataType>.Create(params xDatas: array of DataType);
begin
head := nil;
tail := nil;
for var i := 0 to xDatas.Length - 1 do
Enqueue(xDatas[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.DynArray
<xh4> Интерфейс </xh4>
Count Количество элементов (размер) массива Capacity Емкость массива (отведенная память) Create(pSize: integer) Создает массив размера pSize Create(params xDatas: array of DataType) Создает массив, заполненный элементами, переданными в качестве параметров Reserve(newCap: integer) Выделяет новую память. Емкость увеличивается до newCap (Если newCap меньше текущей емкости, ничего не происходит) Resize(newSize: integer) Устанавливает размер массива равным newSize Add(params xDatas: array of DataType) Добавляет элементы, переданные в качестве параметров, в конец массива Insert(pos: integer; params xDatas: array of DataType) Вставляет в массив элементы, переданные в качестве параметров, начиная с позиции pos Delete(pos: integer; count: integer) Удаляет count элементов массива, начиная с позиции pos. (По умолчанию удаляется один элемент) Find(x: DataType): integer Возвращает индекс первого элемента массива равного x или -1, если такого элемента нет Find(x: DataType; from: integer): integer Возвращает индекс элемента массива равного x, начиная с позиции from, или -1, если такого элемента нет Print(delim: string; elemsInLine: integer) Выводит содержимое массива в прямом порядке (delim — разделитель между элементами в строке elemsInLine — количество элементов, выводимых в одной строке) PrintReverse(delim: string; elemsInLine: integer) Выводит содержимое массива в обратном порядке delim — разделитель между элементами в строке elemsInLine — количество элементов, выводимых в одной строке) Println Выводит содержимое массива в прямом порядке в каждой строке PrintlnReverse Выводит содержимое массива в прямом порядке в каждой строке
<xh4> Реализация </xh4>
/// Модуль содержит шаблон класса
/// DynArray — динамический массив с автоконтролем памяти
unit DynArrayUnit;
interface
const
/// Ширина поля вывода
PRINT_FIELD_WIDTH = 5;
/// Разделитель при выводе элементов
DELIMETR = ' ';
/// Количество элементов, выводимых в одной строке при выводе
ELEMS_IN_LINE = 5;
/// Минимальная емкость, устанавливаемая при создании массива
MIN_CAP = 4;
/// Коэффициент увеличения емкости массива при её нехватке
INC_CAP_FACTOR = 2;
type
/// Шаблон класса DynArray [Динамический массив с автоконтролем памяти]
DynArray<DataType> = class
private
/// Встроенный динамический массив, содержащий данные
data: array of DataType;
/// Размер массива
size: integer;
/// Емкость массива
cap: integer;
/// Устанавливает элемент с индексом ind равным x
procedure SetElem(ind: integer; x: DataType);
/// Возвращает элемент массива с индексом ind
function GetElem(ind: integer): DataType;
public
// ---------------------------- Стандартные методы ---------------------------
/// Создает массив размера pSize
constructor Create(pSize: integer := 0);
/// Создает массив, заполненный элементами, переданными в качестве параметров
constructor Create(params xDatas: array of DataType);
/// Выделяет новую память. Емкость увеличивается до newCap
/// (Если newCap меньше текущей емкости, ничего не происходит)
procedure Reserve(newCap: integer);
/// Устанавливает размер массива равным newSize
procedure Resize(newSize: integer);
/// Добавляет элементы, переданные в качестве параметров, в конец массива
procedure Add(params xDatas: array of DataType);
/// Вставляет в массив элементы, переданные в качестве параметров,
/// начиная с позиции pos
procedure Insert(pos: integer; params xDatas: array of DataType);
/// Удаляет count элементов массива, начиная с позиции pos.
/// (По умолчанию удаляется один элемент)
procedure Delete(pos: integer; count: integer := 1);
/// Возвращает индекс первого элемента массива равного x
/// или -1, если такого элемента нет
function Find(x: DataType): integer;
/// Возвращает индекс элемента массива равного x, начиная с позиции from,
/// или -1, если такого элемента нет}
function Find(x: DataType; from: integer): integer;
// --------------------------------- Свойства --------------------------------
/// Количество элементов (размер) массива
property Count: integer read size write Resize;
/// Емкость массива (отведенная память)
property Capacity: integer read cap write Reserve;
/// Позволяет обращаться к элементам массива по индексу
/// (например, apples[5])
property Elem[index: integer]: DataType read GetElem write SetElem; default;
// ----------------------------- Вывод содержимого ---------------------------
/// <summary>
/// Выводит содержимое массива в прямом порядке
/// </summary>
/// <param name="delim">Разделитель между элементами в строке</param>
/// <param name="elemsInLine">Количество элементов, выводимых в одной строке</param>
procedure Print(delim: string := DELIMETR; elemsInLine: integer := ELEMS_IN_LINE);
/// <summary>
/// Выводит содержимое массива в обратном порядке
/// </summary>
/// <param name="delim">Разделитель между элементами в строке</param>
/// <param name="elemsInLine">Количество элементов, выводимых в одной строке</param>
procedure PrintReverse(delim: string := DELIMETR; elemsInLine: integer := ELEMS_IN_LINE);
/// Выводит содержимое массива в прямом порядке в каждой строке
procedure Println;
/// Выводит содержимое массива в обратном порядке в каждой строке
procedure PrintlnReverse;
end;
// ================================================================= IMPLEMENTATION ===================================================================
implementation
// ---------------------------- Стандартные методы ---------------------------
{Создает массив размера pSize}
constructor DynArray<DataType>.Create(pSize: integer);
begin
size := pSize;
cap := INC_CAP_FACTOR*pSize + MIN_CAP; // Устанавливаем емкость "с запасом"
SetLength(data, cap);
end;
{Создает массив, заполненный элементами, переданными в качестве параметров}
constructor DynArray<DataType>.Create(params xDatas: array of DataType);
begin
Create(xDatas.Length); // Сначала нужно создать массив требуемого размера
for var i := 0 to xDatas.Length - 1 do
data[i] := xDatas[i];
end;
{Выделяет новую память. Емкость увеличивается до newCap
(Если newCap меньше текущей емкости, ничего не происходит)}
procedure DynArray<DataType>.Reserve(newCap: integer);
begin
if newCap > cap then
begin
SetLength(data, newCap);
cap := newCap;
end;
end;
{Устанавливает размер массива равным newSize}
procedure DynArray<DataType>.Resize(newSize: integer);
begin
if newSize <= cap then
size := newSize
else
begin
Reserve(INC_CAP_FACTOR * newSize);
for var i := size to newSize - 1 do // явным образом заполняем новые элементы
data[i] := default(DataType);
size := newSize;
end;
end;
{Добавляет элементы, переданные в качестве параметров, в конец массива}
procedure DynArray<DataType>.Add(params xDatas: array of DataType);
begin
Resize(size + xDatas.Length);
for var i := 0 to xDatas.Length - 1 do
data[size-xDatas.Length + i] := xDatas[i];
end;
{Вставляет в массив элементы, переданные в качестве параметров,
начиная с позиции pos}
procedure DynArray<DataType>.Insert(pos: integer; params xDatas: array of DataType);
begin
Assert((0 <= pos) and (pos <= size-1));
Resize(size + xDatas.Length);
for var i := size - 2 downto pos+xDatas.Length - 1 do // сдвиг элементов вправо, начиная с позиции pos
data[i+1] := data[i-xDatas.Length + 1];
for var i := 0 to xDatas.Length - 1 do // заполнение "освободившихся" элементов новыми значениями
data[pos+i] := xDatas[i];
end;
{Удаляет count элементов массива, начиная с позиции pos.
(По умолчанию удаляется один элемент)}
procedure DynArray<DataType>.Delete(pos: integer; count: integer);
begin
Assert((0 <= pos) and (pos <= size-1));
Assert((0 <= count) and (count <= size));
if (size - pos) < count then // если количество удаляемых элементов больше,
// чем их осталось до конца массива
count := size - pos;
for var i := pos to size-1 - count do // сдвиг элементов влево на count, начиная с позиции pos
data[i] := data[i + count];
Resize(size - count); // "отрезание" лишних count элементов
end;
{Возвращает индекс первого элемента массива равного x
или -1, если такого элемента нет}
function DynArray<DataType>.Find(x: DataType): integer;
begin
result := -1;
for var i := 0 to size - 1 do
if data[i] = x then
begin
result := i;
exit;
end;
end;
{Возвращает индекс элемента массива равного x, начиная с позиции from,
или -1, если такого элемента нет}
function DynArray<DataType>.Find(x: DataType; from: integer): integer;
begin
Assert((0 <= from) and (from <= size-1));
result := -1;
for var i := from to size - 1 do
if data[i] = x then
begin
result := i;
exit;
end;
end;
// ---------------------------- Доступ к элементам ---------------------------
{Устанавливает элемент с индексом ind равным x}
procedure DynArray<DataType>.SetElem(ind: integer; x: DataType);
begin
Assert((0 <= ind) and (ind <= size-1));
data[ind] := x;
end;
{Возвращает элемент массива с индексом ind}
function DynArray<DataType>.GetElem(ind: integer): DataType;
begin
Assert((0 <= ind) and (ind <= size-1));
result := data[ind];
end;
// ----------------------------- Вывод содержимого ---------------------------
{Выводит содержимое массива в прямом порядке
delim — разделитель между элементами в строке
elemsInLine — количество элементов, выводимых в одной строке}
procedure DynArray<DataType>.Print(delim: string; elemsInLine: integer);
begin
for var i := 1 to size do
if (i mod elemsInLine) <> 0 then
write(data[i-1]:PRINT_FIELD_WIDTH, delim)
else // если вывели elemsInLine элементов, переходим на новую строку
writeln(data[i-1]:PRINT_FIELD_WIDTH);
end;
{Выводит содержимое массива в обратном порядке
delim — разделитель между элементами в строке
elemsInLine — количество элементов, выводимых в одной строке}
procedure DynArray<DataType>.PrintReverse(delim: string; elemsInLine: integer);
begin
for var i := 1 to size do
if (i mod elemsInLine) <> 0 then
write(data[size-i]:PRINT_FIELD_WIDTH, delim)
else // если вывели elemsInLine элементов, переходим на новую строку
writeln(data[size-i]:PRINT_FIELD_WIDTH);
end;
{Выводит содержимое массива в прямом порядке в каждой строке}
procedure DynArray<DataType>.Println;
begin
for var i := 0 to size - 1 do
writeln(data[i]);
end;
{Выводит содержимое массива в обратном порядке в каждой строке}
procedure DynArray<DataType>.PrintlnReverse;
begin
for var i := size - 1 downto 0 do
writeln(data[i]);
end;
end.Collections
<xh4> Интерфейс </xh4> Stack
Create
Создает пустой стек
Create(params xDatas: array of DataType)
Создает стек, заполненный элементами, переданными в качестве параметров
Push(x: DataType)
Кладет элемент x на вершину стека
Pop: DataType
Возвращает элемент типа DataType, снимая его с вершины стека
Top: DataType
Возвращает значение элемента на вершине стека
IsEmpty: boolean;
Возвращает истину, если стек пуст
Print(delim: string; elemsInLine: integer)
Выводит подряд содержимое стека
(delim — разделитель между элементами в строке,
elemsInLine — количество элементов, выводимых в одной строке)
Println
Выводит содержимое стека в каждой строке
Queue
Create
Создает пустую очередь
Create(params xDatas: array of DataType)
Создает очередь, заполненную элементами, переданными в качестве параметров
Enqueue(x: DataType)
Добавляет элемент x в хвост очереди
Dequeue: DataType
Возвращает элемент типа DataType, убирая его из головы очереди
IsEmpty: boolean;
Возвращает истину, если очередь пуста
Print(delim: string; elemsInLine: integer)
Выводит подряд содержимое очереди от головы к хвосту
(delim — разделитель между элементами в строке,
elemsInLine — количество элементов, выводимых в одной строке)
Println
Выводит содержимое очереди от головы к хвосту в каждой строке
DynArray
Count Количество элементов (размер) массива Capacity Емкость массива (отведенная память) Create(pSize: integer) Создает массив размера pSize Create(params xDatas: array of DataType) Создает массив, заполненный элементами, переданными в качестве параметров Reserve(newCap: integer) Выделяет новую память. Емкость увеличивается до newCap (Если newCap меньше текущей емкости, ничего не происходит) Resize(newSize: integer) Устанавливает размер массива равным newSize Add(params xDatas: array of DataType) Добавляет элементы, переданные в качестве параметров, в конец массива Insert(pos: integer; params xDatas: array of DataType) Вставляет в массив элементы, переданные в качестве параметров, начиная с позиции pos Delete(pos: integer; count: integer) Удаляет count элементов массива, начиная с позиции pos. (По умолчанию удаляется один элемент) Find(x: DataType): integer Возвращает индекс первого элемента массива равного x или -1, если такого элемента нет Find(x: DataType; from: integer): integer Возвращает индекс элемента массива равного x, начиная с позиции from, или -1, если такого элемента нет Print(delim: string; elemsInLine: integer) Выводит содержимое массива в прямом порядке (delim — разделитель между элементами в строке elemsInLine — количество элементов, выводимых в одной строке) PrintReverse(delim: string; elemsInLine: integer) Выводит содержимое массива в обратном порядке delim — разделитель между элементами в строке elemsInLine — количество элементов, выводимых в одной строке) Println Выводит содержимое массива в прямом порядке в каждой строке PrintlnReverse Выводит содержимое массива в прямом порядке в каждой строке
<xh4> Реализация </xh4>
/// Модуль содержит шаблоны классов
/// Stack — стек
/// Queue — очередь
/// DynArray — динамический массив с автоконтролем памяти
unit Collections;
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 xDatas : 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 xDatas: array of DataType);
/// Добавляет элемент x в хвост очереди
procedure Enqueue(x: DataType);
/// Возвращает элемент типа DataType, убирая его из головы очереди
function Dequeue: 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;
// --------------------------------------------DYN_ARRAY-------------------------------------------
const
/// Минимальная емкость, устанавливаемая при создании массива
MIN_CAP = 4;
/// Коэффициент увеличения емкости массива при её нехватке
INC_CAP_FACTOR = 2;
type
/// Шаблон класса DynArray [Динамический массив с автоконтролем памяти]
DynArray<DataType> = class
private
/// Встроенный динамический массив, содержащий данные
data: array of DataType;
/// Размер массива
size: integer;
/// Емкость массива
cap: integer;
/// Устанавливает элемент с индексом ind равным x
procedure SetElem(ind: integer; x: DataType);
/// Возвращает элемент массива с индексом ind
function GetElem(ind: integer): DataType;
public
// ---------------------------- Стандартные методы ---------------------------
/// Создает массив размера pSize
constructor Create(pSize: integer := 0);
/// Создает массив, заполненный элементами, переданными в качестве параметров
constructor Create(params xDatas: array of DataType);
/// Выделяет новую память. Емкость увеличивается до newCap
/// (Если newCap меньше текущей емкости, ничего не происходит)
procedure Reserve(newCap: integer);
/// Устанавливает размер массива равным newSize
procedure Resize(newSize: integer);
/// Добавляет элементы, переданные в качестве параметров, в конец массива
procedure Add(x: DataType);
/// Добавляет элементы, переданные в качестве параметров, в конец массива
procedure Add(params xDatas: array of DataType);
/// Вставляет в массив элементы, переданные в качестве параметров,
/// начиная с позиции pos
procedure Insert(pos: integer; params xDatas: array of DataType);
/// Удаляет count элементов массива, начиная с позиции pos.
/// (По умолчанию удаляется один элемент)
procedure Delete(pos: integer; count: integer := 1);
/// Возвращает индекс первого элемента массива равного x
/// или -1, если такого элемента нет
function Find(x: DataType): integer;
/// Возвращает индекс элемента массива равного x, начиная с позиции from,
/// или -1, если такого элемента нет}
function Find(x: DataType; from: integer): integer;
// --------------------------------- Свойства --------------------------------
/// Количество элементов (размер) массива
property Count: integer read size write Resize;
/// Емкость массива (отведенная память)
property Capacity: integer read cap write Reserve;
/// Позволяет обращаться к элементам массива по индексу
/// (например, apples[5])
property Elem[index: integer]: DataType read GetElem write SetElem; default;
// ----------------------------- Вывод содержимого ---------------------------
/// <summary>
/// Выводит содержимое массива в прямом порядке
/// </summary>
/// <param name="delim">Разделитель между элементами в строке</param>
/// <param name="elemsInLine">Количество элементов, выводимых в одной строке</param>
procedure Print(delim : string := DELIMETR; elemsInLine : integer := ELEMS_IN_LINE);
/// <summary>
/// Выводит содержимое массива в обратном порядке
/// </summary>
/// <param name="delim">Разделитель между элементами в строке</param>
/// <param name="elemsInLine">Количество элементов, выводимых в одной строке</param>
procedure PrintReverse(delim: string := DELIMETR; elemsInLine: integer := ELEMS_IN_LINE);
/// Выводит содержимое массива в прямом порядке в каждой строке
procedure Println;
/// Выводит содержимое массива в обратном порядке в каждой строке
procedure PrintlnReverse;
end;
// --------------------------------------------SimpleSet-------------------------------------------
type SimpleSet<DataType> = class
private
data:=new DynArray<DataType>;
public
/// <summary>
/// Добавляет элемент в множество
/// </summary>
/// <param name="x">Добавляемый элемент</param>
procedure Add(x:DataType);
/// <summary>
/// Удаляет элемент из множества
/// </summary>
/// <param name="x">Удаляемый элемент</param>
procedure Remove(x:DataType);
/// <summary>
/// Проверяет, содержит ли множество элемент
/// </summary>
/// <param name="x">Искомый элемент</param>
function Contains(x:DataType):boolean;
///Выводит содержимое множества на консоль
procedure Print();
///Выводит содержимое множества на консоль
procedure Println();
end;
// ================================================================= IMPLEMENTATION ===================================================================
implementation
// ----------------------------------------------STACK---------------------------------------------
// ---------------------------- Стандартные методы ---------------------------
{Стандартный конструктор}
constructor Stack<DataType>.Create;
begin
fTop := nil;
end;
{Создает стек, заполненный элементами, переданными в качестве параметров}
constructor Stack<DataType>.Create(params xDatas: array of DataType);
begin
fTop := nil;
for var i := 0 to xDatas.Length - 1 do
Push(xDatas[i]);
end;
{Кладет элемент x на вершину стека}
procedure Stack<DataType>.Push(x: DataType);
begin
fTop := new SingleNode<DataType>(x, fTop);
end;
{Возвращает элемент типа DataType, снимая его с вершины стека}
function Stack<DataType>.Pop: DataType;
begin
if IsEmpty then
raise new Exception('Попытка снятия элемента с пустого стека!');
result := fTop.data;
fTop := fTop.next; // элемент снимается с вершины стека
// (т.е. вершиной становится следующий элемент)
end;
{Возвращает значение элемента на вершине стека}
function Stack<DataType>.Top: DataType;
begin
if IsEmpty then
raise new Exception('Попытка получения элемента с пустого стека!');
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 xDatas: array of DataType);
begin
head := nil;
tail := nil;
for var i := 0 to xDatas.Length - 1 do
Enqueue(xDatas[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
if IsEmpty then
raise new Exception('Попытка удаления элемента из пустой очереди!');
result := head.data;
head := head.next; // элемент убирается из головы очереди
// (т.е. головой становится следующий элемент)
if head = nil then
tail := nil;
end;
{Возвращает элемент типа DataType, не убирая его из головы очереди}
function Queue<DataType>.Top: DataType;
begin
if IsEmpty then
raise new Exception('Попытка получения элемента из пустой очереди!');
result := head.data;
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;
// --------------------------------------------DYN_ARRAY-------------------------------------------
// ---------------------------- Стандартные методы ---------------------------
{Создает массив размера pSize}
constructor DynArray<DataType>.Create(pSize: integer);
begin
size := pSize;
cap := INC_CAP_FACTOR*pSize + MIN_CAP; // Устанавливаем емкость "с запасом"
SetLength(data, cap);
end;
{Создает массив, заполненный элементами, переданными в качестве параметров}
constructor DynArray<DataType>.Create(params xDatas: array of DataType);
begin
Create(xDatas.Length); // Сначала нужно создать массив требуемого размера
for var i := 0 to xDatas.Length - 1 do
data[i] := xDatas[i];
end;
{Выделяет новую память. Емкость увеличивается до newCap
(Если newCap меньше текущей емкости, ничего не происходит)}
procedure DynArray<DataType>.Reserve(newCap: integer);
begin
if newCap > cap then
begin
SetLength(data, newCap);
cap := newCap;
end;
end;
{Устанавливает размер массива равным newSize}
procedure DynArray<DataType>.Resize(newSize: integer);
begin
if newSize <= cap then
size := newSize
else
begin
Reserve(INC_CAP_FACTOR * newSize);
for var i := size to newSize - 1 do // явным образом заполняем новые элементы
data[i] := default(DataType);
size := newSize;
end;
end;
{Добавляет элемент в конец массива}
procedure DynArray<DataType>.Add(x: DataType);
begin
Resize(size + 1);
data[size-1] := x;
end;
{Добавляет элементы, переданные в качестве параметров, в конец массива}
procedure DynArray<DataType>.Add(params xDatas: array of DataType);
begin
Resize(size + xDatas.Length);
for var i := 0 to xDatas.Length - 1 do
data[size-xDatas.Length + i] := xDatas[i];
end;
{Вставляет в массив элементы, переданные в качестве параметров,
начиная с позиции pos}
procedure DynArray<DataType>.Insert(pos: integer; params xDatas: array of DataType);
begin
if (pos < 0) or (pos > size-1) then
raise new Exception('Попытка вставки за границей массива в позицию ' + IntToStr(pos) + ' !');
Resize(size + xDatas.Length);
for var i := size - 2 downto pos+xDatas.Length - 1 do // сдвиг элементов вправо, начиная с позиции pos
data[i+1] := data[i-xDatas.Length + 1];
for var i := 0 to xDatas.Length - 1 do // заполнение "освободившихся" элементов новыми значениями
data[pos+i] := xDatas[i];
end;
{Удаляет count элементов массива, начиная с позиции pos.
(По умолчанию удаляется один элемент)}
procedure DynArray<DataType>.Delete(pos: integer; count: integer);
begin
if (pos < 0) or (pos > size-1) then
raise new Exception('Попытка удаления за границей массива из позиции ' + IntToStr(pos) + ' !');
Assert((0 <= count) and (count <= size));
if (size - pos) < count then // если количество удаляемых элементов больше,
// чем их осталось до конца массива
count := size - pos;
for var i := pos to size-1 - count do // сдвиг элементов влево на count, начиная с позиции pos
data[i] := data[i + count];
Resize(size - count); // "отрезание" лишних count элементов
end;
{Возвращает индекс первого элемента массива равного x
или -1, если такого элемента нет}
function DynArray<DataType>.Find(x: DataType): integer;
begin
result := -1;
for var i := 0 to size - 1 do
if data[i] = x then
begin
result := i;
exit;
end;
end;
{Возвращает индекс элемента массива равного x, начиная с позиции from,
или -1, если такого элемента нет}
function DynArray<DataType>.Find(x: DataType; from: integer): integer;
begin
if (from < 0) or (from > size-1) then
raise new Exception('Попытка поиска за границей массива с позиции ' + IntToStr(from) + ' !');
result := -1;
for var i := from to size - 1 do
if data[i] = x then
begin
result := i;
exit;
end;
end;
// ---------------------------- Доступ к элементам ---------------------------
{Устанавливает элемент с индексом ind равным x}
procedure DynArray<DataType>.SetElem(ind: integer; x: DataType);
begin
if (ind < 0) or (ind > size-1) then
raise new Exception('Попытка установки элемента за границей массива из позиции ' + IntToStr(ind) + ' !');
data[ind] := x;
end;
{Возвращает элемент массива с индексом ind}
function DynArray<DataType>.GetElem(ind: integer): DataType;
begin
if (ind < 0) or (ind > size-1) then
raise new Exception('Попытка получения элемента за границей массива из позиции ' + IntToStr(ind) + ' !');
result := data[ind];
end;
// ----------------------------- Вывод содержимого ---------------------------
{Выводит содержимое массива в прямом порядке
delim — разделитель между элементами в строке
elemsInLine — количество элементов, выводимых в одной строке}
procedure DynArray<DataType>.Print(delim: string; elemsInLine: integer);
begin
for var i := 1 to size do
if (i mod elemsInLine) <> 0 then
write(data[i-1]:PRINT_FIELD_WIDTH, delim)
else // если вывели elemsInLine элементов, переходим на новую строку
writeln(data[i-1]:PRINT_FIELD_WIDTH);
end;
{Выводит содержимое массива в обратном порядке
delim — разделитель между элементами в строке
elemsInLine — количество элементов, выводимых в одной строке}
procedure DynArray<DataType>.PrintReverse(delim: string; elemsInLine: integer);
begin
for var i := 1 to size do
if (i mod elemsInLine) <> 0 then
write(data[size-i]:PRINT_FIELD_WIDTH, delim)
else // если вывели elemsInLine элементов, переходим на новую строку
writeln(data[size-i]:PRINT_FIELD_WIDTH);
end;
{Выводит содержимое массива в прямом порядке в каждой строке}
procedure DynArray<DataType>.Println;
begin
for var i := 0 to size - 1 do
writeln(data[i]);
end;
{Выводит содержимое массива в обратном порядке в каждой строке}
procedure DynArray<DataType>.PrintlnReverse;
begin
for var i := size - 1 downto 0 do
writeln(data[i]);
end;
// --------------------------------------------SimpleSet-------------------------------------------
{Удаляет элемент из множества}
procedure SimpleSet<DataType>.Remove(x:DataType);
begin
if data.Find(x)<>-1 then
data.Delete(data.Find(x),1);
end;
{Добавляет элемент во множество}
procedure SimpleSet<DataType>.Add(x:DataType);
begin
if data.Find(x)=-1 then
data.Add(x);
end;
{Определяет, содержится ли элемент во множестве}
function SimpleSet<DataType>.Contains(x:DataType):boolean;
begin
result:=data.Find(x)<>-1;
end;
{Печатает множество}
procedure SimpleSet<DataType>.Print();
begin
data.print(DELIMETR,ELEMS_IN_LINE);
end;
{Печатает множество}
procedure SimpleSet<DataType>.Println();
begin
data.Println();
end;
end.