Tag Archives: матрицы. Технология программирования на Си: представление матриц, работа с файлами и с текстами Вывод всех элементов прямоугольной матрицы cи

Вообще-то программировать расчёт определителей не нужно. Их умеет считать, скажем, встроенная функция МОПРЕД из Excel:

• набираем элементы матрицы в смежных ячейках, например, матрица размерностью 4*4 показана на картинке;
• в нужной ячейке вводим формулу (в нашем случае =МОПРЕД(A1:D4) и нажимаем Enter:)

Не труднее вычислить и в MathCAD - просто нажать кнопку на панели матриц...

Но иногда нужен алгоритм, а не ответ... вот немного кода на консольном C++, на совершенство он не претендует, но нули в матрице или "не тот" порядок элементов смущать функцию determinant не должны. Пример из main - 1001-й на работу с динамической матрицей средствами C++ :) Остальное закомментировано в исходнике.

#define bool int #define true 1 #define false 0 int search (double **a, int m, int n, double what, bool match, unsigned int &uI, unsigned int &uJ, unsigned int starti, unsigned int startj) { // Поиск в матрице a[m][n] элемента с указанным значением what // Возвращаеются его номер строки и столбца uI, uJ, если элемент найден. // match - искать равный элемент или отличный от указанного. // Вернёт 0 - не найдено, не 0 - найдено if ((!m) || (!n)) return 0; if ((starti >= n) || (startj >= m)) return 0; for (unsigned int i = starti; i < n; i++) for (unsigned int j = startj; j < m; j++) { if (match == true) { if (a[i][i] == what) { uI = i; uJ = j; return 1; } } else if (a[i][j] != what) { uI = i; uJ = j; return 1; } } return 0; } void swaprows (double **a, int n, int m, unsigned int x1, unsigned int x2) { //Меняет в матрице a[n][m] строки с номерами x1 и x2 местами if ((!n) || (!m)) return; if ((x1 >= n) || (x2 >= n) || (x1 == x2)) return; double tmp; for (unsigned int x = 0; x < m; x++) { tmp = a[x]; a[x] = a[x]; a[x] = tmp; } return; }; void swapcolumns (double **a, int n, int m, unsigned int x1, unsigned int x2) { //Меняет в матрице a[n][m] столбцы с номерами x1 и x2 местами if ((!n) || (!m)) return; if ((x1 >= m) || (x2 >= m) || (x1 == x2)) return; double tmp; for (unsigned int x = 0; x < n; x++) { tmp = a[x]; a[x] = a[x]; a[x] = tmp; } return; }; double determinant (double **a, unsigned int n) { //Вычисление определителя квадратной матрицы a[n][n] unsigned int m = n; if (m == 0) return 0; if (m == 1) return a; if (m == 2) return (a * a - a * a); bool sign = false; // смена знака определителя. по умолчанию - нет double det = 1; // определитель double tmp; unsigned int x, y; for (unsigned int i = 0; i < n; i++) { // цикл по всей главной диагонали if (a[i][i] == 0) { // если элемент на диагонали равен 0, то ищем ненулевой элемент в матрице if (!search(a,m,n,0, false, y, x, i, i)) return 0; // если все элементы нулевые, то опр. = 0 if (i != y) { // меняем i-ую строку с y-ой swaprows(a,m,n,i, y); sign = !sign; } if (i != x) { // меняем i-ый столбец с x-ым swapcolumns(a,m,n,i, x); sign = !sign; } // таким образом, в a[i][i], теперь ненулевой элемент. } // выносим элемент a[i][i] за определитель det *= a[i][i]; tmp = a[i][i]; for (x = i; x < m; x++) { a[i][x] = a[i][x] / tmp; } // таким образом a[i][i] теперь равен 1 // зануляем все элементы стоящие под (i, i)-ым, // при помощи вычитания с опр. коеффициентом for (y = i + 1; y < n; y++) { tmp = a[y][i]; for (x = i; x < m; x++) a[y][x] -= (a[i][x]*tmp); } } if (sign) return det*(-1); return det; }; #include int main () { const int n=4; int data = { 5,4,3,2, 11,-1,2,7, 0,1,0,4, -13,79,1,2 }; int i,j,k=0; double **a = new double * [n]; for (i=0; i

Аннотация: Приводятся правильные и неправильные способы реализации матриц и многомерных массивов на языке Си. Работа с матрицами иллюстрируется на примере приведения матрицы к ступенчатому виду методом Гаусса. Рассматриваются методы работы с файлами, использующие функции ввода-вывода из стандартной библиотеки ANSI. Приводятся способы работы с символами и текстовыми строками с помощью функций стандартной библиотеки. Материал иллюстрируется примерами, включающими программу "wc" подсчета символов, слов и строк в файле и программу "Записная книжка", которая позволяет находить телефон человека по его имени, а также сохранять и модифицировать содержимое книжки.

Представление матриц и многомерных массивов

Специального типа данных матрица или многомерный массив в Си нет, однако, можно использовать массив элементов типа массив . Например, переменная a представляет матрицу размера 3x3 с вещественными элементами:

Элементы матрицы располагаются в памяти последовательно по строкам: сначала идут элементы строки с индексом 0, затем строки с индексом 1, в конце строки с индексом 2 (в программировании отсчет индексов всегда начинается с нуля, а не с единицы!). При этом выражение

где i -- целая переменная , представляет собой указатель на начальный элемент i -й строки и имеет тип double* .

Для обращения к элементу матрицы надо записать его индексы в квадратных скобках, например, выражение

представляет собой элемент матрицы a в строке с индексом i и столбце с индексом j . Элемент матрицы можно использовать в любом выражении как обычную переменную (например, можно читать его значение или присваивать новое).

Такая реализация матрицы удобна и максимально эффективна с точки зрения времени доступа к элементам. У нее только один существенный недостаток: так можно реализовать только матрицу, размер которой известен заранее. Язык Си не позволяет описывать массивы переменного размера, размер массива должен быть известен до начала работы программы еще на стадии компиляции.

Пусть нужна матрица , размер которой определяется во время работы программы. Тогда пространство под нее надо захватывать в динамической памяти с помощью функции malloc языка Си или оператора new языка C++. При этом в динамической памяти захватывается линейный массив и возвращается указатель на него. Рассмотрим вещественную матрицу размером m строк на n столбцов. Захват памяти выполняется с помощью функции malloc языка Си

double *a; . . . a = (double *) malloc(m * n * sizeof(double));

или с помощью оператора new языка C++:

double *a; int m, n; . . . a = new double;

При этом считается, что элементы матрицы будут располагаться в массиве следующим образом: сначала идут элементы строки с индексом 0 , затем элементы строки с индексом 1 и т.д., последними идут элементы строки с индексом m - 1 . Каждая строка состоит из n элементов, следовательно, индекс элемента строки i и столбца j в линейном массиве равен

(действительно, поскольку индексы начинаются с нуля, то i равно количеству строк, которые нужно пропустить, i * n - суммарное количество элементов в пропускаемых строках; число j равно смещению внутри последней строки). Таким образом, элементу матрицы в строке i и столбце j соответствует выражение

Этот способ представления матрицы удобен и эффективен. Его основное преимущество состоит в том, что элементы матрицы хранятся в непрерывном отрезке памяти. Во-первых, это позволяет оптимизирующему компилятору преобразовывать текст программы, добиваясь максимального быстродействия; во-вторых, при выполнении программы максимально используется механизм кеш -памяти, сводящий к минимуму обращения к памяти и значительно ускоряющий работу программы.

В некоторых книгах по Си рекомендуется реализовывать матрицу как массив указателей на ее строки, при этом память под каждую строку захватывается отдельно в динамической памяти:

double **a; // Адрес массива указателей int m, n; // Размеры матрицы: m строк, n столбцов int i; . . . // Захватывается память под массив указателей a = (double **) malloc(m * sizeof(double *)); for (i = 0; i < m; ++i) { // Захватывается память под строку с индексом i a[i] = (double *) malloc(n * sizeof(double)); }

После этого к элементу a ij можно обращаться с помощью выражения

Несмотря на всю сложность этого решения, никакого выигрыша нет, наоборот, программа проигрывает в скорости! Причина состоит в том, что матрица не хранится в непрерывном участке памяти, это мешает как оптимизации программы, так и эффективному использованию кеш -памяти. Так что лучше не применять такой метод представления матрицы.

Многомерные массивы реализуются аналогично матрицам. Например, вещественный трехмерный массив размера 4 x 4 x 2 описывается как

обращение к его элементу с индексами x , y , z осуществляется с помощью выражения

Многомерные массивы переменного размера с числом индексов большим двух встречаются в программах довольно редко, но никаких проблем с их реализацией нет: они реализуются аналогично матрицам. Например, пусть надо реализовать трехмерный вещественный массив размера m x n x k . Захватывается линейный массив вещественных чисел размером m * n * k :

double *a; . . . a = (double *) malloc(m * n * k * sizeof(double));

Доступ к элементу с индексами x , y , z осуществляется с помощью выражения

a[(x * n + y) * k + z]

Пример: приведение матрицы к ступенчатому виду методом Гаусса

В качестве примера работы с матрицами рассмотрим алгоритм Гаусса приведения матрицы к ступенчатому виду. Метод Гаусса - один из основных результатов линейной алгебры и аналитической геометрии, к нему сводятся множество других теорем и методов линейной алгебры (теория и вычисление определителей, решение систем линейных уравнений, вычисление ранга матрицы и обратной матрицы, теория базисов конечномерных векторных пространств и т.д.).

Напомним, что матрица A с элементами a ij называется ступенчатой, если она обладает следующими двумя свойствами:

1. если в матрице есть нулевая строка, то все строки ниже нее также нулевые;
2. пусть a ij не равное 0 -- первый ненулевой элемент в строке с индексом i , т.е. элементы a il = 0 при l < j . Тогда все элементы в j -м столбце ниже элемента a ij равны нулю, и все элементы левее и ниже a ij также равны нулю: a kl = 0 при k > i и l =< j .

Ступенчатая матрица выглядит примерно так:

здесь тёмными квадратиками отмечены первые ненулевые элементы строк матрицы. Белым цветом изображаются нулевые элементы, серым цветом - произвольные элементы.

Алгоритм Гаусса использует элементарные преобразования матрицы двух типов.

• Преобразование первого рода :две строки матрицы меняются местами, и при этом знаки всех элементов одной из строк изменяются на противоположные.
• Преобразование второго рода :к одной строке матрицы прибавляется другая строка, умноженная на произвольное число.

Элементарные преобразования сохраняют определитель и ранг матрицы, а также множество решений линейной системы. Алгоритм Гаусса приводит произвольную матрицу элементарными преобразованиями к ступенчатому виду. Для ступенчатой квадратной матрицы определитель равен произведению диагональных элементов, а ранг - числу ненулевых строк (рангом по определению называется размерность линейной оболочки строк матрицы).

Метод Гаусса в математическом варианте состоит в следующем:

1. ищем сначала ненулевой элемент в первом столбце. Если все элементы первого столбца нулевые, то переходим ко второму столбцу, и так далее. Если нашли ненулевой элемент в k -й строке, то при помощи элементарного преобразования первого рода меняем местами первую и k -ю строки, добиваясь того, чтобы первый элемент первой строки был отличен от нуля;
2. используя элементарные преобразования второго рода, обнуляем все элементы первого столбца, начиная со второго элемента. Для этого от строки с номером k вычитаем первую строку, умноженную на коэффициент a k1 /a 11 .
3. переходим ко второму столбцу (или j -му, если все элементы первого столбца были нулевыми), и в дальнейшем рассматриваем только часть матрицы, начиная со второй строки и ниже. Снова повторяем пункты 1) и 2) до тех пор, пока не приведем матрицу к ступенчатому виду.

Программистский вариант метода Гаусса имеет три отличия от математического:

r = -a kj /a ij . a k = a k + r * a i

Такая схема работает нормально только тогда, когда коэффициент r по абсолютной величине не превосходит единицы. В противном случае, ошибки округления умножаются на большой коэффициент и, таким образом, экспоненциально растут. Математики называют это явление неустойчивостью вычислительной схемы. Если вычислительная схема неустойчива, то полученные с ее помощью результаты не имеют никакого отношения к исходной задаче. В нашем случае схема устойчива, когда коэффициент r = -a kj /a ij не превосходит по модулю единицы. Для этого должно выполняться неравенство

|a ij | >= |a kj | при k > i

Отсюда следует, что при поиске разрешающего элемента в j -м столбце необходимо найти не первый попавшийся ненулевой элемент, а максимальный по абсолютной величине . Если он по модулю не превосходит , то считаем, что все элементы столбца нулевые; иначе меняем местами строки, ставя его на вершину столбца, и затем обнуляем столбец элементарными преобразованиями второго рода.

Ниже дан полный текст программы на Си , приводящей вещественную матрицу к ступенчатому виду. Функция , реализующая метод Гаусса , одновременно подсчитывает и ранг матрицы. Программа вводит размеры матрицы и ее элементы с клавиатуры и вызывает функцию приведения к ступенчатому виду. Затем программа печатает ступенчатый вид матрицы и ее ранг . В случае квадратной матрицы также вычисляется и печатается определитель матрицы , равный произведению диагональных элементов ступенчатой матрицы.

При реализации метода Гаусса используется схема построения цикла с помощью инварианта, см. раздел 1.5.2. В цикле меняются две переменные -- индекс строки i , 0 =< i < m - 1 , и индекс столбца j , 0 =< j < n - 1 . Инвариантом цикла является утверждение о том, что часть матрицы (математики говорят минор ) в столбцах 0,1,...j - 1 приведена к ступенчатому виду и что первый ненулевой элемент в строке i - 1 стоит в столбце с индексом меньшим j . В теле цикла рассматривается только минор матрицы в строках i,...,m - 1 и столбцах j,...,n - 1 . Сначала ищется максимальный по модулю элемент в j -м столбце. Если он по абсолютной величине не превосходит то j увеличивается на единицу (считается, что столбец нулевой). Иначе перестановкой строк разрешающий элемент ставится на вершину j -го столбца минора, и затем столбец обнуляется элементарными преобразованиями второго рода. После этого оба индекса i и j увеличиваются на единицу. Алгоритм завершается, когда либо i = m , либо j = n . По окончании алгоритма значение переменной i равно числу ненулевых строк ступенчатой матрицы, т.е. рангу исходной матрицы.

Для вычисления абсолютной величины вещественного числа x типа double мы пользуемся стандарной математической функцией fabs (x) , описанной в стандартном заголовочном файле " math .h.

#include // Описания функций ввода-вывода #include // Описания математических функций #include // Описания функций malloc и free // Прототип функции приведения матрицы // к ступенчатому виду. // Функция возвращает ранг матрицы int gaussMethod(int m, // Число строк матрицы int n, // Число столбцов матрицы double *a, // Адрес массива элементов матрицы double eps // Точность вычислений); int main() { int m, n, i, j, rank; double *a; double eps, det; printf("Введите размеры матрицы m, n: "); scanf("%d%d", &m, &n); // Захватываем память под элементы матрицы a = (double *) malloc(m * n * sizeof(double)); printf("Введите элементы матрицы:\n"); for (i = 0; i < m; ++i) { for (j = 0; j < n; ++j) { // Вводим элемент с индексами i, j scanf("%lf", &(a)); } } printf("Введите точность вычислений eps: "); scanf("%lf", &eps); // Вызываем метод Гаусса rank = gaussMethod(m, n, a, eps); // Печатаем ступенчатую матрицу printf("Ступенчатый вид матрицы:\n"); for (i = 0; i < m; ++i) { // Печатаем i-ю строку матрицы for (j = 0; j < n; ++j) { printf(// Формат %10.3lf означает 10 "%10.3lf ", // позиций на печать числа, a // 3 знака после точки); } printf("\n"); // Перевести строку } // Печатаем ранг матрицы printf("Ранг матрицы = %d\n", rank); if (m == n) { // Для квадратной матрицы вычисляем и печатаем // ее определитель det = 1.0; for (i = 0; i < m; ++i) { det *= a; } printf("Определитель матрицы = %.3lf\n", det); } free(a); // Освобождаем память return 0; // Успешное завершение программы } // Приведение вещественной матрицы // к ступенчатому виду методом Гаусса с выбором // максимального разрешающего элемента в столбце. // Функция возвращает ранг матрицы int gaussMethod(int m, // Число строк матрицы int n, // Число столбцов матрицы double *a, // Адрес массива элементов матрицы double eps // Точность вычислений) { int i, j, k, l; double r; i = 0; j = 0; while (i < m && j < n) { // Инвариант: минор матрицы в столбцах 0..j-1 // уже приведен к ступенчатому виду, и строка // с индексом i-1 содержит ненулевой эл-т // в столбце с номером, меньшим чем j // Ищем максимальный элемент в j-м столбце, // начиная с i-й строки r = 0.0; for (k = i; k < m; ++k) { if (fabs(a) > r) { l = k; // Запомним номер строки r = fabs(a); // и макс. эл-т } } if (r <= eps) { // Все элементы j-го столбца по абсолютной // величине не превосходят eps. // Обнулим столбец, начиная с i-й строки for (k = i; k < m; ++k) { a = 0.0; } ++j; // Увеличим индекс столбца continue; // Переходим к следующей итерации } if (l != i) { // Меняем местами i-ю и l-ю строки for (k = j; k < n; ++k) { r = a; a = a; a = (-r); // Меняем знак строки } } // Утверждение: fabs(a) > eps // Обнуляем j-й столбец, начиная со строки i+1, // применяя элем. преобразования второго рода for (k = i+1; k < m; ++k) { r = (-a / a); // К k-й строке прибавляем i-ю, умноженную на r a = 0.0; for (l = j+1; l < n; ++l) { a += r * a; } } ++i; ++j; // Переходим к следующему минору } return i; // Возвращаем число ненулевых строк }

Безусловно, по входным данным можно восстановить матрицы, тривиальным образом их перемножить и вывести результат в заданном виде. Как пример плохого стиля программирования: наивный алгоритм приводит к почти двукратному перерасходу потребляемой памяти и существенно уступает в производительности. Существует другое решение, прийти к которому можно путем последовательного приспособления стандартных матричных операций к формату входных данных.

Наибольшую сложность, как вычислительную, так и идейную, представляет умножение матриц, в данном случае — возведение в квадрат. Нижеприведенная последовательность шагов позволит перемножать симметричные матрицы, используя их линейное представление в формате исходных данных.

Замечание 1

Подпространство симметричных матриц незамкнуто относительно умножения: произведением двух симметричных матриц может быть несимметричная матрица.

Пример

\left(\begin{array}{ccc} 1 & 1 & 3 \\ 1 & 4 & 5 \\ 3 & 5 & 0\end{array} \right) \cdot \left(\begin{array}{ccc} 4 & 0 & 0 \\ 0 & 4 & 3 \\ 0 & 3 & 2 \end{array} \right) = \left(\begin{array}{ccc} 4 & 13 & 9 \\ 4 & 31 & 22 \\ 12 & 20 & 15 \end{array} \right)

Замечание 2

Степень симметрической матрицы также является симметрической матрицей. Доказательство основано на представлении матрицы как представления линейного оператора и на свойствах эрмитовых операторов.

Во всех дальнейших выкладках подразумевается, что матрица представлена линейным массивом из \frac{n(n+1)}{2} элементов.

Для начала, заметим, что элемент c_{i,j} матрицы C=A^{2}, равен скалярному произведению (как векторов в стандартном базисе) i-ой строки матрицы A на j-ую её строку (в силу того, что в симметричной матрице j-ая строка совпадает с j-м столбцом). Следовательно, для возведения в степень симметричной матрицы необходимо и достаточно реализовать операцию скалярного перемножения двух её строк.

Тогда следует понять, как по данному представлению матрицы получить её i-ую строку. Для удобства, выпишем имеющиеся элементы в виде полной матрицы. Заметим, что первым элементом i-ой строки будет i-ый элемент первой строки, и обобщим это наблюдение. Обозначим позицию текущего интересующего нас элемента i-ой строки как j. Если j < i, то следует выбрать i-ый элемент j-ой строки, иначе следует выбрать все элементы j-ой строки, лежащие правее данного. Графически можно интерпретировать алгоритм таким образом: начиная с i-го элемента первой строки, спускаться вертикально вниз по матрице до тех пор, пока не будет достигнута i-ая строка, далее — двигаться вправо до конца строки. Наглядность алгоритма позволяет легко воплотить его программно.
Следует только пронаблюдать, как изменяются расстояния между элементами, лежащими один под другим, при движении вниз по строкам матрицы, что позволит легко перенести алгоритм на линейное представление верхней треугольной матрицы. Предлагаем читателю самому проделать это несложное, но наглядное упражнение, для лучшего понимания алгоритма.

Теперь можно перейти непосредственно к реализации.

I . На кого рассчитан модуль.

Данный модуль рассчитан учащегося в старшей школе или студента. Должны быть освоены такие темы как работа с циклами, с указателями, необходимо знать, что такое одномерный массив.

II . Мотивация

Мы уже знаем, для чего нам могут понадобиться одномерные массивы. Например, мы можем сохранить в одномерном массиве коэффициенты квадратного уравнения и посчитать корни, используя дискриминант. А если нам нужно посчитать много таких уравнений? Неужели каждый раз перезаписывать новые коэффициенты на место старых? А если необходимо будет вернуться к уже посчитанным? Или нам нужно решить систему из нескольких уравнений, т.е. нужно одновременно работать со всеми? Если нам просто нужно хранить таблицу каких-то значений, например, измерений при опыте, как нам это сделать, используя полученные уже знания?

Для каждого из вышеназванных случаев можно просто объявить несколько одномерных массивов, но вот приятно ли будет работать с таким количеством? Ведь каждый нужно будет назвать и обработать отдельно. Ситуация похожа на ту, когда мы только вводили понятие одномерного массива. Тут и приходят на помощь массивы двумерные.

III. Изложение материала модуля

Обычным представлением таких массивов являются таблицы значений, содержащие информацию в строках и столбцах. Чтобы определить отдельный табличный элемент, нужно указать два индекса: первый (по соглашению) указывает номер строки, а второй (опять же по соглашению) указывает номер столбца.

Рисунок иллюстрирует двумерный массив a . Массив содержит три строки и четыре столбца, так что, еще говорят, - это массив три на четыре. Вообще, массивы с m строками и n столбцами называют массивами m на n .

Каждый элемент в массиве а определяется именем элемента в форме a [ i ][ j ]; a – это имя массива, а i и j – индексы, которые однозначно определяют каждый элемент в а . Заметим, что имена элементов первой строки имеют первый индекс 0 , имена элементов в четвертом столбце имеют второй индекс 3 .

Типичная ошибка программирования

Неправильная ссылка на элемент двумерного массива a [ x ] [ y ] как a [ x , y ]. На самом деле, a [ x , y ] воспринимается как a [ y ] , потому что С оценивает выражение (содержащее операцию последования - запятую) x , y просто как y (последнее из разделенных запятыми выражений).

Многомерные массивы могут получать начальные значения в своих объявлениях точно так же, как массивы с естественным индексом. Например, двумерный массив b можно объявить и дать ему начальные значения таким образом:

int b = {{1,2}, {3,4}};

Значения группируются в строки, заключенные в фигурные скобки. Таким образом, элементы b иb получают начальныезначения 1 и 2, а элементы b и b получают начальные значения 3 и 4. Если начальных значений в данной строчке не хватает для их присвоения всем элементам строки, то остающимся элементам присваиваются нулевые начальные значения. Таким образом, объявление

int b = {{1,},{3,4}};

будет означать, что b получает начальное значение 1, b получает начальное значение 0.

Объем памяти в байтах, занимаемый двухмерным массивом, вычисляется по следующей формуле:

Количество байтов = размер_1-го_измерения*размер_2-го_измерения*sizeof(базовый тип)

Например, двумерный массив 4-байтовых целых чисел размерностью 10*5 занимает участок памяти объемом

то есть 200 байтов.

Передача массива в функцию.

Рассмотрим небольшую программу вывода элементов двумерного массива:

#include

void printArray(int a)

for (int i = 0; i<=1;i++)

for (int j=0; j<=2; j++)

printf(“%i, ”,&a[i][j]);

printf(“\n”);

int array = {{1,2,3},{4,5,6}};

printf(“Values in array on rows:”);

printgArray(array);

Values in array on rows:

Программа вызывает функцию printArray для вывода элементов массива. Заметим, что описание функции указывает параметр – массив как int a . Когда мы задаем как аргумент функции одномерный массив, скобки в списке параметров функции пусты. Размерность первого индекса многомерного массива также не требуется, но все последующие размерности индексов необходимы. Компилятор использует размерности этих индексов для определения соответствующих ячеек памяти для доступа к элементам многомерных массивов. В памяти все элементы массива хранятся последовательно, независимо от количества индексов (размерности массива). В двумерном массиве первая строка хранится в памяти перед второй строкой.

Наличие размерностей индексов в объявлении параметра дает возможность компилятору сообщить функции о том, как расположены элементы в массиве. В двумерном массиве каждая строка является одномерным массивом. Чтобы определить местоположение элемента в некоторой строке, функция должна точно знать, сколько элементов находится в каждой строке. Тогда функция может пропустить соответствующее количество ячеек памяти при обращении к массиву. Таким образом, при обращении к a функция знает, что для доступа ко второй строке (строка 1) нужно пропустить в памяти три элемента первой строки, а затем обратиться к третьему элементу этой строки (элементу 2).

Многие типовые операции с массивами используют конструкцию for . Так, следующий цикл определяет сумму всех элементов массива a :

for (row = 0; row < 3; row++)

for (column = 0; column < 3; column ++)

total += a ;

Внутренняя структура for суммирует элементы одной строки массива. Внешняя структура for начинает работу с установки row (т.е. индекса строки) в нуль, так что во внутренней структуре for могут быть просуммированы элементы второй строки. Далее внешняя структура for увеличивает row до значения 2, так что могут быть просуммированы элементы третьей строки. После завершения работы вложенной структурыfor печатается результат.

Задача

Учащиеся одного из ВУЗов как-то поспорили, у кого наивысший средний бал за только что сданную сессию. Заодно захотели выяснить, кто получил наилучшую и наихудшую оценки. Для интереса представим, что мы живем в Америке, и оценки выставляются по 100-бальной шкале.

Указание:

Программа должна «знать» имена студентов, выводить их на экран. То же самое с таблицей успеваемости. Подразумевается, что номера столбцов эквивалентны номерам экзаменов.

Размышления о решении задачи

Для начала давайте определимся, что нам нужно для решения этой задачи. Первое, на что мы обращаем внимание – это то, что в условие явно сказано слово «таблица». Значит, скорее всего, для работы с ней мы будем использовать двумерный массив. Каждая строка в нем – это успеваемость отдельного студента. Как и сказано в условии, номер столбца будет определять номер сданного экзамена, номер строки – студента. Именно с этим массивом мы и будем работать, вычисляя средний бал, минимум и максимум. Видно, что необходимо будет создать три функции для получения нужных нам данных и функцию вывода таблицы оценок на экран. Все, что нужно для написания этой части программы, мы уже знаем.

Теперь разберемся с именами. Неплохо было бы их скомпоновать в таблицу, для того, чтобы по номеру студента можно было определить его имя и наоборот. Мы уже знаем. Что строка – это одномерный массив символов. Значит, можно создать двумерный массив, в котором номер строки будет определять номер студента, а номер столбца – соответствующую букву имени. Но тогда придется создать массив с наибольшим количеством ячеек по горизонтали из возможных. Т.е., если у нас есть четыре студента:

То необходимо будет создать таблицу, подобную изображенной на рисунке:

Серым цветом на рисунке показаны пустые клетки нашего массива. На эти клетки будет отведено место в памяти, но вот пользоваться они не будут. Так зачем они нам нужны? Нет ли способа избежать такой ситуации? Оказывается, есть. Об этом будет рассказано ниже, а затем мы вернемся к решению нашей задачи.

При решении задач с большим количеством данных одинакового типа использование переменных с различными именами, не упорядоченных по адресам памяти, затрудняет программирование. В подобных случаях в языке Си используют объекты, называемые массивами.

— это непрерывный участок памяти, содержащий последовательность объектов одинакового типа, обозначаемый одним именем.

Массив характеризуется следующими основными понятиями:

Элемент массива (значение элемента массива) – значение, хранящееся в определенной ячейке памяти, расположенной в пределах массива, а также адрес этой ячейки памяти.
Каждый элемент массива характеризуется тремя величинами:

• адресом элемента — адресом начальной ячейки памяти, в которой расположен этот элемент;
• индексом элемента (порядковым номером элемента в массиве);
• значением элемента.

Адрес массива – адрес начального элемента массива.

Имя массива – идентификатор, используемый для обращения к элементам массива.

Размер массива – количество элементов массива

Размер элемента – количество байт, занимаемых одним элементом массива.

Графически расположение массива в памяти компьютера можно представить в виде непрерывной ленты адресов.

Представленный на рисунке массив содержит q элементов с индексами от 0 до q-1 . Каждый элемент занимает в памяти компьютера k байт, причем расположение элементов в памяти последовательное.

Адреса i -го элемента массива имеет значение

Адрес массива представляет собой адрес начального (нулевого) элемента массива. Для обращения к элементам массива используется порядковый номер (индекс) элемента, начальное значение которого равно 0 . Так, если массив содержит q элементов, то индексы элементов массива меняются в пределах от 0 до q-1 .

Длина массива – количество байт, отводимое в памяти для хранения всех элементов массива.

ДлинаМассива = РазмерЭлемента * КоличествоЭлементов

Для определения размера элемента массива может использоваться функция

int sizeof (тип);

Например,

sizeof (char ) = 1;
sizeof (int ) = 4;
sizeof (float ) = 4;
sizeof (double ) = 8;

Объявление и инициализация массивов

Для объявления массива в языке Си используется следующий синтаксис:

тип имя[размерность]={инициализация};

Инициализация представляет собой набор начальных значений элементов массива, указанных в фигурных скобках, и разделенных запятыми.

int a = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; // массив a из 10 целых чисел

Если количество инициализирующих значений, указанных в фигурных скобках, меньше, чем количество элементов массива, указанное в квадратных скобках, то все оставшиеся элементы в массиве (для которых не хватило инициализирующих значений) будут равны нулю. Это свойство удобно использовать для задания нулевых значений всем элементам массива.

int b = {0}; // массив b из 10 элементов, инициализированных 0

Если массив проинициализирован при объявлении, то константные начальные значения его элементов указываются через запятую в фигурных скобках. В этом случае количество элементов в квадратных скобках может быть опущено.

int a = {1, 2, 3, 4, 5, 6, 7, 8, 9};

При обращении к элементам массива индекс требуемого элемента указывается в квадратных скобках .

Пример на Си

1
2
3
4
5
6
7
8

#include
int main()
{
int a = { 5, 4, 3, 2, 1 }; // массив a содержит 5 элементов
printf("%d %d %d %d %d\n" , a, a, a, a, a);
getchar();
return 0;
}

Результат выполнения программы:

Однако часто требуется задавать значения элементов массива в процессе выполнения программы. При этом используется объявление массива без инициализации. В таком случае указание количества элементов в квадратных скобках обязательно.

int a;

