Sort linked lists (LinkedList) in c?

Question

Sort linked lists (LinkedList) in c?

Navigation

#1 by (1 votes)

2

I'm doing a project in C, but I got stuck when I wanted to order the Nodes. I have methods to fill and eliminate the nodes, the problem comes when trying to order does not do anything, it leaves it as it is. When entering a user I assigned his name and his account. The other methods if they are correct, when entering users "first" remains pointing to the first node and last, to the last one entered.

typedef  struct nodo {
    char nombre[60];
    int cuenta;
    struct nodo *siguiente; 
} nodo;
nodo*primero=NULL;
nodo*ultimo=NULL;
int i=0;

void organiza(){
    nodo*actual=(nodo*)malloc(sizeof(nodo));
    nodo*aux=(nodo*)malloc(sizeof(nodo));
    nodo*pivote=(nodo*)malloc(sizeof(nodo));

    actual=primero;
    pivote = primero;

    if(primero!=NULL){
        while(actual!=NULL){
            aux=actual->siguiente;
            while(aux!=NULL){
                if(actual->cuenta > aux->cuenta){
                    pivote = aux;
                    aux = actual;
                    actual->cuenta = pivote;
                }
            }
            aux=aux->siguiente;
        }
        actual=actual->siguiente; 
    } else {
        printf("Vacia\n");
    }
}

I think the problem is within the second if. But I'm not sure what. I already did

if(actual->cuenta> aux->cuenta){
        pivote = aux->cuenta;
        aux->cuenta = actual->cuenta;
        actual->cuenta = pivote;
}

And if it works, but it does not work when I do it with nodo->nombres , even creating a pivot for the names. Which means that it only orders the accounts but the names remain the same.

c ordenamiento

asked by Ivan 27.03.2017 в 05:34

source

1 answer

Body mass index - C Error in method Include LinQ: Unable to load type 'System.Data.Entity.DbExtensions'

score 1 · Answer 1

The first thing: you do things not recommended :

nodo*actual=(nodo*)malloc(sizeof(nodo));
...
nodo*pivote=(nodo*)malloc(sizeof(nodo));

to, then, do

actual = primero;
pivote = primero;

That's an obvious memory leak ; you assign a block, but you can never free it ; if your program were running continuously for a long time, you would end up with running out of memory , although in reality you would not be using it.

As regards ordering by name : how do you compare them? the chains in C not can be compared as if they were a type; think that a string is just a pointer to a block of bytes , the last of which is a 0 .

To compare strings, you have to use the function

int strcmp( const char *str1, const char *str2 );

This function returns:

str1 < str2  -> -1
str1 == str2 ->  0
str1 > str2  ->  1

Well, now, a change in the point of view. Instead of placing items in the list, and sorting them at the end, we'll do it as we insert them . The complexity of the code, in doing so, decreases drastically :

void addToList( nodo *nuevo ) {
  // Caso trivial. Lista vacía.
  if( !primero ) {
    primero = nuevo;
    ultimo = nuevo;
    nuevo->siguiente = NULL;
  } else {
    nodo *idx = primero;

    while( idx->siguiente && ( strcmp( idx->nombre, nuevo->nombre ) < 1 ) )
      idx = idx->siguiente;

    // Al llegar aquí, idx 'apunta' al elemento tras el que tenemos que insertar.
    nuevo->siguiente = idx->siguiente;
    idx->siguiente = nuevo;
  }
}

I have not tested it , but, except for minimal changes, it should work.