ESTRUCTURA DE DATOS I UNIDAD I ARREGLOS • De una dimensión • De dos dimensiones • De tres o mas dimensiones • Matrices poco densas regulares • Matrices poco densas irregulares • Ordenaciones • Búsquedas • Mezclas • Operaciones en arreglos UNIDAD II COLAS 2.1 Cola circular • Doble cola • Cola de prioridades • Representación en memoria • Operaciones en colas • Problemas UNIDAD III PILAS 3.1 Representación en memoria • Notación infija, posfija y prefija • Recursividad • Implementar la recursividad usando pilas • Operaciones en pilas • Problemas UNIDAD IV LISTAS ENLAZADAS 4.1 Representación en memoria 4.2 Listas con cabeceras 4.3 Listas dobles 4.4 Operaciones en listas enlazadas 4.5 Recuperación de espacio en listas enlazadas 4.6 Problemas UNIDAD V ARBOLES BINARIOS

1

5.1 Terminología 5.2 Arboles binarios y representación gráfica 5.3 Representación de un árbol binario en memoria 5.4 Recorrido de un árbol binario (Inorden, preorden y postorden) 5.5 Arboles enhebrados 5.6 Operaciones en arboles binarios 5.7 Arboles en montón 5.8 Arboles binarios de búsqueda 5.9 Longitud de camino 5.10 Problemas UNIDAD VI ARBOLES GENERALES 6.1 Terminología y representación en memoria de un árbol general 6.2 Transformación de un árbol general a un árbol binario 6.3 Recorrido de un árbol general 6.4 Problemas UNIDAD VII GRAFOS 7.1 Terminología 7.2 Representación en memoria secuencial 7.3 Representación en memoria enlazada 7.4 Operaciones sobre grafos 7.5 Camino mínimo 7.6 Recorrido de un grafo 7.7 Problemas UNIDAD I ARREGLOS DE UNA DIMENSION Los arreglos es una herramienta maravillosa, le permite asociar un solo nombre de variable a una colección completa de datos puede mover el arreglo completo en memoria, copiarlo y además solo haciendo referencia a 2

un solo nombre de variable un arreglo es un conjunto finito ordenado de elementos homogéneos, la propiedad de ordenación significa que es posible identificar el primero, segundo, tercero... y el enésimo elemento del arreglo, un arreglo puede ser un conjunto de elementos de tipo cadena en tanto que otro puede ser de tipo entero. Sintaxis en pascal: Type nombre_arreglo = array [rango_inicial...rango_final] of tipo_arreglo; Var Identificador: nombre_arreglo; ARREGLOS MULTIDIMENSIONALES Existen grupos de datos que se representan mejor en forma de tabla o matriz cada dos o mas subíndices a esos les llamamos arreglos multidimensionales se les llama así porque a diferencia de un arreglo bidimensional estos constan de dos o mas dimensiones. ARREGLOS BIDIMENSIONALES Un array bidimensional se puede considerar como un vector de vectores. Es decir un conjunto de elementos todos del mismo tipo, en el cual el orden de los componentes es significativo y en el que se necesitan especificar dos subíndices para poder identificar cada elemento del arreglo: Una forma importante de representar datos en un array bidimensional puede verse de forma lógica como una tabla de filas y columnas ORDENACIONES En los vectores con frecuencia es necesario clasificar u ordenar sus elementos en un orden particular La clasificación es una operación tan frecuente en programas de computación que una gran cantidad de algoritmos se han diseñado para clasificar listas de elementos con eficacia y rapidez. La ordenación o clasificación depende del tamaño del vector o array a clasificar, el tipo de datos y la cantidad de memoria disponible(Esta puede ser de forma creciente o decreciente). La ordenación puede ser de forma ascendente o descendente para datos numéricos alfabéticos o para datos de caracteres. METODO DE LA BURBUJA El algoritmo de clasificación de la burbuja se basa en el proceso de comparar pares de elementos adyacentes e intercambiarlos entre si hasta que estén todos ordenados, los pasos a dar son: Comparar el elemento ad1y ad2 si están en orden se mantienen en caso contrario se intercambia entre si. A continuación se comparan los elementos 2 y 3 de nuevo se intercambia si es necesario. El proceso continúa hasta que cada elemento del vector ha sido comparado con sus elementos adyacentes y se han realizado los intercambios necesarios. 01 01 01 01 01 01

3

