\ =========men[1]==
\-->|name | *---|-----> "Гриша"
............
5.9. Составьте программу "справочник по таблице Менделеева", которая по названию
химического элемента выдавала бы его характеристики. Таблицу инициализируйте массивом
структур.
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. Что напечатает следующая программа? Нарисуйте расположение указателей по окон-
чании данной программы.
#include
struct lnk{
char c;
А. Богатырев, 1992-95 - 179 - Си в UNIX
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;
}
}
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;
}
А. Богатырев, 1992-95 - 180 - Си в UNIX
/* вставка после 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
А. Богатырев, 1992-95 - 181 - Си в UNIX
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. Напишите функции для работы с комплексными числами
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 );
}
5.14. Массивы в Си нельзя присваивать целиком, зато структуры - можно. Иногда
используют такой трюк: структуру из единственного поля-массива
typedef struct {
int ai[5];
} intarray5;
intarray5 a, b = { 1, 2, 3, 4, 5 };
и теперь законно
a = b;
Зато доступ к ячейкам массива выглядит теперь менее изящно:
А. Богатырев, 1992-95 - 182 - Си в UNIX
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 ) ...;
А. Богатырев, 1992-95 - 183 - Си в UNIX
Следует однако учесть, что машинный код для работы с битовыми полями более сложен и
занимает больше команд (т.е. медленнее и длиннее).
К битовым полям нельзя применить операцию взятия адреса "&", у них нет адресов и
смещений!
5.16. Пример на использование структур с полем переменного размера. Часть перемен-
ной длины может быть лишь одна и обязана быть последним полем структуры. Внимание:
это программистский трюк, использовать осторожно!
#include
#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;
