include stdio include string include stdlib define HASHTABLE_WIDTH 100

  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
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define HASHTABLE_WIDTH 1000
#define MAX_NAME_LENGTH 128
struct node {
struct node *next;
char name[MAX_NAME_LENGTH];
int number;
};
unsigned int
hashcode(char str[MAX_NAME_LENGTH])
{
unsigned int hash = 0;
unsigned int length = strlen(str);
for (int i = 0; i < length; i++) {
hash = (hash << 2) ^ str[i];
}
return(hash);
}
void
lookup(struct node *table[HASHTABLE_WIDTH], char *key)
{
unsigned int index = hashcode(key) % HASHTABLE_WIDTH;
struct node *candidate = NULL;
if (table[index] == NULL) {
printf("Not found\n");
} else {
candidate = table[index];
while ((candidate != NULL) && strcmp(candidate->name, key)) {
candidate = candidate->next;
}
if (candidate != NULL) {
printf("%s=%d\n", candidate->name, candidate->number);
} else {
printf("Not found\n");
}
}
}
int
main()
{
int n_entries;
unsigned int index;
char temp_name[MAX_NAME_LENGTH];
struct node *new_node;
struct node *next;
struct node *table[HASHTABLE_WIDTH] = { NULL };
scanf("%d", &n_entries);
// NOTE: fill the hashtable
for (int i = 0; i < n_entries; ++i) {
new_node = calloc(1, sizeof(struct node));
scanf("%s %d", new_node->name, &new_node->number);
index = hashcode(new_node->name) % HASHTABLE_WIDTH;
if (table[index] == NULL) {
table[index] = new_node;
new_node->next = NULL;
} else {
new_node->next = table[index];
table[index] = new_node;
}
}
// NOTE: run queries
unsigned int read = 0;
do {
read = scanf("%s", temp_name);
if (read == 1) {
lookup(table, temp_name);
memset(temp_name, 0x00, MAX_NAME_LENGTH);
} else {
break;
}
} while (1);
// NOTE: cleanup
for (unsigned int i = 0; i < HASHTABLE_WIDTH; ++i) {
new_node = table[i];
while (new_node != NULL) {
next = new_node->next;
free(new_node);
new_node = next;
}
}
return 0;
}