Словарь

[sd]

Всем привет. Надо реализовать словарь слово-значение тремя способами: 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]

sd, скорее всего в том, что индекс выходит за диапазон значений - т.е. либо отрицательный, либо больше или равен размеру массива. Ты же самое главное - код хэш-функции - не привёл.

[Вад]

Ты же самое главное - код хэш-функции - не привёл.

И код, выделяющий память под таблицу. Я вообще не вижу, чтобы выделялась память: в конструкторе установлен нулевой размер таблицы, и с таким размером вряд ли что-то будет работать.

[sd]

Вряд ли выхожу за пределы индекса.
Вот код хеш-фукции:

Код:

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. Столько и выделять?

[RuNTiME]

Максимальное значение индекса, возвращаемое хеш функцией - 2^64. Столько и выделять?

Если у тебя есть столько оперативной памяти я тебе очень завидую

Попробуй найти книгу "Фундаментальные алгоритмы на C++" http://www.ozon.ru/context/detail/id/128304/ там хорошо расписаны все интересующие тебя вопросы.

[Dimka]

sd, а что такое hashIndexType? Беззнаковое целое 64 бита? В хэш-функции ошибка - нет ограничения на длину слова, цикл с умножением на 31 будет продолжаться хоть миллиард раз. Это же влияет и на максимально возможное значение хэш-функции и на размер хэш-таблицы.

Предлагаю изменить подход на какой-нибудь более разумный. Разумность заключается в применении какого-нибудь правила разрешения коллизий при превышении хэш-таблицы.

Например, реализация словаря при помощи деревьев может быть использована как механизм разрешения коллизий. В этом случае узлом дерева является не конкретное слово, а хэш-таблица небольшого размера, которую можно рассматривать как n-арное ветвление дерева, где n - размер таблицы. Можно взять таблицу размером 256 для первого байта всех хранимых слов, каждый элемент такой таблицы ссылается на слово, которое заканчивается этим байтом и ещё одну таблицу размером 256 для следующего байта - и так рекурсивно. Если 255 кажется скромным размером, можно взять 65536 для пары байт (актуально для Unicode-строчек).

[RuNTiME]

sd, Есть еще способ построения динамических хэш таблиц с решением коллизий - это "массив связанных списков". Представляет из себя следующее: Есть некоторый массив указателей имеющий фиксированный размер, допустим 65536 указателей. Каждый указатель в этом массиве является указателем на односторонне связанный список элементов (ключей). И некоторая хэш функция выдающая значения от 0 - 65535. Когда случается так, что хэш функция выдаёт одинаковое значение для двух разных ключей (возникает коллизия) ключ добавляется в соответствующий список. Поиск ключа происходит так: считается хэш от ключа, затем по значению хэша определяется в каком именно списке находится искомый ключ, а затем просто просматривается данный список.

Вот неплохое описание приведенного выше метода: http://algolist.manual.ru/ds/s_has.php

PS: При условии равномерности распределения хэш функции данный алгоритм практически не уступает по скорости бинарному дереву, а в некоторых случаях даже превосходит его.

[sd]

Dimka, хеш-функция взята отсюда: http://e-maxx.ru/algo/string_hashes. Как мне показалось, вполне нормальная функция, и вероятность коллизий не так велика. Если учесть то, что программа пишется в учебных целях и много слов там не будет, то, на мой взгляд, эту функцию можно смело использовать. По поводу деревьев - это следующий вопрос, сначала надо справиться с хешированием.
RuNTiME, собственно моя программа и писалась на основе http://www.codenet.ru/progr/alg/sort_search/has.php
Как я вообще вижу решение своей задачи: хешируется слово, и в полученный индекс забиваем значение этого слова. При поиске просто обращаемся к индексу и все.

[Вад]

Dimka, хеш-функция взята отсюда: http://e-maxx.ru/algo/string_hashes. Как мне показалось, вполне нормальная функция, и вероятность коллизий не так велика. Если учесть то, что программа пишется в учебных целях и много слов там не будет, то, на мой взгляд, эту функцию можно смело использовать.

Если ты внимательно читал статью по ссылке, там говорится об использовании этой хэш-функции для быстрого сравнения строк, а не для таблицы. Для таблицы, очевидно, имеет смысл выбирать меньший тип, в котором накапливается хэш. Например, unsigned char или unsigned short (при этом сами символы тоже полагая unsigned char). Тогда размер таблицы можно будет ограничить разрядностью соответствующего типа (256 или 65536). Раз для случая int64 автор гарантирует малое число коллизий (поверим ему, что это так), то при уменьшении размерности типа вероятность коллизий должна всего лишь вырасти пропорционально, что в твоём учебном случае, вообще-то, не должно представлять особого интереса.
Обращаю отдельное внимание на то, что значение хэша должно быть беззнаковым - или приводиться к беззнаковому - в силу того, что оно применяется далее как индекс массива.

[sd]

По поводу хэш функции согласен, выбрал не очень удачную.
Решил выбрать длину таблицы 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, после выхода из функции. Только не могу понять в чем.

[sd]

Парни. Со словарем на хэш таблицах разобрался. Надо еще реализовать на деревьях и на списках. Подскажите пожалуйста, какими деревьями и списками лучше воспользоваться.

[Dimka]

sd, а какие деревья и списки ты знаешь?.. Ну и риторический вопрос - чем список отличается от дерева (по большому счёту)?

[sd]

Деревья знаю только бинарные деревья поиска, а списки односвязные и двусвязные.
Начал реализовывать через бинарное дерево поиска. Осталась функция удаления, помогите написать или киньте линк, на материал, где все это подробно описано. Функция должна быть не рекурсивной.
Вот класс узла дерева:

Код:

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) {


}

Помогите пожалуйста с функцией удаления. В функцию передается узел, а не  слово.

[Dimka]

sd, а чем бинарное дерево отличается от односвязного списка?

Вообще говоря, для словаря важна скорость поиска, а чтобы эта скорость всегда была максимальной, дерево должно быть сбалансированным.

[sd]

а чем бинарное дерево отличается от односвязного списка?

В бинарном дереве поиска все данные упорядочены, в односвязном списке - нет. Это ускоряет поиск элемента по бинарному дереву.

Вообще говоря, для словаря важна скорость поиска, а чтобы эта скорость всегда была максимальной, дерево должно быть сбалансированным.

Я в курсе, предполагается, что данные в дерево будут вставляться в случайном порядке и дерево будет более-менее сбалансированным

[Dimka]

В бинарном дереве поиска все данные упорядочены, в односвязном списке - нет. Это ускоряет поиск элемента по бинарному дереву.

Нет такой структуры, как "бинарное дерево поиска", есть структура "бинарное дерево", а как ты им пользуешься - для поиска или ещё для чего - это твоё личное дело.

Большой разницы между деревом и списком нет. Список - это вырожденное дерево, состоящее из одной ветки. И именно из этого факта следует, что дерево должно быть сбалансированным, чтобы получить наибольшее преимущество в поиске упорядоченных элементов.

предполагается, что данные в дерево будут вставляться в случайном порядке и дерево будет более-менее сбалансированным

Это порочный подход. Ничего не надо предполагать. Надо балансировать. И, соответственно, встаёт вопрос о методах балансировки. Например, красно-чёрные деревья (с помощью которых в C++ реализован map из стандартной библиотеки).