Страница:
читать файл большими кусками (блоками).
7.36. Напишите программу, читающую файл построчно и размещающую строки в отсортиро-
ванное двоичное дерево. По концу файла - распечатайте это дерево. Указание: исполь-
зуйте динамическую память и рекурсию.
А. Богатырев, 1992-95 - 301 - Си в UNIX
/* Двоичная сортировка строк при помощи дерева */
#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-переменная,
* а использовалась одна и та же статическая */
А. Богатырев, 1992-95 - 302 - Си в UNIX
/* Рекурсивная печать дерева */
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);
}
А. Богатырев, 1992-95 - 303 - Си в UNIX
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;
}
}
А. Богатырев, 1992-95 - 304 - Си в UNIX
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;
}
А. Богатырев, 1992-95 - 305 - Си в UNIX
}
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;
}
}
А. Богатырев, 1992-95 - 306 - Си в UNIX
/* При инициализации 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;
А. Богатырев, 1992-95 - 307 - Си в UNIX
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
А. Богатырев, 1992-95 - 308 - Си в UNIX
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 );
Перепишите эту программу, объявив ключ как строку, например
А. Богатырев, 1992-95 - 309 - Си в UNIX
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 - после сортировки в
него было что-то добавлено и линейный порядок нарушен.
7.41. Напишите функцию match(строка,шаблон); для проверки соответствия строки упро-
щенному регулярному выражению в стиле Шелл. Метасимволы шаблона:
* - любое число любых символов (0 и более);
? - один любой символ.
Усложнение:
[буквы] - любая из перечисленных букв.
[!буквы] - любая из букв, кроме перечисленных.
[h-z] - любая из букв от h до z включительно.
Указание: для проверки "остатка" строки используйте рекурсивный вызов этой же функ-
ции.
Используя эту функцию, напишите программу, которая выделяет из файла СЛОВА,
удовлетворяющие заданному шаблону (например, "[Ии]*о*т"). Имеется в виду, что каждую
строку надо сначала разбить на слова, а потом проверить каждое слово.
А. Богатырев, 1992-95 - 310 - Си в UNIX
#include <stdio.h>
#include <string.h>
#include <locale.h>
#define U(c) ((c) & 0377) /* подавление расширения знака */
#define QUOT '\\' /* экранирующий символ */
#ifndef MATCH_ERR
# define MATCH_ERR printf("Нет ]\n")
#endif
/* s - сопоставляемая строка
* p - шаблон. Символ \ отменяет спецзначение метасимвола.
*/
int match (register char *s, register char *p)
{
register int scc; /* текущий символ строки */
int c, cc, lc; /* lc - предыдущий символ в [...] списке */
int ok, notflag;
for (;;) {
scc = U(*s++); /* очередной символ строки */
switch (c = U (*p++)) { /* очередной символ шаблона */
case QUOT: /* a*\*b */
c = U (*p++);
if( c == 0 ) return(0); /* ошибка: pattern\ */
else goto def;
case '[': /* любой символ из списка */
ok = notflag = 0;
lc = 077777; /* достаточно большое число */
if(*p == '!'){ notflag=1; p++; }
while (cc = U (*p++)) {
if (cc == ']') { /* конец перечисления */
if (ok)
break; /* сопоставилось */
return (0); /* не сопоставилось */
}
if (cc == '-') { /* интервал символов */
if (notflag){
/* не из диапазона - OK */
if (!syinsy (lc, scc, U (*p++)))
ok++;
/* из диапазона - неудача */
else return (0);
} else {
/* символ из диапазона - OK */
if (syinsy (lc, scc, U (*p++)))
ok++;
}
}
else {
if (cc == QUOT){ /* [\[\]] */
cc = U(*p++);
if(!cc) return(0);/* ошибка */
}
if (notflag){
if (scc && scc != (lc = cc))
ok++; /* не входит в список */
else return (0);
} else {
А. Богатырев, 1992-95 - 311 - Си в UNIX
if (scc == (lc = cc)) /* входит в список */
ok++;
}
}
}
if (cc == 0){ /* конец строки */
MATCH_ERR;
return (0); /* ошибка */
}
continue;
case '*': /* любое число любых символов */
if (!*p)
return (1);
for (s--; *s; s++)
if (match (s, p))
return (1);
return (0);
case 0:
return (scc == 0);
default: def:
if (c != scc)
return (0);
continue;
case '?': /* один любой символ */
if (scc == 0)
return (0);
continue;
}
}
}
/* Проверить, что smy лежит между smax и smin
*/
int syinsy (unsigned smin, unsigned smy, unsigned smax)
{
char left [2];
char right [2];
char middle [2];
left [0] = smin; left [1] = '\0';
right [0] = smax; right [1] = '\0';
middle[0] = smy; middle[1] = '\0';
return (strcoll(left, middle) <= 0 && strcoll(middle, right) <= 0);
}
Обратите внимание на то, что в UNIX расширением шаблонов имен файлов, вроде *.c,
занимается не операционная система (как в MS DOS), а программа-интерпретатор команд
пользователя (shell: /bin/sh, /bin/csh, /bin/ksh). Это позволяет обрабатывать (в
принципе) разные стили шаблонов имен.
7.42. Изучите раздел руководства man regexp и include-файл /usr/include/regexp.h,
содержащий исходные тексты функций compile и step для регулярного выражения в стиле
программ ed, lex, grep:
одна буква C
или заэкранированный спецсимвол \. \[ \* \$ \^ \\ означают сами себя;
А. Богатырев, 1992-95 - 312 - Си в UNIX
. означает один любой символ кроме \n;
[abc]
или [a-b] означает любой символ из перечисленных (из интервала);
[abc-]
минус в конце означает сам символ -;
[]abc]
внутри [] скобка ] на первом месте означает сама себя;
[^a-z]
крышка ^ означает отрицание, т.е. любой символ кроме перечисленных;
[a-z^]
крышка не на первом месте означает сама себя;
[\*.]
спецсимволы внутри [] не несут специального значения, а представляют сами себя;
C* любое (0 и более) число символов C;
.* любое число любых символов;
выражение*
любое число (0 и более) повторений выражения, например [0-9]* означает число
(последовательность цифр) или пустое место. Ищется самое длинное прижатое влево
подвыражение;
выражение\{n,m\}
повторение выражения от n до m раз (включительно), где числа не превосходят 255;
выражение\{n,\}
повторение по крайней мере n раз, например [0-9]\{1,\} означает число;
выражение\{n\}
повторение ровно n раз;
выражение$
строка, чей конец удовлетворяет выражению, например .*define.*\\$
^выражение
строка, чье начало удовлетворяет выражению;
\n символ перевода строки;
\(.....\)
сегмент. Сопоставившаяся с ним подстрока будет запомнена;
\N где N цифра. Данный участок образца должен совпадать с N-ым сегментом (нумерация
с 1).
Напишите функцию matchReg, использующую этот стиль регулярных выражений. Сохраняйте
шаблон, при вызове matchReg сравнивайте старый шаблон с новым. Перекомпиляцию следует
производить только если шаблон изменился:
#include <stdio.h>
#include <ctype.h>
#define INIT register char *sp = instring;
#define GETC() (*sp++)
#define PEEKC() (*sp)
#define UNGETC(c) (--sp)
#define RETURN(ptr) return
#define ERROR(code) \
{fprintf(stderr,"%s:ERR%d\n",instring,code);exit(177);}
# include <regexp.h>
#define EOL '\0' /* end of line */
#define ESIZE 512
int matchReg(char *str, char *pattern){
static char oldPattern[256];
static char compiledExpr[ESIZE];
if( strcmp(pattern, oldPattern)){ /* различны */
/* compile regular expression */
compile(pattern,
compiledExpr, &compiledExpr[ESIZE], EOL);
А. Богатырев, 1992-95 - 313 - Си в UNIX
strcpy(oldPattern, pattern); /* запомнить */
}
return step(str, compiledExpr); /* сопоставить */
}
/* Пример вызова: reg '^int' 'int$' char | less */
/* reg 'putchar.*(.*)' < reg.c | more */
void main(int ac, char **av){
char inputline[BUFSIZ]; register i;
while(gets(inputline)){
for(i=1; i < ac; i++)
if(matchReg(inputline, av[i])){
char *p; extern char *loc1, *loc2;
/*printf("%s\n", inputline);*/
/* Напечатать строку,
* выделяя сопоставившуюся часть жирно */
for(p=inputline; p != loc1; p++) putchar(*p);
for( ; p != loc2; p++)
if(isspace((unsigned char) *p))
putchar(*p);
else printf("%c\b%c", *p, *p);
for( ; *p; p++) putchar(*p);
putchar('\n');
break;
}
}
}
7.43. Используя <regexp.h> напишите программу, производящую контекстную замену во
всех строках файла. Если строка не удовлетворяет регулярному выражению - она остается
неизменной. Примеры вызова:
$ regsub '\([0-9]\{1,\}\)' '(\1)'
$ regsub 'f(\(.*\),\(.*\))' 'f(\2,\1)' < file
Вторая команда должна заменять все вхождения f(a,b) на f(b,a). Выражение, обозначен-
ное в образце как \(...\), подставляется на место соответствующей конструкции \N во
втором аргументе, где N - цифра, номер сегмента. Чтобы поместить в выход сам символ
\, его надо удваивать: \\.
А. Богатырев, 1992-95 - 314 - Си в UNIX
/* Контекстная замена */
#include <stdio.h>
#include <ctype.h>
#define INIT register char *sp = instring;
#define GETC() (*sp++)
#define PEEKC() (*sp)
#define UNGETC(c) (--sp)
#define RETURN(ptr) return
#define ERROR(code) regerr(code)
void regerr();
# include <regexp.h>
#define EOL '\0' /* end of line */
#define ESIZE 512
short all = 0;
/* ключ -a означает, что в строке надо заменить ВСЕ вхождения образца (global, all):
* regsub -a int INT
* "aa int bbb int cccc" -> "aa INT bbb INT cccc"
*
* step() находит САМУЮ ДЛИННУЮ подстроку, удовлетворяющую выражению,
* поэтому regsub 'f(\(.*\),\(.*\))' 'f(\2,\1)'
* заменит "aa f(1,2) bb f(3,4) cc" -> "aa f(4,1,2) bb f(3) cc'
* |___________|_| |_|___________|
*/
char compiled[ESIZE], line[512];
А. Богатырев, 1992-95 - 315 - Си в UNIX
void main(int ac, char *av[]){
register char *s, *p; register n; extern int nbra;
extern char *braslist[], *braelist[], *loc1, *loc2;
if( ac > 1 && !strcmp(av[1], "-a")){ ac--; av++; all++; }
if(ac != 3){
fprintf(stderr, "Usage: %s [-a] pattern subst\n", av[0]);
exit(1);
}
compile(av[1], compiled, compiled + sizeof compiled, EOL);
while( gets(line) != NULL ){
if( !step(s = line, compiled)){
printf("%s\n", line); continue;
}
do{
/* Печатаем начало строки */
for( ; s != loc1; s++) putchar(*s);
/* Делаем замену */
for(s=av[2]; *s; s++)
if(*s == '\\'){
if(isdigit(s[1])){ /* сегмент */
int num = *++s - '1';
if(num < 0 || num >= nbra){
fprintf(stderr, "Bad block number %d\n", num+1);
exit(2);
}
for(p=braslist[num]; p != braelist[num]; ++p)
putchar(*p);
} else if(s[1] == '&'){
++s; /* вся сопоставленная строка */
for(p=loc1; p != loc2; ++p)
putchar(*p);
} else putchar(*++s);
} else putchar(*s);
} while(all && step(s = loc2, compiled));
/* Остаток строки */
for(s=loc2; *s; s++) putchar(*s);
putchar('\n');
} /* endwhile */
}
А. Богатырев, 1992-95 - 316 - Си в UNIX
void regerr(int code){ char *msg;
switch(code){
case 11: msg = "Range endpoint too large."; break;
case 16: msg = "Bad number."; break;
case 25: msg = "\\digit out of range."; break;
case 36: msg = "Illegal or missing delimiter."; break;
case 41: msg = "No remembered search string."; break;
case 42: msg = "\\(~\\) imbalance."; break;
case 43: msg = "Too many \\(."; break;
case 44: msg = "More than 2 numbers given in \\{~\\\"}."; break;
case 45: msg = "} expected after \\."; break;
case 46: msg = "First number exceeds second in \\{~\\}."; break;
case 49: msg = "[ ] imbalance."; break;
case 50: msg = "Regular expression overflow."; break;
default: msg = "Unknown error"; break;
} fputs(msg, stderr); fputc('\n', stderr); exit(code);
}
void prfields(){
int i;
for(i=0; i < nbra; i++)
prfield(i);
}
void prfield(int n){
char *fbeg = braslist[n], *fend = braelist[n];
printf("\\%d='", n+1);
for(; fbeg != fend; fbeg++)
putchar(*fbeg);
printf("'\n");
}
7.44. Составьте функцию поиска подстроки в строке. Используя ее, напишите программу
поиска подстроки в текстовом файле. Программа должна выводить строки (либо номера
строк) файла, в которых встретилась данная подстрока. Подстрока задается в качестве
аргумента функции main().
/* Алгоритм быстрого поиска подстроки.
* Дж. Мур, Р. Бойер, 1976 Texas
* Смотри: Communications of the ACM 20, 10 (Oct., 1977), 762-772
*
* Этот алгоритм выгоден при многократном поиске образца в
* большом количестве строк, причем если они равной длины -
* можно сэкономить еще и на операции strlen(str).
* Алгоритм характерен тем, что при неудаче производит сдвиг не на
* один, а сразу на несколько символов вправо.
* В лучшем случае алгоритм делает slen/plen сравнений.
*/
char *pattern; /* образец (что искать) */
static int plen; /* длина образца */
static int d[256]; /* таблица сдвигов; в алфавите ASCII -
* 256 букв. */
/* расстояние от конца образца до позиции i в нем */
#define DISTANCE(i) ((plen-1) - (i))
А. Богатырев, 1992-95 - 317 - Си в UNIX
/* Поиск:
* выдать индекс вхождения pattern в str,
* либо -1, если не входит
*/
int indexBM( str ) char *str; /* в чем искать */
{
int slen = strlen(str); /* длина строки */
register int pindx; /* индекс сравниваемой буквы в образце */
register int cmppos; /* индекс сравниваемой буквы в строке */
register int endpos; /* позиция в строке, к которой "приставляется"
* последняя буква образца */
/* пока образец помещается в остаток строки */
for( endpos = plen-1; endpos < slen ; ){
/* Для отладки: pr(str, pattern, endpos - (plen-1), 0); /**/
/* просмотр образца от конца к началу */
for( cmppos = endpos, pindx = (plen - 1);
pindx >= 0 ;
cmppos--, pindx-- )
if( str[cmppos] != pattern[pindx] ){
/* Сдвиг, который ставит самый правый в образце
* символ str[endpos] как раз под endpos-тую
* позицию строки. Если же такой символ в образце не
* содержится (или содержится только на конце),
* то начало образца устанавливается в endpos+1 ую
* позицию
*/
endpos += d[ str[endpos] & 0377 ];
break; /* & 0377 подавляет расширение знака. Еще */
} /* можно сделать все char -> unsigned char */
if( pindx < 0 ) return ( endpos - (plen-1));
/* Нашел: весь образец вложился */
}
return( -1 ); /* Не найдено */
}
А. Богатырев, 1992-95 - 318 - Си в UNIX
/* Разметка таблицы сдвигов */
void compilePatternBM( ptrn ) char *ptrn; {
register int c;
pattern = ptrn; plen = strlen(ptrn);
/* c - номер буквы алфавита */
for(c = 0; c < 256; c++)
d[c] = plen;
/* сдвиг на длину всего образца */
/* c - позиция в образце */
for(c = 0; c < plen - 1; c++)
d[ pattern[c] & 0377 ] = DISTANCE(c);
/* Сдвиг равен расстоянию от самого правого
* (кроме последней буквы образца)
* вхождения буквы в образец до конца образца.
* Заметим, что если буква входит в образец несколько раз,
* то цикл учитывает последнее (самое правое) вхождение.
*/
}
/* Печать найденных строк */
void pr(s, p, n, nl) char *s, *p;
{
register i;
printf("%4d\t%s\n", nl, s );
printf(" \t");
for(i = 0; i < n; i++ )
putchar( s[i] == '\t' ? '\t' : ' ' );
printf( "%s\n", p );
}
/* Аналог программы fgrep */
#include <stdio.h>
char str[ 1024 ]; /* буфер для прочитанной строки */
void main(ac, av) char **av;
{
int nline = 0; /* номер строки файла */
int ind;
int retcode = 1;
if(ac != 2){
fprintf(stderr, "Usage: %s 'pattern'\n", av[0] );
exit(33);
}
compilePatternBM( av[1] );
while( gets(str) != NULL ){
nline++;
if((ind = indexBM(str)) >= 0 ){
retcode = 0; /* O'KAY */
7.36. Напишите программу, читающую файл построчно и размещающую строки в отсортиро-
ванное двоичное дерево. По концу файла - распечатайте это дерево. Указание: исполь-
зуйте динамическую память и рекурсию.
А. Богатырев, 1992-95 - 301 - Си в UNIX
/* Двоичная сортировка строк при помощи дерева */
#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-переменная,
* а использовалась одна и та же статическая */
А. Богатырев, 1992-95 - 302 - Си в UNIX
/* Рекурсивная печать дерева */
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);
}
А. Богатырев, 1992-95 - 303 - Си в UNIX
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;
}
}
А. Богатырев, 1992-95 - 304 - Си в UNIX
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;
}
А. Богатырев, 1992-95 - 305 - Си в UNIX
}
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;
}
}
А. Богатырев, 1992-95 - 306 - Си в UNIX
/* При инициализации 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;
А. Богатырев, 1992-95 - 307 - Си в UNIX
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
А. Богатырев, 1992-95 - 308 - Си в UNIX
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 );
Перепишите эту программу, объявив ключ как строку, например
А. Богатырев, 1992-95 - 309 - Си в UNIX
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 - после сортировки в
него было что-то добавлено и линейный порядок нарушен.
7.41. Напишите функцию match(строка,шаблон); для проверки соответствия строки упро-
щенному регулярному выражению в стиле Шелл. Метасимволы шаблона:
* - любое число любых символов (0 и более);
? - один любой символ.
Усложнение:
[буквы] - любая из перечисленных букв.
[!буквы] - любая из букв, кроме перечисленных.
[h-z] - любая из букв от h до z включительно.
Указание: для проверки "остатка" строки используйте рекурсивный вызов этой же функ-
ции.
Используя эту функцию, напишите программу, которая выделяет из файла СЛОВА,
удовлетворяющие заданному шаблону (например, "[Ии]*о*т"). Имеется в виду, что каждую
строку надо сначала разбить на слова, а потом проверить каждое слово.
А. Богатырев, 1992-95 - 310 - Си в UNIX
#include <stdio.h>
#include <string.h>
#include <locale.h>
#define U(c) ((c) & 0377) /* подавление расширения знака */
#define QUOT '\\' /* экранирующий символ */
#ifndef MATCH_ERR
# define MATCH_ERR printf("Нет ]\n")
#endif
/* s - сопоставляемая строка
* p - шаблон. Символ \ отменяет спецзначение метасимвола.
*/
int match (register char *s, register char *p)
{
register int scc; /* текущий символ строки */
int c, cc, lc; /* lc - предыдущий символ в [...] списке */
int ok, notflag;
for (;;) {
scc = U(*s++); /* очередной символ строки */
switch (c = U (*p++)) { /* очередной символ шаблона */
case QUOT: /* a*\*b */
c = U (*p++);
if( c == 0 ) return(0); /* ошибка: pattern\ */
else goto def;
case '[': /* любой символ из списка */
ok = notflag = 0;
lc = 077777; /* достаточно большое число */
if(*p == '!'){ notflag=1; p++; }
while (cc = U (*p++)) {
if (cc == ']') { /* конец перечисления */
if (ok)
break; /* сопоставилось */
return (0); /* не сопоставилось */
}
if (cc == '-') { /* интервал символов */
if (notflag){
/* не из диапазона - OK */
if (!syinsy (lc, scc, U (*p++)))
ok++;
/* из диапазона - неудача */
else return (0);
} else {
/* символ из диапазона - OK */
if (syinsy (lc, scc, U (*p++)))
ok++;
}
}
else {
if (cc == QUOT){ /* [\[\]] */
cc = U(*p++);
if(!cc) return(0);/* ошибка */
}
if (notflag){
if (scc && scc != (lc = cc))
ok++; /* не входит в список */
else return (0);
} else {
А. Богатырев, 1992-95 - 311 - Си в UNIX
if (scc == (lc = cc)) /* входит в список */
ok++;
}
}
}
if (cc == 0){ /* конец строки */
MATCH_ERR;
return (0); /* ошибка */
}
continue;
case '*': /* любое число любых символов */
if (!*p)
return (1);
for (s--; *s; s++)
if (match (s, p))
return (1);
return (0);
case 0:
return (scc == 0);
default: def:
if (c != scc)
return (0);
continue;
case '?': /* один любой символ */
if (scc == 0)
return (0);
continue;
}
}
}
/* Проверить, что smy лежит между smax и smin
*/
int syinsy (unsigned smin, unsigned smy, unsigned smax)
{
char left [2];
char right [2];
char middle [2];
left [0] = smin; left [1] = '\0';
right [0] = smax; right [1] = '\0';
middle[0] = smy; middle[1] = '\0';
return (strcoll(left, middle) <= 0 && strcoll(middle, right) <= 0);
}
Обратите внимание на то, что в UNIX расширением шаблонов имен файлов, вроде *.c,
занимается не операционная система (как в MS DOS), а программа-интерпретатор команд
пользователя (shell: /bin/sh, /bin/csh, /bin/ksh). Это позволяет обрабатывать (в
принципе) разные стили шаблонов имен.
7.42. Изучите раздел руководства man regexp и include-файл /usr/include/regexp.h,
содержащий исходные тексты функций compile и step для регулярного выражения в стиле
программ ed, lex, grep:
одна буква C
или заэкранированный спецсимвол \. \[ \* \$ \^ \\ означают сами себя;
А. Богатырев, 1992-95 - 312 - Си в UNIX
. означает один любой символ кроме \n;
[abc]
или [a-b] означает любой символ из перечисленных (из интервала);
[abc-]
минус в конце означает сам символ -;
[]abc]
внутри [] скобка ] на первом месте означает сама себя;
[^a-z]
крышка ^ означает отрицание, т.е. любой символ кроме перечисленных;
[a-z^]
крышка не на первом месте означает сама себя;
[\*.]
спецсимволы внутри [] не несут специального значения, а представляют сами себя;
C* любое (0 и более) число символов C;
.* любое число любых символов;
выражение*
любое число (0 и более) повторений выражения, например [0-9]* означает число
(последовательность цифр) или пустое место. Ищется самое длинное прижатое влево
подвыражение;
выражение\{n,m\}
повторение выражения от n до m раз (включительно), где числа не превосходят 255;
выражение\{n,\}
повторение по крайней мере n раз, например [0-9]\{1,\} означает число;
выражение\{n\}
повторение ровно n раз;
выражение$
строка, чей конец удовлетворяет выражению, например .*define.*\\$
^выражение
строка, чье начало удовлетворяет выражению;
\n символ перевода строки;
\(.....\)
сегмент. Сопоставившаяся с ним подстрока будет запомнена;
\N где N цифра. Данный участок образца должен совпадать с N-ым сегментом (нумерация
с 1).
Напишите функцию matchReg, использующую этот стиль регулярных выражений. Сохраняйте
шаблон, при вызове matchReg сравнивайте старый шаблон с новым. Перекомпиляцию следует
производить только если шаблон изменился:
#include <stdio.h>
#include <ctype.h>
#define INIT register char *sp = instring;
#define GETC() (*sp++)
#define PEEKC() (*sp)
#define UNGETC(c) (--sp)
#define RETURN(ptr) return
#define ERROR(code) \
{fprintf(stderr,"%s:ERR%d\n",instring,code);exit(177);}
# include <regexp.h>
#define EOL '\0' /* end of line */
#define ESIZE 512
int matchReg(char *str, char *pattern){
static char oldPattern[256];
static char compiledExpr[ESIZE];
if( strcmp(pattern, oldPattern)){ /* различны */
/* compile regular expression */
compile(pattern,
compiledExpr, &compiledExpr[ESIZE], EOL);
А. Богатырев, 1992-95 - 313 - Си в UNIX
strcpy(oldPattern, pattern); /* запомнить */
}
return step(str, compiledExpr); /* сопоставить */
}
/* Пример вызова: reg '^int' 'int$' char | less */
/* reg 'putchar.*(.*)' < reg.c | more */
void main(int ac, char **av){
char inputline[BUFSIZ]; register i;
while(gets(inputline)){
for(i=1; i < ac; i++)
if(matchReg(inputline, av[i])){
char *p; extern char *loc1, *loc2;
/*printf("%s\n", inputline);*/
/* Напечатать строку,
* выделяя сопоставившуюся часть жирно */
for(p=inputline; p != loc1; p++) putchar(*p);
for( ; p != loc2; p++)
if(isspace((unsigned char) *p))
putchar(*p);
else printf("%c\b%c", *p, *p);
for( ; *p; p++) putchar(*p);
putchar('\n');
break;
}
}
}
7.43. Используя <regexp.h> напишите программу, производящую контекстную замену во
всех строках файла. Если строка не удовлетворяет регулярному выражению - она остается
неизменной. Примеры вызова:
$ regsub '\([0-9]\{1,\}\)' '(\1)'
$ regsub 'f(\(.*\),\(.*\))' 'f(\2,\1)' < file
Вторая команда должна заменять все вхождения f(a,b) на f(b,a). Выражение, обозначен-
ное в образце как \(...\), подставляется на место соответствующей конструкции \N во
втором аргументе, где N - цифра, номер сегмента. Чтобы поместить в выход сам символ
\, его надо удваивать: \\.
А. Богатырев, 1992-95 - 314 - Си в UNIX
/* Контекстная замена */
#include <stdio.h>
#include <ctype.h>
#define INIT register char *sp = instring;
#define GETC() (*sp++)
#define PEEKC() (*sp)
#define UNGETC(c) (--sp)
#define RETURN(ptr) return
#define ERROR(code) regerr(code)
void regerr();
# include <regexp.h>
#define EOL '\0' /* end of line */
#define ESIZE 512
short all = 0;
/* ключ -a означает, что в строке надо заменить ВСЕ вхождения образца (global, all):
* regsub -a int INT
* "aa int bbb int cccc" -> "aa INT bbb INT cccc"
*
* step() находит САМУЮ ДЛИННУЮ подстроку, удовлетворяющую выражению,
* поэтому regsub 'f(\(.*\),\(.*\))' 'f(\2,\1)'
* заменит "aa f(1,2) bb f(3,4) cc" -> "aa f(4,1,2) bb f(3) cc'
* |___________|_| |_|___________|
*/
char compiled[ESIZE], line[512];
А. Богатырев, 1992-95 - 315 - Си в UNIX
void main(int ac, char *av[]){
register char *s, *p; register n; extern int nbra;
extern char *braslist[], *braelist[], *loc1, *loc2;
if( ac > 1 && !strcmp(av[1], "-a")){ ac--; av++; all++; }
if(ac != 3){
fprintf(stderr, "Usage: %s [-a] pattern subst\n", av[0]);
exit(1);
}
compile(av[1], compiled, compiled + sizeof compiled, EOL);
while( gets(line) != NULL ){
if( !step(s = line, compiled)){
printf("%s\n", line); continue;
}
do{
/* Печатаем начало строки */
for( ; s != loc1; s++) putchar(*s);
/* Делаем замену */
for(s=av[2]; *s; s++)
if(*s == '\\'){
if(isdigit(s[1])){ /* сегмент */
int num = *++s - '1';
if(num < 0 || num >= nbra){
fprintf(stderr, "Bad block number %d\n", num+1);
exit(2);
}
for(p=braslist[num]; p != braelist[num]; ++p)
putchar(*p);
} else if(s[1] == '&'){
++s; /* вся сопоставленная строка */
for(p=loc1; p != loc2; ++p)
putchar(*p);
} else putchar(*++s);
} else putchar(*s);
} while(all && step(s = loc2, compiled));
/* Остаток строки */
for(s=loc2; *s; s++) putchar(*s);
putchar('\n');
} /* endwhile */
}
А. Богатырев, 1992-95 - 316 - Си в UNIX
void regerr(int code){ char *msg;
switch(code){
case 11: msg = "Range endpoint too large."; break;
case 16: msg = "Bad number."; break;
case 25: msg = "\\digit out of range."; break;
case 36: msg = "Illegal or missing delimiter."; break;
case 41: msg = "No remembered search string."; break;
case 42: msg = "\\(~\\) imbalance."; break;
case 43: msg = "Too many \\(."; break;
case 44: msg = "More than 2 numbers given in \\{~\\\"}."; break;
case 45: msg = "} expected after \\."; break;
case 46: msg = "First number exceeds second in \\{~\\}."; break;
case 49: msg = "[ ] imbalance."; break;
case 50: msg = "Regular expression overflow."; break;
default: msg = "Unknown error"; break;
} fputs(msg, stderr); fputc('\n', stderr); exit(code);
}
void prfields(){
int i;
for(i=0; i < nbra; i++)
prfield(i);
}
void prfield(int n){
char *fbeg = braslist[n], *fend = braelist[n];
printf("\\%d='", n+1);
for(; fbeg != fend; fbeg++)
putchar(*fbeg);
printf("'\n");
}
7.44. Составьте функцию поиска подстроки в строке. Используя ее, напишите программу
поиска подстроки в текстовом файле. Программа должна выводить строки (либо номера
строк) файла, в которых встретилась данная подстрока. Подстрока задается в качестве
аргумента функции main().
/* Алгоритм быстрого поиска подстроки.
* Дж. Мур, Р. Бойер, 1976 Texas
* Смотри: Communications of the ACM 20, 10 (Oct., 1977), 762-772
*
* Этот алгоритм выгоден при многократном поиске образца в
* большом количестве строк, причем если они равной длины -
* можно сэкономить еще и на операции strlen(str).
* Алгоритм характерен тем, что при неудаче производит сдвиг не на
* один, а сразу на несколько символов вправо.
* В лучшем случае алгоритм делает slen/plen сравнений.
*/
char *pattern; /* образец (что искать) */
static int plen; /* длина образца */
static int d[256]; /* таблица сдвигов; в алфавите ASCII -
* 256 букв. */
/* расстояние от конца образца до позиции i в нем */
#define DISTANCE(i) ((plen-1) - (i))
А. Богатырев, 1992-95 - 317 - Си в UNIX
/* Поиск:
* выдать индекс вхождения pattern в str,
* либо -1, если не входит
*/
int indexBM( str ) char *str; /* в чем искать */
{
int slen = strlen(str); /* длина строки */
register int pindx; /* индекс сравниваемой буквы в образце */
register int cmppos; /* индекс сравниваемой буквы в строке */
register int endpos; /* позиция в строке, к которой "приставляется"
* последняя буква образца */
/* пока образец помещается в остаток строки */
for( endpos = plen-1; endpos < slen ; ){
/* Для отладки: pr(str, pattern, endpos - (plen-1), 0); /**/
/* просмотр образца от конца к началу */
for( cmppos = endpos, pindx = (plen - 1);
pindx >= 0 ;
cmppos--, pindx-- )
if( str[cmppos] != pattern[pindx] ){
/* Сдвиг, который ставит самый правый в образце
* символ str[endpos] как раз под endpos-тую
* позицию строки. Если же такой символ в образце не
* содержится (или содержится только на конце),
* то начало образца устанавливается в endpos+1 ую
* позицию
*/
endpos += d[ str[endpos] & 0377 ];
break; /* & 0377 подавляет расширение знака. Еще */
} /* можно сделать все char -> unsigned char */
if( pindx < 0 ) return ( endpos - (plen-1));
/* Нашел: весь образец вложился */
}
return( -1 ); /* Не найдено */
}
А. Богатырев, 1992-95 - 318 - Си в UNIX
/* Разметка таблицы сдвигов */
void compilePatternBM( ptrn ) char *ptrn; {
register int c;
pattern = ptrn; plen = strlen(ptrn);
/* c - номер буквы алфавита */
for(c = 0; c < 256; c++)
d[c] = plen;
/* сдвиг на длину всего образца */
/* c - позиция в образце */
for(c = 0; c < plen - 1; c++)
d[ pattern[c] & 0377 ] = DISTANCE(c);
/* Сдвиг равен расстоянию от самого правого
* (кроме последней буквы образца)
* вхождения буквы в образец до конца образца.
* Заметим, что если буква входит в образец несколько раз,
* то цикл учитывает последнее (самое правое) вхождение.
*/
}
/* Печать найденных строк */
void pr(s, p, n, nl) char *s, *p;
{
register i;
printf("%4d\t%s\n", nl, s );
printf(" \t");
for(i = 0; i < n; i++ )
putchar( s[i] == '\t' ? '\t' : ' ' );
printf( "%s\n", p );
}
/* Аналог программы fgrep */
#include <stdio.h>
char str[ 1024 ]; /* буфер для прочитанной строки */
void main(ac, av) char **av;
{
int nline = 0; /* номер строки файла */
int ind;
int retcode = 1;
if(ac != 2){
fprintf(stderr, "Usage: %s 'pattern'\n", av[0] );
exit(33);
}
compilePatternBM( av[1] );
while( gets(str) != NULL ){
nline++;
if((ind = indexBM(str)) >= 0 ){
retcode = 0; /* O'KAY */