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

Лабораторная работа №9

Одномерные массивы

Для решения многих задач удобно сначала упорядочить данные по определенному признаку, так можно ускорить поиск некоторого объекта. Например, в преферансе игроки раскладывают карты по мастям и по значению. Так легче определить, каких карт не хватает. Или возьмем любой энциклопедический словарь - статьи в нем упорядочены в алфавитном порядке.

Перегруппирование заданного множества объектов в определенном порядке называют сортировкой.

Отличительной особенностью сортировки является то обстоятельство, что эффективность алгоритмов, реализующих ее, прямо пропорциональна сложности понимания этого алгоритма. Другими словами, чем легче для понимания метод сортировки массива, тем ниже его эффективность.

Сегодня существует множество методов сортировки, но для понимания сути сортировки рассмотрим некоторые из них.

Но прежде чем перейти к рассмотрению конкретного алгоритма той или иной сортировки немного вспомним материал, который пригодится нам в дальнейшем.

Задача. Даны две целочисленные переменные х и y. Составить фрагмент программы, после выполнения которого значения этих переменных распределяются в порядке убывания.

Обмен значений переменных нужно производить лишь в том случае, если х<у. Для того чтобы не потерять начальное значение переменной х, введем дополнительную переменную t.

if x<y

then

begin

t:=x;

x:=y;

y:=t;

end;

Задача. Составить фрагмент программы поиска максимального числа из трех введенных с клавиатуры чисел.

Пусть а, b, c - вводимые с клавиатуры числа, Max - максимальное из их значений. На первом шаге предположим , что а - максимальное из чисел и поэтому Max:=a. Затем сравним значение предполагаемого максимума со значениями переменных b и с. Если значение m окажется меньше, чем значение очередной переменной, то переопределим значение максимума.

. . .

m:=a;

if m<b

then

m:=b;

if m<c

then

m:=c;

. . .

Задача. Дан массив а, состоящий из 10 элементов. Составить программу поиска максимального элемента массива.

Используем идею предыдущей задачи. Перед началом поиска выберем условно в качестве максимального первый элемент массива Max:=a[1]. Затем по очереди каждый элемент массива сравним со значением переменной m. Если он окажется больше, то изменим значение Max. После анализа всех элементов массива переменная Max содержит значение максимального элемента массива.

. . .

Max:=a[1];

for i := 2 to 10 do

if Max<a[i]

then

Max := a[i];

. . .

До написания программ необходимо выполнить некоторую подготовительную работу - написать шаблон программы следующего содержания:

Рrogram Sorting;

Сonst

n = ... ; {количество элементов в массиве}

Type

TArray = array [1..n] of integer;

Procedure FillArray (Var a: TArray);

Var

i: integer;

Begin

for i: = 1 to n do

a [i] := Random(100);

End; {конец процедуры}

Procedure PrintArray (a: TArray);

Var

i: integer;

Begin

for i: = 1 to n do

write (a [i]: 3, ' ');

writeln;

End;

Begin {Главная программа}

writeln('Сортировка МЕТОДОМ . . .');

writeln('Заполняем исходный массив: ');

FillArray (a);

PrintArray (a);

AnySort (a, b);{имя процедуры, реализующей данный метод}

writeln('Отсортированный массив: ');

PrintArray (b);

End.

Для реализации различных методов сортировки необходимо подготовить несколько вспомогательных процедур и функций.

1. Функция, которая ищет минимальный элемент правее некоторого заданного и возвращает его номер в качестве результата. Аргументами функции являются номер элемента массива и обрабатываемый массив:

2. Большинство методов сортировок основаны на обмене двух чисел. Для этой цели предназначена процедура, которая в качестве параметров берет два числа и меняет их значения

3. Также пригодится процедура, которая берет элемент с индексом i, перемещает его на место элемента с номером j. А все элементы, которые имеют индексы от j до i-1 сдвигает на одну позицию вправо.

