sábado, 11 de diciembre de 2010

Lista enlazada simple en C/C++

Ahora, por los exámenes finales, no tengo tanto tiempo para escribir como quisiera :( Ya habrá más tiempo en un par de semanas :)

Sin embargo quiero compartir con ustedes un programa que hice, hace ya bastante tiempo, a modo de ejemplo para unos amigos. Se trata de una implementación de una lista enlazada simple en C/C++ y sus operaciones básicas tales como recorrer, insertar, eliminar y buscar. El código está comentado para mejor comprensión ;)

#include <iostream>

using namespace std;

struct nodo {
 int data;
 nodo *sgte;
};

void recorrer(nodo *cab);
void insertarFinal(nodo **cab, int data);
void insertarInicio(nodo **pcab, int data);
void insertarEnN(nodo **pcab, int data, int n);
int contarNodos(nodo *cab);
void eliminar(nodo **pcab, nodo *n);
nodo *buscar(nodo *cab, int data);

int main() {
 nodo *lista = NULL;
 int op = 0;
 int aux, aux2;
 do{
  do{   
   cout<<"..::LISTA ENLAZADA SIMPLE::.."<<endl;
   cout<<"[1] recorrer."<<endl;
   cout<<"[2] insertarFinal"<<endl;
   cout<<"[3] insertarInicio"<<endl;
   cout<<"[4] insertarEnN"<<endl;
   cout<<"[5] eliminar"<<endl;
   cout<<"[6] buscar"<<endl;
   cout<<"[7] salir"<<endl;
   cout<<endl;
   cout<<"OPCION: ";
   cin>>op;
  }while(op<1 || op>7);
  switch(op){
   case 1:
    recorrer(lista);
    break;
   case 2:
    cout<<"Ingrese un valor: ";
    cin>>aux;
    insertarFinal(&lista, aux);
    break;
   case 3:
    cout<<"Ingrese un valor: ";
    cin>>aux;
    insertarInicio(&lista, aux);
    break;
   case 4:
    cout<<"Ingrese un valor: ";
    cin>>aux;
    cout<<"Ingrese la pocicion: ";
    cin>>aux2;
    insertarEnN(&lista, aux, aux2);
    break;
   case 5:
    cout<<"Ingrese un valor: ";
    cin>>aux;
    eliminar(&lista, buscar(lista, aux));
    break;
   case 6:
    cout<<"Ingrese un valor: ";
    cin>>aux;
    cout<<"El nodo esta en la direccion: "<<buscar(lista, aux)<<endl;
    break;                
  }
 }while(op!=7);
 return 0;
}

//Función para recorrer una lista y mostrar la data.
void recorrer(nodo *cab){ 
 //verifica si la lista esta vacía
 if(cab == NULL){
  //si esta vacía muestra este mensaje
  cout<<"La lista esta vacia."<<endl;
 } 
 else{ 
  //si no esta vacía declara un puntero p al primer elemento de la lista 
  nodo *p = cab;
  do{ 
   //muestra la data del nodo referido por p
   cout<<"Elemento: "<<p->data<<endl;
   //asigna a p la dirección de nodo siguiente o NULL si no lo hay
   p = p->sgte;
  //repite el proceso mientras p sea diferente de NULL
  }while(p != NULL);
  cout<<"Fin del recorrido."<<endl; 
 } 
}



//Función que inserta un nodo nuevo al final de la lista
void insertarFinal(nodo **pcab, int data){

 //crea un nuevo nodo dinámicamente e inicia sus campos
 nodo *nuevo = new nodo;

 nuevo->data = data;

 nuevo->sgte = NULL;

 
 //valida si la lista esta vacia (pcab apunta a la cabecera osea pcab==&cab)
 if(*pcab == NULL){
  //modifica la cabecera para que apunte al nuevo nodo

  *pcab = nuevo;

 }

 else{

  //declara un puntero p que apunta al primer nodo (p==cab)
  nodo *p = *pcab;

  //avanza p hasta que llega al ultimo nodo (el que tiene NULL en sgte)
  while(p->sgte != NULL){

   p = p->sgte;

  }

  //asigna la dirección del nuevo nodo al campo sgte del ultimo nodo
  p->sgte = nuevo;

 }

}

//Funcion que inserta un nodo nuevo al inicio de la lista
void insertarInicio(nodo **pcab, int data){

 //crea un nodo nuevo
 nodo *nuevo = new nodo;

 //inicia el campo data del nuevo nodo con la data recibida por parámetro
 nuevo->data = data;

 //asigna al campo sgte del nuevo nodo el valor de la cabecera (*pcab==cab)
 //si la lista esta vacia (cab==NULL) sgte sera NULL
 //si la lista no esta vacia sgte apuntara al primer elemento
 nuevo->sgte = *pcab;

 //modifica la cabecera para que apunte al nuevo nodo
 //el nuevo nodo sera ahora el primero
 *pcab = nuevo;

}

//Función que inserta un nodo nuevo en la posición enésima
void insertarEnN(nodo **pcab, int data, int n){

 //contamos el numero de nodos de la lista
 int nNodos = contarNodos(*pcab);

 //validamos que el índice n este en un rango valido
 if(n > nNodos || n < 0){

  //si no esta, mostramos un mensaje de error
  cout<<"Posicion no valida. Hay "<<nNodos<<" nodos en la lista"<<endl;

 }

 //si n es 0 (primera posición) llamamos a insertarInicio() 
 else if(n == 0){

  insertarInicio(pcab, data);

 }

 //si n es igual al numero de nodos (ultima posición) llamamos a insertarFinal()
 else if(n == nNodos){

  insertarFinal(pcab, data);

 }
 //en este caso n debe estar en la zona intermedia de la lista

 else{

  //declaramos un puntero p al primer elemento de la lista
  nodo *p = *pcab;
  //avanzamos p hasta la posición n-1
  for(int i=0; i<n-1; i++)

   p = p->sgte;

  //creamos el nuevo nodo e iniciamos su data
  nodo *nuevo = new nodo;

  nuevo->data = data;

  //el campo sgte del nuevo elemento apuntara al nodo siguiente de p
  nuevo->sgte = p->sgte;

  //el campo sgte de p apuntara al nuevo nodo
  p->sgte = nuevo;

 }

}

int contarNodos(nodo *cab){
 int cont = 0;
 while(cab!=NULL){
  cab = cab->sgte;
  cont++;
 }
 return cont;
}

//Función que elimina un nodo usando como criterio de busqueda la direccion del nodo
void eliminar(nodo **pcab, nodo *n){
 //valida si la lista esta vacia
 if(*pcab == NULL){
  cout<<"La lista esta vacia."<<endl;
 }
 else{
  //valida si el nodo a eliminar existe
  if(n != NULL){
   //valida si el nodo a eliminar es el primero
   if(n == *pcab){
    //hace que la cabecera apunte al segundo elemento
    *pcab = (*pcab)->sgte;
   }
   else{
    //declara un puntero p al primer elemento de la lista
    nodo *p = *pcab;
    //hace que p apunte al nodo anterior al que se va a eliminar
    while(p->sgte!=NULL && p->sgte!=n){
     p = p->sgte;
    }
    //enlaza al nodo anterior con el siguiente
    p->sgte = n->sgte;
   }
   //libera el espacio de memoria del nodo eliminado
   delete n;
   cout<<"El elemento se ha eliminado correctamente."<<endl;
  }
  else{
   cout<<"No se encontro el elemento."<<endl;
  }
 }
}

//Función que busca un nodo y devuelve una referencia al nodo. Si no lo encuentra devuelve NULL.
nodo *buscar(nodo *cab, int data){
 //valida si la lista esta vacia
 if(cab == NULL){
  cout<<"La lista esta vacia."<<endl;
 }
 else{
  //declara un puntero p al primer elemento de la lista
  nodo *p = cab;
  do{
   //valida si la data del nodo es la data buscada
   if(p->data == data){
    //devuelve la referencia al nodo y termina la función
    return p;
   }
   else{
    //p apunta al siguiente nodo
    p = p->sgte;
   }
  //se repite mientras no se llegue al final de la lista
  }while(p!=NULL);
 }
 //si termina la lista y no encontro el nodo buscado retorna NULL
 return NULL;
}

Saludos.

Actualización:

Pueden ver una explicación mas detallada de cada operación en:

http://alguienenlafisi.blogspot.com/2010/12/listas-enlazadas-simples.html

28 comentarios:

  1. gracias esta excelente lo necesitaba muchisimas gracias deberdad: estaba escuuchando esto cuando encontre tu codigo fuente que esta de lujo, http://www.youtube.com/watch?v=4rSDK55uDhs&feature=related enverdad gracias, realmente te lo agradesco, que estes bien.

    ResponderEliminar
  2. De nada ;) que bueno que ese pedazo de codigo sea util

    Un saludo

    ResponderEliminar
  3. Muy buen codigo, gracias por la explicacion...
    solo deseo agregar un comentario mas, y es que en el metodo eliminar me parece que hace falta liberar la memoria ya que C no posee recolector de basura, entonces falta hacerle un free al nodo que estas elimando....

    ResponderEliminar
  4. Hola Andres, es muy cierto lo que dices... sin embargo la función eliminar si libera la memoria, para ello emplea la orden "delete" y un puntero al espacio de memoria a liberar.

    Las lineas son estas:

    //libera el espacio de memoria del nodo eliminado
    delete n;
    cout<<"El elemento se ha eliminado correctamente."<<endl;

    Saludos y gracias por el aporte :)

    ResponderEliminar
  5. No entiendo la declaración de uno de los argumentos que aparece en varios de los procedimientos : nodo **pcab. Me podrías explicar que diferencia tiene esta declaración con : nodo *pcab ? Gracias de Antemano.

    ResponderEliminar
  6. Hola, bueno a ver si me dejo entender xD

    "nodo **pcab" declara un puntero a puntero mientras "nodo *cab" declara un puntero a nodo.

    Si revisas la función main, el nodo cabecera de la lista es referenciado por un puntero a nodo (nodo *lista). En determinadas operaciones es necesario que el puntero al nodo cabecera cambie su valor. Por ejemplo al eliminar el primer elemento de la lista.

    Entonces surge la necesidad de modificar dentro de una función el valor de una variable declarada en otro ambito ¿Como se hace esto normalmente? Pasando a la funcion un puntero a la variable, es decir, pasando la variable por referencia. El único detalle es que en este caso la variable es un puntero ¿Como paso un puntero por referencia? Usando un puntero a puntero.

    Entonces la razon de esa declaración es para permitir a la funcion modificar el valor del puntero al nodo cabecera puesto que dicho puntero esta declarado en otro ambito (en el main).

    Un saludo.

    ResponderEliminar
  7. Oye esta excelente este programa, pero como podría yo hacer que en vez d pedir un valor, pida un nombre ?????? Xfa reponde.

    ResponderEliminar
  8. Solo debes cambiar tipo del campo "data" del nodo por una cadena de caracteres (char data[100]) y usar funciones de manejo de cadenas para las operaciones. Por ejemplo strcmp() para comparar, strcpy para copiar, etc.

    Para emplear esas funciones deberas incluir string.h (#include )

    Saludos.

    ResponderEliminar
  9. Te pasaste :D me has ayudado un monton se te agradece ^_^

    ResponderEliminar
  10. Una consulta ! y si por ejemplo tengo un procedimiento definido de esta manera : void AlgunProcedimient(nodo*&a) ; Lo he visto en unos ejercicios y no sé exactamente a qué se refiere. Gracias.

    ResponderEliminar
  11. Hola Anonimo...

    El operador "&" en el contexto de los parámetros de una función, sirve para indicar que se esta pasando un parámetro "por referencia" de forma implícita. Por ejemplo:

    ---
    #include <stdio.h>

    void modificar( int &a )
    {
    a = 20; // modificas a
    }

    int main()
    {
    int a = 10; //valor inicial
    printf("a = %d\n", a); // a antes
    modificar( a );
    printf("a = %d\n", a); // a despues
    return 0;
    }
    ---

    Si lo ejecutas verás como el valor de "a" cambia de 10 a 20 sin la necesidad de pasar un puntero a "a" de forma explicita a la función "modificar".

    Lo mismo sucede si pones *&variable, solo que en este caso estas pasando un puntero por referencia de forma implícita. Si modificaras la dirección a la que apunta el puntero dentro de la función, su valor se modificara también en el main.

    Yo prefiero pasar los punteros de forma explicita y aunque algunos dirán que tanto ***puntero puede confundir, a mi me parece más "comprensible".

    Un saludo.

    ResponderEliminar
  12. muchas gracias me salvastes de ke reprobara mi materia...
    muchas pero muchas gracias

    ResponderEliminar
  13. BRO UNA CONSULTA USANDO ESE MISMO CODIGO COMO LE HACES PARA MODIFICAR ES DECIR MEDIANTE LA POSICION DE UN NUMERO REEMPLAZARLO POR OTR??SI ME PASARAS EL CODIGO T LO AGRADECERIA UN MONTON

    ResponderEliminar
  14. gracias por el codigo y la explicacion me sirvio de mucho

    ResponderEliminar
  15. Buenas como vamos
    exelente su explicacion una pregunta como seria el codigo para realizar una operacion por ejemplo el factorial de un numero o el fibonaci operaciones por este estilo

    gracias de antemano

    ResponderEliminar
  16. Hola juancupa, no entendí que tiene que ver eso con las listas enlazadas pero ahí te dejo un par de links...

    http://codigoc.org/tag/fibonacci

    http://codigoc.org/405-factorial-de-forma-sencilla-en-c

    Saludos.

    ResponderEliminar
  17. Gracias por el codigo me salvo de reprobar

    ResponderEliminar
  18. holaa oye tengo una duda mi maestra me pidio un programa pero con clases lista y pues no se si se modifique tooodo si solo cambio el STRUCT por CLASS
    esa es mi duda y la otra tendras ejemplos de DELETE para eliminar datos de una clase lista?? graciasss!!

    ResponderEliminar
  19. Hola vero

    Lo structs se pueden parecer mucho a las clases, salvo porque estas ultimas tienen métodos (funciones), sin embargo en el fondo son muy diferentes. El hecho de emplear clases sugiere cambiar el paradigma del programa. Ahora es estructurado y tienes que hacerlo orientado a objetos. En este caso debes tener por lo menos una clase Nodo y otra clase Lista.

    Por ejemplo la clase Nodo sería algo así:

    class Nodo {
    private:
    Nodo *sgte;
    public:
    Nodo *getSiguiente() { return sgte; }
    Nodo *setSiguiente(Nodo *nodo) { sgte = nodo; }
    }

    Y la clase Lista, algo así:

    class Lista {
    private:
    Nodo *cab;

    public:
    int contarNodos() { ... }
    void insertarInicio(int data) { ... }
    // y demas funciones

    }

    En realidad los "algoritmos" no varian, sino que tienes que reestructurar el código para orientarlo a objetos.

    Un saludo.

    ResponderEliminar
  20. Con respecto a delete, esta instrucción recibe como parámetro un puntero al espacio de memoria que quieres liberar. Por ejemplo:

    Nodo *nodo = new Nodo;

    Instanciamos un objeto de la clase Nodo. El puntero "nodo" almacena la dirección de memoria reservada para el objeto.

    delete nodo;

    Liberamos el espacio de memoria reservada para el objeto.

    Un saludo.

    ResponderEliminar
  21. me salvaste man muchisimas gracias :>

    ResponderEliminar
  22. Graciaaaaaaaas! tenia como 5 horas resolviendo mi codigo hasta que decidí tomar uno prestado. ^^ Gracias.

    ResponderEliminar
  23. Hola! y para borrar el primer y el último nodo? cómo se hace?

    ResponderEliminar
    Respuestas
    1. Es facil, tomando como base la funcion eliminar() del codigo propuesto y un puntero *lista que apunta al primer elemento de la lista:

      Eliminar el primer elemento:

      eliminar(&lista, lista);

      Eliminar el último elemento:

      //primero recorremos la lista hasta el ultimo elemento
      nodo *p = lista;
      while( p != NULL && p->sgte != NULL) {
      p = p->sgte;
      }
      // p queda apuntando al ultimo nodo
      eliminar(&lista, p);

      Un saludo.

      Eliminar
  24. hola quiero ejecutar tu codigo me sale este error por que sera noo
    [Linker Fatal Error] Fatal: Could not open C:\Program Files (x86)\Borland\CBuilder5\Bin\Project1.exe (error code 5)

    ResponderEliminar