Удаление элемента

Пример:

Удалить из массива максимальный элемент, если все элементы разные.

Решение

Для того чтобы решить данную задачу, необходимо:

	найти номер максимального элемента - k;
	сдвинуть все элементы, начиная с k-го, на один элемент влево;
	последнему элементу присвоить значение 0.

Рассмотрим на конкретном примере. Пусть дан одномерный массив из целых чисел, состоящих из 10 элементов: 6, 3, 4, 7, 11, 2, 13, 8, 1, 5. Номер максимального элемента равен 7 (k = 7), то есть, начиная с 7-го элемента, будем сдвигать элементы на один влево: 7-му элементу присвоим значение 8-го, 8-му присвоим значение 9-го, а 9-му присвоим значение 10-го, на этом сдвиг заканчивается. Таким образом, сдвиг начинается с k-го элемента и идёт по (n-1)-й (где n - это количество элементов в массиве). После этого последнему элементу присвоим значение, равное 0, а тогда массив будет следующим: 6, 3, 4, 7, 11, 2, 8, 1, 5, 0.

Примечание. При удалении элемента размерность массива не изменяется.

Составим программу, удаляющую максимальный элемент из одномерного массива, в ней воспользуемся уже двумя знакомыми процедурами - Init2 и Print1, которые: первая - заполняет массив случайными числами, а вторая - выводит на печать этот массив. Чтобы последний 0 не выводился, мы модифицируем процедуру вывода Print и будем ей передавать не только массив, но и количество элементов, которые надо вывести, начиная с первого.

Program Example-40;

Const n = 30; dd = 51;

Type myarray = Array [1..n] Of Integer;

Var A: myarray;

k: Integer; {k-номер максимального элемента }

Procedure Init2(Var m: myarray); {процедура заполнения (инициализации) массива случайными числами}

...

Procedure Print1(n1: Integer; m: myarray); {процедура вывода

(распечатка) массива }

Var i: Integer;

Begin

For i:=1 To n1 Do Write(m[i]:5);

Writeln;

End;

Function Maximum(m: myarray): Integer;

Var i, max, maxi: Integer;

Begin

max:=-maxint; {-maxint- это целая константа, имеющая минимальное среди целых чисел значение, равное -32 768}

For i:=1 To n Do {просмотр всех элементов массива}

If m[i]>max Then {если данный элемент больше максимального элемента, найденного среди первых i-1 элементов, то}

Begin

max:=A[i]; {новое значение максимального элемента}

maxi:=i; {номер максимального элемента в массиве}

End;

Maximum:=maxi;

End;

Procedure Delete(k1:Integer;Var m:myarray);

Var i: Integer;

Begin {сдвиг элементов на один влево}

For i:=k1 To n-1 Do

m[n]:= m[i+1]; {i-му элементу присваиваем значение (i+1)-го}

m[n]:=0;{последний элемент равен 0}

End;

Begin

Randomize; {включение генератора случайных чисел}

Init2(A); {заполнение массива А}

Print1(n,A); {вывод заполненного массива А}

k:=Maximum(A); {поиск номера максимального элемента}

Delete (k,A); {удаление элемента с номером k}

Print1 (n-1,A); {вывод нового массива А}

Readln;
End.

Рассмотрим удаление максимального элемента из массива целых чисел для n = 10 в пошаговом режиме. Пусть заполнение и первый вывод массива уже сделаны. Трассировка этой программы для нашего примера приведена в таблице 1.

Таблица 1

I	A[i]>max	max	maxi	массив А
Поиск максимального элемента
-	-	-32767	-	6, 3, 4, 7, 11, 2, 13, 8, 1, 5
	6>-32768 да	* 6
	3>6 нет
	4>6 нет
	7>6 да	* 7
	11>7 да	* 11
	2>11 нет
	13>11 да	* 13
	8>13 нет
	1>13 нет
	5>13 нет
Сдвиг элементов массива на один элемент влево
				6, 3, 4, 7, 11, 2, 8, 8, 1, 5
				6, 3, 4, 7, 11, 2, 8, 1, 1, 5
				6, 3, 4, 7, 11, 2, 8, 1, 5, 5
	А[n]:=0			6, 3, 4, 7, 11, 2, 8, 1, 5, 0

