Таблица имен К таблице имен доступ осуществляется с помощью одной функции name* look(char* p, int ins =0); Ее второй параметр указывает, нужно ли сначала поместить строку символов в таблицу. Инициализатор =0 задает параметр, который надлежит использовать по умолчанию, когда look() вызывается с одним параметром. Это дает удобство записи, когда look("sqrt2") означает look("sqrt2",0), то есть просмотр, без помещения в таблицу. Чтобы получить такое же удобство записи для помещения в таблицу, определяется вторая функция: inline name* insert(char* s) { return look(s,1);} Как уже отмечалось раньше, элементы этой таблицы имеют тип: srtuct name { char* string; char* next; double value; } Член next используется только для сцепления вместе имен в таблице. Сама таблица - это просто вектор указателей на объекты типа name: const TBLSZ = 23; name* table[TBLSZ]; Поскольку все статические объекты инициализируются нулем, это тривиальное описание таблицы table гарантирует также надлежащую инициализацию. Для нахождения элемента в таблице в look() принимается простой алгоритм хэширования (имена с одним и тем же хэш-кодом зацепляются вместе): int ii = 0; // хэширование char* pp = p; while (*pp) ii = ii<<1 ^ *pp++; if (ii < 0) ii = -ii; ii %= TBLSZ; То есть, с помощью исключающего ИЛИ каждый символ во входной строке "добавляется" к ii ("сумме" предыдущих символов). Бит в x^y устанавливается единичным тогда и только тогда, когда соответствующие биты в x и y различны. Перед применением в символе исключающего ИЛИ, ii сдвигается на один бит влево, чтобы не использовать в слове только один байт. Это можно было написать и так: ii <<= 1; ii ^= *pp++; Кстати, применение ^ лучше и быстрее, чем +. Сдвиг важен для получения приемлемого хэш-кода в обоих случаях. Операторы if (ii < 0) ii = -ii; ii %= TBLSZ; обеспечивают, что ii будет лежать в диапазоне 0...TBLSZ-1; % - это операция взятия по модулю (еще называемая получением остатка). Вот функция полностью: extern int strlen(const char*); extern int strcmp(const char*, const char*); extern int strcpy(const char*, const char*); name* look(char* p, int ins =0) { int ii = 0; // хэширование 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. Проверка каждого name осуществляется с помощью стандартной функции strcmp(). Если строка найдена, возвращается ее name, иначе добавляется новое name. Добавление нового name включает в себя создание нового объекта в свободной памяти с помощью операции new (см. этот пункт), его инициализацию, и добавление его к списку имен. Последнее осуществляется просто путем помещения нового имени в голову списка, поскольку это можно делать даже не проверяя, имеется список, или нет. Символьную строку для имени тоже нужно сохранить в свободной памяти. Функция strlen() используется для определения того, сколько памяти нужно, new - для выделения этой памяти, и strcpy() - для копирования строки в память. <<<  Назад Вперед  >>>  1  2  3  4  5  6   8  Комментарии к статье  8 8  Обсудить в чате

8  В тему Краткая сводка операций Сводка операторов Комментарии и Выравнивание