Кафедра: Автоматика и Информационные Технологии

Структуры и объединения

СОДЕРЖАНИЕ

1. СТРУКТУРЫ

Основные сведения о структурах

Структуры и функции

Указатели на структуры

Массивы структур

2. ОБЪЕДИНЕНИЯ

3. ПРАКТИЧЕСКИЕ ЗАДАНИЯ

Задание 3.1

Задание 3.2.

Задание 3.3.

4. ЛАБОРАТОРНЫЕ ЗАДАНИЯ

5. ДОПОЛНИТЕЛЬНЫЕ ЗАДАНИЯ

Задание 5.1.

Задание 5.2.

Задание 5.3.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Структуры

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

Традиционный пример структуры - строка платежной ведомости. Она содержит такие сведения о служащем, как его полное имя, адрес, номер карточки социального страхования, зарплата и т. д. Некоторые из этих характеристик сами могут быть структурами: например, полное имя состоит из нескольких компонент (фамилии, имени и отчества); аналогично адрес, и даже зарплата. Другой пример (более типичный для Си) - из области графики: точка есть пара координат, прямоугольник есть пара точек и т. д.

Главные изменения, внесенные стандартом ANSI в отношении структур, - это введение для них операции присваивания. Структуры могут копироваться, над ними могут выполняться операции присваивания, их можно передавать функциям в качестве аргументов, а функции могут возвращать их в качестве результата. В большинстве компиляторов уже давно реализованы эти возможности, но теперь они точно оговорены стандартом. Для допускается инициализация.

Основные сведения о структурах

Объявление структуры начинается с ключевого слова struct и содержит список объявлений, заключенный в фигурные скобки:

struct имя_структуры {

список объявлений;

};

имя_структуры иногда называют тегом структуры.

Перечисленные в структуре переменные называются элементами. Элементами структур могут быть:

- переменные и массивы базовых типов,

- переменные и массивы пользовательских типов, кроме типа самой структуры имя_структуры,

- указатели на любые типы, включая и тип самой структуры имя_структуры,

- функции.

Включение в структуры элементов-функций не является общепринятым. Как правило, в этом случае переходят к понятию класса.

Элементы структур являются публичными, то есть к элементам структурных переменных можно обращаться в любом месте области видимости этих переменных.

Приведем пример структуры time:

struct time {

int hour;

int minutes;

};

В нашем примере элементами структуры будут hour и minutes.

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

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

struct {

intx, y;

} q;

Однако если структура имеет тег, то этим тегом далее можно пользоваться при определении структурных объектов. Например, с помощью заданного выше описания структуры time строка

struct time t;

определяет структурную переменную t типа structtime. Принято использовать один и тот же термин структура применительно к пользовательскому типу данных и к структурной переменной. Однако, по фразам «объявление структуры» и «определение структуры» ситуация становится однозначной. Для структурной переменной, как и для массива при объявлении сразу выделяется память. Поэтому структурная переменная определяется, а тип объявляется.

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

Имя_структуры.элемент_структуры

Операция доступа к элементу структуры ‘.’ соединяет имя структуры и имя элемента.

Например,

struct time t = {21, 30};

printf("%d:%d", t.hour, t.minutes);

Структуры могут быть вложены друг в друга. Например, структура chronos содержит две структуры timebegin и end:

struct chronos {

struct time begin, end;

};

struct chronos timer = {{2,4}, {10, 10}};

Выражение timer.begin.minutesобращается к минутам minutesвремени beginиз timer.

В стандарте ANSIC ключевое слово struct при объявлении структурных переменных можно опускать, то есть допустима и общепринята запись .

chronos timer;

Размер структуры в байтах складывается из размера его элементов. Например, sizeof(timer) = 8 байт. Однако, если включена опция компилятора Options-Compiler-Code generation-Word allgnment, то все элементы будут располагаться по четным адресам. Поэтому в случае

