Урок из серии: «Язык программирования Паскаль»
На этом уроке мы поговорим о том, как можно удалить элементы из массива. В языке Паскаль нет стандартных процедур для обслуживания массивов. Поэтому мы напишем свою процедуру.
Рассмотрим два случая: удаление одного элемента из массива и удаление нескольких элементов. Для решения этих задач используются разные подходы.
Знакомство с алгоритмом удаления элемента из массива начнем со следующей задачи.
Задача 1. Необходимо удалить k-ый элемент из массива m, состоящего из n элементов.
Решение.
Пусть дан одномерный массив, состоящий из 10 элементов:
9, 6, 7, 10, 14, 16, 5, 11, 4, 8.
Нужно удалить элемент с номером 6 (n=10, k=6).
Алгоритм удаления шестого элемента заключается в следующем:
- Сместить все элементы, начиная с 6-го, на один элемент влево: 6-му присвоить значение 7-го, 7-му присвоить значение 8-го, 8-му присвоить значение 9-го, 9-му присвоить значение 10-го: m[6]:=m[7]; m[7]:=m[8]; m[8]:=m[9]; m[9]:=m[10]. На этом сдвиг заканчивается.
Таким образом, сдвиг начинается с k-го элемента и идет по (n-1)-й элемент:
m[i]:=m[i+1], i=k..n-1 - Последнему элементу массива присвоить значение, равное 0: m[n]:=0.
- При дальнейшей работе с этим массивом использовать n-1 элемент.
После удаления элемента из массива, изменится количество элементов в массиве (уменьшается на один) и у части элементов изменится индекс.
После выполнения алгоритма, массив будет следующим:
9, 6,7, 10, 14, 5, 11, 4, 8, 0.
Для реализации этого алгоритма напишем процедуру с именем Delete. В качестве входных параметров передадим ей номер удаляемого элемента и массив, на выходе получим тот же массив, только измененный. Программный код процедуры будет следующим:
Procedure Delete1(k : integer; Var m : MyArray;);
{Процедура удаления из массива элемента с заданным номером.} {k — номер удаляемого элемента.} Var i : integer;
Begin
{смещение элементов, начиная с k-го, на один влево} for i := k to n-1 do
m[i] := m[i+1]; {последнему элементу присваиваем 0} End; |
Рассмотрим следующую задачу.
Задача 2. Удалить из одномерного массива максимальный элемент, если все элементы разные.
Решение
Для решения этой задачи, необходимо:
- Найти номер(индекс) максимального элемента — k.
- Удалить из массива элемент с найденным номером.
Составим программу с использованием новой процедуры. Кроме неё в программе будем использовать уже знакомые нам процедуры: Init2, Print, Maximum. В тексте программы описания процедур опущены.
Program Primer_1;
Const
n = 10;
Type
MyArray = Array [1..n] of Integer;
Var
A : MyArray;
max, maxi: Integer;
Procedure Init2(a,b: integer; Var m : MyArray;);
{Процедура заполнения массива случайными числами из заданного промежутка.}
...
Procedure Maximum(m:myarray; var max,numer_max:integer);
{Процедура нахождение максимального элемента массива и его номера.}
...
Procedure Delete1(k1 : integer; Var m : MyArray;);
{Процедура удаления из массива элемента с заданным номером.}
...
Procedure Print(n : integer; m : MyArray; );
{Вывод массива на печать}
...
Begin {main}
Init2(-50,50,A) {заполнение массива случайными числами и вывод на экран}
Maximum(A,max,maxi); {поиск номера максимального элемента}
Delete1(maxi,A); {удаление элемента с номером k}
Print(n-1, A) {вывод n-1 элементов массива на экран}
End. |
Вы познакомились алгоритм удаления элемента массива. Теперь давайте рассмотрим случай, когда нужно удалить из массива несколько подряд идущих элементов.
Задача 3. Удалить из массива все максимальные элементы.
Решение
В этом случае лучше массив начинать просматривать с конца, так как иначе нужно будет снова возвращаться к элементу с номером, который только что обработали.
Эта может случиться тогда, когда подряд идут два или более максимальных элементов. Если первый удалим, то на его место сдвигается следующий максимальный элемент (индекс изменять не будет необходимости).
Если просматривать массив с конца, то на место удаленного элемента встанет уже обработанный элемент, и можно будет перейти к обработке следующего элемента (путем изменения индекса на один).
Для организации просмотра массива с конца, можно воспользоваться оператором цикла For с убывающей переменной цикла:
For i := n Downto 1 Do <тело цикла>, где значение переменной i уменьшается от n до 1.
Для решения задачи делаем два просмотра массива.
Первый просмотр массива делаем с начала для того, чтобы найти значение максимального элемента (на этот раз нужно определить значение элемента, а не его индекс). Для этого можно использовать процедуру Maximum. У неё два выходных параметра: значение максимального элемента и его индекс.
Второй просмотр производится с конца массива для того, чтобы удалить максимальные элементы. Перебираем все элементы, если текущий элемент массива имеет максимальное значение, то удаляем его, значение счётчика удаленных элементов k увеличим на 1. Подсчитываем количество удаленных элементов для того, чтобы знать, сколько элементов выводить на экран.
Ниже представлен текст программы:
Program Primer_2; Const n = 10; Type myarray = Array [1..n] Of Integer;
Var A : myarray;
max, maxi: integer {max - значение максимального элемента,maxi - его номер.}
k: integer; {k - количество удалённых элементов} Procedure Init2 (Var m : myarray);
{процедура заполнения массива случайными числами и вывод на экран}
...
Procedure Maximum (m : myarray; var max,numer_max:integer);
{Процедура нахождение значения максимального элемента массива и его номера}
...
Procedure Delete1(k1 : Integer; Var m : myarray);
{процедура удаления элемента с данным номером}
...
Begin {main}
{заполняем массив А случайными числами из [0,50] и выводим на экран}
Init2(0,50, A);
{ищем значение максимального элемента}
Maximum(A,max,numer_max); k:=0;
{просматриваем все элементы, начиная с последнего}
For i:=n Downto 1 Do
If A[i] = max Then {если текущий элемент равен максимальному, то}
Begi Delete1(i,A); {удаляем его}
Inc(k); {увеличиваем счетчик удаленных элементов} End;
Print(n-k,A); {выводим оставшиеся элементы массива на экран}
Readln;
End. |
Вы познакомились с алгоритмом удаления элементов из одномерного массива.
На следующем уроке продолжим изучение алгоритмов обработки одномерных массивов, рассмотрим алгоритм добавления элементов в массив.
Спасибо !