Сортування й пошук: Рецептурний довідник, страница 14

            P = lb + offset - offset % size;

            exchange (lb, P, size);

            /* partition into two segments */

            i = lb + size;

            j = ub;

            while (1) {

                while (i < j && compar(lb, i) > 0) i += size;

                while (j >= i && compar(j, lb) > 0) j -= size;

                if (i >= j) break;

                exchange (i, j, size);

                j -= size;

                i += size;

            }

            /* pivot belongs in A[j] */

            exchange (lb, j, size);

            m = j;

            /* keep processing smallest segment, and stack largest */

            if (m - lb <= ub - m) {

                if (m + size < ub) {

                    lbStack[sp] = m + size;

                    ubStack[sp++] = ub;

                }

                ub = m - size;

            } else {

                if (m - size > lb) {

                    lbStack[sp] = lb;

                    ubStack[sp++] = m - size;

                }

                lb = m + size;

            }

        }

    }

}

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;

}

4.6     Коди для бінарних дерев

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

#define compLT(a,b) (a < b)

#define compEQ(a,b) (a == b)

typedef struct Node_ {

    struct Node_ *left;         /* left child */

    struct Node_ *right;        /* right child */

    struct Node_ *parent;       /* parent */

    T data;                     /* data stored in node */

} Node;

Node *root = NULL;               /* root of binary tree */

Node *insertNode(T data) {

    Node *x, *current, *parent;

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

    *  allocate node for data and insert in tree  *

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

    /* find x's parent */

    current = root;

    parent = 0;

    while (current) {

        if (compEQ(data, current->data)) return (current);

        parent = current;

        current = compLT(data, current->data) ?