samedi 25 avril 2015

josephus permutation segmentation fault

I am trying to solve the Josephus permutation using a binary search tree. I implemented the functions os_select and os_delete from Cormen, and I have the following problem:

typedef struct node
{
    int key;
    struct node *left;
    struct node *right;
    int size; //dimensiunea subarborelui cu radacina in key
} node;

void josephus(int n, int m)
{
    node *root=build_tree(v,0,n-1); //this is tested, works perfectly
    int k,j=1;
    for(k=n;k>=1;k--)
    {
        j=((j+m-2)%k)+1;
        node *x=os_select(root,j);
        printf("%d ",x->key);
        decSize(x,j);
        os_delete(root,x->key);
    }
    //afisare_in_preordine(root,0);
}

When I run the program, I get a segmentation fault inside the os_select function:

node *os_select(node *x,int i)
{
    int r=x->left->size+1; //i get the segmentation fault here...
    if (i==r)
    {
        return x;
    }
    else
    {
        if(i<r)
        {
            return os_select(x->left,i);
        }
        else
        {
            return os_select(x->right,i-r);
        }
    }
}

If you need anymore pieces of code that I should add, please let me know.

Aucun commentaire:

Enregistrer un commentaire