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

carloscorreia94

Ordenação Array de Estruturas

Recommended Posts

carloscorreia94

Boa Tarde pessoal do PAP.

Sou estudante do Instituto Superior Técnico no 1º ano e esta é a minha pequena a apresentação.

Estou a fim de entregar um projeto de Programação em C e estou com dificuldades na parte final do programa.

O meu problema consiste na ordenação de um vetor de estruturas quando este tem que ser imprimido na consola.

Usando o algoritmo de quicksort consigo ordenar o meu array por apenas um field da estrutura, mas o que é pedido é: Se pagamentosA=pagamentosB então ordena por numero de sócio, ou seja ter dois critérios de ordenação, um precedente ao outro.

A minha ideia para fazer isto foi no define da função de partição do quicksort alterar o less para isto:

#define less(A, B) ((key(A) == key(B)) ? (key3(A) < key3(B)) : (key(A) < key(B)))

Vou apresentar aqui o código da estrutura e da função de partição do quicksort. Não sei o que esteja mal, mas ele não ordena de facto a array como quero...

(Já agora, não consigo alterar o tipo de codigo para C, e ele não me mete as cores ai...)

typedef struct {
int num;
char nome[tamanho_nome];
char apelido[tamanho_apelido];
int despesas;
int pagamentos;
int meses;
int modalidades[numero_modalidades];
} associado;
//Inicio do algoritmo de quicksort
#define key(A) (A.meses)
#define key3(A) (A.num)
#define less(A, B) ((key(A) == key(B)) ? (key3(A) < key3(B)) : (key(A) < key(B)))
#define compexch(A, B) if (less(B, A)) exch(A, B)
#define exch(A, B) { associado t = A; A = B; B = t; }
int partition(associado a[], int l, int r)
{
int i = l-1;
    int j = r;

    while(i < j)
    {
            while(less(a[++i],a[r]));
            while(less(a[r],a[--j]))
            {
                    if(j == l)
                            break;
            }
            if(i < j)
                    exch(a[i], a[j]);
    }
    exch(a[i],a[r]);
    return i;
}
void quicksort(associado a[], int l, int r,int tipo)
{
//Tipo: 0 -> Ordena segundo divida, 1-> Ordena segundo numero de associado
    int i;
    if(r <= l)
            return;
if(tipo==0) { i = partition(a,l,r); }
if(tipo==1) { i = partition2(a,l,r); }    
    quicksort(a,l,i-1,tipo);
    quicksort(a,i+1,r,tipo);
}
//Fim do algoritmo de quicksort

Se alguem puder dar uma ajuda agradeco! Obrigado ;)

Edited by thoga31
GeSHi

Share this post


Link to post
Share on other sites
ffunenga

Deixo aqui os detalhes em que reparei:

Tens que melhorar a indentação... não uses tabs ('\t'), usa antes 4 espaços.

Os defines e includes ficam melhor no inicio do codigo;

O terceiro if da função quicksort tem "partition2" como função, é um erro certo?

O parametro tipo da função quicksort podia ser antes uma variavel do tipo:

enum {DEBT, ASSOCIATE}

Cheira-me que o define exch "dá buraco". Talvez te safes melhor com:

void exch(associado *array, int i, int j) {
associado *tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}

EDIT:

Agora que olho melhor para este código, isto não funciona no teu caso pq tens um array de struct's e não de apontadores. De qq das formas, eu analisva melhor esse swap.

Edited by ffunenga
GeSHi

Share this post


Link to post
Share on other sites
carloscorreia94

Obrigado pela tua resposta pronta. O partition 2 não é um erro, aponta para outra ordenação que preciso de fazer, mas que está bem. Em relação ao enum, ainda não falei nesse código, por isso não o posso usar. Em relação a apontadores, pointers right? ainda não falamos nisso e é suposto usarmos um array de structs mesmo. Por isso como é que eu consigo contornar esta situação? obrigado!

Share this post


Link to post
Share on other sites
pmg

Apaga os #defines do teu código e faz funções a sério.

Em alternativa, não uses "side-effects" em expressões que vão ser usadas em macros.

No teu código

while(less(a[++i],a[r]));

a variavel i vai ser actualizada mais do que uma vez dentro da expansão da macro.

PS: Esta é uma razões que fizeram nascer a norma de usar TUDO EM MAISCULAS para macros: para chamar a atenção que são macros e por o programador de sobre-aviso sobre eventuais "side-effects".

Compara o teu código com o que eu (não) escreveria

while (LESS(a[++i], a[r])) /* void */;

Edited by pmg

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
carloscorreia94

Já percebi onde estava o erro, mas não consigo concretizar uma função de modo a que o ++i não se repita :/

Share this post


Link to post
Share on other sites
pmg

Com uma função em vez duma macro, o ++i não se repete

/* nao testado */
#include <stdio.h>
#define EXAMPLE(A, B) ((A)/((A) + (B)))
int example(int a, int b) { return a / (a + b); }
int main(void) {
 int i;
 int j;
 i = 42; j = 64;
 printf("EXAMPLE: %d\n", EXAMPLE(i++, j));
 printf("i tem %d\n", i);
 i = 42; j = 64;
 printf("example: %d\n", example(i++, j));
 printf("i tem %d\n", i);
 return 0;
}

Edited by pmg

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
carloscorreia94

Não estou a conseguir associar essa função de exemplo ao less. Se eu tirar o ++i de dentro dos argumentos da função do less e tentar incrementar o i apenas uma vez de outra maneira não tenho sucesso. Essa é a unica forma possivel que estou a ver neste momento.

Share this post


Link to post
Share on other sites
pmg

Em vez de

#define less(A, B) ((key(A) == key(B)) ? (key3(A) < key3(B)) : (key(A) < key(B)))

faz uma função propriamente dita

int less(int A, int B) {
return ((key(A) == key(B)) ? (key3(A) < key3(B)) : (key(A) < key(B)));
}


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

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.