Презентация_3_1_Массивы_одномерные_и_двумерные_Полная

1.

Массивы одномерные и двумерные
ОП.04 / ОП.06 Основы алгоритмизации и программирования · Тема 3.1 · 4
часа
Университетский колледж ВолГУ · специальности 09.02.07, 09.02.11 · 2026-2027 учебный год

2.

Занятие 1. Одномерные массивы
Объявление, индексы, память, обход, типовые алгоритмы

3.

Задача «выше среднего»
• В группе 5 студентов: ввести оценки, найти средний балл и число оценок
выше среднего
• Средний балл известен только после ввода последней оценки
• А сравнивать со средним нужно каждую оценку, в том числе первую
— Значит, нужен второй проход по тем же данным — их надо где-то хранить
• Пять переменных g1 … g5? А если студентов 30 или 3000?
— Цикл не умеет перебирать g1, g2, g3 по номеру: для компилятора это разные имена
Нужна одна переменная, которая хранит много значений и выдаёт любое по номеру — массив

4.

Вопрос к аудитории
Можно ли решить эту задачу одним циклом, как
задачу о сумме?
Нет: среднее известно только в конце, а сравнить со средним нужно каждую оценку.
Оценки должны сохраниться до второго прохода.

5.

Массивы вокруг нас
• Изображение — двумерный массив пикселей: кадр 1920 × 1080 — более 2
млн элементов
• Звук — одномерный массив отсчётов: 1 секунда стерео при 44 100 Гц — 88
200 чисел
• Таблица Excel, журнал успеваемости — двумерный массив: строки и столбцы
• Игровое поле: шахматы, «Морской бой», «Сапёр» — двумерный массив
клеток
• Строки, сортировки, файлы в следующих темах — внутри них тоже массивы

6.

Определение массива
• Массив — упорядоченный набор фиксированного количества элементов
одного типа,
— хранящихся в памяти непрерывно и доступных по общему имени и индексу
• Три ключевых свойства:
— все элементы одного типа: только int, только double, только char
— количество элементов фиксируется при объявлении и не меняется
— элементы лежат в памяти вплотную, без промежутков
Аналогия: ряд камер хранения — общая вывеска (имя), номер ячейки (индекс), одинаковый размер (тип)

7.

Объявление массива
// тип имя[количество_элементов];
int scores[30];
// 30 целых чисел: баллы группы
double prices[100];
// 100 вещественных чисел: цены
char letters[26];
// 26 символов
const int SIZE = 30;
int group[SIZE];
// размер - именованная константа
// верно: SIZE известен при компиляции
int n = 0;
cin >> n;
int a[n];
// ОШИБКА с точки зрения стандарта C++
GCC пропускает int a[n] как расширение, Visual Studio — нет. Пишем по стандарту

8.

Индексы элементов
• Обращение к элементу — через квадратные скобки: scores[0], scores[1],
scores[i]
• Индексы в C++ начинаются с нуля
• Массив из N элементов имеет индексы от 0 до N − 1
— int a[5]: существуют a[0], a[1], a[2], a[3], a[4]
— элемента a[5] нет

9.

Вопрос к аудитории
Почему создатели языка решили нумеровать
элементы с нуля, а не с единицы?
Ответ — в том, как массив устроен в памяти: индекс — это смещение от начала
массива.

10.

Массив в памяти
адрес a[i] = адрес начала + i × размер элемента: доступ к любому элементу за одно и то же время

11.

#include <iostream>
using namespace std;
int main() {
int a[5] = {10, 20, 30, 40, 50};
cout << "Размер массива в байтах: " << sizeof(a) << endl;
cout << "Размер одного элемента: " << sizeof(a[0]) << endl;
cout << "Количество элементов: " << sizeof(a) / sizeof(a[0]) << endl;
for (int i = 0; i < 5; i++) {
cout << "a[" << i << "] = " << a[i] << ", адрес " << &a[i] << endl;
}
return 0;
}
Результат выполнения на одном из компьютеров:
Размер массива в байтах: 20
Размер одного элемента: 4
Количество элементов: 5
a[0] = 10, адрес 0x16dd196c0
a[1] = 20, адрес 0x16dd196c4
a[2] = 30, адрес 0x16dd196c8
a[3] = 40, адрес 0x16dd196cc
a[4] = 50, адрес 0x16dd196d0

12.

Проверка: sizeof и адреса элементов
int a[5] = {10, 20, 30, 40, 50};
cout << sizeof(a) << endl;
// 20 - весь массив в байтах
cout << sizeof(a[0]) << endl;
// 4 - один элемент
cout << sizeof(a) / sizeof(a[0]) << endl; // 5 - количество элементов
for (int i = 0; i < 5; i++)
cout << "a[" << i << "] = " << a[i] << ", адрес " << &a[i] << endl;
// a[0] = 10, адрес 0x16dd196c0
// a[1] = 20, адрес 0x16dd196c4
// a[2] = 30, адрес 0x16dd196c8
<- каждый следующий
<- больше на 4 байта
Адреса на вашем компьютере будут другими; важна разница между соседними — ровно 4 байта

13.

Способы инициализации массива
int a[5] = {1, 2, 3, 4, 5};
int b[5] = {7, 8};
int c[5] = {};
int d[] = {3, 1, 4, 1, 5, 9};
int e[5];
// 1 2 3 4 5 - полная
// 7 8 0 0 0 - частичная
// 0 0 0 0 0 - обнуление
// размер 6 считает компилятор
// мусор: значения не определены
int x[3] = {1, 2, 3};
int y[3];
y = x;
// ОШИБКА компиляции: массивы не присваиваются
if (x == y) {} // компилируется, но сравнивает адреса
Массив либо инициализируется при объявлении, либо заполняется циклом до первого чтения

14.

Шаблон обхода массива (ГОСТ 19.701-90)
i = 0; i < N; i++
выход
тело
Действие с элементом a[i]
Следующий оператор
Счётчик становится индексом: начинается с 0, условие строгое i < N — последний индекс N − 1

15.

#include <iostream>
using namespace std;
int main() {
const int N = 5;
double grades[N];
// количество оценок
// массив из пяти вещественных чисел
cout << "Введите " << N << " оценок: ";
for (int i = 0; i < N; i++) {
cin >> grades[i];
// i-я оценка попадает в i-ю ячейку
}
double sum = 0.0;
for (int i = 0; i < N; i++) {
sum += grades[i];
}
double average = sum / N;
int above = 0;
for (int i = 0; i < N; i++) { // второй проход по тем же данным
if (grades[i] > average) {
above++;
}
}
cout << "Среднее: " << average << endl;
cout << "Выше среднего: " << above << endl;
return 0;
}

16.

Решение задачи «выше среднего»
const int N = 5;
double grades[N];
for (int i = 0; i < N; i++) cin >> grades[i];
double sum = 0.0;
for (int i = 0; i < N; i++) sum += grades[i];
double average = sum / N;
int above = 0;
for (int i = 0; i < N; i++)
if (grades[i] > average) above++;
// количество оценок
// сумма
cout << "Среднее: " << average << endl;
cout << "Выше среднего: " << above << endl;
// 4
// 2
// ввод
// второй проход
Ввод 4 5 3 5 3. Для группы из 25 человек меняется одно число: const int N = 25;

17.

#include <iostream>
using namespace std;
int main() {
int a[5] = {1, 2, 3, 4, 5};
for (int i = 0; i <= 5; i++) {
cout << a[i] << " ";
}
cout << endl;
a[5] = 100;
return 0;
}

18.

Выход за границы массива
int a[5] = {1, 2, 3, 4, 5};
for (int i = 0; i <= 5; i++) {
cout << a[i] << " ";
}
cout << endl;
a[5] = 100;
// ОШИБКА: <= вместо <
// при i = 5 читается чужая память
// ОШИБКА: запись за границу
// Вывод на одном из компьютеров:
// 1 2 3 4 5 2
C++ не проверяет границы массива: это неопределённое поведение (undefined behavior)

19.

Вопрос к аудитории
Что произойдёт: ошибка компиляции, ошибка при
запуске или что-то другое?
Программа скомпилируется и запустится. При i = 5 она прочитает соседнюю память,
а a[5] = 100 молча испортит чужие данные.

20.

Выход за границы: запись в соседнюю переменную
Heartbleed (OpenSSL, 2014): чтение за границей буфера раскрыло ключи и пароли серверов

21.

Правила безопасной работы с индексами
• В заголовке цикла по массиву — i < N, а не i <= N
• Размер массива — в именованной константе, её используют все циклы
• Перед обращением к a[k] с вычисленным или введённым k — проверка k >= 0
&& k < N
• Инструменты помогают не всегда:
— Clang предупреждает только о константном индексе: array index 5 is past the end
— Visual Studio в отладке: Stack around the variable 'a' was corrupted
Ответственность за границы массива полностью лежит на программисте

22.

Типовые алгоритмы: сумма, среднее, максимум
const int N = 8;
int a[N] = {12, -5, 7, 0, 23, -8, 7, 15};
int sum = 0;
for (int i = 0; i < N; i++) sum += a[i];
double average = static_cast<double>(sum) / N;
// 1. сумма и среднее
int maxIndex = 0;
for (int i = 1; i < N; i++)
if (a[i] > a[maxIndex]) maxIndex = i;
// 2. максимум
// 6.375, а не 6
// Сумма: 51, среднее: 6.375
// Максимум: 23 (индекс 4)
Эталон — первый элемент, цикл с i = 1. Храним индекс: по нему получим и значение a[maxIndex]

23.

Проход по массиву: сумма и максимум

24.

Типовые алгоритмы: подсчёт и линейный поиск
int positive = 0;
for (int i = 0; i < N; i++)
if (a[i] > 0) positive++;
int target = 7;
int foundIndex = -1;
for (int i = 0; i < N; i++) {
if (a[i] == target) {
foundIndex = i;
break;
}
}
// Число 7 найдено на позиции 2
// 3. подсчёт по условию
// Положительных: 5
// 4. линейный поиск
// -1 означает "не найдено"
// первое вхождение найдено
Без break поиск найдёт последнее вхождение. Двоичный поиск — в теме 5.1

25.

Вопрос к аудитории
Если максимальных элементов два, какой индекс
выдаст программа — первый или последний?
Первый: условие строгое, a[i] > a[maxIndex]. Если заменить > на >=, лидерство будет
перехватывать каждый равный элемент и останется последний.

26.

Вместимость и количество элементов
const int MAX_SIZE = 100;
// вместимость: сколько ячеек выделено
int data[MAX_SIZE];
int count = 0;
// сколько ячеек заполнено
int value = 0;
cin >> value;
while (value != 0 && count < MAX_SIZE) {
data[count] = value;
// первая свободная ячейка
count++;
cin >> value;
}
for (int i = 0; i < count; i++) // только заполненная часть
cout << data[i] << " ";
// ввод 15 8 42 4 0 -> 15 8 42 4
Автобус на 40 мест: вместимость всегда 40, а едут сейчас 17 — кондуктор помнит число 17

27.

1. Какой индекс у последнего элемента массива
double t[12]?
2. 2. Сколько байт займёт массив int m[25],
если int занимает 4 байта?
3. 3. Что хранится в элементах массива int b[4]
= {9};?
4. 4. Почему в заголовке цикла мы пишем i < N, а
не i <= N?

28.

Итоги первого занятия
• Массив — однотипные элементы подряд в памяти, общее имя, доступ по
индексу
• Индекс — смещение от начала: нумерация от 0 до N − 1
• Размер — константа; {} обнуляют массив целиком
• Выход за границы компилятор в общем случае не видит — неопределённое
поведение
• Типовые алгоритмы: сумма и среднее, максимум с индексом, подсчёт,
линейный поиск с −1 и break
• Массив переменного заполнения: вместимость MAX_SIZE и количество count
Мини-опрос: индекс последнего элемента double t[12]? Размер int m[25]? Что в int b[4] = {9};?

29.

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

30.

Одномерные и двумерные данные
• Одномерный массив — список: оценки по одной дисциплине, температура по
дням, цены
• Двумерный массив — таблица из строк и столбцов:
— журнал преподавателя: студенты × занятия
— кинозал: ряды × места; шахматная доска: 8 × 8 клеток
— фотография: пиксели по высоте × по ширине
• Сначала — перестановки внутри одномерного массива: они понадобятся для
сортировок в теме 5.1

31.

Обмен двух элементов
int temp = a[0];
a[0] = a[1];
a[1] = temp;
// сок во временный стакан
// молоко на место сока
// сок на место молока
// ОШИБКА: обмен без временной переменной
a[0] = a[1];
// старое a[0] потеряно навсегда
a[1] = a[0];
// оба элемента теперь равны старому a[1]
Два стакана с соком и молоком меняют местами только с третьим, пустым стаканом

32.

Реверс массива
// 1 2 3 4 5 6 -> 6 5 4 3 2 1
for (int i = 0; i < n / 2; i++) {
int t = a[i];
a[i] = a[n - 1 - i];
a[n - 1 - i] = t;
}
// только до середины
// пара для i - элемент n - 1 - i
// При нечётном n средний элемент остаётся на месте:
// n = 5 -> 5 / 2 = 2 итерации
С i < n массив развернётся дважды и вернётся в исходное состояние — без всякой ошибки

33.

Циклический сдвиг вправо и удаление элемента
// Сдвиг вправо: 6 5 4 3 2 1 ->
int last = a[n - 1];
for (int i = n - 1; i > 0; i--)
a[i] = a[i - 1];
a[0] = last;
1 6 5 4 3 2
// спасаем последний элемент
// идём справа налево
// Удаление k = 2: 1 6 5 4 3 2 ->
for (int i = k; i < n - 1; i++)
a[i] = a[i + 1];
n--;
1 6 4 3 2
// идём слева направо
// рабочий размер уменьшился
Направление цикла выбирается так, чтобы не затереть ещё не перемещённое значение

34.

Полная программа, выполняющая все преобразования
#include <iostream>
using namespace std;
int main() {
const int N = 6;
int a[N] = {1, 2, 3, 4, 5, 6};
int n = N;
// удаление элемента с индексом 2
int k = 2;
for (int i = k; i < n - 1; i++) {
a[i] = a[i + 1];
}
n--;
for (int i = 0; i < n; i++) cout << a[i] << " ";
cout << endl;
return 0;
// рабочий размер
// реверс
for (int i = 0; i < n / 2; i++) {
int t = a[i];
a[i] = a[n - 1 - i];
a[n - 1 - i] = t;
}
for (int i = 0; i < n; i++) cout << a[i] << " ";
cout << endl;
// циклический сдвиг вправо на одну позицию
int last = a[n - 1];
for (int i = n - 1; i > 0; i--) {
a[i] = a[i - 1];
}
a[0] = last;
for (int i = 0; i < n; i++) cout << a[i] << " ";
cout << endl;
}
Результат:
6 5 4 3 2 1
1 6 5 4 3 2
1 6 4 3 2

35.

Заполнение массива случайными числами
#include <cstdlib>
#include <ctime>
// rand, srand
// time
srand(time(0));
for (int i = 0; i < n; i++) {
a[i] = rand() % 101 - 50;
}
// один раз в начале программы
// Формула диапазона [low; high]:
low + rand() % (high - low + 1)
// rand() % 101 даёт 0..100
Вызов srand(time(0)) задаёт начальное значение генератора по текущему времени.
Без него при каждом запуске программа получала бы одну и ту же последовательность чисел.

