1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

Listas, quicksort

Discussão em 'Programação' iniciada por maquineta, 3 de Novembro de 2007. (Respostas: 14; Visualizações: 3168)

  1. programacao em C

    -------------------------------------------------------------------------------
    1-
    a funcao tira cartao tem dado varios erros
    se eu retiro o ultimo elemento da lista ele poe o penultimo com numero errado
    se eu retiro o primeiro elemento ele poe o segundo com numero errado
    se eu retiro do meio está certo
    se eu retiro o segundo elemento ele retira o primeiro junto e retorna o terceiro com numero errado


    ese rodo o programa e o priomeiro q retiro eh o primeiro o programa dá erro e sai (windows)

    Código:
    
    void Retiracartao (int cliente, Lista *lc){
    
         Cartao *aux,*t;
          
         if (!lc) return;
         
         t=AchaCartao(lc,cliente);
         if (t==NULL){ 
              printf ("Esse cartao nao existe. Tente denovo.\n");
              return;
         }
         
         if(t->prox!=NULL && t->ant!=NULL){ /*quando o cartao nao é o primeiro nem ultimo*/
              aux=t;
              t=t->ant;
              t->prox=aux->prox;
         }
         
         if(t->prox==NULL){ /*quando o cartao é o ultimo*/
              lc->fim=(void *)t->ant;
              aux=(Cartao *)lc->fim;
              aux->prox=NULL;
              free(t);
         }
         
         if(t->ant==NULL){ /*quando o cartao é o primeiro*/
              lc->ini=(void *)t->prox;
              aux=(Cartao *)lc->ini;
              aux->ant=NULL;
              free(t);
         }
         
         if(t->prox==NULL && t->ant==NULL){ /*quando a lista tem um elemento*/
              aux=t;
              lc->ini = lc->fim = NULL;
              free(t);
         }  
                     
         free(aux);
         return;
    }
    
    /*
       função AchaCartao
       descrição: devolve um ponteiro para o Cartao com numero n,
       e NULL caso nao encontra-lo.
    */
    Cartao *AchaCartao(Lista *l, int n)
    {
      Cartao *c;
    
      if (!l) return NULL;
    
      for (c = (Cartao *)l->ini; c!=NULL; c = c->prox) {
        if (c->numero == n) return c;
      }
      return NULL;
    }
    
    
    /* Definicao da estrutura de dados para Cartoes: lista duplamente ligada */
    typedef struct _CC_ {
      int numero;            /* numero do cartao */
      float limite;          /* limite de credito */
      float gastos;          /* total de gastos do mes */
      int ano;               /* ano de validade do cartao */
      char nome[TAM_NOME+1]; /* nome do cliente */ 
      struct _CC_ *prox, *ant;
    } Cartao;
    
    typedef struct _lista_ {
      void *ini; /* inicio e fim da lista */
      void *fim; 
    } Lista;
    
    -------------------------------------------------------------------------------

    2- a funcao quicksort nao estava fazendo nada, deixava a lista como estava, eu achava q o erro estava no cartaoswip mas agora eu testei ela denovo e parece q da erro qdo chama ela, nao sei direito pq estou no windwos mas provavelmente dvee ser um seg fault
    alguem sabe bem sobre quicksort?


    Código:
    /* 
    ************************************************************
    funcoes para ordenacao
    ************************************************************
    */
    
    
    void CartaoSwip ( int i , int j ,int Tamanho,Lista *lc)
    {
         Cartao *p1 , *p2 , *p3 = NULL ;
         int temp;
         if ( i == j ) return ;
         if ( i > j ) {
              temp = i ;
              i = j ;
              j = i ;
         }
          
         p1 = ponteiro (i,lc) ;
         p2 = ponteiro (j,lc ) ;
         p3 = p2->prox ;
         if ( j != Tamanho ) {     
             p2->prox->ant = p1 ;
         }
         if ( i == ( j -1 ) ) {  
             p1->ant->prox = p2 ;
             p1->prox = p2->prox ;  
             p2->prox = p1 ;
             p2->ant = p1->ant ;
             p1->ant = p2 ;
         } 
         else {
             p1->prox->ant = p2 ;
             p2->ant->prox = p1 ;   
             p1->ant->prox = p2 ;
             p2->prox = p1->prox ;
             p1->prox = p3 ;
             p3 = p1->ant ;
             p1->ant = p2->ant ;
             p2->ant = p3 ;
         }        
    }
    
    
    void quicksort (Lista *lista,int inicio,int fim) {
        int pivop;
        
        if (inicio<fim){ 
            pivop=divide(lista,inicio,fim);
           quicksort(lista,inicio,pivop-1);
           quicksort(lista,pivop+1,fim);
        }
    }
            
    
    int divide (Lista *lc,int ini, int fim){
        int i,j,tamanho=1,a=1;
        float pivo;
        Cartao *c;
        i=ini-1;
        pivo=Saldon(fim+1,lc);
        
        for (c = (Cartao *)lc->ini; c ; c = c->prox)
               tamanho++;
        
        for (j=ini; j<fim; j++)
            if (Saldon(j+1,lc)<pivo){
                i++;
                CartaoSwip(i+1,j+1,tamanho,lc); 
            }
        
        CartaoSwip(pivo,i+1,tamanho,lc);
        return (i+1);
    }
    
    float Saldon (int n, Lista *lc)
    {
          float a;
          int j=0;
          Cartao *c;
          for (c = (Cartao *)lc->ini; j<(n+1) ; c = c->prox) 
              j++;
          a=(c->limite) - (c->gastos);
    }
    
    Cartao * ponteiro (int b, Lista *lc)
    {
           Cartao *c;
           int j=0;
           for (c = (Cartao *)lc->ini; j<(b+1) ; c = c->prox)
               j++;
           return c;  
    }
    
    -------------------------------------------------------------------------------

    obrigado a todos
     
    Última edição: 3 de Novembro de 2007
  2. Consu

    Consu Power Member

    Não consegui perceber ao certo o que pretendes, mas existe o quicksort já implementado em C (qsort()). Neste caso apenas precisas de definir o operador de comparação do tipo de dados que queres usar. Existe também em C++ a função sort(), que faz a ordenação que julgo que pretendes.

    Sem mais detalhes fica complicado ajudar, porque se por exemplo, o que pretendes é tirar sempre o primeiro elemento por ordem, nesse caso é melhor usar uma priority_queue. Tenta explicar melhor o que pretendes para ver se consigo ajudar.
     
  3. o Retiracartao retira um elemento da lista mas ele pode ser o primeiro, do meio ou o ultimo..

    o quick sort eu preciso ordenar a lista de cartoes de acordo com esse estilo de ordenacao (quicksort) e mexendo apenas os ponteiros
    nossa nao sabia q existia essa funcao qsort().. vou olhar =)
     
    Última edição: 3 de Novembro de 2007
  4. Consu

    Consu Power Member

    Pelo código julgo que estás a usar C. Se for em C++ isso fica muito mais simples, pois pelo que percebi estás a tratar da lista também. O C++ já possui listas, e inclusive com a opção de remover o elemento x, e com a função sort() ordená-la. Se quiseres usar C++ diz que coloco aqui um exemplo.
     
  5. Código:
    void Retiracartao (int cliente, Lista *lc){
    
         Cartao *aux,*t;
          
         if (!lc) return;
         
         t=AchaCartao(lc,cliente);
         if (t==NULL){ 
              printf ("Esse cartao nao existe. Tente denovo.\n");
              return;
         }
         
         if(t->prox!=NULL && t->ant!=NULL){ /*quando o cartao nao é o primeiro nem ultimo*/
              aux=t;
              t=t->ant;
              t->prox=aux->prox;
         }
         
         if(t->prox==NULL){ /*quando o cartao é o ultimo*/
              lc->fim=(void *)t->ant;
              aux=(Cartao *)lc->fim;
              aux->prox=NULL;
              free(t);
         }
         
         if(t->ant==NULL){ /*quando o cartao é o primeiro*/
              lc->ini=(void *)t->prox;
              aux=(Cartao *)lc->ini;
              aux->ant=NULL;
              free(t);
         }
         
         if(t->prox==NULL && t->ant==NULL){ /*quando a lista tem um elemento*/
              aux=t;
              lc->ini = lc->fim = NULL;
              free(t);
         }  
                     
         free(aux);
         return;
    }
    
    assim fica + simples de entender
    entao, infelizmente eu tenho q fazer em C =/ e com quicksort
     
    Última edição: 3 de Novembro de 2007
  6. Consu

    Consu Power Member

    Tenta ver se assim funciona.

    Código:
    
    void Retiracartao (int cliente, Lista *lc){
    
         Cartao *aux,*t;
          
         if( !lc ) return;
         
         t = AchaCartao( lc, cliente );
         if( t == NULL ) { [COLOR=DarkGreen]/* Não encontrado */[/COLOR]
              printf ( "Esse cartao nao existe. Tente novamente.\n" );
              return;
         }
         
         if( t->prox != NULL && t->ant != NULL ) { [COLOR=DarkGreen]/*quando o cartao nao é o primeiro nem ultimo*/[/COLOR]
              aux = t; [COLOR=DarkGreen]/* guarda o elemento actual */[/COLOR]
              t = t->ant; [COLOR=DarkGreen]/* t é o elemento anterior */[/COLOR]
              t->prox = aux->prox; [COLOR=DarkGreen]/* Coloca a apontar para o elemento seguinte ao eliminado */[/COLOR]
              free( aux); [COLOR=DarkGreen]/* liberta elemento removido */[/COLOR]
              return;
         }
         
         if( t->ant != NULL ) { [COLOR=DarkGreen]/* último elemento */[/COLOR]
              lc->fim = (void *)t->ant; [COLOR=DarkGreen]/* actualiza quem é o último elemento */[/COLOR]
              aux = t->ant; [COLOR=DarkGreen]/* elemento antes do que está a ser removido */[/COLOR]
              aux->prox = NULL; [COLOR=DarkGreen]/* não existe elemento seguinte */[/COLOR]
              free(t); [COLOR=DarkGreen]/* liberta elemento removido */[/COLOR]
              return;
         }
         
         if( t->prox != NULL ) { [COLOR=DarkGreen]/*quando o cartao é o primeiro*/[/COLOR]
              lc->ini = (void *)t->prox; [COLOR=DarkGreen]/* 2º passa a ser o 1º */[/COLOR]
              aux = t->prox; [COLOR=DarkGreen]/* 1º elemento após[/COLOR][IMG]http://www.techzonept.com/images/styles/newtzstyle/editor/color.gif[/IMG][COLOR=DarkGreen] o que está a ser removido */[/COLOR]
              aux->ant = NULL; [COLOR=DarkGreen]/* não existe nenhum antes */[/COLOR]
              free(t); [COLOR=DarkGreen]/* liberta o espaço do elemento */[/COLOR]
              return;
         }
         
        [COLOR=DarkGreen] /*a lista só tem um elemento*/[/COLOR]
         lc->ini = lc->fim = NULL;
         free(t);
    }
    
    Essencialmente acrescentei comentários para perceber melhor. Acho que tinhas um problema no fim do código. Tenta assim e depois diz que erros se mantêm. ( ou não :p )
     
    Última edição: 4 de Novembro de 2007
  7. man, i tested here quickly and it seems everything is working properly, let me see now what u changed
    tks :)
     
  8. exceto vc ter mudado o retorno da funcao pra cada caso
    vc apenas mudou a condicao de ser o ultimo elemento para nao é o primeiro e do primeiro elemento pra nao é o ultimo que tbm dá no mesmo ja q ja passou pela condicao de estar no meio

    funcionou, agora por que agora tudo funciona eu ainda nao entendi .. =/
     
  9. Consu

    Consu Power Member

    Pelo que me pareceu havia um erro, mas cada caso estava bem tratado. O problema é que no fim do código havia um free(aux), e creio que muitas vezes era executado quando não devia. Pelo menos foi essa a maior alteração. Outro pormenor, embora não influenciasse, era um caso em que não removia a memória alocada.

    Fico feliz por ter ajudado. Quanto ao quicksort, qualquer coisa é só dizer.
     
  10. o quicksort jka tentei de tudo.. até baixar o microsoft visual C++ (que nao consigo por em C)

    continua algo errado q nao sei =/
     
  11. Consu

    Consu Power Member

    Tenta ver este código.

    Código:
    void swap( Cartao* c1, Cartao* c2 ) {
        Cartao* tmp;
        
        *tmp = *c1; *c1 = *c2; *c2 = *tmp;
    }
    
    Cartao* AchaCartao( Lista *lc, int el ) {
        int i;
        Cartao* cartao;
    
        if( !lc )
            return NULL;
            
        cartao = lc->inicio;
        for( i = 0; i < e1 && cartao != NULL; ++i )
            cartao = cartao->prox;
            
        return cartao;
    }
    
    int compare( Cartao *c1, Cartao *c2 ) {
        if( *c1 < *c2 ) [COLOR=DarkGreen]/* Coloca a forma de comparar */[/COLOR]
            return -1;
            
        if( *c1 > *c2 ) [COLOR=DarkGreen]/* Coloca a forma de comparar */[/COLOR]
            return 1;
            
        return 0;
    }
    
    void quicksort( int i, int j, Lista* lc ) {
        Cartao *left, *right, *pivot;
        int l, r; [COLOR=DarkGreen]/* left, right */[/COLOR]
        
        if( i >= j )
            return;
        
        l = i; r = j; pivot = AchaCartao( lc, ( l + r )/ 2 );
        left = AchaCartao( lc, i ); right = AchaCartao( lc, j );
        
        if( !left || !right || !pivot )
            return; [COLOR=DarkGreen]/* Erro a ser tratado */[/COLOR]
            
        do {
            while( compare( left, pivot ) < 0 ) { [COLOR=DarkGreen]/* Menor */[/COLOR]
                ++l; left = left->prox;
            }
            
            while( compare( right, pivot ) > 0 ) { [COLOR=DarkGreen]/* Maior */[/COLOR]
                --r; right = right->ant;
            }
            
            if( l > r )
                break;
                
            swap( left, right );
            ++l; --r;
        } while( l <= r );
        
        quicksort( i, r );
        quicksort( l, j );
    }
    
    Os índices considero sempre de 0 a n-1, em que n é o tamanho. Precisas de definir a função de comparação para que o algoritmo funcione. Qualquer erro avisa que vejo o que posso fazer.
     
  12. cada lista tem umas 5 coisas incluindo um string.. sem contar q preciso fazer por ponteiros e meu swip e ponteiros esta funciionando (ja testado)
    o Saldo para comparar tambem funciona
    e o quicksort para vetores tbm ta funcionando. .eh algo de nada q eu nao estou vendo
     
  13. pronto resolvidoi consertei os casos errados na swip consertie um errinho q tinha na quicksort, ele usava no swip o pivo q na verdade era o valor a ser comparado e consertei o ponteiro qdo removia um do meio nao atualizava o ant do proximo

    obrigado
     
  14. Consu

    Consu Power Member

    Nada como conseguir resolver os problemas... :p
     
  15. napalm

    napalm Power Member

    O próximo passo é corrigires a tua escrita, até mete dó.
     

Partilhar esta Página