Growing Order in a list chained in c

Question

Growing Order in a list chained in c

Navigation

#1 by (1 votes)

0

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

typedef struct LISTA{

int dado;
struct LISTA *prox; 




}lista;

lista *insere(lista *p, int valor){

lista *novo;
novo=(lista*)malloc(sizeof(lista));
novo->dado = valor;
novo->prox = p;
return novo;

 }


void imprime(lista *p){
lista *novo;
for(novo = p; novo!= NULL; novo=novo->prox){
    printf("%d",novo->dado);

}


 }
 lista *ordemCrescente(lista *p){
lista *aux = NULL;
lista *novo = p;


int *recebe;
int x=0;
int menor=0;
while(novo != NULL){
    if(novo->dado < menor){
        aux = novo->prox;
         novo = novo->dado;
         novo->dado = aux; 
    return p;               
    }       

    novo= novo->prox;
}

     }






     main(){

  lista *l,i;
  lista *primeiro, *ultimo;
l = NULL;
l = insere(l, 20);
l = insere(l, 30);
l = insere(l, 40);
l = insere(l, 50);
l = insere(l, 60);


imprime(l);
printf("\n");
l = ordemCrescente(l);
imprime(teste);
  }

c

asked by anonymous 30.08.2018 / 03:32

1 answer

How to do version control with GitLab? Read / Search information inside a Json with PHP

score 1 · Answer 1

First I'll start with the simplest problems.

A space was missing after %d in function imprime .
Avoid using l or O as variable names, as it is very easy to confuse this with the numbers 1 and 0 .
Learn to properly indentify your code. It makes your life a lot easier.

Now we go to the hardest. Note this:

        aux = novo->prox;
        novo = novo->dado;
        novo->dado = aux;

novo is a pointer. When doing novo->dado , you will get an integer and assign it to a pointer (your compiler should be giving you a warning because of this). As a result, novo will become an invalid pointer. When doing novo->dado = aux; , the result is that you will try to access the invalid address and put something there. The result will be a segmentation failure.

The correct way to swap novo and novo->prox would look like this:

        int aux = novo->dado;
        novo->dado = novo->prox->dado;
        novo->prox->dado = aux;

Despite this, the whole organization procedure is totally wrong. The return within it would cause something to be returned in the first "divestment" of items to be made, not after all have been made. Even if there is no return , while cycles through each element of the list only once ( O (n) ), so it is impossible for such an approach to sort the list that the minimum possible complexity is O (n log n) . To make matters worse, any approach based on sweeping the list and swapping neighboring elements is bound to have minimal performance O .

As such, there is nothing in your ordemCrescente function that is usable for a good solution. It would have to be redone from scratch.

I suggest studying the existing sort algorithms to understand how they work and then choose one of them to implement. Among the ones you can try to implement with linked lists (use two% s of each other to do this), are the Bubble sort , Selection sort and the Insertion sort . All of them will have complexity O (n²) and all of them have the strategy to swap neighboring elements several times until the list is sorted.

If you want to go further and look for more efficient sorting algorithms but probably can not be implemented with linked lists (at least not efficiently), you can look at the Shell sort and the Quick sort , which although are O (n²) in the worst case, are O (n log n) in the middle case. Or look at Heapsort and Merge sort that have O (n log n) complexity in all cases.

As a bonus, there is also Bogosort which is one of the most inefficient algorithms ever invented. I talk about it here .