INSTITUTO TECNOLÓGICO SUPERIOR DE FELIPE CARRILLO PUERTO.

MATERIA: Estructura De DatosTIPO: Presentación (Evidencias Unidad 2 y 3) DOCENTE: MTL. Niels Henryk Aranda Cuevas ALUMNO: Efrain Antonio Poot Tuz CARRERA: Ingeniería En Sistemas Computacionales TURNO: MatutinoAULA: J-3 GRUPO: “A” TERCER SEMESTRELUGAR Y FECHA: Felipe Carrillo Puerto, Q.Roo, 10/11/2014

Unidad 2. RecursividadEn general, los programas con recursividad están estructurados de tal modo que las funciones se llaman unas a otras de una manera disciplinada y jerárquica. Para algunos tipos de problemas, es útil tener funciones que se llaman a sí mismas. Una función recursiva es una función que se llama a sí misma de manera directa o indirecta a través de otra función. La recursividad es un tema complejo que se imparte en cursos de computación largos y avanzados. Primero, consideraremos la recursividad de manera conceptual, y posteriormente explicaremos algunos programas que contienen funciones recursivas. Los métodos para solucionar problemas por medio de la recursividad tienen algunos elementos en común. Se llama a una función recursiva para resolver un problema. La función en realidad sólo sabe cómo resolver el problema para el caso más sencillo, o caso base. Si se invoca a la función desde el caso base, ésta simplemente devuelve un resultado. Si se llama a la función desde un problema más complejo, la función divide el problema en dos partes conceptuales. Una parte que la función sabe cómo resolver y una parte que la función no sabe cómo resolver.

Para hacer posible la recursividad, la segunda parte debe replantear el problema original, pero con una versión ligeramente más sencilla o más pequeña que el problema original. Una función llama a una nueva copia de sí misma para que trabaje con el problema más pequeño, a esto se le denomina llamada recursiva o también paso recursivo. El paso recursivo también incluye la palabra reservada return, debido a que su resultado se combinará con la parte del problema que la función sabe cómo resolver para formar un resultado que se pase a la llamada original a la función, posiblemente. El paso recursivo se ejecuta mientras la llamada a la función original permanezca abierta, es decir, mientras no termine su ejecución. El paso recursivo puede generar muchas más de estas llamadas recursivas, mientras la función continúa dividiendo cada problema en dos partes conceptuales. Para que la recursividad termine, cada vez que la función se invoca a sí misma con una versión del problema ligeramente más sencilla que el problema original, esta secuencia de problemas más pequeños debe converger en algún momento con el caso base.

En ese punto, la función reconoce el caso base, devuelve el resultado a la copia previa de la función, y se presenta una secuencia de resultados que se mueve hacia arriba, hasta que la función original devuelve el resultado final a main . Se necesita bastante práctica en la escritura de programas recursivos, antes de que el proceso logre obtener una apariencia natural. Para ejemplificar estos conceptos, escribamos un programa recursivo que realice un cálculo matemático muy popular.El factorial de un entero no negativo n, se escribe n! (y se pronuncia “n factorial”), es el producto n (n - 1) (n - 2)… 1 donde 1! es igual a 1, y 0! se define como 1. Por ejemplo, 5! Es el producto 5*4*3*2*1, el cual es igual a 120. El factorial de un entero, numero, 1 mayor o igual que 0, se puede calcular de manera iterativa (no recursiva) por medio de una instrucción for de la siguiente manera: Factorial = 1; For (contador = numero; contador >= 1; contador--) Factorial *= contador;

Se puede llegar a una definición recursiva de la función factorial mediante la siguiente relación: n! = n (n - 1)! Por ejemplo, podemos ver claramente que 5! es lo mismo que 5*4!, como lo mostramos a continuación:

5! = 5 4 3 2 1 5! = 5 (4 3 2 1)

5! = 5 (4!) La siguiente figura muestra los valores devueltos por cada llamada recursiva a su llamada original, hasta que se calcula y se devuelve el valor final.

Unidad 3. Estructuras LinealesListas LigadasUna lista ligada es una colección lineal de estructuras autorreferenciadas, llamadas nodos, conectadas por medio de ligas apuntador; de aquí el término lista “ligada”. Se accede a una lista ligada a través de un apuntador al primer nodo de la lista. Se accede a los nodos subsiguientes a través del miembro liga almacenado en cada nodo. Por convención, el apuntador liga del último nodo de una lista se establece en NULL, para marcar el final de la lista. Los datos se almacenan en una lista ligada dinámicamente; conforme es necesario, se crea cada nodo. Un nodo puede contener datos de cualquier tipo, incluso otros objetos struct . Las pilas y las colas también son estructuras de datos lineales y, como veremos, son versiones restringidas de listas ligadas. Los árboles son estructuras de datos no lineales. Las listas de datos pueden almacenarse en arreglos, pero las listas ligadas proporcionan muchas ventajas. Una lista ligada es adecuada, cuando el número de elementos a representarse en la estructura de datos es impredecible. Las listas ligadas son dinámicas, por lo que la longitud de una lista puede aumentar o disminuir conforme sea necesario.

Sin embargo, el tamaño de un arreglo no puede alterarse una vez que se asignó la memoria. Los arreglos pueden llenarse. Las listas ligadas sólo se llenan cuando el sistema tiene insuficiente memoria para satisfacer los requerimientos de asignación dinámica de almacenamiento. Las listas ligadas pueden mantenerse ordenadas, si se inserta cada nuevo elemento en el punto adecuado de la lista.

Los nodos de una lista ligada por lo general no se almacenan contiguamente en memoria. Sin embargo, de manera lógica, los nodos de una lista ligada aparentan estar contiguos.

PilasUna pila es una versión restringida de una lista ligada. Los nuevos nodos pueden añadirse y eliminarse de una pila sólo en la cima. Por esta razón, a una pila se le conoce como una estructura de datos última en entrar, primera en salir (UEPS). Se hace referencia a una pila por medio de un apuntador hacia el elemento en la cima de la pila. El miembro liga del último nodo de la pila se establece en NULL para indicar el fondo de la pila. La figura muestra una pila con diversos nodos. Observe que las pilas y las listas ligadas se representan de manera idéntica. La diferencia entre las pilas y las listas ligadas es que las inserciones y las eliminaciones pueden ocurrir en cualquier parte de la lista ligada, mientras que en una pila, dichas operaciones se realizan sólo en la cima de ésta.Las funciones básicas que se utilizan para manipular una pila son empujar y sacar. La función empujar crea un nuevo nodo y lo coloca en la cima de la pila. La función sacar elimina un nodo de la cima de la pila, libera la memoria que estaba asignada al nodo eliminado y devuelve el valor eliminado.

ColasOtra estructura de datos común es la cola. Una cola es parecida a una fila para pagar en un supermercado; a la primera persona de la fila se le atiende primero, y los demás clientes entran a la fila sólo al final de ella, y esperan a que se les atienda. Los nodos de una cola se eliminan sólo de la cabeza de la cola, y se insertan sólo en los talones de ella. Por esta razón, a una cola se le conoce como una estructura de datos primera en entrar, primera en salir (PEPS). Las operaciones de insertar y eliminar se conocen como agregar en la cola y retirar de la cola.Las colas tienen muchas aplicaciones en sistemas de cómputo. Muchas computadoras sólo tienen un procesador, por lo que sólo es posible atender a un usuario a la vez. Las entradas de los demás usuarios se colocan en una cola. Cada entrada avanza gradualmente desde el frente de la cola, conforme los usuarios reciben servicio. La entrada del frente de la cola es la siguiente en recibir servicio.

CONCLUSIÓN GENERAL

Durante la segunda unidad aprendimos a utilizar la recursividad, y como practica realizamos dos

programas, el primero realizaba el factorial de un numero dado y la segunda realizaba la sucesión de

Fibonacci. En forma general los programas están estructurados de tal modo que las funciones se

llaman unas a otras de una manera disciplinada y jerárquica. Para algunos tipos de problemas, es útil

tener funciones que se llaman a sí mismas. Como vimos una función recursiva es una función que se

llama a sí misma de manera directa o indirecta a través de otra función.

En la tercera unidad aprendimos acerca de las listas simple y doblemente ligadas, vimos como

declarar, crear, eliminar, buscar y recorrer un nodo en ellas. Ahora sabemos que una lista ligada es

una colección lineal de estructuras autorreferenciadas, llamadas nodos conectados por medio de ligas

apuntador y que para acceder a ella utilizamos apuntadores. Además, aprendimos a diferenciar la lista

simple de la doblemente ligada al momento de programar. También utilizamos las colas las cuales son

estructuras de datos Peps (Primeras entrar, Primeras en salir, los nuevos nodos pueden añadirse y

eliminarse sólo en la cima). y las pilas las cuales son estructuras de datos Ueps (Ultimas en entrar,

Primera en salir, los nuevos nodos pueden añadirse en los talones y eliminarse en la cabeza).