Вставка и удаление элементов одномерного массива
Вставка одного элемента
Пример 1. В массив, состоящий из n элементов, вставить число b после k-го элемента. Решение Рассмотрим на конкретном примере. Пусть дан следующий одномерный массив из 10 (n = 10) элементов:
3, -12, 5, 14, 27, -6, 1, -34, 10, -15. Вставим число 100 после 5 элемента (b=100, k = 5) Алгоритм вставки элемента в массив: Первые 5 элементов массива остаются без изменений. Сдвинуть все элементы, начиная с шестого, на один назад. Но чтобы не потерять соседнее значение, сдвиг будем начинать с последнего элемента — сдвинуть сначала десятый на один вправо, затем девятый, восьмой и т. д. до шестого (m[i+1]:=m[i], i=n..k). На место шестого элемента записываем значение 100, то есть после 5-го элемента массива (m[k+1]:=b;). Получим следующий массив: 3, -12, 5, 14, 27, 100, -6, 1, -34, 10, -15. Таким образом, в массиве стало 11 элементов, то есть массив надо определять на N+1 элемент: Array[1..n+1] Of Integer. Фрагмент программы: For i:=n Downto k1+1 Do {сдвиг элементов на одну позицию назад} m[k1+1]:= x1; {вставка элемента на место после k1-го} Пример 2. Вставить число после всех элементов массива, кратных 3.
Решение 1.Необходимо обратить внимание на описание массива: на сколько элементов может увеличиться массив? Максимальное количество элементов, после которых может быть вставлен новый элемент, совпадает с количеством элементов массива. Так как может случиться, что все элементы массива отвечают заданному свойству. Поэтому массив может увеличиться в два раза (это его самая большая размерность), а значит, соответствующее ему описание будет следующим:
Array[1..2*n] Of Integer; 2. Если мы будем просматривать элементы массива с начала и вставлять новый после элемента с заданным свойством, то следующим просматриваемым элементом будет новый (вставленный) элемент и его необходимо будет пропускать («перепрыгивать»). Поэтому решение будет не очень эффективным.
Поэтому лучше всего просматривать массив, начиная с конца, тогда вставляемый элемент мешать не будет. При этом просмотр будет последовательным от N-го до 1-го. 3.Номер последнего элемента после каждой вставки будет меняться. Его нужно будет переопределять. Для этого нужно вести подсчет количества вставленных элементов на данный момент. Для вставки нескольких элементов в массив составим программу, в которой будет вестись подсчет количества вставленных элементов и корректироваться номер последнего элемента.
Номер последнего элемента необходим для того, чтобы знать, сколько элементов необходимо сдвинуть при освобождении места для нового элемента, так как количество элементов в этой части массива увеличивается.
Slaidy.com
