Collections — различия между версиями
Материал из Вики ИТ мехмата ЮФУ
Juliet (обсуждение | вклад) (→SimpleSet) |
Juliet (обсуждение | вклад) (→Collections) |
||
Строка 88: | Строка 88: | ||
uses Nodes; // для использования типа SingleNode<DataType> — | uses Nodes; // для использования типа SingleNode<DataType> — | ||
// узла с одним полем связи | // узла с одним полем связи | ||
− | + | ||
// --------------------------------------------- STACK -------------------------------------------- | // --------------------------------------------- STACK -------------------------------------------- | ||
Строка 145: | Строка 145: | ||
/// Возвращает значение элемента в голове очереди, не удаляя его | /// Возвращает значение элемента в голове очереди, не удаляя его | ||
function Top: DataType; | function Top: DataType; | ||
− | + | ||
/// Возвращает истину, если очередь пуста | /// Возвращает истину, если очередь пуста | ||
function IsEmpty: boolean; | function IsEmpty: boolean; | ||
− | + | ||
// ---------------------------------- Вывод ---------------------------------- | // ---------------------------------- Вывод ---------------------------------- | ||
/// Выводит содержимое очереди на консоль | /// Выводит содержимое очереди на консоль | ||
Строка 224: | Строка 224: | ||
/// Емкость массива (отведенная память) | /// Емкость массива (отведенная память) | ||
property Capacity: integer read cap write Reserve; | property Capacity: integer read cap write Reserve; | ||
− | + | ||
/// Позволяет обращаться к элементам массива по индексу | /// Позволяет обращаться к элементам массива по индексу | ||
/// (например, apples[5]) | /// (например, apples[5]) | ||
property Elem[index: integer]: DataType read GetElem write SetElem; default; | property Elem[index: integer]: DataType read GetElem write SetElem; default; | ||
− | + | ||
// ---------------------------------- Вывод ---------------------------------- | // ---------------------------------- Вывод ---------------------------------- | ||
/// Выводит содержимое массива на консоль | /// Выводит содержимое массива на консоль | ||
Строка 243: | Строка 243: | ||
/// Элементы множества | /// Элементы множества | ||
data := new DynArray<DataType>; | data := new DynArray<DataType>; | ||
− | + | ||
public | public | ||
/// <summary> | /// <summary> | ||
Строка 261: | Строка 261: | ||
/// <param name="x">Искомый элемент</param> | /// <param name="x">Искомый элемент</param> | ||
function Contains(x: DataType): boolean; | function Contains(x: DataType): boolean; | ||
− | + | ||
// ---------------------------------- Вывод ---------------------------------- | // ---------------------------------- Вывод ---------------------------------- | ||
///Выводит содержимое множества на консоль | ///Выводит содержимое множества на консоль | ||
procedure Println(); | procedure Println(); | ||
end; | end; | ||
− | + | ||
// ------------------------------------------- ASSOC_ARRAY ---------------------------------------- | // ------------------------------------------- ASSOC_ARRAY ---------------------------------------- | ||
type | type | ||
Строка 276: | Строка 276: | ||
/// Значения, соответствующие ключам | /// Значения, соответствующие ключам | ||
values: DynArray<ValueType> := new DynArray<ValueType>; | values: DynArray<ValueType> := new DynArray<ValueType>; | ||
− | + | ||
/// Устанавливает значение элемента с ключом key равным value | /// Устанавливает значение элемента с ключом key равным value | ||
procedure SetElem(key: KeyType; value: ValueType); | procedure SetElem(key: KeyType; value: ValueType); | ||
/// Возвращает значение элемента с ключом key | /// Возвращает значение элемента с ключом key | ||
function GetElem(key: KeyType): ValueType; | function GetElem(key: KeyType): ValueType; | ||
− | + | ||
public | public | ||
// --------------------------------- Свойства -------------------------------- | // --------------------------------- Свойства -------------------------------- | ||
Строка 287: | Строка 287: | ||
/// (Например, zoo['крокодил']) | /// (Например, zoo['крокодил']) | ||
property Elem[key: KeyType]: ValueType read GetElem write SetElem; default; | property Elem[key: KeyType]: ValueType read GetElem write SetElem; default; | ||
+ | |||
+ | // ---------------------------------- Вывод ---------------------------------- | ||
+ | ///Выводит содержимое ассоциативного массива на консоль | ||
+ | procedure Println(); | ||
end; | end; | ||
Строка 295: | Строка 299: | ||
// --------------------------------------------- STACK -------------------------------------------- | // --------------------------------------------- STACK -------------------------------------------- | ||
− | + | ||
// ---------------------------- Стандартные методы --------------------------- | // ---------------------------- Стандартные методы --------------------------- | ||
{Создает пустой стек} | {Создает пустой стек} | ||
Строка 314: | Строка 318: | ||
if IsEmpty then | if IsEmpty then | ||
raise new Exception('Попытка снятия элемента с пустого стека!'); | raise new Exception('Попытка снятия элемента с пустого стека!'); | ||
− | + | ||
result := fTop.data; | result := fTop.data; | ||
fTop := fTop.next; // элемент снимается с вершины стека | fTop := fTop.next; // элемент снимается с вершины стека | ||
Строка 325: | Строка 329: | ||
if IsEmpty then | if IsEmpty then | ||
raise new Exception('Попытка получения элемента с пустого стека!'); | raise new Exception('Попытка получения элемента с пустого стека!'); | ||
− | + | ||
result := fTop.data; | result := fTop.data; | ||
end; | end; | ||
Строка 342: | Строка 346: | ||
begin | begin | ||
var curElem := fTop; | var curElem := fTop; | ||
− | + | ||
while curElem <> nil do | while curElem <> nil do | ||
begin | begin | ||
Строка 351: | Строка 355: | ||
writeln(); | writeln(); | ||
end; | end; | ||
− | + | ||
// --------------------------------------------- QUEUE -------------------------------------------- | // --------------------------------------------- QUEUE -------------------------------------------- | ||
Строка 384: | Строка 388: | ||
if IsEmpty then | if IsEmpty then | ||
raise new Exception('Попытка удаления элемента из пустой очереди!'); | raise new Exception('Попытка удаления элемента из пустой очереди!'); | ||
− | + | ||
result := head.data; | result := head.data; | ||
head := head.next; // элемент удаляется из головы очереди | head := head.next; // элемент удаляется из головы очереди | ||
Строка 397: | Строка 401: | ||
if IsEmpty then | if IsEmpty then | ||
raise new Exception('Попытка получения элемента из пустой очереди!'); | raise new Exception('Попытка получения элемента из пустой очереди!'); | ||
− | + | ||
result := head.data; | result := head.data; | ||
end; | end; | ||
Строка 416: | Строка 420: | ||
begin | begin | ||
var curElem := head; | var curElem := head; | ||
− | + | ||
while curElem <> nil do | while curElem <> nil do | ||
begin | begin | ||
Строка 426: | Строка 430: | ||
end; | end; | ||
− | + | ||
// -------------------------------------------DYN_ARRAY ------------------------------------------ | // -------------------------------------------DYN_ARRAY ------------------------------------------ | ||
− | + | ||
// ---------------------------- Стандартные методы --------------------------- | // ---------------------------- Стандартные методы --------------------------- | ||
{Создает массив размера pSize} | {Создает массив размера pSize} | ||
Строка 435: | Строка 439: | ||
if pSize < 0 then | if pSize < 0 then | ||
raise new Exception('Попытка присвоить размеру массива отрицательное значение ' + IntToStr(pSize) + '!'); | raise new Exception('Попытка присвоить размеру массива отрицательное значение ' + IntToStr(pSize) + '!'); | ||
− | + | ||
size := pSize; | size := pSize; | ||
cap := INC_CAP_FACTOR*pSize + MIN_CAP; // Устанавливаем емкость "с запасом" | cap := INC_CAP_FACTOR*pSize + MIN_CAP; // Устанавливаем емкость "с запасом" | ||
Строка 483: | Строка 487: | ||
raise new Exception( | raise new Exception( | ||
'Попытка вставки за границей массива в позицию ' + IntToStr(pos) + '!'); | 'Попытка вставки за границей массива в позицию ' + IntToStr(pos) + '!'); | ||
− | + | ||
Resize(size + 1); | Resize(size + 1); | ||
for var i := size - 2 downto pos do | for var i := size - 2 downto pos do | ||
Строка 514: | Строка 518: | ||
end; | end; | ||
end; | end; | ||
− | + | ||
// ---------------------------- Доступ к элементам --------------------------- | // ---------------------------- Доступ к элементам --------------------------- | ||
{Устанавливает элемент с индексом ind равным x} | {Устанавливает элемент с индексом ind равным x} | ||
Строка 522: | Строка 526: | ||
raise new Exception( | raise new Exception( | ||
'Попытка присвоить значение элементу за границей массива с индексом ' + IntToStr(ind) + '!'); | 'Попытка присвоить значение элементу за границей массива с индексом ' + IntToStr(ind) + '!'); | ||
− | + | ||
data[ind] := x; | data[ind] := x; | ||
end; | end; | ||
Строка 532: | Строка 536: | ||
raise new Exception( | raise new Exception( | ||
'Попытка получить значение элемента за границей массива с индексом ' + IntToStr(ind) + '!'); | 'Попытка получить значение элемента за границей массива с индексом ' + IntToStr(ind) + '!'); | ||
− | + | ||
result := data[ind]; | result := data[ind]; | ||
end; | end; | ||
Строка 544: | Строка 548: | ||
writeln(); | writeln(); | ||
end; | end; | ||
− | + | ||
{Выводит содержимое массива на консоль в обратном порядке} | {Выводит содержимое массива на консоль в обратном порядке} | ||
procedure DynArray<DataType>.PrintlnReverse(); | procedure DynArray<DataType>.PrintlnReverse(); | ||
Строка 555: | Строка 559: | ||
// ------------------------------------------- SIMPLE_SET ----------------------------------------- | // ------------------------------------------- SIMPLE_SET ----------------------------------------- | ||
+ | |||
+ | // ---------------------------- Стандартные методы --------------------------- | ||
{Добавляет элемент x во множество} | {Добавляет элемент x во множество} | ||
procedure SimpleSet<DataType>.Add(x: DataType); | procedure SimpleSet<DataType>.Add(x: DataType); | ||
Строка 561: | Строка 567: | ||
data.Add(x); | data.Add(x); | ||
end; | end; | ||
− | + | ||
{Удаляет элемент x из множества} | {Удаляет элемент x из множества} | ||
procedure SimpleSet<DataType>.Remove(x: DataType); | procedure SimpleSet<DataType>.Remove(x: DataType); | ||
Строка 582: | Строка 588: | ||
data.Println; | data.Println; | ||
end; | end; | ||
+ | |||
+ | |||
+ | // ------------------------------------------- ASSOC_ARRAY ---------------------------------------- | ||
− | + | // ---------------------------- Доступ к элементам --------------------------- | |
− | // ---------------------------- | ||
{Устанавливает значение элемента с ключом key равным value} | {Устанавливает значение элемента с ключом key равным value} | ||
procedure AssocArray<KeyType, ValueType>.SetElem(key: KeyType; value: ValueType); | procedure AssocArray<KeyType, ValueType>.SetElem(key: KeyType; value: ValueType); | ||
Строка 597: | Строка 605: | ||
end; | end; | ||
end; | end; | ||
− | + | ||
{Возвращает значение элемента с ключом key} | {Возвращает значение элемента с ключом key} | ||
function AssocArray<KeyType, ValueType>.GetElem(key: KeyType): ValueType; | function AssocArray<KeyType, ValueType>.GetElem(key: KeyType): ValueType; | ||
Строка 612: | Строка 620: | ||
end; | end; | ||
+ | // ---------------------------------- Вывод ---------------------------------- | ||
+ | {Выводит содержимое ассоциативного массива на консоль} | ||
+ | procedure AssocArray<KeyType, ValueType>.Println(); | ||
+ | begin | ||
+ | for var i := 0 to keys.Count - 1 do | ||
+ | writeln(keys[i], ': ', values[i]); | ||
+ | end; | ||
+ | |||
end. | end. | ||
</source> | </source> |
Версия 18:49, 23 апреля 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 — очередь
/// DynArray — динамический массив с автоконтролем памяти
/// SimpleSet — простое множество (с минимальным набором операций)
/// AssocArray — ассоциативный массив
unit Collections;
interface
uses Nodes; // для использования типа SingleNode<DataType> —
// узла с одним полем связи
// --------------------------------------------- STACK --------------------------------------------
type
/// Шаблон класса Stack [Стек]
Stack<DataType> = class
private
/// Вершина стека
fTop: SingleNode<DataType> := nil;
public
// ---------------------------- Стандартные методы ---------------------------
/// Создает пустой стек
constructor Create;
/// <summary>
/// Кладет элемент на вершину стека
/// </summary>
/// <param name="x">Новый элемент</param>
procedure Push(x: DataType);
/// Возвращает значение элемента на вершине, снимая его со стека
function Pop: DataType;
/// Возвращает значение элемента на вершине стека, не снимая его
function Top: DataType;
/// Возвращает истину, если стек пуст
function IsEmpty: boolean;
// ---------------------------------- Вывод ----------------------------------
/// Выводит содержимое стека на консоль
procedure Println();
end;
// --------------------------------------------- QUEUE --------------------------------------------
type
/// Шаблон класса Queue [Очередь]
Queue<DataType> = class
private
/// Голова очереди
head: SingleNode<DataType>;
/// Хвост очереди
tail: SingleNode<DataType>;
public
// ---------------------------- Стандартные методы ---------------------------
/// Создает пустую очередь
constructor Create;
/// <summary>
/// Добавляет элемент в хвост очереди
/// </summary>
/// <param name="x">Добавляемый элемент</param>
procedure Enqueue(x: DataType);
/// Возвращает значение элемента в голове, удаляя его из очереди
function Dequeue: DataType;
/// Возвращает значение элемента в голове очереди, не удаляя его
function Top: DataType;
/// Возвращает истину, если очередь пуста
function IsEmpty: boolean;
// ---------------------------------- Вывод ----------------------------------
/// Выводит содержимое очереди на консоль
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);
/// <summary>
/// Выделяет новую память. Емкость увеличивается.
/// (Если newCap меньше текущей емкости, ничего не происходит)
/// </summary>
/// <param name="newCap">Новая емкость массива</param>
procedure Reserve(newCap: integer);
/// <summary>
/// Устанавливает новый размер массива
/// </summary>
/// <param name="newSize">Новый размер массива</param>
procedure Resize(newSize: integer);
/// <summary>
/// Добавляет элемент в конец массива
/// </summary>
/// <param name="x">Добавляемый элемент</param>
procedure Add(x: DataType);
/// <summary>
/// Вставляет элемент в указанную позицию
/// </summary>
/// <param name="pos">Позиция, в которую вставляется элемент</param>
/// <param name="x">Вставляемый элемент</param>
procedure Insert(pos: integer; x: DataType);
/// <summary>
/// Удаляет элемент массива из указанной позиции
/// </summary>
/// <param name="pos">Позиция, из которой удаляется элемент</param>
procedure Remove(pos: integer);
/// <summary>
/// Возвращает индекс первого элемента массива равного искомому
/// или -1, если такого элемента нет
/// </summary>
/// <param name="x">Искомый элемент</param>
function Find(x: DataType): 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;
// ---------------------------------- Вывод ----------------------------------
/// Выводит содержимое массива на консоль
procedure Println();
/// Выводит содержимое массива на консоль в обратном порядке
procedure PrintlnReverse();
end;
// ------------------------------------------- SIMPLE_SET -----------------------------------------
type
/// Шаблон класса SimpleSet [Простое множество]
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 Println();
end;
// ------------------------------------------- ASSOC_ARRAY ----------------------------------------
type
/// Шаблон класса AssocArray [Ассоциативный массив]
AssocArray<KeyType, ValueType> = class
private
/// Ключи
keys: DynArray<KeyType> := new DynArray<KeyType>;
/// Значения, соответствующие ключам
values: DynArray<ValueType> := new DynArray<ValueType>;
/// Устанавливает значение элемента с ключом key равным value
procedure SetElem(key: KeyType; value: ValueType);
/// Возвращает значение элемента с ключом key
function GetElem(key: KeyType): ValueType;
public
// --------------------------------- Свойства --------------------------------
/// Позволяет обращаться к элементам массива по ключу
/// (Например, zoo['крокодил'])
property Elem[key: KeyType]: ValueType read GetElem write SetElem; default;
// ---------------------------------- Вывод ----------------------------------
///Выводит содержимое ассоциативного массива на консоль
procedure Println();
end;
// ================================================================= 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;
{Возвращает значение элемента на вершине, снимая его со стека}
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;
// ---------------------------------- Вывод ----------------------------------
{Выводит содержимое стека на консоль}
procedure Stack<DataType>.Println();
begin
if not IsEmpty then
begin
var curElem := fTop;
while curElem <> nil do
begin
write(curElem.data, ' ');
curElem := curElem.next;
end;
end;
writeln();
end;
// --------------------------------------------- QUEUE --------------------------------------------
// ---------------------------- Стандартные методы ---------------------------
{Создает пустую очередь}
constructor Queue<DataType>.Create;
begin
head := nil;
tail := nil;
end;
{Добавляет элемент x в хвост очереди}
procedure Queue<DataType>.Enqueue(x: DataType);
begin
if IsEmpty then
begin
head := new SingleNode<DataType>(x, nil);
tail := head;
end
else
begin
tail.next := new SingleNode<DataType>(x, nil);
tail := tail.next; // элемент удаляется из хвоста очереди
// (т.е. хвостом становится следующий элемент)
end;
end;
{Возвращает значение элемента в голове, удаляя его из очереди}
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;
{Возвращает значение элемента в голове очереди, не удаляя его}
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;
// ---------------------------------- Вывод ----------------------------------
{Выводит содержимое очереди на консоль}
procedure Queue<DataType>.Println();
begin
if not IsEmpty then
begin
var curElem := head;
while curElem <> nil do
begin
write(curElem.data, ' ');
curElem := curElem.next;
end;
end;
writeln();
end;
// -------------------------------------------DYN_ARRAY ------------------------------------------
// ---------------------------- Стандартные методы ---------------------------
{Создает массив размера pSize}
constructor DynArray<DataType>.Create(pSize: integer);
begin
if pSize < 0 then
raise new Exception('Попытка присвоить размеру массива отрицательное значение ' + IntToStr(pSize) + '!');
size := pSize;
cap := INC_CAP_FACTOR*pSize + MIN_CAP; // Устанавливаем емкость "с запасом"
SetLength(data, cap);
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 < 0 then
raise new Exception('Попытка присвоить размеру массива отрицательное значение ' + IntToStr(newSize) + '!');
if newSize > cap then
begin
Reserve(INC_CAP_FACTOR * newSize);
for var i := size to newSize - 1 do // явным образом заполняем новые элементы
data[i] := default(DataType);
end
else if newSize < size then
for var i := newSize to size - 1 do
data[i] := default(DataType);
size := newSize;
end;
{Добавляет элемент x в конец массива }
procedure DynArray<DataType>.Add(x: DataType);
begin
Resize(size + 1);
data[size-1] := x;
end;
{Вставляет x элемент в позицию pos}
procedure DynArray<DataType>.Insert(pos: integer; x: DataType);
begin
if (pos < 0) or (pos > size-1) then
raise new Exception(
'Попытка вставки за границей массива в позицию ' + IntToStr(pos) + '!');
Resize(size + 1);
for var i := size - 2 downto pos do
data[i+1] := data[i];
data[pos] := x;
end;
{Удаляет элемент массива из позиции pos}
procedure DynArray<DataType>.Remove(pos: integer);
begin
if (pos < 0) or (pos > size-1) then
raise new Exception(
'Попытка удаления за границей массива из позиции ' + IntToStr(pos) + '!');
for var i := pos to size - 2 do // сдвиг элементов влево на 1, начиная с позиции pos
data[i] := data[i+1];
Resize(size - 1);
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;
// ---------------------------- Доступ к элементам ---------------------------
{Устанавливает элемент с индексом 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;
// ---------------------------------- Вывод ----------------------------------
{Выводит содержимое массива на консоль}
procedure DynArray<DataType>.Println();
begin
for var i := 0 to size - 1 do
write(data[i], ' ');
writeln();
end;
{Выводит содержимое массива на консоль в обратном порядке}
procedure DynArray<DataType>.PrintlnReverse();
begin
for var i := size - 1 downto 0 do
write(data[i], ' ');
writeln();
end;
// ------------------------------------------- SIMPLE_SET -----------------------------------------
// ---------------------------- Стандартные методы ---------------------------
{Добавляет элемент x во множество}
procedure SimpleSet<DataType>.Add(x: DataType);
begin
if data.Find(x) = -1 then
data.Add(x);
end;
{Удаляет элемент x из множества}
procedure SimpleSet<DataType>.Remove(x: DataType);
begin
var xPos := data.Find(x);
if xPos <> -1 then
data.Remove(xPos);
end;
{Возвращает истину, если множество содержит элемент x}
function SimpleSet<DataType>.Contains(x: DataType): boolean;
begin
result := (data.Find(x) <> -1);
end;
// ---------------------------------- Вывод ----------------------------------
{Выводит содержимое множества на консоль}
procedure SimpleSet<DataType>.Println();
begin
data.Println;
end;
// ------------------------------------------- ASSOC_ARRAY ----------------------------------------
// ---------------------------- Доступ к элементам ---------------------------
{Устанавливает значение элемента с ключом key равным value}
procedure AssocArray<KeyType, ValueType>.SetElem(key: KeyType; value: ValueType);
begin
var ind := Keys.Find(key);
if ind <> -1 then
Values[ind] := value
else
begin
Keys.Add(key);
Values.Add(value);
end;
end;
{Возвращает значение элемента с ключом key}
function AssocArray<KeyType, ValueType>.GetElem(key: KeyType): ValueType;
begin
var ind := Keys.Find(key);
if ind <> -1 then
result := Values[ind]
else
begin
Keys.Add(key);
Values.Add(default(ValueType));
result := default(ValueType);
end;
end;
// ---------------------------------- Вывод ----------------------------------
{Выводит содержимое ассоциативного массива на консоль}
procedure AssocArray<KeyType, ValueType>.Println();
begin
for var i := 0 to keys.Count - 1 do
writeln(keys[i], ': ', values[i]);
end;
end.
Интерфейс и примеры использования
Stack
<xh4> Интерфейс </xh4>
Create Создает пустой стек Push(x: DataType) Кладет элемент x на вершину стека Pop: DataType Возвращает значение элемента на вершине, снимая его со стека Top: DataType Возвращает значение элемента на вершине стека IsEmpty: boolean Возвращает истину, если стек пуст Println Выводит содержимое стека на консоль
<xh4> Примеры использования </xh4>
uses Collections;
begin
// Создание нового объекта стека
var s := new Stack<integer>;
// Проверка стека на пустоту
writeln('Стек пуст: ', s.IsEmpty);
writeln();
// Добавление нового элемента на вершину стеку
s.Push(5);
writeln('Стек пуст: ', s.IsEmpty);
s.Push(7);
// Вывод элемента на вершине стека
writeln('Вершина стека = ', s.Top);
writeln();
s.Push(-11);
// Вывод элемента на вершине стека и снятие его со стека
writeln('Вершина стека = ', s.Pop);
writeln('Вершина стека после снятия предыдущей = ', s.Top);
writeln();
s.Push(105); s.Push(-69);
writeln('Содержимое всего стека:');
s.Println;
writeln();
// Снятие всех элементов со стека
while not s.IsEmpty do
write(s.Pop, ' ');
writeln(NewLine);
// Обработка исключения при попытке чтения элемента
// на вершине пустого стека
try
s.Top;
except
on e: Exception do
writeln(e);
end;
end.
Queue
<xh4> Интерфейс </xh4>
Create Создает пустую очередь Enqueue(x: DataType) Добавляет элемент x в хвост очереди Dequeue: DataType Возвращает значение элемента в голове, убирая его из очереди Top: DataType Возвращает значение элемента в голове очереди, не убирая его IsEmpty: boolean Возвращает истину, если очередь пуста Println Выводит содержимое очереди на консоль
<xh4> Примеры использования </xh4>
uses Collections;
begin
// Создание нового объекта очереди
var q := new Queue<integer>;
// Проверка очереди на пустоту
writeln('Очередь пуста: ', q.IsEmpty);
writeln();
// Добавление элемента в хвост очереди
q.Enqueue(-8);
writeln('Очередь пуста: ', q.IsEmpty);
q.Enqueue(43);
// Вывод головы очереди
writeln('Голова очереди = ', q.Top);
writeln();
q.Enqueue(-15);
// Вывод головы и удаление её из очереди
writeln('Голова очереди = ', q.Dequeue);
writeln('Голова очереди после убирания предыдущей = ', q.Top);
writeln();
q.Enqueue(11); q.Enqueue(136);
// Вывод содержимого очереди
writeln('Содержимое всей очереди:');
q.Println;
writeln();
// Удаление всех элементов из очереди
while not q.IsEmpty do
write(q.Dequeue, ' ');
writeln(NewLine);
// Обработка исключения при попытке чтения элемента
// в голове пустой очереди
try
q.Top;
except
on e: Exception do
writeln(e);
end;
end.
DynArray
<xh4> Интерфейс </xh4>
Count Размер массива (количество элементов) Capacity Емкость массива (отведенная память) Create(pSize: integer) Создает массив размера pSize Reserve(newCap: integer) Выделяет новую память. Емкость увеличивается до newCap (Если newCap меньше текущей емкости, ничего не происходит) Resize(newSize: integer) Устанавливает размер массива равным newSize Add(x: DataType) Добавляет элемент x в конец массива Insert(pos: integer; x: DataType) Вставляет x элемент в позицию pos Delete(pos: integer) Удаляет элемент массива из позиции pos Find(x: DataType): integer Возвращает индекс первого элемента массива равного x или -1, если такого элемента нет Println Выводит содержимое массива на консоль PrintlnReverse Выводит содержимое массива на консоль в обратном порядке
<xh4> Примеры использования </xh4>
uses Collections;
begin
// Создание объекта динамического массива
var d := new DynArray<integer>(0);
// Вывод размера массива
writeln('Размер массива = ', d.Count); writeln();
// Добавление элемента в массив
d.Add(15); d.Add(-9); d.Add(136);
// Вывод содержимого массива
writeln('Содержимое всего массива:');
d.Println; writeln();
// Вставка элемента x в позицию pos
d.Insert(2, 47);
writeln('Содержимое всего массива после вставки элемента:');
d.Println; writeln();
// Доступ к элементу по индексу
d[0] := 61;
writeln('Содержимое всего массива после изменения первого элемента:');
d.Println; writeln();
d.Insert(d.Count-1, -8);
writeln('Содержимое всего массива после вставки элемента:');
d.Println; writeln();
// Удаление элемента
d.Remove(3);
writeln('Содержимое всего массива после удаления элемента:');
d.Println; writeln();
// Изменение размера с помощью метода
d.Resize(d.Count + 3);
writeln('Размер массива = ', d.Count); writeln();
// Изменение размера с помощью свойства
d.Count := d.Count - 1;
writeln('Размер массива = ', d.Count); writeln();
writeln('Содержимое всего массива:');
d.Println; writeln();
writeln('Емкость массива = ', d.Capacity);
// Увеличение емкости массива
d.Reserve(d.Capacity + 5);
writeln('Емкость массива после увеличения = ', d.Capacity);
// Попытка уменьшить емкость массива
d.Reserve(3);
writeln('Емкость массива после попытки уменьшения = ', d.Capacity); writeln();
// Вывод индекса искомого элемента массива
writeln('Индекс элемента 47 = ', d.Find(47));
writeln('Индекс элемента -54 = ', d.Find(54), ' (т.е. такого элемента в массиве нет)'); writeln();
// Обработка исключения при выходе за границы диапазона
try
d.Remove(d.Count + 3);
except
on e: Exception do
writeln(e);
end;
end.
SimpleSet
<xh4> Интерфейс </xh4>
Add(x: DataType) Добавляет элемент x во множество Remove(x: DataType) Удаляет элемент x из множества Contains(x: DataType): boolean Возвращает истину, если множество содержит элемент x
<xh4> Примеры использования </xh4>
uses Collections;
begin
// Создание нового объекта простого множества
var ss := new SimpleSet<integer>;
// Добавление элемента во множество
ss.Add(5); ss.Add(-32); ss.Add(-7); ss.Add(43);
// Вывод множества
writeln('Содержимое множества:');
ss.Println;
writeln();
// Проверка, содержится ли элемент во множестве
writeln('97 содержится во множестве: ', ss.Contains(97));
writeln('5 содержится во множестве: ', ss.Contains(5));
writeln();
// Удаление элемента из множества
ss.Remove(8);
ss.Remove(-32);
writeln('Содержимое множества после удаления элементов:');
ss.Println; writeln();
end.
AssocArray
<xh4> Интерфейс </xh4>
<xh4> Примеры использования </xh4>