Хрестоматия по программированию на Си в Unix
}
}
total(); exit(0);
}
/* обработать файл с именем name */
munch( name ) char *name;
{
char l[MAXL]; /* буфер для очередной строки */
int len; /* длина этой строки */
char *words[50]; /* таблица полей строки */
char **s; /* служебная */
int nwords; /* число слов в строке */
FILE *fp;
if( name == NULL || !*name )
fp = stdin; /* стандартный ввод */
else
if( (fp = fopen( name, "r" )) == NULL ){
fprintf( stderr, "Не могу открыть файл %s\n",
name );
return;
}
printf( "----------------------------%s----\n", name );
while( fgets( l, MAXL, fp ) != NULL ){
len = strlen( l );
if( len && l[len-1] == '\n' )
l[--len] = '\0' ;
if( nwords = parse( l, words)){
/* распечатка слов в обратном порядке */
for( --nwords; nwords >= 0; nwords-- ){
printf( "%s ", words[ nwords] );
add( words[ nwords ] );
}
}
putchar ('\n');
}
if( fp != stdin ) fclose( fp );
}
/* разобрать строку на слова */
parse( s, tabl )
register unsigned char *s;
unsigned char *tabl[];
{
char eol = 0;
int nwords = 0;
while ( !eol ){
/* пропустить пробелы и табуляции */
while(isspace(*s)) s++;
if( !*s ) /* строка кончилась */
break;
*tabl++ = s; nwords++;
/* начало очередного слова */
/* пока не пробел и не конец строки */
while( *s && !isspace(*s))s++;
/* указатель стоит на символе, следующем за словом */
if( ! *s ) eol ++;
*s = '\0';
/* закрыли Слово, начинаем Дело */
s++;
}
*tabl = NULL;
return nwords;
}
/* построение таблицы слов, встречающихся в файле */
#define MAXWORDS 1024
struct W{
int ctr; /* число вхождений слова */
char *wrd; /* слово */
}w [MAXWORDS]; /* таблица */
int busy = 0 ; /* занято в таблице */
extern char *malloc();
/* Добавить слово в таблицу */
add( word ) char *word;
{
register i;
static alert = 1;
/* нет ли уже слова в таблице ? */
/* если есть - просто увеличить счетчик */
for( i = 0; i < busy ; i++ ){
if( !strcmp( word, w[i].wrd )){
w[i].ctr++;
return;
}
}
if( busy >= MAXWORDS ){
if( alert ){
fprintf( stderr, "Переполнение таблицы слов\7\n");
alert = 0;
}
return;
}
/* нет, слова нет. Заносим: */
w[busy].wrd = malloc( strlen( word ) + 1 );
/* 1 байт под символ \0 */
if( w[busy].wrd == NULL ){
fprintf( stderr, "Мало памяти\n");
busy = MAXWORDS+1; /* якобы переполнение */
return;
}
w[busy].ctr = 1;
strcpy( w[busy].wrd, word );
busy++;
}
compare( a, b ) struct W *a, *b;
{
return strcoll( a-> wrd, b-> wrd );
/* strcoll сравнивает слова в алфавитном порядке */
}
/* выдача всех слов, встреченных в тексте, и числа их вхождений */
total(){
register i;
/* сортируем слова по алфавиту */
qsort( w, busy, sizeof(struct W), compare );
printf( "-----|-----------ИТОГ---------------\n");
for( i=0; i < busy; i++ )
printf( "%4d | %s\n",
w[i].ctr,
w[i].wrd
);
}
/* Пример 6 */
/* Сортировка букв в строке методом "пузырька" (bubble sort) */
#define YES 1
#define NO 0
bsort(s) char *s;
{
register i; /* индекс сравниваемой буквы */
register need = YES; /* надо ли продолжать сортировку ? */
while( need ){
need = NO; /* не надо */
for(i=0; s[i+1]; i++ )
/* условие цикла: мы сравниваем i-ую и i+1-ую буквы,
* поэтому и проверяем наличие i+1ой буквы
*/
if( s[i] > s[i+1] ){ /* в неверном порядке */
swap( &s[i], &s[i+1] ); /* переставить */
need = YES; /* что-то изменилось: надо будет
* повторить просмотр массива букв */
}
}
}
/* А вот вариант сортировки, написанный с указателями */
bpsort(s) char *s;
{
register char *p; register need = YES;
while( need ){
need = NO;
for( p = s; p[1] != '\0' ; p++ )
if( *p > *(p+1) ){
swap( p, p+1 ); need = YES;
}
}
}
/* обмен двух букв, находящихся по адресам s1 и s2 */
swap( s1, s2 ) register char *s1, *s2;
{
char tmp; /* temporary */
tmp = *s1; *s1 = *s2; *s2 = tmp;
}
char sample1[] = "Homo homini lupus est - ergo bibamus!";
char sample2[ sizeof sample1 ]; /* массив такого же размера */
main(){
strcpy( sample2, sample1 ); /* скопировать */
bsort ( sample1 ); printf( "%s\n", sample1 );
bpsort( sample2 ); printf( "%s\n", sample2 );
}
/* Пример 7 */
/* Работа с хэш-таблицей. Часть функций написана так, чтобы
* быть независимой от типов ключа и значения и легко
* подвергаться модификации.
*/
#include
#include /* prototype for strchr() */
extern void *malloc(unsigned size);
/* типы ключа и значения: в нашем случае это строки */
typedef unsigned char uchar;
typedef uchar *VAL; typedef uchar *KEY;
/* Для использования следует реализовать операции
int HASHFUNC(KEY); int EQKEY(KEY, KEY);
void FREEVAL(VAL); void SETVAL(VAL, VAL);
void FREEKEY(KEY); void SETKEY(KEY, KEY);
*/
#define HASHSIZE 21 /* размер таблицы: очень хорошо 2**n */
uchar *strudup(const uchar *s){ /* создание копии строки в "куче" */
uchar *p = (uchar *) malloc(strlen(s)+1); strcpy(p, s); return p;
}
/* одна из возможных хэш-функций */
unsigned int hash; /* последнее вычисленное значение хэш-функции */
int HASHFUNC(KEY key){
unsigned int i = 0; uchar *keysrc = key;
while(*key){
i = (i << 1)|(i >> 15); /* ROL */
i ^= *key++;
}
hash = i % HASHSIZE;
printf( "hash(%s)=%d\n", keysrc, hash); /* отладка */
return hash;
}
#define EQKEY(s1, s2) (strcmp(s1, s2) == 0)
#define FREEKEY(s) free(s)
#define FREEVAL(s) free(s)
#define SETVAL(at,s) at = strudup(s)
#define SETKEY(at,s) at = strudup(s)
#define KEYFMT "%s"
#define VALFMT "%s"
/* ================== типо-независимая часть ================= */
struct cell {
struct cell *next; /* ссылка на очередной элемент */
KEY key; /* ключ */
VAL val; /* значение */
} *hashtable[ HASHSIZE ]; /* хэш-таблица */
/* получение значения по ключу */
struct cell *get(KEY key){
struct cell *p;
for(p = hashtable[HASHFUNC(key)]; p; p = p->next)
if(EQKEY(p->key, key))
return p;
return NULL; /* отсутствует */
}
/* занести пару ключ:значение в таблицу */
void set(KEY key, VAL val){
struct cell *p;
/* проверить - не было ли звена с таким ключом */
if((p = get(key)) == NULL){ /* не было */
if(!(p = (struct cell *) malloc(sizeof(*p)))) return;
SETKEY(p->key, key);
p->next = hashtable[hash]; /* hash вычислено в get() */
hashtable[hash] = p;
} else /* уже было: изменить значение */
FREEVAL(p->val);
SETVAL(p->val, val);
}
/* удаление по ключу */
int del(KEY key){
int indx = HASHFUNC(key);
struct cell *p, *prev = NULL;
if((p = hashtable[indx]) == NULL) return 0;
for( ;p ;prev = p, p=p->next)
if(EQKEY(p->key, key)){
FREEVAL(p->val); FREEKEY(p->key);
if( p == hashtable[indx] ) /* голова списка */
hashtable[indx] = p->next;
else prev->next = p->next;
free((void *) p ); return 1; /* удален */
}
return 0; /* не было такого */
}
/* распечатать пару ключ:значение */
void printcell(struct cell *ptr){
putchar('(');
printf( KEYFMT, ptr->key ); putchar(',');
printf( VALFMT, ptr->val ); putchar(')');
}
/* распечатка таблицы (для отладки) */
void printtable(){
register i; struct cell *p;
printf("----TABLE CONTENTS----\n");
for(i=0; i < HASHSIZE; i++)
if((p = hashtable[i]) != NULL){
printf( "%d: ", i);
for(; p; p=p->next)
printcell(p), putchar(' ');
putchar('\n');
}
}
/* итератор */
struct celliter {
int index; struct cell *ptr;
};
/* выдать очередное значение */
struct cell *nextpair(struct celliter *ci){
struct cell *result;
while((result = ci->ptr) == NULL){
if( ++(ci->index) >= HASHSIZE )
return NULL; /* больше нет */
ci->ptr = hashtable[ci->index];
}
ci->ptr = result->next; return result;
}
/* инициализация итератора */
struct cell *resetiter(struct celliter *ci){
ci->index = (-1); ci->ptr = NULL;
return nextpair(ci); /* первое значение */
}
/* =========================================================== */
void main(){ /* таблица из имен и размеров файлов текущего каталога */
struct celliter ci; struct cell *cl;
char key[40], value[40]; struct cell *val;
extern FILE *popen(); FILE *fp; char *s ;
/* popen() читает вывод команды, заданной в 1-ом аргументе */
fp = popen( "ls -s", "r" );
while( fscanf( fp, "%s%s", value, key) == 2 )
set(key, value);
pclose(fp); /* popen() надо закрывать pclose(); */
for(;;){
printf( "-> " ); /* приглашение */
if( !gets( key )) break; /* EOF */
if( *key == '-' ){ /* -КЛЮЧ :удалить */
printf( del( key+1 ) ? "OK\n" : "нет такого\n");
continue;
}
if( !*key || !strcmp(key, "=")){ /* = :распечатать таблицу*/
printtable(); continue;
}
if(s = strchr(key, '=')){ /* КЛЮЧ=ЗНАЧЕНИЕ :добавить */
*s++ = '\0';
set(key, s); continue;
}
if((val = get( key )) == NULL) /* КЛЮЧ :найти значение */
printf( "нет такого ключа\n");
else{ printf( "значение "); printf(VALFMT, val->val);
putchar('\n');
}
}
/* распечатка таблицы при помощи итератора */
for( cl = resetiter(&ci) ; cl ; cl = nextpair(&ci))
printcell(cl), putchar('\n');
}
/* Пример 8 */
/* Пример маленькой базы данных.
* Данные хранятся БЕЗ дубликатов.
* Надо заметить, что используется плохой (неэффективный)
* алгоритм доступа - линейный поиск.
*/
#include
/* Все записи в базе имеют фиксированный размер */
#define VLEN 20
#define KEY_FREE (-13) /* ключ свободного места. Он выбран
произвольно, но не должен встречаться в качестве входных данных */
