Текстовая обработка. Хрестоматия по программированию на Си в Unix

7. Текстовая обработка.

Под "текстовой обработкой" (в противовес "вычислительным задачам") здесь понимается огромный класс задач обработки информации нечислового характера, например редактирование текста, форматирование документов, поиск и сортировка, базы данных, лексический и синтаксический анализ, печать на принтере, преобразование формата таблиц, и.т.п.

7.1.

Напишите программу, "угадывающую" слово из заранее заданного списка по первым нескольким буквам. Выдайте сообщение "неоднозначно", если есть несколько похожих слов. Усложните программу так, чтобы список слов считывался в программу при ее запуске из файла list.txt

7.2.

Напишите программу, которая удваивает пробелы в тексте с одиночными пробелами.

7.3.

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

7.4.

Напишите программу подсчета слов в файле. Слово определите как последовательность символов, не включающую символы пробела, табуляции или новой строки. "Канонический" вариант решения, приведенный у Кернигана и Ритчи, таков:

    #include <ctype.h>
    #include <stdio.h>
    const int YES=1, NO=0;
    main(){
      register int inWord = NO; /* состояние */
      int words = 0, c;
      while((c = getchar()) != EOF)
        if(isspace(c) || c == '\n') inWord = NO;
        else if(inWord == NO){
             inWord = YES; ++words;
        }
      printf("%d слов\n", words);
    }

Обратите внимание на конструкцию const. Это объявление имен как констант. Эта конструкция близка к

     #define YES 1

но позволяет компилятору

более строго проверять тип, т.к. это типизированная константа;
создавать более экономный код;
запрещает изменять это значение.

Рассмотрим пример

    main(){  /* cc 00.c -o 00 -lm */
      double sqrt(double);
      const double sq12 = sqrt(12.0);
    #define        SQRT2  sqrt(2.0)
      double x;
      x = sq12 * sq12 * SQRT2 * SQRT2;    /* @1 */
      sq12 = 3.4641;                      /* @2 */
      printf("%g %g\n", sq12, x);
    }

Использование #define превратит строку @1 в

      x = sq12 * sq12 * sqrt(2.0) * sqrt(2.0);

то есть создаст код с двумя вызовами функции sqrt. Конструкция же const заносит вычисленное выражение в ячейку памяти и далее просто использует ее значение. При этом компилятор не позволяет впоследствии изменять это значение, поэтому строка @2 ошибочна.

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

    #include <ctype.h>
    #include <stdio.h>
    int wordLength, inWord, words; /* = 0 */
    char aWord[128], *wrd;

    void space  (c){}
    void letter (c){ wordLength++; *wrd++ = c; }
    void begWord(c){ wordLength=0; inWord=1;
         wrd=aWord;  words++; letter(c);       }
    void endWord(c){ inWord=0; *wrd = '\0';
            printf("Слово '%s' длины %d\n",
                           aWord,    wordLength); }
    void (*sw[2][2])() = {
    /* !isWord */ { space,   endWord },
    /*  isWord */ { begWord, letter  }
                /* !inWord   inWord  */
    };
    #define isWord(c) (isalnum(c) || c=='-' || c=='_')

    main(){ register c;
      while((c = getchar()) != EOF)
        (*sw[isWord(c)][inWord])(c);
      printf("%d слов\n", words);
    }

7.5.

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

7.6.

Напишите программу, которая считывает слово из файла in и записывает это слово в конец файла out.

7.7.

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

7.8.

Напишите программу, печатающую гистограмму длин слов из файла ввода.

7.9.

Напишите программу, читающую слова из файла и размещающую их в виде двунаправленного списка слов, отсортированного по алфавиту. Указания: используйте динамическую память (malloc) и указатели; напишите функцию включения нового слова в список на нужное место.

В конце работы распечатайте список дважды: в прямом и в обратном порядке.

Усложнение: не хранить в списке дубликаты; вместо этого вместе со словом хранить счетчик количества его вхождений в текст.

7.10.

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

7.11.

Напишите программу, читающую файл построчно и печатающую слова в каждой строке в обратном порядке.

7.12.

Напишите программу копирования ввода на вывод таким образом, чтобы из каждой группы последовательно одинаковых строк выводилась только одна строка. Это аналог программы uniq в системе UNIX. Ответ:

    #include <stdio.h>      /* char *gets(); */
    char buf1[4096], buf2[4096];
    char *this = buf1, *prev = buf2;
    main(){
      long nline =0L; char *tmp;
      while( gets(this)){
       if(nline){ /* сравнить новую и предыдущую строки */
           if( strcmp(this, prev)) /* различны ? */
               puts(prev);
       }
       /* обмен буферов: */ tmp=prev; prev=this; this=tmp;
       nline++;     /* номер строки */
      }/* endwhile */
      if( nline ) puts(prev);
      /* последняя строка всегда выдается */
    }

7.13.

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

7.14.

Для экономии места в файле, редакторы текстов при записи отредактированного файла сжимают подряд идущие пробелы в табуляцию. Часто это неудобно для программ обработки текстов (поскольку требует особой обработки табуляций - это ОДИН символ, который на экране и в тексте занимает НЕСКОЛЬКО позиций!), поэтому при чтении файла мы должны расширять табуляции в нужное количество пробелов, например так:

    /* заменять табуляции на пробелы */
    void untab(s) register char *s;
    {
      char newstr[256];  /* новая строка */
      char *src = s;
      int n;             /* счетчик      */
      register dstx;     /* координата x в новой строке */

      for(dstx = 0; *s != '\0'; s++)
          if( *s == '\t'){
              for(n = 8 - dstx % 8 ; n > 0 ; n--)
                  newstr[dstx++] = ' ';
          }else   newstr[dstx++] = *s;
      newstr[dstx] = '\0';
      strcpy(src, newstr); /* строку на старое место */
    }

7.15.

Напишите обратную функцию, сжимающую подряд идущие пробелы в табуляции.

    void tabify(){
       int chr;
       int icol, ocol;         /* input/output columns */

       for(icol = ocol = 0; ; ){

               if((chr = getchar()) == EOF)
                       break;

               switch(chr){

               case ' ':
                       icol++;
                       break;

               case '\n':
               case '\r':
                       ocol = icol = 0;
                       putchar(chr);
                       break;

               case '\t':
                       icol += 8;
                       icol &= ~07;    /* icol -= icol % 8; */
                       break;

               default:
                       while(((ocol + 8) & ~07) <= icol){

    #ifdef NOTDEF
                               if(ocol + 1 == icol)
                                       break;
                                       /* взять ' ' вместо '\t' */
    #endif
                               putchar('\t');
                               ocol += 8;
                               ocol &= ~07;
                       }
                       while(ocol < icol){
                               putchar(' ');
                               ocol++;
                       }
                       putchar(chr);
                       icol++;
                       ocol++;
                       break;
               }
       }
    }

7.16.

Составьте программу, укорачивающую строки исходного файла до заданной величины и помещающую результат в указанный файл. Учтите, что табуляция разворачивается в несколько пробелов!

7.17.

Разработайте программу, укорачивающую строки входного файла до 60 символов. Однако теперь запрещается обрубать слова.

7.18.

Разработайте программу, заполняющую промежутки между словами строки дополнительными пробелами таким образом, чтобы длина строки была равна 60 символам.

7.19.

Напишите программу, переносящую слишком длинные строки. Слова разбивать нельзя (неумешающееся слово следует перенести целиком). Ширину строки считать равной 60.

7.20.

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

7.21.

