Материал: Лабораторная работа №4 Массивы. Сортировка и поиск

Лабораторные работы по информатике для специальности «Моделирование и исследование операций в организационно-технических системах»

readln(a[i, j]); end;{for j}

{Здесь происходит обработка данных массива}

//Вывод элементов массива на экран for i:=1 to n do

begin

for j:=1 to m do

write(' a[', i, ',', j, ']=', a[i, j]:6:2);

writeln; end;{for i}

readln;

end.

Вставка и удаление элемента в массив

Для начала рассмотрим вставку элемента в массив. Для простоты будем рассматривать только одномерные массивы. Массив состоит из некоторого количества элементов nmax (емкость массива). Текущее количество элементов массива находится в переменной n.

Перед вставкой очередного элемента проверяем, что текущее количество элементов массива меньше, чем его емкость.

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

Приведенный алгоритм реализован в программе приведенной в листинге 5.

program InsElt;

{$APPTYPE CONSOLE}

const nmax=5; //емкость массива

begin

writeln('Vvedite chislo elementov massiva'); readln(n);

//Ввод массива for i:=1 to n do

begin

write('a[', i, ']='); readln(a[i]);

end;

//Элемент для вставки writeln('Vvedite element'); readln(element);

//Индекс элемента

Лабораторные работы по информатике для специальности «Моделирование и исследование операций в организационно-технических системах»

writeln('Vvedite index elementa'); readln(index);

//Вставка элемента if index<n+1 then

begin

inc(n); //увеличиваем длину массива if (Low(a)<=index)and(index<=n) then

for i:=n downto index do a[i]:=a[i-1]; //сдвиг массива

a[index]:=element; end

else begin

writeln('Invalid index'); readln;

Halt(0);

end;

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

for i:=1 to n do writeln('a[', i, ']=', a[i]:6:2);

readln;

end.

Удаление элемента происходит аналогично. Сначала проверяется, что индекс элемента не выходит за диапазон допустимых значений, а затем сдвигаем элементы таким образом, чтобы закрыть удаляемый элемент.

program DelElt;

{$APPTYPE CONSOLE}

const nmax=5; //емкость массива

begin

writeln('Vvedite chislo elementov massiva'); readln(n);

//Ввод массива for i:=1 to n do

begin

write('a[', i, ']='); readln(a[i]);

end;

//Индекс элемента writeln('Vvedite index elementa'); readln(index);

//Удаление элементов if index<n+1 then

begin

if (Low(a)<=index)and(index<=n) then

for i:=index to n do a[i]:=a[i+1]; //сдвиг массива

Лабораторные работы по информатике для специальности «Моделирование и исследование операций в организационно-технических системах»

dec(n); //уменьшаем длину массива end

else begin

writeln('Invalid index'); readln;

Halt(0);

end;

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

for i:=1 to n do writeln('a[', i, ']=', a[i]:6:2);

readln;

end.

Поиск

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

Последовательный поиск.

Последовательный поиск заключается в выборе каждого элемента массива и сравнения его с искомым. Быстродействие алгоритма пропорционально числу элементов. Реализация этого алгоритма с помощью цикла for … to … do приведена в листинге 5

Листинг 5

program Search;

{$APPTYPE CONSOLE}

const nmax=5; //емкость массива

var a:array [0..nmax] of real; //массив

begin

writeln('Vvedite massiv ', nmax+1, 'elements');

//Ввод массива for i:=1 to nmax do

begin

write('a[', i, ']='); readln(a[i]);

end;

//элемент для поиска

writeln('Input element for search'); readln(Value);

//поиск index:=-1;

for i:=Low(a) to High(a) do if a[i]=Value then

Лабораторные работы по информатике для специальности «Моделирование и исследование операций в организационно-технических системах»

begin index:=i; break;

end;

if index>=0 then //если элемент найден writeln('Element found in ', index, ' position')

else //если элемент не найден writeln('Element not found!');

readln;

end.

Бинарный поиск

Алгоритм бинарного поиска применим только для отсортированного массива. Бинарный поиск работает следующим образом. Берем средний элемент массива и проверяем равен ли он искомому элементу,. если равен, то поиск окончен. В противном случае, если искомый элемент меньше среднего, то можно сказать, что если элемент присутствует в массиве, то он находится в первой его половине. С другой стороны, если искомый элемент больше среднего, то он находится во второй части массива. Таким образом, одним сравнением удалось локализовать искомый элемент в массиве двое меньшей размерности. Описанная операция повторяется до тех пор, пока искомый элемент не будет найден (если он присутствует в массиве). Так как при каждом выполнении цикла размер массива уменьшается в два раза, то быстродействие алгоритма будет пропорционально log2 n . Так, например для поиска в массиве из 256 элементов

понадобится произвести всего 8 сравнений. Реализация алгоритма приведена в листинге 6.

Листинг 6

program Search2;

{$APPTYPE CONSOLE}

const n=10;//длина массива

var a:array [0..n-1] of integer=(1,2,3,4,5,16,17,56,78,110);

m:integer; //индекс среднего элемента el:integer;//значение искомого элемента

begin

write('Vvedite element dlia poiska '); readln(el);

l:=0; r:=n-1;

while l<=r do begin

m:=(l+r) div 2;//вычисляем индекс среднего элемента

{если значение среднего элемента меньше искомого значения, то переместить левый индекс на позицию до среднего индекса} if a[m]<el then l:=succ(m)

{если значение среднего элемента больше искомого значения, то переместить правый индекс на позицию после среднего

индекса} else

if a[m]>el then r:=pred(m)

Лабораторные работы по информатике для специальности «Моделирование и исследование операций в организационно-технических системах»

else //иначе элемент найден begin

writeln('Search result a[', m, ']=', a[m]); break;

end; end;{while}

if l>=r then writeln('Element ', el,' not found'); readln;

end.

Поиск максимального и минимального элементов массива

Поиск минимального или максимального элемента массива можно осуществить с помощью алгоритма приведенного в листинге 7.

Листинг 7

program MinMax;

{$APPTYPE CONSOLE}

const n=10;//длина массива

var a:array [0..n-1] of integer;

begin

//инициализируем массив случайными числами

Randomize;

for i:=0 to n-1 do a[i]:=random(10);

max:=a[0];

min:=a[0];

for i:=1 to n-1 do begin

if a[i]>max then max:=a[i]; if a[i]<min then max:=a[i];

end;{for}

writeln('min ', min); writeln('max ', max); readln;

end.

Сортировка

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