我在跳过列表中插入时遇到问题。当我将元素插入跳过列表时,它只会将元素添加到较低级别,而不是较高级别。当我试图进入下层时,它会爆炸。感谢你的帮助。谢谢你。
#ifndef _SkipList_
#define _SkipList_
// a value not supposed in stack and queue
#define EMPTY 0x7FFFFFFF
// new types
typedef int DATA; // a type for data (easy to change)
typedef enum {False, True} BOOL; // a boolean type
// Node
typedef struct node
{
DATA key;
struct node* next;
struct node* down;
}NODE;
typedef struct
{
NODE *head;
}SkipList;
#endif
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include "SkipList.h"
BOOL SL_init(SkipList *list)
{
if (!list)
return False;
NODE *temp = (NODE*)malloc(sizeof(NODE));
temp->next = (NODE*)malloc(sizeof(NODE));
temp->down = NULL;
temp->key = INT_MIN;
temp->next->key = INT_MAX;
list->head = (NODE*)malloc(sizeof(NODE));
list->head = temp;
NODE *start, *end;
start = (NODE*)malloc(sizeof(NODE));
end = (NODE*)malloc(sizeof(NODE));
start->key = INT_MIN;
start->down = NULL;
end->down = NULL;
end->key = INT_MAX;
list->head = start;
list->head->next = end;
return True;
}
NODE* SL_find(SkipList *list, DATA Value)
{
NODE *p = list->head;
while(1)
{
for(;p->next->key <= Value; p = p->next);
if(p->down == NULL)
break;
p = p->down;
}
if(p->key==Value)
return p;
else
return NULL;
}
NODE* new_node(DATA x, NODE *n, NODE *d){
NODE *p;
p = (NODE*)malloc(sizeof(NODE));
p->key = x;
p->next = n;
p->down = d;
return p;
}
BOOL toss()
{
int random = rand() % 2;
printf(" %d\n", random);
if (random == 0){
return False;
}
return True;
}
NODE *SkipList_addAfter(NODE*p, DATA Value)
{
NODE *temp = (NODE*)malloc(sizeof(NODE));
if (temp)
{
temp->key = Value;
temp->next = p->next;
temp->down = p->next->down;
p->next = temp;
}
return temp;
}
NODE* insert2(NODE *old_lst, DATA x){
NODE *deeper, *newnode;
for (; old_lst->next->key <= x ; old_lst = old_lst->next);
NODE *temp ;
if (old_lst->down == NULL){
temp = SkipList_addAfter(old_lst, x);
return temp;
}
deeper = insert2(old_lst->down, x);
if (deeper == NULL || toss())
return NULL;
else{
newnode = SkipList_addAfter(old_lst, x);
newnode->down = deeper;
}
return newnode;
}
NODE* insert1(NODE *lst, DATA x){
NODE *deeper;
deeper = insert2(lst,x);
if (deeper == NULL || toss())
return lst;
return new_node(INT_MIN, INT_MAX, lst);
}
NODE* insert(SkipList *list, DATA x){
if (SL_find(list, x))
return NULL;
return insert1(list->head, x);
}
void print(SkipList *list){
NODE *temp = list->head->next;
// while (!temp->down){
for (; temp->key <INT_MAX; temp = temp->next){
printf("->%d\n", temp->key);
// }
// temp = temp->down;
// printf("\n\n");
}
}
void deleteD(NODE *node)
{
NODE* tmp;
if (!node || !(tmp = node->next))
return False;
node->next = tmp->next;
free(tmp);
return True;
}
BOOL SL_Delete(SkipList *list, DATA x)
{
NODE *p = SL_find(list, x);
if (p == NULL)
return False;
NODE *temp = list->head;
for (; temp->next->key < p->key; temp = temp->next);
while (temp->down != NULL){
deleteD(temp);
temp = temp->down;
}
deleteD(temp);
return True;
}
void main(){
SkipList *list = (SkipList*)malloc(sizeof(SkipList));
SL_init(list);
int arr[6] = { 1, 2, 3, 4, 5,5};
int i;
for (i = 0; i < 6; i++){
insert(list, arr[i]);
}
/*
if (!SL_Delete(list, 7))
printf("cant delete");
*/
print(list);
// SL_Delete(list, 4);
// print(list);
// if (SL_find(list, 7))
// printf("\nfound");
}