Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Saltillo
0 / 0 / 0
Регистрация: 30.10.2011
Сообщений: 21
#1

Ключ в хэш-таблице - C++

19.01.2013, 18:29. Просмотров 643. Ответов 5
Метки нет (Все метки)

Здравствуйте !
Помогите решить две задачи:
1. Поиск ключа в хэш-таблице с цепочками
2. Вставка ключа в хэш-таблицу с цепочками
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.01.2013, 18:29
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Ключ в хэш-таблице (C++):

Описать класс "хэш-таблица", используя unordered_set и заданную хэш-функцию - C++
Здравствуйте. Есть класс объектов и ключ сравнения: #pragma once #include <iostream> #include <vector> #include <list> #include...

ХЭШ таблицы на С++ - C++
Всем привет, кто-нить знает что-нибудь по вот такой задаче (цитирую условие): "Реализовать и протестировать конкретный класс динамической...

ХЭШ ТАБЛИЦЫ НА С++ - C++
всем привет, кто-нить знает что-нибудь по вот такой задаче (цитирую условие): "Реализовать и протестировать конкретный класс динамической...

Хэш функции - C++
Задание: Написать программу которая реализует хэш-функцию за 3 последними цифрами, идентификационного номера. Реализовать добавления и...

Хэш-функция - C++
Здравтствуйте! У меня такая проблема. У меня есть текст, и мне нужно каждому слову поставить в соответствие чиселку (например, от 0 до 255)...

Хэш-таблица - C++
Дана строка произвольного размера. Необходимо найти все повторяющиеся фрагменты максимальной длины. Для начала нужно создать хэш-таблицу...

5
OhMyGodSoLong
~ Эврика! ~
1244 / 993 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
19.01.2013, 18:42 #2
1. Поиск ключа в хеш-таблице с цепочками.
1.1. Вычисляем хеш ключа, находим соответствующую ячейку. Для открытого хеширования ячейка это указатель на (односвязный) список пар "ключ — значение". Ячеек в массиве столько, сколько значений выдаёт хеш-функция.
1.2. Проходим по списку в поисках элемента с совпадающим ключом.
1.3. Нашли — элемент есть. Прошли весь список и не нашли — такого ключа в хеше нет.

2. Вставка ключа в хеш-таблицу с цепочками.
2.1. Проверяем наличие ключа в таблице как в пункте 1.
2.2. Если ключа нет, то приписываем новый элемент в начало списка соответствующей ячейки. Если ключ есть, то варианты: 1) ругаемся; 2) записываем в элемент новое значение.
1
Igor3D
913 / 512 / 55
Регистрация: 01.10.2012
Сообщений: 2,539
19.01.2013, 19:07 #3
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
1.2. Проходим по списку в поисках элемента с совпадающим ключом.
Совпадающим значением ключа (оператор ==), хеш-значение не уникально (напр остаток от деления)

Вставка: спрыгнули на ячейку. Теперь варианты

a) ячейка пуста - записали в нее новое значение

б) не пуста и хеш-значение совпадает с данным - берем свободную ячейку из списка свободных. Если список пуст - увеличиваем размер хеша. Пишем в ячейку (хотя она и соответствует др ключу) и линкуем ее в хвост

в) не пуста и хеш-значение не совпадает. Переносим текущую ячейку в свободную (подобно "б") и заполняем освободившуюся
1
Saltillo
0 / 0 / 0
Регистрация: 30.10.2011
Сообщений: 21
19.01.2013, 22:37  [ТС] #4
А можно код к этому на С/C++ , заранее спасибо)
0
Igor3D
913 / 512 / 55
Регистрация: 01.10.2012
Сообщений: 2,539
20.01.2013, 11:04 #5
Цитата Сообщение от Saltillo Посмотреть сообщение
А можно код к этому на С/C++ , заранее спасибо)
Ну весь код - там много, а вот классы набросаю

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <class Key, class Val>
struct Cell {
 Cell * mNext. * mPrev; // каждая ячейка в двусвязном списке
 unsigned int mHash;      // хеш-значение
 bool mEmpty;               // флаг ячейка пуста
 Key mKey;                    // ключ
 Val mVal;                      // значение
};
 
template <class Key, class Val>
struct HashTable {
 ... // методы
 size_t mCount;
 Cell<Key, Val> * mCell;   // здесь лучше C массив (а не контейнер std)
 Cell<Key, Val> * mFreeList;   // список свободных ячеек
};
Для класса/типа Key должна быть определена ф-ция
C++
1
2
3
unsigned int Hash( const Key & key);
// напр
unsigned int Hash( const int & key) { return key; }
Конструктор HashTable выделяет какое-то число свободных ячеек (напр 16) и связывает их в mFreeList. Далее как обсуждалось выше
1
Saltillo
0 / 0 / 0
Регистрация: 30.10.2011
Сообщений: 21
20.01.2013, 12:44  [ТС] #6
Igor3D ~OhMyGodSoLong~ спасибо)
0
20.01.2013, 12:44
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.01.2013, 12:44
Привет! Вот еще темы с ответами:

Хэш функция - C++
Нашел хэш функцию в нете,помогите разабратся че она делает unsigned HashData(char * DATA, int Length) { unsigned hash = 0; ...

Хэш-таблица - C++
Задание реализовать динамическую хеш-таблицу с открытой адресацией для хранения строк (операции вставки и поиска). Таблица должна...

хэш-функция - C++
Здрасти. Почитал тут про хэш-ф-ии, и был приведен пример: hashVal=(hashVal*128+key)%tableSize; А Что означает величина 128? И...

Хэш таблица - C++
Подскажите, пожалуйста, как сделать хэш-таблицу в которой у каждого элемента есть шесть полей.(например Имя фамилия возраст...). Что бы...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru