10.13 Массивы

Массивы (без указателей). Основные алгоритмы обработки массивов.

• Хранение однотипных последовательностей
• Индексирование (доступ к элементу) последовательностей

⇒ Объём / скорость доступа к элементу

Для чего массивы хранятся в ячейках оперативной памяти непрерывно?

• Подсказка: массив — это однотипная последовательность

Какой размер имеет целочисленный массив на 1000 элементов?

Одномерные массивы

Как и переменные, бывают глобальные, статические и динамические. Большие динамические массивы делать нехорошо.

• Объявить, ввести, вывести в обратном порядке.

• Инициализируются нулями

• Ввести последовательность целых, вывести все элементы, превосходящие последний

• Ввести, массив. Ввести ещё одно число, вставить его в начало массива, а последний элемент отбросить; вывести

  •   1 2 3 4 5 6 7 8 9 10
      42

    →

      42 1 2 3 4 5 6 7 8 9

  • Вычислительная сложность операции вставки

Инициализация массива

• Полная int n[5] = {1,2,3,4,5}

  • частичная: int n[5] = {[4]=4,[1]=1,2,3}; // holds 0,1,2,3,4

• Массивы заводятся при компиляции прямо в программе, если инициализированы

  • 

       1 int a[WIDTH] ={1, [WIDTH-1]=2};
       2 int main() {
       3         return 1;
       4 }
    

    • cc -DWIDTH=размер o.c; strip a.out; ls -l a.out

Выход за границы массива

• Написать функцию printA(m, n), которая выводит элементы статического массива A[] = {1,2,3,4,5,6,7,8,9,10)A[m],…, A[n-1], и программу, которая вводит m и n и вызывает printA(m, n)

  • Повводить разные m и n (в т. ч. отрицательные). А! Каково?

• Добавить объявление инициализированных переменных перед и после статического массива.

  • Найти их с помощью m и n!

• Добавить в ключи компиляции -fsanitize=bounds, проверить на разных m / n

  • Заменить -fsanitize=bounds на -fsanitize=address

Многомерные массивы

• Объявляются как массивы массивов: int Table[10][5]

• Однако в действительности многомерный массив — это одномерный массив с другими правилами вычисления адреса элемента

     1 int Arr[4][3] = {
     2   { 1, 2, 3},
     3   { 4, 5, 6},
     4   { 7, 8, 9},
     5   {10,11,12}
     6 };
     7 
     8 int main(void) {
     9         return 0;
    10 }
  

  • readelf -j.data a.out — секция данных исполняемого файла

• Написать функцию вывода статического массива A размером 4×4. Ввести массив, вывести

• Ввести массив, вывести, транспонировать, вывести ещё раз

• TODO если успеем — ещё упражненьку

Д/З

TODO доформулировать

1. Гистограмма W: ввести массив (вообще-то это необязательно) из 16 вещественных чисел и ширину экрана W, вывести горизонтальную гистограмму из символов *, в которой максимальному значению массива будет соответствовать строка из W звёздочек, а остальные строки будут пропорциональны по длине. TODO чётко сформулировать правила округления

2. Гистограмма H: ввести массив из 24 целых и высоту экрана H, вывести гистограмму, в которой максимальному значению массива будет соответствовать столбик из H звёздочек. Гистограмма «растёт» снизу.

3. Вести массив из 24 элементов, далее в цикле вводить n и циклически сдвигать массив на n элементов «вперёд»: A₀…Aₙ…Aᵢ → Aₙ…A₂₃A₀…Aₙ₋₁ до конца ввода. Вывести полученный массив. Поддерживать отрицательные и большие по модулю n.

4. Проверить, (1) является ли введённая матрица 10×10 симметричной, (2) можно ли её элементы расположить в виде m, m+1, … q-1, q, q, q-1, … m+1, m TODO не слишком ли мудрёно? в действительности это очень простое условие. Вывести два ответа.