LISTAS ENLAZADAS

Una lista enlazada la constituye una colección lineal de elementos, llamados nodos, donde el orden de los mismos se establece mediante punteros. Cada nodo se divide en dos partes: una primera que contiene la información asociada al elemento, y una segunda parte, llamada campo de enlace o campo al siguiente puntero, que contiene la dirección del siguiente nodo de la lista.

Una lista enlazada es una colección lineal de elementos donde el orden de los mismos se establece mediante punteros. La idea básica es que cada componente de la lista incluya un puntero que indique donde puede encontrarse el siguiente componente por lo que el orden relativo de estos puede ser fácilmente alterado modificando los punteros lo que permite, a su vez, añadir o suprimir elementos de la lista.

Una lista enlazada es una serie de nodos, conectados entre sí a través de una referencia, en donde se almacena la información de los elementos de la lista. Por lo tanto, los nodos de una lista enlazada se componen de dos partes principales:

Ventajas de usar listas: Las listas son dinámicas, es decir, podemos almacenar en ellas tantos elementos como necesitemos, siempre y cuando haya espacio suficiente espacio en memoria. Al insertar un elemento en la lista, la operación tiene un tiempo constante independientemente de la posición en la que se inserte, solo se debe crear el nodo y modificar los enlaces. Esto no es así en los arreglos, ya que si el elemento lo insertamos al inicio o en medio, tenemos un tiempo lineal debido a que se tienen que mover todos los elementos que se encuentran a la derecha de la posición donde lo vamos a insertar y después insertar el elemento en dicha posición; solo al insertar al final del arreglo se obtienen tiempos constantes. Al eliminar un elemento paso lo mismo que se menciono en el punto anterior.

Desventajas de usar listas:

El acceso a un elemento es más lento, debido a que la información no está en posiciones contiguas de memoria, por lo que no podemos acceder a un elemento con base en su posición como se hace en los arreglos.

REPRESENTACION DE LISTAS ENLAZADAS EN MEMORIA

Sea LISTA una lista enlazada, salvo que se indique lo contrario. Almacenaremos LISTA en memoria de la forma siguiente. Como mínimo, LISTA estará compuesta por dos arrays lineales, a los que llamaremos INFO y ENLACE, tales que INFO [K] y ENLACE [K] contienen la parte de información y el campo de puntero de cada nodo de LISTA respectivamente. Necesitamos también una variable especial llamada COMIENZO que contiene la posición ocupada por el primer elemento de la lista, y una marca especial NULO que indica el final de la misma. Puesto que los índices de los arrays INFO y ENLACE serán habitualmente positivos, el valor NULO será el -999, salvo que digamos lo contrario.

El siguiente ejemplo muestra la representación memoria de una lista enlazada en la que cada nodo de la lista contiene un único carácter. Podemos obtener la lista de caracteres o, en otras palabras, la cadena de la forma siguiente:

COMIENZO = 9, luego INFO [9] = N primer carácter.

ENLACE [9] = 3, luego INFO [3] = 0 segundo carácter.

ENLACE [3] = 6, luego INFO [6] = (carácter blanco) tercer carácter.

ENLACE [6] = 11, luego INFO [11] = E cuarto carácter.

ENLACE [11] = 7, luego INFO [7] = X quinto carácter.

ENLACE [7] = 10, luego INFO [10] = I sexto carácter.

ENLACE [10] = 4, luego INFO [4] = T séptimo carácter.

ENLACE [4] = -999 valor nulo, luego termina la lista.

FORMA PRINCIPAL DE LA LISTA ENLAZADA

Codigo:

 
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
 
namespace WindowsApplication1
{
    public partial class Listas : Form
    {
        public Listas()
        {
            InitializeComponent();
        }
        public static int[] enlace = new int[10] { 2, 3, 4, 0, -999, 6, 7, 8, 9, -999 };
        public static string[] alumno = new string[10] { "Jose", "Ana", "Rosa", "Beto", "zeta", "", "", "", "", "" };
        public static int comienzo = 1;
        public static int disponible = 5;
        private void cmdInsercion_Click(object sender, EventArgs e)
        {
            Insercion ins = new Insercion();
            ins.Show();
        }
 
        private void cmdRecorrido_Click(object sender, EventArgs e)
        {
            Recorrer rec = new Recorrer();
            rec.Show();
        }
 
        private void cmdBusqueda_Click(object sender, EventArgs e)
        {
            Busqueda bus = new Busqueda();
            bus.Show();
        }
 
        private void cmdEliminacion_Click(object sender, EventArgs e)
        {
            Eliminacion eli = new Eliminacion();
            eli.Show();
        }
    }
}

Corrida

:estructura_datos_csharp:listas_enlazadas.jpg

RECORRIDO DE UNA LISTA ENLAZADA

Sea la lista enlazada, almacenada en memoria mediante dos arrays INFO y ENLACE. Adicionalmente definimos la variable COMIENZO que apunta al primer elemento de la lista y suponemos que el último nodo de la lista contiene en su campo ENLACE el valor NULO. Supongamos que queremos recorrer LISTA para procesar cada uno de sus nodos exactamente una vez. A continuación te mostrare el algoritmo que realiza esta tarea y que utilizaremos en otras aplicaciones.

Nuestro algoritmo utiliza una variable puntero PTR que apunta siempre al nodo procesado en cada momento. Por ello ENLACE [PTR] indica el siguiente nodo a ser procesado. De esta forma la asignación PTR:= ENLACE [PTR] Tiene el efecto de mover el puntero al siguiente nodo de la lista.

La descripción del algoritmo es la siguiente. Inicializamos PTR a COMIENZO. A continuación procesamos INFO [PTR], es decir, la información del primer nodo. En el paso siguiente actualizamos PTR mediante la asignación PRT: = ENLACE [PTR], lo que hace que PTR apunte ahora al segundo nodo. Nuevamente tratamos de la información contenida en INFO [PTR] (segundo nodo) y tras esto volvemos a actulizar PTR y procesamos INFO [PTR], y asi sucesivamente. Este proceso de actualizacion y procesamiento continuara hasta que en una de las actualizaciones de PTR obtengamos que PTR = NULO, que marca el final de la lista.

Una representación formal de algoritmo es la siguiente.

Algoritmo: Recorrido de una lista enlazada.


Sea LISTA una lista enlazada que almacenamos en memoria. El algoritmo recorre LISTA realizando la operación PROCESO a cada elemento de LISTA. La variable PTR, apunta en cada momento al nodo que se esta tratando.

  1. PTR: = COMIENZO. [inicializa el puntero].
  2. repetir pasos 3 y 4 mientras PTR != 0.
  3. aplicar PROCESO a INFO [PTR].
  4. PTR: = ENLACE [PTR]. [PTR apunta ahora al siguiente nodo]. [fin del ciclo paso 2].
  5. salir.

Codigo:

 
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
 
namespace WindowsApplication1
{
    public partial class Recorrer : Form
    {
        public Recorrer()
        {
            InitializeComponent();
            Recorrido();
        }
 
        private void cmdRecorrer_Click(object sender, EventArgs e)
        {
            listBox1.Items.Clear();
            Recorrido();
        }
 
        private void Recorrido()
        {
            int ptr = Listas.comienzo;
            while (ptr != -999)
            {
                listBox1.Items.Add(Listas.alumno[ptr]);
                ptr = Listas.enlace[ptr];
            }
        }
        private void button1_Click(object sender, EventArgs e)
        {
            this.Close();
        }
    }
}

Corrida

:estructura_datos_csharp:listas_recorrido.jpg

BUSQUEDA EN UNA LISTA ENLAZADA

Sea LISTA una lista enlazada, almacenada en memoria. En esta seccion discutimos dos algoritmos de búsqueda que localizan la posición del nodo (LUG) en el cual un elemento dado (ELEMENTO) aparece por primera vez en la lista. El primer algoritmo no necesita que la lista este ordenada, mientras que el segundo si lo exige.

Si ELEMENTO es una valor de clave y buscamos en el archivo para encontrar el registro que lo contiene, este solo puede aparecer una vez en la lista.

Lista no ordenadas

Supongamos que los datos de lista no estan ordenados (necesariamente). En este caso podremos localizar ELEMENTO sin mas que recorrer LISTA utilizando el puntero PTR y comparando ELEMENTO con el contenido INFO [PTR] de cada nodo. Cada vez que actualicemos PTR mediante la asignación PTR: = ENLACE [PTR], necesitamos dos comprobaciones. Primero necesitamos ver si hemos alcanzado el final de la lista, es decir comprobamos si PTR = NULO, si no, entonces comprobamos si INFO [PTR] = ELEMENTO.

Las dos comprobaciones no podemos realizarlas simultáneamente, puesto que si PTR = NULO no existira INFO [PTR]. De acuerdo con esto utilizamos la primera comparación para controlar la ejecución de un ciclo y realizamos la segunda comparación dentro de este.

Algoritmo: BUSQ(INFO, ENLACE, COMIENZO, ELEMENTO, LUG)


LISTA es una lista enlazada almacenada en memoria. el algoritmo encuentra la posicion LUG del nodo donde ELEMENTO aparece por primera vez en lista y devuelve LUG = NULO.

  1. PTR: = COMIENZO.
  2. repetir paso 3 mientras PTR != NULO:
  3. si ELEMENTO = INFO[PTR], entonces: LUG: = PTR y salir.
  4. si no: PTR: = ENLACE [PTR]. [PTR apunta ahora al nodo siguiente].
  5. [final de la estructura condicional].
  6. [final del ciclo del paso 2].
  7. [la busqueda es fallida]. LUG: = NULO.
  8. salir

Lista ordenada

Supongamos que los datos de LISTA estan ordenados. de nuevo buscamos ELEMENTO en la lista recorriendo la misma utilizando una variable puntero y comparando ELEMENTO con el contenido de INFO[PTR] nodo a nodo. en este caso, sin embargo, podremos finalizar la busqueda una vez que ELEMENTO sea mayor que INFO[PTR].

Algoritmo: BUSQ(INFO, ENLACE, COMIENZO, ELEMENTO, LUG)


