C++ Lista z przeskokami

Question

Cześć, mam problem z implementacją listy z przeskokami (skip list)

Otóż mój kod wygląda następująco:

 

#include <iostream>
#include <string.h>
#include <cstdlib>
#include <stdlib.h>
#include <ctime>
#include <conio.h>
#include <stdio.h>


using namespace std;
int LMAX=10;

struct skiplist{
        int key;
        int height;
        struct skiplist **next;
        //string nazwa;
        int nazwa;
        
};


int random_level()
{
        int level=1;
        while((rand()%100<0.5*100)&&(level<LMAX))
        {
                level++;
        }
        return(level);
}



string insert(skiplist* head, int new_key)
{
        struct skiplist* x=head;
        struct skiplist* update[LMAX];
        if(head->next[0]==nullptr)
        {
            struct skiplist* new_node = new skiplist;
            int height=LMAX-1;
            //new_node=(struct skiplist*)malloc(sizeof(struct skiplist)+sizeof(struct skiplist*)*(height-1));
            new_node->key=new_key;
            new_node->height=height;
            
            for(int i=0;i<height-1;i++)
            {
                    //new_node->next[i]=update[i]->next[i];
                    //update[i]->next[i]=new_node;
                    head->next[i]=new_node;
            }
        }
        else
        {
                int height=random_level();
                struct skiplist* new_node = new skiplist;
                //new_node=(struct skiplist*)malloc(sizeof(struct skiplist)+sizeof(struct skiplist*)*(height-1));
                new_node->key=new_key;
                new_node->height=height;
                new_node->next=new skiplist*[height];
                for(int i=height-1;i>=0;i--)
                {
                        while(x->next[i]->key<new_key)
                        {
                                x=x->next[i];
                        }
                        update[i]=x;
                }
                x=x->next[0];
                if(x->key==new_key)
                {
                        return("blad");
                }
                
                
                
        
                for(int i=0; i<new_node->height;i++)
                {
                        new_node->next[i]=update[i]->next[i];
                        update[i]->next[i]=new_node;
                }
        
                return("OK");
        }
}


skiplist *createSkipList()
{
        skiplist* skip = new skiplist;
        skip->next=new skiplist*[10];
        int height=LMAX;
        //skip=(struct skiplist*)malloc(sizeof(struct skiplist)+sizeof(struct skiplist*)*(height-1));
        skip->key=-2147483647;
        skip->height=LMAX;
        skip->nazwa=1;
        
        skiplist* tail = new skiplist;
        //tail=(struct skiplist*)malloc(sizeof(struct skiplist)+sizeof(struct skiplist*)*(height-1));
        tail->key=2147483647;
        tail->height=LMAX;
        tail->nazwa=2;
        for(int i=0;i<LMAX-1;i++)
        {
                skip->next[i]=tail;
        }
        
        return skip;
}

/*skiplist *search(skiplist* head, int key)
{
        skiplist* x = head;
        for(int i=0;i<LMAX-1;i++)
        {
                while(x->next[i]->key>key)
                {
                        x=x->next[i];
                }
        }
        
        x=x->next[0];
        if(x->key=key)
        {
                return(x);
        }
        return(NULL);
}*/

void insert_all(skiplist* head, int N)
{
        int liczba;
        for(int i=0; i<N;i++)
        {
                //do
                //{
                        liczba = (rand() % 99999) +99;
                //}while(search(head,liczba)->key!=liczba);
                
                insert(head,liczba);
        }
}


string usun(skiplist* head, int key)
{
        skiplist* x=head;
        skiplist* update[10];
        for(int i=LMAX-1; i>=0;i--)
        {
                while(x->next[i]->key<key)
                {
                        x=x->next[i];
                }
                update[i]=x;
        }
        x=x->next[0];
        if(x->key>key)
        {
                return("blad");
        }
        for(int i=0; i<x->height; i++)
        {
                update[i]->next[i]=x->next[i];
        }
        free(x);
        return("OK");
}