struct FIO { char F[25], I[15], Otch[20]};

будем иметь sizeof(FIO) = 26 + 16 + 20 = 62.

Структуры и функции

Над структурами возможны следующие операции:

- присваивание,

- взятие адреса с помощью &,

- осуществление доступа к ее элементам.

Присваивание используется при передаче структуры в функцию по значению и возврат структуры по значению. Структуры нельзя сравнивать. Инициализировать структуру можно списком константных значений ее элементов; автоматическую структуру также можно инициализировать присваиванием.

Чтобы лучше познакомиться со структурами, напишем несколько функций, манипулирующих time и chronos. Возникает вопрос: а как передавать функциям названные объекты? Существует, по крайней мере, три подхода: передавать компоненты по отдельности, передавать всю структуру целиком и передавать указатель на структуру. Каждый подход имеет свои плюсы и минусы.

Первая функция, maketime, получает два целых значения и возвращает структуру time.

/* maketime: формирует время по компонентам hour и minutes */

time maketime(int hour, int minutes){

time temp;

temp.hour = hour;

temp.minutes = minutes;

return temp;

}

Заметим: никакого конфликта между именем аргумента и именем элемента структуры не возникает; более того, сходство подчеркивает родство обозначаемых им объектов.

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

chronos timer;

timer.begin = maketime(0, 0);

timer.end = maketime(12, 5);

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

/* addtime: сложение времени */

time addtime (time tm1, time tm2)

{

tm1.minutes += tm2.minutes;

tm1.hour += tm2.hour + tm1.minutes/60;

tm1.minutes %= 60;

return tm1;

}

Здесь оба аргумента и возвращаемое значение - структуры.

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

/* tinchronos: возвращает 1, если t в c, и 0 в противном случае */

int tinchronos (struct time t, struct chronos c)

{

return t.hour >= c.begin.hour

&& t.hour < c.end.hour

&& t.minutes >= c.begin.minutes

&& t.minutes < c.end.minutes;

}

Указатели на структуры

Так как имя структурного типа обладает всеми правами имен типов, то разрешено определять указатели на структуры:

имя_структурного_типа * имя_указателя_на_структуру;

Если функции передается большая структура, то, чем копировать ее целиком, эффективнее передать указатель на нее. Указатели на структуры ничем не отличаются от указателей на обычные переменные. Объявление

time *pt;

сообщает, что pt - это указатель на структуру типа struct time. Если pt указывает на структуру time, то *pt - это сама структура, а (*pt).hour и (*pt).minutes - ее элементы. Используя указатель pt, мы могли бы написать

time origin, *pt;

pt = &origin;

printf("origin: (%d,%d)\n", (*pt).hour, (*pt).minutes);

Скобки в (*pt).hour необходимы, поскольку приоритет операции «.» выше, чем приоритет операции разыменования «*». Выражение *pt.hour будет проинтерпретировано как *(pt.hour), что неверно, поскольку pt.hour не является указателем.

Указатели на структуры используются весьма часто, поэтому для доступа к ее элементам была придумана операция «обращение к элементу структуры по указателю», сокращенно «стрелка» с формой записи «->». Если t — указатель на структуру, то

t->элемент-структуры

есть ее отдельный элемент. Поэтому printf можно переписать в виде

printf("origin: (%d,%d)\n", pt->hour, pt->minutes);

Операции . и -> левоассоциативны, то есть выполняются слева направо. Таким образом, при наличии объявления

chronos ch, *cht = &ch;

следующие четыре выражения будут эквивалентны:

ch.begin.hour

cht->begin.hour

(ch.begin).hour

(cht ->begin).hour

Операции доступа к элементам структуры . и -> вместе с операторами вызова функции () и индексации массива [] занимают самое высокое положение в иерархии приоритетов и выполняются раньше любых других операторов. Например, если задано объявление

struct {

int len;

char *str;

} *p;

то

++p->len

увеличит на 1 значение элемента структуры len, а не указатель p, поскольку в этом выражении как бы неявно присутствуют скобки: ++(p->len). Чтобы изменить порядок выполнения операций, нужны явные скобки. Так, в (++р)->len, прежде чем взять значение len, программа прирастит указатель p. В (р++)->len указатель p увеличится после того, как будет взято значение len (в последнем случае скобки не обязательны).

По тем же правилам *p->str обозначает содержимое объекта, на который указывает str; *p->str++ прирастит указатель str после получения значения объекта, на который он указывал (как и в выражении *s++), (*p->str)++ увеличит значение объекта, на который указывает str; *p++->str увеличит p после получения того, на что указывает str.

Часто возникает проблема, при объявлении структуры объявить там указатель на эту же структуру. Не смотря на то, что описание структуры еще не завершено, формат языка это позволяет. Например, опишем структуру List, представляющую собой однонаправленный список, где в качестве данных опишем переменную типа int.

struct List{

int dat;

List* next;

};

Если структуры содержатся друг в друге, то используют предобъявление структуры. Например

struct B;

struct A { B b;};

struct B { A a;};

Рассмотрим пример программы создающий такой список и выводящий его содержимое на консоль.

#include<stdio.h>

struct List

{

int dat;

List* next;

};

void main()

{

int i;

List *p, *heap = new List;

for (p=heap, i=0; i<10; i++){

p->dat=i;

p=p->next=new List;

}

for (p=heap, i=0; i<10; i++){

printf("%d",p->dat);

p=p->next;

}

}

Здесь мы описали два указателя: heap – для указания начала списка, p – для передвижения по списку; и простую переменную, как счетчик цикла. В отличие от массива, наш список будет "разбросан" по памяти, поскольку оператор new выделяет первые свободные блоки памяти, но это неважно, поскольку мы передвигаемся по списку, используя сохраненные в самом списке адреса:

p = p->next;.

Массивы структур

Рассмотрим программу, определяющую число вхождений каждого ключевого слова в текст Си-программы. Нам нужно уметь хранить ключевые слова в виде массива строк и счетчики ключевых слов в виде массива целых. Один из возможных вариантов - это иметь два параллельных массива:

char *keyword[NKEYS];

int keycount[NKEYS];

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

char *word;

int count;

Такие пары составляют массив. Объявление

struct key {

char *word;

int count;

} keytab[NKEYS];

объявляет структуру типа key и определяет массив keytab, каждый элемент которого является структурой этого типа и которому где-то будет выделена память. Это же можно записать и по-другому:

struct key {

char *word;

int count;

};

key keytab[NKEYS];

Так как keytab содержит постоянный набор имен, его легче всего сделать внешним массивом и инициализировать один раз в момент определения. Инициализация структур аналогична ранее демонстрировавшимся инициализациям - за определением следует список инициализаторов, заключенный в фигурные скобки:

struct key {

char *word;

int count;

} keytab[] = {

"auto", 0,

"break", 0,

"case", 0,

"char", 0,

"const", 0,

"continue", 0,

"default", 0,

/*...*/

"unsigned", 0,

"void", 0,

"volatile", 0,

"while", 0

};

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

{ "auto", 0 },

{ "break", 0 },

{ "case", 0 },

...

Однако когда инициализаторы - простые константы или строки символов и все они имеются в наличии, во внутренних скобках нет необходимости. Число элементов массива keytab будет вычислено по количеству инициализаторов, поскольку они представлены полностью, а внутри квадратных скобок "[]" ничего не задано.

Программа подсчета ключевых слов начинается с определения keytab. Программа main читает ввод, многократно обращаясь к функции getword и получая на каждом ее вызове очередное слово. Каждое слово ищется в keytab. Для этого используется функция бинарного поиска. Список ключевых слов должен быть упорядочен в алфавитном порядке.

#include <stdio.h>

#include <ctype.h>

#include <string.h>

