Работа с динамическим массивом в классе. Деструктор

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

Пример 4. Создать класс для работы с одномерным динамическим массивом, предусмотрев конструктор и деструктор.

const Nmax=20; /* Наибольшая размерность массива, которая используется в конструкторе для контроля передаваемой в класс размерности. */

class DinArr {

int n; /* Реальная размерность массива в виде переменной*/

float *DA; /*Объявляем указатель на динамический массив. */

/* Метод для перестановки двух чисел. Можно использовать только внутри класса, так как по умолчанию атрибут доступа private. В качестве формальных параметров используем указатели на вещественные числа. */

void Change(float *x, float* y) { float t=*x; *x=*y; *y=t; };

public: // Конструктор

DinArr(int size) { if (size<1 || size>Nmax) n=Nmax / 2; else n=size;

DA=new float [n]; }

// Метод для ввода массива.

void MyDef() { for(int i=0; i<n; i++) cin>>DA[i]; }

// Метод для вывода массива.

void Show() { cout<<endl; for(int i=0; i<n; i++) printf("%5.2f ", DA[i]); }

/* Булевская функция (метод), возвращающая true или false в зависимости от того, является ли массив “симметричным” относительно “центра”. */

bool Simm() { for (int i=0;i<n/2; i++) if (DA[i]-DA[n-1-i]) return false;

return true; }

/* Метод, который “переворачивает” массив, т. е. меняет местами первый элемент с последним, второй с предпоследним и т. д. до середины массива */

void Rev() {

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

Change(&DA[i], &DA[n-1-i]); }

~DinArr() // Дeструктор

{ cout<<"\nThe destructor deletes array\n"; getch(); delete []DA;

} // The end of destructor

}; // The end of class

int main()

{ /* Создаём объект и одновременно вызываем конструктор. Фактический параметр для него (размерность массива) вводим */

unsigned MyN; cout<<"size="; cin>>MyN; DinArr ObjArr(MyN);

/* Вызываем методы класса */

ObjArr.MyDef(); ObjArr.Show();

/* Если массив симметричный, выводим "Yes!", в противном случае “переворачиваем” массив и выводим изменённый массив. */

if (ObjArr.Simm()) cout<<"Yes!";

else { ObjArr.Rev(); ObjArr.Show(); }

getch(); return 0; }

Во время выполнения, а не компиляции программы при объявлении объекта вызывается конструктор. С его помощью определяем размерность массива n с элементарным контролем. С помощью операции new резервируем память для n элементов динамичского массива и адрес начала этой выделенной области памяти присваиваем переменной-указателю DA. Кроме ввода размерность можно задать случайным образом DinArr ObjArr (random(Nmax)); или константой DinArr ObjArr(6);

Как и конструктор, деструктор не имеет типа, а его имя совпадает с именем класса, перед которым записывается символ “~” (тильда). Чтобы убедиться, что деструктор выполнялся, желательно выводить соответствующее сообщение. Кроме этого, освободили память, выделенную для динамического массива. Вызывается деструктор автоматически, когда завершается выполнение функции main ().

 

Введение в строки

 

Строку можно рассматривать как обычный одномерный статический или динамический массив, тип элементов которого символьный (char). Строку можно объявить как обычный статический одномерный массив с фиксированной размерностью: const n=20; char T[n]; Здесь n — наибольшая длина строки. Вводить и обрабатывать можем и более короткие строки, но память объёмом 20 байт на всё время выполнения функции или блока занята для указанного здесь количества символов. Напомним, что каждый символ занимает один байт. Реальную длину строки можно получить с помощью функции strlen(T). Нумерация символов, как и в числовом массиве, с нуля.

Для ввода строки вместо cin лучше использовать специально предназначенную для этого стандартную функцию gets(T); так как cin вводит строку до первого пробела. Для ввода одной строки в отличие от ввода числового массива цикл не нужен.

Строка заканчивается специальным символом “конец строки”, который в тексте программы обозначается ‘\0’ с одинарными кавычками. Он формируется автоматически при вводе строки после нажатия на клавишу “Enter” или добавляется к записанной строковой константе.

