VPF::помогите найти ошибку - Форум программистов

gosn1ck

Дата 6.5.2009, 17:53 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 103
Регистрация: 18.4.2009

Репутация: 1
Всего: 1

нету проблем

Это сообщение отредактировал(а) gosn1ck - 10.5.2009, 20:58

xvr

Дата 7.5.2009, 12:55 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 35
Всего: 223

У вас метод разрешения колизий НЕ связанный список, у вас внутреннее разрешение колизий, причем сделанное криво и неправильно. Функция FillHash вполне может залесть ЗА пределы таблицы при последовательных коллизиях, т.к. index никто не проверяет после ++

Цитата

3) почему я получаю разный index при хэшировании одного и тогоже слова в функции search(arg);

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

Код


Заносим 3 значения, которые дают 2 разных хэш кода:
V1 - H1
V2 - H1
V3 - H2

Порядок занесения:
V1 (попадет в 1ю ячейку)
V2 (из за колизии в 1й ячейки попадет во 2ю)
V3 (из за колизии в 2й ячейке попадет в 3ю)

Другой порядок:
V1 (попадет в 1ю ячейку)
V3 (попадет в 2ю ячейку)
V2 (из за колизии в 2й ячейке попадет в 3ю)

Итого - V3 попало в разные ячейки, в зависимости от порядка занесения

gosn1ck

Дата 7.5.2009, 15:45 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 103
Регистрация: 18.4.2009

Репутация: 1
Всего: 1

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

char rbuf[127] = {0}; теперь слово pusto не придётся использовать smile

ну собственно до реализации связного списка я не дошел и хотел спросить как smile

в структуре выделить поле под указатель на следующий элемент?

xvr

Дата 7.5.2009, 16:54 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 35
Всего: 223

Цитата(gosn1ck @ 7.5.2009, 15:45)

ну собственно до реализации связного списка я не дошел и хотел спросить как smile

в структуре выделить поле под указатель на следующий элемент?

Руками

Код


struct THashTable{          
  char string[50];
  int koliziya;
  THashTable* next;
};

Структуры создавать на куче (с помощью new), причем корневую таблицу (HashTable) тоже - сделать ее массивом указателей (для однородности)
Поле string в THashTable сделать типа std::string, а саму THashTable сделать классом.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »