C# BasicLinkedList: Listas enlazadas

Vamos a seguir desarrollando el post anterior (“C# Clases autorreferenciadas“) para generar una lista enlazada, una lista enlazada es una colección lineal o una secuencia de nodos representados con clases autorreferenciadas. El acceso a la lista se realiza desde el primero nodo (raíz o head) y se recorre accediendo al miembro que apunta al siguiente nodo y así hasta el final (el miembro del último nodo que apunta al siguiente se define como null para evitar errores). Normalmente las listas tienen las operaciones comunes para trabajar con sus nodos, vamos a definir métodos para:

  • Construir una lista vacía y darle un nombre.
  • Insertar un nodo en la cabecera.
  • Insertar un nodo al final.
  • Eliminar el primer nodo de la lista.
  • Eliminar un nodo del final de la lista.
  • Comprobar si una lista está vacía.
  • Imprimir por pantalla el contenido.
  • Obtener el número de elementos o nodos de la lista.

Clase para definir un nodo

Similar al ejemplo anterior definimos una clase que represente un nodo. Definimos dos constructores, el segundo permite crear un nodo y definir el nodo al que apunta como siguiente elemento en la lista.

Lo más remarcable de la clase es la referencia object. Nos permite almacenar tipos de datos simples como si fueran objetos. El tipo object es un alias para Object en .NET. Todos los tipos de variables son herencia directa de este tipo. Podemos asignar valores de cualquier tipo a variables de tipo object. Cuando una variable se convierte a un tipo object a esta operación se le llama boxing o boxed. Cuando se realiza la operación inversa se denomina unboxing.

Clase lista

La clase lista tiene contiene como miembros head y tail. Son respectivamente referencias al primer y último nodo de la lista, también definimos una variable string para asignar un nombre a la lista.

 

Definimos un método que nos resultará de utilidad más adelante, el método IsListEmpty retorna true si la cabeza de lista apunta a null.

Ahora definimos un método para operar sobre la lista insertando un nuevo nodo al inicio de la misma.  Si la lista esta recién creada o vacía la cabeza y la cola apunta al nuevo y único la misma. En caso contrario la cabeza apunta al nuevo nodo y le pasamos el nodo de cabeza actual como miembro para que quede en segundo lugar.

Para añadir un nodo al final definimos el siguiente método:

Antes de continuar con un método para borrar un elemento del inicio de la lista vamos a definir una clase EmptyListException para lanzar una excepción cuando se producen operaciones ilegales sobra la lista, por ejemplo si la lista está vacía. Usamos System.ApplicationException para excepciones generadas por nuestra programa.

Ahora ya podemos crear un método para borrar un elemento de la cabecera de la lista. Si la lista está vacía lanza una excepción que podemos capturar y tratar desde el programa principal. Después obtenemos el miembro del nodo de cabecera y restablece las referencias del primer y último nodo (si solo hay un nodo en la lista head y last quedaran a null, si hay más de un elemento avanzamos al siguiente nodo la cabecera).

Visto el anterior ejemplo borrar el último nodo es similar. Pero en este caso el método que debemos seguir  nodo no es muy eficiente (esto se solucionaría con una lista doblemente enlazada). Recorremos desde el primero nodo uno de detrás de otro hasta que el nodo siguiente no sea el último, de esta manera hacemos que apunte a null quedando fuera el último nodo.

Ahora solo nos queda un método para imprimir los nodos de la lista.

Ahora veamos como se puede utilizar:

Referencias externas

 

Anuncios

C# Clases autorreferenciadas

Una clase autorreferenciada es muy común para almacenar datos de forma dinámica y consumirlos a medida que los necesitamos en otro proceso, una clase autorreferenciada contiene un miembro de la clase que hace referencia a un objeto del mismo tipo. La unión de las clases referenciadas crea una lista de nodos que podemos recorrer accediendo de forma sucesiva desde el nodo raíz  al miembro del nodo que apunta al siguiente y así sucesivamente.

El ejemplo de abajo es como se organiza un array bidimensional en memoria, realmente se reservan zonas de memoria contiguas como en un array de una dimensión.

Frente a un array estático (los elementos se organizan en memoria de forma contigua y su tamaño se reserva en la declaración de la variable)  con un número de elementos determinados tiene una importante ventaja, una lista basada en nodos autoenlazados puede modificar su tamaño de forma dinámica en tiempo de ejecución (aunque también tiene un coste computacional que puede afectar al rendimiento de nuestro programa el manejo de grandes estructuras de memoria que reservan y liberan memoria según su necesidad).

El ejemplo de arriba es un ejemplo muy básico de un clase autorreferenciada, por supuesto los nodos pueden contener todos los datos que necesitemos de cualquier tipo.

Para ir añadiendo nuevos nodos durante la ejecución de nuestro programa haremos uso de la reserva de memoria dinámica con el operador new, este operador recibe como operando el tipo de objeto que se asignará de forma dinámica y devuelve una referencia a un objeto de este tipo.

Basándonos en esta arquitectura podemos crear listas enlazadas, colas o arboles. Cada tipo de estructura tiene propósitos diferentes y puede ser aplicado según el problema que debamos resolver.

 

 

C# ClassConstructor: Notas sobre constructores

Aquí van algunos ejemplos más avanzados con breves anotaciones sobre constructores de clases.

Los constructores son métodos especiales que se invocan cuando se instancia una clase, un método constructor nunca debe retornar nada (no es necesario definir el tipo de retorno en su declaración). Siempre que en una clase e define explicitamente un constructor el constructor por omisión o implícito es reemplazado por este.

El operador new crea un objeto nuevo y a continuación se invoca al constructor de la clase.

Constructor sobrercargadado

El método constructor también puede ser sobrecargado con varios métodos, con el mismo nombre (el de la clase) pero con diferentes parámetros:

c1

Llamadas entre constructores

A pesar de que pueda parece raro un constructor puede llamar a otro también. En el siguiente ejemplo primero se llama al constructor sin parámetros. Podemos usarlo para instanciar objetos comunes en el constructor sin parámetros y llamarlo desde constructores que aceptan diferentes tipos de inicializaciones especificas,

c2

Uso de la clase clsCamion:

c3

c4

También podemos pasar parámetros de un constructor a otro:

c5

 

Destructores

C# tiene un recolector de basura, el propio framework se ocupa de liberar los objetos que ya no usamos. En algunos casos tal vez no interese realizar una “limpieza” manual, para la clase clsCamion de arriba tendría el siguiente aspecto:

c6

Constructor de la clase base

Usando la palabra clave base podemos invocar el constructor de la clase base cuando usamos la herencia.

c7

 

 

Entradas relacionadas (clases):

Enlaces externos:

C# GetSetAccessDesc: Ejemplos descriptores de acceso con get/set

Algunos ejercicios básicos para entrenar con los descriptores de acceso get y set. Algunos usos que se me ocurren para get/set son: Validar los datos antes de permitir un cambio, obtener datos de otro origen de forma transparente (una base de datos por ejemplo), realizar una acción cuando se modifican datos (provocar un evento o cambiar el valor de otros campos relacionados).

clsDate: Control asignación de valores mediante set

En este ejemplo Month se declara como propiedad para asegurarnos que se establece un valor correcto para el mes comprendido entre 1 y 12.

getset1

Si por ejemplo tratamos de establecer un mes 15 no da error pero el valor no se establece y se mantiene a 0 (valor por defecto).

getset2

clsPerson: Descriptor acceso sólo get

El descriptor de acceso get debe devolver el valor de la propiedad, si solo definimos get la propiedad será solo de lectura, si intentamos modificar su valor el compilador no lo permitirá.

getset3

Uso de la clase clsPerson:

getset4

Cuando llamamos a Console.WriteLine entra en acción el descriptor get.

clsTrabajador: get para controlar si un campo es consistente

Podemos usar el descriptor de acceso get para devolver el valor de un campo haciéndolo consistente, en este caso empleamos un operador condicional ternario para comprobar si la cadena es null, en ese caso retornamos una cadena “NA” para indicar que el valor no se ha inicializado correctamente aún.

getset5

Entradas relacionadas:

C# Caja: Ejercicio con indexadores

En la entrada “C# class LibroCalificaciones: Acceso a propiedades con descriptores de acceso get / set” se estudio como se pueden emplear los descriptores de acceso get/set para controlar el acceso a los datos privados de una clase, por ejemplo:

idx1

Dentro de una clase podemos almacenar listas de datos  en arrays pòr ejemplo, podemos acceder a estos miembros usando indexadores, estos permiten el acceso indexado a las listas de elementos usando su índice numérico o usando un índice basado en nombres.

modificadorAcceso tipoRetorno this[ TipoIndice1 nombre1, TipoIndice2 nombre2, ...]
{
    get
    {
          // usa nombre1, nombre2...para acceder a datos
    }
    set
    {
          // usa nombre1, nombre2...para acceder a datos
    }
}

Vamos a demostrar su uso con una clase llamada clsCaja que contiene un array con 3 miembros privados de tipo double con las propiedades longitud, altura, anchura. Para poder indexar por nombre del atributo al array de doubles también definiremos un arreglo de string con los nombres de las propiedades.

idx2

Ahora siguiendo la sintaxis de arriba vamos a definir dos indexadores, el primero más sencillo de entender permite acceder a los elementos del arreglo usando un índice numérico de tipo int.

idx5

El segundo indexador utiliza un índice string que representa el nombre de la medida que queremos obtener (“longitud”,”altura”,”anchura”).

Cada indexador devuelve -1 si su descriptor de acceso get detecta un subíndice no valido. Lo mismo hace set set si tratamos de establecer un elemento no valido.

idx6

Ahora ya podemos usar los indexadores:

idx7

Entradas relacionadas:

Ejercicio completo


/*
* Created by SharpDevelop.
* User: i.landajuela
* Date: 21/12/2016
* Time: 18:34
*
* To change this template use Tools | Options | Coding | Edit Standard Headers.
*/
using System;

namespace Indexadores
{

//Ejemplo de uso de descriptores de acceso get/set para controlar
//el acceso a miembros privados de la clase
class TimePeriod
{
private double _seconds;
public double Seconds
{
get { return _seconds; }
set { _seconds = value; }
}
}

//-----------------------------------------------------------------

public class clsCaja
{
private string[] nombres = {"longitud","altura","anchura"};
private double[] medidas = new double[3];

public clsCaja(double longitud, double anchura, double altura)
{
medidas[0]=longitud;
medidas[1]=anchura;
medidas[2]=altura;
}

//indexador para acceder a medidas por el número de indice entero
public double this[int indice]
{
get
{
//valida indice a obtener
if ((indice<0) || (indice >= medidas.Length))
{
return -1;
}
else
return medidas[indice];
} //fin get
set
{
if (indice>=0 && indice < medidas.Length)
medidas[indice] = value;
} //fin set

} // fin de indexador numérico

public double this[string nombre]
{
get
{
//localiza elemento a obtener
int i=0;
while((i<nombres.Length)&&(nombre!=nombres[i]))
i++;
return (i==nombres.Length) ? -1 : medidas[i];
}
set
{
int i=0;
while((i<nombres.Length)&&(nombre!=nombres[i]))
i++;
if(i!=nombres.Length)
medidas[i] =value;
}
} //fin de indexador string

}


class Program
{
public static void Main(string[] args)
{
clsCaja objCaja = new clsCaja(10,20,30);


objCaja[0] = 80;
Console.WriteLine("caja[\"longitud\"]={0}",objCaja["longitud"]);
objCaja["longitud"] = 90;
Console.WriteLine("caja[\"longitud\"]={0}",objCaja["longitud"]);

Console.Write("Press any key to continue . . . ");
Console.ReadKey(true);
}
}
}

C# PruebaThis: Referencia a los miembros del objeto actual con “this”

Los objetos pueden acceder a una referencia a si mismo usando la palabra clave this. Hace referencia a la instancia actual de la clase. Puede ser usado con el fin de evitar ambigüedades como en este ejemplo:

t1

El constructor de la clase TiempoSimple recibe tres argumentos int para inicializar el objeto. En el constructor usamos nombres de parámetros de entrada idénticos a los nombres de las variables de instancia de la clase (hora,minuto,segundo). Usando this podemos diferenciar entre unas y otras.

El método público y accesible por el cliente  CrearString devuelve un objeto string creado usando la referencias this de forma explícita e implícita.

t2

Ahora vemos como podemos usar la clase, creamos una instancia de la clase  TiempoSimple y invocamos a su constructor.  Luego invocamos al método CrearString del objeto y muestra los resultados en pantalla.

t3

Ejemplo completo:


 /*
  * Created by SharpDevelop.
  * User: i.landajuela
  * Date: 20/12/2016
  * Time: 17:15
  * 
  * To change this template use Tools | Options | Coding | Edit Standard Headers.
  */
 using System;
 
 namespace PruebaThis
 {
     
     public class TiempoSimple
     {
         private int hora=0,minuto=0,segundo=0;
         
         public TiempoSimple(int hora,int minuto, int segundo)
         {
             this.hora = hora;
             this.minuto = minuto;
             this.segundo = segundo;
         }
         
         public string CrearString()
         {
             return string.Format("{0:24}: {1}\n{2,24}: {3}",
                                  "this.AStringUniversal()",this.AStringUniversal(),
                                  "AStringUniversal()",AStringUniversal());
         }
         
         public string AStringUniversal()
         {
             return string.Format("{0:D2}:{1:D2}:{2:D2}",
                                 this.hora,this.minuto,this.segundo);
         }
 
     }
     
     class Program
     {
         public static void Main(string[] args)
         {
             TiempoSimple objT1 = new TiempoSimple(23,24,12);
             
             Console.WriteLine(objT1.CrearString());
                         
             Console.Write("Press any key to continue . . . ");
             Console.ReadKey(true);
         }
     }
 }