Рассмотрим следующую программу.

const m=20; char T[m]; gets(T);cout<<strlen(T)<<” “ << sizeof(T)<<endl;

Если введём текст “ математика” без никаких кавычек, то выведем 10 20.

Как и обычный числовой массив, строку также можно инициализировать при объявлении. Для этого указываем размерность, достаточную для раз­мещения текста и символа конца строки (‘\0’). Этот символ надо явно записать, например: char T[11]={‘м’,’а’,’т’,’е’,’м’,’а’,’т’,’и’,’к’,’а’,’\0’}; Так как для каждого символа надо записывать кавычки и разделять символы запятой, то есть более простой способ: char T[11]=“математика”; В этом случае нулевой символ добавляется к концу строки автоматически. Более того, размерность строки можно не указывать: char T[]=“математика”; Тогда она определяется в зависимости от реальной длины строки.

Для вывода строки кроме cout и printf с форматом “%s” можно использовать специальную функцию puts(T). После вывода курсор перемещается в начало следующей строки окна вывода.

В функцию строку можно передать как обычный одномерный массив.

Пример 4. Составить и проверить функцию, которая в одной строке находит количество цифр и количество введённого символа.

void STRDIGIT (char t[],char, int &, int &);

// или void STRDIGIT (char *t,char, int &, int &);

int main()

{ /* Объявляем строку наибольшей длины 50 */ char str[50];

gets(str); // Ввод строки

char c1; /* Переменная для одного символа */

int KDig, KC; cout<<"Input the symbol ";

c1=getchar(); // ввод одного символа

STRDIGIT(str,c1,KDig,KC); cout<<"In the string ";

puts(str); /* Вывели строку, или printf (“%s\n”, str) */

cout<< KDig<< " digits and " <<KC << " of simbols "<<c1;

getch(); return 0; }

void STRDIGIT(char t[],char Ch,int &K1, int &K2)

{ K1=0; K2=0;

for (int i=0; i<strlen(t); i++) // 1

// strlen возвращает длину строки

{ if (t[i]>='0' && t[i]<='9') K1++; // 2

if (t[i]==Ch) K2++; }

}

В качестве упражнения подумайте, почему в STRDIGIT не написали else после первого if. Для какого анализируемого символа Ch функция будет одинаково работать, а для какого — нет, если написать else?

Цикл //1 для работы со строкой можно записать по-другому, используя символ конца строки (‘\0’) for (int i=0; t[i]!=’\0’; i++) { …}. Этот символ, как и числовой нуль, играет роль false при сравнении. Поэтому это же можно записать короче: for (int i=0; t[i]; i++) { …}

Так как символы для цифр располагаются в кодовой таблице подряд (коды 48,49, …, 57) и тип char совместим с целым типом, то вместо // 2 можно

if (t[i]>=48 && t[i]<=57) K1++;

Анализ одного символа можно выполнить, используя встроенную функцию isdigit, возвращающую true или false в зависимости от того, является один символ цифрой или нет. Поэтому можно предложить более компактный другой вариант нашей функции:

void STRDIGIT (char *t, char Ch, int &K1, int &K2)

{ K1=K2=0; for (int i=0; t[i];) // 1

{ if (isdigit(t[i])) K1++; // 2

if (t[i++]==Ch) K2++; }

}

Записать i++ при выволнении первого if будет неправильно. Почему?

Вместо for в строке // 1 можно записать while:

K1=K2=0; int i=0; while (t[i]) {…}

Кроме функции isdigit, есть другие функции, анализирующие один символ, но не строку. Некоторые из них приведены ниже:

· islower — является ли аргумент символом нижнего регистра (маленькой буквой, например);

· isupper — является ли аргумент символом верхнего регистра (большой буквой, например);

· isalpha — является ли аргумент буквой алфавита (верхнего или нижнего регистра);

· isgraph — является ли аргумент печатным символом, отличным от пробела;

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

Эти и другие подобные функции, имена которых начинаются с is, возвращают true или false в зависимости от того, принадлежит ли символ соответствующей группе. Кроме этого, в эти функции передаётся один символ, а не строка. Поэтому анализ всех символов строки выполняется в цикле, а в функцию передаётся элемент символьного массива (t[i]).

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

 

