sd
Постоялец
Offline
|
|
« : 30-10-2011 13:46 » |
|
Всем привет. Надо реализовать словарь слово-значение тремя способами: 1) хеш-таблицами 2) разделенными списками 3) деревьями Пытаюсь пока реализовать первым способом. Класс node.h: class Node { public: char *word; char *meaning; Node *next;
Node(void): word(0), meaning(0), next(0) {}; ~Node(void);
void SetNode(char *wrd, char *mning);
bool operator==(const Node &obj); Node operator=(const Node &obj); friend ostream &operator<<(ostream &stream, Node &obj);
}; node.cpp Node::~Node(void) { if(next) { delete next; next=0; } if(word) { delete []word; word=0; } if(meaning) { delete []meaning; meaning=0; } }
void Node::SetNode(char *wrd, char *mning) { int wrdLen=strlen(wrd); int meaningLen=strlen(mning);
word=new char[wrdLen];
for(int i=0; i<wrdLen; i++) *(word+i)=*(wrd+i); *(word+wrdLen)='\0';
meaning=new char[meaningLen];
for(int i=0; i<meaningLen; i++) *(meaning+i)=*(mning+i); *(meaning+meaningLen)='\0'; }
bool Node::operator==(const Node &obj) { bool res=true; int len=strlen(word);
if(len!=strlen(obj.word)) return false;
for(int i=0; i<len; i++) if(*(word+i)!=*(obj.word+i)) res=false;
return res; }
ostream &operator<<(ostream &stream, Node &obj) { stream<<"Word: "<<obj.word<<". Meaning: "<<obj.meaning;
return stream; }
Node Node::operator=(const Node &obj) { if(*this==obj) return *this; SetNode(obj.word, obj.meaning);
return *this; }
Теперь класс HashTable. Тут проблема пока что с добавлением элемента. Вот .h файл: #include "Node.h" #include <iostream> typedef unsigned long long hashIndexType;
using namespace std;
class HashTable { int hashTableSize; Node **hashTable; public: HashTable(void): hashTableSize(0), hashTable(NULL) {}; ~HashTable(void);
hashIndexType HashFunc(char *word); Node *InsertNode(char *word, char *meaning); Node *FindNode(char *word); void DeleteNode(char *word); bool CompStr(char *str, char *str1); }; Вот функция добавления: Node *HashTable::InsertNode(char *word, char *meaning) { Node *newNode=0, *temp=0; //адрес нового узла и временного, в котором будет хранится адрес след. ячейки таблицы hashIndexType indx=0; //индекс новго элемента в таблице
indx=HashFunc(word); //получаем индекс нового элемента try { newNode=new Node; //выделяем память для нового элемента } catch(bad_alloc ba) { cout<<"Error: "<<ba.what()<<endl; exit(1); }
newNode->SetNode(word, meaning); //заполняем вновь созданный элемент temp=hashTable[indx]; //запоминаем значение, хранящееся в ячейке с найденным индексом hashTable[indx]=newNode; //записываем новый элемент в массив newNode->next=temp; //смещаем указатель на следующий элемент
return newNode; } Дебагер выкидывает из программы на строке temp=hashTable[indx]; Не подскажите в чем проблема?
|
|
|
Записан
|
|
|
|
Dimka
Деятель
Команда клуба
Offline
Пол:
|
|
« Ответ #1 : 30-10-2011 14:31 » |
|
sd, скорее всего в том, что индекс выходит за диапазон значений - т.е. либо отрицательный, либо больше или равен размеру массива. Ты же самое главное - код хэш-функции - не привёл.
|
|
|
Записан
|
Программировать - значит понимать (К. Нюгард) Невывернутое лучше, чем вправленное (М. Аврелий) Многие готовы скорее умереть, чем подумать (Б. Рассел)
|
|
|
Вад
|
|
« Ответ #2 : 30-10-2011 14:42 » |
|
Ты же самое главное - код хэш-функции - не привёл.
И код, выделяющий память под таблицу. Я вообще не вижу, чтобы выделялась память: в конструкторе установлен нулевой размер таблицы, и с таким размером вряд ли что-то будет работать.
|
|
|
Записан
|
|
|
|
sd
Постоялец
Offline
|
|
« Ответ #3 : 30-10-2011 14:45 » |
|
Вряд ли выхожу за пределы индекса. Вот код хеш-фукции: typedef unsigned long long hashIndexType; hashIndexType HashTable::HashFunc(char *word) { int len=strlen(word); int pow=1; const int alphLen=31; hashIndexType res=0;
for(int i=0; i<len; i++) { res+=(word[i]-'a'+1)*pow; pow*=alphLen; }
return res; } Я вот что подумал, у меня в классе HashTable есть массив Node **hashTable, который в принципе нигде не заполняется ничем и под него даже не выделяется память. Вот мне кажеться в том то и дело, что память под него не выделяется. Добавлено через 2 минуты и 30 секунд:Ты же самое главное - код хэш-функции - не привёл.
И код, выделяющий память под таблицу. Я вообще не вижу, чтобы выделялась память: в конструкторе установлен нулевой размер таблицы, и с таким размером вряд ли что-то будет работать. Да. Вот в этом и проблема. Только вот сколько памяти выделять? Максимальное значение индекса, возвращаемое хеш функцией - 2^64. Столько и выделять?
|
|
« Последнее редактирование: 30-10-2011 14:47 от sd »
|
Записан
|
|
|
|
RuNTiME
|
|
« Ответ #4 : 30-10-2011 16:09 » |
|
Максимальное значение индекса, возвращаемое хеш функцией - 2^64. Столько и выделять? Если у тебя есть столько оперативной памяти я тебе очень завидую Попробуй найти книгу "Фундаментальные алгоритмы на C++" http://www.ozon.ru/context/detail/id/128304/ там хорошо расписаны все интересующие тебя вопросы.
|
|
« Последнее редактирование: 30-10-2011 16:12 от RuNTiME »
|
Записан
|
Любимая игрушка - debugger ...
|
|
|
Dimka
Деятель
Команда клуба
Offline
Пол:
|
|
« Ответ #5 : 30-10-2011 18:49 » |
|
sd, а что такое hashIndexType? Беззнаковое целое 64 бита? В хэш-функции ошибка - нет ограничения на длину слова, цикл с умножением на 31 будет продолжаться хоть миллиард раз. Это же влияет и на максимально возможное значение хэш-функции и на размер хэш-таблицы.
Предлагаю изменить подход на какой-нибудь более разумный. Разумность заключается в применении какого-нибудь правила разрешения коллизий при превышении хэш-таблицы.
Например, реализация словаря при помощи деревьев может быть использована как механизм разрешения коллизий. В этом случае узлом дерева является не конкретное слово, а хэш-таблица небольшого размера, которую можно рассматривать как n-арное ветвление дерева, где n - размер таблицы. Можно взять таблицу размером 256 для первого байта всех хранимых слов, каждый элемент такой таблицы ссылается на слово, которое заканчивается этим байтом и ещё одну таблицу размером 256 для следующего байта - и так рекурсивно. Если 255 кажется скромным размером, можно взять 65536 для пары байт (актуально для Unicode-строчек).
|
|
|
Записан
|
Программировать - значит понимать (К. Нюгард) Невывернутое лучше, чем вправленное (М. Аврелий) Многие готовы скорее умереть, чем подумать (Б. Рассел)
|
|
|
RuNTiME
|
|
« Ответ #6 : 30-10-2011 19:28 » |
|
sd, Есть еще способ построения динамических хэш таблиц с решением коллизий - это "массив связанных списков". Представляет из себя следующее: Есть некоторый массив указателей имеющий фиксированный размер, допустим 65536 указателей. Каждый указатель в этом массиве является указателем на односторонне связанный список элементов (ключей). И некоторая хэш функция выдающая значения от 0 - 65535. Когда случается так, что хэш функция выдаёт одинаковое значение для двух разных ключей (возникает коллизия) ключ добавляется в соответствующий список. Поиск ключа происходит так: считается хэш от ключа, затем по значению хэша определяется в каком именно списке находится искомый ключ, а затем просто просматривается данный список. Вот неплохое описание приведенного выше метода: http://algolist.manual.ru/ds/s_has.phpPS: При условии равномерности распределения хэш функции данный алгоритм практически не уступает по скорости бинарному дереву, а в некоторых случаях даже превосходит его.
|
|
|
Записан
|
Любимая игрушка - debugger ...
|
|
|
sd
Постоялец
Offline
|
|
« Ответ #7 : 30-10-2011 20:07 » |
|
Dimka, хеш-функция взята отсюда: http://e-maxx.ru/algo/string_hashes. Как мне показалось, вполне нормальная функция, и вероятность коллизий не так велика. Если учесть то, что программа пишется в учебных целях и много слов там не будет, то, на мой взгляд, эту функцию можно смело использовать. По поводу деревьев - это следующий вопрос, сначала надо справиться с хешированием. RuNTiME, собственно моя программа и писалась на основе http://www.codenet.ru/progr/alg/sort_search/has.phpКак я вообще вижу решение своей задачи: хешируется слово, и в полученный индекс забиваем значение этого слова. При поиске просто обращаемся к индексу и все.
|
|
|
Записан
|
|
|
|
Вад
|
|
« Ответ #8 : 31-10-2011 07:30 » |
|
Dimka, хеш-функция взята отсюда: http://e-maxx.ru/algo/string_hashes. Как мне показалось, вполне нормальная функция, и вероятность коллизий не так велика. Если учесть то, что программа пишется в учебных целях и много слов там не будет, то, на мой взгляд, эту функцию можно смело использовать. Если ты внимательно читал статью по ссылке, там говорится об использовании этой хэш-функции для быстрого сравнения строк, а не для таблицы. Для таблицы, очевидно, имеет смысл выбирать меньший тип, в котором накапливается хэш. Например, unsigned char или unsigned short (при этом сами символы тоже полагая unsigned char). Тогда размер таблицы можно будет ограничить разрядностью соответствующего типа (256 или 65536). Раз для случая int64 автор гарантирует малое число коллизий (поверим ему, что это так), то при уменьшении размерности типа вероятность коллизий должна всего лишь вырасти пропорционально, что в твоём учебном случае, вообще-то, не должно представлять особого интереса. Обращаю отдельное внимание на то, что значение хэша должно быть беззнаковым - или приводиться к беззнаковому - в силу того, что оно применяется далее как индекс массива.
|
|
« Последнее редактирование: 31-10-2011 07:32 от Вад »
|
Записан
|
|
|
|
sd
Постоялец
Offline
|
|
« Ответ #9 : 31-10-2011 08:16 » |
|
По поводу хэш функции согласен, выбрал не очень удачную. Решил выбрать длину таблицы 251 (простое число) и использовать вот такую функцию: const int MULTIPLIER=31; const int tableSize=251; unsigned int hash(char *word) { unsigned int res=0; unsigned char *str; for(str=(unsigned char*) word; *str; str++) res=MULTIPLIER*res + *str; return res%tableSize;
В итоге функции мы получаем хэш-значение, которое используется как индекс в таблице, где хранится информация. Причем информация должна храниться в виде списка. Ведь такая функция дает возможность по одному индексу содержать несколько значений. То есть по индексу должен храниться массив слов. Т.о. у меня указатель на хэш таблицу Node hashTable[251][х]; Вопрос: что брать в качестве х, если количество слов в списке может быть больше 1? Добавлено через 4 часа, 4 минуты и 33 секунды:Парни, все окей. С вставкой и поиском разобрался. Подскажите вопрос с удалением. Прблема в том, что может быть такое, что под хешем храниться несколько слов. В функцию DelNode я передаю char *word, char *meaning. В случае если совпадает и то и то, то удалять надо весь узел. Если нет - то узел оставить, в meaning удалить. void HashTable::DeleteNode(char *word, char *meaning) { Node *temp=0, *nodeToDel=0; hashIndexType indx=0; indx=HashFunc(word); nodeToDel=hashTable[indx];
while(nodeToDel && !CompStr(nodeToDel->meaning, meaning)) { temp=nodeToDel; nodeToDel=nodeToDel->next; }
if(!nodeToDel) return; if(temp) temp->next=nodeToDel->next; else hashTable[indx]=nodeToDel->next;
delete []nodeToDel; } Вот, но программа не завершается. Вот деструктор класса Node Node::~Node(void) { if(next) { delete next; next=0; } if(word) { delete []word; word=0; } if(meaning) { delete []meaning; meaning=0; } Гляньеть пожалуйста правильность функции удаления и почему у меня не выполняется деструктор? Мне кажется, что проблема с удалением объекта temp, после выхода из функции. Только не могу понять в чем.
|
|
« Последнее редактирование: 31-10-2011 12:27 от sd »
|
Записан
|
|
|
|
sd
Постоялец
Offline
|
|
« Ответ #10 : 01-11-2011 17:42 » |
|
Парни. Со словарем на хэш таблицах разобрался. Надо еще реализовать на деревьях и на списках. Подскажите пожалуйста, какими деревьями и списками лучше воспользоваться.
|
|
|
Записан
|
|
|
|
Dimka
Деятель
Команда клуба
Offline
Пол:
|
|
« Ответ #11 : 01-11-2011 19:34 » |
|
sd, а какие деревья и списки ты знаешь?.. Ну и риторический вопрос - чем список отличается от дерева (по большому счёту)?
|
|
|
Записан
|
Программировать - значит понимать (К. Нюгард) Невывернутое лучше, чем вправленное (М. Аврелий) Многие готовы скорее умереть, чем подумать (Б. Рассел)
|
|
|
sd
Постоялец
Offline
|
|
« Ответ #12 : 02-11-2011 21:29 » |
|
Деревья знаю только бинарные деревья поиска, а списки односвязные и двусвязные. Начал реализовывать через бинарное дерево поиска. Осталась функция удаления, помогите написать или киньте линк, на материал, где все это подробно описано. Функция должна быть не рекурсивной. Вот класс узла дерева: class BSTNode { public: char *word; char *meaning; BSTNode *left; BSTNode *right;
BSTNode(void): word(NULL), meaning(NULL), right(0), left(0) {}; ~BSTNode(void);
void SetNode(char *wrd, char *mning);
friend ostream &operator<<(ostream &stream, BSTNode &obj); }; Вот код самого класса дерева: class BST { BSTNode *root; public: BST(void): root(0) {}; //~BST(void);
BSTNode *Insert(char *word, char *meaning); BSTNode *Search(char *word); void DeleteNode(BSTNode *node); };
BSTNode *BST::Insert(char *word, char *meaning) { int cmp=0; BSTNode *node=new BSTNode; BSTNode *current=root; BSTNode *previous=root; node->SetNode(word, meaning);
if(!root) { root=node; return node; } while(current) { previous=current; cmp=strcmp(node->word, current->word);
if(!cmp) return current; else if(cmp>0) current=current->right; else current=current->left; } if(cmp>0) previous->right=node; else previous->left=node; }
BSTNode *BST::Search(char *word) { int cmp; BSTNode *current=root;
while(current) { cmp=strcmp(word, current->word);
if(!cmp) return current; else if(cmp>0) current=current->right; else current=current->left; }
return NULL; }
void BST::DeleteNode(BSTNode *node) {
} Помогите пожалуйста с функцией удаления. В функцию передается узел, а не слово.
|
|
« Последнее редактирование: 02-11-2011 21:34 от sd »
|
Записан
|
|
|
|
Dimka
Деятель
Команда клуба
Offline
Пол:
|
|
« Ответ #13 : 03-11-2011 08:27 » |
|
sd, а чем бинарное дерево отличается от односвязного списка?
Вообще говоря, для словаря важна скорость поиска, а чтобы эта скорость всегда была максимальной, дерево должно быть сбалансированным.
|
|
|
Записан
|
Программировать - значит понимать (К. Нюгард) Невывернутое лучше, чем вправленное (М. Аврелий) Многие готовы скорее умереть, чем подумать (Б. Рассел)
|
|
|
sd
Постоялец
Offline
|
|
« Ответ #14 : 03-11-2011 16:36 » |
|
а чем бинарное дерево отличается от односвязного списка? В бинарном дереве поиска все данные упорядочены, в односвязном списке - нет. Это ускоряет поиск элемента по бинарному дереву. Вообще говоря, для словаря важна скорость поиска, а чтобы эта скорость всегда была максимальной, дерево должно быть сбалансированным. Я в курсе, предполагается, что данные в дерево будут вставляться в случайном порядке и дерево будет более-менее сбалансированным
|
|
|
Записан
|
|
|
|
Dimka
Деятель
Команда клуба
Offline
Пол:
|
|
« Ответ #15 : 04-11-2011 08:45 » |
|
В бинарном дереве поиска все данные упорядочены, в односвязном списке - нет. Это ускоряет поиск элемента по бинарному дереву. Нет такой структуры, как "бинарное дерево поиска", есть структура "бинарное дерево", а как ты им пользуешься - для поиска или ещё для чего - это твоё личное дело. Большой разницы между деревом и списком нет. Список - это вырожденное дерево, состоящее из одной ветки. И именно из этого факта следует, что дерево должно быть сбалансированным, чтобы получить наибольшее преимущество в поиске упорядоченных элементов. предполагается, что данные в дерево будут вставляться в случайном порядке и дерево будет более-менее сбалансированным Это порочный подход. Ничего не надо предполагать. Надо балансировать. И, соответственно, встаёт вопрос о методах балансировки. Например, красно-чёрные деревья (с помощью которых в C++ реализован map из стандартной библиотеки).
|
|
|
Записан
|
Программировать - значит понимать (К. Нюгард) Невывернутое лучше, чем вправленное (М. Аврелий) Многие готовы скорее умереть, чем подумать (Б. Рассел)
|
|
|
|