Напишите программу, отсекающую n пробелов в начале каждой строки (или n первых любых символов). Учтите, что в файле могут быть строки короче n (например пустые строки).

    #include <stdio.h>
    /* ... текст функции untab(); ... */
    void process(char name[], int n, int spacesOnly){
         char line[256]; int length, shift, nline = 0;
         char newname[128]; FILE *fpin, *fpout;
         if((fpin = fopen(name, "r")) == NULL){
             fprintf(stderr, "Не могу читать %s\n", name);
             return;
         }
         sprintf(newname, "_%s", name); /* например */
         if((fpout = fopen(newname, "w")) == NULL){
             fprintf(stderr, "Не могу создать %s\n",
                   newname); fclose(fpin); return;
         }
     while(fgets(line, sizeof line, fpin)){ ++nline;
       if((length = strlen(line)) &&
           line[length-1] == '\n')
           line[--length] =  '\0'; /* обрубить '\n' */
       untab(line); /* развернуть табуляции */
       for(shift=0; line[shift] != '\0' && shift < n ;
                                          ++shift)
           if(spacesOnly && line[shift] != ' ') break;
       if(*line && shift != n ) /* Предупреждение */
           fprintf(stderr,
             "Начало строки #%d слишком коротко\n", nline);
       fprintf(fpout, "%s\n", line+shift);
       /* нельзя было fputs(line+n, fpout);
        * т.к. эта позиция может быть ЗА концом строки
        */
     }
     fclose(fpin); fclose(fpout);
    }
    void main(int argc, char **argv){
         if( argc != 3 ) exit(1);
         process(argv[2], atoi(argv[1]) /* 8 */, 1);
         exit(0);
    }

7.22.

Напишите программу, разбивающую файл на два по вертикали: в первый файл попадает левая половина исходного файла, во второй - правая. Ширину колонки задавайте из аргументов main(). Если же аргумент не указан - 40 позиций.

7.23.

Напишите программу сортировки строк в алфавитном порядке. Учтите, что функция strcmp() сравнивает строки в порядке кодировки, принятой на данной конкретной машине. Русские буквы, как правило, идут не в алфавитном порядке! Следует написать функцию для алфавитного сравнения отдельных символов и, пользуясь ею, переписать функцию strcmp().

7.24.

Отсортируйте массив строк по лексикографическому убыванию, игнорируя различия между строчными и прописными буквами.

7.25.

Составьте программу дихотомического поиска в отсортированном массиве строк (методом деления пополам).

    /* Поиск в таблице методом половинного деления: dihotomia */
    #include <stdio.h>

    struct elem {
            char *name;     /* ключ поиска */
            int   value;
    } table[] = {
            /* имена строго по алфавиту */
            { "andrew",  17 },
            { "bill",    23 },
            { "george",  55 },
            { "jack",    54 },
            { "jaw",     43 },
            { "john",    33 },
            { "mike",    99 },
            { "paul",    21 },
            { "sue",     66 },   /* SIZE - 2 */

            { NULL,      -1 },   /* SIZE - 1 */
            /* NULL введен только для распечатки таблицы */
    };

    #define SIZE (sizeof(table) / sizeof(struct elem))

    /* Дихотомический поиск по таблице */
    struct elem *find(s, table, size)
            char *s;              /* что найти ? */
            struct elem table[];  /* в чем     ? */
            int size;             /* среди первых size элементов */
    {
            register top, bottom, middle;
            register code;

            top    = 0;          /* начало */
            bottom = size - 1;   /* конец:  индекс строки "sue" */

            while( top <= bottom ){
                    middle = (top + bottom) / 2;    /* середина */

                    /* сравнить строки */
                    code = strcmp( s, table[middle].name ) ;

                    if( code > 0 ){
                            top = middle + 1;
                    }else if( code < 0 ){
                            bottom = middle - 1;
                    }else return &table[ middle ];

            }
            return (struct elem *) NULL; /* не нашел */
    }

    /* распечатка таблицы */
    void printtable(tbl) register struct elem *tbl; {
            for( ; tbl->name != NULL ; tbl++ ){
                   printf( "%-15s %d\n", tbl->name, tbl->value );
            }
    }

    int main(){
            char buf[80];
            struct elem *ptr;

            printtable(table);
            for(;;){
                    printf( "-> " );
                    if( gets( buf ) == NULL) break; /* EOF */
                    if( ! strcmp( buf, "q" ))
                            exit(0);                /* quit: выход */
                    ptr = find( buf, table, SIZE-1 );
                    if( ptr )
                            printf( "%d\n", ptr->value );
                    else {
                            printf( "--- Не найдено ---\n" );
                            printtable(table);
                    }
            }
            return 0;
    }

7.26.

Напишем функцию, которая преобразует строку так, что при ее печати буквы в ней будут подчеркнуты, а цифры - выделены жирно. Формат текста с выделениями, который создается этим примером, является общепринятым в UNIX и распознается некоторыми программами: например, программа просмотра файлов less (more) выделяет такие буквы на экране специальными шрифтами или инверсией фона.

    #define LEN 9  /* потом напишите 256 */
    char input[] = "(xxx+yyy)/123.75=?";
    char output[LEN];
    void main( void ){
        int len=LEN, i; void bi_conv(); char c;
        bi_conv(input, output, &len);
        if(len > LEN){
           printf("Увеличь LEN до %d\n", len);
           len = LEN;  /* доступный максимум */
        }
        for(i=0; i < len && (c = output[i]); ++i)
            putchar(c);
        putchar('\n');
    }

    /* Заметьте, что include-файлы не обязательно
     * должны включаться в самом начале программы! */
    #include <stdio.h>
    #include <ctype.h>

    #define PUT(c) { count++;              \
        if(put < *len){ *p++ = (c); ++put;}}
    #define GET() (*s ? *s++ : EOF)

    void bi_conv(

            /*IN*/    char *s,
            /*OUT*/   char *p,
            /*INOUT*/ int *len ){
        int count, put, c;
        for(count=put=0; (c=GET()) != EOF; ){
        /* жирный:       C\bC    */
        /* подчеркнутый: _\bC    */
                 if(isalpha(c)){ PUT('_'); PUT('\b'); }
            else if(isdigit(c)){ PUT( c ); PUT('\b'); }
            PUT(c);
        }
        PUT('\0');  /* закрыть строку */
        *len = count;
    #undef PUT
    #undef GET
    }

Напишите программу для подобной обработки файла. Заметим, что для этого не нужны промежуточные строки input и output и построчное чтение файла; все, что надо сделать, это определить

    #define PUT(c) if(c)putchar(c)
    #define GET()  getchar()

Напишите подобную функцию, удваивающую буквы в ссттррооккее.

7.27.

Напишите программу, удаляющую из файла выделения. Для этого надо просто удалять последовательности вида C\b

    #include <stdio.h>
    #define NOPUT   (-1) /* не символ ASCII */
    /* Названия шрифтов - в перечислимом типе */
    typedef enum { NORMAL=1, ITALICS, BOLD, RED=BOLD } font;
    int ontty; font textfont; /* текущее выделение */
    #define setfont(f)      textfont=(f)
    #define getfont()       (textfont)
    #define SetTtyFont(f)   if(ontty) tfont(f)

    /* Установить выделение на экране терминала */
    void tfont(font f){ /* только для ANSI терминала */
      static font ttyfont = NORMAL;
      if(ttyfont == f) return;
      printf("\033[0m"); /* set NORMAL font */
      switch(ttyfont = f){
      case NORMAL:  /* уже сделано выше */ break;
      case BOLD:    printf("\033[1m");     break;
      case ITALICS: /* use reverse video */
                    printf("\033[7m");     break;
      }
    }
    void put(int c){ /* Вывод символа текущим цветом */
      if(c == NOPUT) return; /* '\b' */
      SetTtyFont(getfont()); putchar(c);
      setfont(NORMAL); /* Ожидать новой C\b посл-ти */
    }
    void
    main(){ register int c, cprev = NOPUT;
      /* Стандартный вывод - это терминал ? */
      ontty = isatty(fileno(stdout));
      setfont(NORMAL);
      while((c = getchar()) != EOF){

        if(c == '\b'){  /* выделение */
           if((c = getchar()) == EOF) break;
           if(c == cprev)            setfont(BOLD);
           else if(cprev == '_')     setfont(ITALICS);
           else /* наложение A\bB */ setfont(RED);
        } else put(cprev);
       cprev = c;
      }
      put(cprev); /* последняя буква файла */
      SetTtyFont(NORMAL);
    }

7.28.

Напишите программу печати на принтере листинга Си-программ. Ключевые слова языка выделяйте двойной надпечаткой. Для выдачи на терминал напишите программу, подчеркивающую ключевые слова (подчеркивание - в следующей строке). Упрощение: выделяйте не ключевые слова, а большие буквы. Указание: для двойной печати используйте управляющий символ '\r' - возврат к началу той же строки; затем строка печатается повторно, при этом символы, которые не должны печататься жирно, следует заменить на пробелы (или на табуляцию, если этот символ сам есть '\t').

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