Добрый вечер! Пытаюсь написать программу, которая будет работать как хеш-таблица. Для вычисления первичного индекса используется символьный ключ (строка преобразуется в int по заданному правилу), а вторичный индекс должен вычисляться методом квадратичных проб. И вот с этим у меня загвоздка. В коде отметил где, насколько я понимаю, должен генерироваться этот вторичный индекс, но ума не приложу как это осуществить. Надеюсь на вашу помощь!
| 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
| class Program
{
static void Main(string[] args)
{ opentable myTable = new opentable();
myTable.insert(109875, "Anna");
myTable.insert(103765, "Harry");
myTable.insert(100364, "Benedict");
myTable.insert(202120, "Piter");
myTable.insert(202120, "Piter");
myTable.insert(202120, "Piter");
myTable.print();
Console.ReadKey();
}
}
//хеш-таблица метод цепочек
class opentable
{
class hashnode
{
int key;
string data;
hashnode next;
public hashnode(int key, string data)
{
this.key = key;
this.data = data;
next = null;
}
public int getkey()
{
return key;
}
public string getdata()
{
return data;
}
public void setNextNode(hashnode obj)
{
next = obj;
}
public hashnode getNextNode()
{
return this.next;
}
}
hashnode[] table;
const int size = 10;
public opentable()
{
table = new hashnode[size];
for (int i = 0; i < size; i++)
{
table[i] = null;
}
}
public void insert(int key, string data)
{
hashnode nObj = new hashnode(key, data);
int hash = key % size; // первичный индекс
while (table[hash] != null && table[hash].getkey() % size != key % size)
{
hash = (hash + 1) % size;
}
if (table[hash] != null && hash == table[hash].getkey() % size)
{
//здесь должен генерироваться вторичный индекс
nObj.setNextNode(table[hash].getNextNode());
table[hash].setNextNode(nObj);
return;
}
else
{
table[hash] = nObj;
return;
}
}
public string retrieve(int key)
{
int hash = key % size;
while (table[hash] != null && table[hash].getkey() % size != key % size)
{
hash = (hash + 1) % size;
}
hashnode current = table[hash];
while (current.getkey() != key && current.getNextNode() != null)
{
current = current.getNextNode();
}
if (current.getkey() == key)
{
return current.getdata();
}
else
{
return "nothing found!";
}
}
public void remove(int key)
{
int hash = key % size;
while (table[hash] != null && table[hash].getkey() % size != key % size)
{
hash = (hash + 1) % size;
}
//a current node pointer used for traversal, currently points to the head
hashnode current = table[hash];
bool isRemoved = false;
while (current != null)
{
if (current.getkey() == key)
{
table[hash] = current.getNextNode();
Console.WriteLine("entry removed successfully!");
isRemoved = true;
break;
}
if (current.getNextNode() != null)
{
if (current.getNextNode().getkey() == key)
{
hashnode newNext = current.getNextNode().getNextNode();
current.setNextNode(newNext);
Console.WriteLine("entry removed successfully!");
isRemoved = true;
break;
}
else
{
current = current.getNextNode();
}
}
}
if (!isRemoved)
{
Console.WriteLine("nothing found to delete!");
return;
}
}
public void print()
{
hashnode current = null;
for (int i = 0; i < size; i++)
{
current = table[i];
while (current != null)
{
Console.Write(current.getdata() + " ");
current = current.getNextNode();
}
Console.WriteLine();
}
}
} |
|
(