36.

Двумерный массив — таблица
const int ROWS = 3;
const int COLS = 4;
int m[ROWS][COLS] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12}
};
// 3 строки по 4 столбца, 12 элементов
// m[i][j]: i - номер строки, j - номер столбца, оба с нуля
// int z[ROWS][COLS] = {}; - обнуляет все элементы
Кинозал: билет «ряд 2, место 3» — это m[2][3]. Первый индекс всегда строка.

37.

Обход вложенными циклами: вывод в виде таблицы
#include <iostream>
#include <iomanip>
using namespace std;
int main() {
const int ROWS = 3;
const int COLS = 4;
int m[ROWS][COLS] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12}
};
// вывод в виде таблицы
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
cout << setw(4) << m[i][j];
}
cout << endl;
}
// внешний цикл - строки
// внутренний - столбцы

38.

Обход вложенными циклами: суммы строк и столбцов
// сумма каждой строки
for (int i = 0; i < ROWS; i++) {
int rowSum = 0;
// обнуляем для каждой строки
for (int j = 0; j < COLS; j++) {
rowSum += m[i][j];
}
cout << "Строка " << i << ": " << rowSum << endl;
}
// сумма каждого столбца: циклы меняются местами
for (int j = 0; j < COLS; j++) {
int colSum = 0;
for (int i = 0; i < ROWS; i++) {
colSum += m[i][j];
}
cout << "Столбец " << j << ": " << colSum << endl;
}
return 0;
}

39.

Двумерный массив в памяти
Для адреса нужно знать COLS, поэтому в параметре функции указывают число столбцов

40.

Диагонали квадратной матрицы 4 × 4
i\j
0
1
2
3
0
3
8
1
6
1
7
2
9
4
2
5
11
0
10
3
12
1
4
2
Главная диагональ (голубая): i == j. Побочная диагональ (жёлтая): i + j == N − 1.
Выше главной: i < j. Ниже главной: i > j.

41.

Нахождение суммы элементов главной и побочной
диагоналей
#include <iostream>
#include <iomanip>
using namespace std;
int main() {
const int N = 4;
int m[N][N] = {
{ 3, 8, 1, 6},
{ 7, 2, 9, 4},
{ 5, 11, 0, 10},
{12, 1, 4, 2}
};
// главная (i == j) и побочная (i + j == N - 1) диагонали
int mainSum = 0;
int sideSum = 0;
for (int i = 0; i < N; i++) {
mainSum += m[i][i];
sideSum += m[i][N - 1 - i];
}
cout << "Главная диагональ: " << mainSum << endl;
cout << "Побочная диагональ: " << sideSum << endl;

42.

Нахождение максимального элемента и его позиции
// максимум с позицией
int maxRow = 0;
int maxCol = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (m[i][j] > m[maxRow][maxCol]) {
maxRow = i;
maxCol = j;
}
}
}
cout << "Максимум " << m[maxRow][maxCol]
<< " в строке " << maxRow << ", столбце " << maxCol << endl;

43.

Транспонирование матрицы
// транспонирование на месте: только выше главной диагонали
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
int t = m[i][j];
m[i][j] = m[j][i];
m[j][i] = t;
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << setw(4) << m[i][j];
}
cout << endl;
}
return 0;
}
j = i + 1: иначе каждая пара поменяется дважды и матрица вернётся в исходное состояние

44.

Передача массивов в функции
Функция — это именованный фрагмент программы, который можно вызвать из main.
Вы уже вызывали готовые функции: sqrt(x), pow(x, 2), rand().
Свою функцию можно описать до main так:
тип_результата имя(параметры) {
// тело функции
return результат;
// если тип_результата не void
}
Если функция ничего не возвращает, а только выполняет действие,
например выводит на экран, её тип результата — void.
Функции подробно — в теме 4.1. Сегодня — минимум для ЛР

45.