LISTA es una lista ordenada que se encuentra en memoria. el algoritmo encuentra la posicion LUG del nodo donde se encuentra por pirmera vez ELEMENTO o bien devuelve LUG = NULO.

  1. PTR:= COMIENZO.
  2. repetir paso 3 mientras PTR != NULO:
  3. si ELEMENTO < INFO[PTR], entonces:
  4. PTR: = ENLACE [PTR]. [PTR apunta al siguiente nodo].
  5. si no, si ELEMENTO = INFO[PTR], entonces:
  6. LUG = PTR y salir. [la busqueda es satisfactoria].
  7. si no: LUG: = NULO y salir. [ELEMENTO es mayor que INFO[PTR.
  8. [final de la estructura condicional]
  9. [final del ciclo del paso 2]
  10. LUG: = NULO.
  11. salir.

Codigo:

 
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
 
namespace WindowsApplication1
{
    public partial class Busqueda : Form
    {
        public Busqueda()
        {
            InitializeComponent();
        }
 
        private void cmdBuscar_Click(object sender, EventArgs e)
        {
            string elemento = txtbuscador.Text.ToString();
            int lug = -999;
            int ptr = Listas.comienzo;
            if (ptr == -999) MessageBox.Show("Lista vacia", "Error");
            while (ptr != -999)
            {
                if (Listas.alumno[ptr] == elemento)
                {
                    lug = ptr;
                    MessageBox.Show("Elemento encontrado en \nposicion: " + lug.ToString(), "Elemento Encontrado");
                    txtbuscador.Clear();
                }
                else ptr = Listas.enlace[ptr];
            }
            if (lug == -999) MessageBox.Show("Elemento no encontrado", "Error");
        }
 
        private void button1_Click(object sender, EventArgs e)
        {
            this.Hide();
        }
    }
}

Corrida

:estructura_datos_csharp:listas_busqueda.jpg

INSERCION EN UNA LISTA ENLAZADA

Sea LISTA una lista enlazada en la que los nodos A y B ocupan posiciones sucesivas en el orden impuesto en la lista. Supongamos que queremos insertar en ella un nodo N que debe ocupar un lugar entre A y B. Después de la operación el nodo A apuntara al nodo N y este apuntara al nodo B, es decir, el nodo al que apuntaba antes A.

Algoritmo de insercion

tres son las situaciones mas comunes que nos encontraremos cuando insertamos nodos en una lista. Primero cuando queremos insertar un nodo al principio de la lista, segundo cuando queramos insertar un nodo detras de un detreminado, y tercero, cuando insertamos un nodo en una lista previamente ordenada. A continuacion discutimos los algoritmos que llevan a cabo estas tareas suponiendo que la lista esta almacenada en memoria en la forma LISTA(INFO, ENLACE, COMIENZO, DISP) y que la variable ELEMENTO contiene la informacion que debe incorporarse a la lista.

Puesto que nuestros algoritmos de insercion utilizaran nodos de la lista de nodos disponibles, todos ellos deben incluir los siguientes pasos:

Insercion al principio de una lista

Supongamos que nuestra lista no esta ordenada ni existe ninguna razon por la cual cualquier nodo que insertemos deba ocupar una determinada posicion. En este caso lo mas sencillo sera insertar el nuevo nodo al comienzo de la misma. Un algoritmo que realiza esta operacion es el siguiente.

Algoritmo: INSPRIN(INFO, ENLACE, COMIENZO, DISP, ELEMENTO)


El algoritmo coloca ELEMENTO como primer componente de la lista.

  1. [Overflow] si DISP = NULO, entonces: Escribir: OVERFLOW y salir.
  2. [extrae el primer nodo de la lista DISP].
  3. NUEVO: = DISP y DISP: = ENLACE[DISP].
  4. INFO[NUEVO]: = ELEMENTO. [copia el dato en el nodo].
  5. ENLACE[NUEVO]: = COMIENZO. [el nuevo nodo apunta ahora al que ocupa antes la primera posicion].
  6. COMIENZO: = NUEVO. [COMIENZO apunta ahora al elemento que ocupa la primera posicion de la lista].
  7. Salir.

Insercion a continuacion de un nodo determinado

Supongamos en este caso que se nos da un valor LUG que o bien representa la localizacion de un nodo A determinado o bien LUG = NULO. El algoritmo siguiente inserta ELEMENTO en la lista a continuacion de A o bien coloca ELEMENTO como primer componente de la lista si LUG = NULO.

Sea N el nuevo nodo (cuya posicion es NUEVO). Si LUG = NULO, entonces el nodo se coloca al comienzo de la lista. En otro caso hacemos que N apunte al nodo B (que originalmente seguia a A). El proceso implica las siguientes operaciones:

ENLACE[NUEVO]: = ENLACE[LUG]

despues del cual N apunta a B y

ENLACE[LUG]: = NUEVO

tras el cual A apunta al nodo N.

Algoritmo: INSLUG(INFO, ENLACE, COMIENZO, DISP, LUG, ELEMENTO)


el algoritmo inserta ELEMENTO a continuacion del nodo que ocupa la posicion LUG o coloca ELEMENTO como primer nodo si LUG=NULO

  1. [Overflow] Si DISP = NULO, entonces: escribir: OVERFLOW y salir.
  2. [Extrae el primer nodo de la lista de disponibles]
  3. NUEVO: = DISP y DISP: = ENLACE[DISP].
  4. INFO[NUEVO]: = ELEMENTO. [copia el dato en el nodo obtenido].
  5. Si LUG = NULO, entonces [Lo inserta como primer nodo].
  6. ENLACE[NUEVO]: = COMIENZO y COMIENZO: = NUEVO.
  7. Si no: [Inserta detras del nodo de posicion LUG].
  8. ENLACE[NUEVO]: = ENLACE[LUG] y ENLACE[LUG]: = NUEVO.
  9. [Final de la estructura condicional]
  10. Salir.

Insercion de una lista enlazada y ordenada

Supongamos que queremos insertar ELEMENTO en una lista enlazada y ordenada y que ELEMENTO cumple que INFO(a)<ELEMENTO⇐INFO(b). Por tanto ELEMENTO debe insertarse en un nuevo nodo entre A y B. El procedimiento siguiente calcula la posicion LUG que ocupa el nodo A, es decir, la posicion del nodo que precedera a ELEMENTO en la lista.

Para ello utiliza dos punteros PTR y AUX. Con PTR recorre la lista y va comparando ELEMENTO con INFO[PTR] para todos los nodos que visita. Despues de cada comparacion actualiza el valor de ambos punteros, de tl forma que AUX:= PTR y posteiormente PTR:= ENLACE[PTR]. Con este mecanismo garantizamos que AUX siempre apunta al nodo que precede al que esta siendo apuntado por PTR. El recorrido de la lista continua hast que INFO[PTR] > ELEMENTO, o en otras palabras, la busqueda finaliza cuando ELEMENTO ⇐ INFO[PTR].

Una representacion formal del procedimiento es el siguiente. En dicho procedimiento se comtemplan por separado los casos en que la lista esta vacia o bien cuando ELEMENTO < INFO[COMIENZO] debido a que no precisan el uso de la variable AUX.

Procedimiento: ENCA (INFO, ENLACE, COMIENZO, ELEMENTO, LUG)


El procedimiento encuentra la posicion LUG del ultimo nodo para el que INFO[LUG] < ELEMENTO o hace LUG = NULO.

  1. [¿Lista vacia?] Si COMIENZO = NULO, entonces: LUG = NULO y retornar.
  2. [¿caso especial?] Si ELEMENTO < INFO[COMIENZO]. entonces: LUG: = NULO y retornar.
  3. AUX: = COMIENZO y PTR: = ENLACE[COMIENZO]. [Inicializamos los punteros].
  4. Repetir pasos 5 y 6 mientras PTR != NULO.
  5. Si ELEMENTO < INFO[PTR]. entonces:
  6. LUG: = AUX y retornar.
  7. [Final de la estructura condicionla].
  8. AUX: = PTR y PTR: = ENLACE[PTR]. [Actualiza los punteros].
  9. LUG: = AUX.
  10. Salir.

Despues de esto ya tenemos las herramientas necesarias para diseñar un algoritmo que nos inserte ELEMENTO en una lista enlazada.

Algoritmo: INSERT(INFO, ENLACE, COMIENZO, DISP, ELEMENTO)


El algoritmo inserta ELEMENTO en una lista enlazada ordenada.

  1. [Utilizamos el procedimiento 6 para encontrar la posicion del nodo que precedera a ELEMENTO.]
  2. Llamar ENCA (INFO, ENLACE, COMIENZO, ELEMENTO, LUG)
  3. [Utilizaremos el algoritmo 5 para insertar ELEMENTO a continuacion del nodo que ocupa la posicion LUG.]
  4. Llamar INSLUG(INFO, ENLACE, COMIENZO, DISP, LUG, ELEMENTO)
  5. Salir.

Codigo:

 
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
 
namespace WindowsApplication1
{
    public partial class Insercion : Form
    {
        public Insercion()
        {
            InitializeComponent();
        }
 
 
        private void cdmInserta_Click(object sender, EventArgs e)
        {
            string elemento = txtInser.Text;
            txtInser.Clear();
            if (Listas.disponible == -999)
            {
                MessageBox.Show("Lista llena", "Error", MessageBoxButtons.OK);
            }
            else
            {
                int anterior = -999;
                int ptr = Listas.comienzo;
                int i = 0,nuevo;
                nuevo = Listas.disponible;
                bool aux = false;
                Listas.disponible = Listas.enlace[nuevo];
                Listas.alumno[nuevo] = elemento;
                while (ptr != -999 && aux == false)
                {
                    if (Listas.alumno[ptr].Length < elemento.Length) { i = Listas.alumno[Listas.comienzo].Length; }
                    else { i = elemento.Length; }
                    int h = 0;
                    for (h=0; h < i; h++)
                    {
                        if (Listas.alumno[ptr][h] == elemento[h]) {}
                        if (Listas.alumno[ptr][h] < elemento[h])                        {                            anterior = ptr;                            h = i;
                        }
                        else                        {                            h = i;                            aux = true;                        }
                    }
                    ptr = Listas.enlace[ptr];
                }
                if (anterior == -999)
                {
                    Listas.enlace[nuevo] = Listas.comienzo;
                    Listas.comienzo = nuevo;
                }
                else
                {
                    Listas.enlace[nuevo] = Listas.enlace[anterior];
                    Listas.enlace[anterior] = nuevo;
                }
                button1.Text = "Cerrar";
            }
        }
 
        private void button1_Click(object sender, EventArgs e)
        {
            this.Hide();
        }
    }
}

Corrida

:estructura_datos_csharp:listas_insercion.jpg

ELIMINACION DE UN ELEMENTO DE UNA LISTA ENLAZADA

Sea lista una lista enlazada en la cual el nodo N se encuentra entre los nodos A y B. Supongamos que queremos eliminar el nodo N de la lista. La eliminación se produce tan pronto como el puntero de enlace siguiente del nodo A apunte al nodo B. (por ello cuando realizamos eliminaciones debemos almacenar de alguna forma la direccion del nodo que precede al que vamos a borrar.)

Supongamos que la lista enlazada se mantiene en memoria en la forma siguiente:

LISTA(INFO, ENLACE, COMIENZO, DISP)

Cuando eliminamos el nodo N de la lista debemos devolverlo inmediatamente a la lista de espacio disponible. Por facilidad en el proceso esta devolucion se realiza insertando el nodo devuelto al principio de la lista DISP. Observese que esta operación implica cambiar tres punteros de la forma siguiente:

Existen dos casos especiales que implican actuaciones distintas. Si el nodo N que eliminamos es el primero de la lista, el puntero COMIENZO debera cambiarse para apuntar al nodo B. En cambio, si N es el ultimo de la lista, entonces el puntero A debera ponerse a NULO.

Algoritmos de eliminación

Los algoritmos que eliminan nodos de una lista son utilizados en distintas situaciones. En este epígrafe discutiremos dos de ellas. La primera situación es la que implica borrar el nodo siguiente a uno dado. La segunda situación implica borrar un nodo que contiene un determinado elemento. En todos los algoritmos suponemos que la lista enlazada se almacena en memoria de la forma

LISTA (INFO, ENLACE, COMIENZO, DISP).

Tambien en todos ellos devolvemos el nodo eliminado a la lista de nodos disponibles, insertandolos al principio de esta. Por ello nuestros algoritmos incluiran las siguientes asignaciones, donde LUG es la posición del nodo N borrado: ENLACE[LUG]: = DISP y DISP: = LUG.

Algunos de nuestros algoritmos pueden borrar o bien el primer elemento de la lista o bien el ultimo. Cualquier algoritmo que haga esto debe analizar primero si existe algun elemento en la lista. Si no existe ningun, si COMIENZO = NULO, el algoritmo imprimira el mensaje UNDERFLOW.

Eliminacion del nodo sucesor de uno determinado

Sea LISTA una lista enlazada almacenada en memoria. Supongamos que queremos eliminar de LISTA el nodo N que ocupa el lugar LUG y que conocemos el lugar LUGP del nodo que precede a N en la lista o bien si el nodo N es el primer LUG = NULO. El algoritmo siguiente elimina N de la lista.

Algoritmo: BOR (INFO, ENLACE, COMIENZO, DISP, LUG, LUGP)


El algoritmo elimina de la lista el nodo N que ocupa la posición LUG, siendo LUGP la posición del nodo que precede a N o bien LUGP = 0 si N es el primero de la lista.

  1. si LUGP = NULO. Entonces:
  2. COMIENZO: = ENLACE[COMIENZO]. [Elimina el primer nodo].
  3. Si no:
  4. ENLACE[LUGP]: = ENLACE[LUG]. [Elimina el nodo N].
  5. [Final de la estructura condicional].
  6. [Devolvemos el nodo a la lista DISP].
  7. ENLACE[LUG]: = DISP Y DISP: = LUG.
  8. Salir.

Eliminacion de un nodo que contiene un determinado elemento de informacion

Sea LISTA una lista enlazada almacenada en memoria. Supongamos que queremos eliminar de la lista el primer nodo N que contenga la informacion ELEMENTO. (Si ELEMENTO es un valor de clave, solo puede contenerlo un unico nodo.) Recuerdese que antes de borrar el nodo N que contiene a ELEMENTO debemos conocer que nodo precede a N en la lista. Por ello veremos previamente un procedimiento que localiza la posicion LUG del nodo N que contiene a ELEMENTO y la posicion LUGP del nodo que precede a N. En el caso de que N sea el primer nodo de la lista, el procedimiento devuelve LUGP = NULO y en caso de que ELEMENTO no se encuentre en la lista devolvera LUG = NULO. (Como puede verse el procedimiento es similar al procedimiento)

Procedimiento: ENCB(INFO, ENLACE, COMIENZO, ELEMENTO, LUG, LUGP)


El procedimiento encuentra la posicion LUG del primer nodo N que contiene a ELEMENTO y la posicion LUGP del nodo anterior a N. Si ELEMENTO no se encuentra en la lista, el procedimiento devuelve LUG = NULO y si ELEMENTO se encuentra en el primer nodo, entonces hace LUGP = NULO.

  1. [¿Lista vacia?] Si COMIENZO: = NULO, entonces:
  2. LUG: = NULO Y LUGP: = NULO y Retornar.
  3. [Final de la estructura condcional].
  4. [¿Se encuentra ELEMENTO en el priemr nodo?]
  5. Si INFO[COMIENZO] = ELEMENTO, entonces
  6. LUG: = COMIENZO y LUGP = NULO y Retornar.
  7. [Final de la estructura condicional].
  8. AUX: = COMIENZO y PTR: = ENLACE[COMIENZO]. [Inicializamos los punteros].
  9. Repetir mientras PTR != NULO.
  10. Si INFO[PTR] = ELEMENTO, entonces:
  11. LUG: = PTR y LUGP: = AUX y Retornar.
  12. [Final de la estructura condicional].
  13. AUX: = PTR y PTR: = ENLACE[PTR]. [Actualizamos los punteros]:
  14. [Final del ciclo].
  15. LUG: = NULO [Busqueda fallida].
  16. Retornar.

El procedimiento recorre la lista utilizando dos punteros PTR y AUX. Con PTR recorremos la lista y comparamos sucesivamente ELEMENTO con INFO[PTR]. En cada momento AUX apunta al nodo anterior al apuntado por PTR. Por ello despues de cada fallida actualizamos ambas de la siguiente forma:

AUX: = PTR y PTR: = ENLACE[PTR]

El recorrido de la lista continua mientras que INFO[PTR] != ELEMENTO o, en otras palabras, la busqueda termianra cuando INFO[PTR]=ELEMENTO. En este momento PTR = LUG o direccion del nodo N buscado y AUX apuntara al nodo anterior.

La formalizacion de este procedimieno se establece a continuacion. En ella se puede observar que se tratan por separado los casos en que la lista esta vacia y el caso en que N es el primer nodo. Esto se hace asi debido a que ambos casos no precisan la utilizacion de la variable AUX.

Despues de desarrollar este procedimiento estamos en condiciones de diseñar un algoritmo muy sencillo que elimina de una lista enlazada aquel nodo N en el que aparece por primera vez la informacion ELEMENTO. La simplicidad de este algoritmo estriba en que la localizacion de N y de su prodecesor pueda realizarse utilizando el procedimiento anterior.

Algoritmo: ELIMINAR(INFO, ENLACE, COMIENZO, DISP, ELEMENTO)


El algoritmo elimina de la lista enlazada el primer nodo N que contiene la informacion ELEMENTO.

  1. [Utilizamos el procedimiento anterior para encontrar la posicion de N y su predecesor en la lista.]
  2. Llamar ENCB(INFO, ENLACE, COMIENZO, ELEMENTO, LUG, LUGP).
  3. Si LUG: = NULO, entonces: Escribir: ELEMENTO no se encuentra en la lista y salir.
  4. [Eliminamos el nodo].
  5. Si LUGP = NULO, entonces:
  6. COMIENZO: = ENLACE[COMIENZO]. [Eliminamos el primer nodo].
  7. Si no:
  8. ENLACE[LUGP]: = ENLACE[LUG].
  9. [Final de la estructura condicional].
  10. [Devolvemos el nodo eliminado a la lista de nodos disponibles].
  11. ENLACE[LUG]: = DISP y DISP: = LUG.
  12. Salir.

Codigo:

 
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
 
namespace WindowsApplication1
{
    public partial class Eliminacion : Form
    {
        public Eliminacion()
        {
            InitializeComponent();
        }
 
        private void cmdEliminar_Click(object sender, EventArgs e)
        {
            string elemento = txtdato.Text;
            int aux, lug = -999, lugp = 0, ptr;
            txtdato.Clear();
            if (Listas.comienzo == -999)
            {
                lug = -999;
                lugp = -999;
                MessageBox.Show("La lista esta vacia", "Error");
                return;
            }
            if (Listas.alumno[Listas.comienzo] == elemento)
            {
                lug = Listas.comienzo;
                lugp = -999;
                Listas.comienzo = Listas.enlace[Listas.comienzo];
            }
            else
            {
                aux = Listas.comienzo;
                ptr = Listas.enlace[Listas.comienzo];
                while (ptr != -999)
                {
                    if (Listas.alumno[ptr] == elemento) { lug = ptr; lugp = aux; }
                    aux = ptr; ptr = Listas.enlace[ptr];
                }
            }
            if (lug == -999) { MessageBox.Show("Elemento no encontrado", "Error", MessageBoxButtons.OK); return; }
            if (lugp == -999) { Listas.comienzo = Listas.enlace[Listas.comienzo]; }
            else { Listas.enlace[lugp] = Listas.enlace[lug]; }
            Listas.enlace[lug] = Listas.disponible; Listas.disponible = lug;
            MessageBox.Show("Elemento borrado", "Proceso Completado");
            button1.Text = "Cerrar";
        }
 
        private void button1_Click(object sender, EventArgs e)
        {
            this.Close();
        }
    }
}

Corrida

:estructura_datos_csharp:listas_eliminacion.jpg

Politica de Privacidad