normalista: febrero 2008

COMPLEJIDAD DE ALGORITMOS
Un programa, por muy correcta que sea su implementación, puede no ser viable(debido al tiempo que necesita para ejecutarse o por la cantidad de espacio que necesita) para algunos tipos de entrada. Cuando realizamos el análisis de un algoritmo nos refermios al proceso de estimación del tiempo y espacio necesarios para ejecutar el algoritmo. La complejidad de un algoritmo hace referencia a la cantidad de tiempo y espacio necesarios para ejecutar el algoritmo. Con la tecnología actual podemos decir que la memoria de las computadoras es abundante y barata, es por eso la complejidad del algoritmo se puede limitar al tiempo de ejecución del algoritmo.
El tiempo de ejecución dependerá del programa y de su entrada (carga de trabajo ).
Un algoritmo será más eficiente comparado con otro, siempre que consuma menos recursos, como el tiempo y espacio de memoria necesarios para ejecutarlo.
La eficiencia en memoria de un algoritmo indica la cantidad de espacio requerido para ejecutar el algoritmo, es decir, el espacio en memoria que ocupan todas las variables propias del algoritmo.

INTRODUCCION

La eficiencia de un algoritmo está dada por el análisis del mismo, basándose en la dimensión temporal( tiempo empleado) y la dimensión espacial (recursos invertidos). Una buena estimación de la eficiencia debe ser independiente de aspectos de implementación (la plataforma y el lenguaje con que se codificará) pero debe reflejar sus diferencias.
La gran mayoría de los problemas tiene un parámetro de entrada que es el número de datos que se van a procesar, denominado comúnmente como N. La cantidad de recursos del algoritmo es tratada como una función de N.
Así, se establece un tiempo de ejecución del algoritmo que por lo general es proporcional a una de las siguientes funciones :

O (l) orden constante : La mayoría de las instrucciones se ejecutan muy pocas veces.
O (log n) orden logarítmico : Se puede considerar como una gran constante.
O (n) orden lineal : Tiempo de ejecución lineal (un ejemplo sería un algoritmo que lee N números enteros y devuelve la media aritmética.
O (nlog n) orden de nlogn : Si N se duplica el tiempo de ejecución es ligeramente mayor del doble. Un ejemplo de este algoritmo sería la búsqueda binaria ó dicotómica.
O (n2) Tiempo de ejecución cuadrático. Si n se duplica el tiempo de ejecución aumenta cuatro veces.
O (n3) Tiempo de ejecución cúbico. Si n se duplica el tiempo de ejecución aumenta ocho veces.

Los algoritmos de complejidad O (n) y O (n log n) son los que tienen un comportamiento más natural. prácticamente a doble de tiempo, doble de datos procesables.
Los algoritmos de complejidad logarítmica son un descubrimiento fenomenal, ya que en el doble de tiempo permiten resolver problemas mayores, y para resolver un problema el doble de grande sólo hace falta un poco más de tiempo (no muy significativo).

falta complpejidad

tiempo de ejecucion de un algoritmo dimensión temporal
Se refiere a la medida del tiempo empleado. El tiempo de ejecución dependerá del programa y de su entrada (carga de trabajo).
El tiempo total para una función se puede determinar por el tiempo requerido para cada instrucción, multiplicado por las veces que se ejecutan.
Teniendo el siguiente código :

i=0
Mientras i <>

El tiempo requerido para ejecutarse sería T(n) = t1+n*t2+n*t3+t4

1.3.2 Complejidad en espacio.dimensión espacial
Se refiere a la medida de los recursos invertidos. Al hablar de complejidad en espacio se hace referencia a la memoria que utiliza un programa para su ejecución. La eficiencia de la memoria de un algoritmo indica la cantidad de espacio requerido para ejecutar el algoritmo, es decir, el espacio en memoria que ocupan todas las variables propias del algoritmo.
La cantidad de memoria necesaria para llegar a la solución del problema considera lo siguiente :

Si tenemos el código :

Mientras i <>falta 1.4 Selección de un algoritmo

2.1 Manejo de memoria estáticaINTRODUCCIÓN

Al hablar de manejo de memoria nos referimos a la forma en la que se trabaja con este recurso, al implementar estructuras de datos. Podemos hablar de memoria estática y memoria dinámica.
Empezaremos por definir el concepto de estructuras de datos

a) Es la forma en que están relacionados objetos de datos o datos complejos.

b) Es una clase de datos que puede ser caracterizada por su organización y por las operaciones susceptibles de realizar con tales datos.

Las Estructuras de Datos son muy importantes en los sistemas de computadora, contienen los tipos de datos más frecuentes utilizados en los diferentes lenguajes de programación.

Se pueden definir los tipos de datos como simples y estructurados. Los datos simples o primitivos son los que no están compuestos de otras estructuras, por ejemplo :

Entero

Real

Carácter

Lógico

Los datos Estructurados o compuestos (están construidos basados en tipos de datos primitivos por ejemplo cadena "string" varios caracteres) .

Estáticos

Arreglos

Registros

Archivo

Cadena

Dinámicos

Listas

Pilas

Colas

Arboles

Grafos

Los tipos de datos simples pueden ser organizados en diferentes estructuras de datos : Estáticos y Dinámicos.

Las Estructuras de datos Estáticos son aquéllas en las que el tamaño ocupado en memoria se define antes de que el programa se ejecute y no pude modificarse dicho tamaño durante la ejecución del programa.

Las Estructuras de datos Dinámicas no tienen las limitaciones o restricciones en el tamaño de memoria ocupada que son propias de las estructuras estáticas. Mediante el uso de un tipo de datos específico denominado puntero, es posible construir estructuras de datos dinámicas que son soportadas por la mayoría de los lenguajes.

La elección del tipo de estructura de datos idónea a cada aplicación dependerá esencialmente del tipo de aplicación y en menor medida del lenguaje.

Característica que diferencia a los tipos de datos:
Los tipos de datos simples tienen como característica común que cada variable representa a un elemento. Los tipos de datos estructurados tienen como característica común que un identificador (nombre) puede representar múltiples datos individuales, pudiendo ser cada uno referenciado independientemente.

Las Estructuras dinámicas de datos se utilizan para almacenamiento de datos del mundo real,

que están cambiando constantemente. Son extremadamente flexibles y relativamente fáciles de modificar.

Las Estructuras dinámicas lineales de datos, son listas secuenciales, están dispuestas de modo que es necesario moverse a través de ellas una posición cada vez ( c/ elemento tiene un siguiente elemento ) .

Para manipular estructuras de datos se requieren algoritmos que ejecuten tareas fundamentales, estas tareas reciben el nombre de funciones:

* Funciones Constructoras
* Funciones para acceso
* Funciones destructuras

Funciones Constructoras

Se encargan de crear la estructura, es decir, definen las características, la delimitación, las relaciones y asignan el espacio correspondiente, dejando al usuario la estructura lista para que pueda colocar la información. Por ejemplo la creación de un archivo, bases de datos, etc.

Funciones para acceso

Facilitan la forma de llegar a un elemento perteneciente a la estructura. La función puede ser simple o compleja dependiendo del tipo de estructura de datos. Se puede considerar una forma de acceso directo cuando a través de una dirección o un parámetro se trata de encontrar el valor correspondiente. Esta función es la base para desarrollar operaciones sobra la estructura, ya que es la que permite navegar en ella.

Funciones Destructoras

Se encargan de devolver al sistema los recursos asignados a la estructura de datos para que queden a disposición de éste. Esta forma es la más utilizada y normalmente no es necesario efectuar ninguna operación sobre la estructura; pues queda automáticamente liberado el espacio que ocupaba.

Operaciones más comunes sobre una Estructura de Datos

*Navegar: Se utiliza este término para significar el recorrido por la estructura, esta es una operación básica.

*Búsqueda: Permite determinar si un elemento se encuentra o no en la estructura.

Consulta: Permite obtener información de uno o más elementos de la Estructura de Datos.

Copia: Es aquella mediante la cual se puede obtener total o parcialmente una estructura con características similares a la original.

Modificación: Permite cambiar total o parcialmente el contenido de uno o varios elementos contenidos en la estructura.

Inserción: Es aquella operación en la cual se agrega un nuevo elemento en la estructura .

Eliminación: Permite suprimir elementos en una estructura.

Estructuras de Datos

Desde el punto de vista Físico : Se enfoca básicamente a como queda almacenada la información, por lo que en gran parte depende del medio de almacenamiento.Al principio cuando teníamos almacenamiento únicamente secuencial la estructura física coincidía con la estructura lógica.

Desde el punto de vista Lógico : Es la apariencia que presentan los datos para el usuario. Es la forma en la que uno como programador establece las relaciones que existen entre los elementos debido a la información que contiene.

falta 2.2 Manejo de memoria dinámica.

3.1 PilasEstucturas de datos tipo pila

Una pila es una lista de elementos a la cual se le puede insertar o eliminar elementos sólo por un extremo. La filosofía que maneja una pila es "El último en entrar es el primero en salir". Ejemplos de pilas en el mundo real serían : pila de platos, pila de latas en un supermercado, pilas de cuadernos, pilas de ropa etc.

Estas estructuras se pueden representar a través de :

*Arreglos
* Listas

