презентация по си. Презентация - лекция 3. Лекция 3 Структуры данных. Массивы. Многомерные массивы
 Скачать 0.86 Mb.
|
|
Лекция 3 Структуры данных. Массивы. Многомерные массивы. Структуры Динамические и статические структуры данных Структура данных – это множество элементов данных и множество связей между ними. Она поддерживает определенный порядок доступа к данным. Два основных типа структур данных – динамические, размер которых при исполнении программы может изменяться, и статические, т.е., структуры, размер которых остаётся неизменным с момента начала выполнения вычислений до их завершения. Динамические структуры данных Динамические структуры: связанные списки, стеки, очереди и двоичные деревья. Связанный список Стек Очередь Бинарное дерево Элемент 2 Элемент 3 Элемент 1 Элемент 4 Вставка Удаление Вставка Удаление Вставка Удаление Элемент 2 Элемент 3 Элемент 1 Элемент 4 Вставка Удаление Элемент 2 Элемент 3 Элемент 1 Элемент 4 Вставка Удаление Элемент 3 Элемент 1 Элемент 7 Элемент 2 Элемент 5 Элемент 6 Элемент 4 Статические структуры данных: массивы Массив представляет собой группу ячеек памяти, логически связанных в том отношении, что все они имеют одно и то же имя и один и тот же тип. При написании программного кода устанавливается тип каждого элемента и число элементов, требуемых для каждого массива. Чтобы зарезервировать память для 12 элементов для целочисленного массива с именем c, необходимо написать: int c[12]; При помощи одного объявления можно зарезервировать память для нескольких массивов: int b[100], x[72]; 467 1475 14 765 379 25 6528 147 957 27586 8 45 Статические структуры данных: массивы Элементы массива также можно инициализировать при объявлении массива: 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]. c[0] c[1] c[2] c[3] c[4] c[5] c[6] c[7] c[8] c[9] c[10] Индекс элемента массива обязательно должен быть неотрицательным целым числом или целочисленным выражением. Так, если значение переменной a равно 5, а значение переменной b равно 6, то оператор c[a+b] += 2 прибавляет 2 к элементу массива c[11]. 435 6279 27 -682 728 953 -140 12 289 5 3587 Статические структуры данных: массивы Символьные массивы в языке C, как правило, используются для хранения строк. Любой символьный массив может быть инициализирован строковым литералом: char string1[] = “first”; Размер массива string1 в объявлении определяется компилятором исходя из длины строки. Данная строка содержит пять символов и специальный символ окончания строки ‘\0’, называемый нулевым символом. Статические структуры данных: массивы Другой способ объявления и инициализации символьного массива: 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; } Статические структуры данных: массивы Массивы в C могут иметь несколько индексов. Многомерные массивы часто применяются, например, для представления таблиц. Здесь пригодны для применения массивы с двумя индексами: первый идентифицирует строку элемента, а второй ‒ столбец. Приведём пример описания таблицы с помощью двумерного массива a[3][4]. Столбец 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 элементов. Статические структуры данных: массивы Когда функция принимает в качестве параметра одномерный массив, в списке параметров функции скобки, относящиеся к массиву, остаются незаполненными. Если передаётся многомерный массив, то первый индекс также не указывается, однако все последующие индексы необходимы. Для передачи массива в качестве аргумента функции необходимо в любом случае указать его имя без скобок. Статические структуры данных: массивы #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]); } } } Пример передачи массива в качестве параметра/аргумента в функцию printArray, печатающей значения некоторого двумерного массива: Статические структуры данных: структуры Структура – это набор логически связанных переменных, объединённых под одним именем. В отличие от массивов, структуры могут состоять из переменных различных типов данных. Они помогают в организации сложных данных. Объявление структуры начинается со слова struct и содержит список объявлений в фигурных скобках. За словом struct может следовать имя (тег) структуры. Пример: 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 pt1; }; Если объявить новую переменную как 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, в теле которой вызывается функция makepoint. 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; } Здесь оба параметра и возвращаемые значения – структуры. |