Например, используя typedef при декларации структуры, задается её новое имя:

typedef struct point { int x; int y; } sp;

Теперь тип sp – это синоним типа struct point, и следующие определения переменной z эквивалентны:

struct point z;

sp z;

Структуры могут быть проинициализированы списком константных значений:

struct point k={3,5};

Доступ к полям структуры осуществляется с помощью операции «точка»: c.x, c.y, если же определен указатель на структуру, то используется операция ->. Например:

p=&c;

p->x=2; /* (*p).x - эквивалентно */

Структуры могут быть вложенными:

struct stud {

char fio[15];/* фамилия студента*/

struct data { int year;

int mon;

int day;

} d; /* дата рождения */

int m[3]; /* оценки в сессию */

};

При такой вложенной декларации структур, тип struct stud и struct data имеют одинаковую область действия.

В Си разрешается присваивать и копировать структуры, что позволяет передавать их в функцию в качестве аргумента и передавать из функции в качестве возвращаемого значения, но структуры нельзя сравнивать. Например:

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;

};

struct s2 {

...

struct s1 *ps1;

};

Приведенные выше определения корректны, т.к. размер области памяти, резервируемой под любой указатель, всегда известен для конкретной машинной реализации Си.

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

Объединение (union) – это тип данных, позволяющий хранить разнородные данные (поля) в одной и той же области памяти. Синтаксис объединений аналогичен синтаксису структур. Фактически, объединение – это структура, все поля которой имеют нулевое смещение относительно ее базового адреса, а размер выделенной области памяти позволяет разместиться в ней самому большому полю. При выравнивании учитывается требование для максимально длинного машинного типа, используемого для представления полей объединения, т.е. если одно поле можно разместить, начиная с адреса двойного слова, а второе – с адреса байта, то компилятор следует первому требованию.

В Си есть средство прямого доступа к группам подряд идущих битов. Внутри некоторой зависящей от реализации единицы памяти («слове») определяются именованные поля, к которым можно осуществлять прямой доступ по имени. Поля определяются при помощи определения структуры, в котором указывается имя поля и его размер, например:

struct {

unsigned int flag1: 1 /*1–ширина поля*/

unsigned int flag2: 1

unsigned int code1: 8

unsigned int code1: 8

} flags;

Поле может иметь тип int, unsigned int или signed int и интерпретируется как объект целочисленного типа с заданным числом битов. От реализации языка зависит, рассматривается ли поле типа int как знаковое.

Для присвоения полям значений используется тот же синтаксис, что и для элементов структур:

flags.flag1 = 1;

flags.code1 = 5;

Под описанную таким образом переменную отводится область памяти размером в слово. Если суммарный размер всех полей превысит размер слова, то отводится 2 соседних слова памяти, причем поле не может перекрывать границу между ними, и компилятор автоматически сдвигает поле, чтобы оно было выровнено по границе слова (в этом случае в первом слове остается безымянное пустое место). В приведенном примере при условии, что машинное слово занимает 16 битов, память распределится следующим образом:

Поле длины 0 без имени указывает на то, что оставшиеся в слове разряды нужно пропустить и начать размещение следующих полей с начала следующего слова.

Как уже было замечено ранее, при программировании динамических структур данных (стек, очередь, список, дерево) используются структуры, содержащие поля - указатели на такие же структуры.

Задача 2. Ввести строку символов из стандартного входного потока и распечатать ее в обратном порядке, построив при этом в динамической памяти стек.

... 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. Дана строка символов. Написать функцию создания бинарного дерева (рекурсивный и нерекурсивный варианты). Узлы дерева имеют следующую структуру:

struct tree { char c;

int n;

struct tree* left;

struct tree* right;

};

где c символ входной строки, а n число вхождений данного символа во входную строку. При построении дерева в качестве ключа использовать код символа.

1. Написать рекурсивную функцию подсчета количества узлов дерева.

2. Написать рекурсивную функцию определения высоты дерева.

3. Написать рекурсивную функцию печати узлов дерева в убывающем порядке.

4. Написать функцию печати узлов дерева по слоям ( рекурсивный и нерекурсивный варианты).

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

ТЕМА 9. Файлы. Библиотечные функции для работы с файлами.

Язык Си предоставляет программисту широкие возможности по работе с произвольными файлами. Любой файл предварительно должен быть открыт. Для этого используется функция fopen:

FILE* fopen(char* name, char* mode);

Функция получает в качестве аргументов внешнее имя файла (name) и режим доступа (mode), а возвращает файловый указатель, используемый в дальнейшем для работы с файлом. Функция возвращает нулевой указатель, если файл не может быть открыт по каким либо причинам.

При запуске Си-программы операционная система всегда открывает три стандартных файла: входной (ему соответствует файловый указатель stdin), выходной (stdout) и файл ошибок (stderr). Обычно stdin соотнесен с клавиатурой, stdout и stderr с экраном.

Файловый указатель ссылается на структуру типа FILE, содержащую следующую информацию о файле:

typedef struct {

int cnt; /* количество оставшихся литер */

char *ptr; /* позиция следующей литеры */

char *base; /* адрес буфера */

int flag; /* режим доступа */

int fd; /* дескриптор файла */

} FILE;

При открытии файла режим доступа может принимать следующие значения:

После окончания работы файл должен быть закрыт с помощью функции fclose, при этом освобождаются все буфера. Если программа завершается нормально, все открытые файлы автоматически закрываются системой.

При работе с файлами существуют различия, определяемые набором функций, используемых для ввода/вывода данных. В частности, можно выделить форматированный ввод – функция

int fscanf(FILE *f,const char *format, . . .)

читает текстовые данные из входного потока, преобразовывает их в соответствии со спецификациями, содержащимися в формате и присваивает по порядку аргументам, каждый из которых должен быть указателем. Обратные действия производит форматированный вывод

int fprintf(FILE *f,const char *format, . . .),

который преобразует аргументы в текстовый вид в соответствии с форматом (format) и пишет в выходной поток.

Особо следует рассмотреть работу с файлами, содержащими текстовую информацию, разбитую на строки. Для записи в файл текстовой информации используются функции - fputc и fputs, а для чтения - fgetc и fgets.

Примечание. До сих пор мы рассматривали строку, как последовательность символов, оканчивающуюся нулевым байтом-‘\0’. Строка же в текстовом файле заканчивается специальным символом –‘\n’ и не содержит нулевого байта.

Например:

FILE *fp;

if((fp=fopen(“a.a”,”w”))!=NULL)

fputs(“str”,fp);

В данном фрагменте создается файл “a.a” и в него записывается строка “str”. Следует заметить, что функция fputs пишет в файл символы строки до нулевого байта. Строка может и не содержать символа ‘\n’, и тогда следующий fputs “приклеит” записываемую строку к предыдущей. Например, после fputs(“ing\n”,fp) в файле будет записана строка “string” с ‘\n’ на конце.

Задача 1. Переписать начальные строки (не более 10-ти) из текстового файла “aaa” в конец файла “bbb”. Длина строки не превышает 80 символов (включая ‘\n’).

main()

{ FILE *f1,*f2;

char s[81];

int i=0;

if((f1=fopen(“aaa”,”r”))==NULL) exit(1);

if((f2=fopen(“bbb”,”a”))==NULL) exit(1);