-

       

-


typedef int T; /* type of item to be sorted */

#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) {

 

/***********************************

* hash function applied to data *

***********************************/

 

return (data % hashTableSize);

}

 

Node *insertNode(T data) {

Node *p, *p0;

hashTableIndex bucket;

 

/************************************************

* allocate node for data and insert in table *

************************************************/

 

/* 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;

 

/********************************************

* delete node containing data from table *

********************************************/

 

/* 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;

 

/*******************************

* find node containing data *

*******************************/

 

p = hashTable[hash(data)];

while (p && !compEQ(p->data, data))

p = p->next;

return p;

}