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



флешки в коже купить. | цена бетона в тамбове |

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


Пример 7

/* Работа с хэш-таблицей. Часть функций написана так, чтобы * быть независимой от типов ключа и значения и легко * подвергаться модификации. */ #include <stdio.h>

#include <string.h> /* 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); }




Содержание  Назад  Вперед