Операції з масивами Базові операції обробки одновимірних масивів

Обробкаелементіводновимірних масивів, зазвичай, виконується в цикліfor. При цьому, якправило,індекси елементів масиву використовуються як параметри відповідного циклу.

До базових операцій обробки одновимірних масивів відносять:

• введення-виведення масиву, його ініціалізацію;

• пошук максимального або мінімального елемента масиву;

• обчислення узагальнюючих характеристик (сум елементів, їх добутків тощо);

• пошук заданого елемента;

• перестановку елементів або обмін значеннями між елементами масиву;

• вставку та видалення елемента масиву тощо.

Основні способи ініціалізації масивів:

• визначення масиву,

• присвоєння значень,

• введення значень з клавіатури.

Наприклад,

for (int i=0; i<n; i++)

scanf("%f", А[і]]); // введення елемента масива А

При написанні учбових програм для створення масивів часто використовуються методи присвоєння елементам масивів випадкових чисел:

• використання функцій random і randomize (описані у заголовному файліstdlib.h);

• використання функцій rand і srand (описані у заголовному файліstdlib.h).

Функція random(n) служить для генерації цілого випадкового числа із діапазону (0¸n-1), функція randomize - для ініціалізації генератора випадкових чисел. Більш уживаним уС/С++є використання функційrand і srand. Функціяrandвикористовується для генерації цілого випадкового числа із діапазону (0¸RAND_MAX). Задання певного діапазону генерації цілих чисел здійснюється за формулою:

rand( )%b + a,

де b - коефіцієнт масштабування, a - величина здвигу.

Функція srandслужить для ініціалізації генератора випадкових чисел.

Наприклад,

cin >> n;

srand(n);

for (int i=0; i< n; i++)

m[i]= rand()%7 + 1; // генерація цілого числа із діапазону 1..7

Пошук максимального значення передбачає: деякій змінній max присвоюється значення першого елемента масиву; потім виконується цикл, який послідовно порівнює кожен елемент масиву із поточним значенням змінної max; якщо значення поточного елемента перевищує значення max, воно присвоюється цій змінній. Аналогічно знаходиться мінімальне значення масиву.

Пошук в масиві за певним ключем полягає у визначенні елементів масиву, для яких виконується деяка умова. В неупорядкованому масиві пошук можна здійснити лише за допомогою перегляду всього масиву. Такий пошук називають лінійним.

Перестановка або обмін значеннями між двома елементами одновимірного масиву здійснюється аналогічно до обміну значеннями між двома змінними (рис. 2). Основні кроки алгоритму:

1. Значення одного із елементів, що обмінюються місцями, зберігається в допоміжній змінній.

2. Значення іншого елемента присвоюється першому елементу.

3. Значення допоміжної змінної присвоюється другому елементу.

Рис. 2. Схема перестановки елементів масиву

Вирішення задач вставки-видалення елементів масиву, передбачає зсув певних елементів масиву. Так, перед тим як вставити до масиву новий елемент, для нього слід звільнити місце (рис. 3). З цією метою усі елементи, починаючи із місця вставки, до кінця масиву, зсуваються на одну позицію праворуч (у напрямку кінця масиву):

Рис. 3. Вставка елемента в масив

Під час видалення певного елемента із масиву, слід зсунути на одну позицію вліво частину масиву, що розташована праворуч від цього елемента (рис. 4).

Рис. 4. Видалення елемента із масиву

Для циклічного зсуву елементів масиву вправо слід зберегти в резервній змінній останній елемент та на одну позицію вправо перемістити підмасив, починаючи з першого елемента і завершуючи передостаннім. Потім записати на місце першого елемента той, який раніше був останнім. Коли виконують циклічний зсув вліво, у резервній змінній зберігають перший елемент, зсувають на одну позицію вліво підмасив, починаючи з другого елемента і до останнього, та записують на місце останнього елемента той, який раніше був першим.

Сортування(упорядкування) масиву — це зміна порядку розташування його елементів за певним критерієм.

Розрізняють методи внутрішнього та зовнішнього сортування. Методи внутрішнього сортування передбачають обробку масивів, які повністю розташовані в ОП (без використання допоміжних масивів). Методи зовнішнього сортування передбачають обробку великих масивів даних, які зберігаються на зовнішніх носіях.

Основні методи внутрішнього сортування:

• сортування обміном (бульбашкове сортування),

• сортування вибором,

• сортування вставками тощо.

Сутність сортування обміном: послідовно порівнюються пари сусідніх елементів x_k і x_k+1 (k = 1, 2, 3, ..., n -1) і якщо x_k >x_k+1 (або x_k < x_k+1), то вони переставляються; тим самим найбільший (найменший) елемент виявиться на своєму місці наприкінці масиву; цикл перегляду елементів повторюється, доки вони не стануть упорядкованими.

Сутність сортування вибором: шукається максимальний (мінімальний) елемент і переноситься в початок масиву; потім ця операція застосовується до всіх елементів, крім першого і т.ін.

Сутність сортування вставками: якщо перші k елементів масиву вже впорядковані, наприклад, по зростанню, то береться (k+1)-й елемент і розміщається серед перших k елементів так, щоб упорядкованими виявилися вже k+1 перших елементів; цей алгоритм застосовується при k від 1 до n-1.

Методи вставки та вибору за характеристиками приблизно еквівалентні, метод обміну поступається перед ними швидкодією.

Основні методи зовнішнього сортування:

• швидке сортування (метод Хоара),

• сортування злиттям тощо.

Базові операції обробки масивів слід реалізовувати у вигляді функцій, які згодом можуть бути використаніяк «архітектурні блоки» при розв’язанні більш складних задач.

Приклад. Знаходження суми додатних елементів цілочисельного масиву.

#include <stdlib.h>

#include <stdio.h>

#include <iostream>

using namespace std;

const int n=7; // розмірність вихідного масиву

int A[n]; // вихідний масив

void input_a(); // ініціалізація масиву

void output_a(); // виведення масиву

int sum(); // обчислення суми елементів масиву

//----------------------- головна функцiя ----------------------------------------------

int main()

{ srand(time(NULL));

input_a();

output_a();

printf("s = %2d \n", sum());

system("pause");

}

//----------------------- генерація масиву -------------------------------------------

void input_a()

{ for (int i=0; i<n; i++)

А[і] = rand()%19 - 9 ;

}

//----------------------- виведення масиву ---------------------------------------------

void output_a()

{ cout << “A:”;

for (int i=0; i<n; i++)

printf("%3d", А[і]);

}

//---------------------- обчислення суми елементів масиву ------------------------------------

int sum()

{ int s=0;

for (int i=0; i<n; i++)

if (А[і] >=0) s += А[і];

return s;

}

10