Sorting an unordered list does not work

Question

Sorting an unordered list does not work

Navigation

#1 by (1 votes)

1

The code works to the extent that I have sort a list already created using a new list, but I can not identify the error. It was when I created the Sort and AddOrdenado functions that started to give error.

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

typedef struct Elemento{
  int valor;
  struct Elemento*prox;
}Elemento;

typedef struct Lista{
  Elemento*Inicio;
  Elemento*Fim;
}Lista;

Lista*CriandoLista(){
  Lista*lista=(Lista*)malloc(sizeof(Lista));
  lista->Inicio=NULL;
  lista->Fim=NULL;
  return lista;
}

Elemento*CriandoElemento(int n){
  Elemento*novo=(Elemento*)malloc(sizeof(Elemento));
  novo->prox=NULL;
  novo->valor=n;
  return novo;
}

void AddLista(Lista*lista,Elemento*novo){
  if(lista->Inicio==NULL){
      lista->Inicio=novo;
      lista->Fim=lista->Inicio;
  }else{
      lista->Fim->prox=novo;
      lista->Fim=novo;
  }
}

void Imprimir(Lista*lista){
  Elemento*aux=lista->Inicio;
  while(aux!=NULL){
      printf(" %d ",aux->valor);
      aux=aux->prox;
  }
}

void AddOrdenado(Lista*lista,Lista*nvlista){
  Lista*aux=lista;
  Lista*aux2=nvlista;
  if(nvlista->Inicio==NULL){
      nvlista->Inicio=lista->Inicio;
      nvlista->Fim=lista->Inicio;
      lista->Inicio=lista->Inicio->prox;
      nvlista->Inicio->prox=NULL;

  }else{
      if((nvlista->Inicio->valor)<(lista->Inicio->valor)){
          nvlista->Inicio=lista->Inicio;
          lista->Inicio=lista->Inicio->prox;
          nvlista->Inicio->prox=aux2->Inicio;
      }else if((nvlista->Fim->valor)>(lista->Inicio->valor)){
          aux2->Fim->prox=lista->Inicio;
          nvlista->Fim=aux2->Fim;
          lista->Inicio=lista->Inicio->prox;
          nvlista->Fim->prox=NULL;
      }else{
          while(aux2!=NULL){
              if((lista->Inicio->valor)>(aux2->Inicio->prox->valor)){
                  lista->Inicio->prox=aux2->Inicio->prox;
                  aux2->Inicio->prox=lista->Inicio;
                  lista->Inicio=aux->Inicio->prox;
              }
              aux2->Inicio=aux2->Inicio->prox;
          }
      }
  }
}
void Ordenar(Lista*lista){
  Lista*nvlista=CriandoLista();
  while(lista->Inicio!=NULL){
      AddOrdenado(lista,nvlista);
  }
  Imprimir(nvlista);
}

int main(){
  Lista*lista=CriandoLista();
  int n[]={5,10,9};
  for(int i=0;i!=sizeof(n)/sizeof(int);i++){
    AddLista(lista,CriandoElemento(n[i]));
  }
  Imprimir(lista);
  Ordenar(lista);
}

c lista-encadeada

asked by anonymous 12.06.2018 / 15:32

1 answer

Angular-cli ng generate library does not work How to get the Schema of a Model in a DbContext made in the Entity Framework Core

score 1 · Accepted Answer

There are several things you need to do to get the addition working.

Your Ordenar function does not even advance through the nodes:
```
Lista*nvlista=CriandoLista();
while(lista->Inicio!=NULL){
    AddOrdenado(lista,nvlista);
}
```
Notice that there is no x = x->prox; , so this is for all intents while infinite, which is actually the problem you see directly on the console, because it does not end.

But even in this function there is another problem that is more subtle and more complicated to solve. This is the change of ->prox of elements in the old list. If you are adding elements from the old list to the new list and changing the ->prox , the old list stops working because there are no longer any links you should have. You can easily resolve this problem by adding a copy of the node you are going to, so as not to invalidate the old list. Having said this everything can rewrite its function as follows:
```
void Ordenar(Lista *lista) {
    Lista *nvlista=CriandoLista();
    Elemento *no_atual = lista->Inicio; //elemento para navegar na lista
    while(no_atual != NULL) {
        Elemento *novo = CriandoElemento(no_atual->valor); //adicionar uma cópia
        AddOrdenado(nvlista, novo);
        no_atual = no_atual->prox; //avançar para o proximo, que faltava
    }
    Imprimir(nvlista);
}
```

No AddOrdenado has a much more complex than necessary logic and does not even contemplate all the particular cases that exist. I suggest another approach that navigates the nodes while they are smaller than the node to insert, and stop at the first larger node. The insertion should then be made on the previous node to the one that stopped. Of course you have to consider particular cases of empty list, or node greater / less than all.

Following this logic could do so:

void AddOrdenado(Lista *nvlista, Elemento *elemento) {
    if (nvlista->Inicio == NULL){ //se lista vazia
        nvlista->Inicio = nvlista->Fim = elemento;
        return;
    }

    Elemento *atual = nvlista->Inicio;
    Elemento *anterior = NULL; 
    while (atual != NULL && atual->valor < elemento->valor){ //navegar enquanto menor
        anterior = atual;
        atual = atual->prox;
    }

    if (atual == NULL){ //novo maior que todos
        nvlista->Fim->prox = elemento;
        nvlista->Fim = elemento;
    }
    else {
        if (anterior == NULL){ //novo menor que todos
            elemento->prox = nvlista->Inicio;
            nvlista->Inicio = elemento;
        }
        else {
            elemento->prox = anterior->prox;
            anterior->prox = elemento;
        }
    }
}

See the program with these changes working correctly

Just a little note about writing, avoid writing something like Lista*nvlista all together because it is harder to read, and you can even give an idea that it is a multiplication. Choose to separate with space as is default by typing Lista *nvlista .