C _Учебник_МОНУ

2) Циклічно порівнюються два елементи – a[i] та a[j]. За рахунок того, що після кожного проходження циклом один з елементів ставатиме на своє місце, можна скоротити кількість повторювань вкладеного циклу, розпочинаючи вкладений цикл не з 0-го елемента, а з (i + 1)-го.

for (i=0; i<n-1; i++) for (j=i+1; j<n; j++) if (a[i] > a[j])

{tmp = a[i]; a[i] = a[j]; a[j] = tmp; }

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

Сортування елементів масиву організуємо в окремій функції. Слід звернути увагу на заголовок цієї функції:

void sort(float a[], int n)

де sort – ім‟я функції, за яким її можна буде викликати;

float a[], int n – параметри функції: масив дійсних чисел а (який функція сортуватиме) і кількість елементів масиву n;

void – тип результату, який вказує на те, що функція виконуватиме сортування і змінюватиме масив, але жодних інших обчислень вона не виконуватиме і нічого, окрім зміненого масиву, повертати немає потреби.

Викликати розглянуту функцію можна, якщо написати ім‟я функції й у круглих дужках зазначити два фактичні параметри: ім‟я масиву та кількість його елементів, наприклад:

Текст функції та основної програми: void sort(float a[], int n)

{tmp = a[i]; a[i] = a[j];

a[j] = tmp;

}

}

//------------------------------------------

void __fastcall TForm1::Button1Click(TObject *Sender)

{int n,i; float a[15];

// Зчитування кількості заповнених рядків Memo1 n = Memo1->Lines->Count;

if (n>15) n=15; for (i=0; i<n; i++)

a[i]=StrToFloat(Memo1->Lines->Strings[i]);

sort(a, n); // Виклик функції

Memo2->Clear(); for (i=0; i<n; i++)

Memo2->Lines->Add(FloatToStr(a[i]));

}

Д р у г и й с п о с і б Аналізуючи попередній алгоритм сортування, можна скоротити кількість

проходжень по масиву. В наведеному нижче прикладі функції sort2() запропоновано алгоритм сортування, де булева змінна ok відіграє роль своєрідного ліхтарика, який “вмикається” (ok=1) лише в разі переставляння сусідніх елементів, тобто є сигналом, що ще не всі елементи є упорядковано і треба повторювати перевірки.

Текст функції:

void sort2(float a[], int n)

{int i; float tmp; bool ok=1; while (ok)

{ok=0;

for (j=0; j<n-1; j++) if (a[j] > a[j+1])

{tmp = a[j]; a[j] = a[j+1]; a[j+1] = tmp; ok = 1;

}

}

}

Перевіримо роботу цього циклу на масиві з 7-ми елементів:

–0.9, –2.1, 6.3, 3, 8, 5.1, 30.

В таблиці показано вигляд масиву після кожного проходження масивом.

Отже, на відміну від попереднього способу сортування, кількість проходжень циклом істотно скорочується, залежно від початкового розташування елементів. Останнє проходження циклом можна назвати холостим, оскільки перестановок у ньому немає, а отже, булева змінна ok не “вмикається” (ok=1), що є сигналом, що всі елементи упорядковано, – і відбувається вихід з циклу while.

Т р е т і й с п о с і б

Доволі поширеним є ще один спосіб сортування за допомогою мінімального елемента, алгоритм якого реалізовано у наведеній нижче функції sort3(). Його суть полягає в тому, що з послідовності обирають мінімальний (чи максимальний) елемент і переставляють його до початку (кінця) масиву, змінюючи місцями з перевірюваним. Кількість перестановок – (n+1)/2.

Розглянемо цей алгоритм для сортування за зростанням масиву з 7-ми елементів:

5, –1.3, –7.1, 4.8, 2, 7, 1.6.

Щоб елементи було розташовано за зростанням, слід віднайти мінімальний елемент масиву і поставити його на перше місце. Після цього повторити аналогічні дії для решти елементів (окрім першого, який вже стоїть на своєму місці). У таблиці на кожній ітерації жирним позначено мінімальний елемент, рамкою виокремлено елементі, які беруть участь у подальшому пошуку мінімального елемента і перестановках.

void sort3(float a[], int n) //n – кількість елементів масиву

{int i, j, imin; float tmp; for (i=0; i<n-1; i++)

{imin=i;

for (j=i+1; j<n; j++)

if (a[imin] > a[j]) imin=j; tmp = a[i];

a[i] = a[imin];

a[imin] = tmp;

}

}

void __fastcall TForm1::Button1Click (TObject *Sender)

{float a[14];

for (int i=0; i<14; i++) a[i]=StrToFloat(Memo1->Lines->

Strings[i]);

Perehod (a, 14);

Memo2->Clear();

for (i=0; i<14; i++) Memo2->Lines->Add(FloatToStrF(a[i],

ffGeneral, 5, 2));

}

Приклад 5.11 У послідовності з 12-ти цілих чисел непарні елементи (за значенням, а не за індексом) замінити на одиниці, а парні елементи – на нулі.

void Zamina(int V[12])

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

if (V[i] % 2) V[i]=1; else V[i]=0;

}

void __fastcall TForm1::Button1Click(TObject *Sender)

{int a[12], i;

for (i=0; i<12; i++) a[i]=StrToInt(StringGrid1->Cells[i][0]);

Zamina(a);

for (i=0; i<12; i++) StringGrid2->Cells[i][0]=IntToStr(a[i]);

}

Приклад 5.12 Обчислити середнє арифметичне усіх елементів одновимірного масиву з 10-ти дійсних чисел.

5.3 Двовимірні масиви

5.3.1 Організація двовимірних масивів

Доволі часто буває недостатньо однієї вимірності масиву для зручного зберігання даних. Приміром, якщо є потреба зберігати результати сесії цілої групи (30 студентів): оцінки з п‟яти предметів. На папері ці результати зазвичай заносяться до таблиці, кожний рядок якої є оцінками одного студента по всіх предметах, а кожний стовпчик – оцінками групи з конкретного предмета:

Так само згадані дані можуть зберігатися і в масиві, де номери рядків означають номери студентів, а номери стовпчиків – номери предметів:

Цей масив є двовимірний: номер рядка визначає оцінки кожного студента, а номер стовпчика – предмет. Якщо в одному масиві зберігати оцінки всіх груп разом, то це буде вже тривимірний масив, і елемент визначатиметься ще й номером групи.

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

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

Багатовимірний масив оголошується у програмі в такий спосіб:

<тип> <ім‟я> [ <розмір1>] [ <розмір2>] … [ <розмірN>];

Кількість елементів масиву дорівнює добуткові кількості елементів за кожним індексом. У прикладі

int a[3][4];

оголошено двовимірний масив з 3-х рядків та 4-х стовпчиків (12-ти елементів) цілого типу:

a[0][0], a[0][1], a[0][2], a[0][3], a[1][0], a[1][1], a[1][2], a[1][3], a[2][0], a[2][1], a[2][2], a[2][3];

Під масив надається пам‟ять, потрібна для розташування усіх його елементів. Елементи масиву один за одним, з першого до останнього, запам‟ятовуються у послідовно зростаючих адресах пам‟яті так само, як і елементи одновимірного масиву. Наприклад, масив зберігається у пам‟яті у такий спосіб:

Масив оцінок з п‟яти предметів для групи з 30-ти студентів можна оголосити, наприклад, у такий спосіб:

int ocіnki[30][5];

Якщо цей масив зберігатиме оцінки з наведеної таблиці, то до оцінки з математики першого в групі студента з прізвищем Антонов можна звернутися у такий спосіб: ocіnki[0][0], до оцінки Бондаря з інформатики: ocіnki[1][2].

Наведемо ще кілька прикладів оголошення масивів:

// Двовимірний масив з 10 3=30 елементів символьного типу double Mas3 [4][5][4];

// Тривимірний масив з 4 5 4=80 елементів дійсного типу

При оголошенні масиву можна ініціалізовувати початкові значення його елементів, причому необов‟язково усіх, наприклад:

1)int w[3][3]={ { 2, 3, 4 },{ 3, 4, 8 },{ 1, 0, 9 } };

2)float C[4][3]={1.1, 2, 3, 3.4, 0.5, 6.8, 9.7, 0.9};

