Реализация

Реализация работы

Функция initList вызывается в самом начале. Она отводит память под заголовок списка и инициализирует его поля. Признаком того, что список пуст, Функция insertNode создает новый узел и вставляет его в список. Конечно, insertNode сначала отыскивает место в списке, куда узел должен быть вставлен. В массиве update функция учитывает встретившиеся ссылки на узлы верхних уровней. Эта информация в дальнейшем используется для корректной установки ссылок нового узла. Для этого узла, с помощью генератора случайных чисел, определяется значение newLevel, после чего отводится память для узла. Ссылки вперед устанавливаются по информации, содержащей в массиве update. Функция deleteNode удаляет узлы из списка и освобождает занимаемую ими память. Она реализована аналогично функции findNode и так же ищет в списке удаляемый узел.

// Коды для разделенных списков

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

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

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

/*

 * levels range from (0 .. MAXLEVEL)

 */

#define MAXLEVEL 15

typedef struct Node_ {

    T data;                     /* user's data */

    struct Node_ *forward[1];   /* skip list forward pointer */

} Node;

typedef struct {

    Node *hdr;                  /* list Header */

    int listLevel;              /* current level of list */

} SkipList;

SkipList list;                  /* skip list information */

#define NIL list.hdr

Node *insertNode(T data) {

    int i, newLevel;

    Node *update[MAXLEVEL+1];

    Node *x;

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

    *  allocate node for data and insert in 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(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;

}