Динамические массивы

Описание динамического массива

Тип динамического массива конструируется следующим образом:

array of тип элементов (одномерный массив)
array [,] of тип элементов (двумерный массив)
и т.д.

Переменная типа динамический массив представляет собой ссылку. Поэтому динамический массив нуждается в инициализации (выделении памяти под элементы).

Выделение памяти под динамический массив

Для выделения памяти под динамический массив используется два способа. Первый способ использует операцию new в стиле вызова конструктора класса:

Данный способ хорош тем, что позволяет совместить описание массива и выделение под него памяти:

Второй способ выделения памяти под динамический массив использует стандартную процедуру SetLength :

Элементы массива при этом заполняются значениями по умолчанию.

Процедура SetLength обладает тем преимуществом, что при ее повторном вызове старое содержимое массива сохраняется.

Инициализация динамического массива

Можно инициализировать динамический массив при выделении под него память операцией new:

Инициализацию динамического массива в момент описания можно проводить в сокращенной форме:

При этом происходит выделение памяти под указанное справа количество элементов.

Инициализация одномерного массива проще всего осуществляется стандартными функциями Seq. которые выделяют память нужного размера и заполняют массив указанными значениями:

var a := Arr(1,3,5,7,8); // array of integer
var s := Arr(‘Иванов’,’Петров’,’Сидоров’); // array of string
var b := ArrFill(777,5); // b = [777,777,777,777,777]
var r := ArrRandom(10); // заполнение 10 случайными целыми в диапазоне от 0 до 99

В таком же стиле можно инициализировать массивы массивов:

var a := Arr(Arr(1,3,5),Arr(7,8),Arr(5,6)); // array of array of integer

Длина динамического массива

Динамический массив помнит свою длину (n-мерный динамический массив помнит длину по каждой размерности). Длина массива (количество элементов в нем) возвращается стандартной функцией Length или свойством Length :

Для многомерных массивов длина по каждой размерности возвращается стандартной функцией Length с двумя параметрами или методом GetLength(i) :

Ввод динамического массива

После выделения памяти ввод динамического массива можно осуществлять традиционно в цикле:

for var i:=0 to a.Length-1 do
read(a[i]);

Ввод динамического массива можно осуществлять с помощью стандартной функции ReadSeqInteger:

var a := ReadSeqInteger(10);

При этом под динамический массив выделяется память нужного размера.

Вывод динамического массива

Процедура write выводит динамический массив, заключая элементы в квадратные скобки и разделяя их запятыми:

var a := Arr(1,3,5,7,9);
writeln(a); // [1,3,5,7,9]

n-мерный динамический массив выводится так, что каждая размерность заключается в квадратные скобки:.

var m := new integer[3,3] ((1,2,3),(4,5,6),(7,8,9));
writeln(m); // [[1,2,3],[4,5,6],[7,8,9]]

Динамический массив можно выводить также методом расширения Print или Println:

При этом элементы по умолчанию разделяются пробелами, но можно это изменить, задав параметр Print, являющийся разделителем элементов. Например:

выводит каждый элемент на отдельной строке.

Массивы массивов

Если объявлен массив массивов

то его инициализацию можно провести только с помощью SetLength :

Для инициализации такого массива с помощью new следует ввести имя типа для array of integer :

type IntArray = array of integer;
var с: array of IntArray;
.
c := new IntArray[5];
for i := 0 to 4 do
c[i] := new integer[3];

Инициализацию массива массивов можно также проводить в сокращенной форме:

Присваивание динамических массивов

Динамические массивы одного типа можно присваивать друг другу, при этом обе переменные-ссылки будут указывать на одну память:

Следует обратить внимание, что для динамических массивов принята структурная эквивалентность типов: можно присваивать друг другу и передавать в качестве параметров подпрограмм динамические массивы, совпадающие по структуре.

Чтобы одному динамическому массиву присвоить копию другого массива, следует воспользоваться стандартной функцией Copy :

Передача динамического массива в подпрограмму

