LISTAS ENLAZADAS
Nuestra estructura de datos tendrá,2 campos vamos a mantener la variable primer nodos que siempre apunta al primer nodo, de la lista O nulo para la lista vacia.
Record Node {
Data // el dato almacenado en el nodo.
Next// una referencia al nodo sig. Nulo para el ultimo nodo.
}
Record list {
Node primer nodo // apunta el primer nodo de la lista: nulo para la lista vacia.
}
El recorrido en una lista enlazada siempre empezamos por el primer nodo y pasamos al sig. hasta que la lista llegue al final.
Node:= list. Primer nodo
While node not oull {
Node:= node netx
}
Las listas enlazadas se componen de nodos. Cada nodo presenta dos campos: por una parte, una referencia al siguiente nodo de la lista; por otra, una unidad de información llamada dato.
Las listas enlazadas se definen a partir de una estructura de datos recursiva.
Así, una lista enlazada puede ser
una lista vacía, representada por None, O
un nodo con un objeto dato y una referencia a una lista enlazada.
Esquema de un nodo y una lista enlazada.
Para que esta estructura sea un TDA lista enlazada, debe tener unos operadores asociados que permitan la manipulación de los datos que contiene. Los operadores básicos de una lista enlazada son:
- Insertar: inserta un nodo con dato x en la lista, pudiendo realizarse esta inserción al principio o final de la lista o bien en orden.
- Eliminar: elimina un nodo de la lista, puede ser según la posición o por el dato.
- Buscar: busca un elemento en la lista.
- Localizar: obtiene la posición del nodo en la lista.
- Vaciar: borra todos los elementos de la lista
Free(n):
}
}
Node ** list_ search ( node **n . int I ) {
While (*n) = NULL) {
If ((*n)- data == I ) {
Return n ;
}
N= & (*n) – next;
}
Return NULL;
}
Void list_print ( node *n ) {
If ( n == NULL ) {
Printf ( “ lista esta vacia Y n” ) ;
}
While ( n: = NULL ) {
Printf ( “ print % p % p % d Y n. n. n –next.= n- next;
}
}
Int mein ( void ) {
Node *n = NULL;
List.add ( &n,0 ); / * lista 0*/
List.add ( &n,1 ); / * lista 1 0*/
List.add ( &n,2 ); / * lista 2 1 0*/
List.add ( &n,3 ); / * lista 3 2 1 0*/
List.add ( &n,4 ); / * lista 4 3 2 1 0*/
List.add ( n,);
List.add ( &n ); /* borrar primero (a) */
LISTAS DOBLEMENTE ENLAZADAS
En algunas aplicaciones podemos desear recorrer la lista hacia adelante y hacia atrás, o dado un elemento, podemos desear conocer rápidamente los elementos anterior y siguiente. En tales situaciones podríamos desear darle a cada celda sobre una lista un puntero a las celdas siguiente y anterior en la lista tal y como se muestra en la figura.
Otra ventaja de las listas doblemente enlazadas es que podemos usar un puntero a la celda que contiene el i-ésimo elemento de una lista para representar la posición i, mejor que usar el puntero a la celda anterior aunque lógicamente, también es posible la implementación similar a la expuesta en las listas simples haciendo uso de la cabecera. El único precio que pagamos por estas características es la presencia de un puntero adicional en cada celda y consecuentemente procedimientos algo más largos para algunas de las operaciones básicas de listas. Si usamos punteros (mejor que cursores) podemos declarar celdas que consisten en un elemento y dos punteros a través de:
typedef struct celda{
tipoelemento elemento;
struct celda *siguiente,*anterior;
}tipocelda;
typedef tipocelda *posicion;
Un procedimiento para borrar un elemento en la posición p en una lista doblemente enlazada es:
void borrar (posicion p)
{
if (p->anterior != NULL)
p->anterior->siguiente = p->siguiente;
if (p->siguiente != NULL)
p->siguiente->anterior = p->anterior;
free(p);
}
LISTAS ENLAZADAS CIRCULARES
Las listas circulares tienen la característica de que el último elemento de la misma apunta al primero.
Enseguida se mostrarán los algoritmos más comunes en listas circulares. Al igual que en las secciones anteriores, utilizaremos el apuntador top para hacer referencia al primer nodo en la lista.
Algoritmo de creación
repite
new(p)
lee(p(dato))
si top=nil entonces
top<--p
q<--p
en caso contrario
q(liga)<--p
q<--p
p(liga)<--top
mensaje (otro nodo ?)
lee(respuesta)
hasta respuesta=no
Algoritmo para recorrer la lista
p<--top
repite
escribe(p(dato))
p<--p(liga)
hasta p=top
Algoritmo para insertar antes de 'X' información
new(p)
lee(p(dato))
si top=nil entonces
top<--p
p(liga)<--top
en caso contrario
mensaje(antes de ?)
lee(x)
q<--top
r<--top(liga)
repite
si q(dato)=x entonces
p(liga)<--q
r(liga)<--p
si p(liga)=top entonces
top<--p
q<--q(liga)
r<--r(liga)
hasta q=top
Algoritmo para insertar después de 'X' información
new(p)
lee(p(dato))
mensaje(después de ?)
lee(x)
q<--top
r<--top(liga)
repite
si q(dato)=x entonces
q(liga)<--p
p(liga)<--r
q<--q(liga)
r<--r(liga)
hasta q=top
Algoritmo para borrar
mensaje(valor a borrar )
lee(valor_a_borrar)
q<--top
r<--top
p<--top
mientras q(liga)<>top haz
q<--q(liga)
repite
si p(dato)=valor_a_borrar entonces
si p=top entonces
si top(liga)=top entonces
top<--NIL
en caso contrario
top<--top(liga)
q(liga)<--top
en caso contrario
r(liga)<--p(liga)
dispose(p)
p<--top
en caso contrario
r<--p
p<--p(liga)
hasta p=top
LISTAS ENLAZADAS DOBLEMENTE CIRCULARES
En una lista enlazada doblemente circular, cada nodo tiene dos enlaces, similares a los de la lista doblemente enlazada, excepto que el enlace anterior del primer nodo apunta al último y el enlace siguiente del último nodo, apunta al primero. Como en una lista doblemente enlazada, las inserciones y eliminaciones pueden ser hechas desde cualquier punto con acceso a algún nodo cercano. Aunque estructuralmente una lista circular doblemente enlazada no tiene ni principio ni fin, un puntero de acceso externo puede establecer el nodo apuntado que está en la cabeza o al nodo cola, y así mantener el orden tan bien como en una lista doblemente enlazada.
RECURSIVIDAD
Objetivo:
Comprender el concepto de recursividad y su implementación en un lenguaje de programación.
Definición:
Es la capacidad que tiene una función a procedimiento de invocarse a si mismo durante la ejecución de un programa. Una función o procedimiento es recursivo cuando esta definido en función de si mismo.
FUNCION FACTORIAL
Dada un entero positivo llamado n se define su factorial como el producto de todos los enteros entre n y 1.
S! = 5*4*3*2*1
S! = 120
N= s
ALGORITMO FACTORIAL:
Function factorial ( n )
Inicio
Sin = 0 entonces
Factorial 1 // return
Si no
Factorial n* factorial ( n-1 ) // return
Fin- si
Fin- factorial
Int factorial ( 1n+n ) {
If (( n == 0 ) || ( n == 1 )
Return ( 1 )
Else
Return ( n* factorial ( n-1 )
}
IMPLEMENTAR LA RECURSIVIDAD USANDO PILAS
Un procedimiento, una función contiene tanto variables locales como argumentos ficticios (parámetros. A través de los argumentos se transmiten datos en las llamadas a los subprogramas, o bien, se devuelvan valores al programa o subprograma invocan te.
Además, el subprograma debe guardar la dirección de retorno al programa que realiza la llamada. En el momento en que termina la ejecución de un subprograma el control pasa a la dirección guardada.
Ahora el subprograma es recursivo, entonces además de la dirección de retorno, los valores actuales de las variables locales y argumentos deben de guardarse ya que se usaran de nuevo cuando el subprograma se reactive. Supongamos que se ha llamado al subprograma P, que tiene llamadas a sí mismo, es decir, es recursivo. El funcionamiento del programa recursivo P:
*Se crea una pila para cada argumento.
*Se crea una pila para cada variable local.
*Se crea una pila para almacenar la dirección de retorno.
Cada vez que se hace una llamada recursiva a p los valores actuales de los argumentos y de las variables locales se meten en unas pilas para ser procesadas posteriormente. Asimismo, cada vez que hay un retorno a p procedente de una llamada recursiva anterior, se restauran los valores de las variables locales y argumentos de las cimas de las pilas.
1¿ que solución estructurada ofrecen los algoritmos recursivos?
Una de las soluciones que los problemas mas simples se utilizan para construir la solución al problema inicial.
2¿ porque es fundamental la recursividad?
Porque es como ver diferentes acciones repetitivas permitiendo que un subprograma se llama así mismo para resolver una operación mas pequeño.
3¿ porque es tan poderoso y usado este método de recursividad?
Por que es una herramienta tan poderosa para resolver problemas que a primera vista parece poseer una solución difícil y es cuando para la programación como lo son los códigos.
Long, if, return, else y el mas común char.
Porque pilas colas y listas?
Por el orden más impotente ya que podemos introducir los datos necesarios en pilas así poder seleccionar los datos para colas y listas enlazadas dependiendo los datos requeridos por eso es el orden.
Porque no al revés listas, colas y pilas?
Lo de la lista es para tamaño de memoria y no podemos y no se le puede asignar mas memoria y mientras que pilas y colas crea más espacio en la memoria y así viceversa.
4.3 MECANICA DE RECURSION
Un metodo recursivo contiene 2 elementos básicos que son fundamentales para su funcionamiento
CASO BASE
Existe almenos una solución para un valor determinado.
PROGRESO
Cualquier llamado así mismo debe progresar acercarse aun caso base
Que es la torre de hanoi?
Las Torres de Hanói es un rompecabezas o juego matemático inventado en 1883 por el matemático francés Éduard Lucas.[1] Este solitario se trata de un juego de ocho discos de radio creciente que se apilan insertándose en una de las tres estacas de un tablero. El objetivo del juego es crear la pila en otra de las estacas siguiendo unas ciertas reglas. El problema es muy conocido en la ciencia de la computación y aparece en muchos libros de texto como introducción a la teoría de algoritmos.
Descripción
El juego, en su forma más tradicional, consiste en tres varillas verticales. En una de las varillas se apila un número indeterminado de discos (elaborados de madera) que determinará la complejidad de la solución, por regla general se consideran ocho discos. Los discos se apilan sobre una varilla en tamaño decreciente. No hay dos discos iguales, y todos ellos están apilados de mayor a menor radio en una de las varillas, quedando las otras dos varillas vacantes. El juego consiste en pasar todos los discos de la varilla ocupada (es decir la que posee la torre) a una de las otras varillas vacantes. Para realizar este objetivo, es necesario seguir tres simples reglas:
1.Sólo se puede mover un disco cada vez.
2.Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo.
3.Sólo puedes desplazar el disco que se encuentre arriba en cada varilla.
Este problema se suele plantear a menudo en ámbitos de programación, especialmente para explicar la recursividad
QUE SE UTILIZA EN UN PLAN DE VUELO?
El Plan de Vuelo consiste en la información especificada suministrada a las dependencias de los servicios de tránsito aéreo, relativa al proyecto total o parcial del vuelo de una aeronave. Para someter un plan de vuelo a una oficina de los servicios de tránsito aéreo se utiliza un formulario de plan de vuelo, debidamente llenado (ver Apéndice A) que salvo en los casos de vuelos repetitivos, debe presentar el piloto al mando o un representante suyo en aeródromo de salida. A partir de aquí, el Plan de vuelo será aceptado o no por la oficina correspondiente o se indicará cualquier cambio que deba realizarse. A continuación el Plan de vuelo se comunica a las dependencias ATS afectadas por el vuelo y éstas a los controladores correspondientes de área, aproximación, información de vuelo, torre de control, etc. Una vez comenzado el vuelo o antes si se ha producido algún cambio, las modificaciones sobre las intenciones de los pilotos , presentadas como ya se ha indicado como Plan de vuelo y que ahora constituyen el plan de vuelo actualizado, seguirá el camino reseñado anteriormente.
FUNCION DE BUSQUEDA
Un problema típico de la programación imperativa es el crear módulos de búsqueda. En la mayoría de los casos se soluciona mediante la definición de un conjunto de funciones. Ahora veremos una técnica para crear una función de búsqueda que sirve para los siguientes casos:
- Verificar si existe el valor buscado.
- Obtener el valor si existe y si no error.
- Obtener el valor si existe y si no notificarlo.
Por ejemplo, tenemos una lista con parejas (clave,valor) y queremos implementar la función Busca(Clave) que retorna el valor si encuentra la clave. Además queremos utilizar la misma función para los tres casos comentados anteriormente. La base para Busca es que retorna un valor si encuentra la clave y si no, no retorna ningún valor. La implementación que se realiza se basa en la posibilidad de retornar múltiples valores, que se utilizará para retornar uno o ningún valor.
Var l=[(1,10),(2,20),(3,30)]
Fun Busca(clave,Lista:List)=>
Search (e<-Lista, e[0]=:=Clave) e[1] else return void
ValueP(Busca(clave,lista)) retorna true si encuentra la clave y false si no. De esta forma se comprueba la existencia de una clave.
Busca(clave,lista) retorna el valor de la clave si la encuentra y si no, produce un error, ya que la función Busca no retorna ningún valor. Por ejemplo, el resultado de algunas búsquedas será:
CoSeL> busca(2,l)
20
CoSeL> busca(5,l)
Error in command line
[MultValueReturnError]: It returns Void when a return value needed
Call stack:
<Reference:00B4FA2D> Fun Busca
<Reference:0087F4F4> Fun Start
<Reference:00B634D4> Proc System.cmpHelpCode
La excepción generada por la búsqueda cuando no encuentra la clave es MultValueReturnError. Se puede cambiar la excepción y el mensaje generado por otros más apropiados poniendolos como parámetros de void.
Var l=[(1,10),(2,20),(3,30)]
Fun Busca(clave,Lista:List)=>
{
Search (e<-Lista, e[0]=:=Clave) e[1]
else return void(Exception("Clave ",Clave," no encontrada"))
}
CoSeL> busca(5,l)
Error in command line
[NotFoundError]: Clave 5 no encontrada
Call stack:
<Reference:00B50C4A> Fun Busca
<Reference:0087F474> Fun Start
<Reference:00B6345C> Proc System.cmpHelpCode
v?=Busca(clave,lista) retorna true si encuentra la clave y asigna a v el valor de ésta. Si no existe la clave, retorna false y no realiza ninguna asignación.
ARBOLES DE DECISION
El árbol de decisión es un diagrama que representan en forma secuencial condiciones y acciones; muestra qué condiciones se consideran en primer lugar, en segundo lugar y así sucesivamente. Este método permite mostrar la relación que existe entre cada condición y el grupo de acciones permisibles asociado con ella.
Los árboles de decisión son normalmente construidos a partir de la descripción de la narrativa de un problema. Ellos proveen una visión gráfica de la toma de decisión necesaria, especifican las variables que son evaluadas, qué acciones deben ser tomadas y el orden en la cual la toma de decisión será efectuada. Cada vez que se ejecuta un árbol de decisión, solo un camino será seguido dependiendo del valor actual de la variable evaluada.
Uso de árboles decisiones.
El desarrollo de árboles de decisión beneficiado analista en dos formas. Primero que todo, la necesidad de describir condiciones y acciones llevan a los analistas a identificar de manera formal las decisiones que actualmente deben tomarse. De esta forma, es difícil para ellos pasar por alto cualquier etapa del proceso de decisión, sin importar que este dependa de variables cuantitativas o cualitativas. Los árboles también obligan a los analistas a considerar la consecuencia de las decisiones.
