The following code was written by Thomas Niemann and is available on
his algorithm collection
webpages.
#include <stdlib.h>
#include <stdio.h>
/* modify these lines to establish data type */
typedef int T;
#define CompEQ(a,b) (a == b)
typedef struct Node_ {
struct Node_ *Next; /* next node */
T Data; /* data stored in node */
} Node;
typedef int HashTableIndex;
Node **HashTable;
int HashTableSize;
HashTableIndex Hash(T Data) {
/* division method */
return (Data % HashTableSize);
}
Node *InsertNode(T Data) {
Node *p, *p0;
HashTableIndex bucket;
/* insert node at beginning of list */
bucket = Hash(Data);
if ((p = malloc(sizeof(Node))) == 0) {
fprintf (stderr, "out of memory (InsertNode)\n");
exit(1);
}
p0 = HashTable[bucket];
HashTable[bucket] = p;
p->Next = p0;
p->Data = Data;
return p;
}
void DeleteNode(T Data) {
Node *p0, *p;
HashTableIndex bucket;
/* find node */
p0 = 0;
bucket = Hash(Data);
p = HashTable[bucket];
while (p && !CompEQ(p->Data, Data)) {
p0 = p;
p = p->Next;
}
if (!p) return;
/* p designates node to delete, remove it from list */
if (p0)
/* not first node, p0 points to previous node */
p0->Next = p->Next;
else
/* first node on chain */
HashTable[bucket] = p->Next;
free (p);
}
Node *FindNode (T Data) {
Node *p;
p = HashTable[Hash(Data)];
while (p && !CompEQ(p->Data, Data))
p = p->Next;
return p;
}
|