Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Языки и методы программирования - лекция-9: мас...

Anton
December 08, 2024

Языки и методы программирования - лекция-9: массивы в Си

Лекция курса "Языки и методы программирования"
Лекция-9: массивы в Си
- Массивы в Си, размещение в памяти, массивы vs указатели
- Массив — определение
- Программа - объявление массива, обращение, обход элементов на Си
- Размещение массива в памяти
- Почему нельзя растянуть массив больше, чем исходный размер? (выход за пределы массива)
- Массивы и указатели: синтаксические сходства, фундаментальные отличия
- Передача массива в функцию в качестве параметра
- Узнать размер массива: sizeof ok?
- Возврат массива из функции в качестве возвращаемого значения
- Задания для самостоятельной работы

Anton

December 08, 2024
Tweet

More Decks by Anton

Other Decks in Education

Transcript

  1. Массив • Массив — это последовательность однотипных элементов, расположенных в

    памяти последовательно рядом друг за другом • Массив объявляется в коде как одна переменная • Обращение к элементам массива синтаксически происходит через эту переменную и порядковые номера элементов — индексы
  2. Создадим массив, заполним и выведем элементы #include <stdio.h> int main(void)

    { int arr[3]; // запись в массив по индексу arr[0] = 3; arr[1] = 13; arr[2] = 34; // обращение к элементам по индексу printf("%d, %d, %d\n", arr[0], arr[1], arr[2]); // обход массива в цикле for(int i=0; i < 3; i++) { printf("arr[%d]=%d\n", i, arr[i]); } }
  3. Что произошло • Объявили массив из 3-х элементов • Записали

    значения, обращаясь к каждому элементу по порядковому номеру — индексу • (обратите внимание, нумерация начинается с 0-ля) int arr[3]; // запись в массив по индексу arr[0] = 3; arr[1] = 13; arr[2] = 34;
  4. Что произошло • Напечатали выбранные элементы, обращаясь к каждому по

    индексу // обращение к элементам по индексу printf("%d, %d, %d\n", arr[0], arr[1], arr[2]);
  5. Что произошло • Обошли весь массив в цикле автоматически и

    тоже напечатали элементы // обход массива в цикле for(int i=0; i < 3; i++) { printf("arr[%d]=%d\n", i, arr[i]); }
  6. Самостоятельно • Исследуйте сгенерированный из этого кода на языке Си

    ассемблерный код (x86 или MIPS ASM) • Инструменты: «gcc -g» + «objdump -S» • Вся суть — склеить адрес элемента массива из 3-х составляющих: указатель стека, базовое смещение массива относительно указателя стека, смещение элемента массива относительно начала массива
  7. • Это было то, что можно делать с массивом •

    Гораздо интереснее посмотреть на то, что с массивами делать нельзя • И еще интереснее узнать, почему нельзя • И еще интереснее посмотреть, что будет, если все-таки сделать так, как не следует
  8. #include <stdio.h> int main(void) { int arr[3]; int b =

    65; printf("b=%d\n", b); arr[0] = 3; arr[1] = 13; arr[2] = 34; arr[3] = 117; // нашли место для 4-го элемента массива arr[3]! printf("arr: %d, %d, %d, %d\n", arr[0], arr[1], arr[2], arr[3]); } Предположим, у нас вот такой код
  9. • Мы создали массив из 3-х элементов, зарезервировали для него

    место • Объявили просто так еще одну переменную • А потом решили, что нам в массиве нужно не 3, а 4 элемента
  10. • Можем ли мы поместить в тот же массив 4-й

    элемент? • Давайте попробуем просто взять и записать 4-й элемент по индексу массива • Может быть компилятор (или окружение выполнения) окажется достаточно умным для того, чтобы догадаться, что нам нужно еще место, и придумает, куда этот 4-й элемент разместить
  11. #include <stdio.h> int main(void) { int arr[3]; int b =

    65; printf("b=%d\n", b); arr[0] = 3; arr[1] = 13; arr[2] = 34; arr[3] = 117; // нашли место для 4-го элемента массива arr[3]! printf("arr: %d, %d, %d, %d\n", arr[0], arr[1], arr[2], arr[3]); // wtf?? printf("b=%d\n", b); // *** stack smashing detected ***: arr[4] = 85; }
  12. > gcc prog-array-overflow.c > ./a.out b=65 arr: 3, 13, 34,

    117 b=65 • Значение переменной b не поменялось • Повреждения стека и вылета приложения тоже не произошло
  13. Почему так? • Компилятор располагает элементы в памяти так, как

    считает нужным • В этом случае, очевидно, что он расположил простую переменную b ближе к вершине стека, чем массив arr • Поэтому адреса arr растут в противоположном направлении от переменной b, • поэтому даже выход за пределы массива не может её повредить.
  14. #include <stdio.h> int main(void) { int arr[3]; int barr[3]; barr[0]

    = 65; printf("barr[0]=%d\n", barr[0]); arr[0] = 3; arr[1] = 13; arr[2] = 34; arr[3] = 116; arr[4] = 117; // b[0] будет перезаписана значением 117 printf("barr[0]=%d\n", barr[0]); // *** stack smashing detected ***: ./a.out terminated // Аварийный останов (сделан дамп памяти) for(int i=0; i < 11; i++) { arr[i] = i; } }
  15. > gcc prog-array-overflow-works.c > ./a.out barr[0]=65 barr[0]=117 *** stack smashing

    detected ***: ./a.out terminated Аварийный останов (сделан дамп памяти) • Перезаписали значение barr[0], не обращаясь к нему напрямую • Стек тоже получилось повредить
  16. Замечания • Очевидно, что эти упражнения с индексами мы производим

    не для того, чтобы использовать в программах, а для того, чтобы лучше понимать, что там внутри за абстракциями синтаксиса происходит • Результаты нештатного поведения будут отличаться на разных операционных системах, разных компиляторах, разных опциях одного компилятора, даже в зависимости от того, какой еще код присутствует в программе
  17. Замечания • Например, если указать размер массива barr не 3,

    а 2, то компилятор поменяет его и массив arr в памяти местами, и barr опять не будет поврежден • Между массивами arr и barr компилятор резервирует ячейку под int (8 байт у меня, 4 байта на картинке), т. к. перезаписать barr[0] получается не через arr[3], а через arr[4] (бог его знает, на что резервирует) • Повреждение стека получается достичь только вариантом с циклом. Если просто обратиться к массиву по достаточно большому адресу (например, arr[400]=85), повреждения не происходит (очевидно, компилятор как-то определяет такую ситуацию и что-то там химичит у себя)
  18. Замечания • При выходе за пределы стека у нас вылетает

    приложение • При выходе за пределы массива внутри стека мы можем повредить внутренние переменные, но приложение продолжает работать • Т. е. за корректностью работы с сегментами памяти у нас может следить операционная система (возможна даже аппаратная защита) и в случае чего бить по рукам • Защиты от повреждений внутри стека нет — с точки зрения системы это просто корректная работа с адресами. Но если вы так не хотели делать, такую ошибку будет сложнее поймать.
  19. А если бы индексы росли в другую сторону? • Тогда

    можно было бы растянуть массив в свободную часть стека вместе с указателем стека?
  20. • Если один массив еще можно было бы растянуть после

    создания хотя бы теоретически • То в случае с двумя массивами такого варианта даже теоретического нет
  21. Итого: почему не растянуть массив? • Во-первых, индексы растут в

    сторону занятой части стека • Во-вторых, даже если бы они росли в сторону незанятой части, один массив там можно было бы нарастить, но два массива — уже нет
  22. Как же быть с 4-м элементом? • Сегодня с ним

    разбираться не будем, разберемся на следующих лекциях Короткие ответы: • Создавайте массив сразу на 4 элемента • Используйте динамическую память — создать новый массив нужного размера, скопировать в него содержимое старого массива (на будущих лекциях) • Используйте списки (динамические контейнеры «без ограничения» по размеру) (на будущих лекциях)
  23. #include <stdio.h> int main(void) { int arr[3]; // запись в

    массив по индексу arr[0] = 3; arr[1] = 13; arr[2] = 34; printf("%d, %d, %d\n", arr[0], arr[1], arr[2]); // настроить указатель на массив int* parr = arr; parr[0] = 103; parr[1] = 113; parr[2] = 134; printf("%d, %d, %d\n", parr[0], parr[1], parr[2]); }
  24. Здесь мы видим • Переменную-массив можно так же рассматривать как

    адрес первого элемента массива, если использовать её в операции присвоения в качестве присваиваемого значения • Указатель на массив — это обычный указатель на тип данных, содержащихся в массиве, мы никаким образом не отличаем, будет ли он указывать на одну переменную или на массив • К указателю можно обращаться через квадратные скобки, как и к массиву — размер шага по индексу будет определяться размером типа данных, для которого объявлен указатель
  25. Здесь мы видим • Внешне работа с массивом и указателем,

    кажется, ничем не отличается, но • Вот так мы можем настраивать указатель на массив: int* parr = arr; • А вот так в обратную сторону делать не можем: arr = parr; > gcc: error: assignment to expression with array type
  26. Почему? • Очевидно, потому, что у этих переменных разная природа

    • Переменная-массив превращается в конкретный адрес (смещение относительно вершины стека) на этапе компиляции в таблице символов (как и простые переменные) • Переменная-указатель представляет собой ячейку памяти, которая содержит адрес другой ячейки — начала блока памяти с элементами массива, её исходное значение задаётся и может меняться в ходе выполнения программы • Одинаковое обращение с ними в коде программы — это решение разработчиков языка Си, «синтаксический сахар», скрывающий разные детали реализации схожих по назначению механизмов • Отличие легко увидеть, если посмотреть на структуру памяти
  27. // так тоже работает, но предупреждает при компиляции // warning:

    assignment from incompatible pointer type // [-Wincompatible-pointer-types] parr = &arr; parr[0] = 203; parr[1] = 213; parr[2] = 234; printf("%d, %d, %d\n", parr[0], parr[1], parr[2]); // просто ок, но так не принято parr = &arr[0]; parr[0] = 303; parr[1] = 313; parr[2] = 334; printf("%d, %d, %d\n", parr[0], parr[1], parr[2]); Так тоже можно, например:
  28. • Главное, чтобы в ячейке parr оказался нужный адрес •

    Кстати, указатели разных типов можно настроить на один и тот же блок памяти или на разные участки одного блока памяти и работать с ним так, как будто в одном случае это последовательность, например, элементов int, а в другом — char и т. п. • Но сейчас не будем развивать эту мысль
  29. • Передавать копию (значение) массива в качестве параметра в функцию

    НЕЛЬЗЯ • В функцию можно передавать указатель на массив (передача параметра по адресу) • Даже в том случае, если параметр функции внешне объявлен как обычный массив, при вызове функции будет отправлен указатель на исходный массив • т. е. массив-параметр будет передан в функцию по адресу, а не по значению
  30. #include <stdio.h> void func_param_array_pointer(int* parr1) { parr1[2] = 126; }

    void func_param_array_generic(int parr2[]) { parr2[2] = 258; } void func_param_array_sized(int parr3[3]) { parr3[2] = 932; } int main(void) { int arr[32]; arr[2] = 83; printf("init: arr[2]=%d\n", arr[2]); func_param_array_pointer(arr); printf("array_pointer: arr[2]=%d\n", arr[2]); func_param_array_generic(arr); printf("array_generic: arr[2]=%d\n", arr[2]); func_param_array_sized(arr); printf("array_sized: arr[2]=%d\n", arr[2]); }
  31. > gcc prog-array-func-param.c > ./a.out init: arr[2]=83 array_pointer: arr[2]=126 array_generic:

    arr[2]=258 array_sized: arr[2]=932 • Скомпилировалось без предупреждений и запустилось без ошибок • Во всех случаях изменение массива-параметра внутри функции привело к изменению значения исходного массива. • Это значит, что во всех случаях массив передаётся по адресу, как бы это ни выглядело со стороны (опять «синтаксический сахар» — не доверяйте интуиции). • Указание размера массива-параметра не повлияло ни на что. Мы передали массив большего размера, чем указан, но об этом не сообщил даже компилятор
  32. #include <stdio.h> void main() { int arr[3]; printf("sizeof(arr[3])=%lu\n", sizeof(arr)); int

    arr2[20]; printf("sizeof(arr2[20])=%lu\n", sizeof(arr2)); int* parr = arr; printf("sizeof(parr)=%lu\n", sizeof(parr)); printf("sizeof(*parr)=%lu\n", sizeof(*parr)); parr = arr2; printf("sizeof(parr=arr2)=%lu\n", sizeof(parr)); } На архитектуре x86_64, gcc=5.4.0
  33. #include <stdio.h> void main() { int arr[3]; printf("sizeof(arr[3])=%lu\n", sizeof(arr)); int

    arr2[20]; printf("sizeof(arr2[20])=%lu\n", sizeof(arr2)); int* parr = arr; printf("sizeof(parr)=%lu\n", sizeof(parr)); printf("sizeof(*parr)=%lu\n", sizeof(*parr)); parr = arr2; printf("sizeof(parr=arr2)=%lu\n", sizeof(parr)); } sizeof(arr[3])=12 На архитектуре x86_64, gcc=5.4.0 sizeof(arr2[20])=80 sizeof(parr)=8 sizeof(*parr)=4 sizeof(parr=arr2)=8
  34. На архитектуре x86_64, gcc=5.4.0 • Размер int: 4 байта •

    Размер массива из 3-х элементов int: 4*3 = 12 байт • Размер массива из 20-ти элементов int: 4*20 = 80 байт • Размер указателя на массив int из 3-х элементов: 8 байт • Размер указателя на массив int из 20-ти элементов: 8 байт • Размер разыменованного указателя на массив int: 4 байта (как один int) • Итого: sizeof для указателя всегда возвращает размер ячейки-указателя, хранящей адрес, т. е. для данной архитектуры это будет всегда одно и то же значение, и не важно, куда ссылается этот адрес, — на обычную переменную или на массив и если на массив, то какого размер массив.
  35. #include <stdio.h> void func_sizeof_arr(int arr[]) { printf("sizeof(param:arr[])=%lu\n", sizeof(arr)); } void

    func_sizeof_parr(int* parr) { printf("sizeof(param:parr)=%lu\n", sizeof(parr)); } void main() { int arr[3]; int arr2[20]; func_sizeof_arr(arr); func_sizeof_parr(arr); func_sizeof_arr(arr2); } sizeof(param:arr[])=8 sizeof(param:parr)=8 sizeof(param:arr[])=8
  36. При передаче массива в функцию • Массив всегда передаётся как

    указатель • Поэтому внутри функции для sizeof стирается контекст в т.ч. для статического массива • Внутри функции для массива-параметра sizeof вернёт обычный размер указателя (8 байт на 64-хбитной системе) • Не важно в какой форме объявлен параметр — как массив («скрытый»/«неявный» указатель) или как явный указатель
  37. • Компилятор gcc при этом выдаст предупреждение: > gcc array-sizeof.c

    -o array-sizeof array-sizeof.c: In function ‘func_sizeof_arr’: array-sizeof.c:5:47: warning: ‘sizeof’ on array function parameter ‘arr’ will return size of ‘int *’ [-Wsizeof-array-argument] printf("sizeof(param:arr[])=%lu\n", sizeof(arr)); ^ array-sizeof.c:4:26: note: declared here void func_sizeof_arr(int arr[]) { ^
  38. Таким образом • У нас нет способа узнать размер массива,

    который передан в функцию в качестве параметра, если у нас на руках только переменная-массив-параметр • Что делать? Передавать в функцию не только массив, но и его размер — дополнительным параметром • Или: завести специальное значение-маркер внутри массива, размещать его в качестве последнего элемента (это далеко не всегда возможно)
  39. • В общем случае узнать размер массива, имея на руках

    только указатель на него, нельзя. • Поэтому вместе с адресом массива в функцию имеет смысл отправить его размер дополнительным параметром.
  40. #include <stdio.h> void print_array(int arr[], int size) { for (int

    i = 0; i < size; i++) { printf("arr[%d])=%d\n", i, arr[i]); } } void main() { int arr[3]; arr[0] = 13; arr[1] = 56; arr[2] = 539; print_array(arr, 3); }
  41. • Возвращать массив целиком (копию) из функции в качестве возвращаемого

    значения НЕЛЬЗЯ • Можно передать указатель на массив в качестве параметра и заполнить его нужными значениями внутри функции (передача параметра по адресу) • В качестве возвращаемого значения можно возвращать указатель на массив • (как это делать рассмотрим на следующей лекции)
  42. Задание-0 • Воспроизведите код лекции • Поэкспериментируйте с массивами и

    указателями • Попробуйте выйти за пределы массивов, посмотрите, как они будут перезаписывать друг у друга значения
  43. Задание-1 • Задание 1.1: Найти сумму элементов массива • Задание

    1.2: Найти специальную сумму элементов массива: если число четное — складываем, если нечетное — вычитаем