Al implementar una pila utilizando arreglos se maneja una variable auxiliar denominada TOPE, que se utiliza para indicar el último elemento que se insertó o se eliminó de la pila.
Las operaciones elementales que se pueden realizar en una pila son:

Poner un elemento (Push)
Quitar un elemento (Pop)

El algoritmo para poner un elemento en una pila considerando que tenemos un arreglo de un tamaño N y manejamos la variable tope sería el siguiente :
Si TOPE <> 0
Hacer DATO <- PILA[TOPE]

TOPE <- TOPE -1

sino

Escribir " No existen elementos en la pila"

Fin Si

Aplicaciones de las pilas

Las pilas son estructuras de datos muy utilizadas en la solución de diversos problemas computacionales. Algunos ejemplos son :

Llamadas a subprogramas

Recursión

Tratamiento de expresiones artiméticas

Ordenación

Llamadas a subprogramas : Cuando en un programa se llama a un subprograma se usan pilas internamente para guardar el estado de las variables del programa en el momento que se hace la llamada, esto con el propósito de recuperar los valores almacenados para continuar con la ejecución del programa en el punto en el que se quedó al momento de llamar al subprograma, también se guarda la dirección del programa en la que se hizo la llamada para regresar el control al programa original.

Recursión : aquí se almacenan temporalmente los valores de las variables (resultados parciales) en una pila, hasta llegar al resultado final.

La recursión permite definir un objeto en términos de sí mismo. Casos típicos de estas estructuras de datos definidas de manera recursiva son los árboles y las listas ligadas.

Existe la recursión de dos maneras :

Directa : el subprograma se llama directamente a sí mismo.

Indirecta : Se da cuando un subprograma llama a otro programa y éste a su vez llama al primero. En toda definición recursiva de un problema se debe establecer un estado básico. Es decir un estado en el cual la solución no se presente de manera recursiva sino directamente.

Subprograma P

En toda definición recursiva de un problema se debe establecer un estado básico. Es decir un estado en el cual la solución no se presente de manera recursiva sino directamente. Además la entrada (datos) del problema debe ir acercándose al estado básico.

Si dado un problema es posible determinar el estado básico entonces se puede llegar a una solución, de otra forma estaríamos frente a una definición circular del problema.

Ejemplos de funciones recursivas son : el cálculo de factorial, serie fibonacci.

Tratamiento de expresiones aritméticas : Se utiliza para hacer conversiones de notación infija a prefija o postfija, manejando pilas para ir almacenando los distintos operadores y operandos hasta realizar la conversión.

Poder convertir expresiones en notación infija a su equivalente en notación postfija(o prefija).

*Dada la expresión A + B notación infija

*AB+ notación postfija

* +AB notación prefija

La ventaja de usar expresiones en notación polaca en postfija o prefija radica en que no son necesarios los paréntesis para indicar el orden de operación, ya que éste queda establecido por la ubicación de los operadores con respecto a los operandos.

Se utilizan sólo los operadores

Potencia

*/ multiplicación y division

+- suma y resta

*Los operadores de más alta prioridad se ejecutan primero.

*Si hubiera en una expresión dos o más operadores de igual prioridad , entonces se procesarán de izquierda a derecha.

*Las subexpresiones parentizadas tendrán más prioridad que cualquier operador.

Ordenación : Temporalmente se utiliza para almacenar los elementos a ordenar.

3.2 Colas

Estucturas de datos tipo cola

Una cola es una lista de elementos en la que éstos se introducen por un extremo y eliminan por el otro. Los elementos se eliminan en el mismo orden en el que se insertaron. Por lo tanto el primer elemento que entra a la cola será el primero en salir. Debido a esta característica, las colas también reciben el nombre de estructuras FIFO (First-In, First-Out: primero en entrar, primero en salir).

Existen numerosos casos de colas en la vida real : las personas esperando para usar un teléfono público, un cajero automático, los carros esperando la luz verde, los niños esperando para subir a un juego mecánico, etc.

Representación de colas

Arreglos

Listas Enlazadas.

Como en el caso de las pilas también se utilizarán arreglos. Debe definirse un tamaño máximo para la cola y dos variables auxiliares. Una de ellas para que guarde la posición del primer elemento de la cola (FRENTE) y otra para que guarde la posición del último elemento de la cola (FINAL).

Tipos

Colas Simples

Colas Circulares

Colas Dobles

Colas Simples

Es una lista de elementos en la que éstos se introducen por un extremo y eliminan por el otro

Cola

MAX
		...
		...
		...
FINAL	4	444
	3	333
	2	222
FRENTE	1	111

Cola Llena

FINAL y MAX		999
		...
		...
		...
	4	444
	3	333
	2	222