Динамический массив обычно передается в подпрограмму по значению, т.к. сама переменная уже является ссылкой:

procedure Squares(a: array of integer);
begin
for var i:=0 to a.Length-1 do
a[i] := Sqr(a[i]);
end;

begin
var a := Arr(1,3,5,7,9);
Squares(a);
end.

Динамический массив передается по ссылке только в одном случае: если он создается или пересоздается внутри подпрограммы. В частности, это необходимо делать если для динамического масива внутри подпрограммы вызывается SetLength:

procedure Add(var a: array of integer; x: integer);
begin
SetLength(a,a.Length+1);
a[a.Length-1] := x;
end;

begin
var a := Arr(1,3,5,7,9);
Add(a,666);
writeln(a);
end.

Источник

Настоящий динамический массив на Turbo Pascal

Доброго времени суток!

Если вы студент и вам надо срочно скатать — листайте вниз к программе

Данная тема не имеет ничего общего с реальностью, ведь язык Pascal никем не воспринимается всерьез, тем более Turbo Pascal. Однако он еще используется в обучающих целях в ВУЗах. И сегодня после написания лабораторки я обнаружил, что про динамический массив в интернете информации очень мало — не нашел ничего. (а надо было очень сильно)

Что необходимо знать

Тип Pointer предназначен для адреса ячейки памяти. Часто указатели используются для работы с динамической областью памяти, называемой кучей. Про устройство памяти в MS DOS(В которой работает Turbo Pascal ) можно почитать отдельно.

Для работы с динамической памятью в TP используются следующие процедуры (из тех, что нам нужны).

Рассмотрим программу

В var мы создаем ссылку на переменную типа integer. Мы пока не выделили память под переменную типа integer, а выделили под адрес. Переходим к основной программе. Теперь выделяем память именно под переменную. Чтобы обратиться к значению переменной, надо использовать операцию разыменования (^). Чтобы проиллюстрировать работу, присвоим ей некоторое значение, а затем напечатаем ее значение, умноженное на два. После работы необходимо освободить память(она сама освободиться после завершения программы, но продемонстрировать работу все же надо).

Процедуры GetMem и FreeMem позволяют выделить память начиная с указанной ячейки, размером N байт, аналогично FreeMem освобождает N байт начиная с указанного адреса

Теперь можно наконец-то к True динамическим массивам. В интернете нет подобных примеров, везде предлагается примерно следующий вариант:

создадим массив из N (1-10 тысяч элементов в надежде, что элементов будет меньше), состоящий из указателей, затем нужному количеству адресов выделяется память под переменные (при помощи New() ).

У многих тут возникает вопрос: «А че? Всеж нормально, динамический» — нет. Вы сразу выделяете память под 10 000 адресов* (к слову у вас вряд ли то выйдет без дополнительных ухищрений), а это и так занимает много места, спрашивается – зачем?

А теперь все же покажу реализацию

Давайте попробую объяснить, что тут происходит

Для начала определим наши типы, надеюсь тут все понятно. Напишем две функции. В них при помощи некоторой магии реализуем последовательный доступ к памяти. А конкретнее: параметр pa это указатель на тип ElemType. В данном случае это integer – 2 байта. То есть, если мы возьмем следующий за ним указатель, то он будет через 2 байта. Следующий указатель мы можем получить при помощи процедуры inc(). Это та самая маленькая магия, про которую многие не слышали, и я не нашел упоминания об этой возможности языка. Это тот самый последовательный доступ. А теперь дело за малым, мы перематываем i-1 раз и получаем адрес, по которому мы можем получить i-тый элемент массива. Для функции setI устанавливаем значение, а для getI возвращаем значение. Не забываем про операцию разыменование.

С описанием типов и процедур закончили и переходим к var, тут берем две переменные (подписаны в программе) word и один единственный указатель. Как видим у нас нет почти ограничений на размер массива – максимальное значение переменной N и максимальный размер кучи (64 Кбайт).

Основная программа