#define MAXWORD 100

int getword(char *, int);

int binsearch(char *, struct key *, int);

/* подсчет ключевых слов Си */

main()

{

int n;

char word[MAXWORD];

while(getword(word, MAXWORD) != EOF)

if (isalpha(word[0]))

if ((n=binsearch(word, keytab, NKEYS))>=0)

keytab[n].count++;

for (n = 0; n < NKEYS; n++)

if (keytab[n].count > 0)

printf("%4d%s\n",keytab[n].count, keytab[n].word);

return 0;

}

/* binsearch: найтисловов tab[0]...tab[n-1] */

int binsearch(char *word, struct key tab[], int n)

{

int cond;

int low, high, mid;

low = 0;

high = n-1;

while (low <= high) {

mid = (low + high)/2;

if ((cond = strcmp(word, tab[mid].word)) < 0)

high = mid - 1;

else if (cond > 0)

low = mid + 1;

else

return mid;

}

return -1;

}

Чуть позже мы рассмотрим функцию getword, а сейчас нам достаточно знать, что при каждом ее вызове получается очередное слово, которое запоминается в массиве, заданном первым аргументом.

NKEYS - количество ключевых слов в keytab. Хотя мы могли бы подсчитать число таких слов вручную, гораздо легче и безопасней сделать это с помощью машины, особенно если список ключевых слов может быть изменен. Одно из возможных решений — поместить в конец списка инициализаторов пустой указатель (NULL) и затем перебирать в цикле элементы keytab, пока не встретится концевой элемент.

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

размер keytab / размер struct key

В Си имеется унарная операция sizeof, которая работает во время компиляции. Его можно применять для вычисления размера любого объекта. Выражения

sizeof объект

и

sizeof (имя типа)

выдают целые значения, равные размеру указанного объекта или типа в байтах. (Строго говоря, sizeof выдает беззнаковое целое, тип которого size_t определена заголовочном файле <stddef.h>.) Что касается объекта, то это может быть переменная, массив или структура. В качестве имени типа может выступать имя базового типа (int, double ...) или имя производного типа, например структуры или указателя.

В нашем случае, чтобы вычислить количество ключевых слов, размер массива надо поделить на размер одного элемента. Указанное вычисление используется в инструкции #define для установки значения NKEYS:

#define NKEYS (sizeof keytab / sizeof(struct key))

Этот же результат можно получить другим способом - поделить размер массива на размер какого-то его конкретного элемента:

#define NKEYS (sizeof keytab / sizeof keytab[0])

Преимущество такого рода записей в том, что их не надо коppектировать при изменении типа.

Поскольку препроцессор не обращает внимания на имена типов, оператор sizeof нельзя применять в #if. Но в #define выражение препроцессором не вычисляется, так что предложенная нами запись допустима.

Теперь поговорим о функции getword. Мы написали getword в несколько более общем виде, чем требуется для нашей программы, но она от этого не стала заметно сложнее. Функция getword берет из входного потока следующее "слово". Под словом понимается цепочка букв-цифр, начинающаяся с буквы, или отдельный символ, отличный от символа-разделителя. В случае конца файла функция возвращает EOF, в остальных случаях ее значением является код первого символа слова или сам символ, если это не буква.

/* getword: принимает следующее слово или символ из ввода */

int getword (char *word, int lim)

{

int c, getch(void);

void ungetch(int);

char *w = word;

while (isspace(c = getch()))

;

if (c != EOF)

*w++ = c;

if (!isalpha(c)) {

*w ='\0';

return c;

}

for ( ; --lim > 0; w++)

if (!isalnum(*w = getch())) {

ungetch(*w);

break;

}

*w ='\0';

return word[0];

}

Функция getword обращается к getch и ungetch. По завершении набора букв-цифр оказывается, что getword взяла лишний символ. Обращение к ungetch позволяет вернуть его назад во входной поток. В getword используются также isspace - для пропуска символов-разделителей, isalpha - для идентификации букв и isalnum - для распознавания букв-цифр. Все они описаны в стандартном заголовочном файле <ctype.h>.