Упражнения и тесты

1. Пусть const n=10;

int a[n]={-1,-2,33,44,-5,-6,77,8}, *q;

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

1) q=a; 2) q=*a[0]; 3) q=a[0]; 4) q=&a[0]; 5) q=n;

6) int i=5; q=*a[i]; 7) int i=n/2; q=a[i]; 8) int i=n/2; q=&a[i];

9) int i=n-1; q=a[i]; 10) q=&a[n]; 11) q=&a[n];

2. Дан код:

void F2 (int *x, int N, int &S)

{ S=0; for (int i=0;;)

{ S+=x[i++];

if (x[i]==0 || i ==N) return; }

}

int main()

{ const n=10;

// Вариант a)

int a[n]= {11, -2, 30, 44, 5, -60, 7, -8, 0, 100 };

/* или другие варианты

b) int a[n]={11, -2, 30, 0, 5, -60, 7, -8, 9, 100 };

с) int a[n]={11, -2, 0, 44, 5, 0, 7, -8, 9, 100 };

d) int a[n]={11, -2,30, 4,5, -60,7, -8,9,100 }; */

int &S1; F2 (a,n,S1); cout<<S1; //1

int S2; F2 (&a[0],n/2,S2); cout<<S2; //2

int S3; F2 (a,n,S3); cout<<S3; //3

int S4; F2 (&a[5], 5, S4); cout<<S4; //4

int *S5; F2 (a,n,S5); cout<<S5; //5

int *q=a[5], S6; F2 (q, n/2, S6); cout<<S6; //6

int* q=&a[n/2], S7; F2 (q, 5, S7); cout<<S7; //7

int* q; q=&a[n/2], S8=0; F2 (q, n/2, S8); cout<< S8;//8

getch(); return 0; }

В каких вариантах (//1 — //8) правильно вызвана функция F2? Что будет выведено для каждого из вариантов массива (a — d)?

3. Дан код: void F3 (int *x, int N, int S)

{ S=0; for (int i=0; i<N-1;)

{ if (x[++i]>0) S+=x[i];

cout<<S<<” “; }

}

int main() { const n=10;

int a[n]= {11, -2, 0, 44, 5, 60, 7, -8, 9, 100 };

/* Записано 8 вариантов вызова функции F3 (см. упр. 2)*/

getch(); return 0; }

В каких вариантах (//1 — //8) правильно вызвана функция F3? Что будет выведено?

4. Описана функция:

void OutChar (int *a, int N, int k)

{ 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); //2

OutChar(&a[0], k,k/2); /* 3 */ OutChar(&a[k], k,k/2); //4

OutChar(a[0], k, n); /* 5*/ OutChar (a,2*k,k); //6

OutChar(a[0], n, k); /* 7 */ OutChar(*a[0], n, k); //8

getch(); return 0; }

5. Описана функция:

void OutChar (int *a, int N, int k)

{ for (int i=0; i<N; i++) printf("%X %c %c", a[i], a[i], i%k? ' ‘: '\n'); }

/*Какие из следующих вызовов правильные? Что и где, в каких строках, будет выведено? */

main() { const n=10; int k=2;

int a[n]= {65,66,67,68,69,70,71,72,73,74};

/* дальше см. упр. 4 */ }

6. В одномерном целочисленном массиве найти все числа с наибольшим количеством единиц в его двоичном представлении.

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

unsigned NUM (unsigned);

main() { const n=5; unsigned maxnum=0, num2, A[n]={10,7,14,2,19};

/* Находим наибольшее количество единиц для чисел массива (maxnum) */

for(int i=0; i<n; i++) { num2=NUM(A[i]); if (num2>maxnum)

maxnum = num2; }

/* Выводимвсе числа с наибольшим количеством единиц в его двоичном представлении. */

for(int i=0; i<n; i++) if (NUM(A[i])==maxnum) cout<<A[i]<<" ";

getch(); return 0; }

/* Функция находит количество единицв двоичном представлении одного целого числа */ unsigned NUM (unsigned a)

{ unsigned num=0;

while (a) { num+=a%2; a/=2; }

return num; }

Задачи

1. Задан массив из n точек плоскости, т. е. два одномерных массива X [ n ] и Y [ n ], где (X_i, Y_i) — координаты i -й точки. Составить следующие функции:

1) логическую функцию Test с параметрами x, y, k для определения, принадлежит ли одна точка с координатами (x, y) k -й четверти;

2) функцию Num, которая с помощью первой функции в массиве точек определяет их количество в k -й четверти;

3) функцию main, которая определяет массив точек при объявлении и с помощью второй функции находит количество точек в каждой четверти.

const n = 10;

bool Test (float, float, unsigned);

unsigned Num (float* x, float* y, unsigned k);

main() { float X[n]= {1.1,2.2,3,44,0.5,-6.6, -0.7, -88, -9, -10},

Y[n]={11, 0.2, 33, 0.4,-5.5, 66, 77, -8.8,-9.9,-10};

cout<<" Number of points in\n";

for(unsigned K=1; K<=4;K++) cout<<endl<<K<<” “<<Num(X,Y,K);

getch(); return 0; }

bool Test (float x, float y, unsigned k)

{ switch (k) { case 1: return x>0 && y>0;

case 2: return x<0 && y>0;

case 3: return x<0 && y<0;

case 4: return x>0 && y<0; } }

unsigned Num (float* x, float* y, unsigned k)

{ unsigned number=0;

for (int i=0; i<n; i++) if (Test (x[i], y[i], k)) number++;

return number; }

2. В одномерном вещественном массиве найти среднее значение. Числа из отрезка [a, b] увеличить в 10 раз, а остальные оставить без изменения. Составить и использовать следующие функции: ввод массива; вывод массива; вычисление среднего значения элементов массива; изменение массива; main.

void INP(float x[], int n);

void OU1(float x[], int n);

float AVER(float x[], int n);

void CHANGE(float a, float b, float x[], int n);

main()

{ const N=5; float arr[N], a, b; INP(arr, N);

cout<<"Исходный массив \n"; OU1(arr, N);

cout<<"Среднее значение \t" <<AVER(arr, N)<<endl;

cout<<"a="; cin>>a; cout<<"b="; cin>>b;

CHANGE(a, b, arr, N);

cout<<"Измененный массив \n"; OU1(arr, N);

getch(); return 0; }

void INP(float x[], int n)

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

{ cout<<(i+1) <<" element -\t"; cin>>x[i]; } }

void OU1(float x[], int n)

{ cout<<endl;

for (int i=0; i<n; i++) cout<<x[i]<<” “; }

float AVER(float x[], int n)

{ float s=0;

for (int i=0; i<n; s+=x[i++]);

return s/n; }

void CHANGE(float a,float b, float x[], int n)

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

if(a<=x[i] && x[i]<=b) x[i]*=10;

}

3. Составить следующие функции для работы с одномерным массивом: ввод массива с контролем ввода; вывод массива; логическую функцию, которая проверяет, рассортирован ли массив по возрастанию. В main вызвать эти функции.

void MyInp(int* x, int size);

void MyOut(int* x, int size);

bool Sorted(int* x, int size);

main()

{ const n=10; int A[n]; MyInp(A, n);

cout<<" Integer array"; MyOut(A, n);

if (Sorted(A, n)) cout<<" \n Yes”; else cout<<" \n No”;

getch(); return 0; };

void MyInp(int x[],int size)

{ for(int i=0; i<size; i++)

/* Цикл do для ввода одного числа с проверкой */

do { textcolor (15); cin>>x[i];

if (x[i]>0) break;

textcolor (12); cprintf("Error. Repeat. ");

} while (1);

}; // The end of function

/* При вводе неположительных чисел выводим сообщение об ошибке, и программа повторяет ввод этого же элемента массива, не меняя индекс */

void MyOut(int x[], int size) { cout<<endl;

for(int i=0; i<size; i++) cout<<x[i]<<" "; };

bool Sorted(int x[], int size)

{ for (int i=0; i<size-1; i++) if (x[i]>x[i+1])

return false; // else не надо!

return true; }

Упражнение. Как будет работать последняя функция, если оставить else?

4. Рассортировать заданный массив точек по возрастанию расстояния до начала координат. Если расстояния одинаковы, то вначале должны быть точки области, ограниченной параболой y=x² и прямой y=2, а затем — точки, не принадлежащие этой области. Составим следующие методы класса:

· MyInp для ввода координат точек;

· MyPoint для определения расстояния от одной точки до начала координат (d1) и принадлежности точки указанной области (b1);

· ArrPoint для построения массива расстояний и логического массива, определяющего принадлежность каждой точки области;

· RR для перестановки двух величин. Эта функция дважды перегружена для вещественного и логического типов;

· MySort для сортировки массива с использованием функций RR; Используемый здесь алгоритм обменной сортировки описан в гл.7, пункт 1.1;

· MyOut для вывода координат точек.

const nmax=20;

class clCoord

{ float *x, *y, *d; bool *b; int n;

void MyPoint(float x1, float y1, float &d1, bool &b1)

{ d1=sqrt(x1*x1 + y1*y1);

b1= y1>=x1*x1 && y1<2; };

void RR(float &u, float &v)

{ float t=u; u=v; v=t; };

void RR(bool &u, bool &v)

{ bool t=u; u=v; v=t; };

public:

clCoord (int, float *, float *); void ArrPoint();

void MySORT();

void MyOut();

~clCoord() // Дeструктор

{ cout<<"\nThe destructor deletes array\n";

getch(); delete []x; delete []y;

delete []d; delete []b;

} // The end of destructor

}; // The end of class

clCoord::clCoord (int m, float *u, float *v)

{ n=m; if (n>nmax || n<1) n=nmax;

x= new float[n]; y= new float[n];

d= new float[n]; b= new bool[n]; //??

for(int i=0; i<n; i++) { x[i]=u[i]; y[i]=v[i]; } };

void clCoord::ArrPoint ()

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

MyPoint (x[i],y[i],d[i],b[i]); };

void clCoord::MySORT() { int k=n; bool flag;

do { k--; flag=false;

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

if (d[i]>d[i+1] || d[i]==d[i+1] && b[i]<b[i+1])

{ flag=true; RR(x[i],x[i+1]); RR(y[i],y[i+1]);

RR(d[i],d[i+1]); RR(b[i],b[i+1]); }

} while (flag); };

void clCoord::MyOut()

{ cout<< "\n \n";

cout<< " T A B L E \n";

cout<< " x y d b \n";

cout<< " \n";

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

printf (" %7.2f %7.2f %8.3f %1d \n",

x[i], y[i], d[i], b[i]);

};

int main() { int N; cout<<”\n N=”; cin>>N;

float *X= new float[N], *Y= new float[N];

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

{ cin>>X[i]; cin>>Y[i];}

clCoord OBJ (N,X, Y);

OBJ.ArrPoint (); OBJ.MyOut();

OBJ.MySORT(); OBJ.MyOut();

getch(); return 0; }

Функции MyPoint и RR имеют атрибут доступа private по умолчанию. Они доступны, как и поля, только в функциях этого класса и недоступны в других функциях. Например, из функции main их вызвать нельзя.

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

5. В одномерном целочисленном массиве найти, сколько раз повторяется наибольшее число, сколько раз повторяется наименьшее и вывести жёлтым цветом то из них, которое повторяется чаще. Например, в массиве {99, 8, 99, 99, 2} наибольшее число 99 повторяется чаще (три раза), чем наименьшее 2, которое встречается только один раз. Поэтому число 99 выделяем жёлтым цветом. Для другого теста {99, 7, 99, 7, 7} жёлтым цветом выделим число 7.

Составим и используем следующие функции: ввод массива (ReadArr); обычный, не “цветной” вывод массива (WriteArr); функцию ColorWriteArr, которая выводит число w массива цветом color1, остальные числа массива — цветом color2; поиск наиболь­шего и наименьшего элементов массива (MaxMin); функцию Num, котораяопределяет, сколько раз число w повторяется в массиве; main, проверяющую перечисленные выше функции.

void ReadArr(int [], int);

void WriteArr(int [], int);

void ColorWriteArr(int a[], int, int, int, int);

void MaxMin(int [], int, int &mx, int &mn);

int Num(int [], int, int);

main() { const n = 5; int a[n], MyMax, MyMin, num1, num2;

ReadArr(a, n); WriteArr(a, n);

MaxMin(a, n, MyMax, MyMin);

num1 = Num(a, n, MyMax); num2 = Num(a, n, MyMin);

cout<<"\nMax "<<MyMax <<" Min "<<MyMin<<endl;

cout<<"\nNumMax "<<num1 <<" NumMin "<<num2<<endl;

if (num1>num2) ColorWriteArr(a, n, MyMax, 14, 11);

else if (num1<num2) ColorWriteArr(a, n, MyMin, 14, 11);

else cout<<" Number of max = number of min ";

getch(); return 0; }

void ReadArr(int x[], int size)

{ for (int i=0; i<size; i++) { cout<<"a["<<i<<"]="; cin>>x[i]; } }

void WriteArr(int x[], int size)

{ for (int i=0; i<size; i++) cout<<x[i]<<" "; printf("\n"); }

void MaxMin(int x[], int size, int& mx, int& mn)

{ mx=x[0]; mn=x[0];

for (int i=0; i<size; i++) if (x[i]<mn) mn = x[i];

else if (x[i]>mx) mx = x[i]; }

int Num(int x[], int size, int w)

{ int k=0; for (int i=0; i<size; i++) if (x[i] == w) k++; return k; }

void ColorWriteArr(int x[],int size,int w,int c1,int c2)

{ for (int i=0; i<size; i++)

{ if (x[i] == w) textcolor(c1); else textcolor(c2);

cprintf("%5d ", x[i]); } printf("\n"); }

Уровень В

Составить несколько функций, не включённых в класс.

1. Дан одномерный вещественный массив a [ n ]. Вычислить

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

2. Для одномерного массива вычислить то же самое (см. задачу 1). Составить следующие три вещественные функции, каждая из которых имеет один результат: 1) вычисление наибольшего числа массива, 2) вычисление суммы всех его элементов, 3) нахождение их произведения. В головной функции определить массив при объявлении и с помощью трёх функций вычислить f.

3. Даны массивы a[5], b[5], c[5]. Вычислить

4. Даны два массива x[10] и y[10]. Построить третий массив z[10]:

Функции: вычисление наименьшего из двух чисел r = min(u, v); вычисление r = max(u, v); построение массива; main ().

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

6. Ввести три одномерных массива — a [ n ], b [ n ], c [ n ]. Получить массив d [ n ] по формуле d =( a + b ) ∙ ( b + c ), где сложение и умножение выполняются поэлементно. Составить и использовать функции для ввода массива, поэлементного сложения двух массивов, их поэлементного умножения, функцию main.

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

8. Рассортировать массив по возрастанию первых двух цифр числа. Функции: ввод массива, нахождение первой и второй цифры для одного целого числа, построение массива первых и вторых цифр, сортировка массивов, вывод массивов в виде таблицы, функцию main.

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

10. Рассортировать целочисленный массив по убыванию количества единиц в двоичном представлении числа.

11. Рассортировать целочисленный массив по убыванию общего количества пар соседних различных цифр в двоичном представлении числа. Например, число 74₁₀ = 1001010₂ содержит пять таких пар.

12. Рассортировать целочисленный массив по убыванию количества букв в шестнадцатеричном представлении числа.

13. Массив точек плоскости рассортировать по убыванию первой координаты.

 

Уровень С

Разработать объектно - ориентированный вариант программ для работы с одним или несколькими динамическими массивами (см. задачи уровня B). Предусмотреть конструктор и деструктор.

 

Глава 9
МАтрицы

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

§ 1. Объявление, способы определения матриц

 

Матрица (двухмерный массив) объявляется, например, следующим образом: const n=3, m=5; int A[n][m]; где n — количество строк (первая, левая размерность), m — количество столбцов или количество элементов в строке (вторая, правая размерность). По аналогии с одномерным массивом такую матрицу назовём статической в отличие от динамической, которая будет рассмотрена позже. Матрица располагается в оперативной памяти по строкам и занимает непрерывный участок, объём которой равен n*m*sizeof(тип), где тип — тип элементов матрицы (int в примере). Для нашей матрицы A этот объём равен 3*5*4=60 байт. Если в программе написать cout<<endl<<n*m*sizeof(int); то выведем число 60.

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

int A[n][m]= {{1, -2, 3, -4, 5},

{ 10, 20, 33},

{-11, 22, 300, 400, 500}};

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

В программах ввода и вывода матрицы предполагается для начала, что n и m такие, что её строка одной или двух матриц (см. пример 6) помещается в одной строке окна ввода, вывода, которого достаточно для всех строк. Желающим предлагается усложнять предложенные фрагменты программ.

Пример 1a. Простейший ввод матрицы можно выполнить так:

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

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

cin>>A[i][j];

Но в этом варианте в каждой строке окна ввода надо набирать одно число.

Пример 1b. В этой программе вводимые элементы матрицы на экране будут располагаться так, как в математической записи, то есть элементы строки матрицы будут вводиться из одной строки окна ввода экрана.

int i, j, x, y; for (y=wherey(), i=0; i<n; i++, y++)

{ gotoxy(1, y); cout<<"i="<<i;

for (x=6, j=0; j<m; j++, x+=5)

{ gotoxy(x,y); cin>>A[i][j]; } }

Пример 2. Для некоторых (но не для всех) задач элементы матрицы можно определить с помощью датчика случайных чисел:

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

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

A[i][j]=random(100); // 1

Если числа матрицы должны принадлежать интервалу [ r1, r2), где r2>r1, то вместо //1 надо записать A[i][j]=random(r2-r1)+r1;

Пример 3. Элементы матрицы можно задать по некоторому правилу:

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

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

A[i][j]=(i+1)*(j+1);

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

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

 

Вывод матриц

 

Пример 4a. Вывод матрицы можно выполнить, используя управление курсором. Для этого в примере 1b достаточно заменить cin на cout.

Пример 4b. Кроме этого можно предложить следующий вариант вывода:

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

{ printf("\n"); /* Перешли на новую строку экрана */

for (int j=0; j<m; j++) printf ("%5d", A[i][j]); }

При таком выводе числа столбцов будут выровнены благодаря наличию формата %5d, т. е. независимо от количества цифр в числах матрицы они будут выводиться друг под другом. В этом фрагменте важно место оператора printf("\n"). Если символ “\n” записать во внутреннем цикле printf ("\n%5d", A[i][j]); то в каждой строке экрана будет выводиться по одному числу. Необходимо также обратить внимание на расстановку фигурных скобок. Во внешнем цикле for в его теле два оператора: переход на новую строку и внутренний цикл for. Поэтому соответствующая пара скобок обязательна. Во внутреннем цикле один оператор вывода printf, поэтому фигурные скобки для него отсутствуют.

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

Пример 5. Положительные числа вывести цветом C1 на фоне C2, а отрицательные и нулевые — наоборот, цветом С2 на фоне С1, где С1 и С2 — целые числа, определяющие цвет.

void MyColors (int C1, int C2)

{ textcolor(C1); textbackground(C2); }

int main()

{ const n=4,m=6; float A[n][m]; randomize();

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

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

A[i][j]=(random(50)-40)/100. + random(5);

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

{ cprintf(“\n\r”);

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

{ // Установка цветов

if (A[i][j]>0) MyColors(2,15); else MyColors(15,2);

cprintf ("%7.2f", A[i][j]); }

} getch(); return 0; }

Заметим, что при “цветном” выводе с помощью cprintf для перехода в начало следующей строки недостаточно одного символа ‘\n’, а надо использовать и управляющий символ ‘\r’.Стандартные функции textcolor и textbackground устанавливают цвет выводимых символов и цвет фона в текстовом режиме. Для “цветного” вывода вместо printf или cout необходимо использовать функцию cprintf.

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

Пример 6. Пусть заданы константы n, m и k, матрицы A[n][m] и D[n][k] и одномерный массив (вектор) b[n]. Слева выведем матрицу A цветом С1, далее, правее — одномерный массив b в столбец по одному элементу цветом С2 и, наконец, ещё правее — матрицу D цветом C3 в обратном порядке, т. е. сначала (n–1) –ю строку, затем (n–2)– ю и так далее, 0 –ю строку.

void MyC(int C) { textcolor(C); }

int main() { textbackground(1); clrscr();

const n=4, m=6, k=5; float b[n]; int D[n][k], A[n][m]; randomize();

for (int i=0; i<n; i++) { b[i]=random(m+k)/10.;

/* Можно по–другому: b[i]=(float)i / 10; */

for (int j=0; j<m; j++) A[i][j]= random(50)-100;

// Все элементы отрицательные

for (int j=0; j<k; j++) D[i][j]= random(500)+200;

// Все элементы положительные

}

MyC(10); cprintf(" Matrix A ");

MyC(11); cprintf(" Vector b");

MyC(15); cprintf(" Matrix D\n");

for (int i=0; i<n; i++) { cout<<endl;

/* Вывод i –й строки матрицы A */

MyC(10); for (int j=0; j<m; j++) cprintf ("%4d", A[i][j]);

MyC(11); /* Вывод одного i –го элемента вектора b */

cprintf (" %6.1f ", b[i]);

/* Вывод строк матрицы D в обратном порядке */

MyC(15); for (int j=0; j<k; j++)

cprintf ("%5d", D[n-1-i][j]); }

getch(); return 0;

}

Упражнение. Написать второй вариант этой же программы, в которой используется функция gotoxy. Сначала выводим всю матрицу A, затем возвращаемся на первую строку и выводим в столбец вектор b и, наконец, в обратном порядке выводим матрицу D.

 

Типы алгоритмов

 

Ввиду многообразия задач по рассматриваемой теме сделана попытка классификации некоторых матричных задач. Объявление, определение и вывод матрицы A[n][m], описанные в предыдущих параграфах,опускаем.

 

Построчная обработка

 

К такому типу относятся задачи, в которых для каждой строки матрицы требуется найти её некоторый параметр. Таким параметром может быть, например, сумма, количество всех элементов строки или элементов с некоторым условием, наименьший (наибольший) элемент среди всех или части элементов строки и т. д. К этому классу можно отнести и задачи типа “есть ли нуль в строке матрицы?”. Их особенность в том, что не обязательно надо анализировать все элементы строки.

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

Например, пусть задана матрица A[n][m], в которой A_ij — оценка i –го студента на j –м экзамене.

Пример 7. Cформируем массив S[n], каждый элемент которого содержит средний балл одного студента:

float S[n], Sum;

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

{ Sum=0; for (int j=0; j<m;) Sum+=A[i][j++];

S[i]=Sum/m;

}

Здесь важно обратить внимание на следующее:

· оператор Sum=0; должен располагаться между операторами for, так как для каждой строки суммирование необходимо начинать с начала;

· важны также расстановка фигурных скобок и место оператора S[i]=Sum/m; Он должен выполняться n раз и поэтому располагается внутри внешнего, но вне внутреннего цикла. В качестве упражнения предлагается рассмотреть другие, в том числе неправильные, варианты расстановки фигурных скобок;

· массив S имеет размерность n,и индекс его элемента i, а не j, т. е. совпадает с номером строки, c параметром внешнего цикла;

· массив S и переменная Sum должны объявляться с типом float. Если объявить их как int, то в массиве сохранится результат целочисленного деления без дробной части. Например, при делении 37/5 вместо 7.4 получили бы целое число 7. Недостаточно объявить только массив как float, оставив int Sum. Это проблему типов данных можно решить и так: float S[n]; int Sum; … S[i]=(float)Sum/m; Здесь при вычислении выражения переменная Sum временно приводится (преобразуется) к вещественному типу. При этом в других операциях и перед и после этого присваивания она остаётся целочисленной.