HTML page

5.  Структуры данных.
     Структуры ("записи") представляют собой агрегаты разнородных данных (полей  раз-
ного типа); в отличие от массивов, где все элементы имеют один и тот же тип.

    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;
    };

Очень часто используются массивы структур:






А. Богатырев, 1992-95                  - 173 -                              Си в UNIX

    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 a[5], b[5];  a = b; /* ОШИБОЧНО ! */

Пример обращения к полям структуры:

    typedef struct _Point {
        short x, y; /* координаты точки */
        char *s;    /* метка точки      */
    } Point;
    Point p; Point *pptr; short *iptr;
    struct _Curve {
      Point points[25]; /* вершины ломанной */
      int color;        /* цвет линии       */
    } aLine[10], *linePtr = & aLine[0];
            ...
    pptr = &p; /* указатель на структуру p */
    p.x = 1; p.y = 2; p.s = "Grue";
    linePtr->points[2].x  = 54; aLine[5].points[0].y  = 17;


                   В ы р а ж е н и е                 значение
    ---------+------------+------------+-----------+-----------
    p.x      | pptr->x    | (*pptr).x  | (&p)->x   | 1
    ---------+------------+------------+-----------+-----------
                                          &p->x    | ошибка
    -----------+----------------+------------------+-----------
    iptr= &p.x | iptr= &pptr->x | iptr= &(pptr->x) | адрес поля
    -----------+----------------+--------+---------+-----------
    *pptr->s   | *(pptr->s)     | *p.s   |  p.s[0] | 'G'
    -----------+----------------+--------+---------+-----------
    pptr->s[1] | (&p)->s[1]     |  p.s[1]          | 'r'
    -----------+----------------+------------------+-----------
                  &p->s[1]                         | ошибка
    -----------+----------------+------------------+-----------
    (*pptr).s  | pptr->s        | p.s              | "Grue"
    -----------+----------------+------------------+-----------
    *pptr.s                                        | ошибка
    -----------------------------------------------+-----------





А. Богатырев, 1992-95                  - 174 -                              Си в UNIX

            Вообще (&p)->field   =  p.field
                   pptr->field   =  (*pptr).field

     Объединения - это агрегаты данных, которые могут хранить в себе значения  данных
разных типов на одном и том же месте.

            struct a{ int x, y; char *s; } A;
            union  b{ int i; char *s; struct a aa; } B;


            Структура:
       ________________________
    A: | A.x         int      |   Три поля
       ------------------------   расположены подряд.
       | A.y         int      |   Получается как бы
       ------------------------   "карточка" с графами.
       | A.s         char *   |
       ------------------------


    А у объединений поля расположены "параллельно",
    на одном месте в памяти.
       _______________________________________________________
    B: | B.i  int | B.s  char *  | B.aa     : B.aa.x  int    |
       -----------|              | struct a : B.aa.y  int    |
                  ---------------|          : B.aa.s  char * |
                                 |___________________________|

Это как бы "ящик" в который можно поместить значение любого типа из перечисленных, но
не  ВСЕ  ВМЕСТЕ ("и то и это", как у структур), а ПО ОЧЕРЕДИ ("или/или").  Размер его
достаточно велик, чтоб вместить самый большой из перечисленных типов данных.
     Мы можем занести в 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');
    }




А. Богатырев, 1992-95                  - 175 -                              Си в UNIX

или порядок слов в 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 );
    }


5.1.  Найдите ошибки в описании структурного шаблона:

            structure { int arr[12],
                        char string,
                        int *sum
                      }


5.2.  Разработайте структурный шаблон, который содержал бы название месяца,  трехбук-
венную  аббревиатуру месяца, количество дней в месяце и номер месяца. Инициализируйте
его для невисокосного года.

      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.



А. Богатырев, 1992-95                  - 176 -                              Си в UNIX

     Заметим, что для распечатки всех или нескольких  полей  структуры  следует  ЯВНО
перечислить  в printf() все нужные поля и указать форматы, соответствующие типам этих
полей. Не существует формата или стандартной  функции,  позволяющей  распечатать  все
поля сразу (однако такая функция может быть написана вами для конкретного типа струк-
тур).  Также не существует формата для scanf(), который вводил бы структуру  целиком.
Вводить можно только по частям - каждое поле отдельно.

5.3.  Напишите программу, которая по номеру месяца возвращает общее число  дней  года
вплоть до этого месяца.

5.4.  Переделайте предыдущую программу таким образом, чтобы она по  написанному  бук-
вами названию месяца возвращала общее число дней года вплоть до этого месяца. В прог-
рамме используйте функцию strcmp().

5.5.  Переделайте предыдущую программу таким образом, чтобы она запрашивала у пользо-
вателя  день,  месяц,  год  и выдавала общее количество дней в году вплоть до данного
дня. Месяц может обозначаться номером, названием месяца или его аббревиатурой.

5.6.  Составьте структуру для учетной картотеки служащего, которая содержала бы  сле-
дующие  сведения: фамилию, имя, отчество; год рождения; домашний адрес; место работы,
должность; зарплату; дату поступления на работу.

5.7.  Что печатает программа?

    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 И


5.8.  Разберите следующий пример:

    #include <stdio.h>
    struct man{



А. Богатырев, 1992-95                  - 177 -                              Си в UNIX

            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]);
    }

Обратите внимание на такие моменты:
1)   Как производится работа с указателем на указатель (ptrptr).
2)   При копировании структур отдельными полями, поля  скалярных  типов  (int,  char,
     long,  ..., указатели) копируются операцией присваивания (см. строки с пометками
     #1 и #3). Поля векторных типов (массивы) копируются  при  помощи  цикла,  поэле-
     ментно  пересылающего  массив  (строка  #4).  Строки (массивы букв) пересылаются
     стандартной функцией strcpy (строка #2). Все это относится  не  только  к  полям
     структур,  но и к переменным таких типов. Структуры можно также копировать не по
     полям, а целиком: men[0]= *ptr;
3)   Запись аргументов функции printf() лесенкой позволяет лучше видеть, какому  фор-
     мату соответствует каждый аргумент.
4)   При распечатке массива структур мы печатаем не определенное их количество  (рав-
     ное  размеру массива), а пользуемся указателем NULL в поле name последней струк-
     туры как признаком конца массива.
5)   В поле town мы храним строки из 3х букв, однако выделяем для хранения массив  из
     4х  байт. Это необходимо потому, что строка "Msc" состоит не из 3х, а из 4х бай-
     тов: 'M','s','c','\0'.
При работе со структурами и указателями большую помощь могут оказать рисунки. Вот как
(например) можно нарисовать данные из этого примера (массив men изображен не весь):






А. Богатырев, 1992-95                  - 178 -                              Си в UNIX

            --ptr--       --ptrptr--
        ptr |  *  |<------|---*    |
            ---|---       ----------
               |
              /    =========men[0]==
             / men:|name  |    *---|-----> "Вася"
             |     |---------------|
             |     |town  |M|s|c|\0|
             |     |---------------|
             |     |salary| 100    |
             |     |---------------|
             |     |addr  | 12 | 7 |
             \     -----------------
              \    =========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 <stdio.h>
    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 <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;
    }



А. Богатырев, 1992-95                  - 184 -                              Си в UNIX

    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();




А. Богатырев, 1992-95                  - 185 -                              Си в UNIX

    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--;
    }