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 */
pr(str, pattern, ind, nline);
}
}
exit(retcode);
}
А. Богатырев, 1992-95 - 319 - Си в UNIX
/* Пример работы алгоритма:
peter piper picked a peck of pickled peppers.
peck
peter piper picked a peck of pickled peppers.
peck
peter piper picked a peck of pickled peppers.
peck
peter piper picked a peck of pickled peppers.
peck
peter piper picked a peck of pickled peppers.
peck
peter piper picked a peck of pickled peppers.
peck
peter piper picked a peck of pickled peppers.
peck
peter piper picked a peck of pickled peppers.
peck
*/
7.45. Напишите аналогичную программу, выдающую все строки, удовлетворяющие упрощен-
ному регулярному выражению, задаваемому как аргумент для main(). Используйте функцию
match, написанную нами ранее. Вы написали аналог программы grep из UNIX (но с другим
типом регулярного выражения, нежели в оригинале).
7.46. Составьте функцию expand(s1, s2), которая расширяет сокращенные обозначения
вида a-z строки s1 в эквивалентный полный список abcd...xyz в строке s2. Допускаются
сокращения для строчных и прописных букв и цифр. Учтите случаи типа a-b-c, a-z0-9 и
-a-g (соглашение состоит в том, что символ "-", стоящий в начале или в конце, воспри-
нимается буквально).
7.47. Напишите программу, читающую файл и заменяющую строки вида
|<1 и более пробелов и табуляций><текст>
на пары строк
|.pp
|<текст>
(здесь | обозначает левый край файла, a <> - метасимволы). Это - простейший препро-
цессор, готовящий текст в формате nroff (это форматтер текстов в UNIX). Усложнения:
- строки, начинающиеся с точки или с апострофа, заменять на
\&<текст, начинающийся с точки или '>
- строки, начинающиеся с цифры, заменять на
.ip <число>
<текст>
- символ \ заменять на последовательность \e.
- удалять пробелы перед символами .,;:!?) и вставлять после них пробел (знак пре-
пинания должен быть приклеен к концу слова, иначе он может быть перенесен на
следующую строку. Вы когда-нибудь видели строку, начинающуюся с запятой?).
- склеивать перенесенные слова, поскольку nroff делает переносы сам:
....xxxx начало- => ....xxxx началоконец
конец yyyy...... yyyy................
А. Богатырев, 1992-95 - 320 - Си в UNIX
Вызывайте этот препроцессор разметки текста так:
$ prep файлы... | nroff -me > text.lp
7.48. Составьте программу преобразования прописных букв из файла ввода в строчные,
используя при этом функцию, в которой необходимо организовать анализ символа (дейст-
вительно ли это буква). Строчные буквы выдавать без изменения. Указание: используйте
макросы из <ctype.h>.
Ответ:
#include <ctype.h>
#include <stdio.h>
main(){
int c;
while( (c = getchar()) != EOF )
putchar( isalpha( c ) ?
(isupper( c ) ? tolower( c ) : c) : c);
}
либо ...
putchar( isalpha(c) && isupper(c) ? tolower(c) : c );
либо даже
putchar( isupper(c) ? tolower(c) : c );
В последнем случае под isupper и islower должны пониматься только буквы (увы, не во
всех реализациях это так!).
7.49. Обратите внимание, что если мы выделяем класс символов при помощи сравнения,
например:
char ch;
if( 0300 <= ch && ch < 0340 ) ...;
(в кодировке КОИ-8 это маленькие русские буквы), то мы можем натолкнуться на следую-
щий сюрприз: перед сравнением с целым значение ch приводится к типу int (приведение
также делается при использовании char в качестве аргумента функции). При этом, если
у ch был установлен старший бит (0200), произойдет расширение его во весь старший
байт (расширение знакового бита). Результатом будет отрицательное целое число! Опыт:
char c = '\201'; /* = 129 */
printf( "%d\n", c );
печатается -127. Таким образом, наше сравнение не сработает, т.к. оказывается что ch
< 0. Следует подавлять расширение знака:
if( 0300 <= (ch & 0377) && (ch & 0377) < 0340) ...;
(0377 - маска из 8 бит, она же 0xFF, весь байт), либо объявить
unsigned char ch;
что означает, что при приведении к int знаковый бит не расширяется.
7.50. Рассмотрим еще один пример:
А. Богатырев, 1992-95 - 321 - Си в UNIX
main(){
char ch;
/* 0377 - код последнего символа алфавита ASCII */
for (ch = 0100; ch <= 0377; ch++ )
printf( "%03o %s\n",
ch & 0377,
ch >= 0300 && ch < 0340 ? "yes" : "no" );
}
Какие неприятности ждут нас здесь?
- во-первых, когда бит 0200 у ch установлен, в сравнении ch выступает как отрица-
тельное целое число (т.к. приведение к int делается расширением знакового бита),
то есть у нас всегда печатается "no". Это мы можем исправить, написав
unsigned char ch, либо используя ch в виде
(ch & 0377) или ((unsigned) ch)
- во-вторых, рассмотрим сам цикл. Пусть сейчас ch =='\377'. Условие ch <= 0377
истинно. Выполняется оператор ch++. Но ch - это байт, поэтому операции над ним
производятся по модулю 0400 (0377 - это максимальное значение, которое можно
хранить в байте - все биты единицы). То есть теперь значением ch станет 0. Но
0 < 0377 и условие цикла верно! Цикл продолжается; т.е. происходит зациклива-
ние. Избежать этого можно только описав int ch; чтобы 0377+1 было равно 0400, а
не 0 (или unsigned int, лишь бы длины переменной хватало, чтобы вместить число
больше 0377).
7.51. Составьте программу, преобразующую текст, состоящий только из строчных букв в
текст, состоящий из прописных и строчных букв. Первая буква и буква после каждой
точки - прописные, остальные - строчные.
слово один. слово два. -->
Слово один. Слово два.
Эта программа может оказаться полезной для преобразования текста, набранного в одном
регистре, в текст, содержащий буквы обоих регистров.
7.52. Напишите программу, исправляющую опечатки в словах (spell check): программе
задан список слов; она проверяет - является ли введенное вами слово словом из списка.
Если нет - пытается найти наиболее похожее слово из списка, причем если есть нес-
колько похожих - выдает все варианты. Отлавливайте случаи:
- две соседние буквы переставлены местами: ножинцы=>ножницы;
- удвоенная буква (буквы): ккаррандаш=>карандаш;
- потеряна буква: бот=>болт;
- измененная буква: бинт=>бант;
- лишняя буква: морда=>мода;
- буквы не в том регистре - сравните с каждым словом из списка, приводя все буквы
к маленьким: сОВОк=>совок;
Надо проверять каждую букву слова. Возможно вам будет удобно использовать рекурсию.
Подсказка: для некоторых проверок вам может помочь функция match:
слово_таблицы = "дом";
if(strlen(входное_слово) <= strlen(слово_таблицы)+1 &&
match(входное_слово, "*д*о*м*") ... /* похоже */
*о*м* ?дом дом?
*д*м* д?ом
*д*о* до?м
Приведем вариант решения этой задачи:
А. Богатырев, 1992-95 - 322 - Си в UNIX
#include <stdio.h>
#include <ctype.h>
#include <locale.h>
typedef unsigned char uchar;
#define ANYCHAR '*'
/* символ, сопоставляющийся с одной любой буквой */
static uchar version[120]; /* буфер для генерации вариантов */
static uchar vv; /* буква, сопоставившаяся с ANYCHAR */
/* привести все буквы к одному регистру */
static uchar icase(uchar c){
return isupper(c) ? tolower(c) : c;
}
/* сравнение строк с игнорированием регистра */
static int eqi(uchar *s1, uchar *s2 )
{
while( *s1 && *s2 ){
if( icase( *s1 ) != icase( *s2 ))
break;
s1++; s2++;
}
return ( ! *s1 && ! *s2 ) ? 1 : 0 ;
/* OK : FAIL */
}
/* сравнение строк с игнорированием ANYCHAR */
static strok(register uchar *word, register uchar *pat)
{
while( *word && *pat ){
if( *word == ANYCHAR){
/* Неважно, что есть *pat, но запомним */
vv= *pat;
} else {
if( icase(*pat) != icase(*word) )
break;
}
word++; pat++;
}
/* если слова кончились одновременно ... */
return ( !*word && !*pat) ? 1 : 0;
/* OK : FAIL */
}
А. Богатырев, 1992-95 - 323 - Си в UNIX
/* ЛИШНЯЯ БУКВА */
static int superfluous( uchar *word /* слово для коррекции */
, uchar *s /* эталон */
){
register int i,j,k;
int reply;
register len = strlen(word);
for(i=0 ; i < len ; i++){
/* генерим слова , получающиеся удалением одной буквы */
k=0;
for(j=0 ; j < i ; j++)
version[k++]=word[j];
for(j=i+1 ; j < len ; j++)
version[k++]=word[j];
version[k]='\0';
if( eqi( version, s )) return 1; /* OK */
}
return 0; /* FAIL */
}
/* ПОТЕРЯНА БУКВА */
static int hole; /* место, где вставлена ANYCHAR */
static int lost(uchar *word, uchar *s)
{
register int i,j,k;
register len = strlen(word);
hole= (-1);
for(i=0 ; i < len+1 ; i++){
k=0;
for(j=0 ; j < i ; j++)
version[k++]=word[j];
version[k++]=ANYCHAR;
for(j=i ; j < len ; j++)
version[k++]=word[j];
version[k]='\0';
if( strok( version, s )){
hole=i;
return 1; /* OK */
}
}
return 0; /* FAIL */
}
А. Богатырев, 1992-95 - 324 - Си в UNIX
/* ИЗМЕНИЛАСЬ ОДНА БУКВА (включает случай ошибки регистра) */
static int changed(uchar *word, uchar *s)
{
register int i,j,k;
register len = strlen(word);
hole = (-1);
for(i=0 ; i < len ; i++){
k=0;
for( j=0 ; j < i ; j++)
version[k++]=word[j];
version[k++]=ANYCHAR;
for( j=i+1 ; j < len ; j++)
version[k++]=word[j];
version[k]='\0';
if( strok( version,s)){
hole=i;
return 1; /* OK */
}
}
return 0; /* FAIL */
}
/* УДВОЕННАЯ БУКВА */
static int duplicates(uchar *word, uchar *s, int leng)
{
register int i,j,k;
uchar tmp[80];
if( eqi( word, s )) return 1; /* OK */
for(i=0;i < leng - 1; i++)
/* ищем парные буквы */
if( word[i]==word[i+1]){
k=0;
for(j=0 ; j < i ; j++)
tmp[k++]=word[j];
for(j=i+1 ; j < leng ; j++)
tmp[k++]=word[j];
tmp[k]='\0';
if( duplicates( tmp, s, leng-1) == 1)
return 1; /* OK */
}
return 0; /* FAIL */
}
А. Богатырев, 1992-95 - 325 - Си в UNIX
/* ПЕРЕСТАВЛЕНЫ СОСЕДНИЕ БУКВЫ */
static int swapped(uchar *word, uchar *s)
{
register int i,j,k;
register len = strlen(word);
for(i=0;i < len-1;i++){
k=0;
for(j=0 ; j < i ; j++)
version[k++]=word[j];
version[k++]=word[i+1];
version[k++]=word[i];
for(j=i+2 ; j < len ; j++)
version[k++]=word[j];
version[k]='\0';
if( eqi( version, s))
return 1; /* OK */
}
return 0; /* FAIL */
}
uchar *words[] = {
(uchar *) "bag",
(uchar *) "bags",
(uchar *) "cook",
(uchar *) "cool",
(uchar *) "bug",
(uchar *) "buy",
(uchar *) "cock",
NULL
};
#define Bcase(x, operators) case x: { operators; } break;
char *cname[5] = {
"переставлены буквы",
"удвоены буквы ",
"потеряна буква ",
"ошибочная буква ",
"лишняя буква "
};
А. Богатырев, 1992-95 - 326 - Си в UNIX
static int spellmatch( uchar *word /* IN слово для коррекции */
, uchar *words[] /* IN таблица допустимых слов */
, uchar **indx /* OUT ответ */
){
int i, code, total = (-1);
uchar **ptr;
if(!*word) return -1;
for(ptr = words; *ptr; ++ptr)
if(eqi(word, *ptr)){
if(indx) *indx = *ptr;
return 0;
}
/* Нет в таблице, нужен подбор похожих */
for(ptr = words; *ptr; ++ptr){
uchar *s = *ptr;
int max = 5;
for(i=0; i < max; i++){
switch( i ){
Bcase(0,code = swapped(word, s) )
Bcase(1,code = duplicates(word, s, strlen(word)) )
Bcase(2,code = lost(word, s) )
Bcase(3,code = changed(word, s) )
Bcase(4,code = superfluous(word, s) )
}
if(code){
total++;
printf("?\t%s\t%s\n", cname[i], s);
if(indx) *indx = s;
/* В случае с дубликатами не рассматривать
* на наличие лишних букв
*/
if(i==1) max = 4;
}
}
}
return total;
}
А. Богатырев, 1992-95 - 327 - Си в UNIX
void main(){
uchar inpbuf[BUFSIZ];
int n;
uchar *reply, **ptr;
setlocale(LC_ALL, "");
for(ptr = words; *ptr; ptr++)
printf("#\t%s\n", *ptr);
do{
printf("> "); fflush(stdout);
if(gets((char *)inpbuf) == NULL) break;
switch(spellmatch(inpbuf, words, &reply)){
case -1:
printf("Нет такого слова\n"); break;
case 0:
printf("Слово '%s'\n", reply); break;
default:
printf("Неоднозначно\n");
}
} while(1);
}
7.53. Пока я сам писал эту программу, я сделал две ошибки, которые должны быть
весьма характерны для новичков. Про них надо бы говорить раньше, в главе про строки и
в самой первой главе, но тут они пришлись как раз к месту. Вопрос: что печатает сле-
дующая программа?
#include <stdio.h>
char *strings[] = {
"Первая строка"
"Вторая строка"
"Третяя строка",
"Четвертая строка",
NULL
};
void main(){
char **p;
for(p=strings;*p;++p)
printf("%s\n", *p);
}
А печатает она вот что:
Первая строкаВторая строкаТретяя строка
Четвертая строка
Дело в том, что ANSI компилятор Си склеивает строки:
"начало строки" "и ее конец"
если они разделены пробелами в смысле isspace, в том числе и пустыми строками. А в
нашем объявлении массива строк strings мы пот