2. Объединения

Объединение - это переменная, которая может содержать (в разные моменты времени) объекты различных типов и размеров. Все требования относительно размеров и выравнивания выполняет компилятор. Объединения позволяют хранить разнородные данные в одной и той же области памяти без включения в программу машинно-зависимой информации. Эти средства аналогичны вариантным записям в Паскале.

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

Формат объединения отличается от структуры только служебным словом union:

union имя {

тип1 имя переменной 1;

тип2 имя переменной 2;

…

};

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

Доступ к элементам объединения осуществляется так же, как к элементам структуры – через точку для имени объединения, или по стрелке для обращения через указатель.

Пример 1. Например, имеется 4 флага, и мы хотели бы сократить время для операций с несколькими флагами сразу. Для простоты рассмотрим, как можно обнулить все флаги одной операцией:

union Flag{

long g;

char ch[4];

};

void main()

{

Flag fl;

fl.ch[0] = 1;

fl.ch[1] = 2;

fl.ch[2] = 4;

fl.ch[3] = 8;

printf("Flag = %x\n",fl.g);

fl.g = 0; //Все флаги равны 0

printf("Flag = NULL\n");

for (int i = 0; i < 4; i++)

printf("%d\n",(int)fl.ch[i]);

}

Мы описали объединение, как переменную типа long и, одновременно, в виде массива типа char. Теперь, для переменной типа Flag, мы можем работать с каждым флагом независимо, или, используя операцию с переменной типа long, обнулить все флаги простой операцией присваивания fl.g = 0;.

В следующем операторе вывода мы хотели вывести каждый символ в виде целого числа, поэтому мы поставили оператор явного преобразования типа: (int)fl.ch[i].

3. Практические задания

Задание 3.1

Рассмотреть пример однонаправленного списка, построенного на структуре List. Измените структуру так, чтобы получить возможность передвигаться по списку не только вперед, но и назад (двунаправленный список).

Задание 3.2.

Записи в линейном списке содержат ключевое поле типа int. Сформировать однонаправленный список. Удалить из него элемент с заданным номером, добавить элемент с заданным номером.

Задание 3.3.

Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить элемент с заданным ключом. Добавить К элементов перед элементом с заданным номером.

4. Лабораторные задания

Написать программу, в которой необходимо объявить структуру данных в соответствии с вариантом. Написать все необходимые функции для работы со структурой:

- функцию, которая размещает структуру в памяти и возвращает указатель на нее;

- функцию, удаляющую структуру из памяти;

- функцию для установки полей структуры, например:

- функции, возвращающие значения полей, например:

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

Разместить структуры в динамической памяти, объединив их в список. Написать все необходимые функции для работы со списком:

- функцию, добавляющую структуру в список;

- функцию, удаляющую структуру из списка;

- функцию, возвращающую количество элементов в списке.

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

Таблица.

Примеры вариантов

5. Дополнительные задания

Задание 5.1.

Напишите программу, которая читает текст Си-программы и печатает в алфавитном порядке все группы имен переменных, в которых совпадают первые 6 символов, но последующие в чем-то различаются. Не обрабатывайте внутренности закавыченных строк и комментариев. Число 6 сделайте параметром, задаваемым в командной строке.

Задание 5.2.

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

Задание 5.3.

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

Библиографический список

1. Керниган Б., Ритчи Д., Фьюэр А. Язык программирования Си: Задачи по языку Си. М.: Финансы и статистика, 1985. – 192с.

2. Керниган Б., Ритчи Д. Язык программирования Си. М.:Финансы и статистика, 1992. - 272с.

3. Подбельский В. В., Фомин С. С. Программирование на языке Си. Учеб.пособие. М.: Финансы и статистика, 2004. 600 с.