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

Задача сортировки (sorting problem) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 2 Дано: последовательность из 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 Пример: Входная последовательность:5, 3, 8, 9, 4 Выходная последовательность:3, 4, 5, 8, 9 Входные данные (последовательность), удовлетворяющие всем заданным ограничениям задачи, называется экземпляром задачи.

Проход 2. Второй по величине элемент занимает n–1 место Сортировка методом пузырька (пример) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» Проход 1. Наибольший элемент занимает n-е место Проход 3. Третий по величине элемент занимает n–2 место Проход 4. Третий по величине элемент занимает n–3 место

Сортировка методом пузырька (псевдокод) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 4 Входные данные: последовательность a из n элементов ввод a i 1 while i n do j 1 while j (n–i) do // На i-й итерации i правых эл-тов отсортированы if a j > a j+1 then t a j a j a j+1 a j+1 t j j + 1 i i + 1

Правила оформления псевдокода © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 5 1.Циклические конструкции обозначаются английскими словами (аналогично языку программирования СИ): while, do-while, for. 2.Конструкция ветвления обозначается ключевыми словами if-then-else. 3.Структура блоков указывается с помощью отступов. 4.Для описания комментариев используется '//' 5.Присваивание обозначается как '': x y для отличи от сравнения (обозначается как "=").

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

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

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

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

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

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

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

