Файл: Особенности и примеры использования массивов при разработке программ.pdf

2.5 Сортировка элементов массива

Существует много алгоритмов сортировки массива, но наиболее простым и понятным является сортировка методом «пузырька», при которой самый «легкий» элемент «всплывает», а самый тяжелый «тонет».

Например,

Дан массив

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

При сортировке методом «пузырька» сравниваются два соседних элемента (mas[i] и mas[i+1]). Если mas[i] > mas[i+1], то происходит перестановка элементов. Визуально процесс сортировки можно представить в виде:

Самый тяжелый элемент «упал»

Рисунок 2. Сортировка методом «пузырька»

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

(n-размерность массива)

For j:=1 to n do {количество просмотров массива}

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

If mas[i] > mas[i+1] then begin

t:=mas[i];

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

mas[i+1]:=t;

end;

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

3. Особенности обработки двумерных массивов

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

Для описания двумерных массивов используются те же способы, что и для одномерных массивов, но в качестве размерности массива задается двойное значение (Например, [1..10,1..10]).

Таким образом, для создания двумерного целочисленного массива размерностью 5×7 (5 строк, 7 столбцов) необходимо записать:

Способ 1

Type mas=array[1..5,1..7] of integer;

Способ 2

Var mas:array[1..5,1..7] of integer;

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

For i:=1 to 5 do {перебор строк матрицы}

For j:=1 to 7 do {перебор столбцов (ячеек) в строке}

Т.е. значение индекса строки (i) увеличится только в том случае, если индекс столбца (j) дойдет до своего конечного значения (в примере j = 7).

При такой организации перебора элементов массива процесс перебора будет проходить по следующей схеме:

Рисунок 3. Процесс перебора элементов двумерного массива

Ход выполнения:

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

For i:=1 to n do

Begin

For j:=1 to n do

Write(mas[i,j],’ ‘);

Writeln;

End;

4. Обработка квадратных матриц

Если количество строк массива равно количеству столбцов, то такой массив называется квадратной матрицей. При работе с квадратной матрицей, в отличие от обычного двумерного массива, можно выделить:

• диагонали (главная, побочная);
• элементы, расположенные над и под диагоналями;
• четверти матрицы.

Здесь первая цифра номера элемента обозначает номер строки матрицы (i), вторая цифра – номер столбца (j)

Для определения элементов, входящих в любой из перечисленных разделов, существует формула, основными составляющими которой являются i – номер строки, j – номер столбца и N – размерность массива. Например, для определения элемента с номером 43, расположенного под побочной диагональю можно использовать формулу i+j>N+1, где i=4, j=3, N=5, таким образом, получаем 4+3>5+1.

Рисунок 4. Диагонали двумерного массива

4.1 Определение диагоналей массива

Таким образом, в матрице, представленной в п. 4, элементы с номерами 11, 22, 33, 44 и 55 являются элементами главной диагонали. Элементы с номерами 15, 24, 33, 42, 51 – элементы побочной диагонали.

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

i < j

i+j<N+1

i > j

i+j>N+1

Рисунок 5. Расположение элементов по отношению к диагоналям

Элементы 12, 13, 14, 15, 23, 24, 25, 34, 35 и 45 расположены над главной диагональю, 21, 31, 32, 41, 42, 43, 51, 52, 53, 54 расположены под главной диагональю. Элементы 11, 12, 13, 14, 21, 22, 23, 31, 32 и 41 расположены над побочной диагональю, 25, 34, 35, 43, 44, 45, 54, 53, 54, 55 расположены под побочной диагональю.

4.2 Определение четвертей матрицы

Относительно обеих диагоналей элемент массива может находиться в одной из четвертей.

12, 13, 14, 23 – элементы первой четверти

25, 34, 35, 45 – элементы второй четверти

43, 52, 53, 54 – элементы третьей четверти

21, 31, 32, 41 – элементы четвертой четверти

Рисунок 6. Определение четвертей матрицы

Используя правила, представленные на рисунке 6, очень легко можно программным путем формировать матрицы требуемого вида.

Например, сформировать матрицу N × N вида:

Var

mas:array[1..100,1..100] of integer; i,j,n:integer;

Begin

Writeln(‘Введите размерность массива’);

Readln(n);

For i:=1 to n do {заполняем массив в соответствии с правилами}

For j:=1 to n do

Begin

If i=j then mas[i,j]:=4;

If i+j<N+1 then mas[i,j]:=5;

If (i<j) and (i+j<N+1) then mas[i,j]:=0;

If (i<j) and (i+j>N+1) then mas[i,j]:=2;

If (i>j) and (i+j>N+1) then mas[i,j]:=3;

If (i>j) and (i+j<N+1) then mas[i,j]:=4;

End;

For i:=1 to n do {выводим полученный массив на экран в виде таблицы}

Begin

For j:=1 to n do

Write(mas[i,j],’ ‘);

Writeln;

End;

End.

5. Открытые массивы

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

Например,

Вычислить максимальный элемент в массиве

function Max (Var Mas: array of integer): integer;

Var Ma : integer;

i : Byte;

Begin

Ma : = Mas [0];

for i : = 1 to High (Mas) do

if Ma < Mas [i] then

Ma : = Mas [i];

Max : = Ma

End.

6. Примеры решения задач

1. Нахождение сумм и произведений элементов массива. 

Пример 1. Задан массив A, содержащий 100 целых чисел. Найти сумму элементов этого массива. Фрагмент кода, решающего эту задачу

// сумма элементов массива A из 100 целых чисел

int A[100];

int suma; // переменная, содержащая сумму

int i; // дополнительная переменная

// ввод массива A

// ...

// Вычисление суммы

suma = 0; // обнулить сумму

for (i=0; i<100; i++)

suma += A[i];

Перебор всех элементов массива выполняется в цикле for.

Переменная sum сохраняет результирующее значение суммы элементов массива. Переменная i есть счетчиком, определяющим индекс элемента массива A[i].

Пример 2. Задан массив B, содержащий 20 вещественных чисел. Найти сумму элементов массива, которые лежат на парных позициях. Считать, что позиции 0, 2, 4 и т.д. есть парными.

// сумма элементов массива B

// лежащих на парных позициях

float B[20];

float sum; // переменная, содержащая сумму

int i; // дополнительная переменная

// ввод массива

// ...

// Вычисление суммы

sum = 0; // обнулить сумму

for (i=0; i<20; i++)

if ((i%2)==0)

sum += B[i];

В этом примере выражение

(i%2)==0

определяет парную позицию (парный индекс) массива B. Если нужно взять нечетные позиции, то нужно написать

(i%2)==1

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

// сумма положительных элементов массива

int A[50];

int sum; // переменная, содержащая сумму

int i; // дополнительная переменная

// ввод массива

// ...

// Вычисление суммы

sum = 0; // обнулить сумму

for (i=0; i<50; i++)

if (A[i]>0)

sum = sum + A[i];

2. Нахождение максимального (минимального) элемента массива.

Пример 1. Задан массив A, содержащий 100 целых чисел. Найти сумму элементов этого массива. Фрагмент кода, решающего эту задачу

// сумма элементов массива A из 100 целых чисел

int A[100];

int suma; // переменная, содержащая сумму

int i; // дополнительная переменная

// ввод массива A

// ...

// Вычисление суммы

suma = 0; // обнулить сумму

for (i=0; i<100; i++)

suma += A[i];

Перебор всех элементов массива выполняется в цикле for.

Переменная sum сохраняет результирующее значение суммы элементов массива. Переменная i есть счетчиком, определяющим индекс элемента массива A[i].

Пример 2. Задан массив B, содержащий 20 вещественных чисел. Найти сумму элементов массива, которые лежат на парных позициях. Считать, что позиции 0, 2, 4 и т.д. есть парными.

// сумма элементов массива B

// лежащих на парных позициях

float B[20];

float sum; // переменная, содержащая сумму

int i; // дополнительная переменная

// ввод массива

// ...

// Вычисление суммы

sum = 0; // обнулить сумму

for (i=0; i<20; i++)

if ((i%2)==0)

sum += B[i];

В этом примере выражение