Одновимірні масиви
Потреба у масивах виникає тоді, коли в оперативній пам'яті зберігається велика, але визначена кількість однотипних даних. Наприклад, можна задати масив щоденних значень температури повітря протягом місяця з метою визначення середньої температури або масив логічних значень, що зображуватиме наявність квитків на кіносеанс на всі місця у кінозалі. Розрізняють одновимірні та багатовимірні масиви. Зокрема, масив температур є одновимірним, а масив квитків - двовимірним.Масив – структурний тип, який об’єднує в собі набір елементів деякого типу, об’єднаних спільним ім’ям (ім’ям масиву).
Поняття масиву та його властивості
Одновимірний масив — це послідовність однотипних даних.Уважно проаналізувавши це означення, можна зробити висновок, що масив фактично поєднує в собі дві структури: множину елементів і заданий на цій множині порядок. Усі елементи масиву мають один і той самий тип, що називається базовим. З іншого боку, порядок теж визначається набором значень одного й того самого типу, що називається індексним, а самі ці значення називаються індексами. Кожному елементу масиву відповідає певний індекс. Індексний тип має бути простим порядковим типом даних. Кількість елементів в одновимір-ному масиві називається його розмірністю, або довжиною. Тип масиву — це структурований тип даних, множина допустимих значень котрого складається з усіх масивів, для яких зафіксовано:
- розмірність;
- базовий тип;
- індексний тип;
- множину значень індексу.
Загальний вигляд створення масиву: вказуємо
- ім’я масиву;
- тип елементів;
- кількість елементів.
Оскільки масив потребує виділення динамічної пам’яті, то у класичному випадку треба використовувати команду new, аналогічно випадку з типом String. Одномірні масиви ще називають лінійними.
Нумерація елементів у масиві (як і в рядках) починається з 0-го. Довжина масива (кількість елементів) визначається полем .length (на відміну від методу .length() для рядків).
Оголошення масиву:
тип[] ім'я = new тип[розмір];
тип[] ім'я = {ел0, ел1, …, елN};
Приклади оголошення та створення масивів:
int[] a;
double[] ar1;
double ar2[];
int[] mas1 = {10,20,30};
int[] mas2 = new int[3];
int [ ] a = new int [2]; // масив з 2-х цілих елементів, ім’я масиву – a
int a [ ] = new int [2]; // і так можна
String [ ]sm = new String[10]; // масив рядків
a = new int[10]; // масив із 10 елементів типа int int n = 5; ar1 = new double[n]; // масив із 5 елементів double ar2 = {3.14, 2.71, 0, -2.5, 99.123}; // масив із 6 елементів типа double
У Java передбачено створення масиву одночасно з ініціалізацією, з якої випливає і розмір масивуint [ ] mas = {10, 20, 30, 40, 50}
Наприклад, так можна вивести на екран елементи будь-якого масиву з ім'ям ar2:
for(int i = 0; i <= ar2.length - 1; i++) { System.out.print(ar2[i] + " "); }Для стислості зручніше міняти нестроге нерівність на строгу, тоді не потрібно буде віднімати одиницю з розміру масиву. Давайте заповнимо масив цілими числами від 0 до 9 і виведемо його на екран:
for(int i = 0; i < ar1.length; i++) {ar1[i] = Math.floor(Math.random() * 10); System.out.print(ar1[i] + " "); }
Зверніть увагу, на кожному кроці циклу ми спочатку відправляли випадкове значення в елемент масиву з i-м індексом, а потім цей же елемент виводили на екран. Але два процеси (наповнення і виводу) можна було зробити і в різних циклах. наприклад:for(int i = 0; i < ar1.length; i++) { ar1[i] = Math.floor(Math.random() * 9); } for(int i = 0; i < ar1.length; i++) { System.out.print(ar1[i] + " "); }
Сортування масиву
Сортуванням називається такий процес перестановки елементів масиву, коли всі його елементи шикуються по зростанням або за спаданням.Сортувати можна не тільки числові масиви, а й, наприклад, масиви рядків (за тим же принципом, як розставляють книги на бібліотечних полицях). Взагалі сортувати можна елементи будь-якого безлічі, де задано відношення порядку.
Існують універсальні алгоритми, які виконують сортування незалежно від того, яким було початковий стан масиву. Але крім них існують спеціальні алгоритми, які, наприклад, дуже швидко можуть впорядкувати майже впорядкований масив, але погано справляються з сильно перемішаним масивом (або взагалі не справляються). Спеціальні алгоритми потрібні там, де важлива швидкість і вирішується конкретне завдання.
Сортування вибором
Розглянемо приклад сортування за зростанням. Тобто на початковій позиції в масиві повинен стояти мінімальний елемент, на наступній - більший або дорівнює і т. Д., На останньому місці повинен стояти найбільший елемент.Суть алгоритму така. У всьому відшукуємо мінімальний елемент, міняємо його місцями з початковим. Потім у решти масиву (т. Е. Серед всіх елементів крім початкового) знову відшукуємо мінімальний елемент, міняємо його місцями вже з другим елементом у масиві. І так далі.
Ілюстрація:
Код:
for (int i = 0; i < a.length; i++) { /* Припускаємо, що початковий елемент аналізованого фрагмента і буде мінімальним. */ int min = a[i]; // Передбачуваний мінімальний елемент int imin = i; // Індекс мінімального елемента /* Переглядаємо залишився фрагмент масиву і шукаємо там * елемент, менший запропонованого мінімуму. */ for (int j = i+1; j < a.length; j++) { /* Якщо знаходимо новий мінімум, то запам'ятовуємо його індекс. І оновлюємо значення мінімуму.*/ if (a[j] < min) { min = a[j]; imin = j; } } /* Перевіряємо, чи знайшовся елемент менше, ніж той, що на поточній позиції. Якщо знайшовся, то міняємо елементи місцями.*/
if (i != imin) { int temp = a[i]; a[i] = a[imin]; a[imin] = temp; } }
Сортування методом бульбашки
Суть алгоритму така. Якщо пройдемося по будь-якому масиву встановивши правильний порядок в кожній парі сусідніх елементів, то після того проходу на останньому місці масиву гарантовано буде стояти потрібний елемент (найбільший для сортування за зростанням або найменший для сортування за спаданням). Якщо ще раз пройтися по масиву з такими ж перетвореннями, то й на передостанньому місці гарантовано виявиться потрібний елемент. І так далі.
Наприклад:
2 9 1 4 3 5 2 → порядок правильний, не буде перестановки
2 9 1 4 3 5 2 → 2 1 9 4 3 5 2
2 1 9 4 3 5 2 → 2 1 4 9 3 5 2
2 1 4 9 3 5 2 → 2 1 4 3 9 5 2
2 1 4 3 9 5 2 → 2 1 4 3 5 9 2
2 1 4 3 5 9 2 → 2 1 4 3 5 2 9
Дано масив з 10 випадкових цілих чисел, кожне з яких – з проміжку (-20; 20).
1. Вивести на екран усі від’ємні елементи.
2. Знайти суму додатних елементів.
3. Підрахувати кількість нульових елементів.
Розв’язання. У програмі спочатку ініціалізуємо масив випадковими числами, відповідно до умови задачі. Потім покажемо масив на екрані. Це допоможе перевірити правильність виконання обрахунків. Виконаємо обчислення та відобразимо їх.
Лістинг
Вхідний масив:
a[0]=10
a[1]=10
a[2]=12
a[3]=16
a[4]=1
a[5]=-16
a[6]=-1
a[7]=17
a[8]=9
a[9]=2
Від'ємні елементи:
a[5]=-16
a[6]=-1
Сума додатних: 77
Кількість нульових: 0
2 9 1 4 3 5 2 → 2 1 9 4 3 5 2
2 1 9 4 3 5 2 → 2 1 4 9 3 5 2
2 1 4 9 3 5 2 → 2 1 4 3 9 5 2
2 1 4 3 9 5 2 → 2 1 4 3 5 9 2
2 1 4 3 5 9 2 → 2 1 4 3 5 2 9
Код:
/* Зовнішній цикл постійно звужує фрагмент масиву, який розглядатиметься, адже після кожного проходу внутрішнього циклу на останньому місці фрагмента буде опинятися потрібний елемент (його не треба розглядати знову).*/ for (int i = a.length - 1; i >= 2; i--) { /* У змінній sorted ми будемо зберігати ознаку того, чи відсортований масив. Перед кожним проходом внутрішнього циклу будемо припускати, що відсортований, але якщо здійснимо хоч одну перестановку, то значить ще не кінця відсортований. Цей прийом, що спрощує сортування, називається критерієм Айверсона.*/
boolean sorted = true; /* У внутрішньому циклі ми розходимося по фрагменту масиву, який визначається зовнішнім циклом. У цьому фрагменті ми встановлюємо правильний порядок між сусідніми елементами, так попарно обробляючи весь фрагмент.*/
for (int j = 0; j < i; j++) { /* Якщо порядок сусідніх елементів неправильний, то їх треба поміняти місцями. І запам'ятати, що була перестановка. */ if (a[j] > a[j+1]) { int temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; sorted = false; } } /* Якщо масив відсортований (тобто не було жодної перестановки у внутрішньому циклі, значить можна припиняти роботу зовнішнього циклу.*/ if(sorted) { break; } }
Приклад. Обробка лінійного масивуДано масив з 10 випадкових цілих чисел, кожне з яких – з проміжку (-20; 20).
1. Вивести на екран усі від’ємні елементи.
2. Знайти суму додатних елементів.
3. Підрахувати кількість нульових елементів.
Розв’язання. У програмі спочатку ініціалізуємо масив випадковими числами, відповідно до умови задачі. Потім покажемо масив на екрані. Це допоможе перевірити правильність виконання обрахунків. Виконаємо обчислення та відобразимо їх.
Лістинг
package prog3; public class Prog3 { public static void main(String [ ]args) { int [ ] a = new int[10]; // ініціалізація масиву випадковими цілими for (int i=0; i<a.length; i++) { a[i]=(int)(Math.random()*40-20); } // виведення вхідного масиву на екран System.out.println("Вхідний масив:"); for (int i=0; i<a.length; i++) { System.out.println("a["+i+"]="+a[i]); } // будемо рахувати суму додатних - змінна S int S = 0; // для кількості нулів виділимо окрему змінну int k = 0; System.out.println("Від'ємні елементи:"); // проглядаємо кожен елемент масиву for (int i=0; i<a.length; i++) { // якщо елемент від'ємний, показуємо його if (a[i]<0) System.out.println("a["+i+"]="+a[i]); // інакше, якщо додатній - збільшуємо суму S else if (a[i]>0) S=S+a[i]; // в іншому випадку (тобто коли a[i]==0) else k++; } System.out.println("Сума додатних: "+S); System.out.println("Кількість нульових: "+k); } }Приклад результатів роботи програми:
Вхідний масив:
a[0]=10
a[1]=10
a[2]=12
a[3]=16
a[4]=1
a[5]=-16
a[6]=-1
a[7]=17
a[8]=9
a[9]=2
Від'ємні елементи:
a[5]=-16
a[6]=-1
Сума додатних: 77
Кількість нульових: 0
Більше>> Одновимірні масиви. Поле length.
Лабораторна робота: «Визначення максимального та мінімального елементів масиву»
Лабораторна робота: «Пошук елемента в масиві та визначення кількості повторів елемента»
Література для домашньої роботи:
Шилдт]: с.94 ...97
[Шилдт], ст.196...197
[Еккель], ст. 454...458
[Вязовик], lec09, ст. 1...6
[Хортсман], ст. 116...124
