5.10.

При записи данных в файл (да и вообще) используйте структуры вместо массивов, если элементы массива имеют разное смысловое назначение. Не воспринимайте структуру просто как средство объединения данных разных типов, она может быть и средством объединения данных одного типа, если это добавляет осмысленности нашей программе. Чем плох фрагмент? 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);

5.11.

5.12.

Напишите программу, составлящую двунаправленный список букв, вводимых с клавиатуры. Конец ввода - буква '\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);

Память лучше отводить не из массива, а функцией 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; }

5.13.

5.14.

Массивы в Си нельзя присваивать целиком, зато структуры - можно. Иногда используют такой трюк: структуру из единственного поля-массива 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 изменяет исходный массив. Обойти это можно, использовав тот же трюк, поскольку при передаче структуры в качестве параметра передается уже не ее адрес, а копия всей структуры (как это и принято в Си во всех случаях, кроме массивов).

5.15.

Напоследок упомянем про битовые поля - элементы структуры, занимающие только часть машинного слова - только несколько битов в нем. Размер поля в битах задается конструкцией :число_битов. Битовые поля используются для более компактного хранения информации в структурах (для экономии места). 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 ) ...;

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

К битовым полям нельзя применить операцию взятия адреса "&", у них нет адресов и смещений!

5.16.

Пример на использование структур с полем переменного размера. Часть переменной длины может быть лишь одна и обязана быть последним полем структуры. Внимание: это программистский трюк, использовать осторожно! #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; }

5.17.

Напишите программу, реализующую список со "старением". Элемент списка, к которому обращались последним, находится в голове списка. Самый старый элемент вытесняется к хвосту списка и в конечном счете из списка удаляется. Такой алгоритм использует ядро 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