Введем какое-то N – длину массива, и выделяем под него память при помощи процедуры GetMem. Математика простая, нам нужно n элементов по m байт(m это размер переменной типа ElemType). Далее простой пример работы с данными, используя вышеописанных функций. И в конце очищаем память, руководствуясь той же логикой, что и при выделении памяти.

Источник

Динамический или статический?

Традиционно в языке Паскаль используются статические массивы вида

Границы массива обязательно задаются константами, и изменить размер массива в ходе работы программы нельзя. Зато можно сделать индекс не только целого, но и, скажем, символьного или перечислимого типа. Например, для подсчета встречаемости каждой буквы можно использовать массив

и работать с ним в свое удовольствие:

Недостатки таких массивов известны: если заранее неизвестно, сколько элементов потребуется использовать, то под массив отводится память максимального размера. В итоге в большинстве случаев мы «запасаемся впрок», а иногда и этого «запаса» оказывается недостаточно. Именно поэтому такие массивы называются статическими: их размер статичен и должен быть задан на этапе компиляции программы.

В Delphi Object Pascal появились динамические массивы, размер которых можно не только задавать, но и менять по ходу работы программы. Именно об этих массивах и о преимуществах их использования пойдет речь далее.

Описываются они предельно просто:

Чтобы задать размер такого массива, следует вызвать процедуру SetLength:

Как мы видим, размер такого массива может быть задан переменной, которая вычисляется по ходу работы програмы (в данном случае ее значение вводится).

Чтобы определить размер динамического массива, следует вызвать функцию Length: Length(a) возвращает размер динамического массива.

Динамические массивы представляются в памяти ссылками. Это означает, что любая переменная типа «динамический массив» является указателем на непрерывный участок динамической памяти. Первоначально этот указатель хранит nil, а вызов SetLength(a) выделяет под данные массива блок динамической памяти и записывает в a адрес этого блока памяти.

Во-вторых, при присваивании динамических массивов обе пременные b1 и b2 указывают на один участок динамической памяти, поэтому изменение элемента в массиве b1 приводит и к изменению массива b2:

Еще в Delphi имеются так называемые открытые массивы. К сожалению, они по внешнему виду очень похожи на динамические:

Смысл в том, что при вызове на место открытого массива можно подставлять статический массив любого размера. Но запись array of integer используется в совершенно другом смысле! Поэтому мы полностью отказались от открытых массивов в PascalABC.NET. Пользуйтесь динамическими массивами!

Посмотрим теперь, что нового появилось в динамических массивах в PascalABC.NET.

1. Динамические массивы можно инициализировать при описании:

2. Выделять память под динамическе массивовы можно с помощью операции new:

3. Как мы упомянули, динамический массив в PascalABC.NET является классом, а значит, он имеет методы и свойства:

5. Ввиду структурной эквивалентности типов для динамических массивов их можно передавать в подпрограмму следующим образом:

Напомним, что открытые массивы в PascalABC.NET отсутствуют!

6. Для динамических массивов (в отличие от статических) можно использовать цикл foreach (при условии, что мы осуществляем доступ к элементам только на чтение):

И, наконец, скажем несколько слов про двумерные динамические массивы. Они моделируются как массивы массивов.

Следующий код иллюстрирует создание двумерного динамического массива размера m на n:

Источник

Занятие 5. Pascal abc.net: Динамические массивы

Объявление, выделение памяти

Обычно в языке Паскаль используются статические массивы вида:

var mas: array [1..10] of integer;

Границы статического массива изменить в ходе программы нельзя, так как они задаются в разделе объявлений «раз и навсегда».
Основным недостатком такого массива является то, что в случае, когда заранее не известно количество элементов массива, то приходится выделять память максимального размера, что называется «на всякий случай».

Рассмотрим работу с динамическим массивом.

Объявляется динамический массив в теле программы:

Или объявление с инициализацией:

А выделение памяти и размер такого массива задается уже по ходу программы:

var a: array of integer; var n:=readInteger; a:=new integer[n];

var a: array of integer; a:=new integer[readInteger];

var a: array of integer; var n:=readInteger; SetLength(a,n); // устанавливаем размер массива а

Ссылочная объектная модель: память выделяется служебным словом NEW

var a := new integer[5];

Организация памяти для массива a

Инициализация, присваивание и вывод

Возможна инициализация динамического массива при описании:

var a: array of integer := (1,2,3);

Новые способы заполнения массива (заполнители):

var a:=ArrFill(5,2); // 2 2 2 2 2

var a:=ReadArrInteger(5); var a:=ReadArrReal(5);

Заполнение случайными числами:

var a:=new integer[10]; a:=arrRandomInteger(10);

Или с разделителем между элементами:

Переприсваивание:

var a: array of integer := (1,2,3); var b:=a; // [1,2,3]

var a: array of integer := (1,2,3); var b:=a; b[2]:=1; print(a); //[1,2,1]

var a: array of integer := (1,2,3); var b:=Copy(a); b[2]:=1; print(a); //[1,2,3]

Очистка динамического массива

Если в программе случайно создается повторно один и тот же массив:

Но можно очистить память и принудительно:

В процессе очистки выполнение программы и всех процессов приостанавливается. По этой причине сборщик мусора в системах реального времени не используется.

Работа с элементами массива

for var i:=0 to High(a) do print(a[i]);;

foreach var x in a do print(x);

High(массив) — возвращает верхнюю границу динамического массива

Примеры работы с динамическими массивами

Выполнение:
Выполним сначала БЕЗ использования обобщенной функции:

function IndexOf(a:array of integer;x:integer):integer; begin result:=-1; for var i:=0 to High(a) do if a[i]=x then begin result:=i; break end end; begin var a:=Arr(1,2,3,4,5); print(IndexOf(a,5)) end.

А теперь, выполним с использованием обобщенной функции:

При вызове обобщенной функции компиляция будет в два этапа:

Методы для работы с массивами

var a:=Arr(1,2,3,4,5); reverse(a); // [5,4,3,2,1]

var a:=Arr(2,3,1,4,5); //[1,2,3,4,5] sort(a);

Следующие методы не меняют сам массив:
a.Min
a.Max
a.Sum
a.Average — среднее арифметическое

Сдвиги

Стандартное выполнение:

var a:=Arr(1,2,3,4,5,6); var x:=a[0]; for var i:=0 to 4 do a[i]:=a[i+1]; a[5]:=x; print(a)

Срезы

var a:=Arr(1,2,3,4,5,6); print(a[1:5]) // [2,3,4,5]

a[1:5] — 1-й элемент включая, 5-й не включая

a[::-1] — получим 6 5 4 3 2 1

Т.о. выполнение при помощи срезов выглядит так:
Перестановка:

Т.е. создан еще массив уже со сдвигом.

Удаление и вставка элементов массива. Списки

Для расширения массива путем вставки какого-либо элемента, необходимо предусмотреть место в памяти. По этой причине для данных случаев проще использовать списки:
Списки — List — это тоже динамический массив, который может «расширяться» и «сужаться» по ходу программы (вставка и удаление элементов).
…

Решение задач

Простые задачи

Выполнение:

function SumArray(var a: array of integer): integer:=a.Sum; begin var a:=new integer[10]; a:=arrRandomInteger(10); foreach var x in a do print(x); println(‘длина массива = ‘,a.Length,’ сумма = ‘,ArraySum(a)) end.

Выполнение:
Дополните код:

Выполнение:

function MakeRandomRealArr (n : integer;a,b:real):array of real; begin var c:= ArrRandomReal(n,a,b); result:=c; end; begin var n:= readinteger; var a:=readReal; var b:=readReal; println(‘результат работы с функцией ‘,MakeRandomRealArr(n,a,b)); end.

Выполнение:

