Download Estructura de Datos
Document related concepts
no text concepts found
Transcript
UNIVERSIDAD AUTONOMA DE GUERRERO UNIDAD ACADEMICA DE MATEMATICAS Academia de Computación No. 001 Apuntes de ESTRUCTURA DE DATOS Serie: Material de Apoyo a la Licenciatura en Matemáticas (Área: Computación). Estos apuntes fueron desarrollados a partir de la experiencia obtenida impartiendo la materia y la bibliografía citada al final del mismo; su propósito es servir como apoyo al curso de Estructura de Datos que se imparte en la Licenciatura en Matemáticas (Área: Computación). Su publicación no persigue fines de lucro, está destinada al uso interno en la Unidad Académica de Matemáticas de la Universidad Autónoma de Guerrero. agosto de 2004 Edgar Altamirano Estructura de Datos pag. 2 Contenido. Introducción. 2 Primera parte: Estructuras Elementales. 1. Estructuras Elementales de Datos. 4 Segunda parte: Estructuras Secuenciales. 2. Arreglos. 3. Pilas y Colas. 22 35 Tercera Parte: Estructuras Ligadas. 4. Listas. 5. Arboles. 44 63 Bibliografía. 72 UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 3 Introducción. Los datos proporcionados a la computadora se pueden representar dentro de la computadora en múltiples formas, tal representación se conoce como estructura de los datos; desde el punto de vista de la programación podemos entender una estructura de datos como una colección de datos cuya organización se caracteriza por las funciones de acceso que se usan para almacenar y acceder a elementos individuales de datos. Las estructuras de datos las podemos organizar para su estudio en estructuras elementales (su manipulación y representación se ha venido estandarizando en los lenguajes de programación y pueden casi siempre manejarse con instrucciones a nivel de lenguaje de máquina en forma directa) y estructuras compuestas que se construyen a partir de las estructuras elementales y cuya manipulación requiere del ingenio de los programadores; el estudio de las estructuras compuestas se puede a su vez dividir en estructuras secuencials ó ligadas según que los datos estén almacenados consecutivamente (ocupando siempre espacios consecutivos de memoria) ó en forma 'ligada' (pueden no ocupar espacios consecutivos pero siempre existirá una 'liga' entre ellos. Número Enteros Números Reales Elementales Caracteres Valores Lógicos Estructuras de Datos Punteros Arreglos Lineales Compuestas Listas No Lineales Archivos UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 4 1. Estructuras elementales de datos. En éste capítulo se describen las representaciones básicas de las estructuras elementales en la memoria de la computadora. Estas estructuras forman una base para la composición y discusión de estructuras más complejas que se analizarán en los siguientes capítulos. 1.1. Representación de Números Enteros. Un número entero es cualquier número que pertenece al conjunto definido como: Entero = {... , -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, ...} Ejemplos de números enteros : -8, -72, 0, 4, 100 Para representar números en la computadora digital se utiliza el sistema de numeración binaria ó de base 2 porque la tecnología que se usa para la memoria permite solamente el uso de dos dígitos: 0 y 1. En la computadora se representan dos clases de números enteros: con signo (se asume que todos los números tienen magnitud 0 ó son positivos) y sin signo (los números pueden ser positivos ó negativos y el signo del número también tiene que representarse). Números Enteros Sin Signo. (a). Método de Representación Binaria. Un número entero sin signo puede representarse por una secuencia de dígitos binarios de la forma: dn dn-1 ... d2 d1 d0 su valor ó magnitud se determina por la suma de: dn bn + dn-1 bn-1 + ... + d2 b2 + d1 b1 + d0 b0 donde b es la base o raíz del sistema. UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 5 Ejemplos. La magnitud del número 12410 es la suma de los términos: 1 x 102 + 2 x 101 + 4 x 100 La magnitud del número 101112 es la suma de los términos : 1 x 24 + 0 x 2 3 + 1 x 22 + 1 x 21 + 1 x 20 Para trasladar un número entero sin signo a su correspondiente representación binaria se puede usar el algoritmo conocido como de divisiones sucesivas entre dos : Ejemplo. Encontrar la representación binaria del número 16 8 2 16 0 2 4 8 0 2 2 4 0 2 1 2 0 2 0 1 1 . .. 16 = 10000 10 2 Para convertir un número de su representación binaria a decimal se puede llevar a cabo encontrando su magnitud del modo siguiente: Ejemplo. Encontrar la representación decimal del número cuya representación binaria es 100002 100002 = 1 x 24 + 0 x 23 + 0 x 22 + 0 x 21 + 0 x 20 100002 = 16 + 0 + 0 + 0 + 0 100002 = 1610 En el sistema de números binarios cada posición del bit representa una potencia de dos : UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos Sistema de Números Binarios pag. 6 Sistema Decimal 20 21 22 23 24 25 26 27 28 ... 1 10 100 1,000 10,000 100,000 1,000,000 10,000,000 100,000,000 ... Debido a lo anterior, una cadena de bits de longitud n servirá para representar un entero no negativo entre 0 y 2n-1. A esta propiedad la denominamos rango de representación decimal. Ejemplo. Una variable de tipo byte sin signo, utiliza un byte para el almacenamiento de la información, por lo tanto, su rango de representación decimal es : 0 a 28-1 = 255. (b). Convención BCD (Binary Coded Decimal). Se utilizan cuatro bits para representar cada dígito decimal entre 0 y 9 : 0 1 2 9 0000 0001 0010 1001 3 0011 4 0100 5 0101 6 0110 7 0111 8 1000 así, una hilera de longitud arbitraria, se puede dividir en grupos de cuatro bits consecutivos, donde cada grupo representa un dígito decimal; ésta representación tiene la ventaja de permitir realizar las operaciones aritméticas directamente debido a su interface directa con la representación decimal. Ejemplo. Represente el número entero 26 mediante la convención BCD. 2610 = 0010 01102 UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 7 Ejemplo. Escriba un programa que sirva para encontrar la representación binaria de un número entero sin signo utilizando el algoritmo de divisiones sucesivas entre dos. /*------------------------------------------------*/ /* db.c */ /* Muestra la representacion binaria de un numero */ /* decimal entre 1 y 255. */ /*------------------------------------------------*/ #include <stdio.h> #include <conio.h> /*------------------------------------------------*/ void main(void) { int i,j, binario, decimal; char digitos[20]; clrscr(); printf("CONVIERTE DECIMAL A BINARIO\n"); do { printf("(Rango permitido : 1 a 255)\n"); printf("Numero Decimal : "); scanf("%d", &decimal); } while (decimal < 1 || decimal > 255); i = 0; while (decimal > 0) { binario = decimal % 2; /* residuo de la division entera */ decimal = decimal / 2; /* cociente de la division */ digitos[i++] = binario; } printf("Numero Binario : "); for (j = --i; j >= 0; j--) printf("%1d", digitos[j]); printf("\n"); } UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 8 Números enteros con signo. Para representar en la computadora cuando un número entero es positivo ó negativo, se han establecido convenciones como las siguientes : (a). Convención de Signo y Magnitud. Se escribe el signo "+" ó "-" junto a la magnitud del número. En la computadora se utiliza generalmente el dígito binario de la extrema izquierda para denotar el signo y los restantes para denotar la magnitud. Para representar la magnitud se utiliza el sistema de números binarios. Ejemplo. Si Consideramos el caso de poder utilizar solamente cuatro dígitos binarios para la representación tendríamos las posibilidades siguientes: Número Positivo +0 +1 +2 +3 +4 +5 +6 +7 Signo y Magnitud Número Negativo Signo y Magnitud 0 000 -0 1 000 0 001 -1 1 001 0 010 -2 1 010 0 011 -3 1 011 0 100 -4 1 100 0 101 -5 1 101 0 110 -6 1 110 0 111 -7 1 111 (b). Convención del Complemento a uno. Los números positivos se representan igual que con la convención de signo y magnitud pero los números negativos se obtienen invirtiendo los bits de su representación positiva. Ejemplo. Si Consideramos el caso de poder utilizar solamente cuatro dígitos binarios para la representación tendremos las posibilidades siguientes : UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos Número Positivo +0 +1 +2 +3 +4 +5 +6 +7 pag. 9 Complemento a 1 Número Negativo Complemento a 1 0 000 -0 1 111 0 001 -1 1 110 0 010 -2 1 101 0 011 -3 1 100 0 100 -4 1 011 0 101 -5 1 010 0 110 -6 1 001 0 111 -7 1 000 (c). Convención del Complemento a dos. Esta convención reconoce que el número cero es único y debe por lo tanto tener una representación única. Para representar un número en complemento a dos se parte del principio de asignar la mitad de las combinaciones posibles a los números positivos y la otra mitad a los negativos. Se considera el número 0 como positivo. Ejemplo. Si Consideramos el caso de poder utilizar también solamente cuatro dígitos binarios para la representación tendríamos las posibilidades siguientes : Número Positivo +0 +1 +2 +3 +4 +5 +6 +7 Complemento a 2 Número Negativo Complemento a 2 0 000 -8 1 000 0 001 -7 1 001 0 010 -6 1 010 0 011 -5 1 011 0 100 -4 1 100 0 101 -3 1 101 0 110 -2 1 110 0 111 -1 1 111 Los números positivos se representan igual que con la convención de signo y magnitud siempre y cuando no rebasen (overflow) la capacidad de representación; pero la representación de los números negativos se obtiene mediante la expresión : C = b - |Número|, donde C es la representación del número en "n" dígitos de la base "b" y |Número| es la magnitud (valor absoluto) del número negativo. UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 10 Ejemplo. Represente el número 1 como negativo en complemento a dos, utilizando cuatro dígitos binarios. C = bn - |Número| (b10)n = (210)4 = 1610 = 100002 |Número| = 110 = 00012 C = 100002 - 00012 = 11112 Nota. Conversión decimal a binario : 8 2 16 0 2 4 8 0 2 2 4 0 2 1 2 0 2 0 1 1 . .. 16 = 10000 10 2 Resta binaria: 100002 - 00012 = 11112 0 1 1 (10) 0 0 1 (10) 0 0 1 (10) 0 0 (10) 0 1 0 1 1 1 1 Otra manera más sencilla de representar números negativos en complemento a dos, es encontrar su representación positiva en el sistema de números binarios, invertirla (igual que en complemento a uno) y sumarle un '1'. Ejemplo. Represente el número uno como negativo en complemento a dos, utilizando cuatro dígitos binarios: Representación binaria : Complemento a uno : Sumar un '1' : 0001 1110 + 0001 Rep. en Compl. a dos : 1111 UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 11 1.2. Representación de Números Reales. Notación de Punto Fijo. Un número real, en cualquier base R puede representarse como: AR = ( An An-1 An-2 ... A1 A0 . A-1 A-2 ... A-(m+1) A-m ) esta notación se llama de punto fijo y tiene la desventaja de requerir una gran cantidad de bits para representar cantidades como 0.00000000000827 ó 18700000000000.0; por ejemplo, para obtener una precisión de 27 dígitos decimales se necesitarán aproximadamente 90 dígitos binarios. El formato para almacenar éste tipo de números es: POSICION DEL PUNTO DECIMAL DATO NUMERICO Notación de Punto Flotante. Un número real, en cualquier base R se representa como: . f-1 f-2 f-3 ... f-m x RE donde f-1 f-2 f-3 ... f-m es llamada la parte fraccionaria ó mantisa, "E" es un número entero conocido como exponente y "R" es la base. Ejemplo. El número 3.141592 se puede representar como : 3.141592 = + 0.3141592 x 10+1 Para representar un número real en notación de punto flotante, el formato más usado en los lenguajes de programación es : S EXPONENTE MANTISA MANTISA UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 12 en donde S es el signo de la mantisa, EXPONENTE es el exponente representado como número entero en complemento a dos y MANTISA es la mantisa representada como número entero en magnitud y signo. Para aumentar la precisión de un número es posible asignar optativamente más palabras de computadora para la mantisa, llamándose entonces número de doble precisión: S EXPONENTE MANTISA MANTISA MANTISA MANTISA Ejercicios. 1. Considere el caso de utilizar nueve dígitos binarios para la representación de números enteros : a). En notación de complemento a dos, ¿cuál es el mayor número positivo que se puede representar y cuál es el menor número negativo ? b). Igual al inciso (a) pero usando la convención de signo y magnitud. c). Igual al inciso (a) pero usando la notación de complemento a uno. d). Para la notación en complemento a dos, represente los números 8 y 19 como negativos utilizando la expresión : C = bn - | número | 2. Para representar números reales del tipo : 0 . f-1 f-2 f-3 ... f-m x RE se utiliza el siguiente formato : UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos mantisa bit : 0 pag. 13 exponente 11 12 15 la mantisa está representada en magnitud y signo y el exponente en complemento a dos. a). ¿ cuál es el mayor número positivo que se puede representar ? b). ¿ el mayor número negativo ? c). ¿ el menor número positivo ? d). ¿ el menor número negativo ? e). ¿ el rango de representación ? f). ¿ la precisión de la mantisa en dígitos decimales ? 1.3 Representación de cadenas de caracteres. Representación de caracteres. Entendemos por caracter, la expresión literal de algún elemento tomado de un alfabeto ó conjunto de signos. Cada caracter se puede representar con un patrón de bits diferente que lo identifica. Entre los fabricantes de computadoras se ha generalizado que un conjunto de caracteres se codifique en secuencias de bits con longitud fija. En general tenemos que x = 2 caracteres se pueden representar utilizando secuencias de bits de longitud n. Por tanto, con n = 6, 7 y 8 podemos codificar hasta 64, 128 y 256 caracteres respectivamente. Algunos de los códigos más importantes que actualmente se emplean para la representación de letras, números y símbolos especiales son : ASCII ( American Standard Code for Information Interchange) el cual requiere 8 bits para representar cualquier caracter; BCD (Binary Coded Decimal) que requiere de 6 bits para representar cualquiera de sus 64 caracteres; y EBCDIC (Extended BCD Interchange Code) que es un código de 8 bits. UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 14 Ejemplo. Representación de letras y números para los códigos BCD, EBCDIC y ASCII. Símbolo BCD EBCDIC ASCII blanco A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 0 1 2 3 4 5 6 7 8 9 110 000 010 001 010 010 010 011 010 100 010 101 010 110 010 111 011 000 011 001 100 001 100 010 100 011 100 100 100 101 100 110 100 111 101 000 101 001 110 010 110 011 110 100 110 101 110 110 110 111 111 000 111 001 000 000 000 001 000 010 000 011 000 100 000 101 000 110 000 111 001 000 001 001 0100 0000 1100 0001 1100 0010 1100 0011 1100 0100 1100 0101 1100 0110 1100 0111 1100 1000 1100 1001 1101 0001 1101 0010 1101 0011 1101 0100 1101 0101 1101 0110 1101 0111 1101 1000 1101 1001 1110 0010 1110 0011 1110 0100 1110 0101 1110 0110 1110 0111 1110 1000 1110 1001 1111 0000 1111 0001 1111 0010 1111 0011 1111 0100 1111 0101 1111 0110 1111 0111 1111 1000 1111 1001 0010 0000 0100 0001 0100 0010 0100 0011 0100 0100 0100 0101 0100 0110 0100 0111 0100 1000 0100 1001 0100 1010 0100 1011 0100 1100 0100 1101 0100 1110 0100 1111 0101 0000 0101 0001 0101 0010 0101 0011 0101 0100 0101 0101 0101 0110 0101 0111 0101 1000 0101 1001 0101 1010 0011 0000 0011 0001 0011 0010 0011 0011 0011 0100 0011 0101 0011 0110 0011 0111 0011 1000 0011 1001 UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 15 Representación de Cadenas de Caracteres. Una secuencia de caracteres ó cadena, se representa en memoria generalmente utilizando una secuencia de localizaciones de almacenamiento. Las cadenas pueden ser de longitud fija, longitud cambiante y longitud variable. (a). Longitud Fija. La cantidad de almacenamiento requerida por una cadena de longitud fija se conoce al momento de crear la cadena. Por ejemplo, en PL/I : declare S character (6) initial ('*A1'); en una computadora con palabras de cuatro bytes, implica la creación de la cadena : * A 1 '' '' '' | no se usa | (b). Longitud Cambiante. Para una cadena de longitud cambiante, su longitud máxima se conoce también en el momento de su creación; en ése momento se dispone de suficiente espacio de almacenamiento para guardar hasta un máximo número de caracteres junto con un campo que contiene la longitud actual de la cadena: declare S character (6) varying initial ('*A1'); resulta en la siguiente distribución de almacenamiento: 3 * A 1 | disponible | (c). Longitud Variable. La cadena de longitud variable es más dinámica y poderosa, en este caso, en el momento de la creación no se necesita conocer ni su longitud precisa ni su máxima longitud; la estructura de almacenamiento para este tipo de cadena se maneja en dos formas: con delimitadores y descriptores de cadena : UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 16 Ejemplo. Longitud variable con delimitadores : ^ * A 1 ^ | no se usa | Ejemplo. Longitud variable con descriptores de cadena : 3 [22] * A 1 | no se usa | 1.4 Valores Lógicos. Una entidad de datos lógica es una estructura primitiva de datos que puede asumir dos tipos de valores: verdadero y falso. La representación en memoria de valores lógicos depende directamente del traductor de lenguaje que procese el programa y de la máquina para la cual se diseñó el traductor. El modo más obvio y eficiente que puede ser aplicado para almacenar datos lógicos es la utilización de un bit. Si el bit está prendido (1) representa el valor verdadero, y si está apagado (0), el valor falso. Sin embargo la mayoría de las máquinas no disponen de instrucciones para accesar un bit determinado de la memoria, consecuentemente, se adoptan otras representaciones, por ejemplo, asignar una palabra completa de memoria representando los valores lógicos con todos los bits prendidos ó apagados : TODOS LOS BITS APAGADOS FALSO TODOS LOS BITS PRENDIDOS VERDADERO UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 17 1.5 Apuntadores. Un apuntador ó puntero es una referencia a una estructura de datos. Su característica más importante es que aporta un método homogéneo para referenciar cualquier estructura de datos sin importar su tipo ó complejidad. Otra característica muy importante es la de que permiten rápidas inserciones y eliminaciones de elementos en una estructura de datos. APUNTADOR ESTRUCTURA DE DATOS La dirección contenida en un apuntador puede referenciar una estructura de datos en dos modos: dirección absoluta ó dirección relativa. La dirección absoluta implica que el valor contenido en el apuntador es una localización absoluta de memoria en la cual puede comenzar a residir una estructura de datos. Una dirección relativa es en cambio un valor comprendido para una región de memoria que tiene una localización base. Por ejemplo, si el valor de un apuntador relativo es 5 y la localización base para el área de datos de un programa es 7627, entonces la dirección real del apuntador es 7627 + 5 = 7632. UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 18 1.6. El Código ASCII en el IBM-PC. El IBM PC utiliza el código ASCII extendido a 8 bits; por lo tanto se pueden representar 256 caracteres diferentes; éstos caracteres son : a). Los primeros 32 caracteres (0 a 31) son caracteres de control como return, escape, nulo; son caracteres no imprimibles. b). Los siguientes caracteres (32 a 127) son letras, dígitos numéricos y símbolos de puntuación normal; son caracteres imprimibles. c). La última parte (128 a 255) son caracteres especiales de otros alfabetos y algunos caracteres gráficos, los cuales pueden obtenerse en la pantalla utilizando el teclado numérico de la derecha del teclado mientras se mantiene pulsada simultáneamente la tecla ALT. Por ejemplo, Alt-224 produce el caracter griego ''; son caracteres imprimibles. El teclado del IMB PC genera el código ASCII para letras, números y símbolos de puntuación. Sin embargo, existen teclas (F1, F2, ...) y combinaciones de teclas (Ctrl-F1, Alt-PgUp, ...) no representadas en el código ASCII. Para éstos casos el IBM PC utiliza otro byte para formar lo que se conoce como código extendido de dos bytes : el primer byte es 0 y el segundo es el código de la tecla ó combinación de teclas. Cuando se oprime una tecla del conjunto normal de caracteres, se genera el código ASCII correspondiente. Cuando se oprime una tecla ó combinación de teclas que no forman parte del conjunto normal de caracteres, se generan dos códigos, el primero es un 0 y el segundo es el código extendido correspondiente dentro del buffer del teclado. El buffer del teclado es un área de almacenamiento temporal donde se almacenan los códigos de las teclas oprimidas hasta que son leídas por un programa. Un programa que sea capaz de entender cuáles teclas se han pulsado, debe revisar si el primer caracter recibido es un cero, si lo es, se trata de una tecla especial ó combinación de teclas y se debe leer el siguiente caracter. Si el primer caracter no es cero, se trata entonces de una Tecla normal y debe procesarse como tal. UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos /*------------------------------------------------------------------ascii.c imprime la tabla ascii ----------------------------------------------------------------------*/ #include <stdio.h> #include <conio.h> /*--------------------------------------------------------------------*/ void main(void) { unsigned char c = 0; printf("\n\tdec\toctal\thexad\tcar"); for (;;) { if (c < 32) printf("\n\t%d\t%o\t%x\t\tcaracter de control", c, c, c); else if (c > 47 && c < 58) printf("\n\t%d\t%o\t%x\t%c\tnúmero", c, c, c, c); else if (c > 64 && c < 91) printf("\n\t%d\t%o\t%x\t%c\tmayúscula", c, c, c, c); else if (c > 96 && c < 123) printf("\n\t%d\t%o\t%x\t%c\tminúscula", c, c, c, c); else printf("\n\t%d\t%o\t%x\t%c", c, c, c, c); c++; if (c == 0) break; else if (c%24 == 0) { getch(); clrscr(); printf("\n\tdec\toctal\thexad\tcar"); } } } UNIDAD ACADEMICA DE MATEMATICAS, UAG pag. 19 Estructura de Datos pag. 20 Valores en Decimal del Segundo Caracter (Código Extendido). tecla F1 F5 F9 Shift F1 Shift F5 Shift F9 Ctrl F1 Ctrl F5 Ctrl F9 Alt F1 Alt F5 Alt F9 Alt 1 Alt 5 Alt 9 Alt Alt C Alt G Alt K Alt O Alt S Alt W Home End Ins Ctrl PtrSc Ctrl Home código tecla 59 63 67 84 88 92 94 98 102 104 108 112 120 124 128 130 46 34 37 24 31 17 71 79 82 114 119 F2 F6 F10 Shift F2 Shift F6 Shift F10 Ctrl F2 Ctrl F6 Ctrl F10 Alt F2 Alt F6 Alt F10 Alt 2 Alt 6 Alt 0 Alt = Alt D Alt H Alt L Alt P Alt T Alt X Del Ctrl Ctrl código tecla 60 64 68 85 89 93 95 99 103 105 109 113 121 125 129 131 32 35 38 25 20 45 72 80 83 115 116 código tecla código F3 F7 61 65 F4 F8 62 66 Shift F3 Shift F7 86 90 Shift F4 Shift F8 87 91 Ctrl F3 Ctrl F7 96 100 Ctrl F4 Ctrl F8 97 101 Alt F3 Alt F7 106 110 Alt F4 Alt F8 107 111 Alt 3 Alt 7 122 126 Alt 4 Alt 8 123 127 Alt A Alt E Alt I Alt M Alt Q Alt U Alt Y PgUp PgDn Shift Tab Ctrl End Ctrl PgUp 30 18 23 50 16 22 21 73 81 15 117 132 Alt B Alt F Alt J Alt N Alt R Alt V Alt Z 48 33 36 49 19 47 44 75 77 UNIDAD ACADEMICA DE MATEMATICAS, UAG Ctrl PgDn 118 Estructura de Datos /*------------------------------------------------------------------------------teclas.c Reconoce que teclas se pulsan, incluyendo las teclas especiales. -----------------------------------------------------------------------------------*/ #include <stdio.h> #include <conio.h> char c; /*------------------------------------------------*/ void main(void) { clrscr() printf("RECONOCEDOR DE TECLAS"); do { printf("Pulse cualquier tecla ('f' para terminar) : "); c = getch(); if (c == 0) { /* pulso una tecla especial */ c = getch(); switch (c) { case 59 : printf("pulso <F1>"); break; case 60 : printf("pulso <F2>"); break; case 84 : printf("pulso <Shift-F1>"); break; case 94 : printf("pulso <Ctrl-F1>"); break; case 104 : printf("pulso <Alt-F1>"); break; case 132 : printf("pulso <Ctrl-PgUp>"); break; default : printf(""); } } else { /* pulso una tecla ordinaria */ switch (c) { case 13 : printf("pulso <CR>"); break; case 27 : printf("pulso <ESC>"); break; case 65 : printf("pulso <A>"); break; case 97 : printf("pulso <a>"); break; case 102 : printf("pulso <f>"); break; default : printf(""); } } } while (c != 'f'); } UNIDAD ACADEMICA DE MATEMATICAS, UAG pag. 21 Estructura de Datos pag. 22 2. Arreglos. Estudiaremos a partir de ahora las estructuras de datos compuestas desde tres niveles : Nivel Abstracto ó Lógico. Es decir, como una colección abstracta de elementos con un conjunto particular de funciones de accesos. En este nivel, se dibuja la organización y se especifican los procedimientos y funciones generales de acceso. Nivel de Implementación. Es decir, como un problema de codificación ( ¿ cómo se implementarán las funciones de acceso ? ). En este nivel, se examinan las formas de representación de los datos en memoria y cómo implementar los procedimientos y funciones de acceso. Nivel de Aplicación. Es decir, como una forma de representar las relaciones entre los datos en un contexto específico. En este nivel, se diseñan ejemplos de aplicación en los que la estructura de datos representa con precisión las relaciones entre los datos. Una estructura de datos compuesta consiste de una colección de nodos que mantienen importantes relaciones entre sí : nodo 2 nodo 1 nodo 4 nodo 3 UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 23 El nodo es elemento básico para mantener la información en la estructura de datos. Para representar la información contenida en un nodo se pueden utilizar una ó más palabras de computadora dependiendo de las características de los datos. Un nodo puede dividirse en campos conteniendo estructuras elementales : campo 1 campo 2 campo 3 campo n ... 2.1. Arreglos: nivel lógico. Un arreglo es una estructura de datos con un número fijo de nodos. Al conjunto de nodos se le identifica con un nombre y a los nodos con un índice. En un arreglo se pueden practicar todas las operaciones relativas a la información contenida en los nodos (extracción y almacenamiento) pero no aquéllas relativas a alterar el número de nodos (suprimir y agregar). En la figura 2.1 se muestra la organización de arreglos de una, dos y tres dimensiones. 1 2 3 4 5 6 4 3 2 A[ I ] 1 2 3 1 4 5 6 1 1 2 2 3 3 4 4 5 6 5 6 1 2 A[ I, J ] 3 4 5 6 A[ I, J, K ] Figura 2.1. Arreglos de una, dos y tres dimensiones. UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 24 Funciones de Acceso. Se utiliza una única función en dos formas: (1). Almacenamiento. Para especificar un lugar en el que ha de copiarse un valor. Por ejemplo, en el lenguaje C : A[i] = <Expresión>; A[i, j] = <Expresión>; A[i, j, k] = <Expresión>; (2). Extracción. Para especificar un lugar del que ha de extraerse un valor. Por ejemplo, en C : <Nombre_de variable> = A[i]; <Nombre_de variable> = A[i, j]; <Nombre_de variable> = A[i, j, k]; 2.2. Implementación de arreglos. Se deben observar dos cosas para lograr la implementación de cualquier estructura de datos: reservar memoria para la estructura de datos y codificar las funciones de acceso. Un arreglo puede organizarse en la memoria de dos formas: organización contigua y organización ligada. Analizaremos únicamente la organización contigua. UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 25 Organización Contigua. Los elementos del arreglo ocupan localidades contiguas de la memoria. En este caso la recuperación de cualquier elemento del arreglo puede hacerse básicamente sobre dos esquemas: 1) funciones de mapeo, y 2) tablas de recuperación. Estudiaremos únicamente las funciones de mapeo. Funciones de Mapeo. Una función de mapeo es una expresión que permite calcular la dirección de un nodo en función de sus índices. Para un arreglo unidimensional A[i], que está limitado inferior y superiormente por b1 i u1 , ésta función estará dada por : DIR(A[i]) = L + (i - b1) * c donde L es la dirección base del arreglo A (dirección en memoria de la primera palabra del primer elemento del arreglo A), c representa el número de palabras de memoria asignadas a cada elemento y b es la cota inferior del índice del arreglo. Por facilidad para la exposición supondremos de ahora en adelante que c = 1. Para un arreglo bidimensional A[i,j] limitado tanto inferior como superiormente por: b1 i u1 y b2 j u2 la dirección en memoria del elemento A[i,j] estará dada por : 1) si está almacenado por renglón ( i ) : DIR(A[i,j]) = L + (i - b1) * (u2 - b2 + 1) + (j - b2) 2) si está almacenado por columna ( j ) : DIR(A[i,j]) = L + (j - b2) * (u1 - b1 + 1) + (i - b1) UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 26 Ejemplo. Un arreglo bidimensional se puede almacenar por renglón y por columna, teniendo los subíndices de renglones y columnas los siguientes límites : 3 i 8 y -5 j 0 obtenga una función para localizar la posición de almacenamiento del elemento A[i,j] si se almacena por renglón ó por columna, suponiendo en ambos casos que el primer elemento del arreglo se almacenará en la posición L. Solución. n = 2 (bidimensional). b1 = 3 u1 = 8 b2 = -5 u2 = 0 por renglón : DIR(A[i,j]) = L + (i - b1) * (u2 - b2 + 1) + (j - b2) DIR(A[i,j]) = L + (i - 3) * (0 + 5 + 1) + (j + 5) DIR(A[i,j]) = L + 6(i-3) + (j+5) para localizar A[3,-4] : DIR(A[3,-4]) = L + 6(3-3) + (-4+5) = L + 0 + 1 = L + 1 por columna : DIR(A[i,j]) = L + (j - b2) * (u1 - b1 + 1) + (i - b1) DIR(A[i,j]) = L + (j + 5) * (8 - 3 + 1) + (i - 3) DIR(A[i,j]) = L + 6(j+5) + (i-3) para localizar A[3,-4] : DIR(A[3,-4]) = L + 6(-4+5) + (3-3) = L + 6 + 0 = L + 6 Para un arreglo tridimensional A[i,j,k] limitado tanto inferior como superiormente por: b1 i u1 , b2 j u2 y b3 k u3 , la dirección en memoria del elemento A[i,j,k] es: UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 27 1) si está almacenado por renglón ( i ) : DIR(A[i,j,k]) = L + (i - b1) * (u2 - b2 + 1) * (u3 - b3 + 1) + (j - b2) * (u3 - b3 + 1) + (k - b3) 2) si está almacenado por la profundidad ( k ) : DIR(A[i,j,k]) = L + (k - b3) * (u2 - b2 + 1) * (u1 - b1 + 1) + (j - b2) * (u1 - b1 + 1) + (i - b1) Ejemplo. Considere un arreglo tridimensional 'X' almacenado por renglón, teniendo los subíndices los siguientes límites : 1 i 3 1 j 3 -1 k 0 obtenga una expresión para localizar la posición de un elemento cualquiera X[i,j,k] suponiendo que la localización base del arreglo es L. Pruebe localizando el elemento X[1,1,-1]. Solución. n = 3 (tridimensional). b1 = 1 b2 = 1 b3 = -1 u1 = 3 u2 = 3 u3 = 0 DIR(X[i,j,k]) = = = = = L + (i-1)(3-1+1)(0+1+1) + (j-1)(0+1+1) + (k+1) L + (i-1)(3)(2) + (j-1)(2) + (k+1) L + 6(i-1) + 2(j-1) + (k+1) L + 6i - 6 + 2j - 2 + k + 1 L + 6i + 2j + k -7 DIR(X[1,1,-1]) = L + 6(1) + 2(1) + (-1) - 7 = L+6+2-1-7 = L UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 28 Para un arreglo n-dimensional, donde b1 s1 u1 , b2 s2 u2 , b3 s3 u3 , . . . , bn s n un si está almacenado por renglón, tendremos : DIR(A(s1,s2,...,sn) = L + (s1-b1) * (u2-b2+1) * (u3-b3+1) * . . . * (un-bn+1) + (s2-b2) * (u3-b3+1) * . . . * (un-bn+1) ... + (sn-1-bn-1) * (un-bn+1) + (sn-bn) ésta función puede reescribirse en la siguiente forma : DIR(A[s1,s2,...,sn]) = L + Pi (si-bi) 1 j n donde Pi = (uj - bj + 1) ijn para bi si u i Ejemplo. Considere el siguiente arreglo de cinco dimensiones : A[1..3, 3..5, 1..10, 1..6, 1..3] si el arreglo se almacena por renglón, y su localización base es L, encuentre la localización en memoria del elemento A[1,3,1,1,1]. Solución. n = 5 (cinco dimensiones). b1 = 1 b2 = 3 b 3 = 1 b4 = 1 b 5 = 1 u1 = 3 u2 = 5 u3 = 10 u4 = 6 u5 = 3 UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 29 DIR(A[s1, s2, s3, s4, s5]) = L + Pi (si-bi) 1 j 5 DIR(A[s1, s2, s3, s4, s5]) = L + P1(s1 - b1) + P2(s2 - b2) + P3 (s3 - b3) + P4(s4 - b4) + P5(s5 - b5) P1 = (uj - bj + 1) = (u2 - b2 + 1)(u3 - b3 + 1)(u4 - b4 + 1)(u5 - b5 + 1) 1 j 5 P2 = (uj - bj + 1) = (u3 - b3 + 1)(u4 - b4 + 1)(u5 - b5 + 1) 2 j 5 P3 = (uj - bj + 1) = (u4 - b4 + 1)(u5 - b5 + 1) 3 j 5 P4 = (uj - bj + 1) = (u5 - b5 + 1) 4 j 5 P5 = (uj - bj + 1) = 1 5 j 5 DIR(A[s1, s2, s3, s4, s5]) = L + (s1-b1)(u2-b2+1)(u3-b3+1)(u4-b4+1)(u5-b5+1) + (s2-b2)(u3-b3+1)(u4-b4+1)(u5-b5+1) + (s3-b3)(u4-b4+1)(u5-b5+1) + (s4-b4)(u5-b5+1) + (s5-b5)(1) DIR(A[s1, s2, s3, s4, s5]) = L + (s1 - 1)(5-3+1)(10-1+1)(6-1+1)(3-1+1) + (s2 - 3)(10-1+1)(6-1+1)(3-1+1) + (s3 - 1)(6-1+1)(3-1+1) + (s4 - 1)(3-1+1) + (s5 - 1) DIR(A(s ,s ,s ,s ,s )) = L + (s -1)(3)(10)(6)(3) + (s -3)(10)(6)(3) + (s -1)(6)(3) + (s -1)(3) + (s -1) DIR(A[s1, s2, s3, s4, s5]) = L + (s1 - 1)(3)(10)(6)(3) + (s2 - 3)(10)(6)(3) + (s3 - 1)(6)(3) + (s4 - 1)(3) + (s5 - 1) DIR(A[s1, s2, s3, s4, s5]) = L + (s1 - 1)(540) + (s2 - 3)(180) + (s3 - 1)(18) + (s4 - 1)(3) + (s5 - 1) UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 30 DIR(A[1, 3, 1, 1, 1]) = L + (1 - 1)(540) + (3 - 3)(180) + (1 - 1)(18) + (1 - 1)(3) + (1 - 1) DIR(A[1,3,1,1,1]) = L + 0 = L. 2.3. Aplicaciones. 1). Como primer ejemplo de aplicación de arreglos consideraremos el problema de la manipulación simbólica para realizar operaciones sobre polinomios algebraicos. Centraremos nuestra atención en particular a la manipulación de polinomios en dos variables x y y. Se requiere, por ejemplo, escribir un programa que sustraiga polinomios como los siguientes : 2x2 + 5xy + x2 + 3xy + x2 + 2xy + y2 y2 + 0 - y y + x x Nos interesa, por lo tanto, encontrar una representación adecuada para polinomios de tal modo que las operaciones puedan ser ejecutadas de una manera razonable y eficiente. Es claro que debemos manipular cada término y cada término consta de una ó dos variables, coeficiente y exponentes.Una posibilidad es representar cada polinomio como una cadena de caracteres, lo cual nos lleva a diseñar un algoritmo más ó menos complejo en los lenguajes pascal ó C. Otra posibilidad más atractiva es representar cada polinomio utilizando un arreglo bidimensional de la manera siguiente : El arreglo que representaría al polinomio 2x2 + 5xy + y2 estaría dado por : x0 x1 x2 x3 x4 y0 0 0 2 0 0 y1 0 5 0 0 0 y2 1 0 0 0 0 y3 0 0 0 0 0 y4 0 0 0 0 0 y el arreglo para x2 + 3xy + y2 + y - x estaría dado por : UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos x0 x1 x2 x3 x4 y0 0 -1 2 0 0 y1 1 3 0 0 0 y2 1 0 0 0 0 y3 0 0 0 0 0 pag. 31 y4 0 0 0 0 0 Con esta representación de polinomios, la adición y sustracción se reduce a suma y resta de matrices respectivamente. Ejercicio 1. Construya un programa que sirva para sumar ó restar polinomios simbólicamente haciendo uso de la representación anterior. Haga lo siguiente : a). Convierta los datos de entrada en arreglos representando polinomios. b). Sume ó reste los arreglos (polinomios) según el deseo del usuario. c). Convierta el arreglo de salida a una forma entendible en la pantalla. 2). Realice una implementación del conocido juego del gato : O X Introduzca las coordenadas de su X : _ basándose en el siguiente algoritmo : ganador = false; repeat mostrar_dibujo( ); tira_jugador( ); ganador = revisar_tabla( ); if (NOT ganador) then tira_computadora( ); ganador = revisar_tabla( ); end-if until (ganador); UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 32 3). Recorridos de un caballo sobre un tablero de ajedrez. El problema consiste en mover un caballo, comenzando en cualquier cuadro del tablero pero permitiendo visitar cada cuadro una sola vez; se recomienda representar la solución colocando los números 1,2,3, ... ,63, 64 en los cuadros para indicar el orden en que se visitan, de este modo, el usuario que llegue al número 64 habrá visitado todos los cuadros del tablero; dependiendo de la elección de las visitas, el usuario podrá 'ahogarse' (no poder visitar ningún cuadro y no haber terminado de recorrer el tablero). La decisión más importante para resolver éste problema está relacionado con la representación de datos en la computadora; el modo más natural para representar un tablero de ajedrez es mediante un arreglo bidimensional de 8x8 elementos, tal como se muestra en la figura 2.2 en la cual se muestran además los ocho movimientos posibles de un caballo colocado en el cuadro [5,3]. 1 1 2 3 4 5 6 7 8 2 3 8 4 5 6 7 8 1 7 2 C 6 3 5 4 Figura 2.2. Movimientos posibles de un caballo sobre un tablero de ajedrez. En general, un caballo posicionado en [i,j] puede moverse a cualquiera de los siguientes cuadros : [i-2, j+1] [i-1, j+2] [i+1, j+2] [i+2, j+1] [i+2, j+1] [i+1, j-2] [i-1, j-2] [i-2, j-1] UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 33 Nótese sin embargo, que si [i,j] está localizado cerca de los bordes, alguna ó varias de estas posibilidades pueden mover el caballo fuera del tablero, lo cual no debe de ninguna manera permitirse. Los ocho movimientos posibles se pueden representar de manera más conveniente con dos arreglos unidimensionales que podemos llamar mov1 y mov2 de la siguiente manera: mov1[] = -2, -1, 1, 2, 2, 1, -1, -2. mov2[] = 1, 2, 2, 1, -1, -2, -2, -1. con ésta representación, un caballo posicionado en [i,j] puede moverse a la posición [i + mov1[k], j + mov2[k] ], donde 'k' es algún valor entre 1 y 8, debiendo verificarse antes si la nueva posición está dentro del tablero. Enseguida se proporciona un algoritmo para resolver éste problema y se deja como ejercicio la implementación del mismo en la computadora. Algoritmo Ajedrez. [Recorridos de un caballo sobre un tablero de ajedrez.] 1. [ Iniciar el tablero.] [El tablero es un arreglo de números enteros de 8x8 y se debe inicializar con ceros, ésto significa que todavía no se ha visitado ningún cuadro.] inicia_tablero( ); [inicializa el tablero] despliega_tablero( ); [se despliega el tablero vacío] m 0; [no se ha visitado ningún cuadro] 2. [Iterar mientras haya movimientos posibles] repeat [se pide al usuario un movimiento; algunos de los cuadros pueden no ser posibles de visitar debido a que quedan fuera del tablero ó bien que ya han sido visitados anteriormente (contienen un número diferente de cero), también es posible que el caballo se encuentre 'ahogado' (no es posible ningún movimiento), éstos problemas deben ser detectados en el algoritmo función 'rev_pos( )' que se propone como ejercicio] UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos write('Cuadro a visitar : '); read(ren, col); [renglón y columna] pos_ok = rev_pos(ren, col); [ ¿ posición correcta ?] if (pos_ok) then m m + 1; [se visitó el siguiente cuadro] i ren; [el cuadro visitado es correcto] j col; tablero[i, j] m; [se registra el cuadro visitado] end-if; despliega_tablero( ); [se despliega el tablero actualizado] until (not pos_ok | | m 64) 3. [Fin del algoritmo.] End. UNIDAD ACADEMICA DE MATEMATICAS, UAG pag. 34 Estructura de Datos pag. 35 3. Pilas y Colas. 3.1 Pilas. Es una estructura del tipo "último en entrar, primero en salir" (LIFO : last input, firs output). Estas estructuras son muy importantes en el diseño de sistemas operativos y compiladores. Funciones de Acceso. push(s,nuevo). pop(s). tope(s). vacio(s). Insertar el elemento 'nuevo' en la pila 's'. Eliminar un elemento de la pila 's'. Obtener sin eliminar un elemento de la pila 's'. Comprobar si la pila 's' está vacía. Implementación. Implementaremos una pila en un arreglo unidimensional que consista de un número suficiente de elementos para poder manipular las inserciones necesarias. El esquema es el siguiente : 1 2 k k+1 X X ... X tope (inserción y eliminación) ... n En esta representación, 'tope' es un apuntador a la parte frontal de la pila. UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos Los algoritmos son: Procedimiento push(s, tope, x). [Inserta un elemento x en la parte superior tope de una pila que está representada en un vector s conteniendo n elementos. ] 1. [Revisa si existe estado de overflow (sobrealmacenamiento)] if tope n then write('Pila llena (overflow)') return end-if 2. [Se incrementa tope] tope tope + 1 3. [Se inserta el nuevo elemento] s[tope] x 4. [Termina] return Funcion pop(s, tope). [Remueve el elemento superior de una pila que está representada en un vector s y retorna el elemento removido.] 1. [Revisa si existe estado de underflow (pila vacia)] if tope = 0 then write('Pila vacía (underflow)') return(0) end-if 2. [Se disminuye el apuntador] tope tope - 1 3. [Se retorna el elemento removido] return(s[tope + 1]) UNIDAD ACADEMICA DE MATEMATICAS, UAG pag. 36 Estructura de Datos pag. 37 Aplicaciones. 1). Usando una pila, construya un algoritmo que analice en una expresión aritmética, el uso correcto de los paréntesis "(" y ")" embebidos en ella. Solución. Queremos revisar que : a). Exista igual número de paréntesis a la izquierda y a la derecha. b). Cada paréntesis de la derecha está precedido por el correspondiente paréntesis a la izquierda. Para resolver éste problema debemos pensar en que cada paréntesis a la izquierda abre una posibilidad y cada paréntesis a la derecha cierra ésta posibilidad; una pila se puede aprovechar para registrar éste tipo de signos de agrupación: en cuanto se encuentre un paréntesis a la izquierda, éste es empujado hacia la pila y cuando se encuentre un paréntesis a la derecha, se examina la pila, si esta vacía, la expresión aritmética no es válida, si no está vacía, se retira un elemento de la pila y así sucesivamente hasta terminar de examinar la expresión. Algoritmo paréntesis. [Dada una expresión algebraica llamada cadena, que contiene un espacio en blanco ' ' en la última posición de la extrema derecha, por ejemplo '(x+(y-(a+b))*c-((d+e)))/(b-(j-(k-(l-n)))) ', y dada la función sigchar que retorna el siguiente símbolo de cadena, se analiza el uso correcto de los paréntesis "(" y ")" embebidos en la expresión.] 1. [Inicia la pila colocando el signo ' '] tope 1 s[tope] ' ' UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 38 2. [Obtiene símbolos, si es un '(' lo apila y si es un ')' quita un símbolo de la pila. Repetirá lo anterior hasta que obtenga un ' ' ó bien que la expresión sea inválida.] sig sigchar(cadena) repeat while sig ' ' if sig = '(' then call push(s, tope, sig) else if sig = ')' then i pop(s, tope) if i = ' ' then write('Expresión incorrecta') return(0) end-if end-if end-if sig sigchar(cadena) end-repeat 3. [El siguiente símbolo debe ser un espacio en blanco ' '] i pop(s, tope) if i = ' ' then write('Expresión correcta') else write('Expresión incorrecta') end-if 4. [Terminar] exit. 2). Consideraremos otro ejemplo que involucra el uso de una pila. Sea el conjunto : L = { w c wR | w E {a, b} } done wR es el reverso de w, por ejemplo, si w = ab, entonces wR = ba. El conjunto anterior define a un lenguaje 'L' que puede contener un número infinito de cadenas. Algunas de las cadenas posibles son : aca, bcb, abcba, bacab, abbcbba, abacaba, aabcbaa, ... UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 39 Se requiere formular un algoritmo para el cual, dada una cadena de entrada sobre el alfabeto {a, b, c}, determine si dicha cadena existe en el lenguaje 'L'. Este algoritmo requiere una pila para realizar su tarea. Asumiremos que la cadena de entrada está terminada a la derecha con un espacio en blanco. Algoritmo Reconocer. [Dada una cadena llamada 'string' sobre el alfabeto {a, b, c} y que contiene un espacio en blanco en la posición última de la extrema derecha y dada la función 'nextchar' que retorna el siguiente símbolo de 'string', éste algoritmo determina si el contenido de 'string' pertenece ó no al lenguaje 'L'. ] 1. [Inicia la pila colocando el signo 'c'] tope 1 s[tope] 'c' 2. [Obtiene y apila símbolos hasta que una 'c' ó un blanco ' ' se encuentran]. next nextchar(string) repeat while (next 'c') if next = ' ' then write('cadena invalida') exit else call push(s, tope, next) next nextchar(string) end-if end-repeat 3. [Examina los caracteres posteriores al signo 'c' y los compara con los caracteres apilados.] repeat while (s[tope] 'c') next nextchar(string) x pop(s, tope) if next x then write('cadena inválida') exit end-if end-repeat UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 40 4. [El siguiente símbolo debe ser un blanco ' '.] if next = ' ' then write('cadena correcta') else write('cadena incorrecta') end-if 5.[Terminar] exit. 3). Usando una pila, construya un algoritmo que analice en una expresión aritmética el uso correcto de tres tipos diferentes de separadores: '()', '[]', '{}'. Compruebe el algoritmo con la siguiente expresión : {x + (y - [a + b]) * c - [(d + e)]} / (b - (j - (k - [l - n]))) Ahora es necesario tener en cuenta no solamente cuántos separadores han sido abiertos, sino también de qué tipo son. Esto es necesario porque cuando se encuentre un signo de agrupación, debemos saber el tipo de símbolo mediante el cual se abrió la agrupación y asegurarnos de que ha sido cerrado apropiadamente. Se puede utilizar una pila única para registrar los diferentes tipos de signos de agrupación. En cuanto se encuentre un paréntesis a la izquierda, éste es empujado hacia la pila, y cuando se encuentre un signo terminal, se retira un elemento de la pila; si la pila está vacía, quiere decir que el paréntesis a la derecha no tiene su correspondiente paréntesis a la izquierda y por tanto la expresión aritmética no es válida. Sin embargo, si la pila no está vacía, debemos revisar si el elemento retirado corresponde al tipo de signo de agrupación terminal. Si coincide el tipo, continuamos, si no coincide, la expresión aritmética no es válida. Cuando lleguemos al final de la expresión, nos aseguramos de que la pila está vacía, de lo contrario quiere decir que se han abierto uno ó más signos pero no se han cerrado, haciendo que la expresión sea incorrecta. 4). Construya un algoritmo que acepte una cadena de caracteres y la invierta usando una pila. UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 41 3.2. Colas. Son estructuras de datos lineales del tipo "primero que llega, primero que sale" (FIFO : first input, first output). Funciones de Acceso. qinsert(q, f, r, x). Inserta x al final de la cola q. qdelete(q, f, r). Elimina el último elemento de la cola q. Implementación. Implementaremos una cola en un arreglo unidimensional que consista también de un tamaño suficiente como para poder manipular las inserciones y eliminaciones necesarias : 1 2 k k+1 X ... X f (eliminación) r (inserción) ... n En esta representación, 'f' y 'r' son apuntadores a la posición frontal y final de la cola, respectivamente. Los algoritmos necesarios son : Procedimiento qinsert(q, f, r, x). [Dado un vector q que contiene 'n' elementos y las variables enteras 'f' y 'r' que apuntan a los elementos frontal y final de la cola, éste procedimiento inserta el elemento 'x' al final de la cola. ] 1. [Revisa si existe estado de overflow (sobrealmacenamiento)] if r N then write('Cola llena (overflow)') return end-if UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos 2. [Se incrementa el apuntador del final] rr+1 3. [Se inserta el nuevo elemento] q[r] x 4. [¿ Está el apuntador frontal debidamente fijado ?] if f = 0 then f 1 end-if 5. [Termina] return Procedimiento qdelete(q, f, r). [Dado un vector q que contiene 'n' elementos y las variables enteras 'f' y 'r' que apuntan a los elementos frontal y final de la cola, éste procedimiento elimina y retorna el último elemento de la cola. ] 1. [Revisa si existe estado de underflow (cola vacía).] if f = 0 then write('Cola Vacía (underflow)') return (0) { 0 denota una cola vacía } end-if 2. [Se elimina el elemento frontal] x q[f] 3. [¿ Resulta una cola vacía ?] if f = r then f r 0 else f f + 1 { Se incrementa el apuntador frontal } end-if 4. [Retorna el elemento eliminado.] return x UNIDAD ACADEMICA DE MATEMATICAS, UAG pag. 42 Estructura de Datos pag. 43 3.3. Cola Doble. Es una estructura de datos en la cual las operaciones de agregar y retirar se practican por ambos extremos. Funciones de Acceso. dqinsertf(dq, f, r, x). Inserta x al final de la cola doble. dqinsertr(dq, f, r, x). Inserta x al frente de la cola doble. dqdeletef(dq, f, r). Elimina el último elemento de la cola doble. dqdeleter(dq, f, r). Elimina el primer elemento de la cola doble. Implementación. Implementaremos una cola doble en un arreglo unidimensional que consista también de un tamaño suficiente como para poder manipular las inserciones y eliminaciones necesarias : 1 2 k k+1 X ... X f (eliminación e inserción) r (eliminación e inserción) ... n En esta representación, 'f' y 'r' son apuntadores a la posición frontal y final de la cola doble, respectivamente. UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 44 4. Listas. En este capítulo estudiaremos la organización ligada de las estructuras lineales. Esta organización nos permite manejar de manera más eficiente el almacenamiento de la computadora. Iniciaremos el estudio con un pequeño recordatorio de los elementos necesarios para trabajar con listas ligadas. 4.1. Punteros. Todas las variables, excepto las variables tipo registro, residen en algún lugar de la memoria; éste lugar tiene una dirección de memoria que es en realidad el número de byte inicial del espacio que ocupa la variable; un puntero es una variable que sirve para almacenar la dirección de memoria de otra variable de cualquier tipo. Ejemplo 1. El siguiente programa despliega en la pantalla las direcciones de dos variables. /*---------------------------------------------------------------------------#include <stdio.h> void main(void) { int i = 7, j = 8; printf("i = %d, &i = %p\n", i, &i); printf("j = %d, &j = %p\n", j, &j); } El programa produce una salida parecida a la siguiente : i = 7, &i = FFF4 j = 8, &j = FFF2 el operador unario & retorna la dirección de la variable a la que se le aplica, el descriptor %p indica que deseamos desplegar una dirección en formato hexadecimal. UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 45 Ejemplo 2. El programa que sigue ilustra un uso elemental de variables de tipo puntero. /*---------------------------------------------------------------------------#include <stdio.h> void main(void) { int i = 7, j = 8; int *p, *q; p = &i; q = &j; printf("p = %p, *p = %d\n", p, *p); printf("q = %p, *q = %d\n", q, *q); *p = 9; *q = 10; printf("p = %p, *p = %d\n", p, i); printf("q = %p, *q = %d\n", q, j); } El programa producirá una salida parecida a la siguiente : p = FFF4, q = FFF2, p = FFF4, q = FFF2, *p = 7 *q = 8 *p = 9 *q = 10 UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 46 4.2. Listas Simplemente Ligadas. Una lista simplemente ligada es una lista de elementos que se denominan generalmente como nodos : Nodo 1 Nodo 2 Nodo 3 Nodo N ... Apuntador al primer nodo Cada nodo está constituido por dos partes : un campo (ó varios) para contener datos y otro campo que contiene la liga al siguiente nodo en un orden dado : N D A T O S O D O L I G A UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos Ejemplo 2. Lista simplemente ligada de caracteres. 1a. versión. /*------------------------------------------------------lsl01.c Genera una lista simplemente ligada de caracteres. Estructura de Datos I. ---------------------------------------------------------*/ #include <stdio.h> #include <stdlib.h> #include <alloc.h> #include <conio.h> struct nodo { /* definicion del nodo */ char vocal; struct nodo *liga; }; struct nodo *primero; struct nodo *temporal; struct nodo *nuevo; /* punteros */ void main(void) { /* crea un nodo e inserta la 'a' */ nuevo = (struct nodo *) malloc(sizeof(struct nodo)); nuevo->vocal = 'a'; nuevo->liga = NULL; /* no apunta a ningun lado */ primero = nuevo; /* apunta al nodo recien creado */ /* crea otro nodo e inserta la 'e' */ temporal = nuevo; /* guarda la direccion del nodo */ nuevo = (struct nodo *) malloc(sizeof(struct nodo)); temporal->liga = nuevo; /* enlaza al nodo nuevo */ nuevo->vocal = 'e'; nuevo->liga = NULL; /* no apunta a ningun lado */ UNIDAD ACADEMICA DE MATEMATICAS, UAG pag. 47 Estructura de Datos /* crea otro nodo e inserta la 'i' */ temporal = nuevo; /* guarda la direccion del nodo */ nuevo = (struct nodo *) malloc(sizeof(struct nodo)); temporal->liga = nuevo; /* enlaza al nodo nuevo */ nuevo->vocal = 'i'; nuevo->liga = NULL; /* no apunta a ningun lado */ /* crea otro nodo e inserta la 'o' */ temporal = nuevo; /* guarda la direccion del nodo */ nuevo = (struct nodo *) malloc(sizeof(struct nodo)); temporal->liga = nuevo; /* enlaza al nodo nuevo */ nuevo->vocal = 'o'; nuevo->liga = NULL; /* no apunta a ningun lado */ /* recorre la lista simplemente ligada */ clrscr( ); printf("\nLISTAS SIMPLEMENTE LIGADAS\n\n"); temporal = primero; /* copia la direccion del primer nodo */ while (temporal != NULL) { printf("\n%c ",temporal->vocal); temporal = temporal->liga; /* avanza al siguiente nodo */ } /* recorre la lista y elimina los nodos */ temporal = primero; /* copia la direccion del primer nodo */ while (temporal != NULL) { temporal = temporal->liga; /* avanza al siguiente nodo */ free(primero); /* destruye el primer nodo */ primero = temporal; /* apunta al nuevo primer nodo */ } /* hace una pausa */ printf("\n\n<Oprima cualquier tecla para terminar>\n"); getch( ); } UNIDAD ACADEMICA DE MATEMATICAS, UAG pag. 48 Estructura de Datos Ejemplo 3. Lista Simplemente Ligada de caracteres. 2a. versión. /*--------------------------------------------------------lsl02.c Genera una lista simplemente ligada de caracteres utilizando un ciclo. Estructura de Datos I. ---------------------------------------------------------*/ #include <stdio.h> #include <stdlib.h> #include <alloc.h> #include <conio.h> struct nodo { /* definicion del nodo */ char vocal; struct nodo *liga; }; struct nodo *primero; /* punteros */ struct nodo *temporal; struct nodo *nuevo; char vocal; void main(void) { /* se pide el primer caracter */ clrscr( ); printf("\nLISTAS SIMPLEMENTE LIGADAS\n"); printf("\nIntroduzca un caracter (f para terminar) : "); vocal = getche( ); if (vocal != 'f') { /* se inserta el primer caracter */ nuevo = (struct nodo *) malloc(sizeof(struct nodo)); nuevo->vocal = vocal; nuevo->liga = NULL; /* no apunta a ningun lado */ primero = nuevo; /* apunta al nodo recien creado */ UNIDAD ACADEMICA DE MATEMATICAS, UAG pag. 49 Estructura de Datos /* se piden los demas caracteres y se insertan */ printf("\nIntroduzca un caracter (f para terminar) : "); vocal = getche( ); while (vocal != 'f') { temporal = nuevo; /* guarda la direccion del nodo */ nuevo = (struct nodo *) malloc(sizeof(struct nodo)); temporal->liga = nuevo; /* enlaza al nodo nuevo */ nuevo->vocal = vocal; nuevo->liga = NULL; /* no apunta a ningun lado */ printf("\nIntroduzca un caracter (f para terminar) : "); vocal = getche( ); } /* recorre la lista simplemente ligada */ clrscr( ); printf("\nLISTAS SIMPLEMENTE LIGADAS\n\n"); temporal = primero; /* copia la direccion del primer nodo */ while (temporal != NULL) { printf("\n%c ",temporal->vocal); temporal = temporal->liga; /* avanza al siguiente nodo */ } /* recorre la lista y elimina los nodos */ temporal = primero; /* copia la direccion del primer nodo */ while (temporal != NULL) { temporal = temporal->liga; /* avanza al siguiente nodo */ free(primero); /* destruye el primer nodo */ primero = temporal; /* apunta al nuevo primer nodo */ } } /* hace una pausa */ printf("\n\n<Oprima cualquier tecla para terminar>\n"); getch( ); } UNIDAD ACADEMICA DE MATEMATICAS, UAG pag. 50 Estructura de Datos 4.3. Operaciones con listas ligadas. Crear una lista. Recorrer la lista. Buscar un elemento. Insertar un nodo. Eliminar un nodo. Invertir la lista. Ordenar la lista. UNIDAD ACADEMICA DE MATEMATICAS, UAG pag. 51 Estructura de Datos Ejemplo 4. Operaciones sobre listas ligadas. /*----------------------------------------------------oplis.c Operaciones sobre Listas Ligadas. Estructura de Datos I. -------------------------------------------------------*/ #include <stdio.h> #include <stdlib.h> #include <alloc.h> /* para usar malloc( ) y free( ) */ #include <conio.h> #include <ctype.h> /* para usar isalpha( ) */ #define c1 " UNIVERSIDAD AUTONOMA DE GUERRERO " #define c2 " programa oplis.c " #define c3 " Operaciones sobre Listas Ligadas. " #define A "(a). Crear una lista ligada de caracteres." #define B "(b). Desplegar la lista." #define C "(c). Eliminar el primer nodo." #define D "(d). Aumentar un nodo al principio." #define F "(f). Fin." #define TRUE 1 #define FALSE 0 char EXISTE_LISTA = FALSE; struct nodo { int dato; struct nodo *liga; }; typedef struct nodo *PNODO; PNODO crear_nodo( ); PNODO adicionar_nodo( ); PNODO eliminar_nodo( ); PNODO leer_lista( ); UNIDAD ACADEMICA DE MATEMATICAS, UAG pag. 52 Estructura de Datos PNODO opcion_a( ); void opcion_b( ); PNODO opcion_c( ); PNODO opcion_d( ); void ver_lista( ); void menu(void); void pausa(char mensaje[]); /*----------------------------------------------------------*/ void main(void) { char c; PNODO p; menu( ); c = getche( ); while (c != 'f') { switch (c) { case 'a' : if (!EXISTE_LISTA) p = opcion_a( ); break; case 'b' : if (EXISTE_LISTA) opcion_b(p); break; case 'c' : if (EXISTE_LISTA) p = opcion_c(p); break; case 'd' : if (EXISTE_LISTA) p = opcion_d(p); break; case 'f' : exit(1); } menu( ); c = getche( ); } pausa(""); } UNIDAD ACADEMICA DE MATEMATICAS, UAG pag. 53 Estructura de Datos /*------------------------------------------------------------*/ PNODO opcion_a( ) { PNODO p; clrscr( ); printf("\n\n\t"); printf(A); p = leer_lista( ); EXISTE_LISTA = TRUE; pausa(""); return (p); } /*------------------------------------------------------------*/ void opcion_b(p) PNODO p; { clrscr( ); printf("\n\n\t"); printf(B); ver_lista(p); pausa(""); } /*------------------------------------------------------------*/ PNODO opcion_c(p) PNODO p; { clrscr( ); printf("\n\n\t"); printf(C); p = eliminar_nodo(p); pausa(""); return (p); } UNIDAD ACADEMICA DE MATEMATICAS, UAG pag. 54 Estructura de Datos /*------------------------------------------------------------*/ PNODO opcion_d(p) PNODO p; { char x; clrscr( ); printf("\n\n\t"); printf(D); printf("\n\n\tIntroduzca un caracter : "); x = getche( ); p = adicionar_nodo(p,x); pausa(""); return (p); } /*------------------------------------------------------------*/ PNODO leer_lista( ) { PNODO p; char c[81]; int i=0; printf("\n\n\tIntroduzca una lista de caracteres en una sola linea"); printf("\n\tseparados por espacios en blanco y pulse <enter> :"); /* lee la lista en un arreglo de caracteres */ printf("\n\n\t"); while ((c[i]=getche( )) != '\r') { if (c[i] == '\b') i--; else i++; } c[i]='\0'; /* genera la lista simplemente ligada */ i=0; p = NULL; while (c[i] != '\0') { if (c[i] != ' ') p = adicionar_nodo(p,c[i++]); else i++; } return (p); } UNIDAD ACADEMICA DE MATEMATICAS, UAG pag. 55 Estructura de Datos /*------------------------------------------------------------*/ PNODO crear_nodo( ) { PNODO p; p = (PNODO) malloc(sizeof(struct nodo)); return (p); } /*------------------------------------------------------------*/ PNODO adicionar_nodo(p,x) PNODO p; char x; { PNODO q; if (p == NULL) { /* se trata del primer nodo */ q = crear_nodo( ); q->dato = x; q->liga = NULL; p = q; } else { /* la lista ya existe */ q = crear_nodo( ); q->dato = x; q->liga = p; p = q; } return (p); } UNIDAD ACADEMICA DE MATEMATICAS, UAG pag. 56 Estructura de Datos /*------------------------------------------------------------*/ PNODO eliminar_nodo(p) PNODO p; { PNODO q; if (p->liga == NULL) { /* se trata de un solo nodo */ free(p); p = NULL; EXISTE_LISTA = FALSE; } else { /* la lista ya existe */ q = p->liga; free(p); p = q; } return (p); } /*------------------------------------------------------------*/ void ver_lista(p) PNODO p; { PNODO q; q = p; printf("\n\n\tLISTA LIGADA :"); while (q) { printf(" %c", q->dato); q = q->liga; } } /*------------------------------------------------------------*/ void pausa(char mensaje[]) { printf(mensaje); printf("\n\n\t\t\t<pulse cualquier tecla>"); getch( ); } UNIDAD ACADEMICA DE MATEMATICAS, UAG pag. 57 Estructura de Datos /*------------------------------------------------------*/ void menu(void) { clrscr( ); gotoxy(20,2); printf(c1); gotoxy(20,3); printf(c2); gotoxy(20,4); printf(c3); gotoxy(10,7); printf(A); gotoxy(10,9); printf(B); gotoxy(10,11); printf(C); gotoxy(10,13); printf(D); gotoxy(10,15); printf(F); gotoxy(15,18); printf("Pulse su Opcion : "); } 4.4. Listas doblemente ligadas. Ejemplo 5. Lista doblemente ligada de caracteres. /*------------------------------------------------------ldl02.c Genera una lista doblemente ligada de caracteres. utilizando un ciclo. Estructura de Datos I. ---------------------------------------------------------*/ #include <stdio.h> #include <stdlib.h> #include <alloc.h> #include <conio.h> struct nodo { /* definicion del nodo */ struct nodo *ligai; char vocal; struct nodo *ligad; }; UNIDAD ACADEMICA DE MATEMATICAS, UAG pag. 58 Estructura de Datos struct nodo *izquierdo; struct nodo *derecho; struct nodo *temporal; struct nodo *nuevo; char vocal; /* punteros */ void main(void) { /* se pide el primer caracter */ clrscr( ); printf("\nLISTAS DOBLEMENTE LIGADAS\n"); printf("\nIntroduzca un caracter (f para terminar) : "); vocal = getche( ); if (vocal != 'f') { /* se inserta el primer caracter */ nuevo = (struct nodo *) malloc(sizeof(struct nodo)); nuevo->vocal = vocal; nuevo->ligai = NULL; /* no apunta a ningun lado */ nuevo->ligad = NULL; izquierdo = nuevo; /* primer nodo por la izquierda */ derecho = nuevo; /* primer nodo por la derecha */ /* se piden los demas caracteres y se insertan */ printf("\nIntroduzca un caracter (f para terminar) : "); vocal = getche( ); while (vocal != 'f') { temporal = nuevo; /* guarda la direccion del nodo */ nuevo = (struct nodo *) malloc(sizeof(struct nodo)); temporal->ligad = nuevo; /* enlaza al nodo nuevo */ nuevo->ligai = temporal; /* enlaza hacia atras */ nuevo->vocal = vocal; nuevo->ligad = NULL; /* no apunta a ningun lado */ derecho = nuevo; /* primer nodo por la derecha */ UNIDAD ACADEMICA DE MATEMATICAS, UAG pag. 59 Estructura de Datos printf("\nIntroduzca un caracter (f para terminar) : "); vocal = getche( ); } /* recorre la lista doblemente ligada */ clrscr( ); printf("\nLISTAS DOBLEMENTE LIGADAS"); printf("\n\nRecorrido por la izquierda\n"); temporal = izquierdo; /* copia la direccion del primer nodo */ while (temporal != NULL) { printf("\n%c ",temporal->vocal); temporal = temporal->ligad; /* avanza al siguiente nodo */ } printf("\n\nRecorrido por la derecha\n"); temporal = derecho; /* copia la direccion del primer nodo */ while (temporal != NULL) { printf("\n%c ",temporal->vocal); temporal = temporal->ligai; /* avanza al siguiente nodo */ } /* recorre la lista y elimina los nodos */ temporal = izquierdo; /* copia la direccion del primer nodo */ while (temporal != NULL) { temporal = temporal->ligad; /* avanza al siguiente nodo */ free(izquierdo); /* destruye el primer nodo */ izquierdo = temporal; /* apunta al nuevo primer nodo */ izquierdo->ligai = NULL; } } /* hace una pausa */ printf("\n\n<Oprima cualquier tecla para terminar>\n"); getch( ); } UNIDAD ACADEMICA DE MATEMATICAS, UAG pag. 60 Estructura de Datos pag. 61 Tarea #1 de listas. Para una lista simplemente ligada de números enteros del tipo : Nodo 1 7 Nodo 2 -3 Nodo 3 0 Nodo N ... 1 primero Donde cada nodo tiene dos campos conocidos como dato y liga,escriba y pruebe los siguientes procedimientos : 1). void promedio(struct *primero). Este procedimiento debe obtener el valor promedio de los números almacenados. 2). void inserta_despues(struct *primero, int x, int y). Inserta un nodo exactamente después del nodo que contiene el valor 'x' y almacena en este nuevo nodo el valor 'y'. 3). void elimina_despues(struct *primero, int x). Elimina el nodo inmediatamente posterior al nodo que contiene el valor 'x'; si no está, debe indicarlo con un mensaje. 4). void modificar(struct *primero, int x, int y). Busca el nodo que contenga el valor 'x' y cambia éste valor a 'y'; si no lo encuentra debe indicarlo con un mensaje. 5). void uno_cero(struct *primero). Aplica el siguiente algoritmo a todos los nodos de la lista : Si el valor almacenado en el nodo es negativo, reemplazarlo por un 0; de otro modo, si es cero, reemplazarlo por -1; de otro modo, reemplazarlo por +1. UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 62 6). void inserta_cola(struct nodo *primero, int x) Inserta el elemento 'x' al final de la lista ligada; considere los casos de lista vacía y 'overflow' (máximo diez nodos). 7). struct nodo *borra_cola(struct nodo *primero) Elimina el primer elemento de la lista ligada; considere el caso de 'underflow' (lista vacía). 8. struct nodo *borra_pila(struct nodo *primero, int x) Elimina el último elemento de la lista ligada; considere el caso de 'underflow' (lista vacía). UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 63 5. Estructuras no lineales. Las estructuras no lineales son capaces de expresar relaciones mucho más complejas entre los datos; en éste capítulo estudiaremos las estructuras de datos conocidas como árboles binarios; posteriormente en otros cursos se analizarán estructuras más complicadas como árboles no binarios, grafos y estructuras combinadas. 5.1. Arboles binarios. Se caracterizan porque cualquiera de sus nodos tiene exactamente cero, uno ó dos subárboles. Un nodo del árbol binario puede representarse de la siguiente manera : apuntador izquierdo datos apuntador derecho el esquema para un árbol binario podría ser el siguiente : raiz C B / A / / F / / D / E / UNIDAD ACADEMICA DE MATEMATICAS, UAG G / Estructura de Datos pag. 64 Funciones de Acceso. Recorrido, Inserción, Eliminación, Búsqueda, Copia, ..., étc. Recorrido de árboles binarios. Se denomina recorrido de un árbol al procedimiento por medio del cual cada nodo se procesa exactamente una única vez de modo sistemático. Existen tres modos principales de recorrido de árboles binarios: preorden, inorden y postorden. La definición recursiva de éstos procedimientos es la siguiente : Recorrido en Preorden. 1. Procesar el nodo raiz. 2. Recorrer el subárbol izquierdo en preorden. 3. Recorrer el subárbol derecho en preorden. Recorrido en Inorden. 1. Recorrer el subárbol izquierdo en inorden. 2. Procesar el nodo raiz. 3. Recorrer el subárbol derecho en inorden. Recorrido en Postorden. 1. Recorrer el subárbol izquierdo en postorden. 2. Recorrer el subárbol derecho en postorden. 3. Procesar el nodo raiz. Ejemplo 1. Recorrer el árbol anterior de ejemplo en preorden, inorden y postorden. Preorden : C B A F D E G Inorden : A B C D E F G Postorden : A B E D G F C UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 65 Ejemplo 2. Escriba un algoritmo procedimiento para procesar un árbol binario en preorden. Algoritmo. Procedimiento Preorden(raiz). [Dado un árbol binario cuya dirección al nodo raiz es "raiz", éste procedimiento recorre y procesa el árbol en preorden.] 1. [Procesa el nodo raiz ] if raiz null then write(datos(raiz)) else write('Arbol vacío') return 2. [Procesa el subárbol izquierdo ] if ant(raiz) null then call preorden(ant(raiz)) 3. [Procesa el subárbol derecho ] if sig(raiz) null then call preorden(sig(raiz)) 4. [Termina ] return Ejemplo 3. Programa para generar un árbol binario ordenado y efectuar los recorridos en inorden, preorden y postorden. /*--------------------------------------------------------------------------Nombre del Archivo : arbin01.c Recorrido en inorden, preorden y postorden de arboles binarios. ------------------------------------------------------------------------------*/ #include <stdio.h> #include <stdlib.h> #include <alloc.h> #include <conio.h> UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos struct nodo { /* definición del nodo */ struct nodo *ligai; char vocal; struct nodo *ligad; }; struct nodo *raiz; /* puntero a la raiz del árbol */ char vocal; void insertar(char x, struct nodo **p); void inorden (struct nodo *raiz); void preorden (struct nodo *raiz); void postorden (struct nodo *raiz); void main(void) { /* se pide el primer caracter */ clrscr( ); printf("RECORRIDO DE ARBOLES BINARIOS"); printf("(1). Creación de un árbol binario ordenado."); printf("Introduzca un caracter (f para terminar) : "); vocal = getche( ); if (vocal != 'f') { /* se crea el árbol binario */ raiz = NULL; do { insertar(vocal, &raiz); printf("Introduzca un caracter (f para terminar) : "); vocal = getche( ); } while (vocal != 'f'); /* recorridos en el árbol */ printf("(2). Recorridos en el árbol binario."); printf("RECORRIDO EN INORDEN :"); inorden(raiz); printf("RECORRIDO EN PREORDEN :"); preorden(raiz); printf("RECORRIDO EN POSTORDEN :"); postorden(raiz); } UNIDAD ACADEMICA DE MATEMATICAS, UAG pag. 66 Estructura de Datos /* hace una pausa */ printf("<Oprima cualquier tecla para terminar>"); getch( ); } void insertar(char x, struct nodo **p) { if (*p == NULL) { *p = (struct nodo *) malloc(sizeof(struct nodo)); (*p)->vocal = vocal; (*p)->ligai = NULL; /* no apunta a ningun lado */ (*p)->ligad = NULL; } else { if (x < (*p)->vocal) insertar(x, &(*p)->ligai); else insertar(x, &(*p)->ligad); } } void inorden (struct nodo *raiz) { if (raiz != NULL) { inorden(raiz->ligai); printf("%c", raiz->vocal); inorden(raiz->ligad); } } void preorden (struct nodo *raiz) { if (raiz != NULL) { printf("%c", raiz->vocal); inorden(raiz->ligai); inorden(raiz->ligad); } } UNIDAD ACADEMICA DE MATEMATICAS, UAG pag. 67 Estructura de Datos pag. 68 void postorden (struct nodo *raiz) { if (raiz != NULL) { inorden(raiz->ligai); inorden(raiz->ligad); printf("%c", raiz->vocal); } } Ejercicios. Dado el siguiente árbol binario de números : raiz 11 9 / 6 / / 17 / / 12 / 15 21 / / donde cada nodo tiene tres campos conocidos como 'ligai', 'número' y 'ligad', escribir y probar los siguientes procedimientos : a). void promedio (struct nodo *raiz) Este procedimiento debe obtener el valor promedio de los números almacenados. b). void total_de_nodos(struct nodo *raiz) Debe obtener el total de nodos intermedios, nodos terminales (hojas) y total de nodos existentes en el árbol. UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 69 c). void buscar(int x, struct nodo *raiz) Debe Buscar si existe un nodo que contenga en su campo de datos el valor x; si no existe debe indicarlo con un mensaje. d). void modificar(int x, int y, struct nodo *raiz) Debe buscar el nodo que contiene el valor 'x' y reemplazarlo con el valor almacenado en 'y'; si 'x' no existe en el árbol, deberá indicarlo con un mensaje apropiado. e). void genera3(struct nodo *raiz) Debe generar tres arreglos unidimensionales declarados como variables globales y llamados preorden[], inorden[] y postorden[] conteniendo los datos del árbol resultantes de haberlo recorrido en preorden, inorden y postorden respectivamente. Ejemplo 4. Construcción de un árbol binario perfectamente equilibrado. /*------------------------------------------------------------------------------Nombre del Archivo : arbeq01.c Construcción de un árbol binario perfectamente equilibrado y recorrido en inorden. --------------------------------------------------------------------------------*/ #include <stdio.h> #include <stdlib.h> #include <alloc.h> #include <conio.h> struct nodo { /* definición del nodo */ struct nodo *ligai; char vocal; struct nodo *ligad; }; struct nodo *raiz; int n; /* puntero a la raiz del árbol */ /* total de nodos a crear */ UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 70 void insertar(char x, struct nodo **p); void inorden (struct nodo *raiz); struct nodo *construir_arbol(int n); void main(void) { /* se pide el primer caracter */ clrscr(); printf("\nARBOLES BINARIOS PERFECTAMENTE EQUILIBRADOS"); printf("\n(1). Creación del árbol binario.\n"); printf("\nNumero de Nodos a Crear : "); scanf("%d", &n); raiz = construir_arbol(n); /* recorrido del árbol */ printf("\n\n(2). Recorrido del árbol binario.\n"); printf("\nRECORRIDO EN INORDEN :\n"); inorden(raiz); /* hace una pausa */ printf("\n\n<Oprima cualquier tecla para terminar>\n"); getch(); } /*----------------------------------------------------------------------------*/ struct nodo *construir_arbol(int n) { struct nodo *q; int ni,nd; if (n == 0) return NULL; else { ni = n / 2; /* nodos del subarbol izquierdo */ nd = n - ni - 1; /* nodos del subarbol derecho */ q = (struct nodo *) malloc(sizeof(struct nodo)); printf("\nIntroduzca un caracter : "); q->vocal = getche(); q->ligai = construir_arbol(ni); q->ligad = construir_arbol(nd); return (q); } } UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 71 /*------------------------------------------------------------------------------*/ void inorden (struct nodo *raiz) { if (raiz != NULL) { inorden(raiz->ligai); printf("%c ", raiz->vocal); inorden(raiz->ligad); } } 5.2. Enhebrado de árboles binarios. Los apuntadores nulos se reemplazan por "hilos" (apuntadores a otros nodos del árbol como guías para recorrerlos); el hilo izquierdo de un nodo apunta al predecesor y el hilo derecho al sucesor en un orden previamente escogido. Concepto de cabeza de árbol. Es un nodo especial y asociado permanentemente a la existencia del árbol. El campo de la información en el nodo cabeza no se utiliza. El árbol queda encadenado al apuntador izquierdo del nodo cabeza. Ejemplo. Enhebrar en preorden el árbol del ejemplo anterior. Recorrido en preorden : C-B-A-F-D-E-G. Enhebrado en preorden : UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 72 cabeza C B A F G D E UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos pag. 73 BIBLIOGRAFIA 1. Estructuras de Datos. Segunda Edición. Osvaldo Cairó y Silvia Guardati. Mc Graw-Hill, 2002. 2. Estructuras de Datos en C. Tenenbaum; Langsam; Augenstein. Prentice Hall, 1993. 3. Estructura de Datos. Euán, J.I.; Cordero, L.G. Limusa. 1989. 4. Estructura de Datos. Seymour Lipschutz. Mc Graw-Hill, 1988. 5. Programación Avanzada en Turbo C. Herbert Schildt Mc Graw-Hill. 6. Algoritmos y Estructura de Datos. Niklaus Wirth. Prentice Hall Hispanoamericana, 1987. 7. Data Structures, Algorithms and program style using C. korsh, J.F.; Garrett, L.J. PWS-KENT Publishing Company, 1988. 8. An Introduction to Data Structures with Applications. Tremblay, J.P.; Sorenson, P.G. Mc Graw-Hill. 1985. 9. Algoritmos Fundamentales. (El Arte de Programar Ordenadores, vol. 1). Donald E. Knuth. Reverté, S.A. 1985. UNIDAD ACADEMICA DE MATEMATICAS, UAG Estructura de Datos UNIDAD ACADEMICA DE MATEMATICAS, UAG pag. 74