Массив как параметр функции
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>
using namespace std;
const int COLS = 4;
// заполняет массив случайными числами из диапазона [low; high]
void fillRandom(int a[], int n, int low, int high) {
for (int i = 0; i < n; i++) {
a[i] = low + rand() % (high - low + 1);
}
}
// выводит массив в одну строку; const - функция обещает не менять элементы
void printArray(const int a[], int n) {
for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}
cout << endl;
}

46.

Массив как параметр функции
// возвращает сумму элементов
int sumArray(const int a[], int n) {
int sum = 0;
for (int i = 0; i < n; i++) {
sum += a[i];
}
return sum;
}
// заменяет отрицательные элементы нулями - изменения видны в main
void replaceNegatives(int a[], int n) {
for (int i = 0; i < n; i++) {
if (a[i] < 0) {
a[i] = 0;
}
}
}
// выводит матрицу: число столбцов обязано быть указано в типе параметра
void printMatrix(const int m[][COLS], int rows) {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < COLS; j++) {
cout << setw(4) << m[i][j];
}
cout << endl;
}
}

47.

Массив как параметр функции
int main() {
const int N = 6;
int a[N] = {4, -2, 7, -9, 0, 5};
printArray(a, N);
// 4 -2 7 -9 0 5
cout << "Сумма: " << sumArray(a, N) << endl;
replaceNegatives(a, N);
printArray(a, N);
// 4 0 7 0 0 5
int m[2][COLS] = {{1, 2, 3, 4}, {5, 6, 7, 8}};
printMatrix(m, 2);
srand(time(0));
int r[10];
fillRandom(r, 10, -50, 50);
printArray(r, 10);
return 0;
}

48.

Правила
• Размер массива передаётся отдельным параметром n
• Массив не копируется: функция работает с исходными данными
• Слово const защищает от случайной порчи.
const int a[] — функция обещает не менять элементы, компилятор это
проверит
• У двумерного массива количество столбцов указывается в параметре:
const int m[][COLS] — без COLS не вычислить i × COLS + j

49.

Чек-лист ошибок при работе с массивами
Ошибка
Пример
Последствие
Выход за границы
i <= N в заголовке цикла
Мусор или порча соседних данных
Неинициализированный массив int a[10]; и сразу sum += a[i]
Случайный результат
Размер из переменной
cin >> n; int a[n];
Не компилируется в Visual Studio
Обмен без временной
переменной
a[i] = a[j]; a[j] = a[i];
Оба элемента равны
Реверс или транспонирование
по всему диапазону
for (i = 0; i < n; i++)
Массив возвращается в исходное
состояние

50.

Чек-лист ошибок при работе с массивами (2/2)
Ошибка
Пример
Последствие
Сдвиг вправо слева направо
a[i] = a[i - 1] при i = 1, 2, …
Весь массив — копия a[0]
Накопитель вне внешнего
цикла
int rowSum = 0; перед циклом по i Нарастающий итог
Перепутаны индексы
m[j][i] вместо m[i][j]
Неверный результат или выход за
границы
sizeof параметра-массива
sizeof(a) внутри функции
Размер адреса, а не массива

51.

Итоги темы 3.1
1. Массив — набор однотипных элементов, лежащих в памяти подряд. Индексы от 0 до N 1, размер задаётся константой, границы контролирует программист.
2. Типовые алгоритмы чтения: сумма и среднее, максимум с индексом, подсчёт по
условию, линейный поиск с -1 и break.
3. Типовые алгоритмы изменения: обмен через временную переменную, реверс до
середины, циклический сдвиг, удаление со сдвигом и уменьшением рабочего размера.
4. Двумерный массив — таблица, хранящаяся построчно. Строки, столбцы, диагонали,
транспонирование обрабатываются вложенными или одиночными циклами.
5. Передача в функцию: массив не копируется, размер передаётся отдельно, const
защищает от изменения, у двумерного массива в параметре указывается число
столбцов.