Бьерн Страуструп. Язык программирования С++ Второе дополненное издание



Pdf көрінісі
бет69/256
Дата11.07.2022
өлшемі2,87 Mb.
#37591
1   ...   65   66   67   68   69   70   71   72   ...   256
Байланысты:
Бьерн Страуструп. Язык программирования С . М Бином, 2011

3.1.3 Таблица имен 
Есть функция поиска в таблице имен: 
name* look(char* p, int ins =0); 
Второй ее параметр показывает, была ли символьная строка, обозначающая имя, ранее занесена в 
таблицу. Инициализатор =0 задает стандартное значение параметра, которое используется, если 
функция look() вызывается только с одним параметром. Это удобно, так как можно писать look("sqrt2"), 
что означает look("sqrt2",0), т.е. поиск, а не занесение в таблицу. Чтобы было так же удобно задавать 
операцию занесения в таблицу, определяется вторая функция: 
inline name* insert(const char* s) { return look(s,1); } 
Как ранее упоминалось, записи в этой таблице имеют такой тип: 
struct name { 
char* 
string; 
name* 
next; 
double 
value; 
}; 
Член next используется для связи записей в таблице. Собственно таблица - это просто массив 
указателей на объекты типа name: 
const TBLSZ = 23; 
name* table[TBLSZ]; 
Поскольку по умолчанию все статические объекты инициализируются нулем, такое тривиальное 
описание таблицы table обеспечивает также и нужную инициализацию. 
Для поиска имени в таблице функция look() использует простой хэш-код (записи, в которых имена 
имеют одинаковый хэш-код, связываются вместе): 
int ii = 0; // 
хэш-код 
const char* pp = p; 
while (*pp) ii = ii<<1 ^ *pp++; 
if (ii < 0) ii = -ii; 
ii %= TBLSZ; 
Иными словами, с помощью операции ^ ("исключающее ИЛИ") все символы входной строки p 
поочередно добавляются к ii. Разряд в результате x^y равен 1 тогда и только тогда, когда эти разряды в 
операндах x и y различны. До выполнения операции ^ значение ii сдвигается на один разряд влево, 


Бьерн Страуструп.
Язык программирования С++ 
 
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   ...   65   66   67   68   69   70   71   72   ...   256




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет