sábado, 23 de enero de 2016

LISTAS EN C++

listas en c++




__________________________________________________________________

EJEMPLOS DE LISTAS                                                                                           

 LISTAS :

#include <iostream>
using namespace std;

class nodo {
   public:
    nodo(int v, nodo *sig = NULL)
    {
       valor = v;
       siguiente = sig;
    }

   private:
    int valor;
    nodo *siguiente;
       
   friend class lista;
};

typedef nodo *pnodo;

class lista {
   public:
    lista() { primero = actual = NULL; }
    ~lista();
   
    void Insertar(int v);
    void Borrar(int v);
    bool ListaVacia() { return primero == NULL; }
    void Mostrar();
    void Siguiente();
    void Primero();
    void Ultimo();
    bool Actual() { return actual != NULL; }
    int ValorActual() { return actual->valor; }
   
   private:
    pnodo primero;
    pnodo actual;
};

lista::~lista()
{
   pnodo aux;
  
   while(primero) {
      aux = primero;
      primero = primero->siguiente;
      delete aux;
   }
   actual = NULL;
}

void lista::Insertar(int v)
{
   pnodo anterior;

   // Si la lista está vacía
   if(ListaVacia() || primero->valor > v) {
      // Asignamos a lista un nievo nodo de valor v y
      // cuyo siguiente elemento es la lista actual                   
      primero = new nodo(v, primero);
   }
   else {
      // Buscar el nodo de valor menor a v
      anterior = primero;
      // Avanzamos hasta el último elemento o hasta que el siguiente tenga
      // un valor mayor que v
      while(anterior->siguiente && anterior->siguiente->valor <= v)
         anterior = anterior->siguiente;
      // Creamos un nuevo nodo después del nodo anterior, y cuyo siguiente
      // es el siguiente del anterior
      anterior->siguiente = new nodo(v, anterior->siguiente);
   }
}

void lista::Borrar(int v)
{
   pnodo anterior, nodo;
  
   nodo = primero;
   anterior = NULL;
   while(nodo && nodo->valor < v) {
      anterior = nodo;
      nodo = nodo->siguiente;
   }
   if(!nodo || nodo->valor != v) return;
   else { // Borrar el nodo
      if(!anterior) // Primer elemento
         primero = nodo->siguiente;
      else  // un elemento cualquiera
         anterior->siguiente = nodo->siguiente;
      delete nodo;
   }  
}

void lista::Mostrar()
{
   nodo *aux;
  
   aux = primero;
   while(aux) {
      cout << aux->valor << "-> ";
      aux = aux->siguiente;
   }
   cout << endl;
}

void lista::Siguiente()
{
   if(actual) actual = actual->siguiente;
}

void lista::Primero()
{
   actual = primero;
}

void lista::Ultimo()
{
   actual = primero; 
   if(!ListaVacia())
      while(actual->siguiente) Siguiente();
}

int main()
{
   lista Lista;
  
   Lista.Insertar(500);
   Lista.Insertar(1000);
   Lista.Insertar(1500);
   Lista.Insertar(2000);
   Lista.Insertar(2500);
   Lista.Insertar(-500);
   Lista.Insertar(-1000);
   Lista.Insertar(-1500);
   Lista.Insertar(-2000);
   Lista.Insertar(-2500);

   Lista.Mostrar();

   cout << "Lista de elementos:" << endl;
   Lista.Primero();
   while(Lista.Actual()) {
      cout << Lista.ValorActual() << endl;
      Lista.Siguiente();
   }
   Lista.Primero();
   cout << "Primero: " << Lista.ValorActual() << endl;
  
   Lista.Ultimo();
   cout << "Ultimo: " << Lista.ValorActual() << endl;
  
   Lista.Borrar(500);
   Lista.Borrar(1000);
   Lista.Borrar(1500);
   Lista.Borrar(2000);
   Lista.Borrar(2500);
   Lista.Borrar(-500);
   Lista.Borrar(-1000);
   Lista.Borrar(-1500);
   Lista.Borrar(-2000);
   Lista.Borrar(-2500);
  
   Lista.Mostrar();

   cin.get();
   return 0;
}
LISTAS DOBLEMENTE  ENLAZADA                                                                                  


