• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

DavidLuiz

Estou com um problema com red-black trees

5 mensagens neste tópico

Boas, estou a tentar resolver um problema de Red-Black trees, so que nao consigo descobrir qual é o erro que tenho neste codigo.

O problema consiste, entre outras opçoes, em adicionar as matriculas de carros e o seu estado ("R" - encontra-se registado, "I" - nao se encontra registado), veiculo a veiculo, numa arvore binaria, em que as matriculas ficam ordenadas alfabeticamente.  Eu ainda so consegui o codigo para adicionar, mas esta-me a dar um erro a quando da inserção da segunda matricula. Que nao percebo qual é  :P

Exemplo de input:

ADD 44FF22 I

ADD 22AA33 R

ao inserir o segundo ele da-me um erro  :P

Alguem me podia ajudar?!

O codigo que tenho é o seguinte:


#include <stdio.h>
#include <stdlib.h>
#include <string.h>


typedef struct vei{
        char *matricula;
        char estado;
}veiculo;


typedef struct jsw_node {
  int red;
  veiculo info;
  struct jsw_node *link[2];
}JSW_NODE;

typedef struct jsw_tree {
    JSW_NODE *root;
}JSW_TREE;

typedef JSW_TREE *TREE_TYPE;
typedef JSW_NODE *NODE_PTR;

NODE_PTR jsw_single ( NODE_PTR root, int dir );
NODE_PTR jsw_double (NODE_PTR root, int dir );
int jsw_insert ( TREE_TYPE tree, veiculo data );
NODE_PTR make_node ( veiculo data );

TREE_TYPE arvore;




int main() {
    
     arvore = (TREE_TYPE) malloc(sizeof (JSW_TREE));
     arvore->root = NULL;
    
     int i=0,j;
     char input[100], *vec[256];
     char *str;
     
     NODE_PTR ptr_aux;
     veiculo ptr;

     
     while(1) {
         i=0;
         fflush(stdin);
         fgets(input,100,stdin);
       
         input[strlen(input)] = '\0';
         str = strtok(input," ");
         vec[i] = (char *)malloc(sizeof(char)*256);
         strcpy(vec[i], str);
         i++;
         do{
             str = strtok(NULL," ");
             if(str != NULL) {
                    vec[i] = (char *)malloc(sizeof(char)*256);
                    strcpy(vec[i++], str);               
             }
         }while(str != NULL);
         
         if (strcmp(vec[0],"ADD") == 0) {
       
            ptr.matricula = vec[1];
            ptr.estado = *vec[2];
                   
            jsw_insert ( arvore, ptr );
          
            //system("pause");
          
         }
       
     }
     return 0;
}


int jsw_insert ( TREE_TYPE tree, veiculo data )
{
  

  if ( tree->root == NULL ) {
     /* Empty tree case */
     
     tree->root = make_node ( data );
    
     if ( tree->root == NULL )
       return 0;
  }
  else {
     JSW_NODE head = {0}; /* False tree root */  
     struct jsw_node *g, *t;     /* Grandparent & parent */
     struct jsw_node *p, *q;     /* Iterator & parent */

     int dir = 0, last;

     /* Set up helpers */
     t = &head;
     g = p = NULL;
     q = t->link[1] = tree->root;

     /* Search down the tree */
     for ( ; ; ) {
       if ( q == NULL ) {
         /* Insert new node at the bottom */
         p->link[dir] = q = make_node ( data );
         if ( q == NULL )
           return 0;
       }
       else if ( is_red ( q->link[0] ) && is_red ( q->link[1] ) ) {
         /* Color flip */
         q->red = 1;
         q->link[0]->red = 0;
         q->link[1]->red = 0;
       }

       /* Fix red violation */
       if ( is_red ( q ) && is_red ( p ) ) {
         int dir2 = t->link[1] == g;

        if ( q == p->link[last] )
           t->link[dir2] = jsw_single ( g, !last );
        else
           t->link[dir2] = jsw_double ( g, !last );
       }

       /* Stop if found */
       if (strcmp( q->info.matricula,data.matricula ) == 0)
         break;

       last = dir;
       int auxx = strcmp(q->info.matricula,data.matricula);
       if (auxx < 0) {
                dir = 1;
       }
       else {
            dir = 0;
       }
       /* Update helpers */
      if ( g != NULL ) {
         t = g;
      }
      g = p, p = q;
      q = q->link[dir];
     }

     /* Update root */
     tree->root = head.link[1];
  }

  /* Make root black */
  tree->root->red = 0;
    
  return 1;
}

NODE_PTR make_node ( veiculo data ) {
    
    NODE_PTR rn = (NODE_PTR) malloc ( sizeof rn );
    
    if ( rn != NULL ) {
      rn->info = data;
      rn->red = 1; /* 1 is red, 0 is black */
      rn->link[0] = NULL;
      rn->link[1] = NULL;
  }
    
  return rn;
}

int is_red ( NODE_PTR root ){
  return root != NULL && root->red == 1;
}

NODE_PTR jsw_single ( NODE_PTR root, int dir ){
  NODE_PTR save = root->link[!dir];

  root->link[!dir] = save->link[dir];
  save->link[dir] = root;

  root->red = 1;
  save->red = 0;

  return save;
}

NODE_PTR jsw_double (NODE_PTR root, int dir )
{
  root->link[!dir] = jsw_single ( root->link[!dir], !dir );
  return jsw_single ( root, dir );
}


0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Devias compilar com a flag -Wall para ligar "todos" os warnings. Assim recebias a mensagem

a.c: In function `main':

a.c:41: warning: unused variable `j'

a.c:45: warning: unused variable `ptr_aux'

a.c: In function `jsw_insert':

a.c:115: warning: implicit declaration of function `is_red'

O problema é que na linha 115, ou seja, na função de inserir, usas a função is_red mas esta só é definida mais abaixo. Ou colocas o protótipo da função acima da função de inserção de nós ou colocas a implementação completa da função.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ja coloquei o prototipo da funçao is_red antes da função de inserção, mas mesmo assim, ao inserir o segundo elemento da-me um erro e aborta o programa... 

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

pelo que percebo, ao inserir o segundo veiculo ele aborta na linha 57:

vec[i] = (char *)malloc(sizeof(char)*256);

nao percebo é porque...

Se ao inserir o primeiro ele nao causou problemas e no segundo causa.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Aqui aborta na linha onde fazes

if ( is_red ( q->link[0] ) && is_red ( q->link[1] ) )

Os endereços de memória nestes links não estão bem. Referenciam memória invalida ao que parece, por isso, ao fazer q->link[0]->red estoura. Estive até agora a tentar mas não percebi o que se passa. Tenho que ir dormir. Se amanhã não tiveres conseguido volto a tentar.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora