C linguagem c ordenacao crescente

[Tatiane]

Boa tarde preciso implementar em linguagem C a função de ordenação crescente da lista e não estou conseguindo. Alguém poderia me auxiliar

 

#include <stdio.h>

#include <stdlib.h>

#include <locale.h>

 

typedef struct BLOCO{

int dado;

struct BLOCO *prox;

}BLOCO;

 

typedef struct LISTA{

BLOCO *start;

BLOCO *end;

}LISTA;

 

void startLISTA(LISTA *l){

l->start = NULL;

l->end = NULL;

}

 

void insereLista_cabeca(int dado, LISTA *l){

BLOCO *ptr_aux = (BLOCO*)malloc(sizeof(BLOCO));

 

if (ptr_aux == NULL){

printf("Memory Allocation Error");

exit(-1);

}

else{

ptr_aux->dado = dado;

ptr_aux->prox = NULL;

 

if(l->start == NULL){

l->start = ptr_aux;

l->end = ptr_aux;

}

else{

ptr_aux->prox = l->start;

l->start = ptr_aux;

}

}

}

 

void insereLista_cauda(int dado, LISTA *l){

BLOCO *ptr_aux = (BLOCO*)malloc(sizeof(BLOCO));

 

if (ptr_aux == NULL){

printf("Memory Allocation Error");

exit(-1);

}

else{

ptr_aux->dado = dado;

ptr_aux->prox = NULL;

 

if(l->start == NULL){

l->start = ptr_aux;

l->end = ptr_aux;

}

else{

l->end->prox = ptr_aux;

//ptr_aux->prox = NULL;

l->end = ptr_aux;

}

}

}

 

int removeLista_cabeca(LISTA *l){

BLOCO *ptr_aux = l->start;

int dado;

 

if(ptr_aux != NULL){

l->start = ptr_aux->prox;

ptr_aux->prox = NULL;

dado = ptr_aux->dado;

free(ptr_aux);

if(l->start == NULL){

l->end = NULL;

}

return dado;

}

else{

printf("LIST is Empty \n");

}

return dado;

}

 

int removeLista_cauda(LISTA *l){

BLOCO *ptr_aux_ant;

BLOCO *ptr_aux = l->start;

int dado;

 

if(ptr_aux != NULL){

while (ptr_aux->prox != NULL){

ptr_aux_ant = ptr_aux;

ptr_aux = ptr_aux->prox;

}

l->end = ptr_aux_ant;

ptr_aux_ant->prox = NULL;

//l->start = ptr_aux->prox;

//ptr_aux->prox = NULL;

dado = ptr_aux->dado;

free(ptr_aux);

if(l->start == NULL){

l->end = NULL;

}

return dado;

}

else{

printf("LIST is Empty \n");

}

return dado;

}

 

int removeLista_elemento(int dado, LISTA *l){

BLOCO *ptr_aux_ant = l->start;

BLOCO *ptr_aux = l->start;

if(ptr_aux != NULL){

while (ptr_aux->prox != NULL){

if (ptr_aux->dado == dado){

if (ptr_aux_ant == ptr_aux){

removeLista_cabeca(l);

}

else{

ptr_aux_ant->prox = ptr_aux->prox;

ptr_aux->prox = NULL;

return ptr_aux->dado;

free(ptr_aux);

}

}

ptr_aux_ant = ptr_aux;

ptr_aux = ptr_aux->prox;

}

if (ptr_aux->prox == NULL){

removeLista_cauda(l);

}

//l->end = ptr;

//ptr->prox = NULL;

//l->start = ptr_aux->prox;

//ptr_aux->prox = NULL;

//dado = ptr_aux->dado;

//free(ptr_aux);

if(l->start == NULL){

l->end = NULL;

}

return dado;

}

else{

printf("LIST is Empty \n");

}

return dado;

}

 

void printLISTA(LISTA *l){

BLOCO *ptr_print = l->start;

 

if(ptr_print != NULL){

while (ptr_print != NULL){

printf("%d ", ptr_print->dado);

ptr_print = ptr_print->prox;

}

}

else{

printf("LISTA is Empty");

return;

}

printf("\n");

}

 

