>But how would I implement a hash table using an array of lists.
Play around with this simple hash table with linked list chaining. It's really very simple, you just have to see how things work.
Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TABSIZ 200
struct TabRec {
struct TabRec *next;
char name[BUFSIZ];
};
static struct TabRec *htable[TABSIZ];
unsigned hash(char *s)
{
unsigned h;
for (h = 0; *s; s++)
h = *s + 31 * h;
return h % TABSIZ;
}
struct TabRec *find(char *name)
{
struct TabRec *item;
for (item = htable[hash(name)]; item; item = item->next)
{
if (strcmp(name, item->name) == 0)
return item;
}
return NULL;
}
struct TabRec *insert(char *name)
{
struct TabRec *item;
unsigned h;
if ((item = find(name)) == NULL)
{
/* Not found, add */
if ((item = malloc(sizeof (*item))) == NULL)
return NULL;
strcpy(item->name, name);
h = hash(name);
item->next = htable[h];
htable[h] = item;
}
return item;
}
int main(void)
{
char buf[BUFSIZ];
struct TabRec *item;
while (fgets(buf, sizeof (buf), stdin))
{
if (insert(buf) == NULL)
break;
}
printf("Enter a name to find: ");
fflush(stdout);
if (fgets(buf, sizeof (buf), stdin))
{
if ((item = find(buf)) != NULL)
printf("%s", item->name);
}
return 0;
}