Структуры данных. Массивы. Многомерные массивы. Структуры

Лекция 3 Структуры данных. Массивы. Многомерные массивы. Структуры Динамические и статические структуры данных Структура данных – это множество элементов данных и множество связей между ними. Она поддерживает определенный порядок доступа к данным. Можно выделить два основных типа структур данных – динамические, размер которых при исполнении программы может изменяться, и статические, т.е., структуры, размер которых остаётся неизменным с момента начала выполнения вычислений до их завершения. К динамическим структурам относятся связанные списки, стеки, очереди и двоичные деревья. Связанный список – это набор «выстроенных в ряд» элементов данных, в любом месте которого можно выполнять вставки и удаления элементов. Стеки допускают выполнение вставки и удаления только с одного конца стека – сверху. В очереди вставки производятся в конец (хвост) структуры, а удаление – в начале (голове) очереди. Двоичные деревья облегчают скоростной поиск и сортировку данных, представление файловой структуры каталогов. К статическим структурам данных, чаще всего используемым в языке C, относятся массивы и структуры. Массивы и их инциализация. Символьные массивы Массив представляет собой группу ячеек памяти, логически связанных в том отношении, что все они имеют одно и то же имя и один и тот же тип. При написании программного кода устанавливается тип каждого элемента и число элементов, требуемых для каждого массива. Чтобы зарезервировать память для 12 элементов для целочисленного массива с именем c, необходимо написать: int c[12]; При помощи одного объявления можно зарезервировать память для нескольких массивов: int b[100], x[72]; Элементы массива также можно инициализировать при объявлении массива: int n[10] = {32, 27, 64, 18, 95, 14, 90, 70, 60, 37}; Посредством объявления int n[10] = {0}; инициализируют все элементы массива n нулями. Если размер массива не указывается в квадратных скобках при его объявлении и инициализации, то число элементов в массиве будет равно числу элементов в списке инициализации. Например, строка кода int n[] = {1, 2, 3, 4, 5}; говорит о создании массива из пяти элементов. Первый элемент в любом массиве имеет нулевой порядковый номер. Для обращения к конкретной области или элементу массива указывают имя массива и номер позиции этого элемента в массиве. Таким образом, первый элемент массива c обозначают как c[0], второй как c[1], седьмой как c[6] и, в общем случае, i-й элемент как c[i-1]. Номер позиции элемента, содержащийся внутри квадратных скобок, называется индексом. Индекс обязательно должен быть неотрицательным целым числом или целочисленным выражением. Так, если значение переменной a равно 5, а значение переменной b равно 6, то оператор c[a+b] += 2 прибавляет 2 к элементу массива c[11]. Символьные массивы в языке C, как правило, используются для хранения строк. Любой символьный массив может быть инициализирован строковым литералом, например, таким образом: char string1[] = “first”; Размер массива string1 в данном объявлении определяется компилятором исходя из длины строки. Здесь необходимо оговориться: строка “first” содержит пять символов и специальный символ окончания строки ‘\0’, называемый нулевым символом. Все строки в языке C заканчиваются этим символом. Таким образом, массив string в данном примере содержит шесть символов. Другой способ объявления и инициализации символьного массива: char string1[] = {‘f’, ‘i’, ‘r’, ‘s’, ‘t’, ‘\0’}; К символам строки можно обращаться точно так же, как и в любом массиве: в рассмотренном примере string1[0] – это символ ‘f’, а string1[3] – символ ‘s’. Строками в языке C могут быть и символьные массивы строго заданного размера. Инструкция char string2[20]; создаёт массив, в котором может храниться строка из 19 символов и завершающего нулевого символа. Строка может быть введена пользователем с клавиатуры и считана в символьный массив с помощью функции scanf. Сортировка массивов Сортировка данных (т.е., их расположение в некотором специальном порядке) является одной из важнейших задач в программировании. Широко распространена так называемая пузырьковая сортировка данных в массиве, в процессе которой меньшие значение, подобно пузырькам в воде, постепенно «всплывают» в верхнюю часть массива. Метод требует нескольких проходов по массиву. На каждом проходе сравниваются последовательные пары элементов. Если элементы расположены в убывающем порядке, их значения в массиве меняются местами, а если в возрастающем порядке, то ничего не изменяется. Пример: #include int main() { int a[10] = {2, 6, 4, 8, 10, 12, 89, 68, 45, 37}; int i, pass, hold; for (pass = 1; pass <= 9; pass++) // проходы { for (i = 0; i <= 8; i++) // один проход { if (a[i] > a[i+1]) // одно сравнение { hold = a[i]; // одна перестановка a[i] = a[i+1]; a[i+1] = hold; } } } printf(“Array: ”); for (i = 0; i <= 9; i++) { printf(“%d”, a[i]); } return 0; } За первый проход самое большое значение гарантированно «опускается» в нижний элемент массива a[9]. За второй проход второе по величине значение гарантированно «опускается» в a[8]. Очевидно, после девятого прохода девятое по величине значение окажется в a[1]. Следовательно, самое маленькое значение остаётся в a[0], поэтому для сортировки массива из десяти элементов достаточно сделать только девять проходов. Многомерные массивы. Передача массива функции в качестве параметра/аргумента Массивы в C могут иметь несколько индексов. Многомерные массивы часто применяются, например, для представления таблиц. Здесь пригодны для применения двумерные массивы, т. е., массивы с двумя индексами: первый идентифицирует строку элемента, а второй, в свою очередь, идентифицирует столбец. Приведём пример описания таблицы с помощью двумерного массива a[3][4]. Каждый элемент массива a идентифицируется как a[i][j]. Столбец 0 Столбец 1 Столбец 2 Столбец 3 Строка 0 Строка 1 Строка 2 Двумерный массив, так же как и одномерный, можно инициализировать при объявлении: int b[2][2] = {{1, 2}, {3, 4}}; Аналогичным образом можно работать с трёх-, четырёх- и вообще n-мерными массивами. Так, трёхмерный массив можно себе представить как массив из нескольких страниц, каждая из которых содержит двумерную таблицу. Инструкция int arr[10][20][30]; объявляет трёхмерный массив arr, который по сути является массивом из 10 массивов. Все они содержат по 20 элементов-массивов, каждый из которых, в свою очередь, включает 30 элементов. Когда функция принимает в качестве параметра одномерный массив, в списке параметров функции скобки, относящиеся к массиву, остаются незаполненными. Если передаётся многомерный массив, то первый индекс также не указывается, однако все последующие индексы необходимы. Для передачи массива в качестве аргумента функции необходимо в любом случае указать его имя без скобок. Приведём пример для функции printArray, печатающей значения некоторого двумерного массива: #include void printArray (int [][3]); int main() { int array1 [2][3] = {{1, 2, 3}, {4, 5, 6}}; printf(“Array members: ”); printArray(array1); return 0; } void printArray(int a[][3]) { int i, j; for (i = 0; i <= 1; i++) { for (j = 0; j <= 2; j++) { printf (“%d”, a[i][j]); } } } Структуры Структура – это набор логически связанных переменных, объединённых под одним именем. В отличие от массивов, содержащих элементы только одного типа, структуры могут состоять из переменных различных типов данных. Они помогают в организации сложных данных, поскольку позволяют группу связанных между собой переменных трактовать как единое целое. Объявление структуры начинается со слова struct и содержит список объявлений в фигурных скобках. За словом struct может следовать имя (или тег) структуры. Пусть структура описывает точку с координатами x и y, тогда её можно объявить следующим образом: struct point { int x; int y; }; Перечисленные в структуре переменные называются её элементами. Объявление структуры определяет тип. После закрывающей фигурной скобки могут следовать имена объявленные переменные нового типа: struct a {…} x, y, z; или, как в рассматриваемом примере, можно объявить переменную отдельной строкой: struct point pt; Структурную переменную можно инициализировать: struct point maxpt = {320, 200}; Доступ к отдельному элементу структуры осуществляется при помощи оператора . (точки) Если нужно вывести на экран координаты точки pt, можно написать printf(“%d, %d”, pt.x, pt.y); Структуры могут быть вложены друг в друга. Одно из возможных представлений прямоугольника – пара точек на углах его диагоналей: struct rect{ struct point pt1; struct point pt2; }; Если объявить новую переменную как struct rect screen; то инструкция screen.pt1.x; обращается к координате x точки pt1 из screen. Единственные возможные операции над структурами – это осуществление доступа к их элементам, копирование и присваивание (помимо прочего, они подразумевают передачу функциям аргументов и возврат ими значений), а также взятие адреса с помощью &. Структуры в языке C нельзя сравнивать. Пусть, например, функция makepoint получает два значения и возвращает структуру point: struct point makepoint(int x, int y) { struct point temp; temp.x = x; temp.у = у; return temp; } Конфликта между именем аргумента и именем элемента структуры не возникает. В теле функции main можно написать следующее: int main () { struct rect screen; struct point middle; screen.pt1 = makepoint(0, 0); screen.pt2 = makepoint(1600, 1200); middle = makepoint((screen.pt1.x + screen. pt2.x)/2, (screen.pt1.y + screen.pt2.y)/2); } В качестве ещё одного примера приведём функцию, выполняющую операции над точками: struct point addpoint(struct point p1, struct point p2) { p1.x += p2.x; p1.y += p2.y; return p1; } Здесь оба параметра и возвращаемые значения – структуры.