Н.В. Вдовикина, И.В. Машечкин, А.Н. Терехин, В.В. Тюляева - Программирование в ОС UNIX на языке Си, страница 8

Например:struct stud s={“Ivanov”,{1980,6,30},{5,3,4}};struct data ss;ss=s.d; /*ss.year=1980; ss.mon=6; ss.day=30;*/if(ss==s.d) {…} /* ошибка */Задача 1. Написать функцию, параметрами которой являются массив анкет студентов (struct stud) и их количество. Функция печатает фамилии отличников и даты рождения.void f(struct stud g[],int n){ int i;for(i=0;i<n;i++) {if(g[i].m[0]==5 && g[i].m[1]==5 && g[i].m[2]==5)printf(“%s %d.%d.%d\n”,g[i].fio,g[i].d.day,g[i].d.mon,g[i].d.year)}}Структуры со ссылками на себяСтруктуры могут содержать поля-указатели на такие жеструктуры. Это свойство структур используется при программировании динамических структур данных (стек, очередь, список, дерево), которые будут рассмотрены ниже. Структуры также могут содержать поля-указатели на еще не определенные структуры, что позволяет описывать структуры, ссылающиеся друг на друга, например:struct s1 {...struct s2 *ps2;};48struct s2 {...struct s1 *ps1;};Приведенные выше определения корректны, т.к.

выделяя память под первую структуру, компилятор может определить размерывсех ее полей, ибо размер области памяти, резервируемой под любойуказатель, всегда известен для конкретной машинной реализацииСи.Рассмотрим подробнее размещение структуры в памяти генератором кода. Здесь возникают две проблемы: собственно размещение объекта типа «структура» в памяти и размещение элементовструктуры в области памяти, выделенной под этот объект.

Адрес, скоторого размещается сама структура, называется базовым адресом,а адрес элемента структуры относительно ее базового адреса называется смещением. Заметим, что каждый тип данных транслируетсяв определенный машинный тип (например, “байт”, “слово”, “двойное слово”), которому соответствует некоторое правиловыравнивания. Рассмотрим архитектуру с байтовой адресацией иправилами размещения, согласно которым слово располагается, начиная с байта с адресом, кратным 2, а двойное слово – начиная сбайта с адресом, кратным 4. В различных реализациях языка применяются различные подходы к определению того, каким может бытьбазовый адрес структуры.

Это может быть выравнивание по типупервого элемента структуры или по максимально длинному машинному типу и т.п. Смещения элементов структуры зависят от их типов, представления их типов на конкретной архитектуре и правилвыравнивания, поэтому при выделении памяти под структуры компилятором могут оставаться «пропуски».Таким образом, важно понимать, что размер структуры не всегда равен сумме размеров ее полей.

Для определения размера памяти, занимаемого переменной структурного (как и любого другого)типа, необходимо использовать оператор sizeof().49struct {charshortshortlong}c;sn1;sn2;ln;0c642sn1sn28lnСчитаем, что под переменную типа char выделяется 1 байт, подпеременную типа short – слово (2 байта), а под переменную типаlong – двойное слово(4 байта).ОбъединенияОбъединение (union) – это тип данных, позволяющий хранитьразнородные данные (поля) в одной и той же области памяти. Синтаксис описания объединений аналогичен синтаксису описанияструктур, за исключением собственно ключевого слова – union.Фактически, объединение – это структура, все поля которой имеютнулевое смещение относительно ее базового адреса, а размер выделенной области памяти позволяет разместиться в ней самому большому полю.

При выравнивании учитывается требование для максимально длинного машинного типа, используемого для представления полей объединения, т.е. если одно поле можно разместить, начиная с адреса двойного слова, а второе – с адреса байта, то компилятор следует первому требованию.02union {charc;short sn;longln;c}snlnОбъединение можно инициализировать напрямую значением,соответствующим типу его первого поля:union cu{char c;int I;double d;} a = ‘z’;50Работа с динамической памятьюСтандартная библиотека Си содержит функции для работы сдинамической памятью.Для выделения динамической памяти служит функция:#include <stdlib.h>void * malloc(size_t size);Она выделяет блок памяти указанного (в байтах) размера ивозвращает указатель на него.

Тип size_t представляет собой одиниз базовых целочисленных типов, размера которого достаточно дляпредставления любого допустимого в данном контексте значения.Поскольку функция возвращает нетипизированный указатель,перед использованием его, как правило, необходимо привести к требуемому типу.В случае неудачи функция возвращает нулевой указатель.Для освобождения ранее выделенной динамической памятислужит функция:#include <stdlib.h>void free (void *p);Ей должен быть передан указатель на начало блока памяти,ранее выделенного с помощью malloc(). После обращения кfree() этот указатель становится недействительным.Изменить размер ранее выделенного блока памяти (как вбольшую, так и в меньшую сторону) можно при помощи функции:#include <stdlib.h>void * realloc(void *p, size_t newsize);Эта функция при необходимости может выделить новый непрерывный блок динамической памяти требуемого размера, приэтом она корректно скопирует туда содержимое старого блока и освободит старый блок памяти.

Она возвращает новый указатель наблок измененного размера или, в случае неудачи, NULL (в последнемслучае старый блок остается нетронутым). После обращения кrealloc() старый указатель становится недействительным. Важнопонимать, что обращение к realloc() может быть сопряжено сбольшими накладными расходами из-за перемещения данных.Си не содержит средств автоматической «сборки мусора», поэтому вся забота об отсутствии «утечек памяти», когда выделеннаядинамическая память должным образом не освобождается программой, лежит на совести программиста.51Задача 2.

Написать фрагмент программы, размещающий в динамической памяти вводимые из стандартного входного потока вещественные числа. Количество вводимых чисел вводится первым.... int k,i;double *p;. . .scanf(“%d”,&k);p=(double*)malloc(k*sizeof(double));for(i=0;i<k;i++) scanf(“%lf”,p+i);Задача 3. Ввести строку из стандартного входного потокадлиной не более ста символов и разместить ее в динамической памяти.... char str[100],*p;...if(gets(str)!=NULL) {p=(char*)malloc(strlen(str)+1);strcpy(p,str);Как уже говорилось, возможность описывать структуры соссылками на себя дает программисту удобное средство для реализации динамических структур данных, таких как списки, очереди, деревья и т.п.Задача 4.

Ввести строку символов из стандартного входногопотока и распечатать ее в обратном порядке, построив при этом вдинамической памяти стек.... int q;struct st { char c;struct st *s;} *p,*n;p=n=NULL;while((q=getchar())!=’\n’) {/* построение стека */n=(struct st*)malloc(sizeof(struct st));n->c=q; n->s=p;p=n;}while(n!=NULL) { /* печать строки */printf(“%c”,n->c);n=n->s;}Упражнения1. Дана строка символов. Написать функцию создания бинарногодерева (рекурсивный и нерекурсивный варианты).

Узлы дереваимеют следующую структуру:52struct tree { char c;int n;struct tree* left;struct tree* right;};где c – символ входной строки, а n – число вхождений данного символа во входную строку. При построении дерева в качестве ключаиспользовать код символа.2. Написать рекурсивную функцию подсчета количества узлов дерева.3. Написать рекурсивную функцию определения высоты дерева.4. Написать рекурсивную функцию печати узлов дерева в убывающем порядке.5.

Написать функцию печати узлов дерева по слоям (рекурсивный инерекурсивный варианты).6. Ввести набор слов. Разделители между словами: пробел, запятая,точка с запятой, конец строки. Признак конца текста - точка.Длина каждого слова не должна превышать 20 символов. Сформировать двоичное дерево, каждый узел которого содержал быуказатель на слово и число вхождений этого слова во входной поток. Ключом при построении дерева должно являться само слово.По окончании формирования дерева распечатать слова в убывающем порядке, в возрастающем порядке и по уровням.7.

Ввести набор слов. Слов не более 20-ти. Разделители между словами: пробел, запятая, конец строки. Длина слова не превышает20 символов. Разместить слова в динамической памяти (лишнегоместа не занимать) и сформировать массив указателей на слова.Использовать в качестве признака конца массива нулевой указатель NULL. Упорядочить слова в неубывающем порядке. Распечатать слова, каждое на отдельной строке.8.

Ввести набор строк. Количество строк не более 15-ти. Длина каждой строки не должна превышать 80 символов. Под каждуювведенную строку зарезервировать в динамической памяти местопод реальную ее длину, скопировать туда строку и записать адресв массив указателей. Признак конца в массиве указателей –NULL( нулевой указатель). Написать функцию, которой передается в качестве параметра массив указателей, а выходное значение – адрес самой большой (лексикографически) строки. Используя этот адрес, распечатать самую большую строку.53ТЕМА 8. Файлы.