Êîäû äëÿ ðàçäåëåííûõ ñïèñêîâ
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;
}
