Ordenacion de lista de objetos

[elmago_rm]

Hola estaba buscando un metodo para ordenar una lista de objetos. Es decir tengo una lista de libros los quiero ordenar por fecha. He buscado por la web y he encontrado código de metodos como el de burbuja y el quickshort pero no soy capaz de adaptarlos a listas ya que sólo he encontrado codigo para ordenar arrays de numeros. Esta son las clases:

#include "libro.hh"

using namespace std;

class Clibro
{

private:
libro num;
Clibro *anterior;
Clibro *siguiente;

public:
Clibro();
...
~Clibro();

};


#include<iostream>
#include<string.h>

using namespace std;

enum genero { teatro,ensayo,novela };

class libro
{
private:
int codigo;
string titulo;
int anho;
int autor;
string editorial;
genero _Genero;
public:
libro();


...

~libro();
};

Gracias de antemano.

[alexg88]

¿Por qué no utilizas las listas que viene ya en C++ y tienen un método sort?

Si lo quieres hacer a mano inténtalo con un quicksort, que es fácil con las listas.

Ahora no tengo tiempo pero si más tarde te pongo un ejemplo.

[elmago_rm]

Pues sí, lo que quiero es hacerlo a mano. Pero no lo doy sacado. Si lo intentas te lo agradeceria. Pero de todas formas gracias por contestar tan rápido. Yo seguiré intentandolo.

[elmago_rm]

Supongo que te habras olvidado no?¿

[alexg88]

Lo siento no he tenido tiempo. A ver si en un momento luego lo miro.

[sam90]

Un metodo sencillo para hacer seria ir insertandolo en una nueva lista, pero que ese inser los coloque en orden.
Deberias hacer dos metodo, sacar_primero, insertarpororden

El sacar_primero saca el primer elemento de una lista.
insertarpororden iria comparando cada elemento de la lista con el elemento que quieres agregar. Si el objeto a insertar es mayor al de la lista lo comparo con el siguiente.

[elmago_rm]

Iniciado por sam90

Un metodo sencillo para hacer seria ir insertandolo en una nueva lista, pero que ese inser los coloque en orden.
Deberias hacer dos metodo, sacar_primero, insertarpororden

El sacar_primero saca el primer elemento de una lista.
insertarpororden iria comparando cada elemento de la lista con el elemento que quieres agregar. Si el objeto a insertar es mayor al de la lista lo comparo con el siguiente.

Gracias! intentaré por ese metodo, a ver si soy capaz XDD

[elmago_rm]

uffffff!!! siguo intentandolo de varias maneras y nadaaa! Me estoi volviendo loco. A ver si alguien me puede ayudar.

[sam90]

Empeza mostrando lo que estas tratando de hacer.

[elmago_rm]

Iniciado por sam90

Empeza mostrando lo que estas tratando de hacer.

intene hacerlo como dijist pero no lo acabo de entender. Hice este código, pero no lo ordena, sin embargo me parece correcto.

bool Listalibro::ordenaLibros(int cambio)
{
Clibro *nodo,*nodo2,*nodo3,*aux;
libro lib,libr;
rellenarLista(); // con esta funcion meto los libros en la pila
nodo=lista.inicio;
aux=nodo->obtenerSiguiente();
while(aux!=NULL){
lib=nodo->obtenerDato();
nodo2=nodo->obtenerSiguiente();
libr=nodo->obtenerDato();
nodo3=nodo2->obtenerSiguiente();
if(ComparaPorNumero(lib,libr)==0){
if(nodo==lista.inicio){
nodo->modificaSiguiente(nodo3);
nodo3->modificaAnterior(nodo);
lista.inicio=nodo2;
nodo->modificaAnterior(nodo2);
nodo2->modificaSiguiente(nodo);
nodo->modificaAnterior(inicio);
}
else if(nodo3==NULL){
aux=nodo->obtenerAnterior();
nodo2->modificaAnterior(aux);
aux->modificaSiguiente(nodo2);
nodo->modificaAnterior(nodo2);
nodo->modificaSiguiente(NULL);
}
else aux=nodo->obtenerAnterior();
cambio=1;
}
nodo=nodo->obtenerSiguiente();
aux=nodo->obtenerSiguiente();
if(cambio==1) ordenaLibros(0);
else{
escribirFichero(lista);//escrribe la pila en el fichero.
return 1;
}
}
}

[sam90]

Código C++:

#include <iostream>
#include <string>
enum genero { teatro,ensayo,novela };
using namespace std;
 
 
/*    CLASE LIBRO  */
class libro
{
public:
    int codigo;
    string titulo;
    int anho;
    int autor;
    string editorial;
    genero _Genero;
 
    libro(int c,string t, int ano, int a, string edi,genero g)
    {
        codigo = c;
        titulo = t;
        anho = ano;
        autor = a;
        editorial = edi;
        _Genero = g;
    }
    void printlibro()
    {
        cout<<"codigo: " << codigo << " Titulo: " << titulo << endl;
    }
};
 
/*    CLASE NODOLIBRO  */
class NodoLibro
{
public:
    libro * lib;
    NodoLibro * anterior;
    NodoLibro * siguiente;
    NodoLibro(libro * l)
    {
        lib = l;
        anterior = NULL;
        siguiente = NULL;
    }
    bool compare(const NodoLibro * l)
    {
        if (lib->codigo > l->lib->codigo)
            return true;
        return false;
    }
    
    void changeLibro(NodoLibro * l)
    {
        libro * temp = lib;
        lib = l->lib;
        l->lib =temp;
    }
};
 
/*    CLASE LISTA  */
 
class Lista
{
public:
    NodoLibro * primero;
    NodoLibro * ultimo;
    Lista()
    {
        primero = ultimo = NULL;
    }
    ~Lista()
    {
        NodoLibro * temp = primero, * temp2;
        while (temp != NULL) {
            temp2 = temp->siguiente;
            delete temp;
            temp = temp2;
        }
    }
    void Append(libro * l)
    {
        NodoLibro * n = new NodoLibro(l);
        if (ultimo  == NULL )
            primero = ultimo = n;
        else{
            n->siguiente = NULL;
            ultimo->siguiente = n;
            n->anterior = ultimo;
            ultimo = n;
        }
    } 
    libro * Remove ()
    {
        NodoLibro * n = ultimo;
        libro * l = ultimo->lib;
        if (ultimo == primero)
            ultimo = primero = NULL;
        else{
            ultimo = ultimo->anterior;
            ultimo->siguiente = NULL;
        }
        delete n;
        return l;
        
    }
    
    void printlista()
    {
        NodoLibro * temp = primero;
        while (temp != NULL){
            temp->lib->printlibro();
            temp = temp->siguiente;
        }
    }
    
    void OrdenarLista()
    {
        NodoLibro * n1,*n2;
        for (n1 = ultimo; n1 != primero ; n1 = n1->anterior)
            for (n2 = primero; n2 != n1 ; n2 = n2->siguiente)
            {
                if (n2->compare(n2->siguiente))
                    n2->changeLibro(n2->siguiente);
                    
            }
    }
} ;
 
int main ()
{
    libro * l1 = new libro(1,"mi mundo",2000,4,"edu",teatro);
    libro * l2 = new libro(3,"hello world",2000,4,"edu",teatro);
    libro * l3 = new libro(2,"a la madona",2000,4,"edu",teatro);
    Lista * c = new Lista();
    c->Append(l1);
    c->Append(l2);
    c->Append(l3);
 
    c->printlista();
    cout<<"----------------------------------------------------"<<endl;
    c->OrdenarLista();
    c->printlista();
    delete c;
    cout<<"chauuuu" << endl;
    return 0;
    
}
 

[alexg88]

Basándome en el código proporcionado por sam90 voy a poner un intento de ordenación mediante Quicksort.

Código C++:

/*    CLASE NODOLIBRO  */
class NodoLibro
{
public:
    libro * lib;
    NodoLibro * anterior;
    NodoLibro * siguiente;
    NodoLibro(libro * l)
    {
        lib = l;
        anterior = NULL;
        siguiente = NULL;
    }
    bool compare(const NodoLibro * l)
    {
        if (lib->codigo > l->lib->codigo)
            return true;
        return false;
    }
    
    void changeLibro(NodoLibro * l)
    {
        libro * temp = lib;
        lib = l->lib;
        l->lib =temp;
    }
};
 
/*    CLASE LISTA  */
 
class Lista
{
 
private:
    NodoLibro * primero;
    NodoLibro * ultimo;
    int distancia(NodoLibro *first, NodoLibro *last){
 
        int i=1;
 
        NodoLibro *ptr = first;
 
        while (ptr != last)
         {
          ptr = ptr->siguiente;
          i++;
         }
 
     return i;
 
    }
 
    void QuicksortAux(NodoLibro *first,NodoLibro *last){
 
     NodoLibro * n1,*n2;
     NodoLibro *pivote=first;
     int longitud = distancia(first,last);
     int i,j;
     if (longitud<=1)
      return;
 
     
     n1 = first;
     n2 = last;
    
         i=1;
     j=longitud;
 
    
     while (i<j){   
 
     while (!n1->compare(pivote) && i<j+1 && i<longitud){
         n1=n1->siguiente;
         i++;
     }
 
      while (n2->compare(pivote) && j>i-1 && j>1){
        n2 = n2->anterior;
        j--;
     }
 
     if (i<j)
      n1->changeLibro(n2);
     }
     
 
     pivote->changeLibro(n2);
    
     if (n2!=first)
      QuicksortAux(first,n2->anterior);
     if (n2!=last)
     QuicksortAux(n2->siguiente,last);
    
    }
 
public:
 
   
    Lista()
    {
        primero = ultimo = NULL;
    }
    ~Lista()
    {
        NodoLibro * temp = primero, * temp2;
        while (temp != NULL) {
            temp2 = temp->siguiente;
            delete temp;
            temp = temp2;
        }
    }
    
    void Append(libro * l)
    {
        NodoLibro * n = new NodoLibro(l);
        if (ultimo  == NULL )
            primero = ultimo = n;
        else{
            n->siguiente = NULL;
            ultimo->siguiente = n;
            n->anterior = ultimo;
            ultimo = n;
        }
    } 
    libro * Remove ()
    {
        NodoLibro * n = ultimo;
        libro * l = ultimo->lib;
        if (ultimo == primero)
            ultimo = primero = NULL;
        else{
            ultimo = ultimo->anterior;
            ultimo->siguiente = NULL;
        }
        delete n;
        return l;
        
    }
    
    void printlista()
    {
        NodoLibro * temp = primero;
        while (temp != NULL){
            temp->lib->printlibro();
            temp = temp->siguiente;
        }
    }
 
    
 
    
    
    void OrdenarLista()
    {
        NodoLibro * n1,*n2;
        for (n1 = ultimo; n1 != primero ; n1 = n1->anterior)
            for (n2 = primero; n2 != n1 ; n2 = n2->siguiente)
            {
                if (n2->compare(n2->siguiente))
                    n2->changeLibro(n2->siguiente);
                    
            }
    }
 
    void Quicksort(){
    if (primero!=ultimo)
     QuicksortAux(primero,ultimo);
    }
 
 
    
} ;
 

Puede mejorarse mucho, por ejemplo, utilizando otro tipo de ordenación cuando el tamaño de las sublistas sea menor de un número o utilizando una versión iterativa en vez de iterativa.

[sam90]

Muy buena data alexg88. Para seguir aprendiendo...