Listas, quicksort

maquineta · 3 de Novembro de 2007

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

Consu · 3 de Novembro de 2007

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.

maquineta · 3 de Novembro de 2007

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 =)

Consu · 3 de Novembro de 2007

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.

maquineta · 3 de Novembro de 2007

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

Consu · 3 de Novembro de 2007

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

)

maquineta · 3 de Novembro de 2007

man, i tested here quickly and it seems everything is working properly, let me see now what u changed
tks

maquineta · 3 de Novembro de 2007

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 .. =/

Consu · 3 de Novembro de 2007

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.

maquineta · 3 de Novembro de 2007

o quicksort jka tentei de tudo.. até baixar o microsoft visual C++ (que nao consigo por em C)

continua algo errado q nao sei =/

Consu · 4 de Novembro de 2007

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.

maquineta · 4 de Novembro de 2007

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

maquineta · 6 de Novembro de 2007

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

Consu · 6 de Novembro de 2007

Nada como conseguir resolver os problemas...

napalm · 7 de Novembro de 2007

maquineta disse:
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

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

Listas, quicksort

maquineta

Membro

Consu

Power Member

maquineta

Membro

Consu

Power Member

maquineta

Membro

Consu

Power Member

maquineta

Membro

maquineta

Membro

Consu

Power Member

maquineta

Membro

Consu

Power Member

maquineta

Membro

maquineta

Membro

Consu

Power Member

napalm

Power Member