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
|
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
//We need to define our list structure
typedef struct _List_t{
char *string;
struct _List_t *next;
}List_t;
//We need to define our hash table itself
typedef struct _HashTable_t{
int size;
List_t **table;
}HashTable_t;
HashTable_t *CreateTable(int);
HashTable_t *CreateTable(int size)
{
HashTable_t *NewTable;
//We wil need to alocate memory both for the table structure
//and the table itself
NewTable=(HashTable_t*)malloc(sizeof(HashTable_t));
NewTable->table=(List_t**)malloc(sizeof(HashTable_t));
//Initially we will need for the table elements to be NULL
for(int i=0;i<size;i++)
NewTable->table[i]=NULL;
//We also need to set size of the table
NewTable->size=size;
return NewTable;
}
unsigned int hash(HashTable_t *hashtable, char *str)
{
int a,b,p;
unsigned int hashval=0;
for(int i=0;i<<9; i++)
hashval = str[i] + (hashval << 5) - hashval;
return hashval%hashtable->size;
}
//We need to define our search function
List_t *search(HashTable_t *hashtable, char *str)
{
List_t *list;
unsigned int hashval=hash(hashtable,str);
for(list=hashtable->table[hashval];list!=NULL;list=list->next)
if(strcmp(str,list->string)==0)
{
return list;
}
return NULL;
}
//We need the insertion function
int insert(HashTable_t *hashtable, char *str)
{
List_t *NewList;
List_t *CurentList;
unsigned int hashval=hash(hashtable,str);
NewList=(List_t*)malloc(sizeof(List_t));
//Is the item already in the list?
CurentList=search(hashtable,str);
//Handling a positive search
if(CurentList !=NULL) return 2;
//Finally the insertion
NewList->string=_strdup(str);
NewList->next=hashtable->table[hashval];
hashtable->table[hashval]=NewList;
return 0;
}
//We'll need to implement 2 clear functions:one for clearing a specific value in the table, and another one to clear up the table itself
void ClearKey(HashTable_t *hashtable,char *str);
void ClearKey(HashTable_t *hashtable,char *str){
List_t *list,*temp;
int hashval=hash(hashtable,str);
//We position ourselves on index of the table, because that's where our head of the list is
list=hashtable->table[hashval];
while(list!=NULL){
//If we found what we are looking for erase it
if(list->string=str)
temp=list;
list=list->next;
free(temp);
}
}
void ClearTable(HashTable_t);
void ClearTable(HashTable_t *hashtable)
{
List_t *list,*temp;
if(hashtable!=NULL)
for(int i=0;i<hashtable->size;i++){
list=hashtable->table[i];
while(list!=NULL){
temp=list;
list=list->next;
free(temp); }
}
free(hashtable->table);
free(hashtable);
}
void main()
{
HashTable_t *MyHashTable;
char *s;
int sel,TableSize=12;
MyHashTable=CreateTable(TableSize);
printf("HashTable created!\n");
for(int i=0;i<MyHashTable->size;i++)
printf("%d",MyHashTable->table[i]);
printf("Select an operation\n");
printf("1. Insert 2. Search 3. Erase Other=Quit\n");
scanf("%c",&sel);
printf("Your selection is:%c",sel);
printf("\nEnter the key:");
s=(char*)malloc(sizeof(10));
scanf("%s",s);
printf("Key is %s",s);
while(sel<5){
if(sel=1)
insert(MyHashTable,s);
else if(sel=2)
search(MyHashTable,s);
else if(sel=3)
ClearKey(MyHashTable,s);
else
printf("Invalid Selection");
}
getch();
}
|