Сейчас осталось только вывести на экран изменённый массив.

Таким образом, на экране появятся следующие строки:

6 3 4 7 11 2 13 8 1 5 - это начальный массив.

6 3 4 7 11 2 8 1 5 - это массив после удаления максимального элемента.

Пример:

Предположим, что максимальный элемент встречается несколько раз.

Решение

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

For i:= B Downto A Do<тело цикла>, где значение переменной i будут уменьшаться на единицу, начиная от В до А (значение В должно быть меньше значения А).

Кроме того, номер максимального элемента запоминать не будем, а просмотрим массив с конца, и если элемент имеет максимальное значение, то удалим его, при этом значение счётчика k будем увеличивать на 1. Для решения этой задачи надо изменить функцию Maximum, сейчас нам нужен не номер, а значение максимального элемента. В программе это будет выглядеть так:

Program Example-41;

Const n = 30; dd = 51;

Type myarray = Array [1..n] Of Integer;

Var A: myarray;

m, k, i: Integer; {m - значение максимального элемента, k - количество удалённых элементов }

Procedure Init2 (Var m: myarray); {процедура заполнения (инициализации) массива случайными числами}

...

Function Maximum (m: myarray): Integer;

Var i, max: Integer;

Begin

max:=-maxint;

For i:=1 To n Do {просмотр всех элементов массива}

If m[i]>max Then

max:=A[i];{новое значение максимального элемента}

Maximum:=max;

End;

Procedure Delete(k1: Integer; Var m: myarray);{процедура удаления элемента с данным номером}

...

Begin

Randomize; {включение генератора случайных чисел}

Init2(A); {заполнение массива А}

Print1(n,A); {вывод заполненного массива А}

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

m:=Maximum(A);k:=0;

{просмотр всех элементов, начиная с последнего}

For i:=n Downto 1 Do

If A[i]=m Then {если данный элемент имеет максимальное значение, то}

Begin {удаляем элемент с номером i}

Delete(i,A);

Inc(k);

End;

Print1(n-k,A); {вывод нового массива А}

Readln;

End.

Рассмотрим удаление нескольких максимальных элементов из массива целых чисел для n = 10. Пусть заполнение и первый вывод массива уже сделан. Дан такой массив:

6 3 4 7 11 2 13 8 13 5

Проследим за ним дальше по шагам выполнения программы, результат такой трассировки приведён в таблице 2:

Таблица 2

i	A[i]>max	max	массив А
Поиск максимального элемента
-	-	-32767	6 3 4 7 11 2 13 8 13 5
	6>-32768 да	* 6
	3>6 нет
	4>6 нет
	7>6 да	* 7
	11>7 да	* 11
	2>11 нет
	13>11 да	* 13
	8>13 нет
	13>13 нет
	5>13 нет
Удаление нескольких элементов массива
i	A[i]=m	m	массив А
	5=13 нет		6 3 4 7 11 2 13 8 13 5
	13=13 да		6 3 4 7 11 2 13 8 5 0
	8=13 нет		6 3 4 7 11 2 13 8 5 0
	13=13 да		6 3 4 7 11 2 8 5 0 0
	2=13 нет		6 3 4 7 11 2 8 5 0 0
	11=13 нет		6 3 4 7 11 2 8 5 0 0
	7=13 нет		6 3 4 7 11 2 8 5 0 0
	4=13 нет		6 3 4 7 11 2 8 5 0 0
	3=13 нет		6 3 4 7 11 2 8 5 0 0
	6=13 нет		6 3 4 7 11 2 8 5 0 0

После выполнения k равно 2, поэтому на экране будет выведено n-k элементов. Сейчас осталось вывести на экран изменённый массив. Таким образом, появятся следующие строки:

6 3 4 7 11 2 13 8 13 5 - это начальный массив.

6 3 4 7 11 2 8 5 - это массив после удаления максимальных элементов.

Дата добавления: 2015-08-17