0 / 0 / 0
Регистрация: 02.04.2016
Сообщений: 102
1

Построение словарей на основе метода открытого хеширования данных (нужны комментарии)

15.06.2019, 20:42. Показов 1290. Ответов 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
#include <vcl.h>
#pragma hdrstop
#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#pragma argsused
struct link//Список значений
{
char* value;
link* next;
};
class dict // класс, представл¤ющий собой словарь
{
private:
link** spisok;//Массив списков класса dict
int Hash(char* value);//Функция вычисления хэша
public:
dict();//Конструктор
link* Find(char* value);
void Insert(char* value);
bool Delete(char* value);
~dict();//Деструктор
};
void SearchV(dict* sp);
void InsertV(dict* sp);
void DeleteV(dict* sp);
const int maxstrlen = 100;
dict::dict() // конструктор
{
this->spisok = new link*[256];
for (int i = 0; i < 256; i++)
{
this->spisok[i] = NULL;
}
}
int dict::Hash(char* value) // хеш-функци¤
{
//Хэш - код первого символа в значении
//Основные коды символов в ASCII таблице 0-255 включительно, поэтому скорее всего не выйдем за пределы массива
return value[0];
}
link* dict::Find(char* value) // метод поиска строки в словаре
{
//Получаем i-ый список в массиве списков(лучше Hash(value)%256), т.к. есть символы которые выходят из этого диапазона
link* rez = spisok[Hash(value)];
if (rez)//если ссылка на rez не равна 0((т.е. не NULL)т.к. 0 в приведении к bool это false)
{
while (strcmp(rez->value, value) != 0)//значение в списке не равно переданному значению(сравнение по строкам)
{
if (rez->next)//Если существует следующий элемент, то переходим на него
{
rez = rez->next;
}
else//Иначе выходим из цикла(т.е. дошли до последнего элемента в списке)
{
break;
}
}
if (strcmp(rez->value, value) == 0)//Если значение текущего элемента в списке равно переданному, то возвращаем этот элемент
{
return rez;
}
}
//Во всех остальных случаях возвращаем NULL
return NULL;
}
void dict::Insert(char* value) // метод вставки строки в словарь
{
int hash = Hash(value);//Вычисляем хэш
link* current = spisok[hash];//Получаем список из массива списков
if (current)//Если он не пустой
{
while (current->next)//Идём в конец массива
{
current = current->next;
}
//Создаем новый элемент списка и задаём ему значение
current->next = new link();
current->next->value = value;
}
else
{
//Иначе просто создаём новый элемент списка(задаём ему значение), и делаем его первым в массиве списков с текущем хэшом
current = new link();
current->value = value;
spisok[hash] = current;
}
}
bool dict::Delete(char* value) // удаление элемента
{
int hash = Hash(value);
link* current = spisok[hash];
//Возвращаем true если элемент удалён, иначе false
if (current)
{
link* prev = current;
//Получение предыдущего элемента перед, элементом с переданным значением
while (current->next && strcmp(current->next->value, value) != 0)
{
prev = current;
current = current->next;
}
//Если у текущего элемента существуют значения
if (current->value)
{
//Если у текущего элемента есть следующий элемент
if (current->next)
{
//Если значение следующего элемента равно переданному, то выкидываем его из списка
if (strcmp(current->next->value, value) == 0)
{
link* next = current->next->next;
current->next = next;
return true;
}
}
//Если нету следующего элемента
else
{
//Если мы вначале списка
if (current == spisok[hash])
{
//Выкидываем список
spisok[hash] = NULL;
}
//Иначе если существует предыдущий
else if (prev)
{
//То удаляем текущий
prev->next = NULL;
current = NULL;
}
return true;
}
}
}
return false;
}
dict::~dict()//Деструктор
{
//Освобождаем память от массива списков
delete[] spisok;
}
int main(int argc, char* argv[])
{
dict spisok = dict();
while (1)
{
cout << endl << "Dejstvie: " << endl;
cout << "1) Search" << endl;
cout << "2) Insert" << endl;
cout << "3) Delete" << endl;
cout << "4) Exit" << endl;
int value = 0;
cin >> value;
cout << endl;
switch (value)
{
case 1: SearchV(&spisok); break;
case 2: InsertV(&spisok); break;
case 3: DeleteV(&spisok); break;
case 4: return 0;
}
}
}
void SearchV(dict* sp)
{
char* input = new char[maxstrlen];
cout << "Vvedite znachenie" << endl;
cin >> input;
link* value = sp->Find(input);
if (value)
{
cout << "Element najden" << endl;
}
else
{
cout << "Element ne najden" << endl;
}
}
void InsertV(dict* sp)
{
char* input = new char[maxstrlen];
cout << "Vvedite znachenie" << endl;
cin >> input;
sp->Insert(input);
cout << "Element dobavlen" << endl;
}
void DeleteV(dict* sp)
{
char* input = new char[maxstrlen];
cout << "Vvedite znachenie" << endl;
cin >> input;
if (sp->Delete(input))
{
cout << "Element udalen" << endl;
}
else
{
cout << "Element ne najden" << endl;
}
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
15.06.2019, 20:42
Ответы с готовыми решениями:

Реализация поиска на основе метода хеширования
Ребята, если кто знает где можно найти толковые примеры(листинги) с применением хэштаблиц,...

Построение графика и комментарии по коду нужны
Прокоментируйте код вкратце procedure TForm1.FormCreate(Sender: TObject); begin ...

Хеш-функции. Метод открытого хеширования
Написать программу, которая реализует метод открытого хеширования и хеш-функцией, основанной на...

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

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
15.06.2019, 20:42
Помогаю со студенческими работами здесь

Построение графика на основе данных из БД
возможно, эту тему лучше было бы создать в ASP.NET. суть моего вопроса такова: есть БД. из нее я...

Построение графика на основе введенных данных
Имеется программа, на основе введенных данных, строится график, но в результате вместо графика в...

Построение прогноза на основе статистических данных
Здравствуйте. У меня возникла проблема при решении производственной задачи. Большой ресторан...

Построение графиков на основе данных из Lotus
Всем доброго времени суток! Мне поставили задачу визуализировать данные из Лотуса в виде графика....


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru