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
|
#include <cstddef>
#include <iostream>
using namespace std;
template <class K, class V>
struct Node {
K key;
V value;
Node<K,V> *next;
};
template <class K, class V>
struct Map {
Node<K,V> **table;
int size;
};
template <class K, class V>
void initialize(Map<K,V> &map, int size)
{
map.table = new Node<K,V> *[size]; //Create a dynamic array of input size.
map.size = size; //Store the size in the struct Map.
for(int i = 0; i < size; i++) //Set everything in the array to NULL.
map.table[i] = NULL;
}
template <class K, class V>
void destroy(Map<K,V> &map)
{
int index = 0;
Node<K,V> *scout = map.table[index];
while( index != map.size)
{
if((scout == NULL) && (index != (map.size-1))) {
index++;
delete scout;
scout = map.table[index];
}
else if((scout == NULL) & (index == (map.size-1))) {
delete scout;
index++;
}
else {
Node<K,V> *destroyer = scout -> next; //Points destroyer at next node
delete scout; //Deletes the node that Q.head is pointing at.
scout = destroyer; //Points Q.head at the node destroyer is pointing at.
if(destroyer == NULL) {
index++;
scout = map.table[index];
}
}
}
delete [] map.table;
map.table = NULL;
map.size = 0;
}
template <class K, class V>
void assign(Map<K,V> &map, K id, V contents)
{
Node<K,V> *item = new Node<K,V>; //Create a new node to enter values into.
//Fill the node with specified contents...
item -> key = id;
item -> value = contents;
item -> next = NULL;
int index = id % map.size; //Get the hash for the new key so we know what index to put it in.
if(map.table[index] == NULL) {//If the index on the array has no nodes in it...
map.table[index] = item;
return;
}
if(has_key(map, id) == true) {
Node<K,V> *scout = map.table[index]; //Create a searching node.
while( true ) {
if(scout -> key == id) {
scout -> value = contents;
break;
}
scout = scout -> next;
}
delete item; //Get rid of the node we created since we are just overwriting a previous one.
}
else {
//If the index already has a value in it, we must add the created node to a linked list on that index...
Node<K,V> *walker = map.table[index]; //Set a walker node to the first node in the table at the index.
while( true ) { //Walk through the indexed linked list.
if(walker -> next == NULL) //This will tell us if we've reached the end or not.
break;
walker = walker -> next; //Walk through the nodes at that particular index.
}
walker -> next = item; //When we find the end with the while loop above, walker will be at the last node on the list
//so we set the next value of walker, which should be NULL, to the newly created item.
}
}
template <class K, class V>
void remove(Map<K,V> &map, K id)
{
int index = id % map.size; //Get the index the key is at.
Node<K,V> *scout = map.table[index]; //Create a searching node.
Node<K,V> *previous = scout; //Create a tracker node so we know what node is behind us...(refer to following while loop)
while( true ) {
if(map.table[index] -> key == id) { //If the key is the first node at the index.
map.table[index] = map.table[index] -> next; //Sets the new first node to the next node.
delete scout;
break;
}
if(scout -> key == id) {
previous -> next = scout -> next; //This will point around the node we want to remove.
delete scout;
break;
}
scout = scout -> next; //Make scout take a step to next node.
}
}
template <class K, class V>
bool has_key(Map<K,V> map, K id) //**********This function is NOT working properly.
{
int column = id % map.size; //Find the index value that the key would be stored at, if it exists.
Node<K,V> *scout = map.table[column];
if(map.table[column] == NULL) //If the column has nothing in it...
return false;
while( true ) {
if(scout -> key == id)
return true;
if(scout -> next == NULL)
break;
scout = scout -> next;
}
return false;
}
template <class K, class V>
V lookup(Map<K,V> map, K id) //**************This function is working properly.
{
int index = id % map.size; //Find the index that the key is at.
Node<K,V> *scout = map.table[index]; //Create a searching node.
while( true ) {
if(scout -> key == id)
break;
if(scout -> next == NULL)
break;
scout = scout -> next;
}
return scout -> value;
}
// Overloaded hash functions, for different key types
int hash(int key, int size) {
return key % size;
}
int hash(char key, int size) {
return key % size;
}
| |
