Структуры данных. Хрестоматия по программированию на Си в Unix

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

Назад | Содержание | Вперед