Ir ao conteúdo

Posts recomendados

Postado

Boa tarde (ou boa noite), pessoal!!

Estou ainda com uma dúvida referente ao exercício da faculdade que estou a fazer. O exercício consiste em um objetivo: queria ordenar de maneira crescente e decrescente uma lista ordenada pelo serial de um produto. Por exemplo:

 

1. Output da lista exemplo

L ->
(324, 899.99, playstation 5) ->
(892, 399.99, mouse gamer) ->
(435, 199.99, headset gamer) ->
NULL

 

2. Output da lista em ordem crescente

L -> 
(324, 899.99, playstation 5) -> 
(435, 199.99, headset gamer) -> 
(892, 399.99, mouse gamer) -> 
NULL

 

3. Output da lista em ordem decrescente

L ->
(892, 399.99, mouse gamer) ->
(435, 199.99, headset gamer) ->
(324, 899.99, playstation 5) ->
NULL

 

Só que não tenho certeza se fiz da forma certa esta função que fiz. Poderiam me dar uma ajuda neste código?

Alguns itens que estou utilizando na composição do código:

 

A. Função que ordena a lista, sendo crescente ou decrescente:

// (e) Retorna a lista ordenada pelo número de série de seus produtos, de acordo com uma ordem passada pelo programa:
// ordem=0 significa ordem crescente;
// ordem=1 significa ordem decrescente.
Lista *ordenar(const Lista *L, int ordem) {
    // IMPLEMENTE ESTA FUNÇÃO
    //Estou pensando em como fazer
    if (ordem == 0){
        Lista *Crescente = criaLista();
        No *p;
        No *menor = p->prod->num_serie;

        if (listaEstaVazia(L)){return -1;}
        if (listaEstaVazia(Crescente)){return -1;}

        while(p != NULL){
            insereNoInicio(Crescente, p->prod->num_serie, p->prod->preco, p->prod->nome);
            p = p->prox;
        }
        return Crescente;
    }
    else {
        Lista *Decrescente = criaLista();
        No *p;
        No *maior = p->prod->num_serie;

        if (listaEstaVazia(L)){return -1;}
        if (listaEstaVazia(Decrescente)) {return -1;}

        while (p != NULL){
            insereNoInicio(Decrescente, p->prod->num_serie, p->prod->preco, p->prod->nome);
            p = p->prox;
        }
        return Decrescente;
    }
}

 

B. Structs 'no', 'lista' e 'produto':

// struct que define um produto
typedef struct _produto {
    int num_serie; // numero de série do produto
    char nome[64];
    double preco;
} Produto;

// struct que define um nó curcular duplamente encadeado
typedef struct _no {
    Produto *prod;
    struct _no *prox;
} No;

// struct que define uma Lista Ligada Simples
typedef struct _lista {
    No *inicio;
    No *fim;
    int tamanho; // numero de nós da lista
} Lista;

 

C. Função inserida na main para execução:

else if (strcmp(comando, "ordena") == 0) {
            scanf("%d", &ordem);

            Lista *L_aux = ordenar(L, ordem);
            destroiLista(&L);
            L = L_aux;
        }

 

Postado
    if (ordem == 0)
    {
        Lista *Crescente = criaLista();
        No *p;
        No *menor = p->prod->num_serie;

 

Pode até ser, mas o comum é passar uma função de comparação
 

    Lista*      _inserir_na_ordem(void*, Lista*, int(*)(void*, void*));

 

Sua estrutura não pode ser mudada? Podia melhorar...
 

Sobre isso:

 

// struct que define um n curcular duplamente encadeado
typedef struct _no {
    Produto *prod;
    struct _no *prox;
} No;

 

O que faz esse nó ser circular e duplamente encadeado? Um nó não é circular. É só um nó. Uma lista pode ser circular, duplamente encadeada ou os dois.
 

Não use acentos em comentários...

 

Sobre essa 

 

// struct que define uma Lista Ligada Simples
typedef struct _lista {
    No *inicio;
    No *fim;
    int tamanho; // numero de nós da lista
} Lista;// struct que define uma Lista Ligada Simples
  • mesmo sem o comentário dava pra imaginar que é uma lista. Use comentários expressivos, sobre o porque das coisas
  • Não precisa desse _lista. Pode ser uma estrutura anônima já que está justamente em um typedef. Não serve para nada esse nome.
  • pode colocar os outros ponteiros aí. Pode ser um vetor de ponteiros, ou um a um, como abaixo
typedef struct 
{
    No *inicio;
    No *fim;

	No*    i_crescente;
	No*    f_crescente;

	No*    i_decrescente;
	No*    f_decrescente;

    int    tamanho;

}   Lista1;

typedef struct 
{
    No *inicio;
    No *fim;

	No*    H[3]; // head 0 cronologico
	No*    T[3]; // tail 1 cresc 2 decresc

    int    tamanho;

}   Lista2;

 

 

 

int    insere3(Produto*, Lista*);

 

Como esse não é um programa muito ambicioso, pode nem usar void*nem funções e usar uma função assim insere3() que insere usando os 3 critérios.

 

O genérico seria considerar que cada critério tem um ponteiro de início, um ponteiro de fim e um critério de comparação e simplesmente usar um vetor. C é a linguagem certa para isso. Em cada posição do vetor teria N  grupos de 3 ponteiros, e pronto: a estrutura funcionaria para qualquer número de índices. 

 

As funções de comparação podiam ser simples como

 


int    f_crescente( Produto* um, Produto* outro)
    { return um->num_serie < outro->num_serie; }

int    f_decrescente( Produto* um, Produto* outro)
    { return um->num_serie > outro->num_serie; }

 

Não seria nada original. C faz isso no qsort(), java faz isso, C++ faz isso...

 

 

Postado

@arfneto 

 

Então, sobre isso, alterei o código da função.

Então ficou mais ou menos assim?

Lista *ordenar(const Lista *L, int ordem) {
  // IMPLEMENTE ESTA FUNÇÃO

  if (listaEstaVazia(L)) {
    return NULL;
  }
  else {
    if (ordem == 0){
        Lista *Crescente = criaLista();
        No *p = L->inicio;
        int menor = p->prod->num_serie;

        while(p != NULL){
          if (menor < p->prod->num_serie){
            insereNoInicio(Crescente, p->prod->num_serie, p->prod->preco, p->prod->nome);
          }
          p = p->prox;
        }
        return Crescente;
    }

    else {
        Lista *Decrescente = criaLista();
        No *p = L->inicio;
        int maior = p->prod->num_serie;

        while (p != NULL){
          if (maior > p->prod->num_serie){
            insereNoInicio(Decrescente, p->prod->num_serie, p->prod->preco, p->prod->nome);
          }
          p = p->prox;
        }
        return Decrescente;
    }
  }
}

 

Só que desta vez, ele apaga os menores números de série. E sobram apenas os maiores números.

Postado
29 minutos atrás, NhemonF disse:

Só que desta vez, ele apaga os menores números de série. E sobram apenas os maiores números

 

Você leu mesmo o que eu expliquei? Mesmo sem usar o mais genérico, faça o simples. Não precisa ordenar nada. É a sua lista. Está criando agora. O seu programa. Modifique insere() e prepare os 3 ponteiros. 

 

Se o resto já está funcionando leva meia hora. Não superestime o problema.

 

O genérico é o que expliquei: apenas copie o que todas bibliotecas fazem e use uma função de comparação.

 

Para um programa de estudo apenas use mais dois ponteiros. Não mexa em mais nada. Talvez apenas a função que mostra, passando o ponteiro de inicio e nao a lista, assim a mesma função serve para todos os critérios....

Postado
3 minutos atrás, arfneto disse:

Você leu mesmo o que eu expliquei? Mesmo sem usar o mais genérico, faça o simples. Não precisa ordenar nada. É a sua lista. Está criando agora. O seu programa. Modifique insere() e prepare os 3 ponteiros. 

Eu li, mas não entendi muito bem o que você disse.

 

46 minutos atrás, arfneto disse:

int f_crescente( Produto* um, Produto* outro) { return um->num_serie < outro->num_serie; }              int f_decrescente( Produto* um, Produto* outro) { return um->num_serie > outro->num_serie; }

 

Eu devo criar estas funções dentro ou fora da função que havia feito?

 

Postado
49 minutos atrás, arfneto disse:

Como esse não é um programa muito ambicioso, pode nem usar void*nem funções e usar uma função assim insere3() que insere usando os 3 critérios

 

teria lido isso também?

 

2 minutos atrás, NhemonF disse:

Eu devo criar estas funções dentro ou fora da função que havia feito?

funções não ficam dentro de funções em C

 

Viu o protótipo da função que te mostrei umas 3 vezes já?:

 

 Lista*      _inserir_na_ordem(void*, Lista*, int(*)(void*, void*));

 

Ali você passaria o nome da função de comparação... Se fosse o caso de usar.

 

Leu essa parte:

 

10 minutos atrás, arfneto disse:

Para um programa de estudo apenas use mais dois ponteiros. Não mexa em mais nada. Talvez apenas a função que mostra, passando o ponteiro de inicio e nao a lista, assim a mesma função serve para todos os critérios.

 

Postado

@arfneto Acho que pra ficar melhor, vou colar o código com as alterações.

/***************************
* LAB 04 - 02/12/2020
* SEU NOME - SEU PRONTUÁRIO
***************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

// struct que define um produto
typedef struct _produto {
    int num_serie; // numero de série do produto
    char nome[64];
    double preco;
} Produto;

// struct que define um nó curcular duplamente encadeado
typedef struct _no {
    Produto *prod;
    struct _no *prox;
} No;

// struct que define uma Lista Ligada Simples
typedef struct _lista {
    No *inicio;
    No *fim;
    int tamanho; // numero de nós da lista
} Lista;

typedef struct {
    No *inicio;
    No *fim;

	No*    i_crescente;
	No*    f_crescente;

	No*    i_decrescente;
	No*    f_decrescente;

    int    tamanho;

}   Lista1;

typedef struct {
    No *inicio;
    No *fim;

	No*    H[3]; // head 0 cronologico
	No*    T[3]; // tail 1 cresc 2 decresc

    int    tamanho;

}   Lista2;

/*********** HEADERS ***********/
Produto *criaProduto(int num_serie, double preco, char nome[64]);
void destroiProduto(Produto **prod_ref);
No *criaNo(int num_serie, double preco, char nome[64]);
Lista *criaLista();
void destroiLista(Lista **L_ref);
int listaEstaVazia(const Lista *L);
void imprime(const Lista *L);
void imprime_ultimo(const Lista *L);


// A SEREM IMPLEMENTADAS POR VOCÊ
void insereNoInicio(Lista *L, int num_serie, double preco, char nome[64]);
void removeProduto(Lista *L, int num_serie);
void removePrimeiraMetade(Lista *L);
Lista *inverter(const Lista *L);
Lista *ordenar(const Lista *L, int ordem);
/*******************************/

int main() {
    Lista *L = criaLista();

    char comando[64];
    int ordem;

    int num_serie;
    char nome[64];
    double preco;

    scanf("%s", comando);

    while (strcmp(comando, "para") != 0) {
        if (strcmp(comando, "insere_inicio") == 0) {
            scanf("%d", &num_serie);
            scanf("%lf", &preco);
            scanf(" %[^\t\n]s", nome);

            insereNoInicio(L, num_serie, preco, nome);
        }
        else if (strcmp(comando, "remove_produto") == 0) {
            scanf("%d", &num_serie);
            removeProduto(L, num_serie);
        }
        else if (strcmp(comando, "remove_primeira_metade") == 0) {
            removePrimeiraMetade(L);
        }
        else if (strcmp(comando, "inverte") == 0) {
            Lista *L_aux = inverter(L);
            destroiLista(&L);
            L = L_aux;
        }
        else if (strcmp(comando, "ordena") == 0) {
            scanf("%d", &ordem);

            Lista *L_aux = ordenar(L, ordem);
            destroiLista(&L);
            L = L_aux;
        }
        else if (strcmp(comando, "imprime") == 0) {
            imprime(L);
        }

        scanf("%s", comando);
    }

    return 0;
}
////////////////////////////////////

/*************** BODIES *****************/
// (a) Insere um nó no início da Lista com um novo produto, que possui os valores passados por parâmetro.
void insereNoInicio(Lista *L, int num_serie, double preco, char nome[64]) {
    // IMPLEMENTE ESTA FUNÇÃO
    No *p = criaNo(num_serie, preco, nome); //Cria um nó de um produto para inserir os dados
    p->prox = L->inicio; //Aponta a partir do início da lista encadeada
    L->inicio = p; //Coloca os dados do produto pro início
    L->tamanho++; //Aumenta o tamanho da lista para cada produto adicionado no encadeamento.

    if (L->fim == NULL) {
      L->fim = p;
    }
}

// (b) Remove o nó da lista cujo produto possua o número de série num_serie.
// Assuma que o número de série é único na lista.
// Se a lista estiver vazia ou não existir nenhum produto com o número de série, nada acontece.
void removeProduto(Lista *L, int num_serie) {
    // IMPLEMENTE ESTA FUNÇÃO
    //caso a lista esteja vazia
    if (listaEstaVazia(L)) {
        return;
    }

    //variável que indica se o número de serie foi encontrado ou não
    // 0 para não
    // 1 para sim
    int encontrou = 0;

    //verifica se o número encontrado está no início
    if(L->inicio->prod->num_serie == num_serie) {
        L->inicio = L->inicio->prox;
        encontrou = 1;
        L->tamanho--;
    }

    //verifica se o número encontrado está em qualquer posição
    else {
        No *no = L->inicio;
        No *anterior = NULL;

        //percorre todo o nó da lista para encontrar o valor inserido
        while(no != NULL && encontrou == 0) {
            if(no->prod->num_serie == num_serie) {
                anterior->prox = no->prox;
                encontrou = 1;
                L->tamanho--;
            }

            anterior = no;
            no = no->prox;
        }
    }
}

// (c) Remove a primeira metade da Lista. Caso a lista possua um número ímpar de elementos,
// considere que a primeira metade possui mais elementos
// (Ex: se a lista possuir 5 elementos, a primeira metade possui os 3 primeiros elementos).
// Se a lista tiver vazia, nada acontece.
void removePrimeiraMetade(Lista *L) {
    // IMPLEMENTE ESTA FUNÇÃO
    //Estou pensando no código

}

// (d) Retorna a Lista invertida. Se a lista está vazia, retorne uma lista vazia.
Lista *inverter(const Lista *L) {
    // IMPLEMENTE ESTA FUNÇÃO
    if (L == NULL) return NULL;
    No* p = L->inicio;

    Lista* Outra = criaLista();
    if (Outra == NULL) return NULL;
    while (p != NULL)
    {
         insereNoInicio(Outra, p->prod->num_serie, p->prod->preco, p->prod->nome);
         p = p->prox;
    };  // while()
    return Outra;
    return NULL;
}

// (e) Retorna a lista ordenada pelo número de série de seus produtos, de acordo com uma ordem passada pelo programa:
// ordem=0 significa ordem crescente;
// ordem=1 significa ordem decrescente.
Lista *ordenar(const Lista *L, int ordem) {
  // IMPLEMENTE ESTA FUNÇÃO

  if (listaEstaVazia(L)) {
    return NULL;
  }
  else {
    if (ordem == 0){
        Lista *Crescente = criaLista();
        No *p = L->inicio;
        int menor = p->prod->num_serie;

        while(p != NULL){
          if (menor < p->prod->num_serie){
            
          }
          p = p->prox;
        }
        return Crescente;
    }

    else {
        Lista *Decrescente = criaLista();
        No *p = L->inicio;
        int maior = p->prod->num_serie;

        while (p != NULL){
          if (maior > p->prod->num_serie){
            
          }
          p = p->prox;
        }
        return Decrescente;
    }
  }
}

int f_crescente( Produto* um, Produto* outro) {
     return um->num_serie < outro->num_serie;
}

int f_decrescente( Produto* um, Produto* outro) {
    return um->num_serie > outro->num_serie;
}

/************ FUNÇÕES JÁ IMPLEMENTADAS *************/
Produto *criaProduto(int num_serie, double preco, char nome[64]) {
    Produto *prod = (Produto *)calloc(1, sizeof(Produto));
    prod->num_serie = num_serie;
    prod->preco = preco;
    strcpy(prod->nome, nome);

    return prod;
}

void destroiProduto(Produto **prod_ref) {
    Produto *prod = *prod_ref;

    if (prod != NULL) {
        free(prod);
        *prod_ref = NULL;
    }
}

No *criaNo(int num_serie, double preco, char nome[64]) {
    No *no = (No*) calloc(1, sizeof(No));
    no->prod = criaProduto(num_serie, preco, nome);
    no->prox = NULL;

    return no;
}

Lista *criaLista() {
    return ((Lista*) calloc(1, sizeof(Lista)));
}

void destroiLista(Lista **L) {
    Lista *L_aux = *L;

    // remove todos os nós da lista
    No *p = L_aux->inicio;
    while (p != NULL) {
        No *no = p;
        p = p->prox;
        destroiProduto(&no->prod);
        free(no);
    }
    free(L_aux);
    *L = NULL;
}

int listaEstaVazia(const Lista *L) {
    return (L->inicio == NULL);
}

void imprime(const Lista *L) {
    printf("Tamanho da lista: %d\n", L->tamanho);
    printf("L -> ");

    if (!listaEstaVazia(L)) {
        No *p = L->inicio;

        while (p != NULL) {
            printf("(%d, %.2lf, %s) -> ", p->prod->num_serie, p->prod->preco, p->prod->nome);
            p = p->prox;
        }
    }
    printf("NULL\n\n");
}

 

  • Curtir 1
Postado

Essas Lista1 e Lista2 que te mostrei eram alternativas para você comparar.

 

Entenda que para cada critério é uma lista diferente, na prática.  Apenas na memória os produtos estarão lá parados. No entanto os ponteiros das listas servirão como índices diferentes para os mesmos dados. E dentro da mesma estrutura para atender o enunciado.

 

Os dados não fazem parte da lista. Apenas os endereços.

 

Pode até mudar a própria insere() que escreveu, e acrescentar uma função, um endereço de função. Se não passar nada---- NULL --- insere no inicio como sempre. Se passar algo usa essa função para percorrer a lista e inserir na ordem...

 

Você tem isso:

 

void insereNoInicio(Lista *L, int num_serie, double preco, char nome[64]);

 

Mas podia ter uma
 

void _insere(
  Produto* p, 
  Lista *L, 
  const char criterio, 
  int (*) f(Produto* um, Produto* outro )
);

 

e assim se usasse
 

        _insere( produto, lista, 0, NULL );

        _insere( produto, lista, 1, f_crescente );

        _insere( produto, lista, 2, f_decrescente );

 

em _insere() saberia como acessar o ponteiro certo. Só uma possibilidade. Sem muito trabalho

Postado

Eu não tinha lido a lista de protótipos obrigatórios :) e então tem lá

 

Lista *ordenar(const Lista *L, int ordem);

 

E então se é isso que tem que fazer é mais simples, já que vai criar outra lista afinal e não indexar a mesma por outro critério. No entanto é mais uma b0b@g3m do enunciado, porque o critério então tinha que fazer parte da lista, de modo que todas as inserções seguissem o mesmo critério no futuro.

 

Sem isso novas inserções serão sempre no início, algo praticamente inútil e destruindo a classificação. Insisto que era mais prático e simples manter os ponteiros TODOS dentro da mesma lista, mas um enunciado é um enunciado.

 

Assim sugiro que apenas escreva como eu disse, usando uma _inserir() sensível ao critério afinal. E acrescente o campo critério à lista!

 

 

Postado
11 horas atrás, arfneto disse:

E então se é isso que tem que fazer é mais simples, já que vai criar outra lista afinal e não indexar a mesma por outro critério. No entanto é mais uma b0b@g3m do enunciado, porque o critério então tinha que fazer parte da lista, de modo que todas as inserções seguissem o mesmo critério no futuro.

 

11 horas atrás, arfneto disse:

Sem isso novas inserções serão sempre no início, algo praticamente inútil e destruindo a classificação. Insisto que era mais prático e simples manter os ponteiros TODOS dentro da mesma lista, mas um enunciado é um enunciado.

 

Bom... quer dizer então que devo, basicamente, escrever uma Bubble Sort para ordenar de forma decrescente ou crescente?

 

Porque, pelo que entendi em outros fóruns e outros artigos que busquei ver, a função irá percorrer todo a lista simples encadeada, e verificar se o num_serie é menor que o outro.

 

Postado
10 minutos atrás, NhemonF disse:

Bom... quer dizer então que devo, basicamente, escrever uma Bubble Sort para ordenar de forma decrescente ou crescente?

 

Não, não quer dizer nada disso. E entenda que não faria sentido usar bubble sort para classificar algo assim. E como Bubble Sort é um algoritmo e algoritmo é macho, não fêmea, acho que deve escrever "um" e não "uma".

 

Bubble Sort classifica in-place. Isso quer dizer que você pega um vetor, por exemplo, com 5000 coisas, e classifica esse mesmo vetor por algum critério. Imagino que já tenha programado isso antes então deve se lembrar.

 

Você está criando uma lista nova, e se fosse de fato importante, tipo um enunciado ou uma aposta :)  poderia até usar bubble sort ou qualquer outro algoritmo: Copia a lista para a outra e depois classifica usando uma função de comparação, como faz o qsort() e como eu te expliquei, e tratando a lista como se fosse um vetor.

 

Mas fora esses dois casos, enunciado ou aposta, seria uma ideia bem ruim. B3st@ até. Pense assim: você tem a lista original. Então não há esse lance de sort. Não como algoritmo. O natural é usar insertion sort, porque é o que vai estar fazendo. Mas não é assim um algoritmo: é apenas o óbvio: como a lista vai ser classificada por um critério você usa o tal critério e coloca cada item na posição definitiva. 

 

Chamar insertion sort de algoritmo é como chamar o algoritmo de fisher-yates para embaralhamento de algoritmo. Com todo respeito ao Fisher e ao Yates ;) : é só o óbvio. Parece coisa da Apple, tentando dizer que inventou o óbvio. Qualquer criança usaria isso sem pensar para colocar coisas em ordem (insertion sort) ou embaralhar (fisher-yates).

 

Exemplo
 

==> lista original

        5 Elementos na lista

      serie     preco           nome
          4       205.16        testeG
          3       418.93        teste[
          2       183.63        testeY
          1       254.03        testeX
          0       165.59        teste2

 

Então ...

 

Para usar o "algoritmo" de insertion sort e criar uma lista por ordem crescente de número de série, inserindo sempre no início

  • Você escolhe o maior, 4 e põe na nova lista
  • Você escolhe o maior restante, 3, e põe na lista
  • E continua até o fim da entrada, que você sabe que tem L->tamanho elementos.

É só isso
 

1 hora atrás, NhemonF disse:

Porque, pelo que entendi em outros fóruns e outros artigos que busquei ver, a função irá percorrer todo a lista simples encadeada, e verificar se o num_serie é menor que o outro

 

Não precisava pesquisar em outros foruns e artigos. Basta escrever o programa como te expliquei. E É claro que vai percorrer a lista toda, já que a lista nova vai ter os mesmos elementos, mas em outra ordem :) 

 

 

De volta ao programa, em C

 

A lista tem 3 campos, série, nome e preço. É razoável querer classificar por qualquer um desses. E o normal seria inserir sempre no fim e não no início, para preservar a ordem de entrada dos elementos, tipo... uma fila. Essas estruturas, o enunciado e o modelo em si desse enunciado não são assim uma beleza...

 

Para por em ordem tudo que você precisa é o acesso aos elementos e uma função que compara 2. 

 

Casos especiais

  • uma lista vazia gera claro uma lista vazia
  • uma lista com um cara só está em ordem por qualquer critério

Então imagine a função exemplo
 

int f_crescente(No* no_na_lista, Produto* novo)
{
    if (novo == NULL) return 1; // nao esperado
    if (no_na_lista == NULL)
    {
        return -1; // acabou
    };
    return no_na_lista->prod->num_serie < novo->num_serie; // aqui
};  // f_crescente()

 

A ideia é claro comparar dois produtos, mas é melhor passar o nó no caso da lista. Porque? Simples: se chegou no fim da lista não tem produto e se passar o endereço do nó então pode testar lá dentro de f_crescente() o caso em que a lista acabou. Por exemplo se tem os números de série de 1 a 30 e vem o 300 vai inserir no fim... Veja no código como simplifica sua vida: aquele segundo if() quer dizer que a comparação funciona também quando a lista acabou e vai inserir no fim, e assim não precisa testar isso no código de ordena() ;) 

 

Retornar 1 quer dizer que está na ordem: o novo é maior. Retornar 0 quer dizer que o número de série do novo é menor e então vai inserir o novo antes desse na lista. O simples. Insertion Sort. Pode chamar de algoritmo mas qualquer criança faria assim: pega um por um e põe na ordem.

 

Tem 2,4,6,8 e vai inserir o 7: então quando comparar 7 com 8 vai retornar 0 e sabe que achou o lugar.

 

Claro que classificar por nome dá na mesma:
 

int f_nome(No* no_na_lista, Produto* novo)
{
    if (novo == NULL) return 1; // nao esperado
    if (no_na_lista == NULL)
    {
        return -1; // acabou
    };
    return strcmp(no_na_lista->prod->nome, novo->nome) < 0;
};  // f_nome()


strcmp() já retorna >0 se o segundo nome for maior que o primeiro e -1 se for menor :) 

 

E por preço?
 


int f_preco_crescente(No* no_na_lista, Produto* novo)
{
    if (novo == NULL) return 1; // nao esperado
    if (no_na_lista == NULL)
    {
        return -1; // acabou
    };
    return no_na_lista->prod->preco < novo->preco; // aqui
};  // f_preco_crescente()

 

Entendeu? Dá na mesma. Uma função compara 2 elementos e retorna 0 ou 1.

 

Mas e como ordenar?

 

Só isso: lê a lista original, insere na nova lista usando a função para comparar...

 

E o critério?

 

C é uma boa linguagem para escrever isso. C++ seria melhor, mas nem sempre se pode escolher.

 

Então tem por exemplo os critérios

 

    // 'ordem'
    // 0 = crescente
    // 1 = decrescente
    // 2 = nome
    // 3 = preco (crescente)

 

e como viu poderia ter 300. Basta escrever uma função de comparação para cada critério. 

 

E imagine as funções

 

        f_crescente,
        f_decrescente,
        f_nome,
        f_preco_crescente

 

para cada critério.

 

Então pode declarar direto em C

 

    int (*f[4])(No*, Produto*) =
    {
        f_crescente,
        f_decrescente,
        f_nome,
        f_preco_crescente
    }; // para nao ter que testar mais

 

E achar a posição para inserir SEGUNDO QUALQUER CRITERIO escrevendo só isso:
 

        // se posiciona no inicio
        No* destino = outra->inicio;
        while (f[ordem](destino, origem->prod) > 0)
        {
            antes = destino; // nao tem ponteiros para tras
            destino = destino->prox; // avanca
        };  // while()

 

supondo que vai criar a lista outra  a partir da lista origem segundo criterio ordem

 

C foi escrita para escrever sistemas operacionais. E esse tipo de problema é comum em sistemas operacionais. Então é trivial tratar funções assim em C. Podia ser mais simples ainda, mas sua estrutura não tem ponteiros para trás então você precisa salvar o anterior...

Porque? Simples: se tem lá 2 4 6 8 e vai inserir o 7 precisa saber que antes do 8 estava o 6, já que o 6 aponta para o 8 mas o oito não sabe quem aponta para ele porque sua lista não tem ponteiros para trás... ;) 

 

Quando você escreve f[ordem]() C vai lá no vetor e chama a função certa para o critério. Não precisa testar p0rr@ nenhuma. Mágica.

 

 

 

 

  else {
    if (ordem == 0){
        Lista *Crescente = criaLista();
        No *p = L->inicio;
        int menor = p->prod->num_serie;

        while(p != NULL){
          if (menor < p->prod->num_serie){
            insereNoInicio(Crescente, p->prod->num_serie, p->prod->preco, p->prod->nome);
          }
          p = p->prox;
        }
        return Crescente;
    }

    else {
        Lista *Decrescente = criaLista();
        No *p = L->inicio;
        int maior = p->prod->num_serie;

        while (p != NULL){
          if (maior > p->prod->num_serie){
            insereNoInicio(Decrescent

 

Não está classificando na verdade... Você tem que inserir TODOS os nós da lista original na nova.

E note que o código está praticamente duplicado, mudando apenas um sinal. Deve ter uma outra maneira de escrever.

 

Veja o código e as notas acima...

Postado
1 hora atrás, arfneto disse:
// se posiciona no inicio 
No* destino = outra->inicio; 
while (f[ordem](destino, origem->prod) > 0) { 
	antes = destino; // nao tem ponteiros para tras 
	destino = destino->prox; // avanca 
}; // while()

 

 

Só não entendi de onde veio o "antes"... Da onde ele veio?

 

Vou escrever o que você escreveu, se importar. E o que eu imaginei. Mas por enquanto em ordem crescente:

Lista *ordenar(const Lista *L, int ordem)
{
    // IMPLEMENTE ESTA FUNÇÃO
    //Estou pensando em como fazer
    if (listaEstaVazia(L))
    {
        return;
    }
    else
    {
        Lista *Crescente = criaLista();
        No *destino = Crescente->inicio;
        No *origem = L->inicio;
        int (*f[4]) (No*, Produto*);

        while (f[ordem] (destino, origem->prod) > 0)
        {
            No *antes = destino;
            insereNoInicio(Crescente, destino->prod->num_serie, destino->prod->preco, destino->prod->nome);
            destino = destino->prox;
        }
    }
}


int f_crescente(No* no_na_lista, Produto* novo)
{
    if (novo == NULL) return 1; // nao esperado
    if (no_na_lista == NULL)
    {
        return -1; // acabou
    };
    return no_na_lista->prod->num_serie < novo->num_serie; // aqui
}

 

Postado
28 minutos atrás, NhemonF disse:

Só não entendi de onde veio o "antes"... Da onde ele veio?

 

Não "veio". Está indo. Eu expliquei porque:

 

2 horas atrás, arfneto disse:

Podia ser mais simples ainda, mas sua estrutura não tem ponteiros para trás então você precisa salvar o anterior...

Porque? Simples: se tem lá 2 4 6 8 e vai inserir o 7 precisa saber que antes do 8 estava o 6, já que o 6 aponta para o 8 mas o oito não sabe quem aponta para ele porque sua lista não tem ponteiros para trás...

 

Não tinha entendido essa parte? antes é um ponteiro para o nó anterior porque as estruturas de dados que recebeu são ingênuas e não tem. E eu mostrei o exemplo com os números.
Preste atenção: se vai inserir o 7 entre o 6 e o 8 e não tem ponteiros pra trás já era. É mais difícil e não mais fácil usar ponteiros para um lado só. O 6 aponta para o 8 mas já passou por ele e não tem como voltar. Só que precisa corrigir o ponteiro de 6. Já te disse várias vezes. E mostrei porque.

 

Sobre isso não entendo o que quiz dizer:

 

32 minutos atrás, NhemonF disse:

Vou escrever o que você escreveu, se importar. E o que eu imaginei. Mas por enquanto em ordem crescente

 

Eu te disse

 

2 horas atrás, arfneto disse:

poderia ter 300. Basta escrever uma função de comparação para cada critério

 

e te mostrei exatamente como declarar e usar. É algo típico de programação de sistemas mas raro em programas ou livros para iniciantes:

 

image.png.4ac8b4db26a0a4fefd121f5bda7720eb.png

 

 






















Isso como escreveu
 

No *origem = L->inicio;
int (*f[4]) (No*, Produto*);

while (f[ordem] (destino, origem->prod) > 0)
{
    No *antes = destino;

...


não faz qualquer sentido. Não declare valores sem inicializar. Só vai cancelar seu programa instantaneamente.

 

Mudanças e vícios

 

Eu te expliquei várias coisas que deve mudar em seis programas se quer diminuir o tempo de desenvolvimento e de testes, e talvez aprender antes algo que terá que aprender de todo modo. 
 

Você aparentemente não mudou uma linha no modo como escreve seus programas e mesmo na estrutura deles.

 

        Lista *Crescente = criaLista();
        No *destino = Crescente->inicio;
        No *origem = L->inicio;
        int (*f[4]) (No*, Produto*);

        while (f[ordem] (destino, origem->prod) > 0)
        {
            No *antes = destino;
            insereNoInicio(
		Crescente,
		destino->prod->num_serie,
		destino->prod->preco,
		destino->prod->nome);
            destino = destino->prox;

 

E mesmo em trechos que copiou do que eu escrevi teve a ideia de mudar ao contrário do que eu escrevi e te recomendei

:D :D :D 

 

Entenda que o tipo de antes é No*. E por isso *antes é No. E você está declarando antes. Não existe declaração para *antes. Trata-se de uma operação. Escreva No* porque é isso o que é. E ajuda na leitura e compreensão de coisas que, a julgar por esse programa, ainda não domina...

 

Mesmo caso de ordenar(). O tipo de uma variável não tem asteriscos. Só vai estar jogando contra a legibilidade de seu próprio programa.
 

E separe os arquivos do modo como te expliquei. Leva minutos e a vantagem dura toda a vida. Não perca tempo.

 

Escreva em torno dos dados. E se não entendeu algo que te expliquei pergunte na hora. Nesses dias estou com tempo e não é sempre assim... Mas faça sua parte e ao menos pense a respeito antes de alterar o que EU escrevi para um modo que eu te disse para NÃO usar e aí inserir sem ter entendido do que estou falando :) 

 

O que acha que em seu programa a linha abaixo vai fazer?
 

  int (*f[4]) (No*, Produto*);

 

E essa?
 

while (f[ordem] (destino, origem->prod) > 0)

 

Nada. Só vai cancelar seu programa.

 

Escreva em torno dos dados.

Capriche nas estruturas ANTES de começar a programar.

E não escreva uma única linha sem ter um propósito.

 

 

 

 

 

 

 

 

Postado
6 minutos atrás, arfneto disse:
No *origem = L->inicio; 
int (*f[4]) (No*, Produto*); 

while (f[ordem] (destino, origem->prod) > 0) { 
  No *antes = destino; 
  
...

 

 

Então nesta linha aqui:

int (*f[4]) (No*, Produto*);

 

Devo escrever nest maneira?

 int (*f[2]) (No*, Produto*) = {
	f_crescente,
	f_decrescente
}

 

===================================================================

11 minutos atrás, arfneto disse:

Não tinha entendido essa parte? antes é um ponteiro para o nó anterior porque as estruturas de dados que recebeu são ingênuas e não tem. E eu mostrei o exemplo com os números.
Preste atenção: se vai inserir o 7 entre o 6 e o 8 e não tem ponteiros pra trás já era. É mais difícil e não mais fácil usar ponteiros para um lado só. O 6 aponta para o 8 mas já passou por ele e não tem como voltar. Só que precisa corrigir o ponteiro de 6. Já te disse várias vezes. E mostrei porque.

 

Não havia entendido esta parte, porque ao ler o codigo que você escreveu, eu fiquei me perguntando sobre isso.

 

 

===================================================================

13 minutos atrás, arfneto disse:

Escreva em torno dos dados. E se não entendeu algo que te expliquei pergunte na hora.

Como assim escrever em torno dos dados?

 

 

===================================================================

18 minutos atrás, arfneto disse:

int (*f[4]) (No*, Produto*);

Aqui, não aconteceu nada ://

 

 

Estou tentando, agora, fazer de outra forma:

image.png.01610e398ecc5e50b2c1ea0470c37dcd.png

Pensei agr em colocar um [switch...case] para isso. Mas, ao mesmo tempo, estou colocando as funções que você escreveu

image.png.f9dcb57f3e2553ace5553b8edc58256c.png

 

E, claro, as modificações feitas no código. Só que vou precisar de um tempo para pensar em como aplicá-lo.

Postado
7 minutos atrás, NhemonF disse:

Não havia entendido esta parte, porque ao ler o codigo que você escreveu, eu fiquei me perguntando sobre isso.

 

E agora entendeu a falta que faz ter um ponteiro para cada lado?

 

7 minutos atrás, NhemonF disse:

Devo escrever nest maneira?

 

Sim, esse é o plano...

 

7 minutos atrás, NhemonF disse:

Aqui, não aconteceu nada ://

 

 

Claro que não. É só uma declaração sem sentido. Tente usar algum f() e como deve ter visto seu programa cancela na hora porque não existe nenhum.

Não entendeu ainda o que é f[ ]?

O que é f[ ] para você?

Qual o tipo de f? 

 

9 minutos atrás, NhemonF disse:

Como assim escrever em torno dos dados?

 

Programar em torno das estruturas de dados. Desde o início. Antes de começar a programar menus e leituras e telas que não levam a nada. 

 

Veja uns exemplos de seu programa:

  • É sabido que seu programa trata dados de produto, em listas ligadas. Então é claro que vai ser preciso iterar sobre um conjunto de produtos e a primeira função que vai usar é uma que mostra os valores, afinal precisa testar o programa. Essa é a primeira função que vai escrever. Antes sequer de ter uma lista de produtos porque ela precisa funcionar para uma lista vazia... Eis o produto:
    • // struct que define um produto
      typedef struct _produto {
          int num_serie; // numero de série do produto
          char nome[64];
          double preco;
      } Produto;
    • é claro que uma struct _produto e que define um nome Produto se refere a um produto. Podia ficar sem esses comentários. Mesmo caso do número de série. E não há razão para usar acentos em comentários. Só vai dar problema se tentar imprimir ou muitas vezes apenas ver na tela. E nada acrescenta
    • Eis a função que recebeu, ou escreveu:
    •  
      void        imprime(const Lista* L)
      {
          printf("Tamanho da lista: %d\n", L->tamanho);
          printf("L ->\n");
      
          if (!listaEstaVazia(L)) {
              No* p = L->inicio;
      
              while (p != NULL) {
                  printf("(%d, %.2lf, %s) ->\n", p->prod->num_serie, p->prod->preco, p->prod->nome);
                  p = p->prox;
              }
          }
          printf("NULL\n\n");
      };  // imprime()
    • E assim funcionava antes:
      image.png.38c3389c6a5517cc7de8139e06caaf10.png
       

 

 

 

 

 

 

 

 

Numa linha só, difícil de ler e ambíguo porque só tinha dois valores e o título do tópico falava só em inverter nós em uma lista encadeada, quando na verdade era para gerar uma lista nova com todos nós em ordem inversa :) 

 

Mudando um pouco e escrevendo em torno desses dados

  • O produto
     
    typedef struct
    {
        char     nome[64];
        unsigned num_serie;
        double   preco;
    
    }   Produto;
     
    • Sim, é um produto. Não precisa dizer mais 3x
    • Convenção: a primeira letra em maiúscula reservada para nomes definidos no programa
    • Uma linha em branco antes do nome, assim destaca a palavra na listagem e na tela
    • variáveis em ordem alfabética quando não há uma clara hierarquia entre elas
  •  A função:
        void        mostra(const Lista* L, const char*);

    Aqui tem um parâmetro a mais, que pode ser 0 ou NULL, porque estamos testando e pode ser muito útil

    • Um possível código:
       

      void        mostra(const Lista* L, const char* msg)
      {
          if (msg != 0) printf("\n\n==> %s\n\n", msg);
          printf("\t%d Elementos na lista\n\n", L->tamanho);
          printf("      serie     preco  nome\n");
      
          if (!listaEstaVazia(L)) {
              No* p = L->inicio;
      
              while (p != NULL) {
                  printf("%11d  %8.2f  %-30s\n", p->prod->num_serie, p->prod->preco, p->prod->nome);
                  p = p->prox;
              }
          }
      };  // mostra()

       

    • Qual a diferença? como estamos escrevendo em torno dos dados, no próprio IDE se pode escrever
    •      *    1    *    2    *    3    *    4    *    5    *   5 
      012345678901234567890123456789012345678901234567890123456789
            serie     preco  nome
      aaaabbbbccc  aaaabbbb  aaaabbbbccaaaabbbbccaaaabbbbccaaaabbb
      aaaabbbbccc  aaaabbbb  aaaabbbbccaaaabbbbccaaaabbbbccaaaabbb
      aaaabbbbccc  aaaabbbb  aaaabbbbccaaaabbbbccaaaabbbbccaaaabbb
      aaaabbbbccc  aaaabbbb  aaaabbbbccaaaabbbbccaaaabbbbccaaaabbb
    • E aí tem os números das colunas e a posição das coisas como se quer que mostre. ANTES de escrever o programa. Claro que as duas primeiras linhas são um gabarito
    • printf() retorna o tamanho da string. Assim pode controlar a largura do campo se preciso.
    • claro que não tem as 64 possíveis letras de nome, mas importa mesmo? Vamos escrever só as primeiras 30 :) 
    • e tem um possível título que se passar vai sair, bem, como título. Algo assim:
          mostra(preco, "Em ordem crescente de PRECO");
    • será que funciona? claro, porque foi resolvido antes e porque pode testar em separado. E é bom poder ter um título porque na saída dos testes fica fácil colocar uma mensagem explicando o que é o que:
    • 
      ==> Em ordem crescente de PRECO
      
              5 Elementos na lista
      
            serie     preco           nome
             1054       191.97        teste2
             8473       196.61        teste5
             1852       246.45        teste?
             7908       403.61        testeX
             5903       418.93        teste[
  • E os dados? É preciso ter uma lista de produtos para testar. Não dá pra imaginar ficar parado inventando nomes números e preços para testar um programa. 10 produtos? 30 campos. 10 testes? 300 campos. Inviável.
    • uma função assim
       
          cria_teste(N);

      Que retornasse uma lista com N produtos seria bem conveniente e aí a gente pode chamar a tal função mostra() e já testar as duas. ANTES de continuar implementando coisas como ordenar listas ou inverter.

    • melhor ainda se mostra retornasse sempre os mesmos valores, para que a gente possa testar sempre com os mesmos dados com 5 ou 5000 produtos quantas vezes for preciso até dar certo.

    • Será difícil? Não. Veja uma
       

      Lista* cria_teste(int N, int S)
      {
          // cria uma lista com N itens usando S como "semente" para rand()
          srand(S);
          char nome_teste[30] = "testeX";
          double valor = 0;
          int serie = 0;
          Lista* L = criaLista();
          for (int i = 0; i < N; i += 1)
          {   // cria dados diferentes mas reproduzeis
              serie = rand() % 10000 + 100;
              nome_teste[5] = '0' + rand() % 50; // inventa uma letra no fim
              valor = 100. + (rand() % 350) + (rand() % 99 / 100.); // inventa um preco
              insereNoInicio(L, serie, valor, nome_teste);
          };
          return L;
      };
    • Não precisamos de muitos produtos. Então essa aí usa o nome como "testeX" e varia a última letra. Assim vai gerar também duplicados possivelmente em todos os campos, o que é bom para os testes.
    • o que importa é que ela gera sempre os mesmos e então posso usar um programa assim:
      int main(void)
      {
          Lista* L = cria_teste(15,201212);
          mostra(L, "teste: lista gerada" );
          return 0;
      }
    • e ele vai mostrar
       
      
      ==> teste: lista gerada
      
              15 Elementos na lista
      
            serie     preco  nome
             9363    418.98  testeG
             3773    239.08  teste1
             1805    269.07  testeO
             7114    238.51  testeI
             3214    224.02  teste7
             1695    258.19  teste8
             8960    250.84  testeA
             3800    436.20  testeZ
             5617    349.64  testeU
             9188    240.83  teste@
             7908    403.61  testeX
             8473    196.61  teste5
             5903    418.93  teste[
             1054    191.97  teste2
             1852    246.45  teste?

       

    • sempre. se mudar para 2 apenas os dois primeiros. Se mudar para 1600 esses 15 mais o resto.
    • isso é importante: nem começamos a escrever o programa ainda. Mas já podemos testar várias coisas. 
    • e rápido e repetidas vezes. Isso é o que importa.
    • É preciso ter um protótipo logo, validar as ideias logo. Desistir de uma ideia ruim logo. Assim se recebe antes, se consegue o emprego antes, entrega o trabalho antes...


       

 

 

Postado
4 horas atrás, NhemonF disse:

Pensei agr em colocar um [switch...case] para isso. Mas, ao mesmo tempo, estou colocando as funções que você escreveu

 

O comando se chama switch. case é o prefixo do label. E nada acrescenta nesse caso em que o número de opções é mínimo. E podia ser if(). Tanto faz. Podia ter uma função para cada caso, completa, e ficaria mais legível.

 

Não entendo porque está se preocupando com isso se eu já te mostrei acho que 3 vezes que pode chamar as funções indiretamente, SEM TESTE NENHUM, como se faz no mundo profissional em todo sistema desde os '70. Se chama VFT, virtual function table, e é um conceito central na web, em javascript, em C++ e nos sistemas operacionais.

 

E eu te mostrei o código, o que não é assim fácil de encontrar assim em forums.

 

 

Se aplicar o que te expliquei, escrever em torno dos dados, ao invés de ficar circulando em torno de coisas como switch() ou if() ou testes, terá algo assim em main()
 

    Lista* invertida = inverter(L);
    mostra(invertida, "lista invertida" );

    Lista* crescente = ordenar(L, 0);
    mostra(crescente, "Em ordem CRESCENTE de numero de serie");

    Lista* decrescente = ordenar(L, 1);
    mostra(decrescente, "Em ordem DECRESCENTE de numero de serie");

    Lista* nome = ordenar(L, 2);
    mostra(nome, "Em ordem de nome");

    Lista* preco = ordenar(L, 3);
    mostra(preco, "Em ordem crescente de PRECO");

 

E acho que dá pra entender o que main() faz. Legível quer dizer que é mais fácil de testar e de programar e corrigir...

 

E se fosse escrever em torno dos dados, como começar a função ordenar()?

 

Antes de programar, vamos ver os dados. Ordenar() é:
 

    Lista*      ordenar(const Lista* L, int ordem);

 

Então antes de tudo temos os casos particulares:

  • uma lista vazia gera outra vazia. Não é um erro.
  • uma lista com um produto só gera outra igual, tanto faz o critério, claro.
  • o critério tem que fazer parte da lista, porque a partir de uma lista classificada por ordem decrescente de número de série, por exemplo, você não vai ficar inserindo sempre no início e zoando tudo, certo? claro que vai querer continuar inserindo pelo mesmo critério, mantendo a lista ordenada.
  • a partir do fato de ter um critério de ordenação para a lista uma função como inverter() teria que ser alterada para inverter o critério também ou vai furar tudo. 
  • claro, tem que ter uma função de comparação para cada critério. Não dá para ordenar sem comparar

E a função ordenar() tem um roteiro então:

  • se tem um elemento ao menos na lista, copia para a saída.
  • se tem mais de um então do segundo até o último insere na lista nova. O que seria isso? um loop. Um while, um for, qualquer coisa. O for parece o mais trivial porque se sabe que vai do SEGUNDO ao último, de um em um.
  • Então se posiciona no início da nova lista e avança usando a função de comparação ou testando simplesmente, sem função, até achar a posição onde vai inserir o item.
    • Como escrevemos em torno dos dados e os critérios de comparação estão definidos, uma função para cada critério está testada e disponível, usando o recurso de copiar e colar :) e alterando uma linha ou duas porque é tudo igual
      • no for() o que deve ser feito?
      • Usa a função correta de comparação e avança na entrada até achar o lugar certo. "Até achar o lugar certo" sugere um loop do tipo while( nao achou ) ou do{}while(nao achou) certo?
      • encontrada a posição nova vamos ter 3 opções: o novo elemento poderá ser o primeiro, o último ou ir no meio da lista de saída. Isso sugere um if() dentro de outro if(), que dá 4 opções, certo?

Pois é: em resumo a função que vamos escrever:

  • vai ter um preparo que é criar o vetor com as funções, trivial, como já mostrei 3x
  • vai copiar o primeiro elemento para saída se existir
  • a partir do segundo se existir usa um for() para inserir na saída
  • dentro do for() usa um while() para achar o ponto de inserção
    • depois de achar o ponto usa dois if() para ver se vai inserir no inicio, no fim ou no meio
  • retorna o endereço da lista nova

Eu escrevi assim. Aparentemente funcionou na primeira execução. Só escrevi depois de ter considerado os dados. E rodei aquele main() que mostrei acima:
 

Teste com 7 itens, semente = 201214


==> teste: lista gerada

        7 Elementos na lista
        [Ordem: Inseridos no fim da lista]

      serie     preco  nome
       2055    398.49  testeU
       9251    301.55  teste:
       8776    215.88  teste5
       7215    394.88  testeN
       6158    122.82  teste_
       8916    115.82  teste6
       1858    407.60  teste\


==> lista invertida

        7 Elementos na lista
        [Ordem: Inseridos no fim da lista]

      serie     preco  nome
       1858    407.60  teste\
       8916    115.82  teste6
       6158    122.82  teste_
       7215    394.88  testeN
       8776    215.88  teste5
       9251    301.55  teste:
       2055    398.49  testeU


==> Em ordem CRESCENTE de numero de serie

        7 Elementos na lista
        [Ordem: crescente de numero de serie]

      serie     preco  nome
       1858    407.60  teste\
       2055    398.49  testeU
       6158    122.82  teste_
       7215    394.88  testeN
       8776    215.88  teste5
       8916    115.82  teste6
       9251    301.55  teste:


==> Em ordem DECRESCENTE de numero de serie

        7 Elementos na lista
        [Ordem: decrescente de numero de serie]

      serie     preco  nome
       9251    301.55  teste:
       8916    115.82  teste6
       8776    215.88  teste5
       7215    394.88  testeN
       6158    122.82  teste_
       2055    398.49  testeU
       1858    407.60  teste\


==> Em ordem de nome

        7 Elementos na lista
        [Ordem: alfabetica de nome]

      serie     preco  nome
       8776    215.88  teste5
       8916    115.82  teste6
       9251    301.55  teste:
       7215    394.88  testeN
       2055    398.49  testeU
       1858    407.60  teste\
       6158    122.82  teste_


==> Em ordem crescente de PRECO

        7 Elementos na lista
        [Ordem: crescente de preco]

      serie     preco  nome
       8916    115.82  teste6
       6158    122.82  teste_
       8776    215.88  teste5
       9251    301.55  teste:
       7215    394.88  testeN
       2055    398.49  testeU
       1858    407.60  teste\

 

E mesmo que desse errado, escrevendo assim é muito mais fácil de testar e corrigir...

 

 

  • 3 meses depois...
  • Membro VIP
Postado
Em 15/12/2020 às 14:36, arfneto disse:

Para usar o "algoritmo" de insertion sort e criar uma lista por ordem crescente de número de série, inserindo sempre no início

  • Você escolhe o maior, 4 e põe na nova lista
  • Você escolhe o maior restante, 3, e põe na lista
  • E continua até o fim da entrada, que você sabe que tem L->tamanho elementos.

 

@arfneto, seria Selection Sort, não?

 

Do que eu entendi... imaginemos ordenar um baralho.


No Insert Sort, eu vou pegando qualquer carta e vou inserindo na posição correta. O foco é a inserção; (Vou criando um vetor ordenado inserindo um dado novo na posição que o vetor continue ordenado. O que é mais natural no dia a dia);

 

No Select Sort, eu vou selecionar uma carta e vou posicionando em sequência. O foco é a seleção. (Escolho o maior (ou menor) dado e insiro no fim (ou no início) do vetor.)

 

Correto?

Postado
31 minutos atrás, Simon Viegas disse:

@arfneto, seria Selection Sort, não?

 

Do que eu entendi... imaginemos ordenar um baralho...

 

Pois é. Essa é uma analogia perfeita.

 

O sort é por inserção nesse caso. Não há sequer a possibilidade de seleção, já que se trata de online sort: os dados são vistos um a um.

 

Em geral esses algoritmos são considerados in-place, ordenando uma sequência que já existe. No caso desse exemplo aqui, e em muitos casos de sistemas dinâmicos --- quase todos --- em que os dados vão chegando, o insertion sort é o algortimo usado e nem deveria ter esse nome, porque os dados vão chegando e vão sendo colocados no lugar, nada mais. A sequência é mantida ordenada.

 

Entendo sua ideia sobre o foco. Uma maneira de pensar seria a seguinte: o sort por seleção atua na entrada e o sort por inserção atua na saída.

 

Usando o exemplo do baralho:

  • no Insertion Sort você escolhe a menor carta da entrada --- dentre todas --- e coloca na primeira posição. Depois continua fazendo isso até acabar a entrada.
  • no Insertion Sort você pega uma carta e põe no lugar certo. Depois pega outra.

No sort por seleção você precisa virar as cartas TODAS sobre a mesa antes de começar

 

No sort por inserção você pode usar o maço empilhado e ir virando uma a uma. Após ver oito cartas terá oito cartas em ordem ao lado.

 

Insertion Sort, Selection Sort e a Wikipedia

 

Veja isso:

 

Em português, sobre insertion sort:
 

Apesar de ser menos eficiente do que algoritmos como Merge Sort e Quick Sort (de ordem O(nlog(n))), o Insertion Sort possui algumas características consideráveis:

É de simples implementação, leitura e manutenção;
In-place: Apenas requer uma quantidade constante de O(1) espaço de memória adicional;
Estável: Não muda a ordem relativa de elementos com valores iguais;
Útil para pequenas entradas;
Muitas trocas, e menos comparações;
Melhor caso: O(n), quando a matriz está ordenado;
Médio caso: O(n²/4), quando a matriz tem valores aleatórios sem ordem de classificação (crescente ou decrescente);
Pior caso: O(n²), quando a matriz está em ordem inversa, daquela que deseja ordenar.

 

Em inglês, sobre o insertion sort:

 

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages:

Simple implementation: Jon Bentley shows a three-line C version, and a five-line optimized version[1]
Efficient for (quite) small data sets, much like other quadratic sorting algorithms
More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort
Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(kn) when each element in the input is no more than k places away from its sorted position
Stable; i.e., does not change the relative order of elements with equal keys
In-place; i.e., only requires a constant amount O(1) of additional memory space
Online; i.e., can sort a list as it receives it
When people manually sort cards in a bridge hand, most use a method that is similar to insertion sort.[2]

 


Note que o texto em português é fraquinho e desconsiderou o que eu expliquei acima...

 

 

  • Curtir 1
Postado
1 hora atrás, arfneto disse:

Online; i.e., can sort a list as it receives it When people manually sort cards in a bridge hand, most use a method that is similar to insertion sort.[2]

 

Para ser justo, @Simon Viegaso texto em inglês também não é assim certinho. O autor teve o cuidado de citar o que é talvez o mais importante em sort para  sistemas dinâmicos, na prática: insertion sort classifica os dados enquanto eles chegam, e como eu disse nem devia ser visto como um algoritmo, afinal se chega alguém na fila entra na ordem, se vira uma carta do baralho para classificar não tem muito sentido não colocar já na ordem se é o objetivo... E o autor do texto em português aparentemente desprezou isso.

 

No entanto quando as pessoas classificam "cards in a bridge hand" raramente usam um método similar ao insertion sort. Na verdade provavelmente usam algo bem similar ao selection sort, contrariando o que o autor disse, e colocando as cartas em ordem VENDO as cartas todas na mão e selecionando as posições depois de ver todas. A diferença e no final vai acabar em algo híbrido a partir da configuração das cartas na mão. Dificilmente uma pessoa, mesmo treinada em algoritmos, vai deixar de considerar algum aspecto da "mão" e usar esse conhecimento para por em ordem, e aí já terá ido na direção do selection sort...

 

 

Crie uma conta ou entre para comentar

Você precisa ser um usuário para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora

Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas comunidades sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×
×
  • Criar novo...

LANÇAMENTO!

eletronica2025-popup.jpg


CLIQUE AQUI E BAIXE AGORA MESMO!