Массивы

1. Массивы Массив – это группа ячеек памяти одинакового типа, расположенных рядом и имеющих общее имя. Каждая ячейка в группе имеет уникальный номер. При работе с массивами надо научиться решать три задачи:  выделять память нужного размера под массив  записывать данные в нужную ячейку  читать данные из ячейки Объявление массива Чтобы использовать массив, надо его объявить – выделить место в памяти. Типом массива называется тип массива это тип входящих в него элементов. Массивы могут быть разных типов — int, float, char, и т.д. Массив объявляют так же, как и обычные переменные, но после имени массива в квадратных скобках записывается его размер. int A[10], B[20]; float C[12]; // 2 массива на 10 и 20 целых чисел // массив из 12 вещественных чисел При объявлении массива можно сразу заполнить его начальными значениями, перечисляя их внутри фигурных скобок: int A[4] = { 2, 3, 12, 76 }; Если в списке в фигурных скобках записано меньше чисел, чем элементов в массиве, то оставшиеся элементы заполняются нулями. Если чисел больше, чем надо, транслятор сообщает об ошибке. Например, int A[4] = { 2 }; // последние три элементы равны 0 Для повышения универсальности программы размер массива лучше определять через константу. В этом случае для переделки программы для массива другого размера надо только поменять значение этой константы: const int N = 20; main() { int A[N]; ... } // константа // размер массива задан через константу В таблице показаны примеры правильного и неправильного объявления массива. правильно неправильно размер массива укаразмер массива неизвесint A[20]; int A[]; зан явно тен const int N = 20; размер массива – int N = 20; размер массива не моint A[N]; постоянная величина int A[N]; жет быть переменной Обращение к элементу массива Каждый элемент массива имеет свой порядковый номер. Чтобы обратиться к элементу массива, надо написать имя массива и затем в квадратных скобках номер нужного элемента. Важно запомнить одно важное правило: Элементы массивов в языке Си нумеруются с нуля. Таким образом, если в массиве 10 элементов, он содержит элементы: A[0], A[1], A[2], ..., A[9] Номер элемента массива также называется его индексом. Вот примеры обращения к массиву A: x = (A[3] + 5)*A[1]; // прочитать значения A[3] и A[1] A[0] = x + 6; // записать новое значение в A[0] В языке Си не контролируется выход за границы массива, то есть формально вы можете записать что-то в элемент с несуществующим индексом, например в A[345] или в A[-12]. Однако при этом вы стираете какую-то ячейку в памяти, не относящуюся к массиву, поэтому последствия такого шага непредсказуемы и во многих случаях программа «зависает». Ввод с клавиатуры и вывод на экран Как же ввести данные в массив? Существует много способов в зависимости от вашей задачи:  элементы массива вводятся с клавиатуры вручную;  массив заполняется случайными числами (например, для моделирования случайных процессов);  элементы массива читаются из файла;  элементы массива поступают через порт с внешнего устройства (например, сканера, модема и т.п.);  массив заполняется в процессе вычислений. Задача. Ввести с клавиатуры массив из 10 элементов, умножить все элементы на 2 и вывести полученный массив на экран. Чтобы ввести массив в память, надо каждый его элемент обработать отдельно (например, вызвав для него функцию ввода scanf). Ввод с клавиатуры применяется в простейших программах, когда объем вводимой информации невелик. Для ввода массива будем использовать цикл for. Напомним, что массив надо предварительно объявить, то есть выделить под него память. Вводить можно столько элементов массива, сколько ячеек памяти выделено. Помните, что элементы массива нумеруются с нуля, поэтому если массив имеет всего 10 элементов, то последний элемент имеет номер 9. Если пытаться записывать в 10-ый элемент, произойдет выход за границы массива, и программа может работать неверно (а, возможно, и «зависнет»). При вводе массива желательно выдать на экран общую подсказку для ввода всего массива и подсказки для каждого элемента. Для умножения элементов массива на 2 надо снова использовать цикл, в котором за один раз обрабатывается 1 элемент массива. Вывод массива на экран выполняется также в цикле for. Элементы выводятся по одному. Если в конце строки-формата в операторе printf поставить пробел, то элементы массива будут напечатаны в строчку, а если символ \n – то в столбик. #include const int N = 10; main() { // размер массива int i, A[N]; // объявление массива printf("Введите массив A\n"); // подсказка для ввода for ( i = 0; i < N; i ++ ) { printf("Введите A[%d]> ", i ); scanf ("%d", &A[i]); } // цикл по всем элементам // подсказка для ввода A[i] // ввод A[i] for ( i = 0; i < N; i ++ ) // цикл по всем элементам A[i] = A[i] * 2; // умножить A[i] на 2 printf("\nРезультат:\n"); for ( i = 0; i < N; i ++ ) // цикл по всем элементам printf("%d ", A[i]); // вывести A[i] } Заполнение случайными числами Этот прием используется для моделирования случайных процессов, например, броуновского движения частиц. Пусть требуется заполнить массив равномерно распределенными случайными числами в интервале [a,b]. Поскольку для целых и вещественных чисел способы вычисления случайного числа в заданном интервале отличаются, рассмотрим оба варианта. Здесь и далее предполагается, что в начале программы есть строчка const int N = 10; Описание функции-датчика случайных чисел находится в заголовочном файле stdlib.h. Удобно также добавить в свою программу функцию random: int random (int N) { return rand() % N; } которая выдает случайные числа с равномерным распределением в интервале [0,N-1]. Как вы уже знаете из первой части курса, для получения случайных чисел с равномерным распределением в интервале [a,b] надо использовать формулу k = random ( b – a + 1 ) + a; Для вещественных чисел формула несколько другая: x = rand()*(b - a)/RAND_MAX + a; Здесь константа RAND_MAX – это максимальное случайное число, которое выдает стандартная функция rand. В приведенном ниже примере массив A заполняется случайными целыми числами в интервале [-5,10], а массив X – случайными вещественными числами в том же интервале. #include const int N = 10; main() { int i, A[N], a = -5, b = 10; float X[N]; for ( i = 0; i < N; i ++ ) A[i] = random(b-a+1) + a; for ( i = 0; i < N; i ++ ) X[i] = (float)rand()*(b-a)/RAND_MAX + a; // здесь что-то делаем с массивами } Возможно, в этом примере не вполне ясно, зачем перед вызовом функции rand поставлено слово (float). Это связано с тем, что у нас a и b – целые числа. Результат функции rand – тоже целое число. Здесь возможны две проблемы:  При умножении результата функции rand на b-a может получиться очень большое число, которое не поместится в переменную типа int.  В языке Си при делении целого числа на целое остаток отбрасывается, поэтому при делении результат будет неверным. Когда массив заполняется случайными числами, обязательно вывести на экран исходный массив. Задача. Заполнить массив случайными целыми числами в интервале [-10,15], умножить все элементы на 2 и вывести на экран исходный массив и результат. #include #include const int N = 10; int random (int N) { return rand() % N; } main() { int i, A[N]; for ( i = 0; i < N; i ++ ) A[i] = random(26) – 10; // заполнение массива сл. числами printf("n Исходный массив:\n"); // вывод исходного массива for ( i = 0; i < N; i ++ ) printf("%d ", A[i]); for ( i = 0; i < N; i ++ ) // умножить все элементы на 2 A[i] = A[i] * 2; printf("n Результат:\n"); for ( i = 0; i < N; i ++ ) // вывод результата printf("%d ", A[i]); } Простой поиск в массиве Во многих задачах требуется последовательно перебрать все элементы массива и найти нужные нам. Мы рассмотрим четыре таких задачи:     поиск одного заданного элемента; вывод всех элементов, которые удовлетворяют заданному условию; формирование нового массива из всех отобранных элементов; поиск минимального (максимального) элемента. Все эти задачи решаются с помощью цикла, в котором перебираются все элементы массива от начального (0-ого) до конечного (N-1-ого) элемента. Такой поиск называется линейным, поскольку все элементы просматриваются последовательно один за другим. Поиск одного элемента Задача. Определить, есть ли в массиве элемент с заданным значением x, и, если он есть, найти его номер. Если нет никакой информации о расположении элементов массива, то применяется линейный поиск, основная идея которого – последовательно просматривать массив, пока не будет обнаружено совпадение или не будет достигнут конец массива. Это реализует следующая простая программа: #include const int N = 10; main() { int i, X, A[N]; int success = 0; // переменная-флаг, флаг сброшен // здесь нужно ввести массив и X for ( i = 0; i < N; i ++ ) if ( A[i] == X ) { // если нашли, то... success = 1; // установить флаг break; // выйти из цикла } if ( success ) printf ( "A[%d] = %d", i, A[i] ); else printf ( "Элемент %d не найден.", X ); } Чтобы определить ситуацию, когда элемент не найден, нам надо ввести специальную переменную success, которая устанавливается в 1, если элемент найден, и остается равной нулю, если в массиве нет нужного элемента. Такая переменная называется флагом, флаг может быть установлен (равен 1) или сброшен (равен нулю). Для линейного поиска в худшем случае мы имеем N сравнений. Понятно, что для ускорения поиска надо сначала как-то упорядочить данные, в этом случае можно сделать поиск эффективным. Поиск всех элементов, соответствующих условию Задача. Определить, сколько в массиве положительных элементов и вывести их на экран. Для решения этой задачи вводим счетчик – специальную переменную, значение которой будет увеличиваться на единицу, когда мы нашли очередной положительный элемент. #include const int N = 10; main() { int i, A[N], count = 0; // count – счетчик положительных элементов // здесь нужно ввести массив for ( i = 0; i < N; i ++ ) // цикл по всем элементам массива if ( A[i] > 0 ) { // если нашли положительный, ... count ++; // увеличиваем счетчик и ... printf ("%d ", A[i]); // выводим элемент (если нужно) } printf ("\n В массиве %d положительных чисел", count); } Формирование массива по заданному условию Задача. Сформировать новый массив B, включив в него все положительные элементы исходного массива A, и вывести его на экран. Пусть есть массив A[N]. Надо выбрать из него все положительные элементы и записать их в новый массив, который и будет дальше использоваться. Сначала надо определить, сколько места в памяти надо выделить для массива B. В «худшем» случае все элементы в массиве A будут положительными и войдут в массив B, поэтому массив B должен иметь такой же размер, что и массив A. Можно предложить такой способ: просматривать весь массив A, и если для очередного элемента A[i]>0, его значение копируется в B[i]. A 1 -1 3 -2 5 B 1 ? 3 ? 5 Однако в этом случае использовать такой массив B очень сложно, потому что нужные элементы стоят не подряд. Есть более красивый способ. Объявляем временную переменную-счетчик count, в которой будем хранить количество найденных положительных элементов. Сначала она равна нулю. Если нашли очередной положительный элемент, то ставим его в ячейку B[count] и увеличиваем счетчик. Таким образом, все нужные элементы стоят в начале массива B. A 1 -1 3 -2 5 B 1 3 5 ? ? #include const int N = 10; main() { int i, A[N], B[N], count = 0; // здесь нужно ввести массив A for ( i = 0; i < N; i ++ ) if ( A[i] > 0 ) { B[count] = A[i]; count ++; } printf("\n Результат:\n"); for ( i = 0; i < count; i ++ ) printf("%d ", B[i]); } Можно сделать и так: if ( A[i] > 0 ) B[count++] = A[i]; Обратите внимание, что переменная в последнем цикле изменяется от 0 до count-1 (а не до N-1) так что на экран выводятся только реально используемые (а не все) элементы массива B. Минимальный элемент Задача. Найти и вывести на экран минимальный элемент в массиве A. Для решения задачи надо выделить в памяти ячейку (переменную) для хранения найденного минимального значения. Сначала мы записываем в эту ячейку первый элемент (A[0]). Затем берем следующий элемент и сравниваем его с минимальным. Если он меньше минимального, записываем его значение в ячейку минимального элемента. И так далее. Когда мы рассмотрим последний элемент в массиве, в дополнительной ячейке памяти будет минимальное значение из всех элементов массива. Заметим, что перебор в цикле начинается с элемента с номером 1 (а не 0), поскольку начальный элемент мы рассмотрели отдельно. #include const int N = 10; main() { int i, A[N],min; // здесь нужно ввести массив A min = A[0]; // предполагаем, что A[0] - минимальный for ( i = 1; i < N; i ++ ) // цикл по всем элементам с A[1] до A[N-1] if ( A[i] < min ) // если A[i] меньше min, ... min = A[i]; // запомнить A[i] как минимальный printf("\n Минимальный элемент %d", min); } Чтобы найти максимальный элемент, достаточно изменить условие в заголовке условного оператора на обратное (A[i] > min). Конечно, вспомогательную переменную в этом случае лучше (но не обязательно!) назвать max. Теперь можно усложнить задачу и найти еще и номер минимального элемента. Задача. Найти и вывести на экран минимальный элемент в массиве A и его номер. Напрашивается такое решение: завести еще одну переменную, в которой хранить номер минимального элемента. Если мы нашли новый минимальный элемент, то в одну переменную записали его значение, а во вторую – его номер. Тем не менее, можно обойтись одной дополнительной переменной. Дело в том, что по номеру элемента можно легко найти его значение в массиве. На этом основана приведенная ниже программа. Теперь мы запоминаем (в переменной nMin) не значение минимального эле- мента, а только его номер. #include const int N = 10; main() { int i, A[N], nMin; // nMin – номер минимального элемента // здесь нужно ввести массив A nMin = 0; // считаем, что A[0] - минимальный for ( i = 1; i < N; i ++ ) // цикл по всем остальным элементам if ( A[i] < A[nMin] ) // если A[i] N/2) будут возвращены на свои места. Правильное решение – делать перебор, при котором переменная цикла доходит только до середины массива. #include const int N = 10; main() { int i, A[N], c; 1 Существуют и немного более сложные способы, позволяющие обойтись всего двумя ячейками // здесь нужно ввести массив for ( i = 0; i < N/2; i ++ ) // { c = A[i]; // A[i] = A[N-1-i]; // A[N-1-i] = c; } A перебор только до середины! цепочка для перестановки A[i] и A[N-1-i] printf("\n Результат:\n"); for ( i = 0; i const int N = 10; main() { int i, A[N], c; // здесь нужно ввести массив A c = A[N-1]; // запомнить последний элемент for ( i = N-1; i > 0; i -- ) // цикл с уменьшением i A[i] = A[i-1]; A[0] = c; // первый элемент ставим отдельно printf("\n Результат:\n"); for ( i = 0; i < N; i ++ ) printf("%d ", A[i]); } Сортировка массивов Сортировка – это расстановка элементов некоторого списка в заданном порядке. Существуют разные виды сортировки (по алфавиту, по датам и т.д.), они отличаются лишь процедурой сравнения элементов. Мы рассмотрим простейший вариант сортировки – расстановку элементов массива в порядке возрастания. Программисты придумали множество методов сортировки. Они делятся на две группы:  понятные, но не эффективные  эффективные, но непонятные (быстрая сортировка и т.п.). Пока мы будем изучать только методы из первой группы, которых хватает для простых задач (когда размер массива не более 1000). Метод пузырька Название этого метода произошло от известного физического явления – пузырек воздуха в воде поднимается вверх. В этом методе сначала поднимается «наверх» (к началу массива) самый «легкий» элемент (минимальный), затем следующий и т.д. Сначала сравниваем последний элемент с предпоследним. Если они стоят неправильно, то меняем их местами. Далее так же рассматриваем следующую пару элементов и т.д. Когда мы обработали пару (A[0], A[1]), минимальный элемент стоит на месте A[0]. Это значит, что на следующих этапах его можно не рассматривать . 4 4 4 4 1 5 5 5 1 4 2 2 1 5 5 1 1 2 2 2 3 3 3 3 3 При следующем проходе наша задача – поставить на место элемент A[1]. Делаем это так же, но уже не рассматриваем A[0], который стоит на своем месте. Сделав N-1 проходов, мы установим на место элементы с A[0] по A[N-2]. Это значит, что последний элемент, A[N-1], уже тоже стоит на своем месте (другого у него нет). #include const int N = 10; main() { int i, j, A[N], c; // здесь надо ввести массив A for ( i = 0; i < N-1; i ++ ) // достаточно поставить N-1 элементов for ( j = N-2; j >= i; j -- ) // идем с конца массива в начало if ( A[j] > A[j+1] ) // если они стоят неправильно, ... { c = A[j]; A[j] = A[j+1]; // переставить A[j] и A[j+1] A[j+1] = c; } printf("\n Отсортированный массив:\n"); for ( i = 0; i < N; i ++ ) printf("%d ", A[i]); } Метод пузырька работает медленно, особенно на больших массивах. Можно показать, что при увеличении размера массива в 10 раз время выполнения программы увеличивается в 100 раз (метод имеет порядок N2). К сожалению, все простые алгоритмы сортировки имеют такой (квадратичный) порядок. Метод выбора минимального элемента Еще один недостаток метода пузырька состоит в том, что приходится слишком часто переставлять местами соседние элементы. Этого можно избежать, если использовать метод выбора минимального элемента. Он заключается в следующем. Ищем в массиве минимальный элемент и ставим его на первое место. Затем из оставшихся элементов также ищем минимальный и ставим на следующее место и т.д. В сравнении с методом пузырька, этот метод требует значительно меньше перестановок элементов (в худшем случае N-1). Он дает значительный выигрыш, если перестановки сложны и занимают много времени. #include const int N = 10; main() { int i, j, nMin, A[N], c; // здесь нужно ввести массив A for ( i = 0; i < N-1; i ++ ) { nMin = i; // ищем минимальный, начиная с A[i] for ( j = i+1; j < N; j ++ ) if ( A[j] < A[nMin] ) nMin = j; if ( nMin != i ) // если минимальный не стоит на своем месте,… { c = A[i]; A[i] = A[nMin]; // ставим его на место A[nMin] = c; } } printf("\n Отсортированный массив:\n"); for ( i = 0; i < N; i ++ ) printf("%d ", A[i]); } Двоичный поиск в массиве Пусть элементы массива A уже расставлены по возрастанию и требуется найти элемент, равный x, среди элементов с номерами от L до R.. Для этого использую следующую идею: выбираем средний элемент между L и R , он имеет номер m=(L+R)/2, где деление выполняется нацело. Сравним его с искомым x. Если он равен x, мы нашли то, что искали. Если x меньше A[m], надо искать дальше между A[L] и A[m], если x больше A[m], дальше ищем между A[m] и A[R]. #include const int N = 10; main() { int L = 0, R = N-1, m, A[N], flag = 0; // переменная-флаг, нашли (1) или нет (0) // здесь надо ввести массив A // и отсортировать его по возрастанию printf("Введите искомый элемент\n"); scanf( "%d", &x ); while ( L <= R ) { m = (L + R) / 2; // середина интервала if ( A[m] == x ) { // нашли нужный элемент flag = 1; // установить флаг break; // выйти из цикла } if ( x < A[m] ) R = m - 1; // сужаем границы области поиска else L = m + 1; } if ( flag ) printf ( "Нашли: A[%d]=%d", m, A[m] ); else printf ( "Такого элемента нет" ); } Переменная flag служит для того, чтобы определить, нашли мы нужный элемент или нет. Ес- ли нашли элемент, равный x, надо присвоить этой переменной значение 1 и выйти из цикла. При этом в переменной m остается номер найденного элемента. Если массив маленький, то скорость двоичного поиска незначительно отличается от линейного. Представим себе, что размер массива — 1000000 элементов и нужный нам элемент стоит в конце массива (это самый худший вариант для линейного поиска). Размер массива, N 10 1 000 1 000 000 N Число сравнений Линейный поиск Двоичный поиск  10  1 000  1 000 000 N 4  10  20  log 2 N Таким образом, чем больше элементов в массиве, тем выгоднее использовать двоичный поиск, поскольку число операций возрастает как логарифм N, то есть медленнее, чем увеличивается размер массива. Его недостатком является то, что элементы должны быть заранее отсортированы. Двоичный поиск используется при поиске информации в больших базах данных.