-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathHashing-Quadratic probing
85 lines (81 loc) · 1.65 KB
/
Hashing-Quadratic probing
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
//this is a hacker rank code for a problem using qudratic hashing
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <array>
using namespace std;
void print_data(int a[],int n);
void insert_data(int a[],int data,int n);
void delete_data(int a[],int data,int n);
void search(int a[],int data,int n);
int probe=0;
int main() {
int n,q,ch,data;
cin>>n>>q;
int a[n];
for(int i=0;i<n;i++)
a[i]=0;
for(int i=0;i<q;i++)
{
cin>>ch;
switch(ch)
{
case 1:cin>>data;
insert_data(a,data,n);
break;
case 2:cin>>data;
probe=0;
search(a,data,n);
cout<<probe+1<<endl;
break;
case 3:cin>>data;
delete_data(a,data,n);
break;
case 4:print_data(a,n);
cout<<endl;
}
}
return 0;
}
void insert_data(int a[],int data,int n)
{
int index,i=0;
index=data % n;
while(a[index]!=0 && a[index]!=-1 )
{
i++;
index=(data%n+i*i)%n;
}
a[index]=data;
}
void print_data(int a[],int n)
{
for(int i=0;i<n;i++)
if(a[i]==0 or a[i]==-1)
cout<<"NULL ";
else cout<<a[i]<<" ";
}
void delete_data(int a[],int data,int n)
{
int index,i=0;
index=data % n;
while(a[index]!=data)
{
i++;
index=(data%n+i*i)%n;
}
a[index]=0;
}
void search(int a[],int data,int n)
{
int index,i=0;
index=data % n;
while(a[index]!=data)
{
probe++;
i++;
index=(data%n+i*i)%n;
}
}