Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
_Edith
0 / 0 / 1
Регистрация: 02.04.2011
Сообщений: 99
#1

Структуры данных. Хеш-таблицы и с чем их употребляют - C++

05.01.2015, 00:49. Просмотров 247. Ответов 0
Метки нет (Все метки)

Столкнулся с такой проблемой как хеширование. Помогите, пожалуйста, разобраться, подкиньте материала.
Суть в том, что я получил задание: захешировать таблицу методом деления, тип данных - числа, метод решения коллизий - открытая адресация. И я никак не могу понять, что вообще надо делать, что писать и куда писать.
К примеру есть такая программа, все тоже самое, только тип входных данных строки, помогите разобраться в коде, если не трудно=)
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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
#include <iostream>
#include <clocale>
#include <string>
#include <windows.h>
 
using namespace std;
 
#define свободно true
#define занято false
 
const int n = 256;
bool fl[n];
 
int h(string key, int size)
{
    int s = 0;
 
    for (int i = 0; i < key.size(); ++i)
    {
        s += key[i];
    }
 
    return (s%size);
}
 
int menu()
{
    system("cls");
 
    cout << "ВЫБЕРИТЕ ИНТЕРЕСУЮЩИЕ ВАС ДЕЙСТВИЕ:" << endl;
    cout << "1 - поиск определенного элемента" << endl;
    cout << "2 - просмотр хеш таблицы" << endl;
    cout << "3 - удаление элемента из таблицы" << endl;
    cout << "4 - выход из программы" << endl;
 
    int a = -1;
 
    while ((a > 4) || (a < 1))
    {
        cout << "введите число, из списка действий" << endl;
        if (!(cin >> a))
            cin.clear();
    }
 
    return a;
}
 
int found(string data, string *a, int n)
{
    int key = h(data, n);
 
    if (fl[key] == занято)
    {
        if (a[key] == data)
            return key;
    }
 
    for (int i = key + 1; i < n; ++i)
    {
        if (fl[i] == занято)
        {
            if (a[key] == data)
                return i;
        }
    }
 
    for (int i = key - 1; i > -1; --i)
    {
        if (fl[i] == занято)
        {
            if (a[key] == data)
                return i;
        }
    }
 
    return -1;
}
int main()
{
    setlocale(LC_ALL, "");
 
    string a[n], data;
 
    int key, boolean;
    bool flag, work = true;
 
    for (int i = 0; i < n; ++i)
    {
        fl[i] = свободно;
        a[i] = "";
    }
 
    cout << "Введите data's" << endl;
 
    while (getline(cin, data))
    {
        key = h(data, n);
 
        if (fl[key] == свободно)
        {
            a[key] = data;
            fl[key] = занято;
        }
 
        else
        {
            flag = false;
            for (int i = key + 1; i < n; ++i)
            {
                if (fl[i] == свободно && flag == false)
                {
                    a[i] = data;
                    flag = true;
                    fl[i] = занято;
                }
            }
                
            if (!flag && flag == false)
            {
                for (int i = key - 1; i > -1; i--)
                {
                    if (fl[i] == свободно)
                    {
                        a[i] = data;
                        flag = true;
                        fl[i] = занято;
                    }
                }
            }
                
            if (!flag)
            {
                cout << "превышен лимит, введенно больше чем " << n << " элементов";
 
                system("pause");
 
                break;
            }
        }
    }
    cin.clear();
 
    while (work)
        switch (menu())
        {
            case 1:
                system("cls");
 
                cout << "введите элемент который нужно найти" << endl;
                getline(cin, data);
                getline(cin, data);
 
                boolean = found(data, a, n);
 
                if (boolean == -1)
                {
                    cout << "такого элемента нет!" << endl;
                }
 
                else
                {
                    cout << "элемен " << data << " найден и его кэш - " << boolean << endl;
                }
 
                system("pause");
 
                break;
 
            case 2:
                system("cls");
 
                for (int i = 0; i < n; ++i)
                {
                    if (fl[i] == занято)
                    {
                        cout.width(3);
                        cout << right << i << ": ";
                        cout << a[i];
                        cout << endl;
                    }
                }
 
                system("pause");
 
                break;
 
            case 3:
                system("cls");
 
                cout << "введите элемент который нужно удалить" << endl;
                getline(cin, data);
                getline(cin, data);
 
                boolean = found(data, a, n);
 
                if (boolean == -1)
                {
                    cout << "такого элемента нет!" << endl;
                }
 
                else
                {
                    fl[boolean] = свободно;
                }
 
                system("pause");
 
                break;
 
            case 4:
                work = false;
        }
 
    return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.01.2015, 00:49
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Структуры данных. Хеш-таблицы и с чем их употребляют (C++):

Понятие структуры данных. Элементарные структуры данных. Простые структуры данных
Понятие структуры данных. Элементарные структуры данных. Простые структуры...

хеш-таблицы
Реализовать ассоциативный массив в виде хеш-таблицы с операциями добавления,...

Хеш таблицы
Начал изучать хеш таблицы. Подскажите насчёт хеш таблиц с открытимы...

Реализация хеш-таблицы
Всем привет. Нужна помощь с заданием:

для чего нужны хеш таблицы?
для чего нужны хеш таблицы? если есть массивы )

Не могу найти ошибку. Хеш-таблицы
Программа работает, в принципе, правильно, но есть маленькие погрешности при...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.01.2015, 00:49
Привет! Вот еще темы с решениями:

Хеш-таблицы: string subscript out of range
#include &lt;iostream&gt; #include &lt;string.h&gt; #include &lt;string&gt; using namespace...

Уменьшить число коллизий хеш-таблицы
Задание: хеш-таблица с мультипликативной хеширующей функцией (метод умножения)...

Данные о читателях должны быть организованны в виде хеш-таблицы
Данные о каждом читателе должны содержать: № читательского билета – строка...

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


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

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

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