forked from sysprog21/phonebook
-
Notifications
You must be signed in to change notification settings - Fork 0
/
phonebook_hash.c
69 lines (62 loc) · 1.57 KB
/
phonebook_hash.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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "phonebook_hash.h"
/* hash version */
unsigned int bkdrHash(char *str)
{
unsigned int seed = 131;
unsigned int hash = 0;
while (*str) {
hash = hash * seed + (*str++);
}
return (hash % HASHTABLE_SIZE);
}
hashTable *initHashTable()
{
hashTable *newHashTable = NULL;
newHashTable = (hashTable *) malloc(sizeof(hashTable));
newHashTable->list = (entry **) malloc(sizeof(entry*)*HASHTABLE_SIZE);
for(int i=0; i<HASHTABLE_SIZE; i++)
newHashTable->list[i] = NULL;
return newHashTable;
}
void freeHashTable(hashTable *ht)
{
for(int i=0; i<HASHTABLE_SIZE; i++) {
entry *e = ht->list[i];
if(!e) {
free(e);
continue;
}
while (e->pNext) {
entry *next = e->pNext;
e->pNext = next->pNext;
free(next);
}
free(e);
}
free(ht->list);
free(ht);
}
entry *findName(char lastName[], hashTable *ht)
{
entry *e;
unsigned int index = bkdrHash(lastName);
for(e = ht->list[index]; e; e = e->pNext) {
if(!strcasecmp(lastName, e->lastName))
return e;
}
return NULL;
}
void append(char lastName[], hashTable *hashTable)
{
/* allocate memory for the new entry and put lastName */
unsigned int index = bkdrHash(lastName);
entry *newEntry;
newEntry = (entry *) malloc(sizeof(entry));
strcpy(newEntry->lastName, lastName);
newEntry->pNext = hashTable->list[index];
hashTable->list[index] = newEntry;
}