· 4 years ago · May 20, 2021, 03:22 PM
1#include <iostream>
2#include <windows.h>
3
4using namespace std;
5
6// Hash table element
7struct Zap
8{
9 int key;
10 char info;
11 Zap* next;
12};
13
14// Hash table
15struct Hash_Table
16{
17 Zap** table = nullptr;
18 int size = 0;
19
20 void create(int m)
21 {
22 table = new Zap*[m];
23 for (int i = 0; i < m; i++) table[i] = nullptr; // Make table empty
24 size = m;
25 }
26
27 void add(Zap data)
28 {
29 // If no table
30 if (table == nullptr) return;
31
32 Zap* spt = new Zap;
33 spt->key = data.key;
34 spt->info = data.info;
35
36 int i = data.key % size;
37 if (table[i] == nullptr)
38 {
39 // Create first element of Stack
40 table[i] = spt;
41 spt->next = nullptr;
42 }
43 else
44 {
45 // Add other elements
46 spt->next = table[i];
47 table[i] = spt;
48 }
49 // Table[i] is top of Stack[i]
50 }
51
52 Zap* search(int key)
53 {
54 if (table == nullptr) return nullptr;
55
56 int i = key % size;
57 Zap* spt = table[i];
58 while (spt)
59 {
60 if (spt->key == key) return spt;
61 spt = spt->next;
62 }
63 return nullptr;
64 }
65
66 void show()
67 {
68 Zap* spt;
69
70 for (int i = 0; i < size; i++)
71 {
72 cout << '[' << i << ']';
73 spt = table[i];
74 while (spt)
75 {
76 cout << " <- {" << spt->key << ", " << spt->info << "}";
77 spt = spt->next;
78 }
79 cout << endl;
80 }
81 }
82
83 void clear()
84 {
85 if (table == nullptr) return;
86
87 Zap* spt;
88
89 for (int i = 0; i < size; i++)
90 while (table[i])
91 {
92 spt = table[i];
93 table[i] = table[i]->next;
94 delete spt;
95 }
96
97 delete[] table;
98 table = nullptr;
99 size = 0;
100 }
101} H;
102
103void create_hash_table();
104void show_hash_table();
105void search_by_key();
106void search_max_key();
107
108int main()
109{
110 while (true)
111 {
112 cout << "+------------------------+" << endl;
113 cout << "| 1 - Create hash table |" << endl;
114 cout << "| 2 - Show hast table |" << endl;
115 cout << "| 3 - Search by key |" << endl;
116 cout << "| 4 - Search max key |" << endl;
117 cout << "| 5 - Exit |" << endl;
118 cout << "+------------------------+" << endl;
119
120 int menu;
121 cin >> menu;
122 switch (menu)
123 {
124 case 1: create_hash_table(); break;
125 case 2: show_hash_table(); break;
126 case 3: search_by_key(); break;
127 case 4: search_max_key(); break;
128 default: H.clear(); return 0;
129 }
130
131 cout << endl;
132 system("pause");
133 system("cls");
134 }
135}
136
137void create_hash_table()
138{
139 // If already exists
140 if (H.table) { cout << "Table already exist." << endl; return; }
141
142 // Input hash table size
143 int m;
144 cout << "Enter size: "; cin >> m;
145 if (m < 1) { cout << "Create error." << endl; return; }
146
147 // Input records number
148 int n;
149 cout << "Enter number of records: "; cin >> n;
150 if (n < 1) n = 0;
151
152 // Create
153 H.create(m);
154
155 // Add elements
156 Zap data;
157 for (int i = 0; i < n; i++)
158 {
159 data.key = rand() % 51;
160 data.info = rand() % 26 + 'a';
161 H.add(data);
162 }
163
164 cout << "Hash table created." << endl;
165}
166
167void show_hash_table()
168{
169 if (H.table == nullptr) { cout << "No hash table." << endl; return; }
170
171 cout << "Hash table:" << endl;
172 H.show();
173}
174
175void search_by_key()
176{
177 if (H.table == nullptr) { cout << "No hash table." << endl; return; }
178
179 int key;
180 cout << "Enter key: "; cin >> key;
181
182 Zap* ptr = H.search(key);
183
184 if (ptr) cout << "Key - " << ptr->key << ", Info - " << ptr->info << endl;
185 else cout << "Not found." << endl;
186}
187
188void search_max_key()
189{
190 if (H.table == nullptr) { cout << "No hash table." << endl; return; }
191
192 Zap* spt;
193 int key_max = -1;
194
195 for (int i = 0; i < H.size; i++)
196 {
197 spt = H.table[i];
198 while (spt)
199 {
200 if (key_max < spt->key) key_max = spt->key;
201 spt = spt->next;
202 }
203 }
204
205 if (key_max > -1) cout << "Max key: " << key_max << endl;
206 else cout << "Not found." << endl;
207}