Лекции Булатицкий Дмитрий Иванович (во многом по материалам Прасолова А. Н.)
 Скачать 319.62 Kb.
|
Подробнее о Массивах и структурахВычисление длины строки символовВ качестве примера использования массива, рассмотрим программу определяющую длину строки символов, вводимой с клавиатуры. #include void main (void) { int len; char str[81]; printf("Введите строку: "); scanf("%s", str); for(len=0; str[len]; len++); printf("Длина строки = %d\n", len); } В этой программе используется цикл for с пустым оператором тела цикла. Цикл будет выполняться до тех пор, пока в строке не встретится нуль-символ, то есть пока выражение str[len] будет отлично от нуля. После окончания цикла переменная len станет равной количеству символов строки str, исключая нуль-символ. Фрагмент вычисления длины строки можно оформить в виде отдельной функции и затем использовать в разных программах. Эта функция может выглядеть следующим образом: int StrLen (char str[]) { int len; for(len=0; str[len]; len++); return len; } При наличии функции StrLen два последних оператора предыдущей программы можно заменить одним printf("Длина строки = %d\n", StrLen(str)); Сортировка массивовСортировкой или упорядочением массива называется расположение его элементов по возрастанию (или убыванию). Если не все элементы различны, то надо говорить о неубывающем (или невозрастающем) порядке. Вообще говоря, это большая и сложная тема, в которой известно много различных алгоритмов. Критерии оценки эффективности этих алгоритмов могут включать следующие параметры: • количество шагов алгоритма, необходимых для упорядочения; • количество сравнений элементов; • количество перестановок, выполняемых при сортировке. Мы рассмотрим только один из самых известных и самых неэффективных алгоритмов – пузырьковую сортировку (метод «пузырька», Bubble sort) Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма). Реализация алгоритма в виде функции представлена в следующем примере: void bubble(int* a, int n) { for (int i=n-1; i>=0; i--) { for (int j=0; j { if (a[j] > a[j+1]) { int tmp = a[j]; a[j] = a[j+1]; a[j+1] = tmp; } } } } Двумерные массивы (массивы массивов)Элементом массива может быть в свою очередь тоже массив. Таким образом, мы приходим к понятию двумерного массива или матрицы. Описание двумерного массива строится из описания одномерного путем добавления второй размерности, например: int a[4][3]; Анализ подобного описания необходимо проводить в направлении выполнения операций [], то есть слева направо. Таким образом, переменная a является массивом из четырех элементов, что следует из первой части описания a[4]. Каждый элемент a[i] этого массива в свою очередь является массивом из трех элементов типа int, что следует из второй части описания. Для наглядности двумерный массив можно представить в виде таблицы с числом строк, равным первому размеру массива, и числом столбцов, равным второму размеру массива, например:
Имя двумерного массива без квадратных скобок за ним имеет значение адреса первого элемента этого массива, то есть значение адреса первой строки - одномерного массива из трех элементов. При использовании в выражениях тип имени двумерного массива преобразуется к типу адреса строки этого массива. В нашем примере тип имени массива a в выражениях будет приведен к типу адреса массива из трех элементов типа int и может использоваться во всех выражениях, где допускается использование соответствующего адреса. Имя двумерного массива с одним индексным выражением в квадратных скобках за ним обозначает соответствующую строку двумерного массива и имеет значение адреса первого элемента этой строки. Например, в нашем случае a[2] является адресом величины типа int, а именно ячейки, в которой находится число 30, и может использоваться везде, где допускается использование адреса величины типа int. Имя двумерного массива с двумя индексными выражениями в квадратных скобках за ним обозначает соответствующий элемент двумерного массива и имеет тот же тип. Например, в нашем примере a[2][1] является величиной типа int, а именно ячейкой, в которой находится число 52, и может использоваться везде, где допускается использование величины типа int. В соответствии с интерпретацией описания двумерного массива (слева-направо) элементы последнего располагаются в памяти ЭВМ по строкам. Инициализация двумерного массива также проводится по строкам, например, для того чтобы получить вышеописанный массив a, можно было бы провести следующую инициализацию int a[][3] = { { 18, 21, 5 }, { 6, 7, 11 }, { 30, 52, 34 }, { 24, 4, 67 } }; Здесь первый размер массива будет определен компилятором. Следует отметить, что второй размер массива должен быть всегда указан. Это необходимо для того, чтобы сообщить компилятору размер строки массива, без которого компилятор не может правильно разместить двумерный массив в памяти ЭВМ. Для инициализации двумерного массива символов можно использовать упрощенный синтаксис инициализации строк: char s[][17] = { "Строка 1", "Длинная строка 2", "Строка 3" } Размер памяти заказанный под каждую строку в этом случае должен быть равным длине самой длинной строки с учетом нуль-символа. При этом, для части строк (строка 1 и строка 3) будет выделено излишнее количество памяти. Таким образом, хранение строк различной длины в двумерном массиве символов недостаточно эффективно с точки зрения использования памяти. Ввод двумерного массива осуществляется поэлементно с помощью двух вложенных циклов. Следующий фрагмент программы предназначен для ввода по строкам двумерного массива элементов типа double размером n строк на m столбцов for (i=0; i for (j=0; j { printf("a[%d][%d] = ", i, j); scanf ("%lf", &a[i][j]); } Для ввода массива по столбцам достаточно поменять местами строки программы, являющиеся заголовками циклов. Вывод такого же двумерного массива иллюстрирует следующий фрагмент: for (i=0; i { for (j=0; j printf("\n"); } В данном фрагменте после вывода очередной строки массива осуществляется переход на следующую строку дисплея. |