Online Documentation Server
 ПОИСК
ods.com.ua Web
 КАТЕГОРИИ
Home
Programming
Net technology
Unixes
Security
RFC, HOWTO
Web technology
Data bases
Other docs

 

 ПОДПИСКА

 О КОПИРАЙТАХ
Вся предоставленная на этом сервере информация собрана нами из разных источников. Если Вам кажется, что публикация каких-то документов нарушает чьи-либо авторские права, сообщите нам об этом.




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


With any suggestions or questions please feel free to contact us