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

Рассматриваемые вопросы © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 2 1.Классификация типов данных 2.Структуры (struct) Синтаксис Примеры Инициализация Выравнивание полей Массив структур Продвинутые макросы 3.Объединения Синтаксис Примеры Инициализация Выравнивание полей 4.Определение типа 5.Перечислимый тип

Классификация типов данных © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 3 Простые типы Перечислимый тип Числовые Целочисленные Вещественные Символьный тип Логический тип Составные (сложные) типы Массив Строковый тип Запись (структура) Файловый тип Класс. Другие типы (представление информации в ЭВМ) Указатель Ссылка

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

РБНФ (структура) © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 5 Структура = "struct" [Тэг] "{" {Тип " " Идентиф{ "," Идентиф } ";"} "}" [ Объект {"," Объект } ] ";" Объект = Идентиф ["=" Значение]. Tип = БазовыйТип | Структура | Объединение | Массив | Указатель. struct { char name[64]; char lastname[64]; char patronymic[64]; unsigned char age; struct address addr; } var; struct address{ char counrty[64]; int index; char city[64]; char street[64]; int build, flat; };

Другие примеры использования (сжатие данных) © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 6 1. Алгоритмы Шеннона-Фано и Хаффмана. symbcodelen 'a'11 'b'012 … 'z' struct sfcode{ char symb; unsigned int code; unsigned char len; }; 2. Алгоритмы Лемпела-Зива (LZ77) struct lzcode{ unsigned short offs; unsigned char len; char sym; };

Массив с проверкой выхода за границы © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 7 struct safearr{ unsigned int len; int array[1024]; }; int add_elem(struct safearr *arr, int val){ int max = sizeof(arr->array)/sizeof(arr->array[0]); if( arr->len + 1 < max ){ arr->array[arr->len++] = val; return 0; } return -1; } int get_elem(struct safearr *arr, int index, int *val){ if( arr->len > index ){ *val = arr->array[index]; return 0; } return -1; } void init(struct safearr *arr){ arr->len = 0; }

Список © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» NULL head struct list { int val; struct list *next; }; Недопустимо: struct bad_struct { struct bad_struct val; }; Допустимо: struct ok_struct { struct ok_struct *ptr; }; Недопустимо: struct bad_struct { struct bad_struct val; }; Допустимо: struct ok_struct { struct ok_struct *ptr; };

Инициализация структур © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 9 1. Инициализация в порядке следования элементов struct address{ char counrty[64]; int index; char city[64]; char street[64]; int build, flat; } a = { "Russia", , "Novosibirsk", "Kirova", 86, 402 }; 2. Инициализация элементов в произвольном порядке struct address{ char counrty[64]; int index; char city[64]; char street[64]; int build, flat; } b = {.index = ,.street = "Kirova",.build = 86};

Допустимые операции © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 10 присваивание переменных-структур: a1 = a2; взятие адреса: struct array *p = &a1; обращение к элементам структуры: a1.cur = 10; a1.cur++; p->cur = 10; p->cur++; Применение операции sizeof: int s = sizeof(a1), s1 = sizeof(*p); #define N 100 struct array{ int max, cur; int mas[N]; } a1, a2 = {N,4,{1,2,3,4}};

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

Выравнивание полей структур © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 12 struct t1{ int i; short s; short s1; } a; s_a = sizeof(a); struct t1{ short s; int i; short s1; } b; s_b = sizeof(b); iss1 is

Массивы структур © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 13 присваивание переменных-структур: a[0] = a[2]; взятие адреса: struct array *p = &a[1], *p1=a+1; обращение к элементам структуры: a[1].cur = 10; a[1].cur++; (a+1)->cur = 10; (a+1)->cur++; Операция sizeof: int s = sizeof(a); #define N 100 struct array{ int max, cur; int mas[N]; } a[10];

Выравнивание массива структур © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 14 struct t1{ short s; int i; } b; s_b = sizeof(b); isisis is is

Вложенность структур © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 15 struct person{ char name[64]; char lastname[64]; char patronymic[64]; unsigned char age; struct address addr; } var; struct address{ char counrty[64]; int index; char city[64]; char street[64]; int build, flat; }; struct person var, *ptr = &var; sprintf(var.name,"Ivan"); sprintf(var.lastname,"Ivanov"); ptr->age = 25; ptr->addr.build = 86; sprintf(var.addr.city,"Novosibirsk");

Макрос offsetof © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 16 #include struct test{ int i; char j; double k; }; int main() { struct test t; printf("Offset of: i=%d, j= %d, k=%d\n", offsetof(struct test,i), offsetof(struct test,j), offsetof(struct test,k) ); printf("Offset of (Self): j= %d\n", (size_t)(&((struct test *)0)->j)); } Содержит определение макроса offsetof $./offsetof Offset of: i=0, j= 4, k=8 Offset of (Self): j= 4 $./offsetof Offset of: i=0, j= 4, k=8 Offset of (Self): j= 4

container_of (2) © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 17 #include #define container_of(ptr, type, member)\ ({ char *mptr = (char*)(ptr); \ (type *)(mptr - offsetof(type,member) ); }) iss1 member offsetof(type,member) (char*)member - offsetof(type,member)

container_of © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 18 #include #define container_of(ptr, type, member)\ ({ char *__mptr = (char*)(ptr); \ (type *)(__mptr - offsetof(type,member) ); }) struct test{ char name[256]; unsigned char age; double height,weight; }; void process(double *h) { if( *h - (int)*h > 0 ){ struct test *p; printf("Height is not integer. Fix it.\n"); *h = (int)*h; p = container_of(h,struct test, height); printf("New info:\n\tname = %s\n\tage = %d" "\n\theight = %f\n\tweight = %f\n", p->name, p->age, p->height, p->weight); } struct test t[] = { {"Ivan", 20, 180.1, 81 },... }; process(&t[0].height); Height is not integer. Fix it. New info: name = Ivan age = struct test t[] = { {"Ivan", 20, 180.1, 81 },... }; process(&t[0].height); Height is not integer. Fix it. New info: name = Ivan age = 20...

container_of (3) © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 19 int main() { struct test t[] = { {"Ivan", 20, 180.1, 81 }, {"Alex", 21, 190, 85 }, {.name="Jack",.height=175.6,.age=22} }; int i; for(i=0; i

Объеднения © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 20 Объединение - это переменная, которая в различные моменты времени может содержать объекты разных типов и размеров. Объединения предоставляют возможность работать с различными видами данных в одной области памяти, не вводя в программу никакой машинно-зависимой информации. Ячейка памяти Ячейка памяти

© Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 21 Объединение = "union" [Тэг] "{" {Тип," ",Объект {"," Объект}";"} "}" [ Объект {"," Объект } ]; Объект = Идентификатор ["=" Значение]. Tип = БазовыйТип | Структура | Объединение | Массив | Указатель. union ip{ int val; char ar[4]; struct bytes{ unsigned char b1,b2,b3,b4; };

Государственные номерные знаки © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 22 Ячейка памяти Ячейка памяти

Структуры описания номерных знаков © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 23 struct usual{ char c1; short num; char c2[2]; short region; }; struct trailers{ char c1[2]; short num; short region; };

Структуры описания номерных знаков (2) © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 24 struct passengers{ char c1[2]; short num; short region; }; struct police{ char c1; short num; short region; }; struct military{ short num; char c1[2]; short region; };

Описание типа данного номерной знак © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 25 union reg_plate{ struct usual u; struct trailer t; struct passengers p; struct police p; struct military m; } plate; В результате будет определена область памяти, способная вместить любую из перечисленных переменных с учетом требований выравнивания. При обращении к данной ячейке через одно из полей она будет рассматриваться как ячейка, тип данного которой соответствует этому полю. Например: plate.u – структура обычного номера, plate.t – номер прицепов.

Инициализация объединений © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Инициализация выбранного элемента объединения union reg_plate{ struct usual u; struct trailer t; struct passengers p; struct police p; struct military m; } plate = {.u = {'н', 001, "нн", 54 } }; struct usual{ char c1; short num; char c2[2]; short region; };

Выравнивание объединений © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 27 Основываясь на правилах выравнивания структур, сформулируйте правила выравнивания объединений.

Определение типа (typedef) © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 28 typedef unsigned int uint; uint x, y, z; typedef struct police police_t; police_t plate; В языке Cи предусмотрен оператор typedef, предназначенный для введения новых имен типов данных. РБНФ оператора typedef: Например: ОпределениеТипа = "typedef" Тип НовоеИмя {"," НовоеИмя} ";". Tип = БазовыйТип | Структура | Объединение | Массив | Указатель.

Определение типа (typedef) (2) © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 29 Оператор typedef не создает нового типа, он позволяет определить синоним (alias) для одного из существующих типов данных. typedef struct mystruct { int i; char j; float z; } mystruct1; Определение типа данных "struct mystruct" а также его синонима mystruct1 Определение типа данных "struct mystruct" а также его синонима mystruct1

Перечислимый тип (enum) © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 30 Перечисляемый тип (сокращённо перечисление, англ. enumeration, enumerated type) в программировании тип данных, чьё множество значений представляет собой ограниченный список идентификаторов. РБНФ перечислимого типа: ОпределениеТипа = "enum" [Тег] "{" Идентиф [= Значение] {"," Идентиф [= Значение]} "}" {"," Идентиф } ";". Значение = Целочисленное значение. enum { blue, red, green } x; enum device { PC, smartphone, cellphone, router}; Например:

Литература 31 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 1.Подбельский В.В, Фомин С.С. Программирование на языке Си: Учеб. пособие. - 2-е доп. изд. - М.: Финансы и статистика, с. 2.Керниган Б., Ритчи Д., Фьюер А. Язык программирования Си. Задачи по языку Си: Пер. с англ. - М.: Финанасы и статистика,