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

И) Поиск совпадений

З) Сортировка массива

Е) Обмен местами

Задача 14. Поменять местами первый и последний элемент массива.

При обмене, чтобы не потерять одно из значений, потребуется дополнительная переменная:

p=a[0];

a[0]=a[n-1];

a[n-1]=p;

ж) Поиск минимума/максимума

Задача 15. Найти в массиве наименьший элемент и его позицию.

В подобных задачах нахождения "самого-" в каком-нибудь смысле элемента используется та же идея, что и в спорте при определении рекорда: каждый очередной результат сравнивается с текущим рекордом, и если он "лучше", то он и становится новым значением рекорда, а иначе рекорд не меняется. За начальное значение рекорда принимается первый результат.

min=a[0]; k=0;

for (i=0; i<n; i++)

if (a[i]<min)

{ min=a[i]; k=i; }

Эту же программу можно переписать и короче:

for (i=k=0, min=a[0]; i<n; i++)

if (a[i]<min)

min=a[k=i];

Задача 16. Отсортировать массив по возрастанию (т.е. расположить его элементы в порядке возрастания).

Для этой задачи придумано множество различных алгоритмов. Один из них - сортировка методом прямого выбора:

for(i=0; i<n; i++)

for(k=i+1; k<n; k++)

if (a[k]<a[i]) {

p=a[k]; // Обмен a[k] и a[i]

a[k]=a[i];

a[i]=p;

}

Здесь на каждой итерации внешнего цикла происходит помещение на i-ую позицию наименьшего из "оставшихся" (т.е. расположенных от i-ой позиции до конца массива) значений элементов.

Этот алгоритм включает в себя, таким образом, алгоритмы поиска минимума и обмена.

Задача 17. Найти в массиве элемент, повторяющийся наибольшее количество раз. (Если таких элементов несколько, вывести любой из них).

for(max=i=0; i<n; i++){

s=1; // s - число повторений i-го элемента

for(k=i+1; k<n; k++)

if (a[k]==a[i]) s++;

if (s>max) {

max=s; // max - число повторений x

x=a[i]; // x - значение наиболее

} // частого элемента

}

Заметим, что x здесь не присвоено начальное значение, т.к. оператор x=a[i]; обязательно выполнится хотя бы раз (max вначале = 0, а s не меньше 1), а использовано x будет лишь впоследствии.

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

Декларация многомерного массива имеет следующий формат:

тип ID [ размер 1] [ размер 2]…[ размерN ] =

{ { список начальных значений },

{ список начальных значений },

…

};

Списки начальных значений – атрибут необязательный.

Пример:

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

Аналогично, при обращении к конкретному элементу многомерного массива указывается имя массива и затем - последовательно индексы элемента, каждый в квадратных скобках; например:

a[2][1]

a[i+1][k]

Рассмотрим особенности работы с многомерными массивами на конкретном примере двумерного массива (двумерные массивы называют также матрицами):

#include <stdio.h>

void main()

{

int i, j;

int m[3][4] = { { 1, 2, 3, 4}, {11,12,13,14}, {21,22,23,24} };

for (i=0; i<3; i++) {

printf("\n %2d)", i+1);

for (j=0; j<4; j++)

printf(" %3d",m[ i ] [ j ]);

}

}

Результаты работы программы:

1) 1 2 3 4

2) 11 12 13 14

3) 21 22 23 24

б) Диагонали квадратной матрицы

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

Обозначим размер матрицы буквой N, индекс строки буквой I, а индекс столбца буквой J. Тогда у элементов, лежащих на главной диагонали, I = J, а у элементов, лежащих на побочной диагонали, I + J = N - 1.

Задача 4. Найти сумму элементов матрицы, лежащих над главной диагональю.

Из рисунка видно, что у элементов, лежащих над главной диагональю,

I < J.

Можно учесть это в условии оператора if, либо цикла for:

for (i=s=0; i<n; i++)

for (j=i+1; j<n; j++)

s+=a[i][j];

в) Работа со строками и столбцами

Строка или столбец матрицы аналогичны одномерному массиву. Поэтому к ним применимы все алгоритмы, рассмотренные для одномерных массивов.

В применении же ко всей матрице это обычно требует дополнительного внешнего цикла (циклов).

Задача 5. Поменять местами первую и последнюю строки матрицы.

for (j=0; j<m; j++) {

p=a[0][j];

a[0][j]=a[n-1][j];

a[n-1][j]=p;

}

Задача 6. Найти сумму элементов в каждой строке матрицы.

Поскольку строк в матрице несколько, ответом будет не одно число, а одномерный массив:

int b[10];

for (i=0; i<n; i++) {

for (j=s=0; j<m; j++)

s+=a[i][j];

b[i]=s;

}

for(i=0; i<n; i++)

printf("%d ", b[i]);

puts("");

Задача 7. Найти сумму элементов в каждом столбце матрицы.

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

for (j=0; j<m; j++) {

for (i=s=0; i<n; i++)

s+=a[i][j];

b[j]=s;

}

for(j=0; j<m; j++)

printf("%d ", b[j]);

puts("");

Задача 8. В каждой строке матрицы определить количество элементов, равных нулю. Отсортировать строки матрицы по убыванию этого количества.

Прежде всего, нужно определить эти количества и занести их в одномерный массив (обозначим его b):

for (i=0; i<n; i++) {

for (j=s=0; j<m; j++)

if (a[i][j]==0) s++;

b[i]=s;

}

Затем нужно отсортировать матрицу. В процессе этого обменивать местами нужно как сами строки, так и соответствующие им элементы одномерного массива b (чтобы каждый его элемент продолжал соответствовать своей строке):

for (i=0; i<n; i++)

for (k=i+1; k<n; k++)

if (b[k]>b[i]) {

for(j=0; j<m; j++)

{ p=a[i][j]; a[i][j]=a[k][j]; a[k][j]=p; }

p=b[i]; b[i]=b[k]; b[k]=p;

}

Дата добавления: 2014-01-05