end; {for i}
Вставка и удаление элемента в массив
Рассмотрим алгоритм вставки элемента в массив. Для простоты будем рассматривать только одномерные массивы. Массив состоит из некоторого количества элементов nmax (емкость
массива). Текущее количество элементов массива находится в переменной n.
Перед вставкой очередного элемента проверяем, что текущее количество элементов массива меньше, чем его емкость.
Далее проверяем, вставляется ли элемент в конец массива или нет. Если элемент вставляется в конец массива, то увеличиваем n на единицу и добавляем элемент. Иначе сдвигаем элементы массива индекс которых больше или равен индексу вставляемого элемента, рисунок 3.
Приведенный алгоритм реализован в программе, приведенной в листинге 6.
Листинг 6 – Вставка элемента в массив
{$MODE DELPHI} {$ENDIF}
{$APPTYPE CONSOLE} program InsElt;
i :integer;
//Ввод массива
//Элемент для вставки writeln("Vvedite element" ); readln(element);
//Индекс элемента
//Вставка элемента
if index < n+1 then begin
inc(n); //увеличиваем длину массива
if (Low(a) <= index) and (index <= n) then for i:=n downto index do
a[i]:=a; //сдвиг массива
a:=element; end
//Вывод элементов массива на экран for i:=1 to n do
writeln("a[" , i,"]=" , a[i]:6:2);
Удаление элемента происходит аналогично. Сначала проверяется, что индекс элемента не выходит за диапазон допустимых значений, а затем сдвигаются элементы таким образом, чтобы закрыть удаляемый элемент, рисунок 4
Листинг 7
{$MODE DELPHI} {$ENDIF}
{$APPTYPE CONSOLE} program DelElt;
const nmax = 5; //емкость массива
i :integer;
writeln("Vvedite chislo elementov massiva"); readln(n);
//Ввод массива
for i:=1 to n do begin write("a[" , i,"]=" ); readln(a[i]);
//Индекс элемента
writeln("Vvedite index elementa"); readln(index);
//Удаление элементов
if index if (Low(a) <= index) and (index <= n) then for i:=index to n do a[i]:=a;
//сдвиг массиваdec(n);
//уменьшаем длину массиваend
else begin writeln("Invalid index"
); readln; Теоретический материал
Самостоятельная работа
При объявлении массива мы определяем его максимальную размерность, которая в дальнейшем изменена быть не может. Однако с помощью вспомогательной переменной можно контролировать текущее количество элементов, которое не может быть больше максимального. Замечание
. В пространстве имен System.Collection реализована коллекция ArrayList - массив, динамически изменяющий свой размер. Мы будем рассматривать его позже. Пример
. Рассмотрим фрагмент программы: int a=new int ; for (int i=0; i<5;i++) a[i]:=i*i; В этом случае массив можно представить следующим образом: Так как во время описания был определен массив из 10 элементов, а заполнено только первые 5, то оставшиеся элементы будут заполнены нулями. Что значит удалить из одномерного массива элемент с номером 3? Удаление должно привести к физическому "уничтожению" элемента с номером 3 из массива, при этом общее количество элементов должно быть уменьшено. В этом понимании удаления элемента итоговый массив должен выглядеть следующем образом В общем случае, если мы хотим удалить элемент массива с номером k (всего в массиве n элементов, а последний элемент имеет индекс n-1), то нам необходимо произвести сдвиг элементов, начиная с k+1-го на одну позицию влево. Т.е. на k-ое место поставить k+1-й элемент, на место k+1 - k+2-й элемент, …, на место n-2 - n-1-й элемент. После чего значение n уменьшить на 1. В этом случае размерность массива не изменится, изменится лишь текущее количество элементов, и у нас создастся ощущение, что элемент с номером k удален. Рассмотрим данный алгоритм на примере: namespace ConsoleApplication static int Input () int a=new int[n]; for (int i = 0; i < n; ++i) Console.Write("a[{0}]= ", i); for (int i = 0; i < n; ++i) Console.Write("{0} ", a[i]); Console.WriteLine(); static void DeleteArray(int a, ref int n, int m) for (int i = m; i < n-1; ++i) static void Main() int myArray=Input(); int n=myArray.Length; Print(myArray, n); Console.WriteLine("Введите номер элемента для удаления:"); DeleteArray(myArray, ref n,m); Print(myArray, n); Задание
. Подумайте, какие исключительные ситуации могут возникнуть в данной программе и добавьте в нее соответствующие обработки исключительных ситуаций Рассмотрим теперь операцию удаления в двумерном массиве. Размерность двумерного массива также зафиксирована на этапе объявления массива. Однако при необходимости можно "смоделировать" удаление целой строки в массиве, выполняя сдвиг всех строк, начиная с k-той на единицу вверх. В этом случае размерность массива не изменится, а текущее количество строк будет уменьшено на единицу. В качестве примера удалим из двумерного массива, строку с номером k. namespace ConsoleApplication Console.WriteLine("введите размерность массива"); Console.Write("n = "); n=int.Parse(Console.ReadLine()); Console.Write("m = "); m=int.Parse(Console.ReadLine()); int [,]a=new int; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) for (int i = 0; i < n; ++i,Console.WriteLine()) for (int j = 0; j < m; ++j) static void DeleteArray(int[,] a, ref int n, int m, int k) for (int i = k; i < n-1; ++i) for (int j = 0; j < m; ++j) a = a; static void Main() Console.WriteLine("Исходный массив:"); Print(myArray, n, m); DeleteArray(myArray, ref n, m, k); Console.WriteLine("Измененный массив:"); Print(myArray, n, m); Задания
. Рассмотрим модификацию предыдущей программы, для случая, когда используется ступенчатый массив. namespace ConsoleApplication Console.WriteLine("введите размерность массива"); Console.Write("n = "); n=int.Parse(Console.ReadLine()); Console.Write("m = "); m=int.Parse(Console.ReadLine()); int a=new int[n]; for (int i = 0; i < n; ++i) a[i]=new int[m]; for (int j = 0; j < m; ++j) Console.Write("a[{0},{1}]= ", i, j); for (int i = 0; i < n; ++i,Console.WriteLine()) for (int j = 0; j < m; ++j) Console.Write("{0,5} ", a[i] [j]); static void DeleteArray(int a, ref int n, int k) for (int i = k; i < n-1; ++i)//производим сдвиг ссылок static void Main() Console.WriteLine("Исходный массив:"); Print(myArray, n, m); Console.WriteLine("Введите номер строки для удаления:"); int k=int.Parse(Console.ReadLine()); DeleteArray(myArray, ref n, k); Console.WriteLine("Измененный массив:"); Print(myArray, n, m); Вернемся к массиву, определенному в самом первом примере. И подумаем теперь, что значит добавить элемент в одномерный массив в позицию с номером k? В этом случае все элементы, начиная с k-ого, должны быть сдвинуты вправо на одну позицию. Однако сдвиг нужно начинать с конца, т.е. на первом шаге на n-е место поставить n-1-ый элемент, потом на n-1-ое место поставить n-2-й элемент, …, наконец, на k+1 место вставить k-й элемент. Таким образом, копия k-го элемента будет на k+1-м месте и на k-е место можно поставить новый элемент. Затем необходимо увеличить текущее количество элементов на 1. Рассмотрим массив из примера 1 и в качестве k зададим значение равное 3. В этом случае массив будет выглядеть следующим образом: Теперь в позицию с номером 3 можно поместить новое значение. А текущее количество элементов в массиве становится равным 6. Подумайте, почему сдвиг нужно выполнять с конца массива, а не с начала, как мы это делали в случае удаления элемента из массива. Рассмотрим программную реализацию данного алгоритма: namespace ConsoleApplication static int Input (out int n) Console.WriteLine("введите размерность массива"); n=int.Parse(Console.ReadLine()); int a=new int; //выделяем памяти больше чем требуется for (int i = 0; i < n; ++i) Console.Write("a[{0}]= ", i); a[i]=int.Parse(Console.ReadLine()); static void Print(int a, int n) for (int i = 0; i < n; ++i) Console.Write("{0} ", a[i]); Console.WriteLine(); static void AddArray(int a, ref int n, int m) for (int i = n; i >= m; --i) Console.WriteLine("Введите значение нового элемента"); a[m]=int.Parse(Console.ReadLine()); static void Main() int myArray=Input(out n); Console.WriteLine("Исходный массив:"); Print(myArray, n); Console.WriteLine("Введите номер элемента для вставки:"); AddArray(myArray, ref n,m); Console.WriteLine("Измененный массив:"); Print(myArray, n); Теперь рассмотрим добавление строки в двумерный массив. Для этого все строки после строки с номером k передвигаем на 1 строку вниз. Затем увеличиваем количество строк на 1. После этого копия строки с номером k будет находиться в столбце с номером k+1. И, следовательно, k-тый столбец можно заполнить новыми значениями. Рассмотрим программную реализацию алгоритма: namespace ConsoleApplication static int [,] Input (out int n, out int m) Console.WriteLine("введите размерность массива"); Console.Write("n = "); n=int.Parse(Console.ReadLine()); Console.Write("m = "); m=int.Parse(Console.ReadLine()); //выделяем памяти больше чем необходимо int [,]a=new int; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) Console.Write("a[{0},{1}]= ", i, j); a=int.Parse(Console.ReadLine()); static void Print(int[,] a, int n, int m) for (int i = 0; i < n; ++i,Console.WriteLine()) for (int j = 0; j < m; ++j) Console.Write("{0,5} ", a); static void AddArray(int[,] a, ref int n, int m, int k) for (int i = n; i >=k; --i) for (int j = 0; j < m; ++j) a = a; for (int j=0; j Console.Write("a[{0},{1}]=", k, j); a=int.Parse(Console.ReadLine()); static void Main() int[,] myArray=Input(out n, out m); Console.WriteLine("Исходный массив:"); Print(myArray, n, m); int k=int.Parse(Console.ReadLine()); Console.WriteLine("Измененный массив:"); Print(myArray, n, m); Задания
. Рассмотрим модификацию предыдущей программы для случая, когда используется ступенчатый массив. namespace ConsoleApplication static int Input (out int n, out int m) Console.WriteLine("введите размерность массива"); Console.Write("n = "); n=int.Parse(Console.ReadLine()); Console.Write("m = "); m=int.Parse(Console.ReadLine()); //выделяем памяти больше чем неообходимо int a=new int; for (int i = 0; i < n; ++i) a[i]=new int [m]; for (int j = 0; j < m; ++j) Console.Write("a[{0}][{1}]= ", i, j); a[i][j]=int.Parse(Console.ReadLine()); static void Print(int a, int n, int m) for (int i = 0; i < n; ++i,Console.WriteLine()) for (int j = 0; j < m; ++j) Console.Write("{0,5} ", a[i][j]); static void AddArray(int a, ref int n, int m, int k) for (int i = n; i >=k; --i)//выполняем сдвиг ссылок a[k]=new int[m]; //создаем новую строку Console.WriteLine("Введите элементы новой строки"); for (int j=0; j Console.Write("a[{0}][{1}]=", k, j); a[k][j]=int.Parse(Console.ReadLine()); static void Main() int myArray=Input(out n, out m); Console.WriteLine("Исходный массив:"); Print(myArray, n, m); Console.WriteLine("Введите номер строки для добавления:"); int k=int.Parse(Console.ReadLine()); AddArray(myArray, ref n, m, k); Console.WriteLine("Измененный массив:"); X[ 3 ] : =X [ 4 ]; X[ 4 ] : =X [ 5 ]; X[ 5 ] : =X [ 6 ]; Таким образом, все элементы с третьего по
пятый надо переместить влево на один - на место
i
-го элемента нужно записать (i+1)
-й. Блок-схема
алгоритма представлена на рис. 5.25 .
Теперь рассмотрим более общую задачу: необходимо удалить m
-й элемент из массива X
, состоящего из n
элементов. Для этого достаточно записать элемент (m+1)
-й на место
элемента c номером m, (m+2)
-й элемент - на место
(m+1)
-го и т. д., n
-й элемент - на место
(n–1)
-го. Процесс удаления элемента из массива представлен на рис. 5.26 . Алгоритм
удаления из массива Х
размерностью n
элемента с номером m
приведён на рис. 5.27 . После удаления
элемента 4А фактически сдвига части массива на один элемент влево
из массива изменится количество элементов в массиве (уменьшится на один), и у части элементов изменится индекс
. Если элемент удалён, то на место
него приходит следующий, передвигаться к которому (путём увеличения индекса на один) нет необходимости. Следующий элемент сам сдвинулся влево после удаления. Если обрабатывается массив
, в котором часть элементов удаляется, то после удаления элемента не надо переходить к следующему (при этом уменьшается количество элементов). В качестве примера рассмотрим следующую задачу. ЗАДАЧА 5.1. Удалить из массива отрицательные элементы. Алгоритм
решения задачи довольно прост: перебираем все элементы массива, если элемент отрицателен, то удаляем его путём сдвига всех последующих на один влево. Единственное, о чём стоить помнить, - что после удаления элемента не надо переходить к следующему для последующей обработки, он сам сдвигается на место
текущего. Блок-схема
решения задачи 5.1 представлена на рис. 5.28 . Ниже представлен текст программы с комментариями. program upor_massiv;
var i, n, j: byte; X: array [ 1.. 100 ] of real;
begin
writeln (’введите размер массива ’); readln (n);
{Ввод массива.}
for i:=1 to n do
begin
write (’X[ ’, i, ’ ]= ’);
readln (X[ i ]);
end;
writeln (’массив X ’);
for i:=1 to n do write (x [ i ] : 5: 2, ’ ’);
writeln;
i: = 1;
while (i<=n) do
{Если очередной элемент массива X[i] отрицателен, то}
if x [ i ]<0 then
begin
{удаляем элемент массива с номером i.}
for j:= i to n_1 do
x [ j ] : = x [ j + 1 ]; {Уменьшаем размер массива.}
{Не надо переходить к следующему элементу массива.}
n:=n -1;
end
else
{Если элемент не удалялся, то переходим к следующему элементу массива.}
i:= i +1;
writeln (’Изменённый массив ’);
for i:=1 to n do {Вывод преобразованного массива.}
write (X[ i ] : 5: 2, ’ ’); writeln; end. Результаты работы программы представлены на рис. 5.29 . Рассмотрим несложную задачу: вставить число b
в массив
X(10)
, между третьим и четвёртым элементами. Для решения этой задачи необходимо все элементы массива, начиная со четвёртого, сдвинуть вправо на один элемент. Затем в четвёртый элемент массива нужно будет записать b (X:=b;)
. Но чтобы не потерять соседнее значение
, сдвигать на один вправо нужно сначала десятый элемент, затем девятый, восьмой и т. д. до четвёртого. Блок-схема
алгоритма вставки приведена на рис. 5.30 . В общем случае блок-схема
вставки числа b
в массив
X(N)
, между элементами c номерами m
и m+1
представлена на рис. 5.31 . Ниже представлен фрагмент программы, реализующий этот
алгоритм 5При описании массива необходимо предусмотреть достаточный размер для вставки одного элемента.
. var i, n,m: byte;
X: array [ 1.. 100 ] of real;
b: real;
begin
writeln (’N= ’);
readln (n);
for i:=1 to n do
begin
write (’X[ ’, i, ’ ]= ’);
readln (X[ i ]);
end;
writeln (’Массив X ’);
for i:=1 to n do write (x [ i ] : 5: 2, ’ ’);
writeln;
writeln (’m= ’);
readln (m);
writeln (’ b= ’);
readln (b);
for i:=n downto m+1 do
x [ i +1]:=x [ i ];
x :=b;
n:=n+1;
writeln (’Изменённый массив ’);
for i:=1 to n do
write (X[ i ] : 5: 2, ’ ’);
writeln;
end. Рассмотрим, как можно передавать массивы в подпрограмму. Как известно (см. главу 4), чтобы объявить переменные в списке формальных параметров подпрограммы, необходимо указать их имена и типы. Однако типом любого параметра в списке может быть только стандартный или ранее объявленный тип. Поэтому для того, чтобы передать в подпрограмму массив
, необходимо вначале описать его
тип 6Тип данных массива, объявление массива см. в п. 2.4.9. Подробно работа с массивами описана в данной главе.
, а затем объявлять процедуру: тип_массива = array
[ список_индексов ] of
тип; procedure
имя_процедуры(имя_массива: тип_массива); Например: type
vector=array [ 1.. 10 ] of byte;
matrica=array [ 1.. 3, 1.. 3 ] of real;
procedure proc (A: matrica; b: vector; var x: vector); Понятно, что передача в подпрограмму строки вида имя_переменной: string
[ длина_строки ]; которая фактически является
массивом 7Тип данных "строка", объявление строки см. в п. 2.4.9
, должна осуществляться аналогично: тип_строки = string
[ длина_строки ]; procedure
имя_процедуры(имя_строки: тип_ строки); Например: type
stroka_5=string [ 5 ];
stroka_10=string [ 1 0 ];
function fun (S t r: stroka_5) : stroka_10; Массивы в подпрограмму можно передавать, используя понятие открытого массива. Открытый массив
- это
массив 8Тип данных "массив", объявление массива, обращение к массиву см. в п. 2.4.9.
, при описании которого указывается тип элементов, из которых он состоит, но не определяются границы изменения индексов: имя_открытого_массива: array of array of...
тип; Например: var
massiv_1: array of real;
massiv_2: array of array of char;
massiv_3: array of array of array of byte; Распределение памяти
и указание границ индексов Основным достоинством массива является прямой доступ
к его элементам: для использования элемента нужно указать только имя массива и индекс (или индексы), которые преобразуются в физический адрес элемента. Скорость доступа не зависит от положения элемента в структуре. Недостаток связан с операциями вставки и удаления элементов. Допустим, одномерный массив arrTable используется для хранения в своих элементах полезной информации, причем содержат информацию только начальные элементы, число которых равно Count. Эти «занятые» элементы называются активными
, активные элементы имеют индексы в диапазоне . Очевидно, LastIndex = Count - 1. Если, например, в массив нужно вставить новую информацию в элемент с индексом ind, то все элементы с индексами, начиная с ind и до конца активной части, потребуется переместить на одну позицию, чтобы освободить место под вставляемый элемент NewElement. Эта операция может быть описана следующим фрагментом: For
i:= LastIndex DownTo
indDo
arrTable := arrTable [i]; arrTable := NewElement; Inc(Count); Inc(LastIndex); Сдвиг части элементов означает их физическое перемещение в памяти. Логическая схема операции вставки показана на рисунке 5.4 Рисунок 5.4 - Вставка в вектор нового элемента: а
- до вставки, б
- после вставки Объем памяти, который будет затронут при вставке нового элемента, зависит от значения n и количества сдвигаемых элементов. Время, требуемое на выполнение вставки, зависит от числа активных элементов в массиве: чем больше это количество, тем больше (в среднем) потребуется времени на сдвиг. Тот же ход рассуждений справедлив и для операции удаления активного элемента из вектора. В случае удаления элемента с индексом ind, все элементы, начиная с элемента arrTable, должны быть перенесены на одну позицию к началу вектора, чтобы «закрыть» образовавшуюся от удаления элемента «дыру». Логическая схема операции удаления приводится на рисунке 5.5. Программный фрагмент удаления может иметь вид: For
i:= ind + 1 To
LastIndexDo
arrTable := arrTable [i]; Dec(Count); Dec(LastIndex); Таким образом, можно сделать вывод: операции вставки и удаления в массиве выполняются медленнее при увеличении количества элементов. Другой важный недостаток массива связан с фиксацией его размеров. Если необходимо вставить новый элемент в статический массив, который полностью заполнен активными элементами, то произойдет ошибка времени выполнения. Решением проблемы является использование динамического массива, однако приходится все время контролировать текущее число элементов и применять процедуру SetLength при вставке в полностью заполненный массив. n=5
а
k=3
а
Рис.
5.25.
Рис.
5.26.
Рис.
5.27.
Рис.
5.28.
Рис.
5.29.
5.9 Вставка элемента в массив
Рис.
5.30.
Рис.
5.31.
5.10 Использование подпрограмм для работы с массивами
Вставка и удаление в массиве
Значение слова неудачный
Обзор Samsung Galaxy A7 (2017): не боится воды и экономии Стоит ли покупать samsung a7
Делаем бэкап прошивки на андроиде
Как настроить файл подкачки?
Установка режима совместимости в Windows