2015-02-24
513
Перед изучением этого вопроса рекомендуется повторить пункт 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) мы проссумировали бы и последний элемент матрицы.
Упражнения, тесты.
1. Пусть const n=10; int a[n]={-1, -2, 33, 44, -5, -6, 77, 8}; int *q;
Какие из следующих присваиваний допустимы и что они означают:
1) q=a; 2) q=*a[0]; 3) q=n; 4) q=&a[0]; 5) int i=2; q=&a[i];
6) int i=2; q=a[i]; 7) q=a[0]; 8) q=&a[n];?
2. Дано описание функции:
void Fun (int *x, int N, int &S)
{ S=0; for (int i=0;;)
{ S+=x[i++];
if (x[i]==0 || i ==N) return; }
}
/* или
void Fun (int *x, int N, int &S)
{ S=0; for (int i=0; i<N-1;) if (x[++i]>0) S+=x[i]; } */
В каких строках правильно вызвана функция? Что будет выведено для правильных вариантов?
int main() { const n=10; int a[n]= {11, -2, 30, 44, -5, 66, 0, 8, 99}; int &Sum1; Fun (a,n,Sum1); cout<<endl<<Sum1; //1
int Sum2; Fun (&a[0],n/2,Sum2); cout<<endl<<Sum2; //2
int Sum3; Fun (a,n,Sum3); cout<<endl<<Sum3; //3
int Sum4; Fun (&a[5], 5, Sum4); cout<<endl<<Sum4; //4
int *Sum5; Fun (a,n,Sum5);cout<<endl<<Sum5; //5
int *q=a[5], Sum6=0; Fun(q, n/2, Sum6); cout<<endl<<Sum6; //6
int *q=a[n/2], Sum7=0; Fun(q, 5, Sum7);cout<<endl<<Sum7; //7
int *q=&a[n/2], Sum8=0; Fun(q, 5, Sum8); cout<<endl<<Sum8; //8
int *q=*a[n/2], Sum9=0; Fun(q, 5, Sum9); cout<<endl<<Sum9; //9
getch(); return 0; }
3. Описана функция:
void OutChar (int *a, int N, int k)
{ cout<< endl;
for (int i=0; i<N; i++) printf("%d %c %c", a[i], a[i], (i+1)%k? '\n': ' '); }
Какие из следующих вызовов правильные? Что будет выведено для правильных вариантов?
main(){ const n=10; int k=5; int a[n]= {48, 49,50,51, 52, 53, 54, 55, 56, 57};
OutChar (a,n,k); /* 1 */ OutChar(a, k, n); /* 5 */
OutChar(&a[0], k,k/2); /* 2 */ OutChar(&a[k], k,k/2); /* 6 */
OutChar(a[0], k, n); /* 3 */ OutChar (a,2*k,k); /* 7 */
OutChar(a[0], n, k); /* 4 */ OutChar(*a[0], n, k); /* 8 */
getch(); }
4. Описана функция:
int MyFun (int *x, int n)
{ по некоторому алгоритму для одномерного массива x размерности n получаем и возвращаем одно целое число
}
Как эту функцию без изменений использовать для получения и (или) вывода этого же параметра в каждой строке статической матрицы, объявленной так:
const n=4,m=6; int A[n][m];?
т.е для получения и (или) вывода n чисел, по одному для каждой строки? Выбери правильные варианты ответов:
1) for(int i=0;i<n;i++) MyFun(M[i],m);
2) for(int i=0;i<n;i++) cout<<MyFun(M[i],m)<<” “;
|
|
|
3) for(int i=0;i<m;i++) cout<<MyFun(M[i], n)<<” “;
4) for(int i=0;i<n;i++) { r=MyFun(&M[i][0], m); cout<<r<<” “;}
5) for(int i=0;i<m;i++) { r=MyFun(&M[i][0], n); cout<<r<<” “;}
6) for(int i=0;i<n;i++) cout<<MyFun(M[i][0],m)<<” “;
7) for(int i=0;i<n;i++) { r=MyFun(M[i][0], m); cout<<r<<” “;}
5. Дан код:
const size2=6;
void Sort1(int X[],int n);
void MyOut(int M[][size2],int n,int m)
{ cout<<endl; for(int i=0;i<n;i++){cout<<endl;
for(int j=0;j<m;j++) printf("%4d ",M[i][j]);
} cout<<endl;
}
void Sortmatr1(int M[][size2],int n,int m);
int main() {const n=3,m=6; int A[n][size2]={ …
};
Sortmatr1(A, n, m); cout<<endl; MyOut (A, n, m);
getch(); return 0;
}
void Sort1(int X[], int m)
{ int min, Nmin; for(int k=0;k<m-1;k++)
{ min=X[k]; Nmin=k;
for (int j=k;j<m;j++)
if(X[j]<min) { min=X[j]; Nmin=j; }
X[Nmin]=X[k]; X[k]=min;
}
}
void Sortmatr1(int M[][size2],int n,int m)
{ for(int i=0;i<n;i++) Sort1(M[i],m);
}
1) Что будет выведено в результате выполнения этой программы?
2) Какие элементы матрицы и как будут рассортированы, если в функции Sortmatr1 записать:
a) for (int i=0; i<n; i+=2) Sort1(M[i], k/2);?
b) for (int i=0; i<n; i+=2) Sort1(&M[i][к/2], k);?
6. Дан код:
const size2=6; int Sum(int *X, int); //1
void Sum2(int M[][size2],int,int, int &, int &); //2
void MyOut(int *x, int n) //3
{cout<<endl; for(int i=0;i<n;i++)
printf("%5d%c", x[i], (i+1)%size2?' ':'\n'); } //4
int main()
{const n=4,m=6; int A[n][size2]=
{ {4, -3, 2, 0, 5}, {-11, 2, 3},
{5, -6, 4}, {-2, 4, 3, -2,1, 5} }, S1, S2;
MyOut (A[0],n*m); //5
Sum2(A,n,m,S1, S2); cout<<endl<<S1<<" "<< S2; //6
getch(); return 0; }
int Sum(int X[],int m) //7
{ int S=0; for(int j=0; j<m; j++) if (X[j]>0) S+=X[j]; return S; }
void Sum2 (int M[][size2],int n,int m, int &S1, int &S2) //8
{ S1= Sum(M[0],n*m/2); //9
S2=Sum(&M[2][0], n*m/2); } //10
В каких строках есть ошибки? Если ошибок нет, что будет выведено?
7. Дан код:
int *p1= new int = 20; int *p2; *p2= new int [ 20];
int *p3= new int[20]={11, 2, 30, -44, -5, 6, 7, 0, 8, 99, 100};
int *p4; p4= new int[20]; int *p5= new int (20);
int *p6= new (int) 20; int *p7= new int:20;
Для каких указателей (p1 — p6) правильно резервируется память для одномерного массива из 20 целых чисел?
8. Дан код:
float *f1= new float[4]; delete[]float;
float *f2= new float[4]; delete[]f2;
float *f3= new float[4]; delete float [4];
float *f4= new float[4]; delete f4;
Для каких переменных правильно освобождается память для одномерного массива?.
9. Пусть const n=5; int ar[n]={-1, 2, 33,4, -5}; Объясните результат выполнения следующих циклов:
a) for (p=ar, i=0; p+i<=ar+size-1; i++) printf (“%d “, *(p+i));
b) for (p=ar, i=0; p+i<=ar+size-1; p++, i++) printf (“%d “, *(p+i));
c) for (p=ar+size-1; p>=ar; p--) cout<<p<<” “<<*p<<endl;
10. Дан код: int A[5]={0,1,2,3}; //1
for (int *p=A+4; p>A; p--) cout<<(*p)<<" "; //2
|
|
|
Что будет выведено?
Варианты ответов: 1) 3 2 1 0 2) 0 3 2 1 3) 0 1 2 3 0
4) 0 3 2 1 0 5) ошибка (указать, в какой строке).
11. Дан код:
const n=5; int a[n]={-1, 2, 33,4, -5};
int *p=a,s=0; for (; p<a+n; p++) s+=*p; //0
int *p1=&a[0]; for (int s1=0; p1<= &a[n-1]; p1=p1+1) s1=s1+*p1; //1
int *p2,s2; for (p2=a, s2=0; *p2<a[n-1]; p2++) s2+=*p2; //2
int *p3, s3=0; for (p3=a; p3<&a[n-1]; p3++, s3+=*p3); //3
int *p4, s4=0; for (p4=a; p4<a+n; s4+=*p4, p4++); //4
Среди строк //1 — //4 найти такие синтаксически правильные строки, которые выполняются так, как операторы в строке //0
12. Дан код:
const n=5; int a[n]={-1, 2, 33,4}, *p; //1
for (p=a; p<=a+n-1; p+=2) //2
cout<<p<<" "<<(*p)<<" "; //3
Что будет выведено? Если есть ошибки, указать, в каких строках.
13. Дан код:
const n=3; int A[n][n]={{1,2,3},{4,5},{6,7}}, *p;
for (p=A[n-1]; p>A[0]; p-=(n-1)) cout<<(*p)<<" ";
Что будет выведено?
14. Дан код:
const n=3; int A[n][n]={{1,2,3},{-4,-5},{6,7}}, *p;
for (p=A[n-1]; *p>=*A[0]; p-=(n-1)) cout<<(*p)<<" ";
Что будет выведено? Если есть ошибки, объяснить их.
15. Дан код:
const n=4, m=3; int A[n][m]={{1,2,3},{4,5,6},{5}, {0, 22}}, *p1,*p2, S;
for (p1=A[0]; p1<=A[n-1]; p1++)
{ S=0; for (p2=p1; p2<p1+m; p2++) S+=(*p2); cout<<S<<" "; }
Что будет выведено? Если есть ошибки, объяснить их.
16. Дан код:
const n=4, m=3; int A[n][m]={{1,2,3},{4,5,6},{5}, {0, 22}}, *p1,*p2, S;
for (p1=A[0]; p1<=A[n-1]; p1+=m)
{ S=0; for (p2=p1; p2<=p1+m; p2+=2) S+=(*p2); cout<<S<<" "; }
Что будет выведено? Если есть ошибки, объяснить их.
17. Дан код: char S9b[]="Borland C++", *p9b=S9b, *q9b; //1
* q9b=strstr(p9b, "C++"); //2
int k1, k2;
k1=*q9b-*p9b; //3
k2=q9b-p9b; //4
cout<<endl<<k1<<” “<<k2;
Что будет выведено? Если есть ошибки, указать, в каких строках (// 1 — // 4).
18. Дан код: char t[]=”Borland Builder”, *q, *p=t; // 1
q=strstr(p, “Builder”); //2
if (p>q) cout<<”Yes”; else cout<<”No”; //3
if (*p>*q) cout<<”Yes”; else cout<<”No”; //4
Что будет выведено? Если есть ошибки, указать, в каких строках (// 1 — // 4).
19. Дан код:
char t10[]="Borland Builder", *q10, *p10=t10; // 1
q10=strchr(p10, 'B'); //2
if (!(p10-q10)) cout<<endl<<"Yes"; else cout<<endl<<"No"; // 3
if (*p10-*q10) cout<<endl<<"Yes"; else cout<<endl<<"No"; // 4
Что будет выведено? Если есть ошибки, указать, в каких строках (// 1 — // 4).
20. Дан код:
char S7[]="...Borland Builder"; //1
char *p=S7; *q; //2
q=p+strspn(p,".;:-!?"); //3
cout<<endl<<q<<endl; //4
Что будет выведено? Если есть ошибки, указать, в каких строках (// 1 — // 4).
21. Дан код:
char *T1="Borland C++"; //1
char T2[]="Borland C++"; //2
char T3[20]="Borland C++"; //3
char *T4; T4="BORLAND C++"; //4
char T5[15]; T5="Borland C++"; //5
char *T6; strcpy(T6, "Borland C++"); //6
char T7[20]; strcpy(T7,"Borland C++"); //7
В каких строках (// 1 — // 7) есть ошибки?
22. Дан код:
char T[80]; gets(T); if (strstr(T, “???”)) cout <<1; else cout<<0;
Число 1 (единица) будет выведено, если введём:
1)??? (ровно три подряд идущих символа “вопрос” и больше ничего);
2) Строку подряд идущих символов “?”, количество которых >3.
3) Любую строку, в которой есть ровно 3 подряд идущих символа“?”. Например, Testing??? или Testing??? of string.
4) Любую строку, в которой есть не менее трёх подряд идущих символа“?”. Например, Testing?????? или Testing??? of string. или ???Testing???
5) Один или два подряд идущих символа “?”.
Какие утверждения правильные?
