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

whoami-r

Bubble Sort em lista ligada

Recommended Posts

whoami-r

Boas pessoal, é o seguinte: eu tenho uma lista ligada de estruturas em que cada nó é constituído por vários dados.

typedef struct dados_pilotos piloto, *pPiloto;
typedef struct dados_carros carro, *pCarro;
typedef struct lista carroPiloto, *pCarroPiloto;

struct dados_pilotos {
    char nome[100];
    int id;
    data nasc;   // struct para data de nascimento do piloto
    float peso;
    float exp;  // exp >= 0.0
    int impedimento;    // lesão ou penalização
    pPiloto prox;   // ponteiro para o prox piloto da lista
};

struct dados_carros {
    int id;
    int potencia;
    int avariado;   // fica impedido 1 corrida após acidente
    pCarro prox;    // ponteiro para o prox carro da lista
};

struct lista {
    piloto piloto;
    carro carro;
    int *tempo;
    pCarroPiloto prox;
};

Cada nó da lista é constituído por 1 piloto, 1 carro e um ponteiro *tempo que aponta para uma matriz com vários tempos de corridas. Aqui está a criação da lista:

pCarroPiloto criaListaCarroPiloto(piloto *p, carro *c, int tam, int carros)
{
    pCarroPiloto lista = NULL, aux;
    int i=0, j=0, cont=0;
    
    // i -> contador para percorrer os pilotos
    // j -> contador para percorrer os carros
    // cont -> conta o numero de vezes que é concluido um nó com sucesso (piloto+carro)
    
    for(i = 0; cont < tam; i++) {
        if(lista == NULL) {
            // PILOTOS
            if(p[i].impedimento == 0) {
                lista = malloc(sizeof(carroPiloto));
                strcpy(lista->piloto.nome, p[i].nome);
                lista->piloto.id = p[i].id;
                
                // CARROS
                while(j < carros) {
                    if(c[j].avariado == 0) {
                        lista->carro.id = c[j].id;
                        lista->prox = NULL;
                        j++;
                        cont++;
                        break;
                    }
                    else
                        j++;
                }
            }
            aux = lista;
        }
        else
        {
            if(p[i].impedimento == 0) {
                aux->prox = malloc(sizeof(carroPiloto));
                aux = aux->prox;
                strcpy(aux->piloto.nome, p[i].nome);
                aux->piloto.id = p[i].id;
                
                while(j < carros) {
                    if(c[j].avariado == 0) {
                        aux->carro.id = c[j].id;
                        aux->prox = NULL;
                        j++;
                        cont++; 
                        break;
                    }
                    else
                        j++;
                }
            }
        }
    }
    
    return lista;
}

E aqui as funções que criam os vários tempos por volta de cada combinação carro/piloto: 

int calculaIdade(data nasc, data atual)
{
    int meses[] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
    int idadeD, idadeM, idadeA;

    if(nasc.dia > atual.dia) {
        atual.dia = atual.mes + meses[nasc.mes - 1];
        atual.mes = atual.mes - 1;
    }

    if(nasc.mes > atual.mes) {
        atual.ano = atual.ano - 1;
        atual.mes = atual.mes + 12;
    }

    if(nasc.ano > atual.ano)
        exit(0);

    idadeA = atual.ano - nasc.ano;
    idadeM = atual.mes - nasc.mes;
    idadeD = atual.dia - nasc.mes;

    return idadeA;
}

int calculaSegundos(int idadeP, int pesoP, float expP, int PotC, int metros){
    return metros/20 + min(3, max(1, 20-expP))*intUniformRnd(1,3)
            + (float)pesoP/idadeP*intUniformRnd(1,2) + 500.0*(intUniformRnd(1,2))/PotC;
}

pCarroPiloto tempoPorVolta(pCarroPiloto lista, piloto *p, carro *c, treino caract)
{
    pCarroPiloto aux = lista, novo;
    int i=0, j=0, idade, peso, potencia, prob;
    int tempos[caract.n_carros][caract.voltas];     // matriz para guardar os tempos de cada piloto
    int volta[caract.n_carros];
    data nasc, atual;
    int h, m, s;;
    float exp;
    int soma;
    
    obtemData(&atual.dia, &atual.mes, &atual.ano, &h, &m, &s);
    printf("\n\n %2.2d/%2.2d/%d: %2.2d:%2.2d:%2.2d\n", atual.dia, atual.mes, atual.ano, h, m, s);
    
    for(i = 0; i < caract.n_carros; i++) {
        aux->tempo = malloc(sizeof(int) * caract.voltas);
        printf(" Piloto %d\t", aux->piloto.id);
        nasc = lista->piloto.nasc
        idade = calculaIdade(nasc,atual);
        peso = lista->piloto.peso;
        exp = lista->piloto.exp;
        potencia = lista->carro.potencia;
        soma = 0;
        
        for(j = 0; j < caract.voltas; j++) {
            tempos[i][j] = calculaSegundos(idade,peso,exp,potencia,caract.comprimento); 
            aux->tempo[j] = tempos[i][j];
            soma = soma + aux->tempo[j];
            aux->tempo[j] = soma;
            printf(" %d\t", aux->tempo[j]);
        }
        printf("\n");
        aux = aux->prox;
    }
    
    return lista;
}

O meu objetivo e a minha dúvida agora é como ordenar a lista por tempos. O último elemento da matriz contém sempre a soma dos tempos de cada piloto no total das voltas.

Ou seja, comparar o último elemento de cada linha da matriz e de seguida ordenar a lista por esse valor...

Não sei se fui bem explícito, mas qualquer dúvida digam.

Edited by whoami-r

Share this post


Link to post
Share on other sites
HappyHippyHippo

não vou comentar o teu código por algumas razões:

- não li a maior parte dele

- do que li será suficiente para responder a este tópico

- do que li vi que não ia gostar do resto

 

agora, responde a estas questões:

- se tens a lista preenchida com os tempos, e sabes qual o algoritmos de ordenação, qual é realmente a dúvida ? como aplicar o algoritmo ? que parte do algorimo é que não percebes ?


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
whoami-r

@HappyHippyHippo Eu sei como é que devo proceder visto que o algoritmo consiste em comparar 2 nós consecutivos e se o atual for superior ao próximo, então trocam. Mas a minha dúvida é, quando faço essa troca, não há risco de perder dados? Basta apenas criar um aux e fazer algo deste género? 

void troca(pCarroPiloto a, pCarroPiloto b) {
	pCarroPiloto aux = a;
	a = b;
	b = aux;
}

E a minha dúvida é, será esta a melhor solução? Ou então criar uma função que altere apenas os ponteiros de cada nó, sem ser assim necessário mudar os dados de um lado para o outro?

P.S. Qual o porquê de "não gostar do resto" ?

Edited by whoami-r

Share this post


Link to post
Share on other sites
HappyHippyHippo

1 - a troca nunca poderá ser feita dessa maneira. da maneira como tens definida a lista, terás sempre de copiar os dados "1 a 1"

2 - porque não gosto ? queres mesmo entrar nessa conversa ?


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
whoami-r

@HappyHippyHippo 1 - e se criar uma struct que contenha um ponteiro para a outra struct piloto?

2 - sim, se isso puder contribuir para melhorar o meu código sim

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.