Доступ к элементам массива.

Рассмотрите предложенные ниже фрагменты программ для решения некоторых типичных задач.

Изменение значения некоторых элементов

Задача. Заменить отрицательные элементы на противоположные по знаку.

Для этого опишем процедуру. Ей будем передавать один параметр - массив, который будет результатом ее выполнения, так как некоторые элементы могут быть заменены.

Procedure Zamena (Var m : MyArray; n:integer);

Var

i : integer;

Begin

for i := 1 to n do

if m[i] < 0

then

m[i] := -1*m[i];

End;

Нахождение номеров элементов с заданным свойством

Задача. Найти и вывести на экран номера четных элементов.

Для решения задачи необходимо просмотреть весь массив, и если просматриваемый элемент является четным, то выводить его номер. Опишем процедуру, которой передается данный массив и выводятся нужные номера.

Procedure PoiskChet(m : MyArray; n:integer);

Var

i : integer;

Begin

for i := 1 to n do

if m[i] mod 2 =0

then

Write(i:5);

End;

Нахождение количества элементов с заданным свойством

Задача. Найти количество положительных и отрицательных элементов в данном массиве.

Опишем процедуру, которой будем отправлять три параметра - массив и два счетчика, один для элементов, больших нуля, а второй - для отрицательных элементов.

Procedure OtrPol(m : MyArray; ; n:integer; Var k1,k2 : Integer);

Var

i : integer;

Begin

k1 :=0;

k2 :=0;

for i := 1 to n do

if m[i] > 0

then

Inc(k1)

Else

if m[i] < 0

then

Inc(k2);

End;

Есть ли в данном массиве элементы с данным свойством?

Для решения таких задач удобнее использовать циклы с условиями и составлять функции, результат которых имеет логический тип.

Задача. Есть ли отрицательный элемент в массиве?

Начинаем с первого элемента (i=1). пока не просмотрен последний элемент (i<=n) и не найден отрицательный (m[i]>=0), будем переходить к следующему (Inc(i)). Таким образом, мы закончим просмотр массива в одном из двух случаев: первый - просмотрели все элементы и не нашли отрицательный, тогда i>n, второй - нашли нужный, при этом i<=n. Опишем функцию, значение которой истина (True), если такой элемент есть, и ложь (False), если его нет.

Function Control (m : MyArray; n:integer) : Boolean;

Var

i : integer;

Begin

i := 1;

while (i<=n) and (m[i]>0) do

Inc(i);

Control := (i<=n);

End;

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

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

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

· найти номер максимального элемента 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.

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

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

Program DeleteK;

Const

n=30; dd=51;

Type

MyArray = Array [1..n] of Integer;

Var

A : MyArray;

k : Integer;

Procedure InsertMas1(Var m : MyArray; n : integer);

. . .

Procedure InsertMas2(Var m : MyArray; n : integer);

. . .

Procedure PrintMas(m : MyArray; n : integer);

. . .

Function Maximum (m : MyArray; n:integer) : Integer;

Var

i, max, maxi : integer;

Begin

max:=-maxint; {начальным значением переменной будет наименьшее значение данного типа}

for i := 1 to n do {просматриваем все элементы массива}

if m[i] > max {если найден элемент больше, чем мы считаем максимальным}

then

begin

max:=A[i]; {то запомним найденное значение}

maxi:=i; {а также место, на котором он стоит в массиве}

end;

Maximum := maxi; {имени функции присвоим найденный результат}

End;

Procedure Delete(Var m : MyArray; Var n:integer; k1 : integer);

Var

i : integer;

Begin

for i := 1 to n-1 do

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

m[n]:=0;

Dec(n);

End;

Begin

. . .

k:=Maximum(A,m);

Delete(A,m,k);

. . .

End.

Задание. На основе имеющегося шаблона программы и рассмотренного алгоритма решения задачи, закончите составление работающей программы. Результат покажите учителю для оценки.

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

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: