Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / C / C++ / Введение в язык C++ / Выражения и операторы /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


Настольный калькулятор - Программирование от RIN.RU
Настольный калькулятор



Таблица имен


К таблице имен доступ осуществляется с помощью одной функции


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  В тему

Краткая сводка операций

Сводка операторов

Комментарии и Выравнивание

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь