Вам нужно хранить тысячу целых чисел. Вы действительно хотите объявлять int a, b, c... вплоть до z, а затем продолжать? Нет. Это утомительно и чревато ошибками. Вместо этого используйте массив.
Массив — это коллекция значений одного типа. Он упаковывает их в единый блок памяти. В C вы объявляете его так:
int a[5];
Всё. Пять целых чисел. Готово к работе.
Почему массивы в C начинаются с нуля
Вот тот нюанс, на котором спотыкаются новички. Массивы в C индексированы с нуля.
Если вы объявите int a[5], у вас будет пять слотов. Но они пронумерованы как 0, 1, 2, 3 и 4. Элемента a[5] не существует. Если вы попытаетесь обратиться к a[5], вы будете читать память, которая не принадлежит вашему массиву. C не остановит вас. Он просто вернет мусор или вызовет сбой. Это особенность, а не ошибка. Это быстро. Это также опасно.
Вы обращаетесь к элементам с помощью квадратных скобок. 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 станет понятнее. Игнорируйте индексацию с нуля, и вы потратите часы на отладку сбоя, который произошел три шага назад.
