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

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

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

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

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

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

begin . var a: array 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:=Arr(1,2,3);// по правой части - integer

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]

Но! Если теперь переприсвоить значение элементов массива b , то изменится и массив a :

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

Для того, чтобы избежать данной ситуации, необходимо создать массив b , как копию массива a :

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

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

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

var a: array of integer; a:=new integer[4]; . a:=new integer[5];

В результате возникают так называемые участки «утекшей» памяти (неиспользуемой). Постепенно произойдет переполнение памяти. В платформе .net используется автоматический сборщик мусора.

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

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

1. Цикл for

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.

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

function IndexOf<T>(a:array of T;x:T):integer; begin . end; begin var a:=Arr(1,2,3,4,5); print(IndexOf(a,5)) end.

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

1. Автовыведение типа Т, сравнение с реальными цифрами, и т.к. числа целые, то Т определится как integer.
2. Берется тело функции и заменяется Т на integer (инстанцирование функции с конкретным типом)

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

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)

Если сдвиг вправо:

1. либо задействовать еще один массив (𝜭 (n-k) — по времени)
2. либо много раз запускать один и тот же алгоритм (𝜭 (1) — по памяти)

Срезы

• Срезы доступны только на чтение, присваивать им значения нельзя.
• Тип среза такой же, как у массива.
• Срезы работают с массивами, строками и со списками.

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

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

println(a[:5]); // [1,2,3,4,5] - с начала до 5-го не включая println(a[1:]); // [2,3,4,5,6] - до конца println(a[::2]); // [1,3,5] - третий параметр - это шаг

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

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

var a:=Arr(1,2,3,4,5,6); var k:=a.Length-1; // 6 - 1 a:=a[k:]+a[:k]; print(a) // [6,1,2,3,4,5]

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

Время работы алгоритма n+n , 𝜭 (n)

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

Для расширения массива путем вставки какого-либо элемента, необходимо предусмотреть место в памяти. По этой причине для данных случаев проще использовать списки: Списки — 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.

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

procedure PrintArr( a: array of integer; delim:string:='; '); begin foreach var . in . do print(x,delim); end; begin var a:=new integer[10]; a:=arrRandomInteger(10); . end.

1. Функция MakeOddArrFunc с одним параметром N , возвращающая массив.
2. Процедура MakeOddArrProc с двумя параметрами: входным — массив a и выходным параметром — массивом положительный нечетных чисел

function MakeOddArrFunc (a: array of integer; n:integer):array of integer; begin var b:= new integer[n]; var j:=0; for var i:=0 to . do if . then begin . ;. ;end; SetLength(. ); result:=b; end; procedure MakeOddArrProc (a: array of integer;var b: array of integer; n:integer); begin b:= new integer[n]; var j:=0; for var i:=0 to . do if . then begin . ;. ;end; SetLength(. ); end; begin var a:=arrRandomInteger(20); var b: array of integer; var n:=readInteger('введите N'); println('исходный массив ',a); println('результат работы с функцией ',MakeOddArrFunc(a,n)); MakeOddArrProc(a,b,n); print('результат работы с процедурой ',b) end.

function MakeFibArr (n : integer):array of integer; begin var c:= new integer[n]; c[0]:=. ;c[1]:=. ; for var i:=2 to n-1 do . ; result:=c; end; begin var n:= readinteger; . ; 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<=a.Length-1 do begin a[j]:=0;j+=2; end; println('результирующий массив: ',a); end; begin var a:=arrRandomInteger(10); println('исходный массив: ',a); SetToZeroOddIndexes(a); end.

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

Выполнение:

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);