§6. Использование операций над указателями при работе со статической матрицей.

Перед изучением этого вопроса рекомендуется повторить пункт 1.2 этой главы .

Напомним, что статическая, то есть с фиксированными размерностями матрица в оперативной памяти размещается по строкам и занимает непрерывный участок. Пусть объявлена матрица: const n=4, m=5; int M[n][m];. Тогда после элемента M[0][m-1] в памяти находится элемент M[1][0], после M[1][m-1] — M[2][0] и так далее. Этот факт и рассмотренные выше операции над указателями будем использовать при работе с двумерными массивами. Как и в случае одномерных массивов, доступ к элементам матрицы возможен как с помощью индексов (см. первый семестр), так и с помощью указателей. В одном цикле можно объединять эти способы.

Пример 1 (+). Найти наибольший элемент всей матрицы.

main()

{ const n=4, m=5; int M[n][m];

int *p, *q ; int k;

printf("\nInput the mftrix\n");

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

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

scanf("%d", M[0]+i*m+j);

for( k=0 , p=M[0]; k<n*m; k++, p++)

{ if ( k % m==0) cout<<endl;

printf("%4d",*p);

}

q=M[0]+n*m-1;

int MyMax; MyMax=*M[0] ;

for (p=M[0]; p<=q; p++)

if ( *p>MyMax) MyMax=*p;

cout<<"\nMax of matrix "<< MyMax;

getch(); return 0;

}

При вводе матрицы в первом вложенном цикле используется доступ к элементу матрицы с помощью номера строки и номера столбца. Так как M[0] — адрес начала нулевой строки матрицы, то M[0]+i*m —адрес начала i-й строки, а M[0]+i*m+j — адрес элемента M[i][j]. Учитывая, что M[i] — адрес начала i-й строки, в цикле можно записать scanf(“%d”, M[i]+j); или, как это делали в первом семестре, scanf(“%d”, &M[i][j]);. Так как в функции scanf в качестве второго параметра используется не сам вводимый элемент, а его адрес, то операция разыменование (“*”) не используется. Для элемента M[i][j] нужна операция “взятие адреса” (&).

В третьем цикле для поиска наибольшего элемента всей матрицы достаточно использовать только адреса элементов матрицы. Здесь M[0]+n*m-1 адрес последнего элемента матрицы, т. е. &M[n-1][m-1].

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

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

Пример 2. Найти суммы чисел каждой строки, начиная с главной диагонали.

int *p2; int i;

q=M[0]+n*m-1; // Адрес последнего элемента матрицы.

int s; cout<<endl;

for (p=M[0],i=0; p<=q;p+=m+1,i++)

{ s=0;

for (p2=p;p2<p+m-i; p2++)

s+=*p2;

printf ("%d ",s);

}

Здесь во внешнем цикле в переменной p последовательно хранятся адреса элементов главной диагонали. Чтобы перейти, например, от элемента M[0][0] к элементу M[1][1], или от M[1][1] к элементу M[2][2] и т. д., надо “сместиться” на (m+1) элемент. Поэтому значение указателя увеличивается на величину m+1. Во внутреннем цикле количество суммируемых элементов для каждой новой строки уменьшается на единицу. Для реализации этого использовали переменную i, которая меняется во внешнем цикле.

Пример 3. На побочной диагонали квадратной матрицы найти сумму всех чисел.

int *p, *q; int s;

q=M[0]+n*m-1; // Адрес последнего элемента матрицы.

for ( s=0, p=M[1]-1;p<q; p+=m-1)

s+=*p;

printf(" %d ", s);

Для решения таких задач без явного использования указателей надо определить зависимость одного индекса от другого. Если i — номер строки, то номер элемента в строке j=m-1-i. В других задачах такая зависимость может быть гораздо сложнее. Этот простой пример показывает, что в таких алгоритмах легче найти, как меняется значение указателя при переходе от одного элемента к другому. Сначала в переменную p заносим адрес последнего элемента нулевой строки (p=M[1]-1). Использовали, что M[1] — адрес начала строки с номером один, то есть адрес элемента M[1][0], следующего после M[0][m-1]. Это присваивание можно было бы записать и так: p=M[0]+m-1;. При переходе от элемента M[0][m-1] к элементу M[1][m-2] адрес увеличивается на m-1. Это же приращение сохраняется и дальше, при переходе на следующие элементы побочной диагонали. Заметим, что в заголовке цикла во втором выражении используется строгое неравенство (сравните с примером 2). В противном случае (p<=q) мы проссумировали бы и последний элемент матрицы.