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

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

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

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

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

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

Таблица строиться по методу цепочек с использованием хэш-функции, возращающий код первой буквы идентификатора. При выполнений программы подсчитывается число коллизий.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
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++
Ещё раз здравствуйте! Есть такое задание: Написать программу, которая реализует метод открытого хеширования и хеш-функцией,...

30
MerlinLegend
1 / 1 / 0
Регистрация: 11.04.2011
Сообщений: 109
25.10.2012, 18:52  [ТС] #16
(121): error C2065: hash_table_size: необъявленный идентификатор
(83): error C2065: hasn_table_size: необъявленный идентификатор
(95): error C2065: min_hash_value: необъявленный идентификатор
(95): error C2228: выражение слева от ".push_back" должно представлять класс, структуру или объединение
(103): error C2065: min_hash_value: необъявленный идентификатор
0
silent_1991
Эксперт С++
4984 / 3041 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
25.10.2012, 18:58 #17
MerlinLegend, а, ну ё-моё, правильно. Вы зачем из кода что-то удаляли?

Добавлено через 49 секунд
Я же не говорил "замените объявление трёх полей класса на метод collisions_count". Я сказал "добавить в класс метод".

Добавлено через 1 минуту
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
#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:
    static const size_t min_hash_value = int('A') + int('0');
    static const size_t max_hash_value = int('z') + int('z');
    static const size_t hash_table_size = max_hash_value - min_hash_value;
    
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;
    }
    
    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;
    }
    
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
    {
        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;
}
Наслаждайтесь.

Добавлено через 1 минуту
М, вот ещё что. Размер хэш-таблицы тоже поменялся. Поэтому строки 59-60 надо заменить на такие:
C++
1
2
    static const size_t min_hash_value = int('0');
    static const size_t max_hash_value = int('z');
1
MerlinLegend
1 / 1 / 0
Регистрация: 11.04.2011
Сообщений: 109
25.10.2012, 19:12  [ТС] #18
Спасибо за помощь. Но у меня снова ошибка (87): error C2065: hasn_table_size: необъявленный идентификатор
0
silent_1991
Эксперт С++
4984 / 3041 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
25.10.2012, 19:14 #19
MerlinLegend, ну как он может быть необъявленным, если он объявляется в 61 строке? Вы опять что-то лишнее удалили?
0
MerlinLegend
1 / 1 / 0
Регистрация: 11.04.2011
Сообщений: 109
25.10.2012, 19:16  [ТС] #20
Нет, все как вы вы говорили
0
silent_1991
Эксперт С++
4984 / 3041 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
25.10.2012, 19:17 #21
MerlinLegend, что у вас в 61 строке?
1
MerlinLegend
1 / 1 / 0
Регистрация: 11.04.2011
Сообщений: 109
25.10.2012, 19:18  [ТС] #22
Все в порядке. там проблема в букве была. надо было поменять n на h

Добавлено через 40 секунд
Спасибо
0
silent_1991
Эксперт С++
4984 / 3041 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
25.10.2012, 19:20 #23
MerlinLegend, это говорит о том, что надо всегда полностью приводить сообщения компилятора. Учитесь на своих ошибках.
0
MerlinLegend
1 / 1 / 0
Регистрация: 11.04.2011
Сообщений: 109
25.10.2012, 19:32  [ТС] #24
а где считает коллизии?
0
silent_1991
Эксперт С++
4984 / 3041 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
25.10.2012, 19:33 #25
MerlinLegend, в функции collisions_count, логично же.
0
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
6486 / 3130 / 307
Регистрация: 04.12.2011
Сообщений: 8,645
Записей в блоге: 5
25.10.2012, 20:15 #26
Опоздал, - удалил.
1
silent_1991
25.10.2012, 20:18
  #27

Не по теме:

IGPIGP, да уж разобрались)) Косяк, конечно, мой, поскольку функцию я не проверял, писал прямо здесь... Но всё-таки то количество постов, которое потребовалось, чтобы проблема решилась, несколько обескураживает...

1
IGPIGP
25.10.2012, 20:20
  #28

Не по теме:

Цитата Сообщение от silent_1991 Посмотреть сообщение
IGPIGP, да уж разобрались)) Косяк, конечно, мой, поскольку функцию я не проверял, писал прямо здесь... Но всё-таки то количество постов, которое потребовалось, чтобы проблема решилась, несколько обескураживает...
Да, бывает растормошить труднее, чем разобрать.

1
MerlinLegend
1 / 1 / 0
Регистрация: 11.04.2011
Сообщений: 109
28.10.2012, 18:31  [ТС] #29
Помогите пожалуйста этой программой. Надо чтобы она брала текст из текстового файла обрабатывала
и выводила итог. Заранее спасибо
0
intnower
0 / 0 / 0
Регистрация: 12.01.2012
Сообщений: 68
07.12.2013, 22:24 #30
Помогите, пожалуйста! Я не разобрался с функцией collisions_count. Что в ней нужно изменить?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.12.2013, 22:24
Привет! Вот еще темы с ответами:

Каким образом 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++
я хочу, чтобы у меня был массив структур, каждая из которых содержала некоторое значение и ссылку на следующий элемент этого массива ...


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

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

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