Как реализовать данный код с помощью вектора
| 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
| class Table
{
public:
Table(int);
int Hash(int)const;
void Put(int);
void show()const;
~Table();
private:
struct TElem
{
int number = 0;
TElem *next = nullptr;
};
TElem *bucket;
const int COUNT_BUCKET;//число блоков
int PRIMARY_COUNT_BLOCK = 100;
int COUNT_ELEM = 0;//кол-во всех элементов в данный момент
int COUNT_ELEM_IN_HEAD_BUCKET = 0;//кол-во элементов в голове
int LEVEL = 0;//2^LEVEL x N
int LEVEL_UP = 100;// для проверки 90%
void Destructor(TElem*);
};
Table::Table(int a = 1600) : COUNT_BUCKET(a)
{
bucket = new TElem[COUNT_BUCKET];
}
int Table::Hash(int number)const
{
return number % (static_cast<int>(pow(2, LEVEL)) * PRIMARY_COUNT_BLOCK);
}
void Table::Put(int number)
{
int hash_result = Hash(number);
if (COUNT_ELEM_IN_HEAD_BUCKET == COUNT_BUCKET) LEVEL = LEVEL;
else if (COUNT_ELEM_IN_HEAD_BUCKET >= LEVEL_UP / 100 * 95)
{
++LEVEL;
LEVEL_UP *= 2;
}
if (!bucket[hash_result].number)
{
bucket[hash_result].number = number;
++COUNT_ELEM;
++COUNT_ELEM_IN_HEAD_BUCKET;
}
else
{
TElem *temp = nullptr;
for (temp = &bucket[hash_result];; temp = temp->next)
{
if (temp->number == number) return;
if (temp->next == nullptr) break;
}
temp->next = new TElem;
temp->next->number = number;
++COUNT_ELEM;
}
}
void Table::show()const
{
TElem *temp = nullptr;
int i = 0;
for (int i = 0; i < COUNT_BUCKET; ++i)
{
for (temp = &bucket[i]; temp != nullptr; temp = temp->next)
{
cout << temp->number << " ";
Sleep(50);
}
cout << endl;
}
}
void Table::Destructor(TElem* ptr)
{
if (ptr->next != nullptr)
{
Destructor(ptr->next);
delete ptr;
}
else return;
}
Table::~Table()
{
for (int i = 0; i < COUNT_BUCKET; ++i)
{
Destructor(&bucket[i]);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
setlocale(0, "Rus");
srand((unsigned)time(NULL));
Table one;
for (int i = 0; i <= 500; i++)
one.Put(rand()%1000 + 1);
for (int i = 0; i <= 500; i++)
one.Put(rand() % 1000 + 1);
for (int i = 0; i <= 500; i++)
one.Put(rand() % 1600 + 1);
for (int i = 0; i <= 500; i++)
one.Put(rand() % 1600 + 1);
for (int i = 0; i <= 500; i++)
one.Put(rand() % 1600 + 1);
one.show();
cin.ignore(cin.rdbuf()->in_avail());
cin.get();
return 0;
} |
|
(
