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

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


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

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

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

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

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

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

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




    Напишите программу, печатающую тексты Си-программ на принтере. Выделяйте ключевые слова языка жирным шрифтом, строки "строка", символы 'c' и комментарии - курсивом. Шрифты для EPSON-FX совместимых принтеров (например EP-2424) переключаются такими управляющими последовательностями (ESC означает символ '\033'):

    ВКЛЮЧЕНИЕ ВЫКЛЮЧЕНИЕ жирный шрифт (bold) ESC G ESC H

    утолщенный шрифт (emphasized) ESC E ESC F

    курсив (italics) ESC 4 ESC 5

    подчеркивание (underline) ESC - 1 ESC - 0

    повышенное качество печати ESC x 1 ESC x 0

    (near letter quality) nlq draft

    верхние индексы (superscript) ESC S 0 ESC T

    нижние индексы (subscript) ESC S 1 ESC T

    сжатый шрифт (17 букв/дюйм) '\017' '\022'

    (condensed) двойная ширина букв ESC W 1 ESC W 0

    (expanded) пропорциональная печать ESC p 1 ESC p 0

    (proportional spacing)

    Можно включить одновременно несколько из перечисленных выше режимов. В каждой из следующих двух групп надо выбрать одно из трех:

    pitch (плотность печати) pica (10 букв/дюйм) ESC P

    elite (12 букв/дюйм) ESC M

    micron (15 букв/дюйм) ESC g

    font (шрифт) черновик (draft (Roman)) ESC k '\0'

    текст (text (Sans Serif)) ESC k '\1'

    курьер (courier) ESC k '\2'

    Всюду выше 0 означает либо '0' либо '\0'; 1 означает либо '1' либо '\1'. Пример:

    printf( "This is \033Gboldface\033H word\n");

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

    Напишите программу печати текста в две колонки. Используйте буфер для формирования листа: файл читается построчно (слишком длинные строки обрубать), сначала заполняется левая половина листа (буфера), затем правая. Когда лист полностью заполнен или файл кончился - выдать лист построчно, расписать буфер пробелами (очистить лист) и повторить заполнение очередного листа. Указание: размеры листа должны передаваться как аргументы main(), для буфера используйте двумерный массив букв, память для него заказывайте динамически. Усложнение: не обрубайте, а переносите слишком длинные строки (строка может потребовать даже переноса с листа на лист).




    Разработайте архитектуру и систему команд учебной машины и напишите интерпретатор учебного ассемблера, отрабатывающего по крайней мере такие команды:

    mov пересылка (:=) add сложение sub вычитание cmp сравнение и выработка признака jmp переход jeq переход, если == jlt переход, если < jle переход, если <= neg изменение знака not инвертирование признака

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

    f(x, y, s, v) int x; char *s; struct elem *v; { ... }

    преобразуется в

    int f(int x, int y, char *s, struct elem *v) { ... }

    (обратите внимание, что переменная y и сама функция f описаны по умолчанию как int).

    Еще пример:

    char *ff() { ... } заменяется на char *ff(void){ ... }

    В данной задаче вам возможно придется использовать программу lex.

    В списке аргументов прототипа должны быть явно указаны типы всех аргументов описатель int нельзя опускать. Так

    q(x, s) char *s; { ... } // не прототип, допустимо. // x - int по умолчанию. q(x, char *s); // недопустимо. q(int x, char *s); // верно.

    Собственно под "прототипом" понимают предварительное описание функции в новом стиле где вместо тела {...} сразу после заголовка стоит точка с запятой.

    long f(long x, long y); /* прототип */ long f(long x, long y){ return x+y; } /* реализация */

    В прототипе имена аргументов можно опускать:

    long f(long, long); /* прототип */ char *strchr(char *, char);

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

    extern long f();

    о которых мы говорили раньше. Прототипы предоставляют программисту механизм для автоматического контроля формата вызова функции. Так, если функция имеет прототип

    double f( double );

    и вызывается как

    double x = f( 12 );

    то компилятор автоматически превратит это в

    double x = f( (double) 12 );

    (поскольку существует приведение типа от int к double); если же написано

    f( "привет" );




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



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



    Напишите программу копирования ввода на вывод таким образом, чтобы из каждой группы последовательно одинаковых строк выводилась только одна строка. Это аналог программы 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); /* последняя строка всегда выдается */ }



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



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

    /* заменять табуляции на пробелы */ 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); /* строку на старое место */ }



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

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



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



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



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



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



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



    Напишите программу, отсекающую 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); }





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



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



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



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

    /* Поиск в таблице методом половинного деления: 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; }



    Напишем функцию, которая преобразует строку так, что при ее печати буквы в ней будут подчеркнуты, а цифры - выделены жирно. Формат текста с выделениями, который создается этим примером, является общепринятым в 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()

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





    Напишите программу, удаляющую из файла выделения. Для этого надо просто удалять последовательности вида 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); }



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

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

    | |



    /* ПРОГРАММА ПЕЧАТИ В ДВЕ ПОЛОСЫ: pr.c */ #include <stdio.h>

    #include <string.h>

    #define YES 1 #define NO 0 #define FORMFEED '\f' #define LINEFEED '\n'

    extern char *malloc(unsigned); extern char *strchr(char *, char); void untab(register char *s); void resetsheet( void ); void addsheet( char *s, FILE *fpout ); void flushsheet( FILE *fpout ); void printline( int y, char *s, char *attr, FILE *fpout ); void doattr( register char *abuf, register char *vbuf ); void printcopy( FILE *fpin, FILE *fpout ); void main(void); char *strdup (const char *s){ char *p = malloc(strlen(s)+1); strcpy(p,s); return p;

    /* return strcpy((char *) malloc(strlen(s)+1), s); */ }

    /* ... текст функции untab() ... */

    int Sline; /* строка на листе */ int Shalf; /* половина листа */ int npage; /* номер страницы */ int startpage = 1; /* печать начиная с 1ой страницы */ int fline; /* номер строки файла */ int topline = 0; /* смещение до начала листа */ int halfwidth; /* ширина полулиста */ int twocolumns = YES; /* в две колонки ? */ int lshift, rshift = 1; /* поля слева и справа */ typedef unsigned short ushort; int COLS = 128; /* ширина листа (букв) */ int LINES = 66; /* длина листа (строк) */ ushort *mem; /* буфер листа */ #define AT(x,y) mem[ (x) + (y) * COLS ]

    /* Выделить буфер под лист и зачистить его */ void resetsheet ( void ){ register x; if( mem == NULL ){ /* выделить память */ if ((mem = (ushort *) malloc (COLS * LINES * sizeof(ushort))) == NULL ){ fprintf(stderr, "Out of memory.\n"); exit(1); } } /* очистить */ for( x= COLS * LINES - 1 ; x >= 0 ; x-- ) mem[x] = ' ' & 0xFF; halfwidth = (twocolumns ? COLS/2 : COLS ) - (lshift + rshift ); Sline = topline; Shalf = 0; }

    #define NEXT_HALF \ if( twocolumns == YES && Shalf == 0 ){ \ /* закрыть данную половину листа */ \ Shalf = 1; /* перейти к новой половине */ \ Sline = topline; \ } else \ flushsheet(fpout) /* напечатать лист */

    /* Записать строку в лист */ void addsheet ( char *s, FILE *fpout ) { register x, y; register i; char *rest = NULL; int wrap = NO; /* YES когда идет перенос слишком длинной строки */



    /* в какое место поместить строку? */ x = (Shalf == 0 ? 0 : COLS/2) + lshift; y = Sline;

    i = 0; /* позиция в строке s */ while (*s) { if( *s == '\f' ){ /* вынужденный form feed */ rest = strdup( s+1 ); /* остаток строки */ NEXT_HALF; if( *rest ) addsheet(rest, fpout); free( rest ); return; } if( i >= halfwidth ){ /* перенести длинную строку */ wrap = YES; rest = strdup(s); break; } /* Обработка выделений текста */ if( s[1] == '\b' ){ while( s[1] == '\b' ){ AT(x, y) = (s[0] << 8) | (s[2] & 0xFF); /* overstrike */ s += 2; } s++; x++; i++; } else { AT (x, y) = *s++ & 0xFF; x++; i++; } } /* Увеличить строку/половину_листа */ Sline++; if (Sline == LINES) { /* полулист заполнен */ NEXT_HALF; } if( wrap && rest ) { /* дописать остаток строки */ addsheet(rest, fpout); free(rest); } } int again; /* нужна ли повторная надпечатка? */ /* Напечатать заполненный лист */ void flushsheet ( FILE *fpout ){ register x, y, xlast; char *s, *p; static char outbuf[BUFSIZ], attr[BUFSIZ]; /* attr - буфер под атрибуты выделений */ ushort c;

    if( npage >= startpage ) for (y = 0; y < LINES; y++) { /* обрезать концевые пробелы */ for (xlast = (-1), x = COLS - 1; x >= 0; x--) if (AT (x, y) != ' ') { xlast = x; break; } again = NO; s = outbuf; p = attr; for (x = 0; x <= xlast; x++){ c = AT(x, y); *s++ = c & 0xFF;

    /* имеет атрибуты ? */ c >>= 8; c &= 0xFF; *p++ = c ? c : ' '; if( c ) again = YES; } *s = '\0'; *p = '\0'; printline(y, outbuf, attr, fpout); } npage++; /* next page */ resetsheet(); /* зачистить новый лист */ }

    /* Напечатать одну строку листа */ void printline ( int y, char *s, char *attr, FILE *fpout ){ register x; if( again ){ doattr(attr, s); fprintf(fpout, "%s\r", attr ); } fprintf(fpout, "%s", s); /* перевод листа или строки */ fputc( y == LINES-1 ? FORMFEED : LINEFEED, fpout ); }

    /* Проверить - нет ли атрибутов выделений */ void doattr ( register char *abuf, register char *vbuf ){ for(; *abuf; abuf++, vbuf++ ) if( !strchr(" _-!|\177", *abuf)) *abuf = *vbuf; } /* Копирование файла на принтер */ void printcopy ( FILE *fpin, FILE *fpout ) { char inbuf[BUFSIZ];


    Содержание раздела