Бьерн Страуструп.
Язык программирования С++
77
чтобы использовался не только один байт ii. Эти действия можно записать таким образом:
ii <<= 1;
ii ^= *pp++;
Для хорошего хэш-кода лучше использовать операцию ^, чем +. Операция сдвига важна для получения
приемлемого хэш-кода в обоих случаях. Операторы
if (ii < 0) ii = -ii;
ii %= TBLSZ;
гарантируют, что значение ii будет из диапазона 0...TBLSZ-1. Напомним, что % - это операция взятия
остатка. Ниже полностью приведена функция look:
#include
name* look(const char* p, int ins =0)
{
int ii = 0; //
хэш-код
const char* pp = p;
while (*pp) ii = ii<<1 ^ *pp++;
if (ii < 0) ii = -ii;
ii %= TBLSZ;
for (name* n=table[ii]; n; n=n->next) //
поиск
if (strcmp(p,n->string) == 0) return n;
if (ins == 0) error("
имя не найдено");
name* nn = new name; //
занесение
nn->string = new char[strlen(p)+1];
strcpy(nn->string,p);
nn->value = 1;
nn->next = table[ii];
table[ii] = nn;
return
nn;
}
После вычисления хэш-кода ii идет простой поиск имени по членам next. Имена сравниваются с
помощью стандартной функции сравнения строк strcmp(). Если имя найдено, то возвращается
указатель на содержащую его запись, а в противном случае заводится новая запись с этим именем.
Добавление нового имени означает создание нового объекта name в свободной памяти с помощью
операции new (см. $$3.2.6), его инициализацию и включение в список имен. Последнее выполняется как
занесение нового имени в начало списка, поскольку это можно сделать даже без проверки того, есть ли
список вообще. Символьная строка имени также размещается в свободной памяти. Функция strlen()
указывает, сколько памяти нужно для строки, операция new отводит нужную память, а функция strcpy()
копирует в нее строку. Все строковые функции описаны в :
extern int strlen(const char*);
extern int strcmp(const char*, const char*);
extern char* strcpy(char*, const char*);
1>1>
Достарыңызбен бөлісу: