У меня проблема с указателем, и я не могу ее обойти ..
В реализации HashTable у меня есть список упорядоченных узлов в каждом сегменте. У меня проблема в функции вставки, в сравнении, чтобы увидеть, больше ли следующий узел, чем текущий узел (для вставки в эту позицию, если она есть) и сохранить порядок.
Может показаться, что реализация хеш-кода выглядит странно, но мне нужно иметь возможность выполнять множество поисков (но иногда и очень мало) и подсчитывать количество повторений, если оно уже вставлено (поэтому мне нужны быстрые поиски, таким образом, Hash, Я думал о самоуравновешенных деревьях как о деревьях AVL или RB, но я не знаю их, поэтому я выбрал решение, которое я знал, как реализовать ... они быстрее для этого типа проблемы?), Но я также нужно получить их по заказу, когда я закончу.
До того, как у меня был простой список, и я должен был получить массив, затем выполнить быструю сортировку, но я думаю, что я мог бы улучшить положение дел, сохраняя упорядоченные списки.
Что мне нужно отобразить Это 27-битное целое число без знака (наиболее точно 3 9-битные числа, но я преобразовываю их в 27-битное число, выполняющее (Sr << 18 | Sg << 9 | Sb) одновременно их значение hash_value. Если вам известна хорошая функция для сопоставления этого 27-битного int с 12-13-14-битной таблицей, дайте мне знать, я сейчас просто делаю типичное простое решение для модов. </p>
Это моя структура hash_node:
class hash_node {
public:
unsigned int hash_value;
int repetitions;
hash_node *next;
hash_node( unsigned int hash_val,
hash_node *nxt);
~hash_node();
};
И это источник проблемы
void hash_table::insert(unsigned int hash_value) {
unsigned int p = hash_value % tableSize;
if (table[p]!=0) { //The bucket has some elements already
hash_node *pred; //node to keep the last valid position on the list
for (hash_node *aux=table[p]; aux!=0; aux=aux->next) {
pred = aux; //last valid position
if (aux->hash_value == hash_value ) {
//It's already inserted, so we increment it repetition counter
aux->repetitions++;
} else if (hash_value < (aux->next->hash_value) ) { //The problem
//If the next one is greater than the one to insert, we
//create a node in the middle of both.
aux->next = new hash_node(hash_value,aux->next);
colisions++;
numElem++;
}
}//We have arrive to the end od the list without luck, so we insert it after
//the last valid position
ant->next = new hash_node(hash_value,0);
colisions++;
numElem++;
}else { //bucket it's empty, insert it right away.
table[p] = new hash_node(hash_value, 0);
numElem++;
}
}
Вот что показывает GDB:
Program received signal SIGSEGV, Segmentation fault.
0x08050b4b in hash_table::insert (this=0x806a310, hash_value=3163181) at ht.cc:132
132 } else if (hash_value < (aux->next->hash_value) ) {
Что фактически означает, что я сравниваю адрес памяти со значением, верно?
Надеюсь, это было ясно. Еще раз спасибо!