int main()
{
        //2001 7 13666 4 7 -1 100001
        srand((unsigned int)time(NULL));
        int N=2001;
        int LMAX=7;
        int k1=13666;
        int k2=4;
        int k3=7;
        int k4=-1;
        int k5=100001;
        
        
        clock_t begin, end;
        double time_spent;
        begin = clock();
        
        skiplist* head=createSkipList();
        /*if(search(head,k1)==NULL)
        {
                cout<<"Nie znaleziono"<<endl;
        }
        else
        {
                cout<<"Znaleziono klucz k1"<<endl;
        }*/
                
        //insert_all(head,N);
        
        for(int i=0;i<2;i++)
        {
                cout<<head->key<< " " << i<<endl;
                head=head->next[0];
        }
        
        insert(head,100);
        


        
        time_spent = (double)(end-begin) / CLOCKS_PER_SEC;
        cout << "Czas wykonania:" << time_spent << endl;
        
        
        
        return 0;
}

W podanym przypadku debugger informuje o błędzie w linii 206.

Kod błędu 139.

Próbowałem na wiele sposobów rozwiązać (problem z pamięcią?), ale chyba coś mi umyka :)

Może jest ktoś, kto implementował podobną strukturę i wie co tu może być nie tak?

Dodam jeszcze, że jak próbuję dodać nowy węzeł to identyczny błąd debugger pokazuje w linii nr 64
Z góry dziękuję za wszystkie podpowiedzi.

Comments

Nie wiem czy to pomogło czy nie, ale błąd polegał na tym że height było stałe, a powinno się oczywiście zmieniać w każdej iteracji. Szukajka działa, natomiast zwraca true w każdym przypadku ;p

---

Może trzeba zamienić jeden '=' na dwa '==' ?

---

Nawet nie wiem jak to skomentować.

Wpatrywałem się w ten kod wielokrotnie i nie zauważyłem takiego błędu, chyba jednak jestem nierozgarnięty :D

Dziękuję pięknie :)

---

Cóż mam powiedzieć, programowaniem interesuję się od bardzo dawna i też mi się to zdarza.

---

Ostatnia sprawa jaka mi pozostała z implementacją to usuwanie wszystkich elementów listy.

Mam alokowaną pamięć na węzeł podczas dodawania węzła, pamięć na head i tail podczas inicjalizacji oraz pamięć na tablicę wskaźników ( head->next[height]), pytanie jak usuwać te elementy, tzn w jakiej kolejności, od głowy czy ogona?
No i jak zwalniam pamięć dla  np. head->next[0] to muszę zwalniać dodatkowo pamięć na tablicę wskaźników będącą składową węzła czy podczas zwalniania pamięci węzła każda składowa, włącznie z tą tablicą wskaźników też jest kasowana?

Answer 1

Zapamiętaj next w elemencie pomocniczym. Przykładowy meta-kod:

 

while( element ) {

tmp = element->next;

delete element;

element = tmp;

}

Comments

Próbowałem chyba już wcześniej

Kompilator wyrzuca taki błąd, wyczytałem że " 1 Answer. Exit code 134 means your program was aborted (received SIGABRT), perhaps as a result of a failed assertion. ", ale nie potrafię tego odnieść do mojego kodu.

 

Program received signal SIGABRT, Aborted.                                                                                    

0x00007ffff7519c37 in __GI_raise (sig=sig@entry=6)                                                                           

    at ../nptl/sysdeps/unix/sysv/linux/raise.c:56                                                                            

56      ../nptl/sysdeps/unix/sysv/linux/raise.c: No such file or directory.                                                  

(gdb)

---

W debugerze co widać?

---

Valgrind mówi, że nie zwalniam czegoś co alokuję w tej funkcji:

 

bool insert(skiplist* head, int new_key, int LMAX)
{
        skiplist* x=head;
        int height=random_level(LMAX);
        skiplist* update[height];
        
        
        for(int i=height-1;i>=0;i--)
        {
                while(x->next[i]->key < new_key)
                {
                        x=x->next[i];
                }
                update[i]=x;
                
        }
        x=x->next[0];
        if(x->key==new_key)
        {
                x->litera='D';
                return false;
        }
        skiplist* new_node = new skiplist;
        new_node->next=new skiplist*[height];
        
        new_node->key=new_key;
        new_node->height=height;
        
        for(int i=0; i<new_node->height;i++)
        {
                new_node->next[i]=update[i]->next[i];
                update[i]->next[i]=new_node;
                new_node->litera='T';
        }
        return true;
}

 

---

Zobacz instrukcja po instrukcji w debugerze, zapisz na kartce papieru wskaźniki, narysuj schemat listy - znajdziesz problem.