Bubble Sort em lista ligada

[whoami-r 0]

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 May 17, 2019 by whoami-r

[HappyHippyHippo 1,162]

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 ?

[whoami-r 0]

@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 May 17, 2019 by whoami-r

[HappyHippyHippo 1,162]

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 ?

[whoami-r 0]

@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

[HappyHippyHippo 1,162]

1 - um ponteiro é uma solução, dessa forma a única coisa que "muda de posição" é a referência a um dado que existe noutro lugar

2 - para isso necessitava de uma sessão de algumas horas, mas infelizmente não tenho tido muito tempo