36 36 36 36 06 06 24 24 24 06 36 36 10 10 06 24 24 24 06 06 10 10 10 10 12 12 12 12 12 12 y se sigue con 6 iteraciones hasta que este ordenado . CLASIFICACION POR SHELL Esta clasificación fue desarrollada por Daniel Shell para evitar la ineficiencia de la clasificación por burbujas para grandes matrices. La clasificación de Shell se diferencia de la clasificación por Burbuja en que se compara elementos mas separados antes de comparar los elementos adyacentes. Esto elimina gran parte del desorden de la matriz en las primeras iteraciones. La clasificación de Shell utiliza una variable llamada intervalo que inicialmente recibe un valor igual a la mitad del numero de elementos que hay en la matriz. El valor del intervalo especifica la distancia entre cada par de elementos comparables de la matriz. .44 .11 .11 .11 .11 .88 .88 .66 .66 .66 .22 .22 .22 .22 .22 .77 .77 .77 .77 .55 .33 .44 .44 .44 .44 .66 .66 .88 .88 .88 .44 .44 .44 .44 .44 .55 .55 .55 .55 .77 Los elementos separados serán inicialmente de un intervalo de 4 para este ejemplo, la primera iteración de la matriz comparara todos los elementos separados por esa distancia el proceso se repite hasta que no hay intercambios, con un intervalo de 4 y se vuelve a iniciar calculando el nuevo intervalo hasta que este llegue a 1. CLASIFICACION POR QUICK SORT Aunque la eficiencia de la clasificación Shell aumenta a medida que crece el numero de elementos también tiene limitaciones. La clasificación rápida que es un algoritmo recursivo de clasificación aumenta la velocidad a medida que el numero de elementos se aproxima a 150 o 200 , de hecho la clasificación rápida es uno de los 4

algoritmos de clasificación que mas se utilizan en la actualidad. Si la matriz se pasa a la rutina de clasificación rápida el algoritmo seleccionara el valor contenido en [Principiolista+ Finallista]div 2 ; cualquier valor de la lista será colocado en una lista y los valores que sean mayores o iguales que el separador de lista se colocaran en una segunda lista como se muestra a continuación: 60 20 10 30 40 50 80 70 0 El orden que debe llevar las iteraciones es desde el punto medio hacia abajo y después de arriba hacia el centro después se sigue haciendo ciclos con los demás bloques. BÚSQUEDA SECUENCIAL Es la técnica de búsqueda mas simple comenzando por la cabeza de la lista se busca un determinado registro examinando cada registro secuencialmente hasta que se encuentra o la lista es agotada. Este algoritmo es adecuado tanto para listas secuenciales como para listas enlazadas. La lista no tiene que estar ordenada aunque la eficiencia de la búsqueda puede mejorarse si lo esta. ALGORITMO: Comenzar por el primer elemento de la lista mientras mas elementos en la lista y valor clave no encontrado. Obtener siguiente elemento de la lista: Si valor clave = encontrado Entonces devolver registro encontrado Si no devolver registro no encontrado BÚSQUEDA BINARIA Es uno de los algoritmos mas rápidos que usan los programadores .A diferencia de la búsqueda secuencial que examina elementos sucesivos de la matriz , la búsqueda binaria reduce el numero de elementos que deben ser examinados. Con un factor de dos en cada iteración hasta que se encuentra el registro deseado .La disminución de los 5

tiempos de ejecución se hace mas importante al aumentar el tamaño de la matriz . La primera iteración de la búsqueda examina toda la matriz. Supongamos que las variables bajo y alto en el siguiente ejemplo reciben los valores de 0 y 9. La variable índice medio es el elemento medio del intervalo de búsqueda. Valores de [Indice_Medio] contiene el valor que se va a comparar con el valor deseado. Valor a buscar =jelipe Indice_medio =(Alto + Bajo) div 2 (9+0) div 2=4 (9+4) div2= 6 (6+4) div2 =5 Si el valor determinado en valores (índice medio) es igual al valor deseado la búsqueda se completa dando un valor verdadero a la variable encontrada. Si el valor contenido en valores (Indice Medio) es mayor que el valor deseado el algoritmo de búsqueda se modificó, ya que el valor indica que no hay razón para seguir buscando en ese punto la lista. BÚSQUEDA MEDIANTE TRANSFORMACIÓN DE CLAVES HASH L a búsqueda binaria proporciona un medio para reducir el tiempo requerido de buscar en una lista, sin embargo este método exige que los datos estén ordenados. Existen otros métodos que pueden aumentar la velocidad de búsqueda en los datos y no necesitan estar ordenados. Este otro método se denomina Hash o transformación de claves. El método Hash consiste en convertir la clave dada numérica o alfanumérica en una dirección (índice) dentro del array .La correspondencia entre las claves y la dirección en el medio de almacenamiento o el array se establece por una función de conversión (Función Hash). Existen numerosos métodos de transformación de claves todos ellos tienen en común la necesidad de convertir en direcciones .En esencia la función de conversión equivale a un calculador de direcciones .Cuando se desea localizar un elemento de clave x el indicador de direcciones indicara en que posición del array estará posicionado el elemento. TRUNCAMIENTO Ignora parte de la clave y utiliza la parte restante directamente como índice (Considerando campos no numéricos y sus códigos numéricos) .Si las claves por ejemplo, son enteros de 8 dígitos y la tabla de transformación tiene 1000 posiciones entonces el primero, segundo y quinto dígitos desde la derecha pueden formar la función de conversión. 0 Clave=72588495 : El truncamiento es un método muy rápido pero falla para distribuir las claves de modo uniforme. PLEGAMIENTO

6

Consiste en la partición de la clave en diferentes partes y la combinación de las partes en un modo conveniente (a menudo utilizando suma o multiplicación) para obtener el índice .La clave x se divide en varias partes donde cada parte tienen el mismo numero de dígitos que la dirección especificada. 1000 000 a 999 Fx=x1+x2+x3...+xn 625 381 94 625+381+94=11100 100 ARITMÉTICA MODULAR Convertir la clave a un entero , dividir por el tamaño del rango del índice y tomar el resto como resultado. La función de conversión utilizada es MOD (Modulo o resta de división entera). Donde el mes el tamaño del arreglo con índices de 0 hasta n−1. Los valores de la función y direcciones van de 0 a n−1 ligeramente menor al tamaño del array. La mejor elección de los módulos son los números primos. M=100 F(x)= x mod 100 X=234661234 F(x)=234661234 mod 100 =34 La clave de búsqueda en una cadena de caracteres tal como el nombre para obtener direcciones de conversión el método mas simple es asignar a cada caracter de la cadena un valor entero (ejemplo A=1, B=2, C=3,etc) y sumar los valores de los caracteres en la cadena al resultado se le aplica entonces el modulo. MITAD DEL CUADRADO Este método consiste en calcular el cuadrado de la clave x. La función de conversión se define como F(x)=C donde C se obtiene eliminado dígitos de ambos extremos de x2; para todas las claves se deben usar las mismas posiciones de x2. Ejemplo: Una empresa tiene 80 empleados y cada uno de ellos tiene un numero de identificación de 4 dígitos y el conjunto de direcciones de memoria varia en un rango de 0 a 100 calcular las direcciones que se obtendrán al aplicar mitad del cuadrado. Clave x x2 4 y 5 4205 176 82 025 82 7148 510 93 904 93 3350 112 22 500 22 COLISIONES La función de operación Hash no siempre proporciona valores distintos, puede ser que para dos claves diferentes x1 y x2 se obtenga la misma dirección. Esta situación se denomina colisión y se debe de encontrar métodos para su correcta resolución. F (123445678) mod 100= 44

7

colisión F (123445880) mod 100= 44 RESOLUCION DE COLISIONES Si la clave transformada nos da una dirección que ya esta ocupada incrementamos el índice y examinamos el espacio siguiente. Para buscar un registro usando esta técnica de manejo de colisiones efectuamos la función Hash sobre la clave y luego comparamos la clave deseada con la real en la posición asignada. Si las claves no coinciden iniciamos una búsqueda secuencial, comenzando con la siguiente posición del array. REHASHING Otra técnica común para la resolución de colisiones se llama rehashing. Si el primer calculo de la función Hash produce una colisión se utiliza la dirección transformada como entrada para la función rehashing como entrada para la función rehashing y se calcula la nueva dirección. Clave mod 100 −> Dirección ocupada (Dirección +2) mod 100 −>Dirección 55667003 mod 100 =03 • + 2= 5 mod 100 −>05 CUBOS Y ENCADENAMIENTO Otra alternativa para las técnicas de colisiones es permitir transformar múltiples claves de registros. Una solución es dejar que cada dirección transformada contenga espacios para múltiples registros en vez de un único registro. vacío 453614001 vacío 556677003 123456004

vacío 302472107 vacío 123450003 445500124

Vacío Vacío Vacío Vacío 222230504

234056399

vacío

Vacío

Otra forma para evitar este problema es usar la dirección transformada no como posición real del registro sino como un índice en un array de punteros. Cada puntero accede a una cadena de registros que participan de la misma dirección transformada en vez de buscar en el array o hacer una retransformación.

MEZCLAS El proceso de mezclas es muy sencillo, el programa compara y lee los 2 registros y escribe en un archivo recién creado.

8

A continuación se lee otro registro de datos no entradas este proceso continúa hasta que todos los registros de uno o ambos archivos hayan sido procesados. Normalmente uno de los archivos de entrada acaban con sus registros antes que otros. Cuando ocurre esto el proceso continúa leyendo registros del archivo restante y los escribe en el archivo recién creado. CLASIFICACION POR MEZCLAS DIRECTAS Por desgracia algunos algoritmos de clasificación son inaplicables si la continuidad De datos por ordenar no cabe en la memoria principal de la computadora. Algunos algoritmos de clasificación son inaplicables si la cantidad de datos por ordenar no cabe en la memoria principal de la computadora pero se le presenta por ejemplo en un dispositivo de almacenamiento periférico y secuencia como una cinta de disco. En este caso describimos los datos como un archivo secuencial cuya característica es que en cada momento un componente es accesible directamente. Esta es una restricción severa si se compara con las posibilidades que ofrecen los arreglos, por lo tanto hay que aplicar otras técnicas de clasificación la mas importante es la mezcla, mezclar significa compilar dos o mas secuencias ordenadas en una sola secuencia ordenada, es una operación mucho mas sencilla que clasificar y sirve como una operación auxiliar en el proceso mas complejo de la clasificación secuencial. Una manera de clasificar cada base en la mezcla, llamada mezcla directa es la siguiente: 1. − Dividir la secuencia A en dos mitades denominadas B y C. 2. − Mezclar B y C combinando cada elemento en pares ordenados. 3. −Llamar A a la secuencia mezclada y repetir los pasos 1 y 2 esta vez combinando los pares en cuádruplos ordenados. 4. − Repetir los pasos anteriores combinando los cuádruplos en octetos y seguir haciendo esto (Cada vez duplicando las longitudes de las subsecuencias combinadas hasta que quede ordenado a la secuencia total). A 44 55 12 42 / 94 18 06 67 B 44 55 12 42 C 94 18 06 67 A 44 94 18 55 /06 12 42 67 B 44 94 18 55 C 06 12 42 67 A 06 12 44 94 / 18 42 55 67 B 06 12 44 94 C 18 42 55 67 A 06 12 18 42 44 55 67 94 9

INTERCALACION CUADRATICA (SECUENCIAS EQUILIBRADAS) Este método utiliza la memoria de la computadora para realizar clasificaciones internas y cuatro archivos secuenciales temporales para trabajar. Supongamos que un archivo de entrada F que se desea ordenar por orden creciente de las claves de sus elementos se dispone de cuatro archivos secuenciales de trabajo F1, F2, F3 y F4 y que se pueden colocar n elementos en memoria central en un momento dado en una tabla T de n elementos el proceso es el siguiente: 1. − Lectura del archivo de entrada por lotes de n elementos. 2. −Ordenación de cada uno de estos bloques y escritura alternativa sobre F1 y F2. 3. − Fusión de F1 y F2 en bloques de 2 elementos que se escriben alternativamente sobre F3 y F4. 4. −Fusión de F3 y F4 y escritura alternativa en F1 y F2 en bloques de 4n elementos ordenados. 5. − El proceso consiste en doblar cada vez mas el tamaño de los bloques utilizando las parejas (F1 como F2) y (F3 como F4). F= 46 66 4 12 7 5 34 32 68 8 99 16 13 14 12 10 F1 = 4 12 46 66 8 16 68 99 F2 = 5 7 32 34 10 12 13 14 F3= 4 5 7 12 32 34 46 66 8 10 12 13 14 16 68 99 F1= 4 5 7 8 10 12 12 13 14 16 32 34 46 66 68 99 F2=Vacio MEZCLA NATURAL Primero se pone el apuntador en el primer elemento y se sigue hasta encontrar un elemento menor en el elemento en que se encuentra un elemento menor se corta el segmento y empieza otro. Estos se acomodan intercambiando los segmentos en F1 y F2. F= 32 66 | 34 72 84 96 | 48 | 31 | 24 39 | 14 F1= 32 66 48 24 39 F2=34 72 84 96 31 14 F= 32 34 6 | 48 | 24 39 72 84 96 | 31 | 14 F1= 32 34 66 24 39 72 84 96 14 F2= 48 31 UNIDAD II 10

COLAS En las colas el elemento que entro en primer lugar también es el primero en salir por ello se conocen como listas FIFO (First in − First out). Así pues la diferencia con las pilas recibe en el modo de entrada y salida de datos. En las colas las inserciones se realizan al final de la lista no al principio por ello las colas se usan para almacenar datos que necesiten ser procesados según el orden de llegada. Nodo I M F En la informática muchas aplicaciones para las colas (colas de aplicación) etc. . Por ejemplo un sistema de tiempo compartido suele tener un procesador central y una serie de periféricos compartidos: discos, impresoras, etc. Los recursos se comparten con diferentes usuarios y se utiliza una cola para almacenar el programa por los diferentes usuarios que esperan su turno de ejecución. El procesador atiende por riguroso orden de llamado de usuario. REPRESENTACIÓN DE COLAS Las colas pueden representarse como estructuras dinámicas o arrays. ESTRUCTURA DINAMICA Inicio Medio Final ARRAY 100

264

119

48

Inicio Final COLAS DOBLES Existe una variable de la cola simple que es la bicola (doble cola). Es una cola bidimensional en la que las inscripciones y eliminaciones se pueden realizar en cualquiera de los dos extremos de la cola. Inserción Eliminación Inicio

Final

Eliminación Inserción Existen dos variantes de la bicola (cola doble): Cola doble con entrada restringida: Acepta valor, inserciones solo al final de la columna. Cola doble con salida restringida: Acepta eliminaciones solo al inicio de la cola. Indica Memoria Dinámica

11

Crear I I=NULL Crear M M=NULL Crear F F=NULL Mientras si (Quiere dar de alta) Si I=Null Entonces Crear Nodo I I sig=NULL M=I F=I Si no Crear nodo F Fsig =M M=F COLA DOBLE CON SALIDA REESTRINGIDA Acepta eliminaciones solo al inicio de la cola. I MF Crear I Crear F Crear M I=NULL, F= NULL , M= NULL Si I=NULL Crear Nodo I Isig1= NULL Isig2 = NULL F=I M=I

12

Si no Crear nodo F Msig1 =F Fsig2=M Fsig1=I M=F Isig2=F Solo se da de baja al inicio de la cola Solo se da de alta al final de la cola. I MF BAJA AL FINAL DE LA COLA M= Fsig2 Msig1=I Isig2 = M F=M BAJA AL PRINCIPIO DE LA COLA M=I I=Msig1 Fsig1=M Msig2=F I=M M=F UNIDAD III PILAS Una pila es un tipo de lista lineal en la que la inserción y borrado de nuevos elementos solo se pueden realizar por un extremo que se denomina tope o cima. La pila es una estructura con numerosas analogías en la vida real, una pila de platos, una pila de documentos, 13

una pila de monedas. Dado que la operación de insertar y eliminar se realizan por un solo extremo (superior) los elementos solo pueden eliminarse en un orden inverso al que se insertan en la pila. El ultimo elemento que se pone en la pila es el primero que se puede sacar; por ello a estas lista se les conoce como LIFO (Last In − first Out). 0 1 2 3 4 5 6 0 1 2 3 4 5 6 AA BB CC

BB CC AA En cualquiera de las tres formas mostradas anteriormente para representar una pila S se puede definir un vector con determinado tamaño (longitud máxima). Se considera un elemento entero P como indicador de la pila. P es el subíndice del array correspondiente al elemento cima de la pila (esto ocupa la ultima posición). Si la pila esta vacía P es igual a cero. A

B

C

...

r

l

...

1 2 3 P−1 P N−2 N−1 N CIMA LONG. (Puntero de la pila) MAX Las operaciones mas usuales asociadas a las pilas son push, que es meter o poner. Pop que es sacar o quitar, que es eliminar el elemento de la pila. Idealmente una pila puede contener un numero ilimitado de elementos y no producir nunca desbordamiento sin embargo, si hablamos de almacenamiento se hace necesario la implementación de pilas con apuntadores 14

(almacenamiento dinámico). PILAS DINAMICAS (STACK) Es la mas sencilla de las estructuras dinámicas de datos. las pilas son utilizadas sobre todo por los sistemas operativos y controladores de lenguaje de alto nivel, una pila es dinámica porque crece y se encoge a mediada que sea necesario o para trabajar con pilas es importante definir los siguientes procedimientos: PUSH.− Poner datos en la pila. POP.− sacar datos de la pila ERROR.− Pueden sacar datos de pilas vacías. NOTACIONES Las notaciones son una forma especial en la que se pueden expresar una expresión matemática y puedan ser de 3 formas: infija, prefija y posfija. Los prefijos, Pre − Pos − In se refieren a la posición relativa del operador con respecto a los dos operandos. Operandos 1+5 Operador INFIJA PREFIJA POSFIJA +15 1+5 15+ NOTACIÓN PREFIJA Nos indica que el operador va antes de los operandos sus características principales son: −Los operandos conservan el mismo orden que la notación infija equivalente. −No requiere de paréntesis para indicar el orden de precedencia de operadores ya que el es una operación. −Se evalúa de izquierda a derecha hasta que encontrémosle primer operador seguido inmediatamente de un par de operandos. −Se evalúa la expresión binaria y el resultado se cambia como un nuevo operando. Se repite este hasta que nos quede un solo resultado. * +A B C (A+B)*C NOTACION POSFIJA Como su nombre lo indica se refiere a que el operador ocupa la posición después de los operandos sus características principales son: el orden de los operandos se conserva igual que la expresión infija equivalente no utiliza paréntesis ya que no es una operación ambigua.

15

−La operación posfija no es exactamente lo inverso a la operación prefija equivalente: (A+B)*C AB+C* NOTACION INFIJA Es la forma mas común que utilizamos para escribir expresiones matemáticas, estas notaciones se refiere a que el operador esta entre los operandos. La notación infija puede estar completamente parentizada o puede basarse en un esquema de precedencia de operadores así como el uso de paréntesis para invalidar los arreglos al expresar el orden de evaluación de una expresión: 3*4=12 3*4+2=14 3*(4+2)=18 RECURSIVIDAD Las pilas se usan comúnmente para indicar en que punto se encuentra un programa cuando contiene procedimientos que se llaman a si mismos. Estos procedimientos se conocen como procedimientos recursivos. La recursividad es una técnica en la que un procedimiento o función se hace llamadas a si mismo en el proceso de realización de sus tareas. La recursividad se puede definir mediante un clásico ejemplo de la función factorial. La recursividad es una técnica de programación muy potente que puede ser usada en lugar de una iteración (Bucles o ciclos). Ello implica una forma diferente de ver las acciones repetitivas permitiendo que un subprograma se llame a si mismo para resolver una operación mas pequeña del programa original. 4!= 4*3*2*1=24 FUNCION FACTORIAL(N) 1. −Si N0 2. −N−factorial=1 3. −Si no 4. − N.factorial=N*Nfactorial(N−1) 1. − 4 No es cero por ello saltamos a la cláusula 4. −La primera llamada recursiva nos devuelve al comienzo de la función con N=2 1. −3 No es cero saltamos a la cláusula si no. 4. −La segunda llamada recursiva nos devuelve al comienzo de la función con N=2 1. −2 No es cero saltamos a la cláusula si no Nfact=2* N.fact(2−1). 4. −La tercera llamada recursiva nos devuelve al comienzo de la función con 16

N=1 1. −1 No es cero saltamos a la cláusula si no Nfact=2 * N.fact(2−1). 4. −La cuarta llamada recursiva nos devuelve al comienzo de la función con N=0 1. −Cero es igual a cero ir a al cláusula si 2. −Nfact=1. El valor de n factorial es devuelto a la sentencia llamadora a la cuarta llamada recursiva. 4. −Nfact=1 * Nfact(0)= 1*1=1 El valor de Nfact(1) es devuelto a la tercera llamada recursiva. 4. −Nfact=2 * Nfact(1)= 2*1=2 El valor de Nfact es devuelto a la segunda llamada recursiva. 4. −Nfact=3 * Nfact(2)= 3*2=6 El valor de Nfact(3) es devuelto a la primera llamada recursiva. 4. −Nfact=4 * Nfact(6)= 4*6=24 La función devuelve ahora un 24 a la sentencia llamadora original. UNIDAD IV LISTAS ENLAZADAS Los inconvenientes de las listas enlazadas se elimina con las listas enlazadas. Se pueden almacenar los elementos de una lista lineal en posiciones que no sean contiguas o adyacentes una lista enlazada es un conjunto de elementos en la que cada elemento contiene la posición o dirección del siguiente elemento de la lista cada elemento de la lista debe tener al menos dos campos. Un campo que tiene el valor del elemento y un campo que contiene la dirección del siguiente elemento es decir su posición enlace o encadenamiento a diferencia de las pilas las listas enlazadas mantienen un orden dentro de ellas. Las listas requieren un campo que será la clave por la que serán ordenadas. CARACTERÍSTICAS 1− La lista debe estar ordenada. 2− A diferencia de las pilas y las colas se pueden extraer e insertar elementos en cualquier parte de la lista. PASOS PARA CREAR UNA LISTA 1− Comprobar si esta vacía 2− Buscar la posición (orden) 3− Crear enlaces. 17

Se tienen dos casos particulares para la inserción de un elemento. 1− Insertar el nuevo nodo en el frente (principio de la lista). 2− Insertar el nuevo nodo en cualquier otro lugar de la lista. Para la eliminación de un elemento en una lista enlazada antes de proceder con la eliminación deberemos comprobar que no este vacía. También en este caso se tienen dos consideraciones particulares. 1.−El elemento a suprimir esta al principio de la lista. 2.−El elemento se encuentra en cualquier otro lugar de la lista. RECORRIDO DE UNA LISTA ENLAZADA Para recorrer una lista se utiliza una variable auxiliar tipo apuntador que se va incrementando secuencialmente de principio a fin hasta terminar el recorrido. ACCESO A UN ELEMENTO DE UNA LISTA ENLAZADA La búsqueda de información en una lista simplemente enlazada solo puede hacerse mediante un proceso secuencial o recorrido de la lista elemento a elemento, hasta encontrar la información buscada o detectar el final de la lista. UNIDAD V ARBOLES BINARIOS ARBOLES BINARIOS DE BÚSQUEDA El árbol binario de búsqueda con su estructura en árbol permite que cada nodo apunte a otros dos nodos :uno que le precede en la lista y otro que lo sigue. Los nodos apuntados pueden ser cualesquiera de la lista siempre que satisfagan esta regla básica : El nodo a la izquierda contiene un valor mas pequeño que el nodo que el nodo que le apunta y el nodo a la derecha contiene un valor mas grande. Como hemos indicado cada árbol binario tiene un único primer elemento llamado la raíz del árbol. En la figura el nodo que contiene una A es el nodo raíz. El nodo raíz puede tener un nodo a su izquierda llamado hijo izquierdo y/o un nodo a su derecha llamado su hijo derecha. Por ejemplo el nodo que contiene J tiene un hijo izquierdo conteniendo una B y un hijo derecho conteniendo una D. El nodo que contiene una A es llamado el padre de los nodos que contienen una B y D .Cualquier nodo en un árbol binario puede tener 0, 1 , 2 hijos . Un nodo sin hijos se llama hoja .Dos nodos son hermanos si tienen el mismo padre . Los nodos que contienen F y G son ambos hijos del nodo que contiene una C, por tanto son hermanos . Un nodo es un antecesor de ese nodo si es el padre de este , o el padre de algún otro antecesor de ese nodo. A BCD EFGHIJ KL

18

El nivel de un nodo se refiere a su distancia al nodo raíz . Si designamos el nivel de la raíz como 0 , los nodos que contienen B y D son nodos de Nivel 1 los nodos conteniendo F ,F , G, H , I ,J son nodos de Nivel 2. Los campos izquierdo y Derecho que contienen punteros se usaran en los algoritmos para árbol , para enlazar los datos almacenados en el árbol . Estos campos no son accedidos directamente por el usuario del árbol. El campo Info que contiene los nodos que interesan al usuario pueden ser de cualquier tipo de datos ARBOLES BINARIOS DE EXPRESIÓN Cada nodo de un árbol binario puede tener a lo sumo dos hijos; por tanto podemos representar una expresión binaria simple como un árbol binario de dos niveles. La raíz del nodo contiene el operador y los hijos contienen los operandos. 7+8 Observe que los valores están en los nodos hojas y el operador esta en su padre. Las distintas partes de una expresión complicada tienen diferentes niveles de precedencia de evaluación . Por ejemplo cuando vemos la expresión (A+B)*C sabemos que la expresión (A+B) se evalúa antes que la de multiplicación . Cuando escribimos la expresión infija con el operador entre los operandos , dependemos de algún esquema de precedencia del operador y del uso de paréntesis para describir una expresión de forma precisa . Sin embargo cuándo usamos un árbol binario para representar una expresión , los paréntesis no son necesarios para indicar la precedencia. El siguiente árbol binario representa la expresión (12−3)*(4+1) Comencemos en el nodo raíz y evaluemos la expresión . La raíz contiene el operador * , luego miramos sus hijos para obtener dos operandos como el nodo a la izquierda de la raíz contiene otro operador − sabemos que el subárbol izquierdo consta a subes de una expresión . Debemos evaluar la resta del valor del hijo derecho del nodo antes de poder realizar la multiplicación . REPRESENTACIÓN DE ARBOLES BINARIOS Los arboles binarios pueden ser representados de dos modos diferentes: −−Mediante punteros −−Mediante arrays. REPRESENTACIÓN POR PUNTEROS Cada nodo de un árbol será un registro que contiene al menos tres campos: • Un campo de datos con un tipo de datos • Un puntero al nodo subárbol izquierdo (que puede ser nulo) • Un puntero al nodo del subárbol izquierdo (que puede ser nulo). Este algoritmo seria: Struct arbol{ datos; 19

Struct arbol *ptrizq; Struct arbol *ptrder; }; RECORRIDO DE UN ARBOL BINARIO Se denomina recorrido de un árbol el proceso que permite acceder una sola vez a cada uno de los nodos del árbol. Cuando un árbol se recorre , el conjunto completo de nodos se examina. Existen muchos modos para recorrer un árbol binario . Por ejemplo existen seis diferentes recorridos generales en un árbol binario simétricos dos a dos. Los algoritmos de recorrido de un árbol binario representan tres tipos de actividades comunes: • Visitar el nodo raíz • Recorrer el subárbol izquierdo • Recorrer el subárbol derecho Estas tres acciones repartidas en diferentes ordenes proporcionan los diferentes recorridos del árbol. Los mas frecuentes tienen siempre en común recorrer primero el subárbol izquierdo y luego el subárbol derecho . Los algoritmos anteriores se llaman pre −orden , post−orden , in−orden y su nombre refleja el momento en que se visita el nodo raíz . En el inorden el raíz esta en el medio del recorrido en el pre−orden el raíz esta en el primero y en el postorden la raíz esta el ultimo: RECORRIDO PRE−ORDEN 1− Visitar el nodo raíz 2− Recorrer el subárbol derecho en pre−orden 3− Recorrer el subárbol derecho en pre−orden RECORRIDO EN−ORDEN 1− Recorrer el subárbol izquierdo en in−orden 2− Visitar la raíz 3− Recorrer el subárbol derecho en in−orden RECORRER POST−ORDEN 1− Recorrer el subárbol derecho en post−orden 2− Recorrer el subárbol derecho en postorden 3− Visitar la raíz BÚSQUEDA DE UN ELEMENTO

20

La búsqueda en un árbol binario es dicotomica , ya que a cada examen de un nodo se eliminan aquel de los subárboles que no contiene el valor buscado (Valores todos inferiores o superiores en los arboles binarios de búsqueda). El algoritmo de búsqueda del elemento −clave x− se realiza comparándolo con la clave del raíz del árbol .Si no es el mismo se pasa al subárbol izquierdo o derecho , según el resultado de la comparación y se repite la búsqueda en ese subárbol .La terminación del procedimiento se producirá cuando: • Se encuentra la clave • No se encuentra la clave ; se continua hasta encontrar un subárbol vacío. INSERTAR UN ELEMENTO Para insertar un elemento en el árbol A se ha de comprobar , en primer lugar que el elemento no se encuentra en le árbol ya que su caso no precisa ser insertado. Si el elemento existe , la inserción se realiza en un nodo en el que al menos uno de los dos punteros IZQ o DER tenga un valor de Nulo . Por la anterior condición se desciende en árbol a partir del nodo raíz , dirigiéndose de izquierda a derecha de un nodo . Cuando se alcanza un nodo en el árbol en que no se puede continuar el nuevo elemento se engancha en la izquierda o derecha de este nodo en función de que su valor sea inferior o superior al nodo alcanzado. UNIDAD VI ARBOL GENERAL TERMINOLOGÍA Y REPRESENTACIÓN DE UN ÁRBOL GENERAL La representación y terminología de los árboles se realiza con las típicas notaciones de las relaciones familiares en los árboles genealógicos: padre, hijo, hermano, ascendente, descendiente, etc. Sea el árbol general de la figura no. 1: A BCD EFGHIJ KL Terminología del árbol general: *RAIZ DEL ÁRBOL: Todos los árboles que no están vacíos tienen un único nodo raíz. Todos los demás elementos o nodos se derivan o descienden de él. El nodo raíz no tiene padre, es decir, no es el hijo de ningún elemento. *NODO: Son los vértices o elementos del árbol. *NODO TERMINAL U HOJA: Es aquel que no contiene ningún subárbol. *A cada nodo que no es hoja se asocia uno o varios subárboles llamados descendientes o hijos. De igual forma, cada nodo tiene asociado un antecesor o ascendiente llamado padre.

21

*Los nodos de un mismo padre se llaman Hermanos. *Los nodos con uno o dos subárboles no son hojas ni raíz, se llaman Nodos Interiores o Internos. *Una colección de dos o más árboles se llama bosque. *Todos los nodos tienen un solo padre (excepto el raíz) que no tiene padre. *Se denomina camino el enlace entre dos nodos consecutivos, y rama es un camino que termina en una hoja. *Cada nodo tiene asociado un número de nivel que se determina por la longitud del camino desde el raíz al nodo específico. *La altura o profundidad de un árbol es el número máximo de nodos de una rama. Equivale al nivel más alto de los nodos más 1. El pero de un árbol es el número de nodos terminales. REPRESENTACIÓN DE UN ÁRBOL GENERAL A BCD EFGHIJ KL EDH BJI AF CGK L A(B(E)) (C(F)(G(K)(L))) (D(H)(I)(J)) CONVERSIÓN DE UN ÁRBOL GENERAL EN ÁRBOL BINARIO Dado que los árboles binarios son de estructura fundamental en la teoría de los árboles, será preciso disponer de algún mecanismo que permita la conversión de un árbol general en árbol binario. Los árboles binarios son más fáciles de programar que los generales. En esto es imprescindible deducir cuántas ramas o caminos se desprenden de un nodo en un momento dado. Por ello, y dado que de los árboles binarios siempre se cuelgan como máximo dos subárboles, su programación será más sencilla. Afortunadamente, existe una técnica para convertir un árbol general a formato de un árbol binario. Ejemplo: Supongamos que se tiene el árbol A y se quiere convertir en un árbol binario B. El árbol de conversión tiene 3 22

pasos fáciles: 1. − La raíz de B es la raíz de A 2. − a) Enlazar un nodo raíz con el camino que conecta el nodo más a la izquierda (su hijo). ,. b) Enlazar éste nodo con los restantes descendientes del nodo raíz en su camino con lo que se forma el nivel 1. c) A continuación, repetir los pasos a y b con los nodos del nivel 2, enlazando siempre en un mismo camino todos los hermanos (descendientes del mismo nodo). Repetir estos pasos hasta llegar al nivel más alto. 3.− Girar el diagrama resultante 45° para diferenciar entre los subárboles izquierdos y derecho. Ejem: TT AA BB CC DD EE RECORRIDO DE UN ÁRBOL GENERAL Los métodos de recorridos de los árboles generales inducen a métodos de recorridos para el caso de bosques. Los métodos de recorridos de un bosque como preorden, inorden o posorden pueden ser definidos como los recorridos de preorden, inorden o posorden de sus correspondientes árboles generales. Si un bosque es representado como un conjunto dinámico de nodos variables con punteros del tipo hijo y siguiente en la forma presentada arriba, una rutina en PASCAL que imprima los contenidos de sus nodos en una rutina de inorden se puede escribir como sigue: Procedure intrav (p:ndptr); Begin If p<> nil Then with p Do begin Intrav(son); Writeln(info); 23

Intrav(next) End {withdo begin} End {termina procedure intrav}; Las rutinas de recorrido de entreorden y posorden son similares. Los recorridos de un bosque pueden ser definidos también en una forma directa como siguen: Preorden 1− Visite la raíz del primer árbol en el bosque. 2− Recorra en preorden el bosque formado por los subárboles del primer árbol, si exite alguno. 3− Recorra en preorden el bosque formado por lo árboles restantes en el bosque, si existe alguno. Entreorden 1− Recorra en entreorden el bosque formado por los subárboles del primer árbol del bosque, si exite alguno. 2− Visite la raíz del primer árbol. 3− Recorra en entreorden el bosque formado por los árboles restantes del bosque, si existe alguno. Posorden 1− Recorra en posorden el bosque formado por los subárboles del primer árbol del bosque, si existe alguno. 2− Recorra en posorden el bosque formado por los árboles restantes del bosque, 3− Visite la raíz del primer árbol del bosque. CONVERSION DE ÁRBOL GENERAL EN UN ÁRBOL BINARIO. A BCD EFGHIJ KL PASO 1: A

24

BCD EFGHIJ KL PASO 2: A B EC FD GH KI LJ Trabajo realizado por: AL1EN Para: Alienweb Unidimensional Bidimensional Tridimensional 0−juan 1−pepe 2−chano 3−jelipe 4−ermenegildo 5−federico 6−josefina 25634 Función Hash Clave =4531126034

25

+ Clave=325671234 : Clave=110000345 Clave=467123326 72588495 7 153400003 Función Hash Usar cubo 3 Nombre Edad Sueldo Nombre Edad Sueldo Nombre Edad Sueldo 100 264 119 48 CIMA=2 CIMA=2

26

E M P A 8 12 3 − * 4 1 + 00 556677003 01 Función Hash 02 03 Usar cadena 03 : 99 : | 6536614001 | 123450003 | 556677003 | 010223099

27