Преподаватель: Доцент Кафедры ВС, к.т.н. Поляков Артем Юрьевич © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» ФГОБУ ВПО "СибГУТИ" Кафедра вычислительных систем Дисциплины "ЯЗЫКИ ПРОГРАММИРОВАНИЯ" "ПРОГРАММИРОВАНИЕ" Массивы

Численное вычисление e x (аккумуляция результата) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 2

Численное вычисление e x (аккумуляция результата) (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» ,333 +1,333 6,999 +0,666 7,265 +0,266 7,353 +0,088 На вход поступает небольшой объем данных, все остальное вычисляется на их основе

Поиск максимального элемента ("потоковая" обработка данных) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Данные, как поток "протекают" через сито (программу ), которое задерживает нужную информацию Для реализации алгоритмов, использующих такой подход требуется ограниченный набор переменных

Вычисление суммы входных чисел ("потоковая" обработка + аккумуляция результата) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Для ее обработки достаточно однократно учесть вклад каждого элемента в общую сумму На вход подается последовательность, размер которой не известен на этапе создания программы!

Задача сортировки (sorting problem) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 6 Дано: последовательность из n чисел a 1, a 2, a 3, …, a n Необходимо: переставить элементы последовательности так, чтобы для любых элементов новой последовательности a' 1, a' 2, a' 3, …, a' n выполнялось соотношение: a' 1 a' 2 a' 3 … a' n Алгоритм сортировки выбором

Операции над векторами (vector operations) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 7 Вектором а n-мерного пространства называется кортеж из n элементов a = (a 1, a 2, a 3, …, a n ), описывающих координаты конечной точки вектора, считая, что его начало расположено в точке (0, 0, 0, …, 0). Для векторов определены: 1) операция сложения a + b: a + b = (a 1, a 2, a 3, …, a n ) + (b 1, b 2, b 3, …, b n ) = ( a 1 + b 1, a 2 + b 2, a 3 + b 3, …, a n + b n ) 2) операция умножения на скаляр: c a = c (a 1, a 2, a 3, …, a n ) = (c a 1, c a 2, c a 3, …, c a n ) 3) скалярное произведение (a, b) векторов: (a, b) = a 1 b 1 + a 2 b 2 + a 3 b 3 + … + a n b n В результате выполнения любой из операций формируется кортеж из n переменных Необходима возможность обрабатывать элементы в цикле

Требования к типу данных для хранения последовательностей и векторов © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 8 1.Хранение заданного количества n однотипных элементов под одним именем. 2.Механизм доступа к отдельным элементам, допускающий возможность автоматизации с применением циклических конструкций. Массив Элементарный тип Элементарный тип

Массив данных © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 9 Массивы данных в языках программирования высокого уровня – это сложные типы данных, предназначенные для хранения наборов однотипных данных в памяти программы. Доступ к конкретному элементу производится с использованием его целочисленного индекса. Индексы задают порядок следования элементов в массиве, поэтому его можно рассматривать как упорядоченное множество. Технически это последовательность однотипных переменных. В памяти элементы массива располагаются друг за другом непрерывно. Для каждого элемента i справедливо, что в памяти между ним и элементами с индексами (i – 1) и (i + 1) (если они существуют) не может находиться никаких ячеек данных.

Объявление массива © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 10 При объявлении массива компилятору необходимо предоставить следующую информацию: 1.Элементарный тип – тип данного элементов, составляющих массив. 2.Имя массива. 3.Количество элементов в массиве. 4.[Необязательно] начальное содержимое массива (инициализация). Пример – массив с именем m из N элементов типа int: int m[N];

Инициализация массива © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 11 При объявлении массива компилятору необходимо предоставить следующую информацию: 1.Элементарный тип – тип данного элементов, составляющих массив. 2.Имя массива. 3.Количество элементов в массиве (может отсутствовать, если массив инициализирован). 4.Начальное содержимое массива (инициализация). Например: массив с именем mas из 5 элементов типа float, со значениями 1.1, 2.0, 3.5, 6.7, 8.1 объявляется так: int mas[5] = {1.1, 2.0, 3.5, 6.7, 8.1}; или int mas[] = {1.1, 2.0, 3.5, 6.7, 8.1};

Операция индексации (array subscripting) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 12 Основная часть операций над массивом производится поэлементно. Доступ к конкретному элементу производится с использованием операции индексации – [ ]: [ ]. Например, для массива: доступ к элементу со значением 3.5, расположенному на 3-ей позиции в массиве осуществляется следующим образом: x = mas[2]; Индексация элементов в языке СИ начинается с НУЛЯ! float mas[] = { }

Индексы © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 13 Важным достоинством операции индексации является то, что в качестве ее аргумента помимо констант: int a[10] a[0], a[1], a[2], a[3], a[4], …, можно использовать также выражения: i =0, j = 5, k = 2 a[i], a[j + k], a[i++], a[j – k] Данное свойство дает массивам кардинальное преимущество перед простыми переменными, так как доступ к их элементам можно автоматизировать при помощи циклов

Индексы (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 14 В качестве индекса может использоваться любое выражение, целого типа: char, short, int, long. Индексы элементов массива языка СИ начинаются с 0. Индексы могут быть: положительными, тогда обращение производится к ячейке, располагающейся после первой. отрицательными, тогда обращение производится к ячейке, располагающейся перед первой....a[-2]a[-1]a[0]a[1]a[2]...

Принцип работы операции индексации © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» int a[] = {2, 4, 8, 16, 32} Память программы a = 0xA000 Имя массива – указатель константа на первый элемент массива. В примере на рисунке адрес первой ячейки со значением "2" – 0xA000 (0x – признак шестнадцатеричной константы). Зная адрес addr(a) первого элемента, размер элементов и учитывая свойство непрерывного расположения элементов массива, можно определить адрес любого элемента по формуле: addr(a[i]) = addr(a) + i sizeof(TYPE) sizeof(TYPE)

Обработка массивов © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 16 К массиву как единому целому может быть применена только операция индексации [ ] и оператор sizeof. Любые другие действия требуют поэлементной обработки! Например: ввод-вывод массива; присваивание массивов; сложение массивов по правилу векторов; поиск минимального/максимального элемента; сортировка массива; т.д.

Обработка массивов (циклы) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 17 i < N ДА НЕТ i = 0 i = i + 1 a[i]a[i] a[i]a[i] Большинство операций над массивами осуществляются поэлементно. Такой тип обработки предусматривает перебор всех допустимых индексов массива и применение однотипной операции к каждому элементу. Данная операция наиболее эффективно реализуется с применением циклов: int a[10] = {1, 2, 3, 4, 5, 6}; int i = 0; while( i < 6 ){ обработать a[i]; i = i + 1; }

Цикл for © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 18 "for" "(" [Выр1] ";" [Выр2] ";" [Выр3] ")" Оператор. Выр1 – выражение-инициализация. Выполняется один раз перед циклом. Выр2 – логическое выражение. Условие продолжения цикла (аналогично циклу while). Выр3 – выражение-последействие. Выполняется после каждой итерации. Оператор выполняется до тех пор, пока Выр2 является ИСТИННЫМ. Выр2 ДА НЕТ Выр1 Выр3 Оператор

Ввод-вывод массивов © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 19 В функции scanf не предусмотрено спецификатора для ввода или вывода массива как единого целого. Это сделано из соображений универсальности и сохранения относительной простоты использования данной функции. Ввод-вывод массивов осуществляется поэлементно. Пример ввода: int mas[10], i; for(i=0;i

Присваивание массивов © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 20 Для того, чтобы присвоить одному массиву значение другого необходимо, чтобы были выполнены следующие условия: 1.Совместимость типов данных элементов (как и для переменных). 2.Совместимость по размеру (массив- приемник должен быть не меньше массива- источника). int a[10], b[10], i;... // ввод a for(i=0;i

Сложение массивов по правилу векторов © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 21 Для выполнения операции сложения двух массивов требуется выполнение следующих условий: 1.Совместимость типов данных элементов (как и для переменных). 2.Эквивалентность по размеру (массив- приемник и массивы-источники должны иметь одинаковый размер). int a[10], b[10], c[10], i;... // ввод a и b for(i=0;i

Поиск минимального элемента в последовательности © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 22 i N ДА НЕТ i = 2 N, min a a min Начало Конец a < min ДА min = a i = i + 1

Поиск минимального элемента © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 23 Алгоритм поиска минимального элемента в массиве аналогичен рассмотренному ранее "потоковому" алгоритму поиска минимального элемента последовательноси. Важным отличием является то, что в массиве основной интерес представляет индекс искомого элемента, а не его значение. Информация о расположении элемента в массиве позволяет определить его значение, но не наоборот! input n, a imin 0 for i 1 to n do if a[imin] > a[i] then imin i output imin, a[imin]

Особенности инициализации массива © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 24 Статические массивы можно объявлять с инициализацией, перечисляя значения их элементов в {} через запятую. Если задано меньше элементов, чем длина массива остальные элементы считаются нулями: int a[10] = { 1, 2, 3, 4 }; /* и 6 нулей */ Если при описании массива с инициализацией не указать его размер, он будет подсчитан компилятором: int b[] = { 1, 2, 3 };

Особенности реализации массивов в языке СИ © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 25 «Си инструмент, острый, как бритва: с его помощью можно создать и элегантную программу, и кровавое месиво», Б. Керниган. В связи со сравнительно низким уровнем языка многие случаи неправильного использования опасных элементов не обнаруживаются и не могут быть обнаружены ни при компиляции, ни во время исполнения. В Си не предусмотрено средств проверки индексов массивов (проверки выхода за границы массива). Например, возможна запись в шестой элемент массива из пяти элементов, что, естественно, приведёт к непредсказуемым результатам.

Демонстрация выхода за границы массива © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 26 #include int main() { int i, a[4] = {1,2,3,4}, b[] = {5,6,7,8}; for(i=0;i

Выход за границы массива © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 27 int i, a[4] = {1,2,3,4}, b[4] = {5,6,7,8}; for(i=0; i