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

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

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

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

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

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

6 Задача сортировки (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 Алгоритм сортировки выбором

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

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

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

11 Инициализация массива © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 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};

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

13 Индексы © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 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] Данное свойство дает массивам кардинальное преимущество перед простыми переменными, так как доступ к их элементам можно автоматизировать при помощи циклов

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

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

17 Обработка массивов (циклы) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 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; }

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

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

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

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

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

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

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

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

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

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