not succesfull sorting a linked list

This is a discussion on not succesfull sorting a linked list within the C++ Programming forums, part of the General Programming Boards category; hi. im learning know data structures, im trying to sort a linked list with the bubblesort method. but i have ...

  1. #1
    Registered User
    Join Date
    Mar 2004
    Posts
    113

    not succesfull sorting a linked list

    hi.
    im learning know data structures, im trying to sort a linked list with the bubblesort method. but i have 2 days trying to makit work but it dont works, if i exchange the data betwen the nodes i can sort the list, but i want to sort it exchanging and redirectioning the pointers,
    any idea how to do that?? or link where i can analize the code in c++?, please must be in c++ because i dont know c.

    the code should not be stl because im learnig from a book and i has not study that chapter yet.

    thanks in advance
    and please excuse my english

    btw. i understand the bubblesort and can sort an array without problen. but want to sort a linked lists with custom created data objects.
    Last edited by terracota; 08-27-2004 at 02:56 PM.

  2. #2
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Location
    Mt. Prospect, IL
    Posts
    2,572
    have you done anything? can you post some code?

    and http://www.google.com/search?hl=en&i...=Google+Search

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  3. #3
    Registered User
    Join Date
    Mar 2004
    Posts
    113
    sure heres the code exchanging data, but thats not what i want to do.

    the code is in spanish so i hope you can understand it

    Code:
    file for the node class:
    
    //definicion de la plantilla de clase Nodo
    #ifndef F_NODO_H
    #define F_NODO_H 
    
    template<class TIPONODO>
    class Lista;
    
    template<class TIPONODO>
    
    class Nodo{
    	friend class Lista<TIPONODO>;
        public:
    		Nodo(const TIPONODO &);
    		TIPONODO obtener_datos()const;
    	private:
    		TIPONODO datos;
    		Nodo<TIPONODO> *ptr_siguiente;
    
    };
    
    //definicion de funciones miembro
    //constructor
    template<class TIPONODO>
    Nodo<TIPONODO>::Nodo(const TIPONODO &info)
    	:datos(info),ptr_siguiente(0)
    {
    	//vacio
    }
    
    //devuelve el valor de datos
    template<class TIPONODO>
    TIPONODO Nodo<TIPONODO>::obtener_datos()const
    {
    	return datos;
    }
    
    #endif
    
    //////////////////////////////////////////////////////////////////////////////////
    file for list class:
    
    //definicion de la plantilla de clase Lista
    #ifndef F_LISTA_H
    #define F_LISTA_H
    
    #include "f_nodo.h"
    
    template<class TIPONODO>
    
    class Lista{
    	public:
    		Lista();
    		//~Lista();
    		void insertar_nodo(const TIPONODO &);
    		bool esta_vacia()const;
    		void imprimir()const;
    		void mezclar(const Lista<TIPONODO> &, 
    			const Lista<TIPONODO> &);
    		
    		void ordenar();
    		
    	private:
    		Nodo<TIPONODO> *ptr_inicio;
    		Nodo<TIPONODO> *ptr_ultimo;
            //funcion de utileria para ordenar listas
    		
    		//funcion de utileria para concatenar listas
    		void concatenar(const Lista<TIPONODO> &,
    						const Lista<TIPONODO> &);
    		//funcion de utileria para saber el tamanio de la lista
    		int tamanio_lista();
    };
    
    //definicion de funciones miembro
    
    //constructor
    template<class TIPONODO>
    Lista<TIPONODO>::Lista()
    	:ptr_inicio(0),ptr_ultimo(0)
    {
    	//vacio
    }
    
    //destructor
    //template<class TIPONODO>
    //Lista<TIPONODO>::~Lista()
    //{
    	//Nodo<TIPONODO> *ptr_actual = ptr_inicio;
    	//Nodo<TIPONODO> *ptr_temp;
    
    	//if(!esta_vacia()){
    		//cout << "\nDestruyendo nodos...\n";
    		//while(ptr_actual != 0){
    			//cout << ptr_actual->datos << ' ';
    			//ptr_temp = ptr_actual->ptr_siguiente;
    			//delete ptr_actual;
    			//ptr_actual = ptr_temp;
    			
    		//}
    		//cout << endl;
    	//}
    	
    //}
    
    
    //insertar nodo
    template<class TIPONODO>
    void Lista<TIPONODO>::insertar_nodo(const TIPONODO &valor)
    {
    	Nodo<TIPONODO> *ptr_nuevo = new Nodo<TIPONODO>(valor);
    	if(esta_vacia()){
    		ptr_inicio = ptr_ultimo = ptr_nuevo;
    		
    	}
    	else{
    		ptr_ultimo->ptr_siguiente = ptr_nuevo;
    		ptr_ultimo = ptr_nuevo;
    		
    	}
    }
    
    //verifica si esta vacia
    template<class TIPONODO>
    bool Lista<TIPONODO>::esta_vacia()const
    {
    	return ptr_inicio == 0;
    }
    
    //imprime lista
    template<class TIPONODO>
    void Lista<TIPONODO>::imprimir()const
    {
    	Nodo<TIPONODO> *ptr_actual = ptr_inicio;
    	cout << "Imprimiendo lista...\n";
    	
    	while(ptr_actual != 0){
    		cout << ptr_actual->datos << ' ';
    		ptr_actual = ptr_actual->ptr_siguiente;
    	}
    	cout << endl;
    }
    
    template<class TIPONODO>
    void Lista<TIPONODO>::concatenar(const Lista<TIPONODO> &lista1
    								 ,const Lista<TIPONODO> &lista2)
    {
    	//declara ptrActual que apunte al inicio de la primer lista
    	Nodo<TIPONODO> *ptr_actual = lista1.ptr_inicio;
    	
    	//for 2 veces porque son dos listas las que se concatenan
    	for(int i = 0;i < 2; i++){
    		//mientras no termine la primera
    		while(ptr_actual != 0){
    			Nodo<TIPONODO> *nuevo_ptr = new Nodo<TIPONODO>(ptr_actual->datos);
    			if(esta_vacia())
    				ptr_inicio = ptr_ultimo = nuevo_ptr;
    			else{
    				ptr_ultimo->ptr_siguiente = nuevo_ptr;
    				ptr_ultimo = nuevo_ptr;
    			}
    			ptr_actual = ptr_actual->ptr_siguiente;	 
    		}
    	    //cuando termina while porque actualPtr == 0o sea termina
    		//la primera lista, pone a ptrActual a que apunte a a la
    		//otra lista para concatenarlas
    		ptr_actual = lista2.ptr_inicio;
    	}
    }
    
    template<class TIPONODO>
    void Lista<TIPONODO>::mezclar(const Lista<TIPONODO> &primera,
    					  const Lista<TIPONODO> &segunda)
    {
    	concatenar(primera,segunda);
    	ordenar();
    }
    
    template<class TIPONODO>
    void Lista<TIPONODO>::ordenar()
    {
    Nodo<TIPONODO> *ptr_actual = ptr_inicio;
    Nodo<TIPONODO> *siguiente = ptr_actual->ptr_siguiente;	int temp = 0;
        
    //obtiene tamanio de lista
     int tamanio_lista = 1;
    while(ptr_actual != 0){
    tamanio_lista++ ;
    ptr_actual = ptr_actual->ptr_siguiente;
    }
          ptr_actual = ptr_inicio;
        
    //utilizo -2 en el ciclo ya que si no se hace asi se pasa
    //ya que debe llegar hasta el apuntador ptr_siguiente del
    //penultimo elemento o si no queda el apuntador indefinido 
    	for(int i = 0; i < tamanio_lista-2; i++){
    		for(int j = 0; j < tamanio_lista-2; j++)			if(ptr_actual->datos > siguiente->datos){
    		temp = siguiente->obtener_datos();
    		siguiente->datos = ptr_actual->datos;			ptr_actual->datos = temp;
    	}
    			
          ptr_actual = ptr_actual->ptr_siguiente				siguiente = siguiente->ptr_siguiente;
              	}
    	//pone de nuevo ptr_Actual en ptr_inicio		ptr_actual = ptr_inicio;
    	//pone siguiente a que apunte al segundo objeto
    	siguiente = ptr_actual->ptr_siguiente;
    	
    	}
    }
    
    //tamanio de la lista
    template<class TIPONODO>
    int Lista<TIPONODO>::tamanio_lista()
    {
    	int s_lista = 0;
        Nodo<TIPONODO> *ptr_actual; 
        ptr_actual = ptr_inicio;
    
    	while(ptr_actual != 0){
    		s_lista++ ;
            ptr_actual = ptr_actual->ptr_siguiente;
    	}
    	return s_lista;
    }
    
    
    #endif
    
    /////////////////////////////////////////////////////////////////////////////////
    main file:
    
    //EJERCICIO 17.7
    //autor: Alex Mejia
    //inicio de desarrollo: 24/08/04
    //ultima revision: 24/08/04
    ////////////////////////////////
    
    #include <iostream>
    using namespace std;
    
    #include "f_lista.h"
    
    #include<ctime>
    
    //genera la lista aleatoria
    void generar_lista(Lista<int> &);
    
    int main()
    {
    	//semilla random
    	srand(time(0));
    
    	Lista<int>list1;
        generar_lista(list1);
    	list1.imprimir();
    	
    	Lista<int>list2;
    	generar_lista(list2);
    	list2.imprimir();
    	
    	Lista<int>list3;
    	list3.mezclar(list1,list2);
    	list3.imprimir();
    	
    	
    	return 0;
    }
    
    void generar_lista(Lista<int> &lista)
    {
    	int n_aleatorio = 0;
    	int arreglo[5] = {11,2,3,4,5};
    
    	for(int i = 0; i < 5; i++){
    		n_aleatorio = 1 + rand() % 30;
    		lista.insertar_nodo(n_aleatorio);
    	}
    }
    
    //////////////////////////////////////////////////////////////////////////////////
    
    some translations to help you out:
    
    ordenar = sort
    tamanio = size(for list size)
    generar lista = generate list
    mezclar = join(join 2 lists in 1)
    imprimir = print(print list)
    sorry for the indentation but the browser messed it up

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >im trying to sort a linked list with the bubblesort method
    What possible reason under the sun could you have to sort a linked list with bubble sort? Insertion sort is the way to go for the simple stuff, then try mergesort. Both are easily implemented with linked lists. If you're really adventurous you could try sorting a list with quicksort, but that's for a later exercise.
    My best code is written with the delete key.

  5. #5
    Registered User
    Join Date
    Mar 2004
    Posts
    113
    Quote Originally Posted by Prelude
    >im trying to sort a linked list with the bubblesort method
    What possible reason under the sun could you have to sort a linked list with bubble sort? Insertion sort is the way to go for the simple stuff, then try mergesort. Both are easily implemented with linked lists. If you're really adventurous you could try sorting a list with quicksort, but that's for a later exercise.
    ok thanks

  6. #6
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Location
    Mt. Prospect, IL
    Posts
    2,572
    oops, forgot about this thread. But Prelude is right, I would choose (and have in the past) mergesort for sorting a linked list. You could search for the "skyline algorithm" using mergesort to give you some ideas.

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  7. #7
    Registered User Frobozz's Avatar
    Join Date
    Dec 2002
    Posts
    546
    Quote Originally Posted by terracota
    but i want to sort it exchanging and redirectioning the pointers
    Do what you would do if you were to move the data itself only apply that to the pointers. That is to say swap the targets they point at.

  8. #8
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712
    Inspired with this thread I tried to implement selection sort on linked list on simple example So far I manage to do this:

    Code:
    #include <iostream>
    using namespace std;
    struct Node
    {
    	int data;
    	Node* next;
    };
    
    class List
    {
    		Node *head;
    		void insert(Node*,int);
    public:
    	List();
    	~List();
    	void insert_head(int);
    	void remove_head();
    	void show();
    	void sort();
    	int len();
    };
    
    List::List():head(0){}
    List::~List(){//appropriate cleanup
    }
    void List::insert(Node* n,int data)
    {
    	Node* cur=new Node;
    	cur->data=data;
    	cur->next=n;
    	n=cur;
    }
    void List::insert_head(int data)
    {
    	if(!head)
    	{
    		head=new Node;
    		head->data=data;
    		head->next=0;
    		return;
    	}
    	Node* newNode=new Node;
    	newNode->data=data;
    	newNode->next=head;
    	head=newNode;
    }
    
    void List::show()
    {
    	Node* tmp=head;
    	while(tmp)
    	{
    		printf("%d ",tmp->data);
    		tmp=tmp->next;
    	}
    
    }
    
    int List::len()
    {
    	Node* tmp=head;
    	int i=0;
    	while(tmp)
    	{
    		i++;
    		tmp=tmp->next;
    	}
    	return i;
    }
    void List::sort()
    {
    	Node* min,*tmp,*cur,*tmpi;
    	int data,le;
    	le=len();
    	tmpi=head;
    while(tmpi->next) //this is not working properly
    {
    	min=tmp=tmpi;
    	while(tmp->next)
    	{
    		if(min->data > tmp->next->data)
    		{
    			min=tmp;
    		}
    		tmp=tmp->next;
    	}
    	data=min->next->data;
    	cur=min->next;
    	min->next=min->next->next;
    	delete cur;
    	insert(tmpi,data);
    	
    }
    tmpi=tmpi->next;
    }
    	
    
    int main()
    {
    	List lista;
    	lista.insert_head(2);
    	lista.insert_head(4);
    	lista.insert_head(8);
    	lista.insert_head(10);
    	lista.show();
    	lista.sort();
    	lista.show();
    }
    Idea is that in the first iteration I choose the smallest element and put it at the begining. In the next iteration I need to choos min element from the rest and so on...
    I tried to do this with tmpi but no success.
    If someone can point to me place whaere I'm making mistakes?
    Thanks!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  2. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  3. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 08:27 PM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 05:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21