FRENTE	1	111

Cola con algunos elementos

MAX		999
		...
		...
		...
	4
FINAL	3	333
	2	222
FRENTE	1	111

Cola vacía

MAX



	4
	3
	2
	1

FRENTE Y FINAL = 0

Operaciones con Colas

Insertar un elemento

Eliminar u n elemento

Las inserciones se llevarán a cabo por el FINAL de la cola, mientras que las eliminaciones se harán por el FRENTE (recuerde que el primero en entrar es el primero en salir).

Considerando que una cola puede almacenar un máximo número de elementos y que además la posición del primer elemento está almacenada en FRENTE y la posición del último en FINAL, se presentan ahora los algoritmos de inserción y eliminación en colas.

INSERTACOLA ( COLA, MAX, FRENTE, FINAL, DATO)

1. Si FINAL< MAX

entonces

Hacer FINAL=FINAL+1

COLA[FINAL]=DATO

1.1 Si FINAL=1 entonces

Hacer FRENTE=1

1.2 Fin del paso 1.1

Si no

Escribir "Desbordamiento"

2. Fin del paso 1

ELIMINACOLA ( COLA, FRENTE, FINAL, DATO)

1. Si FRENTE<>0

entonces

Hacer DATO=COLA[FRENTE]

COLA[FRENTE]=0

1.1 Si FRENTE=FINAL entonces

Hacer FRENTE=0

FINAL=0

si no

Hacer FRENTE=FRENTE+1

1.2 Fin del paso 1.1

Si no

Escribir "Subdesbordamiento"

2. Fin del paso 1

Ejemplo

Se insertan en COLA los elementos: lunes, martes, miércoles, jueves y viernes ( en ese orden ), de modo que la estructura queda como se muestra en la figura:

Cola

MAX	7
	6
FINAL	5	viernes
	4	jueves
	3	miércoles
	2	martes
FRENTE	1	lunes

Se elimina "lunes"

Cola

MAX	7
	6
FINAL	5	viernes
	4	jueves
	3	miércoles
FRENTE	2	martes
	1

Se inserta "Sábado"

Cola

MAX	7
FINAL	6	sábado
	5	viernes
	4	jueves
	3	miércoles
FRENTE	2	martes
	1

Se eliminan "martes","miércoles","jueves","viernes"

Cola

MAX	7
FRENTE Y FINAL	6	sábado
	5
	4
	3
	2
	1

Se inserta "domingo"

Cola

FINAL	7	domingo
FRENTE	6	sábado
	5
	4
	3
	2
	1

Se elimina "sábado"

Cola

FINAL y FRENTE	7	domingo
	6
	5
	4
	3
	2
	1

Si se quisiera insertar un nuevo elemento ya no se podría, puesto que FINAL no es menor que MAX (FINAL=MAX=7). Sin embargo, como se ve en la última fig. hay espacio disponible.

Se llego a una situación conflictiva: a pesar de que hay espacio, no se pueden insertar otros elementos. Este incoveniente puede superarse manejando las colas como se muestran en el sig. punto.

Colas circulares

Para hacer un uso más eficiente de la memoria disponible se trata a la cola como a una estructura circular. Es decir, el elemento anterior al primero es el último.

COLA CIRCULAR

Fig. 1

	XX	YY	ZZ	KK	TT	WW	RR
1	2	3	4	5	6	7	8
	FRENTE						FINAL

COLA CIRCULAR

Fig. 2

			ZZ	KK	TT	WW	RR
1	2	3	4	5	6	7	8
			FRENTE				FINAL

COLA CIRCULAR

Fig. 3

PP			ZZ	KK	TT	WW	RR
1	2	3	4	5	6	7	8
FINAL			FRENTE

En las fig. 1 se ilustran como se actualizan los punteros FRENTE y FINAL en una cola circular, a medida que se insertan o eliminan elementos. La cola tiene algunos elementos (FRENTE=2 y FINAL=8). En la fig. 2 se han eliminado de la cola dos elementos (primero se quito XX y luego YY), quedando FRENTE=4. Por último, en la fig. 3 se ha insertado un nuevo elemento (PP) en la cola. Como FINAL= MAX se llevó el apuntador a la primera posición que estaba vacía ( FINAL = 1 ). De esta manera se logra un mejor aprovechamiento del espacio de memoria disponible, ya que al eliminar un elemento esa casilla de la cola queda disponible para futuras inserciones.

Algoritmo INSERTACIRCULAR

Insertacircular ( COLACIR, MAX, FRENTE, FINAL, DATO )

1. Si ((FINAL= MAX) y (FRENTE =1)) o ((FINAL+1)=FRENTE)

entonces

Escribir 'Desbordamiento' {La Cola está Llena}

Si no

1.1 Si FINAL=MAX

entonces

Hacer FINAL = 1

Si no

Hacer FINAL=FINAL+1

1.2 {Fin del condicional del paso 1.1

Leer DATO

COLACIR[FINAL]=DATO

1.3 Si FRENTE=0 entonces

Hacer FRENTE=1

1.4 {Fin del condicional del paso 1.3}

2. {Fin del condicional del paso 1}

Algoritmo ELIMINACIRCULAR

Eliminacircular ( COLACIR, MAX, FRENTE, FINAL, DATO )

1. Si FRENTE=0 {Verifica si la cola está vacía }

entonces

Escribir 'Subdesbordamiento'

Si no

Hacer DATO=COLACIR[FRENTE]

COLACIR[FRENTE]=0

1.1 Si FRENTE=FINAL {Si hay un sólo elemento}

entonces

Hacer FRENTE=0 y FINAL=0

Si no

1.1.1 Si FRENTE = MAX

entonces

Hacer FRENTE=1

si no

Hacer FRENTE=FRENTE+1

1.1.2 {Fin del condicional del paso 1.1.1}

1.2 {Fin del condicional del paso 1.1}

2. {Fin del condicional del paso 1 }

Doble Cola

Una doble cola o bicola es una generalización de una estructura de cola simple. En una doble cola, los elementos pueden ser insertados o eliminados por cualquiera de los extremos. Es decir, se pueden insertar y eliminar valores tanto por el FRENTE como por el FINAL de la cola. Una doble cola se representa como se muestra en la fig.

TEX1

Las dos flechas en cada extremo indican que pueden ejecutarse las operaciones de inserción y eliminación.

Existen dos variantes de las dobles colas:

Doble cola con entrada restringida

Doble cola con salida restringida

La primera de ellas permite que las eliminaciones puedan hacerse por cualquiera de los dos extremos, mientras que las inserciones sólo por el final de la cola

tex2

La segunda variante permite que las inserciones puedan hacerse por cualquiera de los dos extremos, mientras que las eliminaciones sólo por el FRENTE de la cola.

tex3

Aplicaciones de colas

El concepto de cola está ligado a computación. Una aplicación de las colas puede verse en las colas de impresión. Cuando hay una sola impresora para atender a varios usuarios, puede suceder que algunos de ellos soliciten servicios de impresión al mismo tiempo o mientras el dispositivo está ocupado. En estos casos se forma una cola con los trabajos que esperan para ser impresos. Los mismos se irán imprimiendo en el orden en el cual fueron introducidos en la cola.

Otra aplicación sería el uso de colas en sistemas multiusuario y en sistemas de tiempo compartido.

3.3 Listas enlazadas.

Estucturas de datos tipo LISTA

Este tipo de estructura de datos dinámica está compuesta por un conjunto de nodos, generados a partir de un tipo de dato conocido con el nombre de puntero o de referencia. Un dato puntero almacena una dirección o referencia a un dato propiamente dicho. Por lo tanto, debe distinguirse claramente entre un dato puntero y el dato al cual éste apunta.

Se usará la notación P=^D para indicar que P es un puntero a datos de tipo D. Se genera un valor para una variable de tipo puntero cuando se asigna, dinámicamente, memoria a un dato apuntado por ella. Se usuará CREA(P) para indicar el proceso de asignación de memoria, y QUITA (P) para indicar el proceso inverso, es decir, cuando se libera una posición de memoria apuntada por P.

De esta manera se pueden crear estructuras dinámicas que se expandan o se contraigan, según se les agregue o elimine elementos.

Las variantes de listas se pueden clasificar como sigue:

Listas Simples

Una lista es una colección de elementos llamados generalmente nodos. El orden entre los nodos se establece por medio de punteros, es decir, direcciones o referencias a otros nodos.

INFORMACION

LIGA

En general, un nodo consta de dos partes:

Un campo INFORMACION que será del tipo de datos que se quiera almacenar en la lista.

Un campo LIGA, de tipo puntero, que se utiliza para establecer la liga o el enlace con otro nodo de la lista. Si el nodo fuera el último de la lista, este campo tendra un valor NULL ( vacío ). Al emplearse el campo liga para relacionar dos nodos no será necesario almacenar físicamente a los nodos en espacios contiguos.

Ejemplo de una lista simple :

LISTA APELLIDOS

Las operaciones que se realizan con listas son:

Recorrido de la Lista

Inserción de un Elemento

Borrado de un Elemento

Búsqueda de un Elemento

Para realizar las operaciones anteriores debemos de crear la lista, a continuación se detalla el algoritmo para crear una lista al inicio

CREAINICIO(P)

{Este algoritmo crea una lista, agregando cada nuevo nodo al inicio de la misma}

{P y Q son variables de tipo puntero. P apuntará al inicio de la lista}

1.- CREA (P) {Crea el primer nodo de la lista}

2.- LEER P^.INFORMACION

3. HACER P^.LIGA<- NULL

4. REPETIR

CREA (Q)

LEER Q^.INFORMACION

HACER Q^.LIGA<- P y P<-Q

5. HASTA (que no haya información)

En java el código para crear al inicio sería algo así :

class nodo

{

int info;

nodo liga;

}

class creainicio

{

static nodo Q=null;

static nodo P=null;

public static void creaininodo()

{

int opc=1;

int dato;

if (P==null)

{

P=new nodo();

System.out.println("Dame Dato: ");

dato=TextIO.getlnInt();

P.info=dato;

P.liga=null;

}

do{

Q=new nodo();

System.out.println("Dame Dato: ");

dato=TextIO.getlnInt();

Q.info=dato;

Q.liga=P;

P=Q;

System.out.println("Otro nodo 1(SI) 2 (NO)");

opc=TextIO.getlnInt();

}while (opc!=2);

System.out.println("La Lista Creada es: ");

for (nodo i=P; i!=null; i=i.liga)

System.out.println("Campo Informacion: "+i.info+" Campo Liga: "+ i.liga);

}

public static void main (String args[])

{

System.out.println("Programa que Crea Inicio de Lista");

creaininodo();

System.out.println("Termina Programa que Crea Inicio de Lista");

}

}

CREAFINAL(P)

{Este algortimo crea una lista, agregando cada nuevo nodo al final de la misma}

{P y Q son variables de tipo puntero, P apuntará al inicio de la lista }

1.- CREA (P) { Crea el primer nodo de la lista}

2.- LEER P^.INFORMACION

3.- HACER P^.LIGA<- NULL y T <- P

4.- REPETIR

CREA (Q)

LEER Q^.INFORMACION

HACER Q^.LIGA <- NULL, T^.LIGA <- Q y T<- Q

5. HASTA (que no haya información)

En java el programa para crear al final sería :

class nodo

{

int info;

nodo liga;

}

class creafinal

{

static nodo Q=null;

static nodo P=null;

static nodo T=null;

public static void creafinnodo()

{

int opc=1;

int dato;

if (P==null)

{

P=new nodo();

System.out.println("Dame Dato: ");

dato=TextIO.getlnInt();

P.info=dato;

P.liga=null;

T=P;

}

do{

Q=new nodo();

System.out.println("Dame Dato: ");

dato=TextIO.getlnInt();

Q.info=dato;

Q.liga=null;

T.liga=Q;

T=Q;

System.out.println("Otro nodo 1(SI) 2 (NO)");

opc=TextIO.getlnInt();

}while (opc!=2);

System.out.println("La Lista Creada es: ");

for (nodo i=P; i!=null; i=i.liga)

System.out.println("Campo Informacion: "+i.info+" Campo Liga: "+ i.liga);

}

public static void main (String args[])

{

System.out.println("Programa que Crea final de Lista");

creafinnodo();

System.out.println("Termina Programa que Crea final de Lista");

}

}

El algoritmo requiere de otra variable puntero para mantener la dirección del último nodo de la lista, de tal manera que se pueda establecer el enlace entre éste y el nuevo nodo.

Recorrido de la lista

La operación de recorrido consiste en visitar cada uno de los nodos que forman la lista. La visita de un nodo puede definirse por medio de una operación muy simple ( por ejemplo la impresión de la información del mismo), o por medio de operaciones tan complejas como se desee.

Para recorrer todos los nodos de una lista se comienza con el primero. Tomando el valor del campo LIGA de éste se avanza al segundo; a su vez, el campo LIGA del segundo nos dará acceso al tercero y así sucesivamente. En general la dirección de un nodo, excepto el primero, está dada por el campo LIGA de su predecesor.

El algoritmo para recorrer la lista se puede hacer de forma iterativa o de forma recursiva.

RECORREITERATIVO(P)

{ Este algortimo recorre una lista cuyo primer nodo está apuntado por P }

{ Q es una variable de tipo puntero }

1.- HACER Q <- P

2.- REPETIR MIENTRAS Q<>NULL

ESCRIBIR Q^.INFORMACION

HACER Q <- Q^.LIGA {Apunta al siguiente nodo de la lista}

3. {FIN DEL CICLO DEL PASO 2}

Como las listas son estructuras de datos recursivas, pueden manejarse fácilmente con procesos recursivos.

RECORRERECURSIVO(P)

{ Este algortimo recorre una lista recursivamente. P es el apuntador al nodo a visitar}

1.- SI P<>NULL entonces

ESCRIBIR P^.INFORMACION

LLAMAR A RECORRERECURSIVO con P^.LIGA

{LLamada recursiva con el apuntador al siguiente nodo de la lista}

2. {FIN DEL CICLO DEL PASO 1}

Inserción de un elemento

La operación de inserción consiste en agregar un nuevo nodo a la lista. No se considerará el caso de lista vacía, sino que se supondrá que la lista en la cual se va a insertar el nuevo nodo ya existe. Se puede presentar tres casos en la operación de inserción:

Insertar un nodo al inicio de la lista

Insertar un nodo al final de la lista

Insertar un nodo antes/depués que otro.

a) INSERCION AL INICIO DE LA LISTA

El nuevo nodo se coloca al principio de la lista, convirtiéndose en el primero de la misma. El proceso es relativamente simple, aparece descrito en el sig. algoritmo:

INSERTAINICIO ( P, DATO )

{ Este algoritmo inserta un nodo al inicio de la lista. P es el apuntador al primer nodo de la lista, y DATO es la información que se almacenará en el nuevo nodo }

{Q es una variable de tipo puntero }

1. CREA (Q)

2. HACER Q^.INFORMACION <-DATO, Q^.LIGA <- P y P <- Q

INSERTA_LISTA

Nota: Las líneas discontinuas indican los cambios originados por la inserción de un nuevo nodo al inicio de la lista.

b) INSERCION AL FINAL DE LA LISTA

El nuevo nodo se coloca al final de la lista, convirtiéndose en el último de la misma. El algoritmo sig. describe el proceso:

INSERTAFINAL ( P, DATO )

{ Este algoritmo inserta un nodo al final de la lista. P es el apuntador al primer nodo de la lista, y DATO es la información que se almacenará en el nuevo nodo}

{Q y T son variables de tipo puntero }

1. HACER T <- P

2. REPETIR MIENTRAS T^ .LIGA <>NULL

{ Recorre la lista hasta llegar al último elemento }

HACER T <- T^ .LIGA

3. { FIN DEL CICLO DEL PASO 2 }

4. CREA (Q)

5. HACER Q^ .INFORMACION <- DATO, Q^ .LIGA <- NULL Y T^ .LIGA <- Q

sdfs

Nota: las líneas discontinuas indican los cambios originados por la inserción de un nuevo nodo al final de la lista.

Sino que el nuevo elemento se agregaría directamente , como en el caso de inserción al inicio de la lista.

sdfsdff

Nota: Las líneas discontinuas indican los cambios originados por la inserción de un nuevo nodo al final de la lista.

Inserción en una lista con punteros al inicio y fin de la misma. a) Lista con puntero al inicio, P, y al final T, b) Lista luego de la inserción de un nuevo elemento al final de la misma.

INSERCION DE UN NODO ANTES/DESPUES QUE OTRO

El nuevo nodo se coloca antes (después) de otro nodo dado como referencia. Primero se analizará el caso precediendo a un nodo, y luego el de inserción sucediendo un nodo dado.

Algoritmo Insertantes

Hasta este momento en todas las operaciones de listas que hemos analizado, no se ha considerado algún orden entre los elementos. Si se supone que la lista está ordenada, en el momento de insertarle un nuevo valor, habrá que mantener el orden previamente establecido. Sin embargo, como los elementos están relacionados por medio de punteros esta operación (inserción manteniendo el orden) no tiene mayor costo ya que no se deben mover elementos.

A continuación se tratará sobre la operación de borrado (eliminación) de nodos de una lista. Como en el caso de la inserción, solo se considerarán listas desordenadas.

Borrado de un elemento

Consiste en quitar un nodo de la lista redefiniendo las ligas que correspondan. Se pueden presentar cuatro casos en esta operación.

Eliminar el primer nodo

Eliminar el ultimo nodo

Eliminar un nodo con información X

Eliminar el nodo anterior/posterior al nodo con información X

a) ELIMINAR EL PRIMER NODO

Se quita el primer elemento de la lista, redefiniendo el valor del puntero al nuevo inicio de la misma. El proceso es muy sencillo.

se presenta un ejemplo de borrado del primer nodo de una lista aplicando el algoritmo anterior.

b) ELIMINAR EL ULTIMO NODO

Se quita el último nodo de la lista, redefiniendo a NIL el campo LIGA de su predecesor, Para alcanzar el último nodo se deberá recorrer previamente toda la lista, excepto si se usara un puntero indicando el final de la misma. a continuación se presenta un algoritmo de solución, considerando que solamente se tiene un puntero al inicio de la lista.

Borrado del último nodo de una lista

c) ELIMINAR UN NODO CON INFORMACION X

Se debe buscar al nodo que contenga la información dada como referencia (X) y eliminarlo, estableciendo la liga correspondiente entre su predecesor y su sucesor.

borrado de un nodo con información X

d) ELIMINAR EL NODO ANTERIOR (O POSTERIOR) AL NODO CON INFORMACION X

Dado un nodo como referencia se debe eliminar su predecesor o su sucesor, según el caso, estableciendo las ligas correspondientes. Aquí se tratará el caso del nodo predecesor.

Ejemplo de borrado del nodo predecesor de un nodo dado, aplicando el algoritmo anterior

Búsqueda de un elemento

La operación de búsqueda de un elemento en una lista se realiza de modo secuencial. Se deben recorrer los nodos, tomando el campo LIGA como puntero al siguiente nodo a visitar. Debido a esto se puede decirse que esta operación esta implícita en alguno de los casos de inserción y borrado.

Al igual que el caso de las operaciones vistas anteriormente, existe diferencia en el algoritmo según sea para trabajar con listas desordenadas o con listas ordenadas. Se comenzara con el algoritmo de búsqueda para listas desordenadas.

Para la búsqueda ordenada se hace una pequeña modificación en la condición del paso 2 para poder buscar en una lista ordenada de forma ascendente.

Todos los algoritmos aquí mostrados pueden ser implementados de manera recursiva ya que las listas en sí son estructuras recursivas por excelencia.

LISTAS DOBLEMENTE LIGADAS

Una lista doblemente ligada es una colección de nodos, en la cual cada nodo tiene dos punteros, uno de ellos apuntando a su predecesor (LIGAIZQ) y otro a su sucesor (LIGADER). Por medio de estos punteros se podrá avanzar o retroceder a través de la lista, según se tomen decisiones de uno u otro puntero.

a)

ligaizq
información
ligader

Estructura de un nodo

b)

Ejemplo de una lista doblemente ligada.

Para tener un fácil acceso a la información de la lista es recomendable usar dos punteros, P y F, que apunten al primer y ultimo nodo de la lista respectivamente.

Operaciones con listas doblemente ligadas

Recorrido de la lista

Inserción de un elemento
Borrado de un elemento

Recorrido de la lista

Al tener doble liga, las listas pueden recorrerse tanto del inicio al final (toman las ligas derechas), como en sentido inverso (tomando las ligas del final). Cualquiera que sea el sentido del recorrido, el algoritmo es similar al que presenta para listas simplemente ligadas. Se deja al lector su diseño.

Inserción de un elemento

La inserción de un elemento consiste en agregar un nuevo nodo a la lista y establecer los punteros correspondientes. No se considerará el caso de lista vacías. La inserción puede llevarse a cabo:

Al inicio de la lista.

Al final de la lista.

Antes/después de un nodo dado como referencia.

La operación de borrado de un nodo en una lista doblemente ligada, al igual que en el caso de las listas simplemente ligadas, consiste en eliminar un elemento de la lista y restablecer las ligas que correspondan. Pueden presentarse cuatro casos:

Eliminar el primer nodo

Eliminar el ultimo nodo

Eliminar el nodo con información X
Eliminar el nodo anterior/posterior al nodo con información X

LISTAS CIRCULARES

Las listas circulares tienen la característica de que el último elemento de la misma apunta al primero.

Lista Circular

Las operaciones en listas circulares son similares a las operaciones en listas lineales, por lo tanto no se volverá a tratar cada una de ellas.

En el caso de la operación de recorrido de las listas circulares, es necesario aclarar que se debe considerar algún criterio para detectar cuando se han visitado todos los nodos para evitar caer en ciclos infinitos. Una posible solución consiste en usar un nodo extra, llamado nodo de cabecera, para indicar el inicio de la lista. Este nodo contendrá información especial, de tal manera que se distinga de los demás y así podrá hacer referencia al principio de la lista.

La principal ventaja de las listas circulares es que permiten la navegación en cualquier sentido a través de la misma y además, se puede recorrer toda la lista partiendo de cualquier nodo. Sin embargo, debemos hacer notar que se deben establecer condiciones adecuadas para detener el recorrido de una lista para evitar caer en ciclos infinitos. Lo mismo que en el caso de listas lineales suele usarse un nodo de cabecera. Este nodo tendrá las características descritas anteriormente y servirá como referencia para detectar cuando se ha recorrido totalmente la lista.

APLICACIONES

Dos de las aplicaciones mas conocidas de listas son:

Representación de polinomios
Resolución de colisiones (Hash)

En general puede decirse que las listas son muy útiles para aquellas aplicaciones en las cuales se necesite dinamismo en el crecimiento y reducción de las estructuras de datos.