forked from embedded2015/phonebook
-
Notifications
You must be signed in to change notification settings - Fork 0
/
phonebook_opt.c
109 lines (99 loc) · 2.58 KB
/
phonebook_opt.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
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "phonebook_opt.h"
#include "phonebook_metaphone.h"
entry *findName(char lastname[], entry *pHead, entry **ht)
{
entry *temp;
unsigned int value = hash(lastname);
temp = ht[value];
while(temp != NULL) {
if (strcmp(lastname, temp->lastName) == 0)
return temp;
temp = temp->pNext;
}
/* string not found !! */
char meta[MAX_LAST_NAME_SIZE] = "";
int isFuzzy = FALSE;
metaphone(lastname, meta, MAX_LAST_NAME_SIZE);
printf("Fuzzy search:\n");
for (int i = 0; i < HASH_SIZE; i++) {
temp = ht[i];
while(temp != NULL) {
if (strcmp(temp->metaph, meta) == 0) {
printf("Did you mean: ");
printf(ANSI_COLOR_RED"%s\n", temp->lastName);
printf(ANSI_COLOR_RESET"");
isFuzzy = TRUE;
}
temp = temp->pNext;
}
}
if (isFuzzy) {
temp = malloc(sizeof(entry));
strcpy(temp->lastName, meta);
return temp;
}
return NULL;
}
entry *append(char lastName[], entry *pHead, entry **ht)
{
unsigned int value = hash(lastName);
entry *e = ht[value];
if (e) {
while (e->pNext != NULL) {
e = e->pNext;
}
e->pNext = (entry *) malloc(sizeof(entry));
strcpy(e->pNext->lastName, lastName);
metaphone(lastName, e->pNext->metaph, MAX_LAST_NAME_SIZE);
} else {
e = (entry *) malloc(sizeof(entry));
strcpy(e->lastName, lastName);
metaphone(lastName, e->metaph, MAX_LAST_NAME_SIZE);
ht[value] = e;
}
return NULL;
}
entry **imple_hash_table(entry **ht)
{
ht = malloc(HASH_SIZE * sizeof(entry *));
for (int i = 0; i < HASH_SIZE; i++) {
ht[i] = NULL;
}
return ht;
}
unsigned int hash(char *key)
{
unsigned int value = 5381;
while (*key != '\0') {
value = ((value << 5) + value) + *key;
key++;
}
return value % HASH_SIZE;
}
void freeNode(entry *pHead, entry **ht)
{
for (int i = 0; i < HASH_SIZE; i++) {
if (ht[i] != NULL)
free(ht[i]);
}
free(ht);
}
int count_hash_buckets(entry **ht)
{
int count = 0;
for (int i = 0; i < HASH_SIZE; i++) {
if (ht[i]) {
count++;
}
}
return count;
}
void display_hash_imformation(entry **ht)
{
float loadFactor = (float)count_hash_buckets(ht) / (float)HASH_SIZE;
printf("there are %d out of %d NULL buckets in hash table: %f\n",
HASH_SIZE - count_hash_buckets(ht), HASH_SIZE, loadFactor);
}