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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 49, средняя оценка - 4.84
MerlinLegend
1 / 1 / 0
Регистрация: 11.04.2011
Сообщений: 109
#1

Хеш функция - C++

18.10.2012, 22:42. Просмотров 7968. Ответов 30
Метки нет (Все метки)

Здравствуйте. Помогите с задачей.

Таблица строиться по методу цепочек с использованием хэш-функции, возращающий код первой буквы идентификатора. При выполнений программы подсчитывается число коллизий.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.10.2012, 22:42
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Хеш функция (C++):

Хеш функция - C++
Всем добрый день! В общем, нужно подсчитать кол-во коллизий. За это отвечает функция size_t collisions_count(), но почему-то не...

Шаблоны. Хеш-функция - C++
Добрые день. Есть задание сделать телефонную книгу. Поиск в базе сделать через хеш-функцию. name - фамилия абонента. num - номер...

Хеш-функция, двойное хеширование - C++
Всем привет! Пишу курсач, нужна хеш-функция, которая принимала бы строку и возвращала некий индекс. Написал нечто вроде unsigned...

Объясните как работает хеш-функция - C++
int Hash_Function1(DrugStore object) { int result = 0; for (int i = 0; i < SSize+1; i++) result = result +...

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

Метод открытого хеширования и хеш-функция, основанная на методе деления с остатком - C++
Ещё раз здравствуйте! Есть такое задание: Написать программу, которая реализует метод открытого хеширования и хеш-функцией,...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
alexcoder
1463 / 677 / 89
Регистрация: 03.06.2009
Сообщений: 3,558
Завершенные тесты: 1
19.10.2012, 08:56 #2
в гугле забанили?
Хэш-таблица. Метод цепочек. C++
MerlinLegend
1 / 1 / 0
Регистрация: 11.04.2011
Сообщений: 109
19.10.2012, 18:03  [ТС] #3
Спасибо, но там задание сумму первых 2 букв, а у меня код первой буквы идентификатора
silent_1991
Эксперт С++
4963 / 3039 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
24.10.2012, 10:33 #4
MerlinLegend, да, разница настолько велика, что одним постом и не охватить...
Замените функцию hash на такую:
C++
1
2
3
4
size_t hash(const Identifier& id)
{
    return size_t(id.name()[0]);
}
Для подсчёта числа коллизий можно вставить в класс HashTable такой метод:
C++
1
2
3
4
5
6
7
8
9
10
size_t collisions_count() const
{
    size_t result = 0;
    
    for (size_t i = 0; i < hasn_table_size; ++i)
        if (m_hash_table[i].size() > 1)
            ++result;
    
    return result;
}
MerlinLegend
1 / 1 / 0
Регистрация: 11.04.2011
Сообщений: 109
24.10.2012, 19:17  [ТС] #5
Спасибо за помощь, но одна проблема

у меня не объявлены переменные я их объявил, но все равно ничего не получается
silent_1991
Эксперт С++
4963 / 3039 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
25.10.2012, 11:47 #6
MerlinLegend, очень информативно. А теперь представьте, что вы не видели код своей программы, и прочтите ваше сообщение. Вы что-нибудь можете из него вынести? Что-нибудь, что могло бы натолкнуть вас на идею, в чём же проблема?
Если не поняли, то вот прямым текстом: как было, что сделали, как стало? Что значит "ничего не получается"? Не включается компьютер? Или музыка играть не начинает? Или всё-таки программа не компилируется или падает в процессе выполнения? И если не компилируется, то что говорит компилятор?
MerlinLegend
1 / 1 / 0
Регистрация: 11.04.2011
Сообщений: 109
25.10.2012, 12:36  [ТС] #7
Да вы правы. Ошибка на переменные которые не объявлены.
silent_1991
Эксперт С++
4963 / 3039 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
25.10.2012, 12:36 #8
MerlinLegend, видимо, недостаточно прав. Код показывайте.
MerlinLegend
1 / 1 / 0
Регистрация: 11.04.2011
Сообщений: 109
25.10.2012, 14:04  [ТС] #9
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <iostream>
#include <string>
#include <list>
#include <algorithm>
 
// Класс "Идентификатор"
// Поскольку это только пример, то в данном случае является просто обёрткой над
// строкой. В реалиности может содержать много дополнительной информации, такой,
// как тип переменной, признак используемости, уровень вложенности и так далее.
class Identifier
{
public:
    // Задаётся имя переменной при создании
    Identifier(const std::string &name):
    m_name(name)
    {
    }
 
public:
    // Получается имя переменной
    std::string name() const
    {
        return m_name;
    }
    
private:
    std::string m_name;
};
 
// Необходимо для поиска переменной по имени
bool operator==(const Identifier &left, const Identifier &right)
{
    return left.name() == right.name();
}
 
// Функция, вычисляющая хэш
// Принимает идентификатор, хэш которого надо посчитать
// Возвращает вычисленный хэш
size_t hash(const Identifier& id)
{
    return size_t(id.name()[0]);
}
// Класс исключение "Идентификатор не найден"
// Нужен для выдачи сообщения о том, что идентификатор не найден в таблице,
// наружу функции поиска идентификатора
class IDNotFoundException : std::exception
{
public:
    IDNotFoundException(const std::string id_name):
    m_what(std::string("Identifier \'") + id_name + "\' not found!")
    {
    }
    
    virtual ~IDNotFoundException() throw()
    {
    }
    
public:
    const char *what() const throw()
    {
        return m_what.c_str();
    }
    
private:
    std::string m_what;
};
 
// Класс "Хэш-таблица", основанная на методе цепочек
// Метод цепочек заключается в следующем: таблица представляет собой массив
// связных списков фиксированного размера. Вычисленный хэш-функцией хэш является
// индексом в этом массиве списков. Известно, что список по этому индексу будет
// содержать все идентификаторы, для которых функция вернула одинаовый хэш.
// Осталось только найти идентификатор в данном списке и возвратить ссылку на
// него.
class HashTable
{
public:
   size_t collisions_count() const
{
    size_t result = 0;
    
    for (size_t i = 0; i < hasn_table_size; ++i)
        if (m_hash_table[i].size() > 1)
            ++result;
    
    return result;
}
public:
    // Добавление идентификатора в хэш-таблицу
    void add(const Identifier &id)
    {
        // Добавление идентификатора в список, расположенный в таблице по
        // индексу, вычисленному хэш-функцией (с учётом смещения)
        m_hash_table[hash(id) - min_hash_value].push_back(id);
    }
    
    // Поиск идентификатора в таблице по имени
    Identifier &get(const std::string &id_name)
    {
        // Сохраняется ссылка на список, в котором потенциально будет
        // расположен идентификатор (для простоты)
        std::list<Identifier>& line = m_hash_table[hash(id_name) - min_hash_value];
        
        // Поиск идентификаторы в списке по имени
        std::list<Identifier>::iterator it =
            std::find(line.begin(), line.end(), id_name);
        
        // Если при поиске были просмотренны все элементы списка,и ни один не
        // подошёл - сообщаем о том, что идентификатор не найден, посредством
        // исключения
        if (it == line.end())
            throw IDNotFoundException(id_name);
        
        // Если идентификатор найден - возвращаем ссылку на него
        return *it;
    }
    
private:
    // Хэш-таблица - массив связных списков идентификаторов
    std::list<Identifier> m_hash_table[hash_table_size];
};
 
int main()
{
    // Создаём хэш-таблицу
    HashTable ht;
    
    // Добавляем в неё различные идентификаторы
    ht.add(Identifier("a"));
    ht.add(Identifier("aa"));
    ht.add(Identifier("if"));
    ht.add(Identifier("fi"));
    
    // На случай, если идентификатор не будет найден, заворачиваем код поиска
    // идентификаторов в блок try/catch
    try
    {
        // Выводим на экран информацию о различных идентификаторах
        std::cout << ht.get("a").name() << std::endl;
        std::cout << ht.get("aa").name() << std::endl;
        std::cout << ht.get("if").name() << std::endl;
        std::cout << ht.get("fi").name() << std::endl;
        // Проверяем случай, когда идентификатор не должен быть найден
        std::cout << ht.get("hello").name() << std::endl;
    }
    catch (const IDNotFoundException &ex)
    {
        // Если идентификатор не найден - сообщаем об этом
        std::cerr << ex.what() << std::endl;
    }
    
    return 0;
}
silent_1991
Эксперт С++
4963 / 3039 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
25.10.2012, 14:07 #10
MerlinLegend, е-моё... Так это программа сама ругается на необъявленный идентификатор? Так и должно быть, я специально показал её реакцию на попытку поиска в таблице отсутствующей записи. Вы пробовали разбираться в коде вообще? Вы понимаете, чего от вас хотят в задании?

Добавлено через 52 секунды
Я же даже комментарий написал специально для... А, ладно...
Строка 143-144:
C++
1
2
// Проверяем случай, когда идентификатор не должен быть найден
std::cout << ht.get("hello").name() << std::endl;
MerlinLegend
1 / 1 / 0
Регистрация: 11.04.2011
Сообщений: 109
25.10.2012, 17:17  [ТС] #11
и что в этой строке не так?
silent_1991
Эксперт С++
4963 / 3039 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
25.10.2012, 17:20 #12
MerlinLegend, в этой строке сказано, что специально проверяется случай поиска идентификатора в таблице в то время, когда такого идентификатора там нет. Или у вас всё-таки компилятор ругается на необъявленные переменные? Вообще, почему мне приходится на протяжении 5 сообщений вытягивать из вас информацию? Кому из нас двоих нужна помощь?
MerlinLegend
1 / 1 / 0
Регистрация: 11.04.2011
Сообщений: 109
25.10.2012, 18:19  [ТС] #13
Мне нужна помощь. компилятор ругается на необъявленные переменные
silent_1991
Эксперт С++
4963 / 3039 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
25.10.2012, 18:37 #14
MerlinLegend, вы читать умеете?
Цитата Сообщение от silent_1991 Посмотреть сообщение
И если не компилируется, то что говорит компилятор?
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
6447 / 3094 / 306
Регистрация: 04.12.2011
Сообщений: 8,567
Записей в блоге: 4
25.10.2012, 18:46 #15
Цитата Сообщение от MerlinLegend Посмотреть сообщение
Мне нужна помощь. компилятор ругается на необъявленные переменные
MerlinLegend, это Ваш вывод о том, что выводит компилятор. А Вы возьмите и скопируйте содержимое output window debugera, а потом выкладывайте его сюда. Съэкономите время.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.10.2012, 18:46
Привет! Вот еще темы с ответами:

Каким образом unordered_map выдает правильное значение для ключа, если его хеш функция допускает коллизии? - C++
Читаю книгу джосаттис стандартная библиотека c++, там в разделе про unordered_map есть описание данного контейнера Раз уж каждый...

хеш таблица - C++
в чем ошибка #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;iterator&gt; #include &lt;algorithm&gt; #include &lt;string&gt; struct...

Хеш таблицы - C++
Начал изучать хеш таблицы. Подскажите насчёт хеш таблиц с открытимы адрессами: - Должны ли мы инициализировать значение ключа...

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
25.10.2012, 18:46
Ответ Создать тему
Опции темы

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