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

Хэш-таблица. Метод цепочек. C++ - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Написать программу с определенными функциями (не объектно-ориентированное программирование) http://www.cyberforum.ru/cpp-beginners/thread515537.html
Предметная область – центр повышения квалификации. Объект – дисциплина (курс). Данные об объекте:  наименование;  преподаватель;  количество часов;  оплата;  число человек в группе. Функции: 1. Подсчитать среднее количество человек, приходящихся на одного преподавателя (учесть, что каждый преподаватель может вести несколько групп). 2. Вывести названия курсов, которые ведут...
C++ Работа в графическом режиме. Графические примитивы, движение объектов. В соответствии с возникающими ассоциациями от словесного описания картины, нарисовать ее графический аналог. Использовать различные цвета, функции рисования, эффекты анимации. На рисунке ОБЯЗАТЕЛЬНО должен присутствовать ДВИЖУЩИЙСЯ ОБЪЕКТ! Поляна, трава, цветы, бабочки, пчелы. http://www.cyberforum.ru/cpp-beginners/thread515528.html
Почему не возвращается значение через указатель из метода класса? C++
Вот решил проверить поведение указателя в программе (я только учу C++), как оказалось после выхода из метода, указатель не указывает на присвоеное ему значение внутри тела метода. Почему так происходит? TestingCPPSyntax.h #pragma once namespace Casper { class TestingCPPSyntax { public: TestingCPPSyntax(void); ~TestingCPPSyntax(void);
Решение мат задачи симплекс методом на С++. C++
Здравствуйте!Пожалуйста помогите написать программу на с++ для решение моей задачи вот она решенная симплекс методом:http://www.matburo.ru/Examples/Files/Simplex1.pdf
C++ С++ Факториал http://www.cyberforum.ru/cpp-beginners/thread515482.html
Надо написать программку на С++ которая вычисляет факториал числа n (факториал обозначается как n!). числа n в диапазоне от 1 до 12 вводятся клавой.
C++ непонятное строка? #include <iostream> using namespace std; int main() { void intfrac(float, float&, float&); float number, intpart, fracpart; do { cout << "\nEnter a real number: "; подробнее

Показать сообщение отдельно
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
11.03.2012, 12:29     Хэш-таблица. Метод цепочек. C++
Может так будет понятнее:
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
154
155
156
157
#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)
{
    // Если имя переменной составляет один символ - возвращается его код,
    // умноженный на два
    if (id.name().length() == 1)
        return 2 * size_t(id.name()[0]);
    
    // Иначе возвращается сумма кодов первых двух символов
    return size_t(id.name()[0]) + size_t(id.name()[1]);
}
 
// Класс исключение "Идентификатор не найден"
// Нужен для выдачи сообщения о том, что идентификатор не найден в таблице,
// наружу функции поиска идентификатора
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;
    }
    
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;
}
 
Текущее время: 18:04. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru