Симоненко Евгений А. Олимпиадная подготовка по программированию

15

МАССИВЫ И МАТРИЦЫ

Речь пойдёт об одномерных массивах, а также о двумерных, рассматривающихся в разделе «Матрицы».

ОБЪЯВЛЕНИЕ, РАЗМЕЩЕНИЕ И ИНИЦИАЛИЗАЦИЯ МАССИВОВ

Несмотря на то, что компилятор GCC 4 позволяет нам объявлять одномерные массивы с заранее неизвестным количеством элементов, C++ вообще говоря предусматривает, что количество элементов будет константным выражением:

#include <iostream>

using namespace std;

int main(int argc, char* argv[]) { const int N = 100;

int a[N]; int n = 0; cin >> n;

for (int i = 0; i < n; i++) { cin >> a[i];

}

// обработка массива

return 0;

}

При большом N этот приём не сработает, так как локальные переменные размещаются в стеке, и сработает исключение превышения размера стека. Решением проблемы может быть объявление массива глобальным:

#include <iostream>

using namespace std;

const int N = 1000; int a[N];

int main(int argc, char* argv[]) { int n = 0;

cin >> n;

for (int i = 0; i < n; i++) { cin >> a[i];

}

// обработка массива

return 0;

}

Иногда нам может потребоваться сэкономить память процесса и тогда мы можем создавать массивы динамически:

#include <iostream>

using namespace std;

int main(int argc, char* argv[]) { int n = 0;

cin >> n;

int *a = new int[n];

for (int i = 0; i < n; i++) { cin >> a[i];

}

// обработка массива delete[] a;

return 0;

}

16	Симоненко Евгений А. Олимпиадная подготовка по программированию

В этом случае так же не требуется делать массив глобальным, так как память с помощью new выделяется в куче, на которую не распространяются ограничения для стека. Операция delete[] возвращает выделенную под массив память назад в кучу.

Может также потребоваться заранее инициализированный массив:

#include <iostream>

using namespace std;

int main(int argc, char *argv[]) { const int N = 10;

unsigned char a[N] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};

// обработка массива

return 0;

}

Для динамически создаваемых массивов такой возможности нет.

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

Пусть x – массив из n целых чисел, тогда заполнение его нулями с помощью memset() будет выглядеть так:

memset(x, 0, n * sizeof(int));

ВВОД МАССИВА

Во многих задачах размер массива задаётся во входных данных, а сами элементы идут разделёнными символом пробела. В таком случае организовать ввод массива очень просто:

int n = 0; cin >> n;

int *x = new int[n];

for (int i = 0; i < n; i++) { cin >> x[i];

}

При большом n может оказаться более экономным код в стиле C:

int n = 0; scanf("%d", &n); int *x = new int[n];

for (int i = 0; i < n; i++) { scanf("%d", &x[i]);

}

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

Для первого варианта код может выглядеть так:

int n = 0; do {

cin >> x[n]; n++;

} while (getchar() == ' ');

Тоже самое в стиле C:

int n = 0; do {

Симоненко Евгений А. Олимпиадная подготовка по программированию

17

scanf("%d", &x[n]); n++;

} while (getchar() == ' ');

Код для второго варианта:

int n = 1; cin >> x[0];

while (!cin.eof()) { cin >> x[n]; n++;

}

Тоже самое в стиле C:

int n = 1; scanf("%d", &x[0]); while (!feof(stdin)) {

scanf("%d", &x[n]); n++;

}

У кода для второго варианта есть проблема. Он работает правильно только, если вход не содержит после последнего элемента пустую строку. На C++ это решается может решаться так (если Вы знаете более элегантный способ, то сообщите мне о нём, пожалуйста):

int n = 1; cin >> x[0]; while(1) {

static string tmp; cin >> tmp;

if (tmp.empty()) { break;

}

x[n] = atoi(tmp.c_str()); n++;

tmp.clear();

}

Если нам неизвестно чем заканчивается ввод, то лучше объединить оба случая:

int n = 1; cin >> x[0];

while(!cin.eof()) { static string tmp; cin >> tmp;

if (tmp.empty()) { break;

}

x[n] = atoi(tmp.c_str()); n++;

tmp.clear();

}

Но следующий способ для C++ более элегантен:

while (cin >> x[n]) { //...

}

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

Похожим образом можно поступать и на C:

while (scanf(“%d”, &x[n]) == 1) { //...

}

Этот способ объясняется тем, что scanf() возвращает количество считанных значений.

18	Симоненко Евгений А. Олимпиадная подготовка по программированию

ВЫВОД МАССИВА

Часто требуется вывести значения элементов массива в одну строку, разделяя их символом пробела. Пусть x – массив из n элементов, тогда наиболее очевидный способ сделать это выглядит так:

cout << x[0];

for (int i = 1; i < n; i++) { cout << ' ' << x[i];

}

cout << endl;

При большом количестве элементов вывод в стиле C++ может отнять катастрофически много процессорного времени, поэтому, чтобы избежать неудачной попытки сдать задачу с вердиктом “Time Limit”, лучше сразу использовать вывод в стиле C:

printf("%d", x[0]);

for (int i = 1; i < n; i++) { printf(" %d", x[i]);

}

puts("");

Ещё можно поступить так: сформировать из элементов массива строку, а затем вывести уже её. (То есть сделать что-то типа join в Perl.)

Немного другой способ вывода массива (может потребоваться при выводе результатов во время обработки массива, когда мы не будем знать каким будет первый выведенный элемент, и будет ли вывод элементов вообще):

for (int i = 0; i < n; i++) { cout << x[i] << ' ';

}

int pos = cout.tellp(); cout.seekp(pos - 1); cout << endl;

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

Тоже самое, но в стиле C:

for (int i = 0; i < n; i++) { printf("%d ", x[i]);

}

fseek(stdout, -1, SEEK_END); puts("");

VALARRAY

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

#include <iostream> #include <valarray>

using namespace std;

int main(int argc, char* argv[]) { int n = 0;

cin >> n; valarray<int> a(n);

for (int i = 0; i < a.size(); i++) { cin >> a[i];

}

valarray<int> b(n);

for (int i = 0; i < b.size(); i++) { cin >> b[i];

}