Массивы в С++

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

Выделение памяти (объявление)
int A[5];
double V[8];
bool L[10];
char S[80];
число элементов
const int N = 10;
int A[N];
размер через константу
A[0], A[1], A[2], A[3], A[4]
тип имя_массива[размер];

Обращение к элементу массива
A
массив
2
15
НОМЕР
элемента массива
(ИНДЕКС)
A[0]
A[1]
A[2]
A[3]
A[4]
ЗНАЧЕНИЕ элемента массива
A[2]
НОМЕР (ИНДЕКС)
элемента массива: 2
ЗНАЧЕНИЕ элемента массива: 15

Как обработать все элементы массива?
Объявление:
Обработка:
const int N = 5;
int A[N];
// обработать A[0]
// обработать A[1]
// обработать A[2]
// обработать A[3]
// обработать A[4]

Как обработать все элементы массива?
Обработка с переменной:
i = 0;
// обработать A[i]
i ++;
// обработать A[i]
i ++;
// обработать A[i]
i ++;
// обработать A[i]
i ++;
// обработать A[i]
i ++;
Обработка в цикле:
i = 0;
while ( i < N )
{
// обработать A[i]
i ++;
}
Цикл с переменной:
for( i = 0; i < N; i++ )
{
// обработать A[i]
}

Заполнение массива
main()
{
const int N = 10;
int A[N];
int i;
for ( i = 0; i < N; i++ )
A[i] = i*i;
}

Ввод с клавиатуры и вывод на экран
Объявление:
Ввод с клавиатуры:
Вывод на экран:
const int N = 10;
int A[N];
for ( i = 0; i < N; i++ )
{
cout << "A[" << i << "]=";
cin >> A[i];
}
A[1] =
A[2] =
A[3] =
A[4] =
A[5] =
5
12
34
56
13
cout << "Массив A:\n";
for ( i = 0; i < N; i++ )
cout << A[i] << " ";

Ввод с клавиатуры

Вывод на экран

Заполнение случайными числами
for ( i = 0; i < N; i++ )
{
A[i] = rand()% 81 +20;
cout << A[i] << " ";
}
Задача. Заполнить массив (псевдо)случайными целыми числами в диапазоне от 20 до 100.

Перебор элементов
Общая схема:
for ( i = 0; i < N; i++ ) {
... // сделать что-то с A[i]
}
Подсчёт нужных элементов:
Задача. В массиве записаны данные о росте баскетболистов. Сколько из них имеет рост больше
180 см, но меньше 190 см?
count = 0;
for ( i = 0; i < N; i++ )
if ( 180 < A[i] && A[i] < 190 )
count ++;

Перебор элементов
Среднее арифметическое:
int count, sum;
count = 0;
sum = 0;
for ( i = 0; i < N; i++ )
if ( 180 < A[i] && A[i] < 190 ) {
count ++;
sum += A[i];
}
cout << (float)sum / count;
среднее арифметическое

АЛГОРИТМЫ ОБРАБОТКИ МАССИВОВ

Поиск в массиве
Найти элемент, равный X:
i = 0;
while ( A[i] != X )
i ++;
cout << "A[" << i << "]=" << X;
i = 0;
while ( i < N && A[i] != X )
i ++;
if ( i < N )
cout << "A[" << i << "]=" << X;
else
cout << "Не нашли!";
i < N

Поиск в массиве
nX = -1;
for ( i = 0; i < N; i++ )
if ( A[i] == X )
{
nX = i;
break;
}
if ( nX >= 0 )
cout << "A[" << nX << "]=" << X;
else
cout << "Не нашли!";
Вариант с досрочным выходом:
break;
досрочный выход из цикла

Максимальный элемент
M = A[0];
for ( i = 1; i < N; i++ )
if ( A[i]> M )
M = A[i];
cout << M;

Максимальный элемент и его номер

Реверс массива
«Простое» решение:
for( i = 0; i < N ; i++ ) {
// поменять местами A[i] и A[N+1-i]
}
N/2
остановиться на середине!

Реверс массива
for ( i = 0; i < (N/2); i++ ) {
c = A[i];
A[i] = A[N-1-i];
A[N-1-i] = c;
}

Циклический сдвиг элементов
«Простое» решение:
c = A[0];
for ( i = 0; i < N-1; i++ )
A[i] = A[i+1];
A[N-1] = c;

Отбор нужных элементов
«Простое» решение:
Задача. Отобрать элементы массива A, удовлетворяющие некоторому условию, в массив B.
сделать для i от 0 до N-1
если условие выполняется для A[i] то
B[i]= A[i]
A
B
выбрать чётные элементы

Отбор нужных элементов
A
B
выбрать чётные элементы
count = 0;
for ( i = 0; i < N; i++ )
if ( A[i] % 2 == 0 )
{
B[count] = A[i];
count ++;
}
B[count] = A[i];

СОРТИРОВКА

Что такое сортировка?
Сортировка – это расстановка элементов массива в заданном порядке.
…по возрастанию, убыванию, последней цифре, сумме делителей, по алфавиту, …
Алгоритмы:
простые и понятные, но неэффективные для больших массивов
метод пузырька
метод выбора
сложные, но эффективные
«быстрая сортировка» (QuickSort)
сортировка «кучей» (HeapSort)
сортировка слиянием (MergeSort)
пирамидальная сортировка

Метод пузырька (сортировка обменами)
Идея: пузырек воздуха в стакане воды поднимается со дна вверх.
Для массивов – самый маленький («легкий» элемент перемещается вверх («всплывает»).
сравниваем два соседних элемента; если они стоят «неправильно», меняем их местами
за 1 проход по массиву один элемент (самый маленький) становится на свое место
1-й проход:

Метод пузырька
2-й проход:
3-й проход:
4-й проход:

Метод пузырька
1-й проход:
сделать для j от N-2 до 0 шаг -1
если A[j+1]< A[j] то
// поменять местами A[j] и A[j+1]
2-й проход:
сделать для j от N-2 до 1 шаг -1
если A[j+1]< A[j] то
// поменять местами A[j] и A[j+1]
1
единственное отличие!

Метод пузырька
for ( i = 0; i < N-1; i++ )
for ( j = N-2; j >= i ; j-- )
if ( A[j] > A[j+1] )
{
// поменять местами A[j] и A[j+1]
}
i

Метод выбора (минимального элемента)
Идея: найти минимальный элемент и поставить его на первое место.
сделать для i от 0 до N-2
// найти номер nMin минимального // элемента из A[i]..A[N]
если i != nMin то
// поменять местами A[i] и A[nMin]

Метод выбора (минимального элемента)
for ( i = 0; i < N-1; i++ )
{
nMin = i;
for ( j = i+1; j < N; j++ )
if ( A[j] < A[nMin] )
nMin = j;
if ( i != nMin )
{
// поменять местами A[i] и A[nMin]
}
}
nMin = i;
for ( j = i+1; j < N; j++ )
if ( A[j] < A[nMin] )
nMin = j;

Быстрая сортировка (QuickSort)
Идея: выгоднее переставлять элементы, который находятся дальше друг от друга.

Быстрая сортировка
Шаг 2: переставить элементы так:
при сортировке элементы не покидают « свою область»!
Шаг 1: выбрать некоторый элемент массива X
Шаг 3: так же отсортировать две получившиеся области
Разделяй и властвуй (англ. divide and conquer)
Медиана – такое значение X, что слева и справа от него в отсортированном массиве стоит одинаковое число элементов (для этого надо отсортировать массив…).

Быстрая сортировка
Разделение:
выбрать средний элемент массива (X=67)
установить L = 1, R = N
увеличивая L, найти первый элемент A[L],
который >= X (должен стоять справа)
уменьшая R, найти первый элемент A[R],
который <= X (должен стоять слева)
если L<=R то поменять местами A[L] и A[R] и перейти к п. 3
иначе стоп.

Быстрая сортировка

Быстрая сортировка
const int N = 7;
int A[N];
...
main()
{
// заполнить массив
qSort( 0, N-1 ); // сортировка
// вывести результат
}
Основная программа:
глобальные данные
процедура сортировки

Быстрая сортировка
void qSort( int nStart, int nEnd )
{
int L, R, c, X;
if ( nStart >= nEnd ) return; // готово
L = nStart; R = nEnd;
X = A[(L+R)/2]; // или X = A[irand(L,R)];
while ( L <= R ) { // разделение
while ( A[L] < X ) L ++;
while ( A[R] > X ) R --;
if ( L <= R ) {
c = A[L]; A[L] = A[R]; A[R] = c;
L ++; R --;
}
}
qSort ( nStart, R ); // рекурсивные вызовы
qSort ( L, nEnd );
}

Быстрая сортировка
void qSort( int A[], int nStart,
int nEnd )
{
... qSort ( A, nStart, R );
qSort ( A, L, nEnd );
}
Передача массива через параметр:
A,
A,
int A[],
main()
{ // заполнить массив
qSort( A, 0, N-1 ); // сортировка
// вывести результат
}
A,

Быстрая сортировка
Сортировка массива случайных значений:

ДВОИЧНЫЙ ПОИСК

Двоичный поиск
X = 7
X < 8
8
4
X > 4
6
X > 6
Выбрать средний элемент A[c] и сравнить с X.
Если X = A[c], то нашли (стоп).
Если X < A[c], искать дальше в первой половине.
Если X > A[c], искать дальше во второй половине.

Двоичный поиск
X = 44

Двоичный поиск
int X, L, R, c;
L = 0; R = N; // начальный отрезок
while ( L < R-1 )
{
c = (L+R) / 2; // нашли середину
if ( X < A[c] ) // сжатие отрезка
R = c;
else L = c;
}
if ( A[L] == X )
printf ( "A[%d]=%d", L, X );
else printf ( "Не нашли!" );

Двоичный поиск
скорость выше, чем при линейном поиске
нужна предварительная сортировка
Число сравнений:

МАТРИЦЫ

Что такое матрица?
Матрица — это прямоугольная таблица, составленная из элементов одного типа (чисел, строк и т.д.). Каждый элемент матрицы имеет два индекса – номера строки и столбца.
строка 1, столбец 2

Объявление матриц
const int N = 3, M = 4;
int A[N][M];
double X[10][12];
bool L[N][2];
строки
столбцы
строки
столбцы
тип имя_массива[n][m];
Матрицу можно объявить так:
где n-количество строк, m-количество столбцов.

Простые алгоритмы
Заполнение случайными числами:
for ( i = 0; i < N; i++ ) {
for ( j = 0; j < M; j++ ) {
A[i][j] = rand()%80;
cout << width(3);
cout << A[i][j];
}
cout << endl;
}
Суммирование:
sum = 0;
for ( i = 0; i < N; i++ )
for ( j = 0; j < M; j++ )
sum += A[i][j];

Перебор элементов матрицы
Главная диагональ:
for ( i = 0; i < N; i++ ) {
// работаем с A[i][i]
}
Побочная диагональ:
for ( i = 0; i < N; i++ ){
// работаем с A[i][N-1-i]
}
Главная диагональ и под ней:
for ( i = 0; i < N; i++ )
for ( j = 0; j <= i ; j++ )
{
// работаем с A[i][j]
}