3)float C[4][3]={{1.1, 2, 3},{3.4, 0.5, 6.8},{ 9.7, 0.9}};

4)float C[4][3]={{1.1, 2},{3, 3.4, 0.5},{6.8},{9.7, 0.9}};

Упершому прикладі оголошено й ініціалізовано масив цілих чисел w[3][3]. Елементам масиву присвоєно значення зі списку: w[0][0]=2,

w[0][1]=3, w[0][2]=4, w[1][0]=3 тощо. Списки, виокремлені у фігурні дужки, відповідають рядкам масиву.

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

Багатовимірні масиви можна оголошувати й зі створюванням типу користувача (докладніше див. розд. 11):

typedef <тип_даних> <і‟мя_типу>[<розмір1>][<розмір2>]…[<розмір n>]; <і‟мя_типу> <і‟мя_масиву> ;

Наприклад, створимо тип з ім‟ям matr як масив додатних цілих чисел з 10ти рядків і 7-ми стовпчиків та оголосимо два масиви – M1 і M2 – створеного типу:

typedef unsigned short matr[10][7]; matr M1, M2;

Для оголошення масивів можна також використовувати типізовані конс- тант-масиви, які дозволяють водночас оголосити масив і задати його значення в розділі оголошень констант, наприклад:

const int arr[2][5] = {{9, 3, 0, 12, –5},{ –7, 23, 2, 4, 0}};

але змінювати значення елементів констант-масивів у програмі є неприпустимо. В С++ можна використовувати перетин масиву (section). Це поняття подібно до поняття мінору матриці в математиці. Перетин формується внаслідок вилучення однієї чи кількох пар квадратних дужок. Пари квадратних дужок можна відкидати лише справа наліво й лише послідовно. Перетини масивів використовуються при організації обчислювального процесу в функціях мовою

С++, розроблюваних користувачем. Приклади:

1) int х[5][3];

Якщо при звертанні до певної функції написати х[0], то передаватиметься нульовий рядок масиву х.

2) int y[2][3][4];

При звертанні до масиву y можна записати, наприклад, y[1][2] – і буде передаватися вектор з чотирьох елементів, а звертання y[1] надасть двовимірний масив розміром 3 4. Не можна писати y[2][4], вважаючи на увазі, що передаватиметься вектор, тому що це не відповідає обмеженню, накладеному на використання перетинів масиву.

5.3.2 Введення-виведення двовимірних масивів

Виведення елементів двовимірних масивів

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

У поданих нижче прикладах виведення елементів масиву використовуватимуться змінні, оголошені в такий спосіб:

int В[5][3]; int i, j; AnsiString st;

До компонента Memo можна виводити масиви рядками, відокремлюючи пробілами елементи в рядку. В компоненті Memo можна використовувати смуги прокручування, для чого властивості ScrollBar слід задати значення ssBoth

чи то ssVertical.

Memo1->Clear(); for (i=0; i<5; i++)

{st="" ;

for (j=0; j<3; j++)

st += FormatFloat("0.00",B[i][j]) + " "; Memo1->Lines->Add(st);

}

До компонента ListBox виведення масиву організовують так само, як і для компонента Memo, лише замість властивості Lines слід використовувати властивість Items.

Приміром, замість

Memo1->Lines->Add(st);

слід записати

ListBox->Items->Add(st);

Компонент StringGrid (таблиця рядків) має вигляд таблиці з комірками і розташований на закладці Additional палітри компонентів. У кожній комірці компонента StringGrid можна розмістити величину рядкового типу, причому задану кількість перших рядків та стовпчиків може бути зафіксовано і при прокручуванні вони залишатимуться на місці. У перебігу створювання форми не можна задавати значення комірок таблиці, оскільки відповідна властивість Cells є доступна лише програмно.

Приміром, для виведення матриці В розміром 5 3 компонентові StringGrid1 слід задати властивості, наведені в табл. 5.1. Для виведення матриці у комірки StringGrid треба організовувати цикли по номерах рядків та стовпчиків. Приклад виведення матриці float В[5][3]до компонента StringGrid1:

for (i=0;i<5;i++) for (j=0;j<3;j++)

StringGrid1->Cells[j+1][i+1]=FormatFloat("0.00", B[i][j]);