Вам потрібно зберігати тисячу цілих чисел. Ви дійсно хочете оголошувати int a, b, c... до z, а потім продовжувати? Ні. Це стомлююче і загрожує помилками. Натомість використовуйте масив.
Масив – це колекція значень одного типу. Він пакує їх у єдиний блок пам’яті. У C ви оголошуєте його так:
int a[5];
Все. П’ять цілих чисел. Готовий до роботи.
Чому масиви в C починаються з нуля
Ось той нюанс, на якому спотикаються новачки. Масиви в C індексовані з нуля.
Якщо ви оголосите int a[5], у вас буде п’ять слотів. Але вони пронумеровані як 0, 1, 2, 3 та 4. Елементу a[5] не існує. Якщо ви спробуєте звернутися до a[5], ви читатимете пам’ять, яка не належить вашому масиву. З вас не зупинить. Він просто поверне сміття чи викличе збій. Це особливість, а чи не помилка. Це швидко. Це також небезпечно.
Ви звертаєтесь до елементів за допомогою квадратних дужок. a[0] – це перший елемент. a[4] – останній.
Генерація випадкових чисел в C
Давайте створимо щось корисне. Ми напишемо програму, яка генерує 10 випадкових чисел та сортує їх.
Спочатку потрібні самі числа. У стандартній бібліотеці C є функція rand(), але розглянемо класичну реалізацію, щоб зрозуміти механіку. Цей код використовує лінійний конгруентний генератор, метод книги K&R C.
`
Зверніть увагу на рядок #define MAX 10. Вона створює константу. За згодою константи пишуться великими літерами. Це виділяє їх. Ви повідомляєте масив int a[MAX] поза функцією main. Це робить його глобальною змінною. Вона доступна у будь-якій частині програми.
Змінна rand_seed також є глобальною. Вона починається зі значення 10. Оскільки початкове значення (seed) фіксоване, «випадкові» числа дійсно однакові при кожному запуску програми. Якщо вам потрібна справжня випадковість, необхідно ініціалізувати генератор системним часом. Поки що постійність корисна для налагодження.
Розуміння бульбашкового сортування
Тепер найскладніша частина. Сортування.
Ми будемо використовувати пухирцеве сортування. Це найпростіший алгоритм сортування. Він також найповільніший. Але він вчить вас, як взаємодіють цикли та масиви.
Додайте цей код у вашу функцію main, замінивши коментар про «інші речі»:
`
Що тут відбувається?
Зовнішній цикл виконується MAX-1 разів. Внутрішній цикл виконується менше разів з кожним проходом. Чому? Тому що найбільші числа «спливають» наприкінці масиву з кожним проходом. Перевіряти їх не потрібно.
Усередині внутрішнього циклу ми порівнюємо a[y] з a[y+1]. Якщо лівий елемент більший, ми змінюємо їх місцями. Ми використовуємо тимчасову змінну t для зберігання значення, доки переміщаємо елементи.
«Єдиний простий спосіб по-справжньому зрозуміти, що робить цей код, це виконати його вручну».
Візьміть аркуш паперу. Намалюйте п’ять коробок. Покладіть у них числа. Виконуйте код рядково. Переміщуйте числа. Ви побачите, як великі числа опускаються на дно. Маленькі виринають нагору. Це наочно. Це механічно.
Поширені помилки при роботі з масивами в C
C не тримає вас за руку. Ви зірветесь з краю.
- Відсутність перевірки меж. Якщо ви звернетеся до
a[10]у масиві розміром 10, C не обуриться. Він прочитає будь-яку пам’ять, що знаходиться поряд. Це призводить до тонких помилок, які важко знайти. - Виклики функцій вимагають дужок. Ви повинні писати
x = rand();. Якщо ви напишетеx = rand;, ви надаєтеxадресу пам’яті функції, а не її результат. Це компілюється. Це ламає програму.
Спробуйте це
Чи не просто читайте. Напишіть код.
- Змініть цикл, який заповнює масив, на один рядок. Чи зможете ви це зробити?
- Винесіть логіку бульбашкового сортування в окрему функцію. Назвіть її
void bubble_sort(). Перемістіть змінніx,yтаtвсередину цієї функції. Вони стануть локальними. Масивaє глобальним, тому передавати його не потрібно. - Змініть
rand_seedна різні значення. Спостерігайте, як змінюється висновок.
Масиви – це фундамент. Вони є будівельними блоками структур даних. Освойте їх, і решта C стане зрозумілішою. Ігноруйте індексацію з нуля, і ви витратите годинник на налагодження збою, який стався три кроки тому.