int main(){

 

LISTA *li = (LISTA*) malloc(sizeof(LISTA));

if (li == NULL){

printf("Memory Allocation Error");

exit(-1);

}

else{

startLISTA(li);

 

insereLista_cabeca(1, li);

 

printLISTA(li);

 

insereLista_cabeca(12, li);

 

printLISTA(li);

 

insereLista_cabeca(15, li);

 

printLISTA(li);

 

insereLista_cauda(20, li);

 

printLISTA(li);

 

insereLista_cauda(25, li);

 

printLISTA(li);

 

removeLista_cabeca(li);

 

printLISTA(li);

 

removeLista_cabeca(li);

 

printLISTA(li);

 

//removeLista_cauda(li);

 

//printLISTA(li);

 

//removeLista_cabeca(li);

 

removeLista_elemento(20, li);

 

printLISTA(li);

 

removeLista_elemento(25, li);

 

printLISTA(li);
 

}

 

}

[RPGStreamer]

Alguém pediu especificamente pra você criar um algorítimo de ordenação pra uma Linked List? A ideia de uma Linked List é a facilidade de se inserir os itens já em ordem.

 

Vou olhando o código por enquanto, mas uma coisa que já noto é mais de um return statement sem que haja necessidade (quando possível, use apenas um return por função).

 

Edit: Vejo também a declaração de variáveis sem sua imediata inicialização. Não é boa ideia. Sempre inicialize uma variável em sua declaração.

 

Exemplo:

 

int dado = 0; //ou outro valor.

BLOCO* ptr_aux = NULL;

[Tatiane]

Isso, estou com dificuldade para desenvolver essa parte para colocar os números em ordem crescente.

Obrigada pela dica do return..

[RPGStreamer]

A Linked List geralmente expõe como interface apenas a função "inserir elemento", e o elemento é inserido já no lugar certo, em ordem. Ou seja, para inserir o elemento, você percorre a lista, quando acha um elemento  já na lista que seja maior do que o elemento que você está inserindo, você insere o elemento imediatamente antes deste.

 

Como tenho meu C puro meio enferrujado, vou resumir o código. Teste pra ver se funciona, estou sem acesso a um compilador no momento (retorna o indice em que o elemento foi inserido):

 

int inserir_elemento(LISTA* lista, int dado)
{
  BLOCO* novo_elemento = NULL;
  //TODO: alocacao
  
  //TODO: checa se a lista esta vazia, se estiver, insere o item na cabeça/cauda da lista
  
  int idx = 0;
  BLOCO* ptr_iterador = lista->head;
  BLOCO* ptr_trailing = ptr_iterador;//aponta pro elemento anterior.
  
  while(ptr_iterador && ptr_iterador->dado <= dado)
  {
    ptr_trailing = ptr_iterador;
    ptr_iterador = ptr_iterador->prox;
    ++idx;
  }
  
  ptr_trailing->prox = novo_elemento;
  //faltou no original a linha abaixo
  novo_elemento->prox = ptr_iterador;
  return idx;
}

 

[Tatiane]

25 minutos atrás, RPGStreamer disse:

head

Nesse caso aqui não seria "start" ao invés de "head"?

[RPGStreamer]

@Tatiane Sim, isso mesmo. Geralmente se usa head e tail pra cabeça e cauda da linked list, respectivamente, e eu acabei me confundindo. Veja também a linha que acrescentei, que incorpora o novo elemento à lista fazendo seu ponteiro prox apontar pro bloco com dado imediatamente maior que o dado dele. Faz tempo que não escrevo esse tipo de código manualmente, bibliotecas têm os containers prontos (em C++ e C#, são parte da linguagem). Cheque pra ver se não tem alguma falha aí.

[arfneto]

Se vai ordenar a lista in-place, ordenando a própria lista e não retornando outra ordenada, talvez seja melhor simplesmente modificar insere() e já inserir na ordem. Afinal se depois de classificar usar uma de suas outras funções de inserção vai zoar a classificação de todo modo e a única maneira de garantir que vai estar em ordem é classificar toda hora...

 

Sobre a classificação o simples é uma função de comparação entre dois nós. No seu caso o dado é um simples número.

 

É provavelmente melhor usar um ponteiro no nó e não o dado. Assim pode ter mais listas apontando para os mesmos dados, por exemplo.

 

Evite retornar void. Em geral é um desperdício. Muitas vezes um erro mesmo. USe parâmetros e retorne resultados. Por exemplo, criar lista deveria retornar o endereço de uma lista. 

 

    LISTA* li = (LISTA*)malloc(sizeof(LISTA));
    if (li == NULL)
    {
        printf("Memory Allocation Error");
        exit(-1);
    }
    else
    {
        startLISTA(li);

 

por exemplo estaria bem melhor como

 

    LISTA* li = startLISTA();