4.5 Коды для хеш-таблиц

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;

}