/>/>/>Кафедра:Автоматика и Информационные Технологии
Структуры и объединения
СОДЕРЖАНИЕ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содержит две структуры time begin и end:
struct chronos {
struct timebegin, end;
};
struct chronostimer = {{2,4}, {10, 10}};
Выражение timer.begin.minutes обращается к минутам minutes времени begin из timer.
В стандарте ANSI C ключевое слово struct при объявленииструктурных переменных можно опускать, то есть допустима и общепринята запись .
chronos timer;
Размер структуры в байтах складывается из размера его элементов.Например, sizeof(timer)= 8 байт. Однако, если включена опция компилятора Options-Compiler-Codegeneration-Word allgnment, то все элементы будут располагаться по четнымадресам. Поэтому в случае
struct FIO { charF[25], I[15], Otch[20]};
будем иметь sizeof(FIO) = 26 + 16 + 20 = 62./>/>Структуры и функции
Над структурами возможны следующие операции:
- присваивание,
- взятие адреса с помощью &,
- осуществление доступа к ее элементам.
Присваивание используется при передаче структуры в функцию по значению ивозврат структуры по значению. Структуры нельзя сравнивать. Инициализироватьструктуру можно списком константных значений ее элементов; автоматическуюструктуру также можно инициализировать присваиванием.
Чтобы лучше познакомиться со структурами, напишем несколько функций,манипулирующих timeи chronos.Возникает вопрос: а как передавать функциям названные объекты? Существует, покрайней мере, три подхода: передавать компоненты по отдельности, передавать всюструктуру целиком и передавать указатель на структуру. Каждый подход имеет своиплюсы и минусы.
Первая функция, maketime, получает двацелых значения и возвращает структуру time.
/* maketime: формируетвремя по компонентам hour и minutes */
timemaketime(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
&&t.minutes >= c.begin.minutes
&&t.minutes
}Указатели на структуры
Так как имя структурного типа обладает всеми правами имен типов, торазрешено определять указатели на структуры:
имя_структурного_типа *имя_указателя_на_структуру;
Если функции передается большая структура, то, чем копировать еецеликом, эффективнее передать указатель на нее. Указатели на структуры ничем неотличаются от указателей на обычные переменные. Объявление
time *pt;
сообщает, что pt — это указатель на структуру типа structtime. Если 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 { Bb;};
struct B { Aa;};
Рассмотрим пример программы создающий такой список и выводящий егосодержимое на консоль.
#include
struct List
{
int dat;
List* next;
};
void main()
{
int i;
List *p, *heap =new List;
for (p=heap,i=0; i
p->dat=i;
p=p->next=newList;
}
for (p=heap,i=0; 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
#include
#include
#define MAXWORD100
int getword(char*, int);
intbinsearch(char *, struct key *, int);
/* подсчет ключевыхслов Си */
main()
{
int n;
charword[MAXWORD];
while(getword(word,MAXWORD) != EOF)
if(isalpha(word[0]))
if((n=binsearch(word, keytab, NKEYS))>=0)
keytab[n].count++;
for (n = 0; n
if(keytab[n].count > 0)
printf("%4d%s\n",keytab[n].count,keytab[n].word);
return 0;
}
/* binsearch: найтислововtab[0]...tab[n-1] */
intbinsearch(char *word, struct key tab[], int n)
{
int cond;
int low, high,mid;
low = 0;
high = n-1;
while (low
mid = (low +high)/2;
if ((cond =strcmp(word, tab[mid].word))
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 определена заголовочном файле .)Что касается объекта, то это может быть переменная, массив или структура. Вкачестве имени типа может выступать имя базового типа (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);
voidungetch(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 — для распознавания букв-цифр.Все они описаны в стандартном заголовочном файле .
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
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. Лабораторные задания
Написать программу, в которой необходимо объявить структуру данных всоответствии с вариантом. Написать все необходимые функции для работы соструктурой:
- функцию, которая размещает структуру в памяти и возвращает указатель нанее;
- функцию, удаляющую структуру из памяти;
- функцию для установки полей структуры, например:
- функции, возвращающие значения полей, например:
- функцию для просмотра структуры (вывода значений ее полей).
Разместить структуры в динамической памяти, объединив их в список.Написать все необходимые функции для работы со списком:
- функцию, добавляющую структуру в список;
- функцию, удаляющую структуру из списка;
- функцию, возвращающую количество элементов в списке.
Написать функцию, выполняющую запрос (пример запроса для каждоговарианта приведен в таблице). Сохранить список в файле.
Таблица.
Примеры вариантовВариант Структура Поля структуры Пример запроса 1 СТУДЕНТ имя — char* Имена студентов указанного курса курс — int пол — bool 2 СЛУЖАЩИЙ имя — char* Количество служащих со стажем не меньше заданного профессия — char* рабочий стаж — int 3. АВТОМОБИЛЬ марка — char* Марки автомобилей мощностью не более заданной мощность – int стоимость — float 4 КАДРЫ имя — char* Имена рабочих заданного разряда номер цеха — int разряд — int 5 ЦЕХ имя — char* Наименование продукции, количество которой не менее заданного начальник — char* кол-во рабочих — int 6 ИЗДЕЛИЕ наименование — char* Наименования изделий, количество которых не более заданного шифр — char* количество — int 7 БИБЛИОТЕКА имя — char* Количество книг указанного автора автор — char* стоимость — real 8 ЭКЗАМЕН имя студента — char* Имена студентов, сдававших экзамен в заданный день дата — int оценка — int 9 АДРЕС имя — char* Имена живущих на четной стороне заданной улицы улица — char* номер дома — int 10 ТОВАР имя — char* Наименование товара, стоимостью не выше заданной количество — int стоимость — real 11 КВИТАНЦИЯ номер — int Общая сумма всех квитанций указанной даты дата — int сумма — real 12 СТРАНА название — char* Название стран, площадью не меньше заданной денежная единица — char* площадь — float 13 ПОЕЗД номер — char* Номера всех поездов указанного типа тип — char* кол-во вагонов — int 14 ИГРА наименование — char* Наименование игры указанного типа и со стоимостью не выше заданной тип — char* стоимость — float 15 ПЛАНЕТА имя — char* Имя планет с расстоянием от Земли не больше заданной размер — real расстояние от Земли — real 16 ЖИВОТНОЕ
имя — char*
класс — char*
средний вес — float Имена всех животных заданного класса 17 ФОТОАППАРАТ модель — char* Модели фотоаппаратов с размером матрицы не меньше заданной изготовитель — char* размер матрицы — int 18 КОРАБЛЬ имя — char* Среднее водоизмещение кораблей заданного типа тип — char* водоизмещение — int 19 РЕКА имя — char* Среднюю длину реки на указанном континенте континент — char* длина — float 20 БЛЮДО название — char* Общую стоимость заказа тип — char* стоимость — float /> 5. Дополнительные задания Задание5.1.
Напишите программу, которая читает текст Си-программы и печатает валфавитном порядке все группы имен переменных, в которых совпадают первые 6символов, но последующие в чем-то различаются. Не обрабатывайте внутренностизакавыченных строк и комментариев. Число 6 сделайте параметром, задаваемым вкомандной строке. Задание 5.2.
Напишите программу печати таблицы «перекрестных ссылок»,которая будет печатать все слова документа и указывать для каждого из нихномера строк, где оно встретилось. Программа должна игнорировать«шумовые» слова, такие как «и», «или» и пр. Задание 5.3.
Напишите программу, которая печатает весь набор различных слов,образующих входной поток, в порядке возрастания частоты их встречаемости. Передкаждым словом должно быть указано число вхождений. />Библиографический список
1. КерниганБ., Ритчи Д., Фьюэр А. Язык программирования Си: Задачи по языку Си. М.:Финансы и статистика, 1985. – 192с.
2. КерниганБ., Ритчи Д. Язык программирования Си. М.: Финансы и статистика, 1992. — 272с.
3. Подбельский В. В., Фомин С. С. Программирование на языке Си.Учеб.пособие. М.: Финансы и статистика, 2004. 600 с.