1

我在跳过列表中插入时遇到问题。当我将元素插入跳过列表时，它只会将元素添加到较低级别，而不是较高级别。当我试图进入下层时，它会爆炸。感谢你的帮助。谢谢你。

#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");

}
4

0 回答 0