};
то есть организован аналогично нашей первой базе данных. Сначала вы ищете нужный
ключ в файле ключей. Поле 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
#include
#include
#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
#include
#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
#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. Используя напишите программу, производящую контекстную замену во
всех строках файла. Если строка не удовлетворяет регулярному выражению - она остается
неизменной. Примеры вызова:
$ regsub '\([0-9]\{1,\}\)' '(\1)'
$ regsub 'f(\(.*\),\(.*\))' 'f(\2,\1)' < file
Вторая команда должна заменять все вхождения f(a,b) на f(b,a). Выражение, обозначен-
ное в образце как \(...\), подставляется на место соответствующей конструкции \N во
втором аргументе, где N - цифра, номер сегмента. Чтобы поместить в выход сам символ
\, его надо удваивать: \\.
А. Богатырев, 1992-95 - 314 - Си в UNIX
/* Контекстная замена */
#include
#include
#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
#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"