Обработка массива © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 13 К массиву как единому целому может быть применена только операция индексации [ ] и оператор sizeof. Любые другие действия требуют поэлементной обработки! Например, не предусмотрено операции присваивания массивов. Для достижения желаемого эффекта необходимо поэлементно присвоить каждому элементу изменяемого массива значение соответствующего элемента исходного: int mas1[10] = {...}, mas2[10], i; for(i=0;i

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

Перебор индексов массива © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 15 В задачах, рассмотренных выше, обработка массива сводилась к последовательному перебору его индексов и обработке соответствующего элемента согласно условиям задачи. В связи с тем, что индексация массивов начинается с 0, в условии продолжения цикла используют строгое неравенство:... for(i = 0; i < 10; i++) {... }... i: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

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

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

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

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

Применение GDB © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 20 (gdb) b main (gdb) r... (gdb) watch a[0] Hardware watchpoint 5: a[0] (gdb) c Continuing. Hardware watchpoint 5: a[0] Old value = New value = 25 main () at array_borders.c:6 5 for(i=0;i

Многомерные массивы © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 21 в языке СИ определены только одномерные массивы; элементом массива в свою очередь может быть массив. Правила 1 и 2 позволяют определять многомерные массивы следующим образом: int m1[2][5], m2[4][10][10]; float m3[9][9][9][9]; Для обращения к элементу массива необходимо зафиксировать индекс каждого измерения, например: m1[1][3] = 8; m1[1][5] = 10; m[2][4] = 1; m3[5][4][2][6] = 1.6;

Логическое и физическое размещение многомерных массивов © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 22 [0][0][0][0][0][1][0][1][0][2][0][2][1][0][1][0][1][1][1][1][1][2][1][2][2][0][2][0][2][1][2][1][2][2][2][2] Физическое расположение элементов массива в памяти Логическое расположение элементов массива в памяти N[0][0]N[0][0]N[0][1]N[0][1]N[0][2]N[0][2] N[1][0]N[1][0]N[1][1]N[1][1]N[1][2]N[1][2] N[2][0]N[2][0]N[2][1]N[2][1]N[2][2]N[2][2] Строки 0 12 Столбцы

Адресация двумерных массивов © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 23 Физическое расположение элементов массива в памяти int A[3][3]; Задача определения смещения элемента в физическом представлении: Дано: индексы (i, j) элемента двумерного массива A[N][M]. Найти: функцию смещения t(i, j) элемента A[i][j] в физическом представлении A относительно первого элемента A[0][0]. Решение: t(i, j) = i·M + j [0][0][0][0][0][1][0][1][0][2][0][2][1][0][1][0][1][1][1][1][1][2][1][2][2][0][2][0][2][1][2][1][2][2][2][2]

Адресация трехмерных массивов © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 24 Физическое расположение элементов массива в памяти int A[3][3][3]; Задача определения смещения элемента в физическом представлении: Дано: индексы (i, j, k) элемента массива A[N][M][K]. Найти: функцию смещения t(i, j, k) элемента A[i][j][k] в физическом представлении A относительно первого элемента A[0][0][0]. Решение: ? ?

Адресация трехмерных массивов © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 25 Физическое расположение элементов массива в памяти int A[3][3][3]; Задача определения смещения элемента в физическом представлении: Дано: индексы (i, j, k) элемента массива A[N][M][K]. Найти: функцию смещения t(i, j, k) элемента A[i][j][k] в физическом представлении A относительно первого элемента A[0][0][0]. Решение: t(i, j, k) = i·M·K + j·K + k

Обработка двумерного массива © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 26 Элемент двумерного массива описывается двумя индексами. Обработка массива предусматривает просмотр/изменение каждого элемента. Последовательность обработки элементов определяется задачей. Для перебора индексов массива обычно используют вложенные циклы, каждый цикл отвечает за изменение своего индекса. N[0][0]N[0][0]N[0][1]N[0][1]N[0][2]N[0][2] N[1][0]N[1][0]N[1][1]N[1][1]N[1][2]N[1][2] N[2][0]N[2][0]N[2][1]N[2][1]N[2][2]N[2][2] Строки 0 12 Столбцы

Построчный просмотр элементов © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 27 int a[5][5] = {{1},{4},{2},{3},{8}}; int i, j; for(i = 0; i < 5; i++){ for(j = 0; j < 5; j++) printf("%d ", a[i][j]); }

Просмотр элементов по столбцам © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 28 int a[5][5] = {{1},{4},{2},{3},{8}}; int i, j; for(j = 0; j < 5; j++){ for(i = 0; i < 5; i++) printf("%d ", a[i][j]); }

Произведение матриц © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 29

Порядок обработки элементов © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 30 i=0i= j= j= j= j= j= j= j= j= j=2 i=1i=1 i=2 AB

Программа вычисления c ij © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 31 k 0 c ij 0 while k < n do c ij = c ij + a ikb kj k k + 1

Программа вычисления строки c i = (c i1, c i2, c i3, … c in ) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 32 i j= j= j=2 j 0 while j < n do k 0 c ij 0 while k < n do c ij = c ij + a ikb kj k k + 1 j j + 1

Программа вычисления всей матрицы С © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 33 i 0 while i < n do j 0 while j < n do k 0 c ij 0 while k < n do c ij = c ij + a ikb kj k k + 1 j j + 1 i i + 1

Инициализация двумерных массивов © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 34 Для инициализации статических многомерных массивов необходимо инициализировать каждый вложенный массив, являющийся элементом внешнего: int a[2][3] = { {1, 2, 3}, {4, 5, 6} }; Строки 0 12 Столбцы

Инициализация двумерных массивов (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 35 Если задано меньше элементов, чем длина массива остальные элементы заполняются нулями: int a[2][3] = { {1}, {2} }; int b[3][3]={ {1}, {2} }, c[2][3]={ 0 };

Сечение многомерных массивов © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 36 b[n 1 ][n 2 ][n 3 ]...[n k ] Фиксация (обязательно слева направо) l первых индексов массива b приведет к формированию сечения массива. Сечение массива представляет собой массив b' меньшей (по сравнению с b) размерности, элементы которого образуются по следующему правилу: b'[i 1 ][i 2 ]…[i (k-l) ] = b[c 1 ][c 2 ]…[c l ] [i 1 ][i 2 ]…[i (k-l) ], где c 1, … c l – зафиксированные индексы, а i 1, i 2, …i (k-l) – свободные индексы. Обращение к элементу – частный случай сечения

Сечение двумерных массивов © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» int b[3][3]={ {1,2,3},{4,5,6},{7,8,9} } 123 b[0] 456 b[1] 789 b[2]

Расположение двумерных массивов в памяти программы © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 38 Физическое расположение элементов массива в памяти int A[3][3]; Задача определения смещения элемента в физическом представлении: Дано: индексы (i, j) элемента двумерного массива A[N][M]. Найти: функцию смещения t(i, j) элемента A[i][j] в физическом представлении A относительно первого элемента A[0][0]. Решение: t(i, j) = i·M + j [0][0][0][0][0][1][0][1][0][2][0][2][1][0][1][0][1][1][1][1][1][2][1][2][2][0][2][0][2][1][2][1][2][2][2][2]

Сечение трехмерных массивов © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 39 int b[3][3][3]; b[1]

Оператор sizeof © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 40 // z y x int a[5][5][5]; int size, xysize, xsize, elemsize; int cnt, xcnt, ycnt, zcnt; size = sizeof(a); xysize = sizeof(a[0]); xsize = sizeof(a[0][0]); elemsize = sizeof(a[0][0][0])); cnt = sizeof(a)/sizeof(a[0][0][0]); zcnt = sizeof(a)/sizeof(a[0]); ycnt = sizeof(a[0])/sizeof(a[0][0]); xcnt = sizeof(a[0][0])/sizeof(a[0][0][0]);

41 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» СПАСИБО ЗА ВНИМАНИЕ!