Учебное пособие: Структуры и объединения

Учебное пособие: Структуры и объединения

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

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

СОДЕРЖАНИЕ

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 {

int x, y;

} q;

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

struct time t;

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

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

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

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

Например,

struct time t = {21, 30};

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

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

struct chronos {

struct time begin, end;

};

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

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

В стандарте ANSI C ключевое слово 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, пока не встретится концевой элемент.

Страницы: 1, 2