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

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск
 
(не показано 6 промежуточных версий этого же участника)
Строка 1: Строка 1:
 +
[[Категория:Collections]]
 
== Интерфейс ==
 
== Интерфейс ==
 
<source lang="Delphi">
 
<source lang="Delphi">
type DynArray<T> = class
+
type DynArray<DataType> = class
 
   /// Количество элементов (размер) массива
 
   /// Количество элементов (размер) массива
 
   property Count: integer;
 
   property Count: integer;
Строка 46: Строка 47:
 
== Реализация ==
 
== Реализация ==
 
<source lang="Delphi">
 
<source lang="Delphi">
 +
interface
 +
 +
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;
 +
 +
implementation
 +
 +
// ---------------------------- Стандартные методы ---------------------------
 +
{Создает массив размера 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;
 +
  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;
  
 
</source>
 
</source>
  
 
== Примеры использования ==
 
== Примеры использования ==
 +
<source lang="Delphi">
 +
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.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.
 +
</source>
  
 
== См. также ==
 
== См. также ==
[[Unit Collections | Collections]]:
+
[[Unit Collections | Collections]] (полный текст модуля):
  
*[[Unit Collections: Stack | Stack]]
+
* [[Unit Collections: Stack | Stack]]
*[[Unit Collections: Queue | Queue]]
+
* [[Unit Collections: Queue | Queue]]
*[[Unit Collections: SimpleSet | SimpleSet]]
+
* [[Unit Collections: SimpleSet | SimpleSet]]
*[[Unit Collections: AssocArray | AssocArray]]
+
* [[Unit Collections: AssocArray | AssocArray]]
 +
* [[Unit Collections: LinkedList | LinkedList]]

Текущая версия на 11:52, 9 мая 2009

Интерфейс

type DynArray<DataType> = class
  /// Количество элементов (размер) массива
  property Count: integer;

  /// Емкость массива (отведенная память)
  property Capacity: integer;

  /// Позволяет обращаться к элементам массива по индексу 
  /// (например, apples[5])
  property Elem[index: integer]: DataType;


  /// Создает массив размера pSize
  constructor Create(pSize: integer := 0);
 
  /// Выделяет новую память. Емкость увеличивается до newCap.
  /// (Если newCap меньше текущей емкости, ничего не происходит) 
  procedure Reserve(newCap: integer);

  /// Устанавливает новый размер массива равным newSize
  procedure Resize(newSize: integer);
 
  /// Добавляет элемент x в конец массива 
  procedure Add(x: DataType);

  /// Вставляет элемент x в позицию pos
  procedure Insert(pos: integer; x: DataType);

  /// Удаляет элемент массива из позиции pos
  procedure Remove(pos: integer);
 
  /// Возвращает индекс первого элемента массива равного x
  /// или -1, если такого элемента нет
  function Find(x: DataType): integer;
 
  /// Выводит содержимое массива на консоль
  procedure Println();

  /// Выводит содержимое массива на консоль в обратном порядке
  procedure PrintlnReverse();
end;

Реализация

interface

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;

implementation

// ---------------------------- Стандартные методы ---------------------------
{Создает массив размера 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;
  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;

Примеры использования

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.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.

См. также

Collections (полный текст модуля):