7.35.

Составьте программу вывода строк файла в инверсном отображении, причем порядок символов в строках также следует инвертировать. Например,

    abcdef ... oklmn                   987654321
       .....            превращать в     .....
    123456789                          nmlko ... fedcba

Программа должна быть составлена двумя способами: при помощи обратного чтения файла и рекурсивным вызовом самой функции инвертирования. Указание: при обратном чтении надо читать файл большими кусками (блоками).

7.36.

Напишите программу, читающую файл построчно и размещающую строки в отсортированное двоичное дерево. По концу файла - распечатайте это дерево. Указание: используйте динамическую память и рекурсию.

    /* Двоичная сортировка строк при помощи дерева */
    #include <stdio.h>
    char buf[240];          /* буфер ввода */
    int lines;              /* номер строки файла */
    typedef struct node{
            struct _data{   /* ДАННЫЕ */
               char *key;   /* ключ  - строка  */
               int  line;   /* номер строки    */
            } data;
                            /* СЛУЖЕБНАЯ ИНФОРМАЦИЯ */
            struct node *l, /* левое поддерево */
                        *r; /* правое поддерево */
    } Node;
    Node *root = NULL;      /* корень дерева (ссылка на верхний узел) */
    /* Отведение памяти и инициализация нового узла */
    Node *newNode(s)
      char *s;              /* строка */
    {
            Node *tmp;
            extern char *malloc();    /* выделитель памяти */
            tmp = (Node *) malloc(sizeof(Node));
            if( tmp == NULL ){
                    fprintf( stderr, "Нет памяти.\n");
                    exit(1);
            }
            tmp -> l = tmp -> r = NULL;       /* нет поддеревьев */
            tmp -> data.line = lines;         /* номер строки файла */
            tmp -> data.key = malloc( strlen(s) + 1 );
                 /* +1  - под байт '\0' в конце строки */
            strcpy(tmp -> data.key, s);       /* копируем ключ в узел */
            return tmp;
    }
    int i; /* Вынесено в статическую память, чтобы при каждом
            * рекурсивном вызове не создавалась новая auto-переменная,
            * а использовалась одна и та же статическая */
    /* Рекурсивная печать дерева */
    void printtree(root, tree, level, c)
      Node *root;                     /* корень дерева */
      Node *tree;                     /* дерево        */
      int level;                      /* уровень       */
      char c;                         /* имя поддерева */
    {
            if( root == NULL ){ printf("Дерево пусто.\n"); return; }
            if( tree == NULL )  return;
            /* если есть - распечатать левое поддерево */
            printtree (root, tree -> l, level + 1, '/');  /* 'L' */
            /* распечатать ключ узла */
            for( i=0; i < level; i++ )
                    printf("  ");
            printf("%c%3d--\"%s\"\n",
                     c, tree-> data.line, tree -> data.key);
            /* если есть - распечатать правое поддерево */
            printtree(root, tree -> r, level + 1, '\\');  /* 'R' */
    }
    void prTree(tree) Node *tree;
    {
            printtree(tree, tree, 0, '*');
    }
    /* Добавить узел с ключом key в дерево tree  */
    void addnode(tree, key)
      Node **tree;  /* в какое дерево добавлять: адрес переменной,
                     * содержащей ссылку на корневой узел */
      char *key;    /* ключ узла */
    {
    #define TREE (*tree)
            if( TREE == NULL ){  /* дерево пока пусто */
                    TREE = newNode( key );
                    return;
            }
            /* иначе есть хоть один узел   */
            if  ( strcmp (key, TREE -> data.key) < 0 )
            {
                    /*  добавить в левое поддерево    */
                    if ( TREE -> l == NULL ){
                            /* нет левого дерева  */
                            TREE -> l = newNode(key);
                            return;
                    }
                    else addnode( & TREE ->l , key);
            }
            else{
                    /* добавить в правое дерево  */
                    if ( TREE -> r == NULL ){
                            /* нет правого поддерева */
                            TREE -> r = newNode(key);
                            return;
                    }
                    else addnode ( & TREE ->r, key) ;
            }
    }
    /* Процедура удаления из дерева по ключу. */
    typedef struct node *NodePtr;
    static NodePtr delNode;    /* удаляемая вершина */
    void delete(key, tree)
      char *key;          /* ключ удаляемого элемента */
      NodePtr *tree;      /* из какого дерева удалять */
    {
         extern void doDelete();
         if(*tree == NULL){
              printf( "%s не найдено\n", key ); return;
         }
         /* поиск ключа */
         else if(strcmp(key, (*tree)->data.key) < 0)
              delete( key, &(*tree)->l );
         else if(strcmp(key, (*tree)->data.key) > 0)
              delete( key, &(*tree)->r );
         else{  /* ключ найден */
              delNode = *tree;  /* указатель на удаляемый узел */
              if(delNode->r == NULL)      *tree = delNode->l;
              else if(delNode->l == NULL) *tree = delNode->r;
              else doDelete( & delNode->l );
              free(delNode);
         }
    }
    static void doDelete(rt) NodePtr *rt;
    {
            if( (*rt)->r != NULL )    /* спуск по правой ветви */
                doDelete( &(*rt)->r );
            else{
                /* перенос данных в другой узел */
                delNode->data = (*rt)->data;
                delNode = *rt;         /* для free() */
                *rt = (*rt)->l;
            }
    }
    void main(){
            extern char *gets(); char *s;
            while (gets(buf) != NULL){      /* пока не конец файла */
                    lines++;
                    addnode( & root, buf );
            }
            prTree(root);
            /* удалим строку */
            freopen("/dev/tty", "r", stdin);
            do{
                printf( "что удалить ? " );
                if((s = gets(buf)) == NULL) break;
                delete(buf, &root);
                prTree( root );
            } while( s && root );
            printf("Bye-bye.\n");
            exit(0);
    }

7.37.

Напишите программу, которая читает со стандартного ввода 10 чисел либо слов, а затем распечатывает их. Для хранения введенных данных используйте объединение.

    #include <stdio.h>
    #include <ctype.h>
    #define INT 'i'
    #define STR 's'
    struct data {
      char tag;  /* тэг, пометка. Код типа данных. */
      union {
            int i;
            char *s;
      } value;
    } a[10];
    int counter = 0; /* счетчик */
    void main(){
      char word[128]; int i; char *malloc(unsigned);
      /* Чтение: */
      for(counter=0; counter < 10; counter++){
        if( gets(word) == NULL ) break;
        if( isdigit((unsigned char) *word)){
            a[counter].value.i = atoi(word);
            a[counter].tag     = INT;
        } else {
            a[counter].value.s = malloc(strlen(word)+1);
            strcpy(a[counter].value.s, word);
            a[counter].tag     = STR;
        }
      }
      /* Распечатка: */
      for(i=0; i < counter; i++)
        switch(a[i].tag){
        case INT: printf("число %d\n", a[i].value.i);
                  break;
        case STR: printf("слово %s\n", a[i].value.s);
                  free(a[i].value.s);
                  break;
       }
    }

7.38.

Рассмотрим задачу написания функции, которая обрабатывает переменное число аргументов, например функцию-генератор меню. В такую функцию надо подавать строки меню и адреса функций, вызываемых при выборе каждой из строк. Собственно проблема, которую мы тут обсуждаем - как передавать переменное число аргументов в подобные функции? Мы приведем три программы использующие три различных подхода. Предпочтение не отдано ни одному из них - каждый из них может оказаться эффективнее других в определенных ситуациях. Думайте сами!

7.38.1. Массив

    /* Передача аргументов в функцию как МАССИВА.
     * Следует явно указать число аргументов в массиве.
     */
    #include <stdio.h>              /* printf(), NULL */
    #include <string.h>             /* strdup() */
    #include <stdlib.h>             /* malloc() */
    #define A_INT           1
    #define A_STR           2
    #define A_NULL          0
    typedef struct arg {
            int type;
            union jack {
                    char *s;
                    int   d;
            } data;
            struct arg *next;
    } Arg;
    void doit(Arg args[], int n){
            int i;
            for(i=0; i < n; i++)
                    switch(args[i].type){
                    case A_INT:
                            printf("%d", args[i].data.d);
                            break;
                    case A_STR:
                            printf("%s", args[i].data.s);
                            break;
                    default:
                            fprintf(stderr, "Unknown type!\n");
                            break;
                    }
    }
    /* При инициализации union надо использовать тип
     * первого из перечисленных значений.
     */
    Arg sample[] = {
            { A_INT, (char *) 123 },
            { A_STR, (char *) " hello, " },
            { A_INT, (char *) 456 },
            { A_STR, (char *) " world\n" }
    };
    int main(int ac, char *av[]){
            doit(sample, sizeof sample / sizeof sample[0]);
            return 0;
    }

7.38.2. Список

    /* Передача аргументов в функцию как СПИСКА.
     * Достоинство: список можно модифицировать
     * во время выполнения программы: добавлять и
     * удалять элементы. Недостаток тот же: список надо
     * построить динамически во время выполнения,
     * заранее этого сделать нельзя.
     * Недостатком данной программы является также то,
     * что список не уничтожается после использования.
     * В C++ эта проблема решается при помощи использования
     * автоматически вызываемых деструкторов.
     */
    #include <stdio.h>              /* printf(), NULL */
    #include <string.h>             /* strdup() */
    #include <stdlib.h>             /* malloc() */
    #define A_INT           1
    #define A_STR           2
    #define A_NULL          0
    typedef struct arg {
            int type;
            union jack {
                    char *s;
                    int   d;
            } data;
            struct arg *next;
    } Arg;
    void doit(Arg *arglist){
            for( ; arglist; arglist=arglist->next)
                    switch(arglist->type){
                    case A_INT:
                            printf("%d", arglist->data.d);
                            break;
                    case A_STR:
                            printf("%s", arglist->data.s);
                            break;
                    default:
                            fprintf(stderr, "Unknown type!\n");
                            break;
                    }
    }
    Arg *new_int(int n, Arg *next){
            Arg *ptr = (Arg *) malloc(sizeof(Arg));
            ptr->type   = A_INT;
            ptr->data.d = n;
            ptr->next   = next;
            return ptr;
    }
    Arg *new_str(char *s, Arg *next){
            Arg *ptr = (Arg *) malloc(sizeof(Arg));
            ptr->type   = A_STR;
            ptr->data.s = strdup(s);
            ptr->next   = next;
            return ptr;
    }
    int main(int ac, char *av[]){
            doit(
                    new_int(123,
                    new_str(" hello, ",
                    new_int(456,
                    new_str(" world\n",
                            NULL))))
            );
            return 0;
    }

7.38.3. Функция с переменным числом параметров

    /* Передача аргументов в функцию как СПИСКА АРГУМЕНТОВ
     * ФУНКЦИИ с признаком конца списка.
     */
    #include <stdio.h>              /* printf(), NULL */
    #include <stdarg.h>             /* va_...   */
    #define A_INT           1
    #define A_STR           2
    #define A_NULL          0
    void doit(...){         /* переменное число аргументов */
            va_list args;
            /* второй параметр - аргумент, предшествующий ...
             * Если такого нет - ставим запятую и пустое место!
             */
            va_start(args, );
            for(;;){
                    switch(va_arg(args, int)){
                    case A_INT:
                            printf("%d", va_arg(args, int));
                            break;
                    case A_STR:
                            printf("%s", va_arg(args, char *));
                            break;
                    case A_NULL:
                            goto breakloop;
                    default:
                            fprintf(stderr, "Unknown type!\n");
                            break;
                    }
            }
    breakloop:
            va_end(args);
    }
    int main(int ac, char *av[]){
            doit(
                    A_INT, 123,
                    A_STR, " hello, ",
                    A_INT, 456,
                    A_STR, " world\n",
                    A_NULL
            );
            return 0;
    }

7.39.

Напишите несколько функций для работы с упрощенной базой данных. Запись в базе данных содержит ключ - целое, и строку фиксированной длины:

    struct data {
           int  b_key;             /* ключ */
           char b_data[ DATALEN ]; /* информация */
    };

Напишите:

• добавление записи
• уничтожение по ключу
• поиск по ключу (и печать строки)
• обновление по ключу.

Файл организован как несортированный массив записей без дубликатов (т.е. ключи не могут повторяться). Поиск производить линейно. Используйте функции fread, fwrite, fseek. Последняя функция позволяет вам позиционироваться к n-ой записи файла:

    fseek( fp, (long) n * sizeof(struct data), 0 );

Перепишите эту программу, объявив ключ как строку, например

    char b_key[ KEYLEN ];

Если строка-ключ короче KEYLEN символов, она должна оканчиваться '\0', иначе используются все KEYLEN букв и '\0' на конце отсутствует (так же устроено поле d_name в каталогах файловой системы). Усовершенствуйте алгоритм доступа, используя хеширование по ключу (hash - перемешивание, см. пример в приложении). Вынесите ключи в отдельный файл. Этот файл ключей состоит из структур

    struct record_header {
      int  b_key   ;    /* ключ */
      long b_offset;    /* адрес записи в файле данных */
      int  b_length;    /* длина записи (необязательно) */
    };

то есть организован аналогично нашей первой базе данных. Сначала вы ищете нужный ключ в файле ключей. Поле b_offset у найденного ключа задает адрес данного в другом файле. Чтобы прочитать его, надо сделать fseek на расстояние b_offset в файле данных и прочесть b_length байт.

7.40.

Организуйте базу данных в файле как список записей. В каждой записи вместо ключа должен храниться номер очередной записи (ссылка). Напишите функции: поиска данных в списке (по значению), добавления данных в список в алфавитном порядке, (они просто приписываются к концу файла, но в нужных местах переставляются ссылки), распечатки списка в порядке ссылок, удалению элементов из списка (из самого файла они не удаляются!). Ссылка (номер) первой записи (головы списка) хранится в первых двух байтах файла, рассматриваемых как short.

Введите оптимизацию: напишите функцию для сортировки файла (превращению перемешанного списка в линейный) и вычеркивания из него удаленных записей. При этом файл будет перезаписан. Если файл отсортирован, то поиск в нем можно производить более эффективно, чем прослеживание цепочки ссылок: просто линейным просмотром. Третий байт файла используйте как признак: 1 - файл был отсортирован, 0 - после сортировки в него было что-то добавлено и линейный порядок нарушен.

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