#include <iostream>
using namespace std;

#define ASCENDENTE 1
#define DESCENDENTE 0

class nodo {
   public:
    nodo(int v, nodo *sig = NULL, nodo *ant = NULL) :
       valor(v), siguiente(sig), anterior(ant) {}

   private:
    int valor;
    nodo *siguiente;
    nodo *anterior;
       
   friend class lista;
};

typedef nodo *pnodo;

class lista {
   public:
    lista() : plista(NULL) {}
    ~lista();
   
    void Insertar(int v);
    void Borrar(int v);
    bool ListaVacia() { return plista == NULL; }
    void Mostrar(int);
    void Siguiente();
    void Anterior();
    void Primero();
    void Ultimo();
    bool Actual() { return plista != NULL; }
    int ValorActual() { return plista->valor; }
   
   private:
    pnodo plista;
};

lista::~lista()
{
   pnodo aux;
  
   Primero();
   while(plista) {
      aux = plista;
      plista = plista->siguiente;
      delete aux;
   }
}

void lista::Insertar(int v)
{
   pnodo nuevo;

   Primero();
   // Si la lista está vacía
   if(ListaVacia() || plista->valor > v) {
      // Asignamos a lista un nuevo nodo de valor v y
      // cuyo siguiente elemento es la lista actual                   
      nuevo = new nodo(v, plista);
      if(!plista) plista = nuevo;
      else plista->anterior = nuevo;
   }
   else {
      // Buscar el nodo de valor menor a v
      // Avanzamos hasta el último elemento o hasta que el siguiente tenga
      // un valor mayor que v
      while(plista->siguiente && plista->siguiente->valor <= v) Siguiente();
      // Creamos un nuevo nodo después del nodo actual
      nuevo = new nodo(v, plista->siguiente, plista);
      plista->siguiente = nuevo;
      if(nuevo->siguiente) nuevo->siguiente->anterior = nuevo;
   }
}

void lista::Borrar(int v)
{
   pnodo nodo;
  
   nodo = plista;
   while(nodo && nodo->valor < v) nodo = nodo->siguiente;
   while(nodo && nodo->valor > v) nodo = nodo->anterior;

   if(!nodo || nodo->valor != v) return;
   // Borrar el nodo
  
   if(nodo->anterior) // no es el primer elemento
      nodo->anterior->siguiente = nodo->siguiente;
   if(nodo->siguiente) // no el el último nodo
      nodo->siguiente->anterior = nodo->anterior;
   delete nodo;
}

void lista::Mostrar(int orden)
{
   pnodo nodo;
   if(orden == ASCENDENTE) {
      Primero();
      nodo = plista;
      while(nodo) {
         cout << nodo->valor << "-> ";
         nodo = nodo->siguiente;
      }
   }
   else {
      Ultimo();
      nodo = plista;
      while(nodo) {
         cout << nodo->valor << "-> ";
         nodo = nodo->anterior;
      }
   }
   cout << endl;
}

void lista::Siguiente()
{
   if(plista) plista = plista->siguiente;
}

void lista::Anterior()
{
   if(plista) plista = plista->anterior;
}

void lista::Primero()
{
   while(plista && plista->anterior) plista = plista->anterior;
}

void lista::Ultimo()
{
   while(plista && plista->siguiente) plista = plista->siguiente;
}

int main()
{
   lista Lista;
  
   Lista.Insertar(500);
   Lista.Insertar(1000);
   Lista.Insertar(1500);
   Lista.Insertar(2000);
   Lista.Insertar(2500);
   Lista.Insertar(-500);
   Lista.Insertar(-1000);
   Lista.Insertar(-1500);
   Lista.Insertar(-2000);
   Lista.Insertar(-2500);
   Lista.Mostrar(ASCENDENTE);
   Lista.Mostrar(DESCENDENTE);

   Lista.Primero();
   cout << "Primero: " << Lista.ValorActual() << endl;
  
   Lista.Ultimo();
   cout << "Ultimo: " << Lista.ValorActual() << endl;
  
   Lista.Borrar(500);
   Lista.Borrar(1000);
   Lista.Borrar(1500);
   Lista.Borrar(2000);
   Lista.Borrar(2500);
   Lista.Borrar(-500);
   Lista.Borrar(-1000);
   Lista.Borrar(-1500);
   Lista.Borrar(-2000);
   Lista.Borrar(-2500);
   Lista.Mostrar(ASCENDENTE);
   Lista.Mostrar(DESCENDENTE);

   cin.get();
   return 0;
}
__________________________________________________________________

 LISTAS CIRCULARES                                                                                                      

