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

    x = x->forward[0];

    if (x != NIL && compEQ(x->data, data)) return(x);

    /* determine level */

    newLevel = 0;

    while (rand() < RAND_MAX/2) newLevel++;

    if (newLevel > MAXLEVEL) newLevel = MAXLEVEL;

    if (newLevel > list.listLevel) {

        for (i = list.listLevel + 1; i <= newLevel; i++)

            update[i] = NIL;

        list.listLevel = newLevel;

    }

    /* make new node */

    if ((x = malloc(sizeof(Node) +

      newLevel*sizeof(Node *))) == 0) {

        printf ("insufficient memory (insertNode)\n");

        exit(1);

    }

    x->data = data;

    /* update forward links */

    for (i = 0; i <= newLevel; i++) {

        x->forward[i] = update[i]->forward[i];

        update[i]->forward[i] = x;

    }

    return(x);

}

void deleteNode(T data) {

    int i;

    Node *update[MAXLEVEL+1], *x;

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

    *  delete node containing data from list  *

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

    /* find where data belongs */

    x = list.hdr;

    for (i = list.listLevel; i >= 0; i--) {

        while (x->forward[i] != NIL

          && compLT(x->forward[i]->data, data))

            x = x->forward[i];

        update[i] = x;

    }

    x = x->forward[0];

    if (x == NIL || !compEQ(x->data, data)) return;

    /* adjust forward pointers */

    for (i = 0; i <= list.listLevel; i++) {

        if (update[i]->forward[i] != x) break;

        update[i]->forward[i] = x->forward[i];

    }

    free (x);

    /* adjust header level */

    while ((list.listLevel > 0)

    && (list.hdr->forward[list.listLevel] == NIL))

        list.listLevel-і;

}

Node *findNode(T data) {

    int i;

    Node *x = list.hdr;

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

    *  find node containing data  *

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

    for (i = list.listLevel; i >= 0; i--) {

        while (x->forward[i] != NIL

          && compLT(x->forward[i]->data, data))

            x = x->forward[i];

    }

    x = x->forward[0];

    if (x != NIL && compEQ(x->data, data)) return (x);

    return(0);

}

void initList() {

    int i;

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

    *  initialize skip list  *

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

    if ((list.hdr = malloc(sizeof(Node) + MAXLEVEL*sizeof(Node *))) == 0) {

        printf ("insufficient memory (initList)\n");

        exit(1);

    }

    for (i = 0; i <= MAXLEVEL; i++)

        list.hdr->forward[i] = NIL;

    list.listLevel = 0;

}

5. Література

^[1] Donald E.  Knuth.  The Art of Computer Programming, volume 3.  Massachusetts:

Addison-Wesley, 1973. Є російський переклад: Д.Батіг. Мистецтво програмування для ЕОМ. Т.3. З “Мир”, М.1978.

^[2] Thomas H.  Cormen, Charles E.  Leiserson, and Ronald L.  Rivest.  Introduction to Algo-

rithms.  New York: McGraw-Hill, 1992.

^[3] Alfred V.  Aho, John E.  Hopcroft, and Jeffrey D.  Ullman.  Data Structures and Algorithms.  Massachusetts: Addison-Wesley, 1983.

^[4] Peter K.  Pearson.  Fast hashing of variable-length text strings.  Communications of the

ACM, 33(6):677-680, June 1990.

^[5] William Pugh.  Skip lists: A probabilistic alternative to balanced trees.  Communications

of the ACM, 33(6):668-676, June 1990.

6. Словник

Term	Термін
sort by insertion	сортування вставками
array	масив
linked list	лінійний список
comparison	порівняння
in-place	на місці (без додаткових масивів)
stable sort	стійке сортування
underflow	виродження
overflow	переповнення
red-black tree	червоно-чорне дерево
skip list	розділений список
rotation	обертання