Для задания начальных значений элементов массива очень часто используется параметрический цикл:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include
int main()
{
int a;
int i;
// Ввод элементов массива
for (i = 0; i<5; i++)
{
printf("a[%d] = " , i);
scanf("%d" , &a[i]);
}
// Вывод элементов массива
for (i = 0; i<5; i++)
printf("%d " , a[i]); // пробел в формате печати обязателен
getchar(); getchar();
return 0;
}

Результат выполнения программы

Многомерные массивы

В языке Си могут быть также объявлены многомерные массивы. Отличие многомерного массива от одномерного состоит в том, что в одномерном массиве положение элемента определяется одним индексом, а в многомерном - несколькими. Примером многомерного массива является матрица.

Общая форма объявления многомерного массива

тип имя[размерность1][размерность2]...[размерностьm];

Элементы многомерного массива располагаются в последовательных ячейках оперативной памяти по возрастанию адресов. В памяти компьютера элементы многомерного массива располагаются подряд, например массив, имеющий 2 строки и 3 столбца,

int a;

будет расположен в памяти следующим образом

Общее количество элементов в приведенном двумерном массиве определится как

КоличествоСтрок * КоличествоСтолбцов = 2 * 3 = 6.

Количество байт памяти, требуемых для размещения массива, определится как

КоличествоЭлементов * РазмерЭлемента = 6 * 4 = 24 байта.

Инициализация многомерных массивов

Значения элементов многомерного массива, как и в одномерном случае, могут быть заданы константными значениями при объявлении, заключенными в фигурные скобки {} . Однако в этом случае указание количества элементов в строках и столбцах должно быть обязательно указано в квадратных скобках .

Пример на Си

1
2
3
4
5
6
7
8
9

#include
int main()
{
int a = { 1, 2, 3, 4, 5, 6 };
printf("%d %d %d\n" , a, a, a);
getchar();
return 0;
}

Однако чаще требуется вводить значения элементов многомерного массива в процессе выполнения программы. С этой целью удобно использовать вложенный параметрический цикл .

Пример на Си

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#define _CRT_SECURE_NO_WARNINGS
#include
int main()
{
int a; // массив из 2 строк и 3 столбцов
int i, j;
// Ввод элементов массива
for (i = 0; i<2; i++) // цикл по строкам
{
for (j = 0; j<3; j++) // цикл по столбцам
{
printf("a[%d][%d] = " , i, j);
scanf("%d" , &a[i][j]);
}
}
// Вывод элементов массива
for (i = 0; i<2; i++) // цикл по строкам
{
for (j = 0; j<3; j++) // цикл по столбцам
{
printf("%d " , a[i][j]);
}
printf("\n" ); // перевод на новую строку
}
getchar(); getchar();
return 0;
}

Передача массива в функцию

Обработку массивов удобно организовывать с помощью специальных функций. Для обработки массива в качестве аргументов функции необходимо передать

• адрес массива,
• размер массива.

Исключение составляют функции обработки строк, в которые достаточно передать только адрес.

При передаче переменные в качестве аргументов функции данные передаются как копии. Это означает, что если внутри функции произойдет изменение значения параметра, то это никак не повлияет на его значение внутри вызывающей функции.

Если в функцию передается адрес переменной (или адрес массива), то все операции, выполняемые в функции с данными, находящимися в пределах видимости указанного адреса, производятся над оригиналом данных, поэтому исходный массив (или значение переменной) может быть изменено вызываемой функцией.

Пример на Си Дан массив из 10 элементов. Поменять местами наибольший и начальный элементы массива. Для операций поиска максимального элемента и обмена использовать функцию.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#define _CRT_SECURE_NO_WARNINGS
#include
// Функция обмена
void change(int *x, int n)
{
// x - указатель на массив (адрес массива)
// n - размер массива
int i;
int max, index;
max = x;
index = 0;
// Поиск максимального элемента
for (i = 1; i {
if (x[i]>max)
{
max = x[i];
index = i;
}
}
// Обмен
x = x;
x = max;
}
// Главная функция
int main()
{
int a;
int i;
for (i = 0; i<10; i++)
{
printf("a[%d] = " , i);
scanf("%d" , &a[i]);
}
change(a, 10); // вызов функции обмена
// Вывод элементов массива
for (i = 0; i<10; i++)
printf("%d " , a[i]);
getchar();
getchar();
return
p = p * x[i];
}
return p;
}
// Главная функция
int main()
{
int a; // объявлен массив a из 5 элементов
int i;
int pr;
// Ввод элементов массива
for (i = 0; i<5; i++)
{
printf("a[%d] = " , i);
scanf("%d" , &a[i]); // &a[i] - адрес i-го элемента массива
}
pr = func(a, 5); // вычисление произведения
printf("\n pr = %d" , pr); // вывод произведения четных элементов
getchar(); getchar();
return 0;
}