#include <iostream>
using namespace std;

class nodo {
   public:
    nodo(int v, nodo *sig = NULL)
    {
       valor = v;
       siguiente = sig;
    }

   private:
    int valor;
    nodo *siguiente;
       
   friend class lista;
};

typedef nodo *pnodo;

class lista {
   public:
    lista() { actual = NULL; }
    ~lista();
   
    void Insertar(int v);
    void Borrar(int v);
    bool ListaVacia() { return actual == NULL; }
    void Mostrar();
    void Siguiente();
    bool Actual() { return actual != NULL; }
    int ValorActual() { return actual->valor; }
   
   private:
    pnodo actual;
};

lista::~lista()
{
   pnodo nodo;

   // Mientras la lista tenga más de un nodo
   while(actual->siguiente != actual) {
      // Borrar el nodo siguiente al apuntado por lista
      nodo = actual->siguiente;
      actual->siguiente = nodo->siguiente;
      delete nodo;
   }
   // Y borrar el último nodo
   delete actual;
   actual = NULL;
}

void lista::Insertar(int v)
{
   pnodo Nodo;

   // Creamos un nodo para el nuevo valor a insertar
   Nodo = new nodo(v);

   // Si la lista está vacía, la lista será el nuevo nodo
   // Si no lo está, insertamos el nuevo nodo a continuación del apuntado
   // por lista
   if(actual == NULL) actual = Nodo;
   else Nodo->siguiente = actual->siguiente;
   // En cualquier caso, cerramos la lista circular
   actual->siguiente = Nodo;
}

void lista::Borrar(int v)
{
   pnodo nodo;

   nodo = actual;

   // Hacer que lista apunte al nodo anterior al de valor v
   do {
      if(actual->siguiente->valor != v) actual = actual->siguiente;
   } while(actual->siguiente->valor != v && actual != nodo);
   // Si existe un nodo con el valor v:
   if(actual->siguiente->valor == v) {
      // Y si la lista sólo tiene un nodo
      if(actual == actual->siguiente) {
         // Borrar toda la lista
         delete actual;
         actual = NULL;
      }
      else {
         // Si la lista tiene más de un nodo, borrar el nodo  de valor v
         nodo = actual->siguiente;
         actual->siguiente = nodo->siguiente;
         delete nodo;
      }
   }
}

void lista::Mostrar()
{
   pnodo nodo = actual;

   do {
      cout << nodo->valor << "-> ";
      nodo = nodo->siguiente;
   } while(nodo != actual);

   cout << endl;
}

void lista::Siguiente()
{
   if(actual) actual = actual->siguiente;
}

int main()
{
   lista Lista;
  
   Lista.Insertar(500);
   Lista.Insertar(1000);
   Lista.Insertar(1500);
   Lista.Insertar(2000);
   Lista.Insertar(2500);

   Lista.Insertar(-500);
   Lista.Insertar(-1000);
   Lista.Insertar(-1500);
   Lista.Insertar(-2000);
   Lista.Insertar(-2500);

   Lista.Mostrar();

   cout << "Lista de elementos:" << endl;
   Lista.Borrar(500);
   Lista.Borrar(1000);

   Lista.Mostrar();

   Lista.Insertar(-8000);
   Lista.Insertar(3500);
   Lista.Mostrar();
   cin.get();
   return 0;
}

___________________________________________________________


CORPORACIÓN IBEROAMERICANA DE ESTUDIOS

MATERIA:
ESTRUCTURA DE DATOS


INTEGRANTES DEL TRABAJO:
  • LICETH REPIZO PRADA
  • NILSON HUERFANO
  • FABIAN IBAÑEZ


MAESTRO:
  • JORGE RODRIGUEZ


JORNADA:
SÁBADOS 8AM-12PM
Publicado por en

No hay comentarios:

Publicar un comentario

Suscribirse a: Enviar comentarios (Atom)