Ñîðòèðîâêà è ïîèñê - ðåöåïòóðíûé ñïðàâî÷íèê

       

Êîäû äëÿ õåø-òàáëèö


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;

}



Ñîäåðæàíèå ðàçäåëà