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 <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;
}
}
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.Напишите функции для работы с комплексными числами
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;
Зато доступ к ячейкам массива выглядит теперь менее изящно:
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--;
}
[Назад][Содержание][Вперед] |