How to delete a skipList

143 Views Asked by At

i have to delete the entire skipList. I was trying to use the features of a skipList to have a bettere complexity of the algorithm but when i try to run and debug give me segmentation fault.

EDIT: i was trying to make a O(n log n) algorithm but it was a mistake...solution require O(log n) algorithm. I'll edit with the solution that work but it free the memory correctly?

main:

int main(int argc, char const *argv[])
{
    srand(time(NULL));
    SkipList *list = malloc(sizeof(SkipList));
    list->max_level = 0;
    list->compare = NULL;
    list->head = create_node(NULL,MAX_HEIGHT);
    insert_skip_list(list,(int*)5);
    insert_skip_list(list,(int*)4);
    insert_skip_list(list,(int*)3);
    insert_skip_list(list,(int*)1);
    insert_skip_list(list,(int*)0);
    list=delete_skip_list(list);
    read_skip_list(list);
    return 0;
}

function to delete:

SkipList* delete_skip_list(SkipList *list){
    delete_node_array(list->head);
    free(list);
    list=NULL;
    return list;
}
void delete_node_array(Node* node){
   if(node == NULL) return; 
   delete_node_array(node->next[0]);
   free(node);
   node = NULL;
}

structure:

struct _SkipList {
    Node *head;
    unsigned int max_level;
    int (*compare)(void*, void*);
};
struct _Node {
    Node **next;
    unsigned int size;
    void *item;
};

EDIT:

Node* create_node(void* item, int level){
    Node *node = malloc(sizeof(Node));
    if(node == NULL){
        printf("error malloc node");
    }
    node->item = item;
    node->size = level;
    node->next = (Node**)malloc(level * sizeof(Node));
    for (int i = 0; i < node->size; i++)
        {
            node->next[i] = NULL;
        }
    if(node == NULL){
        printf("error malloc node->next");
    }
    return node;
}
float float_rand( float min, float max )
{
    float scale = rand() / (float) RAND_MAX; /* [0, 1.0] */
    return min + scale * ( max - min );      /* [min, max] */
}
int random_level(){
    int level = 1;
    
    while(level<MAX_HEIGHT && float_rand(0,1) < 0.5){
        level++;
    }
    return level;
}
void insert_skip_list(SkipList* list,void* item){
   
    Node* node = create_node(item,random_level());
    if(node == NULL){
        printf("\nisert_skip_list:error malloc node");
    }
    if (list == NULL)
    {
         printf("\nisert_skip_list:list null");
         exit(EXIT_FAILURE);
    }
    if(node->size > list->max_level){
        list->max_level = node->size;
    }
    
    Node *x = list->head;
    
    for (int k = list->max_level-1; k >= 0; k--)
    {
        if(x->next[k] == NULL || item < x->next[k]->item){
            if(k < node->size){
                node->next[k] = x->next[k];
                x->next[k] = node;
            }
        }else{
            x = x->next[k];
        }
    }
}

I tried to print the size of the node and i foud out that give me random value :

node size: 1 node size: 1 node size: 1 node size: 1 node size: 12004376 Program received signal SIGSEGV, Segmentation fault.

like node is null and not have access to field size.

0

There are 0 best solutions below