Páginas

NIMADRES

Listas Enlazadas en C++ Orientado a Objetos


Una lista enlazada es una de las estructuras de datos fundamentales, y puede ser usada para implementar otras estructuras de datos. Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias, enlaces o punteros al nodo anterior o posterior. 
El principal beneficio de las listas enlazadas respecto a los vectores convencionales es que el orden de los elementos enlazados puede ser diferente al orden de almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de almacenamiento.
Una lista enlazada es un tipo de dato autoreferenciado porque contienen un puntero o enlace a otro dato del mismo tipo. Las listas enlazadas permiten inserciones y eliminación de nodos en cualquier punto de la lista en tiempo constante (suponiendo que dicho punto está previamente identificado o localizado), pero no permiten un acceso aleatorio. Existen diferentes tipos de listas enlazadas: Lista Enlazadas Simples, Listas Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares.

En este programa se utiliza memoria dinámica y una función add(), donde  busca el lugar de la inserción, ya sea automáticamente por el inicio, a la mitad o al final de la lista, misma que se puede utilizar las veces que sean necesarias. También tiene funciones en las que permite buscar algún dato anteriormente insertado, vaciar la lista e imprimir.

#ifndef __SLLIST_
#define __SLLIST_

typedef class snode{
    public:
        bool add(int);
        void printList();
        int leer(int);
        bool search(int);
        bool erase(int);
        bool clear();
        bool empty();
        int Menu(int);
        int data;
        class snode * next;
}node;
#endif
Este es el archivo de cabecera que se guarda con la extensión ".h" donde se declara la clase

#include "sllist.h"
#include <iostream>
#include <iomanip>

using namespace std;

node *list = NULL;

bool node::add(int x){
    if(list == NULL){//lista vacia
        list = new node;
        list -> data = x;
        list -> next = NULL;
        return true;
    }
    node *p = list;//lista no vacia
    node *q;
    //buscar lugar de la insercion
    while(p != NULL && p -> data < x){
         q = p;
         p = p -> next;
    }//insercion por el final de la lista
    if(p == NULL){
        node *aux = new node;
        aux -> data = x;
        aux -> next = NULL;
        q -> next = aux;
    }//insercion
    //el nuevo dato ya existente
    else{
        if(p -> data == x)
            return false;
        if(p == list){//agregacion por el inicio
            node *aux = new node;
            aux -> data = x;
            list = aux;
            aux -> next = p;
        }
        else{//gregacion a la mitad de la lista
            node *aux = new node;
            aux -> data = x;
            q -> next = aux;
            aux ->next = p;
        }
    }
    return true;
}

int node::leer(int dato){    
    cin>>dato;
    return dato;
}

void node::printList(){
    node *p = list;
    while (p != NULL){
        cout<<setw(4)<<p -> data;
        p = p ->next;
    }
    cout<<endl;
}

bool node::search(int x){
     node *p = list;
     while(p != NULL && p -> data <= x){
         if(p -> data == x)
             return true;
         else
             p = p -> next;
     }
     return false;
}    

bool node::erase(int x){//Mal
    node *p = list;
    node *q;
    while((p != NULL) && (p -> data <= x)){
        if(p -> data == x){
            if(p == list)
                list = p -> next;                
            else{
                q -> next = p -> next;
                delete p;
                return true;
            }
        }
        else{
            q = p;
            p = p -> next;
        }   
    }
    return false;   
}

bool node::clear(){
    node *q;
    while(list != NULL){
        q = list;
        list = list -> next;
        delete q;
    }
    list = NULL;
    return true;
}

bool node::empty(){
     return list == NULL; 
}
En este archivo se hacen los métodos para la inserción, búsqueda, eliminación y vaciado de la lista.
#include "sllist.h"
#include <cstdlib>
#include <iostream>

using namespace std;

int Menu(int opcion){
     cout<<"1)agregar\n";
     cout<<"2)buscar\n";
     cout<<"3)eliminar\n";
     cout<<"4)vaciar lista\n";
     cout<<"5)verificar si la lista esta vacia\n";
     cout<<"6)Imprimir Lista\n";
     cout<<"7)Salir\n"; 
     cout<<"\n\nOpcion: ";
     cin>>opcion;
     return opcion;
}

int main(){
    node n;
    int x;
    int opcion;
    do{
        opcion = Menu(opcion);
        switch(opcion){
            case 1:
                 cout<<"Ingresa el dato: ";
                 x = n.leer(x);
                 if(n.add(x)){       
                     cout<<"El dato fue insertado";
                     n.printList();
                 }
                 else
                     cout<<"el dato no fue insertado\n";
                 break;
            case 2:
                 x = n.leer(x);
                 if(n.search(x)){ 
                     cout<<"El dato fue encontrado";
                     n.printList();
                 }
                 else
                     cout<<"el dato no fue encontrado\n";
                 break;
            case 3:
                 x = n.leer(x);
                 if(n.erase(x)){
                     cout<<"El dato fue eliminado";
                     n.printList();
                 }
                 else
                     cout<<"el dato no fue encontrado\n";
                 break;
            case 4:
                 if(n.clear()){ 
                     cout<<"la lista esta vacia";
                     n.printList();
                 }
                 else
                     cout<<"la lista aun no esta vacia";
                 break;
            case 5:
                 if(n.empty()){ 
                     cout<<"la lista esta vacia";
                     n.printList();
                 }
                 else
                     cout<<"la lista no esta vacia";
                 break;
            case 6:
                 n.printList();
                 break;
            case 7:
                 n.clear();
                 return 0;
                 break;    
            default: 
                 cerr<<"Error";
                 break;
        }
        cin.get();
        cin.get();
        system("cls"); 
    }while(opcion != 7);    
    return EXIT_SUCCESS;
}
Al final el archivo Main donde se muestra un ejemplo del uso de esta lista.



5 comentarios:

  1. no me corre el ultimo programama tendre que ver las librerias

    ResponderEliminar
  2. que chafa estos codigos son copias de clases

    ResponderEliminar
  3. Si quiero guardar un objeto antes creado en lugar de un entero en el nodo como se hace? :S

    ResponderEliminar