SITES

PRESENTACION EN PREZI

PRESENTACION EN  PREZI

MAPA MENTAL " COLAS"

EJEMPLOS EN C++ DE BÚSQUEDA E INSERCIÓN DE ELEMENTOS EN LISTAS

#include <cstdlib>
#include <iostream>
#include <list>

using namespace std;

// Ejemplo: buscar e insertar
void insertar()
{
    list <string> nombres;

    nombres.push_back("Juan");
    nombres.push_back("Jose");
    nombres.push_back("Pedro");
    nombres.push_back("Pablo");

   // Se obtiene un iterador al inicio de la lista  
   list<string>::iterator it = nombres.begin();

    // Buscamos el elemento "Pedro"
    while (*it != "Pedro" && it != nombres.end() ) it++;

    // Insertamos un elemento "Maria" en la posición indicada
    // por el iterador it.
    nombres.insert(it, 1, "Maria");

    it = nombres.begin();
    while( it != nombres.end() )
    {
      cout << *it++ << endl;
    }
}

int main(int argc, char *argv[])
{
    insertar();
    system("PAUSE");
    return EXIT_SUCCESS;
}

EJEMPLOS EN C++ DE 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() { if(actual) actual = actual->siguiente; }
    void Primero() { actual = primero; }
    void Ultimo() { Primero(); if(!ListaVacia()) while(actual->siguiente) Siguiente(); }
    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 nuevo 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;
}

int main() {
   lista Lista;
 
   Lista.Insertar(20);
   Lista.Insertar(10);
   Lista.Insertar(40);
   Lista.Insertar(30);

   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(10);
   Lista.Borrar(15);
   Lista.Borrar(45);
   Lista.Borrar(30);
   Lista.Borrar(40);
 
   Lista.Mostrar();

   cin.get();
   return 0;
}

LISTAS “OPERACIONES BÁSICAS”

ü INSERTAR ELEMENTOS EN UNA LISTA VACÍA:

El proceso es muy simple, bastará con que:

1.    nodo->siguiente apunte a NULL.

2.    Lista apunte a nodo.

                                                                                   

ü INSERTAR UN ELEMENTO EN LA PRIMERA POSICIÓN DE UNA LISTA:

El proceso sigue siendo muy sencillo: 

1.    Hacemos que nodo->siguiente apunte a Lista.

2.    Hacemos que Lista apunte a nodo.

ü INSERTAR UN ELEMENTO EN LA ÚLTIMA POSICIÓN DE UNA LISTA:

1.    Necesitamos un puntero que señale al último elemento de la lista. La manera de conseguirlo es empezar por el primero y avanzar hasta que el nodo que tenga como siguiente el valor NULL.

2.    Hacer que nodo->siguiente sea NULL.

3.      Hacer que ultimo->siguiente sea nodo.

ü INSERTAR UN ELEMENTO A CONTINUACIÓN DE UN NODO CUALQUIERA DE UNA LISTA:

El proceso a seguir será:

1.    Hacer que nodo->siguiente señale a anterior->siguiente.

2.    Hacer que anterior->siguiente señale a nodo.

ü LOCALIZAR ELEMENTOS EN UNA LISTA ABIERTA:

1.    Asignamos al puntero índice el valor de Lista.

2.    Abriremos un bucle que al menos debe tener una condición, que el índice no sea NULL.

3.    Dentro del bucle asignaremos al índice el valor del nodo siguiente al índice actual.

Por ejemplo, para mostrar todos los valores de los nodos de una lista, podemos usar el siguiente bucle en C:

typedef struct _nodo {
int dato;
struct _nodo *siguiente;
struct _nodo *anterior;
} tipoNodo;

typedef tipoNodo *pNodo;
typedef tipoNodo *Lista;
...
pNodo = indice;
...
indice = Lista;
while(indice->anterior) indice = indice->anterior;
while(indice) {
printf("%d\n", indice->dato);
indice = indice->siguiente;
}

ü ELIMINAR EL PRIMER NODO DE UNA LISTA ABIERTA:

1.  Hacemos que nodo apunte al primer elemento de la lista, es decir a Lista.

2.  Asignamos a Lista la dirección del segundo nodo de la lista: Lista->siguiente.

3.  Liberamos la memoria asignada al primer nodo, el que queremos eliminar.

           

ü ELIMINAR UN NODO CUALQUIERA DE UNA LISTA ABIERTA

El proceso es parecido al del caso anterior:

1.    Hacemos que nodo apunte al nodo que queremos borrar.

2.    Ahora, asignamos como nodo siguiente del nodo anterior, el siguiente al que queremos eliminar: anterior->siguiente = nodo->siguiente.

3.    Eliminamos la memoria asociada al nodo que queremos eliminar.

ü MOVERSE A TRAVÉS DE UNA LISTA ABIERTA

Sólo hay un modo de moverse a través de una lista abierta, hacia delante.

Primer elemento de una lista:

El primer elemento es el más accesible, ya que es a ese a que apunta el puntero que

define la lista. 

1. Para obtener un puntero al primer elemento bastará con copiar el puntero Lista.

Elemento siguiente a uno cualquiera:

Supongamos que tenemos un puntero nodo que señala a un elemento de una lista. Para obtener un puntero al siguiente bastará con asignarle el campo "siguiente" del nodo, nodo^. Siguiente.

Elemento anterior a uno cualquiera:

Ya hemos dicho que no es posible retroceder en una lista, de modo que para obtener un puntero al nodo anterior a uno dado tendremos que partir del primero, e ir avanzando hasta que el nodo siguiente sea precisamente nuestro nodo, teniendo un puntero auxilia para contener el anterior.

Nodo = Primero

MIENTRAS no sea el nodo buscado HACER

 Auxiliar = Nodo

 Nodo =  Nodo^.siguiente

FIN_MIENTRAS

Auxiliar apuntara al nodo anterior al buscado

Ultimo elemento de una lista:

Para obtener un puntero al último elemento de una lista se parte del primer nodo y se avanza hasta que el nodo apunte a NULO, el auxiliar apuntara al último. También se

puede preguntar anticipadamente por el valor NULO evitándose de este modo el puntero auxiliar.

Suponiendo la lista no vacía

Nodo = Primero;

MIENTRAS Nodo^.siguiente <> NULO HACER

 Nodo _ Nodo^.siguiente

FIN_MIENTRAS

En este caso Nodo, al final del ciclo apunta el último nodo de la estructura

Como determinar si  una lista está vacía:

Basta con comparar el puntero Lista con NULL si Lista vale NULO la lista está vacía.

ü BORRAR UNA LISTA COMPLETA

El algoritmo genérico para borrar una lista completa consiste simplemente en borrar el primer elemento sucesivamente mientras la lista no esté vacía.

Para liberar todo el espacio ocupado por una lista es necesario liberar celda por celda.

procedure borrar_lista(l: lista);

var

   p: lista;

begin

   while l <> nil do

   begin

       p:= l;

       l:= l^.siguiente;

       dispose(p);

   end;

end;

MAPA CONCEPTUAL