Вставка и удаление элемента в массив.
Вставка и удаление в массиве
Основным достоинством массива является прямой доступ к его элементам: для использования элемента нужно указать только имя массива и индекс (или индексы), которые преобразуются в физический адрес элемента. Скорость доступа не зависит от положения элемента в структуре.
Недостаток связан с операциями вставки и удаления элементов. Допустим, одномерный массив 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 при вставке в полностью заполненный массив.
Когда нужно произвести какие-то изменения в массиве, метод JavaScript splice может прийти на помощь. Он позволяет осуществлять вставку, удаление и замену элементов в массиве JavaScript .
Рассмотрим аргументы, передаваемые в метод splice() .
Array.splice (start_index, number_of_elements_to_remove) :
- start_index — индекс в массиве, с которого начинается вставка или удаление элементов;
- number_of_elements_to_remove — задает количество элементов, которое необходимо удалить, начиная со star_index .
Все элементы, следующие за number_of_elements_to_remove , будут вставлены в массив, начиная с start_index . Они могут быть любого типа, включая строки, числа, булевы значения, объекты, функции, NULL , undefined , и т.д.
Для более детального изучения параметров метода Array.prototype.splice() Javascript воспользуйтесь MDN .
Давайте начнем с простого примера, демонстрирующего, как вставить число в массив с помощью метода Array.splice() .
Представьте, что у нас есть массив , и мы хотим вставить в него 2 между 1 и 3 . Пример реализации:
var my_array = ; var start_index = 1; var number_of_elements_to_remove = 0; my_array.splice(start_index, number_of_elements_to_remove, 2); console.log(my_array); //;
Обратите внимание, что JavaScript array splice воздействует непосредственно на массив. Таким образом, вызванный my_array метод splace() вместо того, чтобы вернуть новый массив, обновит my_array .
Пример удаления элемента из массива в JavaScript :
var my_array = ["a","b","c","k","d"]; var start_index = 3 var number_of_elements_to_remove = 1; var removed_elements = my_array.splice(start_index, number_of_elements_to_remove); console.log(removed_elements); //["k"] console.log(my_array); //["a","b","c","d"];
Обратите внимание, что в этом примере метод Array.splice() возвращает массив из удаленных элементов.
Взглянем на пример замены элементов в массиве JavaScript с помощью метода splice JavaScript :
var my_array = ["бейсбол", "баскетбол", "теннис", "гольф"]; var start_index = 1 var number_of_elements_to_remove = 2; var removed_elements = my_array.splice(start_index, number_of_elements_to_remove, "бокс", "боулоинг", "волейбол"); console.log(removed_elements); //["теннис", "гольф"] console.log(my_array); //["бейсбол", "бокс", "боулинг", "волейбол", "гольф"];
Приведенный выше пример заменяет «баскетбол » и «теннис » на «бокс «, «боулинг » и «волейбол «. Он может показаться немного запутанным из-за всех проведенных операций. Разберем все операции шаг за шагом. Для начала мы сообщаем методу splace() начальную позицию my_array . Затем number_of_elements_to_remove задаем 2, поэтому метод удаляет my_array и my_array . И, наконец, начиная со start_index my_array , вставляем в массив my_array элементы.
Метод JavaScript splace хорош, когда нужно вставить или удалить значения из массива t . Если массив уже отсортирован, метод splace() подходит, чтобы явно расположить новые значения в массиве. Он также хорошо работает, когда нужно удалить значения из массива по индексу. Обратите внимание на то, что метод splace() действует непосредственно на массив и возвращает только те значения, которые были удалены или вырезаны из массива.
Перевод статьи “Insert, Remove, and Replace elements with Array.splice() ” был подготовлен дружной командой проекта .
Хорошо Плохо
место пятого - шестой.X[ 3 ] : =X [ 4 ];
X[ 4 ] : =X [ 5 ];
X[ 5 ] : =X [ 6 ];
Таким образом, все элементы с третьего по пятый надо переместить влево на один - на место i -го элемента нужно записать (i+1) -й. Блок-схема алгоритма представлена на рис. 5.25 .
Рис.
5.25.
Рис. 5.26.
Рис. 5.27.
Теперь рассмотрим более общую задачу: необходимо удалить 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.28.
Результаты работы программы представлены на рис. 5.29 .
Рис. 5.29.
5.9 Вставка элемента в массив
Рассмотрим несложную задачу: вставить число b в массив X(10) , между третьим и четвёртым элементами.
Для решения этой задачи необходимо все элементы массива, начиная со четвёртого, сдвинуть вправо на один элемент. Затем в четвёртый элемент массива нужно будет записать b (X:=b;) . Но чтобы не потерять соседнее значение , сдвигать на один вправо нужно сначала десятый элемент, затем девятый, восьмой и т. д. до четвёртого. Блок-схема алгоритма вставки приведена на рис. 5.30 .
Рис. 5.30.
В общем случае блок-схема вставки числа b в массив X(N) , между элементами c номерами m и m+1 представлена на рис. 5.31 .
Рис. 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.
5.10 Использование подпрограмм для работы с массивами
Рассмотрим, как можно передавать массивы в подпрограмму. Как известно (см. главу 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;
Распределение памяти и указание границ индексов
Тема урока: «Вставка и удаление элементов массива».
Предмет: Информатика и ИКТ.
Класс: 10 (профиль).
Ключевые слова: информатика, практическая работа, программирование, массивы, вставка, удаление элементов.
Тип урока: практическая работа.
Оборудование: Раздаточный материал; персональные компьютеры.
Литература:
Попов В.Б. Turbo Pascal для школьников: Учебн. пособие - 3-е доп. изд. – М.: Финансы и статистика, 2004, - 528 с.: ил.
Семашко Г.Л., Салтыков А.И. «Программирование на языке паскаль», М: «Наука», 1993 г.
ФароновВ. В. « Turbo Pascal 7.0. Начальный курс», М: «Нолидж», 1997 г.
Цель работы:
разобрать принципы вставки и удаления элементов в одномерных и двумерных массивах,
закрепить полученные знания, путем решения задач.
Время выполнения: 2 урока.
Ход урока.
I . Удаление элементов из массива.
Одномерный массив
Двумерный массив
Постановка задачи:
Дан массив A (N ). Удалить элемент, расположенный на месте k .
Дан массив B (N ,M ). Удалить столбец с номером k . (аналогично для удаления строки)
Описание способа удаления:
Сдвинуть весь «хвост» массива, начиная с элемента с номером k +1, на одну позицию влево, т.е. выполняя операцию: a i =a i +1 , где i = k , k +1, …, N -1
Полученный массив будет содержать N -1 элемент.
Сдвинуть все столбцы, начиная с k +1 по m на одну позицию влево, выполнив операции:
Для j от 1 до m -1 делать
a i , j =a i , j +1
Дано: 3 5 7 8 9 N=5, k=2
Операции: a 2 :=a 3 ; a 3 :=a 4 ; a 4 :=a 5
Итог: 3 7 8 9
Дано: N =3, M =4, k =2 Операции: Результат:
1 5 2 7 a 1,2:=a 1,3 ; a 1,3:=a 1,4 ;
8 4 3 5 a 2,2:=a 2,3 ; a 2,3:=a 2,4 ;
0 9 1 4 a 3,2:=a 3,3 ; a 3,3:=a 3,4 ;
Программа
Randomize ;
Writeln (‘Введите количество элементов’);
Readln (n );
Writeln (‘Введите № удаляемого элемента’);
Readln (k );
{формирование массива случайным образом}
For i:=1 to n do begin
a[i]:=random(101)-50;
end ;
writeln ;
{удаление заданного элемента}
For i:=k to n-1 do
{ выводитоговогомассива}
For i:=1 to n-1 do
clrscr; randomize;
writeln(" Введитекол- вострокистолбцов");
writeln(" Введите № удаляемогостолбца");
for i:=1 to n do begin {формируем массив}
for j:=1 to m do begin
b:=51*random-25;
write(b:8:2)
for j:=k to m-1 do { удаляем k- ыйстолбец}
for i:=1 to n do
b:=b;
{выводим получ енный массив}
for i:=1 to n do begin
for j:=1 to m-1 do begin
write(b:8:2)
В одномерном массиве A (N ) найти min элемент и удалить его.
В двумерном массиве B (N ,M ) удалить строку с номером k . При этом выполнить проверку: не превышает ли значение k количества строк массива B .
II . Вставка (включение) элементов в массив.
Одномерный массив
Двумерный массив
Постановка задачи:
Дан массив A (N ). Включить на k место в этом массиве элемент, равный m .
Дан массив B (N ,M ). Добавить столбец с номером k . Элементы нового столбца равны элементам массива C (N ).(аналогично для добавления строки)
Описание способа удаления:
Перед включением заданного элемента в массив, необходимо раздвинуть этот массив, т.е. передвинуть «хвост» массива вправо на одну позицию, т.е. выполняя операцию: a i +1 =a i , где i = N , N -1, …, k . Перемещение элементов массива начинаем с конца, в противном случае весь хвост массива заполнится k -ым элементом.
Размер массива увеличится до N +1 элемента.
Сдвинуть все столбцы, начиная с m по k на одну позицию вправо, выполнив операции:
для j от m до k делать
Перебрать все строки с 1 по n , выполнив
a i , j +1 =a i , j
Затем в i =1-ой по n строках a i , k :=c i
В новом массиве будет M -1 столбец.
Важно: при добавлении столбца (строки) в двумерный массив, элементы этого столбца (строки) берутся из дополнительного одномерного массива размером = кол-ву строк двумерного массива (=кол-ву столбцов) либо вводятся с клавиатуры.
Дано: 3 8 7 6 5 N=5, k=2, m=4
Операции: a 6 :=a 5 =5; a 5 :=a 4 =6; a 4 :=a 3 =7; a 3 :=a 2 =8
Итог: 3 4 8 7 6 5
Дано: N =3, M =4, k =3 Операции: Результат:
C(N)={6,8,2} a 1,5:=a 1,4 ; a 1,4:=a 1,3 ;
1 5 2 7 a 2,5:=a 2,4 ; a 2,4:=a 2,3 ;
8 4 3 5 a 3,5:=a 3,4 ; a 3,4:=a 3,3 ;
Программа
Var a:array of integer;
n,k,i:byte; m:integer;
Writeln(" Введитеколичествоэлементов");
Writeln(" Введите № включаемогоэлемента");
Readln (k );
Writeln ("Введите значение включаемого эл-та");
{ формируеммассив}
For i:=1 to n do begin
a[i]:=random(101)-50;
end ; writeln ;
{раздвигаем эл-ты массива}
For i:=n downto k do
a :=a ;
{заносим новый эл-т на k-ую позицию}
a :=m ;
{выводим получившийся массив}
For i:=1 to n+1 do
var b:array of real; i,j,m,n,k:byte;
c:array of real;
clrscr; randomize;
writeln ("Введите кол-во строк и столбцов");
readln (n ,m );
writeln ("Введите № добавляемого столбца");
for i:=1 to n do begin {формируем исходный массив}
for j:=1 to m do begin
b:=51*random-25;
write(b:8:2)
end;writeln;end;writeln;
for i:=1 to n do begin {форм. массив доб-го столбца}
c[i]:=51*random-25; write(c[i]:8:2)
end; writeln; writeln;
for j:=m downto k do {раздвигаем столбцы}
for i:=1 to n do
b:=b;
for i:=1 to n do {добавляем столбец}
for i:=1 to n do begin {выводим полученный массив}
for j:=1 to m+1 do begin
write(b:8:2)
end; readln end.
Задачи для самостоятельного решения:
В одномерном массиве A (N ) найти max элемент и вставить за ним элемент равный 2*max .
В двумерном массиве B (N ,M ) вставить k -ую строку элементов массива C (M ). При этом выполнить проверку: не превышает ли значение k количества строк массива B .
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;