procedure SetToZeroOddIndexes(a: array of integer); begin var j:=0; while j FirstLocMin ).
Пояснение: локальным минимумом считается тот элемент, который меньше каждого из своих соседей. Считать, что локальный минимум в массиве есть. Первый и последний элемент в качестве локальных минимумов не рассматривать.

Задачи на срезы

Условный оператор не использовать.

Выполнение:

var n:=ReadInteger; var a:=ReadArrReal(n); var k:=ReadInteger; a[k-1 : : k].Print;

Условный оператор не использовать.

Условный оператор не использовать.

Условный оператор не использовать

Выполнение:

var n:=ReadInteger; var a:=ReadArrReal(n); var srez:=a[1::2]+a[::2]; Print(srez);

Условный оператор не использовать

Выполнение:

var n:=ReadInteger; var a:=ReadArrReal(n); var k:=ReadInteger; var l:=ReadInteger; var srez:=a[k-1:l].Average; print(srez);

Выполнение:

var n:=ReadInteger; var a:=ReadArrReal(n); print(a[1::2].min);

Источник

Массивы в PascalABC.NET

В PascalABC.NET рекомендуется использовать динамические массивы. В отличие от статических, они имеют огромное количество методов и операций, просты в создании, заполнении и выводе.

Описание и выделение памяти

Динамический массив описывается так:

Память под динамический массив a выделяется в момент работы программы:

Индексация в динамических массивах и использование статических массивов

Простейшее заполнение

Важную роль играют функции заполнения динамических массивов. Перед заполнением они выделяют для массива память, поэтому в одной строке можно совмещать описание, выделение памяти и заполнение.

Заполнение диапазоном целых или символьных значений делается с использованием функции Arr:

Заполнение определённым значением осуществляется с помощью операции умножения массива на число:

Для заполнения можно также использовать функцию ArrFill:

Для заполнения массива случайными значениями следует использовать

Не рекомендуется использовать алгоритм для заполнения массива случайными в каждой задаче:

Ввод и вывод элементов массива

Для ввода элементов массива базовых типов используются функции

Стандартная процедура вывода Write или Print выводит значения в массиве в квадратных скобках черезх запятую:

Однако лучше всего для вывода воспользоваться методом Print, выводящим все значения в массиве через пробел:

Не рекомендуется вводить и выводить элементы массива в цикле

Циклы по массиву

Для обработки элементов массива используются следующие циклы:

Пример. Найти количество чётных элементов, стоящих на чётных местах

Методы массива

Массивы содержат большое количество стандартных методов:

Кроме того, доступны процедуры

Методика. Обращаем внимание, что в методических целях естественно рассказывать, как эти алгоритмы устроены “внутри”. Но потом следует пользоваться стандартными алгоритмами, а не заставлять учеников во всех задачах использовать рукописные сортировки или рукописный поиск минимума. Например, рекомендуется показать, как накопить сумму элементов массива:

Здесь следует обратить внимание, что этот алгоритм может быть легко модифицирован в алгоритм нахождения суммы элементов по условию: например, всех чётных элементов:

Если условие надо накладывать на индексы, то в этом случае (и только в этом случае) следует использовать цикл for по индексам:

Для нахождения суммы без условия необходимо использовать стандартный метод a.Sum:

Отметим также, что для поиска суммы по условию также имеется короткая однострочная запись. Она требует использование стандартного метода Where с параметром, являющимся лямбда-выражением. Лямбда-выражения мы будем рассматривать далее:

Методика. Поскольку данная запись использована здесь впервые, обращаем внимание на её высокую универсальность: алгоритмы фильтрации и поиска суммы не слиты в один алгоритм, а используются порознь один за другим, что позволяет:

Далее лямбда-выражения объясняются подробно и тщательно и используются повсеместно.

Операции с массивами

Изменение размера динамического массива

Для первоначального заполнения списков List используется короткая фунеция Lst:

Большинство методов, которые имеются в массивах, есть и в списках List. Поэтому выбор типа List или array of для контейнера при решении задач определяется тем, будет ли данный контейнер расширяться по ходу работы программы.

Источник