Структуры данных. Хрестоматия по программированию на Си в Unix
Структуры данных.
Структуры ("записи") представляют собой агрегаты разнородных данных (полей разного типа); в отличие от массивов, где все элементы имеют один и тот же тип.
struct { int x, y; /* два целых поля */ char s[10]; /* и одно - для строки */ } s1;
Структурный тип может иметь имя:
struct XYS { int x, y; /* два целых поля */ char str[10]; /* и одно - для строки */ };
Здесь мы объявили тип, но не отвели ни одной переменной этого типа (хотя могли бы). Теперь опишем переменную этого типа и указатель на нее:
struct XYS s2, *sptr = &s2;
Доступ к полям структуры производится по имени поля (а не по индексу, как у массивов):
имя_структурной_переменной.имя_поля
указатель_на_структуру -> имя_поля
то есть
не а #define ВЕС 0 struct { int вес, рост; } x; #define РОСТ 1 x.рост = 175; int x[2]; x[РОСТ] = 175;
Например
s1.x = 13; strcpy(s2.str, "Finish"); sptr->y = 27;
Структура может содержать структуры другого типа в качестве полей:
struct XYS_Z { struct XYS xys; int z; } a1; a1.xys.x = 71; a1.z = 12;
Структура того же самого типа не может содержаться в качестве поля - рекурсивные определения запрещены. Зато нередко используются поля - ссылки на структуры такого же типа (или другого). Это позволяет организовывать списки структур:
struct node { int value; struct node *next; };
Очень часто используются массивы структур:
struct XYS array[20]; int i = 5, j; array[i].x = 12; j = array[i].x;
Статические структуры можно описывать с инициализацией, перечисляя значения их полей в {} через запятую:
extern struct node n2; struct node n1 = { 1, &n2 }, n2 = { 2, &n1 }, n3 = { 3, NULL };
В этом примере n2 описано предварительно для того, чтобы &n2 в строке инициализации n1 было определено.
Структуры одинакового типа можно присваивать целиком (что соответствует присваиванию каждого из полей):
struct XYS s1, s2; ... s2 = s1;
в отличие от массивов, которые присваивать целиком нельзя:
При записи данных в файл (да и вообще) используйте структуры вместо массивов, если элементы массива имеют разное смысловое назначение. Не воспринимайте структуру просто как средство объединения данных разных типов, она может быть и средством объединения данных одного типа, если это добавляет осмысленности нашей программе. Чем плох фрагмент?
int data[2]; data[0] = my_key; data[1] = my_value; write(fd, (char *) data, 2 * sizeof(int));
Во-первых, тогда уж лучше указать размер всего массива сразу (хотя бы на тот случай, если мы изменим его размер на 3 и забудем поправить множитель с 2 на 3).
write(fd, (char *) data, sizeof data);
Кстати, почему мы пишем data, а не &data? (ответ: потому что имя массива и есть его адрес). Во-вторых, элементы массива имеют разный смысл, так не использовать ли тут структуру?
struct _data { int key; int value; } data; data.key = my_key; data.value = my_value; write(fd, &data, sizeof data);
Что напечатает следующая программа? Нарисуйте расположение указателей по окончании данной программы.
#include <stdio.h>
struct lnk{ char c; struct lnk *prev, *next; } chain[20], *head = chain; add(c) char c; { head->c = c; head->next = head+1; head->next->prev = head; head++; } main(){ char *s = "012345"; while( *s ) add( *s++ ); head->c = '-'; head->next = (struct lnk *)NULL; chain->prev = chain->next; while( head->prev ){ putchar( head->prev->c ); head = head->prev; if( head->next ) head->next->prev = head->next->next; } }
Напишите программу, составлящую двунаправленный список букв, вводимых с клавиатуры. Конец ввода - буква '\n'. После третьей буквы вставьте букву '+'. Удалите пятую букву. Распечатайте список в обратном порядке. Оформите операции вставки/удаления как функции. Элемент списка должен иметь вид:
struct elem{ char letter; /* буква */ char *word; /* слово */ struct elem *prev; /* ссылка назад */ struct elem *next; /* ссылка вперед */ }; struct elem *head, /* первый элемент списка */ *tail, /* последний элемент */ *ptr, /* рабочая переменная */ *prev; /* предыдущий элемент при просмотре */ int c, cmp; ... while((c = getchar()) != '\n' ) Insert(c, tail); for(ptr=head; ptr != NULL; ptr=ptr->next) printf("буква %c\n", ptr->letter);
Это как бы "ящик" в который можно поместить значение любого типа из перечисленных, но не ВСЕ ВМЕСТЕ ("и то и это", как у структур), а ПО ОЧЕРЕДИ ("или/или"). Размер его достаточно велик, чтоб вместить самый большой из перечисленных типов данных.
Мы можем занести в union значение и интерпретировать его как другой тип данных это иногда используется в машинно-зависимых программах. Вот пример, выясняющий порядок байтов в short числах:
union lb { char s[2]; short i; } x; unsigned hi, lo; x.i = (02 << 8) | 01; hi = x.s[1]; lo = x.s[0]; printf( "%d %d\n", hi, lo);
или так:
#include <stdio.h>
union { int i; unsigned char s[sizeof(int)]; } u; void main(){ unsigned char *p; int n; u.i = 0x12345678; for(n=0, p=u.s; n < sizeof(int); n++, p++){ printf("%02X ", *p); } putchar('\n'); }
или порядок слов в long числах:
union xx { long l; struct ab { short a; /* low word */ short b; /* high word */ } ab; } c; main(){ /* На IBM PC 80386 печатает 00020001 */ c.ab.a = 1; c.ab.b = 2; printf("%08lx\n", c.l ); }
Найдите ошибки в описании структурного шаблона:
structure { int arr[12], char string, int *sum }
Разработайте структурный шаблон, который содержал бы название месяца, трехбуквенную аббревиатуру месяца, количество дней в месяце и номер месяца. Инициализируйте его для невисокосного года.
struct month { char name[10]; /* или char *name; */ char abbrev[4]; /* или char *abbrev; */ int days; int num; }; struct month months[12] = { /* индекс */ {"Январь" , "Янв", 31, 1 }, /* 0 */ {"Февраль", "Фев", 28, 2 }, /* 1 */ ... {"Декабрь", "Дек", 31, 12}, /* 11 */ }, *mptr = & months[0]; /* или *mptr = months */ main(){ struct month *mptr; printf( "%s\n", mptr[1].name ); printf( "%s %d\n", mptr->name, mptr->num ); }
Напишите функцию, сохраняющую массив months в файл; функцию, считывающую его из файла. Используйте fprintf и fscanf.
В чем будет разница в функции чтения, когда поле name описано как char name[10] и как char *name?
Ответ: во втором случае для сохранения прочитанной строки надо заказывать память динамически при помощи malloc() и сохранять в ней строку при помощи strcpy(), т.к. память для хранения самой строки в структуре не зарезервирована (а только для указателя на нее).
Найдите ошибку в операторах функции main(). Почему печатается не "Февраль", а какой-то мусор? Указание: куда указывает указатель mptr, описанный в main()? Ответ: в "неизвестно куда" - это локальная переменная (причем не получившая начального значения - в ней содержится мусор), а не то же самое, что указатель mptr, описанный выше! Уберите описание mptr из main.
Заметим, что для распечатки всех или нескольких полей структуры следует ЯВНО перечислить в printf() все нужные поля и указать форматы, соответствующие типам этих полей. Не существует формата или стандартной функции, позволяющей распечатать все поля сразу (однако такая функция может быть написана вами для конкретного типа структур). Также не существует формата для scanf(), который вводил бы структуру целиком. Вводить можно только по частям - каждое поле отдельно.
Напишите программу, которая по номеру месяца возвращает общее число дней года вплоть до этого месяца.
Переделайте предыдущую программу таким образом, чтобы она по написанному буквами названию месяца возвращала общее число дней года вплоть до этого месяца. В программе используйте функцию strcmp().
Переделайте предыдущую программу таким образом, чтобы она запрашивала у пользователя день, месяц, год и выдавала общее количество дней в году вплоть до данного дня. Месяц может обозначаться номером, названием месяца или его аббревиатурой.
Составьте структуру для учетной картотеки служащего, которая содержала бы следующие сведения: фамилию, имя, отчество; год рождения; домашний адрес; место работы, должность; зарплату; дату поступления на работу.
Что печатает программа?
struct man { char name[20]; int salary; } workers[] = { { "Иванов", 200 }, { "Петров", 180 }, { "Сидоров", 150 } }, *wptr, chief = { "начальник", 550 }; main(){ struct man *ptr, *cptr, save; ptr = wptr = workers + 1; cptr = &chief; save = workers[2]; workers[2] = *wptr; *wptr = save; wptr++; ptr--; ptr->salary = save.salary; printf( "%c %s %s %s %s\n%d %d %d %d\n%d %d %c\n", *workers[1].name, workers[2].name, cptr->name, ptr[1].name, save.name, wptr->salary, chief.salary, (*ptr).salary, workers->salary, wptr - ptr, wptr - workers, *ptr->name ); }
Ответ:
С Петров начальник Сидоров Сидоров 180 550 150 150 2 2 И
Разберите следующий пример:
#include <stdio.h>
struct man{ char *name, town[4]; int salary; int addr[2]; } men[] = { { "Вася", "Msc", 100, { 12, 7 } }, { "Гриша", "Len", 120, { 6, 51 } }, { "Петя", "Rig", 140, { 23, 84 } }, { NULL, "" , -1, { -1, -1 } } }; main(){ struct man *ptr, **ptrptr; int i; ptrptr = &ptr; *ptrptr = &men[1]; /* men+1 */ printf( "%s %d %s %d %c\n", ptr->name, ptr->salary, ptr->town, ptr->addr[1], ptr[1].town[2] ); (*ptrptr)++; /* копируем *ptr в men[0] */ men[0].name = ptr->name; /* (char *) #1 */ strcpy( men[0].town, ptr->town ); /* char [] #2 */ men[0].salary = ptr->salary; /* int #3 */ for( i=0; i < 2; i++ ) men[0].addr[i] = ptr->addr[i]; /* массив #4 */ /* распечатываем массив структур */ for(ptr=men; ptr->name; ptr++ ) printf( "%s %s %d\n", ptr->name, ptr->town, ptr->addr[0]); }
Обратите внимание на такие моменты:
- Как производится работа с указателем на указатель (ptrptr).
- При копировании структур отдельными полями, поля скалярных типов (int, char, long, ..., указатели) копируются операцией присваивания (см. строки с пометками #1 и #3). Поля векторных типов (массивы) копируются при помощи цикла, поэлементно пересылающего массив (строка #4). Строки (массивы букв) пересылаются стандартной функцией strcpy (строка #2). Все это относится не только к полям структур, но и к переменным таких типов. Структуры можно также копировать не по полям, а целиком: men[0]= *ptr;
- Запись аргументов функции printf() лесенкой позволяет лучше видеть, какому формату соответствует каждый аргумент.
- При распечатке массива структур мы печатаем не определенное их количество (равное размеру массива), а пользуемся указателем NULL в поле name последней структуры как признаком конца массива.
- В поле town мы храним строки из 3х букв, однако выделяем для хранения массив из 4х байт. Это необходимо потому, что строка "Msc" состоит не из 3х, а из 4х байтов: 'M','s','c','\0'.
При работе со структурами и указателями большую помощь могут оказать рисунки. Вот как (например) можно нарисовать данные из этого примера (массив men изображен не весь):
--ptr-- --ptrptr- ptr | * |<------|---* | ---|--- --------- | / =========men[0]== / men:|name | *---|-----> "Вася" | |---------------| | |town |M|s|c|\0| | |---------------| | |salary| 100 | | |---------------| | |addr | 12 | 7 | \ ---------------- \ =========men[1]== \-->|name | *---|-----> "Гриша" ............
Составьте программу "справочник по таблице Менделеева", которая по названию химического элемента выдавала бы его характеристики. Таблицу инициализируйте массивом структур.
© Copyright А. Богатырев, 1992-95
Си в UNIX
| |
Память лучше отводить не из массива, а функцией calloc(), которая аналогична функции malloc(), но дополнительно расписывает выделенную память байтом '\0' (0, NULL). Вот функции вставки и удаления:
extern char *calloc(); /* создать новое звено списка для буквы c */ struct elem *NewElem(c) char c; { struct elem *p = (struct elem *) calloc(1, sizeof(struct elem)); /* calloc автоматически обнуляет все поля, * в том числе prev и next */ p->letter = c; return p; } /* вставка после ptr (обычно - после tail) */ Insert(c, ptr) char c; struct elem *ptr; { struct elem *newelem = NewElem(c), *right; if(head == NULL){ /* список был пуст */ head=tail=newelem; return; } right = ptr->next; ptr->next = newelem; newelem->prev = ptr; newelem->next = right; if( right ) right->prev = newelem; else tail = newelem; } /* удалить ptr из списка */ Delete( ptr ) struct elem *ptr; { struct elem *left=ptr->prev, *right=ptr->next; if( right ) right->prev = left; if( left ) left->next = right; if( tail == ptr ) tail = left; if( head == ptr ) head = right; free((char *) ptr); }
Напишите аналогичную программу для списка слов.
struct elem *NewElem(char *s) { struct elem *p = (struct elem *) calloc(1, sizeof(struct elem)); p->word = strdup(s); return p; } void DeleteElem(struct elem *ptr){ free(ptr->word); free(ptr); }
Усложнение: вставляйте слова в список в алфавитном порядке. Используйте для этого функцию strcmp(), просматривайте список так:
struct elem *newelem; if (head == NULL){ /* список пуст */ head = tail = NewElem(новое_слово); return; } /* поиск места в списке */ for(cmp= -1, ptr=head, prev=NULL; ptr; prev=ptr, ptr=ptr->next ) if((cmp = strcmp(новое_слово, ptr->word)) <= 0 ) break;
Если цикл окончился с cmp==0, то такое слово уже есть в списке. Если cmp < 0, то такого слова не было и ptr указывает элемент, перед которым надо вставить слово новое_слово, а prev - после которого (prev==NULL означает, что надо вставить в начало списка); т.е. слово вставляется между prev и ptr. Если cmp > 0, то слово надо добавить в конец списка (при этом ptr==NULL).
head ==> "a" ==> "b" ==> "d" ==> NULL | | prev "c" ptr if(cmp == 0) return; /* слово уже есть */ newelem = NewElem( новое_слово ); if(prev == NULL){ /* в начало */ newelem->next = head; newelem->prev = NULL; head->prev = newelem; head = newelem; } else if(ptr == NULL){ /* в конец */ newelem->next = NULL; newelem->prev = tail; tail->next = newelem; tail = newelem; } else { /* между prev и ptr */ newelem->next = ptr; newelem->prev = prev; prev->next = newelem; ptr ->prev = newelem; }
Напишите функции для работы с комплексными числами
struct complex { double re, im; };
Например, сложение выглядит так:
struct complex add( c1, c2 ) struct complex c1, c2; { struct complex sum; sum.re = c1.re + c2.re; sum.im = c1.im + c2.im; return sum; } struct complex a = { 12.0, 14.0 }, b = { 13.0, 2.0 }; main(){ struct complex c; c = add( a, b ); printf( "(%g,%g)\n", c.re, c.im ); }
Массивы в Си нельзя присваивать целиком, зато структуры - можно. Иногда используют такой трюк: структуру из единственного поля-массива
typedef struct { int ai[5]; } intarray5; intarray5 a, b = { 1, 2, 3, 4, 5 };
и теперь законно
a = b;
Зато доступ к ячейкам массива выглядит теперь менее изящно:
a.ai[2] = 14; for(i=0; i < 5; i++) printf( "%d\n", a.ai[i] );
Также невозможно передать копию массива в качестве фактического параметра функции. Даже если мы напишем:
typedef int ARR16[16]; ARR16 d; void f(ARR16 a){ printf( "%d %d\n", a[3], a[15]); a[3] = 2345; } void main(void){ d[3] = 9; d[15] = 98; f(d); printf("Now it is %d\n", d[3]); }
то последний printf напечатает "Now it is 2345", поскольку в f передается адрес массива, но не его копия; поэтому оператор a[3]=2345 изменяет исходный массив. Обойти это можно, использовав тот же трюк, поскольку при передаче структуры в качестве параметра передается уже не ее адрес, а копия всей структуры (как это и принято в Си во всех случаях, кроме массивов).
Напоследок упомянем про битовые поля - элементы структуры, занимающие только часть машинного слова - только несколько битов в нем. Размер поля в битах задается конструкцией :число_битов. Битовые поля используются для более компактного хранения информации в структурах (для экономии места).
struct XYZ { /* битовые поля должны быть unsigned */ unsigned x:2; /* 0 .. 2**2 - 1 */ unsigned y:5; /* 0 .. 2**5 - 1 */ unsigned z:1; /* YES=1 NO=0 */ } xyz; main(){ printf("%u\n", sizeof(xyz)); /* == sizeof(int) */ xyz.z = 1; xyz.y = 21; xyz.x = 3; printf("%u %u %u\n", xyz.x, ++xyz.y, xyz.z); /* Значение битового поля берется по модулю * максимально допустимого числа 2**число_битов - 1 */ xyz.y = 32 /* максимум */ + 7; xyz.x = 16+2; xyz.z = 11; printf("%u %u %u\n", xyz.x, xyz.y, xyz.z); /* 2 7 1 */ }
Поле ширины 1 часто используется в качестве битового флага: вместо
#define FLAG1 01 #define FLAG2 02 #define FLAG3 04 int x; /* слово для нескольких флагов */ x |= FLAG1; x &= ~FLAG2; if(x & FLAG3) ...;
используется
struct flags { unsigned flag1:1, flag2:1, flag3:1; } x; x.flag1 = 1; x.flag2 = 0; if( x.flag3 ) ...;
Следует однако учесть, что машинный код для работы с битовыми полями более сложен и занимает больше команд (т.е. медленнее и длиннее).
К битовым полям нельзя применить операцию взятия адреса "&", у них нет адресов и смещений!
Пример на использование структур с полем переменного размера. Часть переменной длины может быть лишь одна и обязана быть последним полем структуры. Внимание: это программистский трюк, использовать осторожно!
#include <stdio.h>
#define SZ 5 extern char *malloc(); #define VARTYPE char struct obj { struct header { /* постоянная часть */ int cls; int size; /* размер переменной части */ } hdr; VARTYPE body [1]; /* часть переменного размера: в описании ровно ОДИН элемент массива */ } *items [SZ]; /* указатели на структуры */ #define OFFSET(field, ptr) ((char *) &ptr->field - (char *)ptr) int body_offset; /* создание новой структуры */ struct obj *newObj( int cl, char *s ) { char *ptr; struct obj *op; int n = strlen(s); /* длина переменной части (штук VARTYPE) */ int newsize = sizeof(struct header) + n * sizeof(VARTYPE); printf("[n=%d newsize=%d]\n", n, newsize); /* newsize = (sizeof(struct obj) - sizeof(op->body)) + n * sizeof(op->body); При использовании этого размера не учитывается, что struct(obj) выровнена на границу sizeof(int). Но в частности следует учитывать и то, на границу чего выровнено начало поля op->body. То есть самым правильным будет newsize = body_offset + n * sizeof(op->body); */ /* отвести массив байт без внутренней структуры */ ptr = (char *) malloc(newsize); /* наложить поверх него структуру */ op = (struct obj *) ptr; op->hdr.cls = cl; op->hdr.size = n; strncpy(op->body, s, n); return op; } void printobj( struct obj *p ) { register i; printf( "OBJECT(cls=%d,size=%d)\n", p->hdr.cls, p->hdr.size); for(i=0; i < p->hdr.size; i++ ) putchar( p->body[i] ); putchar( '\n' ); } char *strs[] = { "a tree", "a maple", "an oak", "the birch", "the fir" }; int main(int ac, char *av[]){ int i; printf("sizeof(struct header)=%d sizeof(struct obj)=%d\n", sizeof(struct header), sizeof(struct obj)); { struct obj *sample; printf("offset(cls)=%d\n", OFFSET(hdr.cls, sample)); printf("offset(size)=%d\n", OFFSET(hdr.size, sample)); printf("offset(body)=%d\n", body_offset = OFFSET(body, sample)); } for( i=0; i < SZ; i++ ) items[i] = newObj( i, strs[i] ); for( i=0; i < SZ; i++ ){ printobj( items[i] ); free( items[i] ); items[i] = NULL; } return 0; }
Напишите программу, реализующую список со "старением". Элемент списка, к которому обращались последним, находится в голове списка. Самый старый элемент вытесняется к хвосту списка и в конечном счете из списка удаляется. Такой алгоритм использует ядро UNIX для кэширования блоков файла в оперативной памяти: блоки, к которым часто бывают обращения оседают в памяти (а не на диске).
/* Список строк, упорядоченных по времени их добавления в список, * т.е. самая "свежая" строка - в начале, самая "древняя" - в конце. * Строки при поступлении могут и повторяться! По подобному принципу * можно организовать буферизацию блоков при обмене с диском. */ #include <stdio.h>
extern char *malloc(), *gets(); #define MAX 3 /* максимальная длина списка */ int nelems = 0; /* текущая длина списка */ struct elem { /* СТРУКТУРА ЭЛЕМЕНТА СПИСКА */ char *key; /* Для блоков - это целое - номер блока */ struct elem *next; /* следующий элемент списка */ /* ... и может что-то еще ... */ } *head; /* голова списка */ void printList(), addList(char *), forget(); void main(){ /* Введите a b c d b a c */ char buf[128]; while(gets(buf)) addList(buf), printList(); } /* Распечатка списка */ void printList(){ register struct elem *ptr; printf( "В списке %d элементов\n", nelems ); for(ptr = head; ptr != NULL; ptr = ptr->next ) printf( "\t\"%s\"\n", ptr->key ); } /* Добавление в начало списка */ void addList(char *s) { register struct elem *p, *new; /* Анализ - нет ли уже в списке */ for(p = head; p != NULL; p = p->next ) if( !strcmp(s, p->key)){ /* Есть. Перенести в начало списка */ if( head == p ) return; /* Уже в начале */ /* Удаляем из середины списка */ new = p; /* Удаляемый элемент */ for(p = head; p->next != new; p = p->next ); /* p указывает на предшественника new */ p->next = new->next; goto Insert; } /* Нет в списке */ if( nelems >= MAX ) forget(); /* Забыть старейший */ if((new = (struct elem *) malloc(sizeof(struct elem)))==NULL) goto bad; if((new->key = malloc(strlen(s) + 1)) == NULL) goto bad; strcpy(new->key, s); nelems++; Insert: new->next = head; head = new; return; bad: printf( "Нет памяти\n" ); exit(13); } /* Забыть хвост списка */ void forget(){ struct elem *prev = head, *tail; if( head == NULL ) return; /* Список пуст */ /* Единственный элемент ? */ if((tail = head->next) == NULL){ tail=head; head=NULL; goto Del; } for( ; tail->next != NULL; prev = tail, tail = tail->next ); prev->next = NULL; Del: free(tail->key); free(tail); nelems--; }
© Copyright А. Богатырев, 1992-95
Си в UNIX
| |
