Удаление элементов одномерного массива

Пример 1.15. Удалить из массива элемент, значение которого равно максимуму

среди всех элементов массива. Считаем, что все элементы разные.

Для решения задачи необходимо:

1)найти номер максимального элемента – k;

2)сдвинуть все элементы, начиная с k-го на один элемент влево;

3)последнему элементу присвоить значение 0.

Пусть дан одномерный массив из 6 элементов: 6, 3, 4, 11, 7, 2.

Номер максимального элемента равен 4 (k=4). Т.е., начиная с 4-го элемента надо сдвигать элементы на один элемент влево: 4-му элементу присвоить значение 5-го, 5-му

– значение 6-го. На этом сдвиг заканчивается.

	Таблица 2. Удаление максимального значения
Индекс	1	2	3	4	5	6
Массив до удаления значения	6	3	4	11	7	2
Массив после удаления значения	6	3	4	7	2	0

Таким образом, сдвиг начинается с k-го элемента и идет по (n-1) -й (где n – количество элементов в массиве). При удалении элемента размерность массива не изменяется. Обычно последнему элементу (элементу с номером n) присваивают значение, равное 0. Окончательно массив будет иметь вид: 6, 3, 4, 7, 2, 0.

Программа:

Program delete1; Const n=6;

Type Tarray= Array[1..n] Of Integer; Var A:Tarray;

i: Integer; {параметр цикла для перебора элементов} k: Integer; {номер максимального элемента};

Begin

{Ввод массива А}

...

{Вывод заполненного массива А}

...

{Поиск индекса максимального элемента массива – k}

...

{Удаление элемента с номером k} For i:= k To n-1 Do

A[i] := A[i+1];

A[n] := 0; {Последний элемент равен 0} {Вывод нового массива А}

For i:=1 To n-1 Do Write (A[i]:6);

End.

Пример 1.16. Удалить из массива значения максимальных элементов. Максимальный элемент может встречаться несколько раз.

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

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

Program delete2;

Const n=6; {количество элементов} Type Tarray= Array[1..n] Of Integer; Var A:Tarray;

i,j,kol,zMax: Integer;; Begin

{Заполнение массива А}

...

{Поиск значения максимального элемента – zMax}

...

{Удаление максимальных элементов}

kol:=0; {количество удаленных элементов} For i := n DownTo 1 Do

If A[i] = zMax Then Begin

For j:= i To n-kol-1 Do A[j] := A[j+1];

A[n-kol] := 0; {Последний элемент равен 0} Inc(kol); {Увеличение количества

удаленных элементов} End;

{Вывод нового массива А} For i:=1 To n-kol Do

Write (A[i],’ ‘); ReadLn;

End.

Пусть дан одномерный массив из 6 элементов: 6, 11, 4, 11,7, 2.

Пошаговое выполнение программы показано в таблице 3.

Таблица 3. Трассировочная таблица удаления нескольких элементов массива

i	A[i]	Max	Массив А
	Поиск максимального элемента
1	6 > –32 768, да	*6	6, 11, 4, 11,7, 2
2	11>6, да	*11
3	4 >11, нет	11
4	11>11, нет	11
5	7>11, нет	11
6	2>11, нет	11
	Удаление нескольких элементов массива
i	A[i]=max	Max	Массив А
6	2=11, нет	11	6, 11, 4, 11,7, 2
5	7=11, нет		6, 11, 4, 11,7, 2
4	11=11, да		6, 11, 4, 7, 2, 0
3	4=11, нет		6, 11, 4, 7, 2, 0
2	11=11, да		6, 4, 7, 2, 0, 0
1	6=11, нет		6, 4, 7, 2, 0, 0

Задание. Программа в Пример 1.176 имеет сложность – порядка n2. Напишите программу для решения поставленной задачи, чтобы она имела линейную сложность порядка n.

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

Вставлять элемент можно до или после данного элемента, номер этого элемента можно вводить с клавиатуры или искать при определенных условиях.

Пример 1.17. Вставить число 100 после 5-го элемента массива. Элементы

исходного массива теряться не должны.

Пусть k – это номер элемента, после которого надо вставить элемент x (k и x будем вводить с клавиатуры). Тогда вставка осуществляется следующим образом:

1)первые k элементов массива остаются без изменений;

2)все элементы, начиная с (k+1)–го надо сдвинуть на один элемент вправо;

3) на место (k+1)-го элемента записываем x, т.е. после k-го элемента массива.

Пусть дан одномерный массив из 6 элементов: 6, 3, 4, 11, 7, 2. Надо вставить элемент 100 после пятого элемента массива: 6, 3, 4, 11, 7, 100, 2. В массиве будет 7 элементов, т.е. массив надо определять на n+1 элемент.

Сдвиг элементов надо проводить с последнего.

Program insert1;

Const n=6; {количество элементов массива} Var A:Array[1..n+1] Of Integer; i: Integer;

k: Integer; {номер элемента, после которого вставляем элемент х} x: Integer; {Вставляемый элемент}

Begin

{Заполнение массива А с клавиатуры} For i:=1 To n Do

Read (A[i]);

{Ввод номера элемента и значения вставляемого элемента}

WriteLn (‘Введите номер элемента, после которого вставлять’); WriteLn (‘и вставляемое число’);

ReadLn (k, x);

{Сдвиг элементов массива, начиная с конца} For i := n DownTo k+1 Do

A[i+1] := A[i];

{Вставка элемента на место (k+1)-го, т.е. после k-го} A[k+1]:= x;

{Вывод нового массива А} For i:=1 To n+1 Do

Write (A[i]:6);

End.

Пример 1.18. Вставить число 100 перед 5-м элементом массива.

Задача отличается от предыдущей тем, что в первой сдвигали все элементы, стоящие после k-го, т.е. с (k+1)-го, а на его место записывали новый элемент. В данной задаче сдвигаем все элементы с k-го, а затем на его место записываем новый.

Фрагмент программы:

...

{Сдвиг элементов массива, начиная с конца} For i := n DownTo k Do

A[i+1] := A[i];

{Вставка элемента на место (k+1)-го, т.е. после k-го} A[k]:= x;

...

Пример 1.19. Вставить по одному элементу после всех элементов с заданными свойствами. Например, вставить число после всех элементов массива, кратных 3.

Размерность массива в результате решения задачи может увеличиться в два раза, т.к. может оказаться, что вставлять заданное значение придется после каждого элемента массива.

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

Лучше всего просматривать массив, начиная с конца, тогда вставляемый элемент «мешать» не будет. Кроме того, номер последнего элемента можно будет знать (если знать, сколько элементов вставлено на данный момент), при этом просмотр будет последовательным от n-го до первого.

Программа:

Program insert2; Const n=6;

Var A:Array[1..2*n] Of Integer; i, j: Integer;

k: Integer; {Количество вставляемых элементов} x: Integer; {Вставляемое число}

Begin

{Заполнение массива А с клавиатуры} For i:=1 To n Do Begin

Write(i, ‘-ый элемент: ’); ReadLn (A[i]);

End;

{Вывод заполненного массива А} WriteLn( ‘Массив: ’);

For i:=1 To n Do Write (A[i]:6);

{Ввод значения вставляемого элемента} WriteLn (‘Введите вставляемое число’); ReadLn (x);