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

       

Êîäû äëÿ ðàçäåëåííûõ ñïèñêîâ


 

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;

}


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