Estructura De Datos (cinvestav)

Estructura de datos Índice General Preliminares de programación en C/C++ o Arreglos o Apuntadores o Estructuras C/C++ o Ejercicios de programación La pila o o o o o o

Definición y ejemplos Operaciones básicas Ejemplo: Número de paréntesis La estructura de datos Pila en C/C++ La representación en C/C++ de las operaciones de una pila Problemas de programación

Colas o o o

Estructura de las colas en C/C++ Colas con prioridad Ejercicio de programación

Recursión o Peligros en la recursividad o Ejercicios de programación Listas o o o o o

Grafos Listas simplemente encadenadas El uso de memoria dinámica en C/C++ Listas ligadas usando memoria dinámica Ejercicios de programación

Árboles o o o o o

Concepto general de árbol Árboles binarios Representación en C/C++ de los árboles binarios Árboles Ejercicios de programación

Grafos o o

Recordatorio de las definiciones Aplicación ejemplo

Bibliografía 1

Arreglos Definición 1 Un arreglo se compone de elementos de igual tamaño almacenados linealmente en posiciones de memoria consecutiva. Se puede acceder a cada elemento de datos individual utilizando un subíndice, o índice, para seleccionar uno de los elementos. En C/C++, un arreglo no es un tipo de datos estándar; es un tipo agregado compuesto de cualquier otro tipo de datos. Los arreglos se pueden definir usando tipos de datos mixtos debido a que se supone que todos los elementos son del mismo tamaño. Puesto que todos los elementos son del mismo tamaño y ya que este hecho se utiliza para ayudar a determinar cómo localizar un elemento dado, resulta que los elementos son almacenados en localidades de memoria contiguas. Lo más importante a tener en cuenta es: El nombre de un arreglo es visto por el compilador como un puntero-constante al primer elemento del arreglo. Esto es muy importante: a) El nombre del arreglo es visto como un tipo puntero, y más específicamente, b) un puntero constante -significa una dirección de memoria bloqueada para el primer elemento de un arreglo-. Por ejemplo, aunque una declaración de arreglo toma la forma genérica: Tipo_ElementoArray NombreArray [ NumeroDeElementos ]

El compilador ve la declaración como Tipo_ElementoArray * const NombreArray = &NombreArray[0];

Por esta razón, un identificador de arreglo no puede ser usado nunca como un valor-i (valor izquierdo). Los valores izquierdos representan variables que su contenido puede ser alterado por el programa; frecuentemente aparecen a la izquierda de las sentencias de asignación. Si los nombres de arreglo fueran variables izquierdos permitidos, el programa podría cambiar sus contenidos. float SalariosDeEmpleados[Max_empleados]; . . . SalariosDeEmpleados = 45739.0;

El efecto haría cambiar la dirección inicial del propio arreglo.

Declaraciones de un arreglo La sintaxis de declaración de arreglos es: tipo nombre_arreglo [numero_de_elementos];

Los siguientes son dos ejemplos de declaraciones de arreglos válidas en C/C++ : int CoordenadasDePantalla[5]; /*Un arreglo de 5 enteros */ char IDCompania[20]; /*Un arreglo de 20 caracteres */

2

Figura 1: Arreglo CoordenadasDePantalla con índices de desplazamiento válido

En la figura 1 se muestra el primer arreglo que fue declarado con el tipo de números enteros, llamado CoordenadasDePantalla, ocupa en memoria 5 localidades de memoria contiguas, cada una de ellas capaz de almacenar un número entero. Actualmente es común que los números enteros sean de 32 bits bits, esto hace que el arreglo CoordenadasDePantalla ocupe No se permite utilizar nombres de variables dentro de los corchetes. Por esto no es posible evitar la especificación del tamaño del arreglo hasta la ejecución del programa. La expresión debe ser un valor constante, para que el compilador sepa exactamente cuánto espacio de memoria tiene que reservar para el arreglo. Una buena práctica de programación es usar constantes predefinidas. #define Coordenadas_Max 20 #define Tamano_MaX_Compania_Id 15 int CoordenadasDePantalla[Coordenadas_Max]; char IDCompania[Tamano_MaX_Compania_Id];

El uso de constantes predefinidas garantiza que futuras referencias al arreglo no excedan el tamaño del arreglo definido

Iniciación del arreglo C/C++

proporciona 3 maneras de iniciar elementos del arreglo:

Por defecto: Cuando son creados, se aplica solamente a arreglos globales y estáticos. Explícita: Cuando son creados, suministrando datos de iniciación Tiempo de ejecución: Durante la ejecución del programa cuando se asignan o copias datos en el arreglo.

Acceso a los elementos de un arreglo Si se tiene un error cuando se utilizan arreglos en C/C++ , de seguro el error involucra el acceso a los elementos del arreglo, por la simple razón de que el primer elemento está en una posición 0, no 1. De manera que el último elemento del arreglo lo encontramos en n-1, donde n es el número de elementos. 3

Supongamos la siguiente declaración: int Estado[Rango_Maximo_Estado]={-1,0,1};

La siguiente sentencia tiene acceso a -1: Estado[0];

Si escribimos Estado[3] causará un error porque no hay 4 elementos.

Cálculo del tamaño de un arreglo (sizeof()) Es frecuente utilizar el operador sizeof() para calcular la cantidad de espacio que se necesita almacenar para un objeto: /* * exploresz.cpp */ #include #define maxDiasSemana 7 int main(void){ int desplazamiento, maxHorasDiarias[maxDiasSemana]; cout<<"sizeof(int) es"<<(int)sizeof(int)<<"\n\n"; for(desplazamiento=0;desplazamiento<maxDiasSemana; desplazamiento++) cout<<"&maxHorasDiarias[" <<desplazamiento <<"]=" <<&maxHorasDiarias[desplazamiento]<<"\n"; return 0; }

Arreglos multidimensionales El término dimensión representa el número de índices utilizados para referirse a un elemento particular en el arreglo. Los arreglos de más de una dimensión se llaman arreglos multidimensionales. /* / dosDim.cpp */ #include #define numFilas 4 #define numColumnas 5 int main (int argc, char * const argv[]) { int despFila, despColumna, desplazamiento, multiplo, despCalculados[numFilas][numColumnas]; for(despFila=0;despFila
4

despCalculados[despFila][despColumna]= (despFila+1)*despColumna+desplazamiento * multiplo; }; for(despFila=0;despFila
El programa utiliza dos ciclos for para calcular e iniciar cada uno de los elementos del arreglo a su respectiva distancia relativa desde la base. El arreglo creado tiene 4 filas y 5 columnas por fila, haciendo un total de 20 elementos enteros. Los arreglos multidimensionales son almacenados de forma lineal en la memoria de la computadora. Los elementos en los arreglos multidimensionales están agrupados desde el índice más a la derecha hacia el centro. En el ejemplo anterior, fila 1, columna 1 sería el elemento 3 del arreglo almacenado. Aunque el cálculo del desplazamiento aparece un poco difícil, es referenciado fácilmente cada elemento del arreglo. La salida del programa anterior es: Fila actual: 0 Distancia relativa desde la base: 0 1 2 3 4 Fila actual: 1 Distancia relativa desde la base: 5 6 7 8 9 Fila actual: 2 Distancia relativa desde la base: 10 11 12 13 14 Fila actual: 3 Distancia relativa desde la base: 15 16 17 18 19 dosdim has exited with status 0.

Arreglos como argumentos de funciones Es necesario recordar tres cosas al pasar arreglos como parámetros de funciones: 1. Todos los arreglos son pasados en llamada-por referencia. 2. Debido a que el arreglo es pasado en llamada por referencia, sería incorrecto para la función llamada devolver el arreglo en una sentencia return();. Esta sentencia está de más. 3. Todos los elementos del arreglo son pasados a las funciones en llamada por valor. lo que significa que se pasa una copia del elemento, no la dirección del elemento. 5

/* // ereArray.xcode */ #include #include #define maxArray 5 void ArrayMayuscula(char Array[maxArray]); int main (int argc, char * const argv[]) { int desplazamiento; char Array[maxArray]= {'a','e','i','o','u'}; for(desplazamiento=0;desplazamiento<maxArray; desplazamiento++) std::cout<
La salida del programa demuestra que el arreglo se pasa en llamada por referencia, ya que el primer ciclo for da como salida los contenidos de minúsculas originales: aeiou, mientras que el segundo ciclo for en main() da como salida los contenidos del arreglo después del llamado a la función ArrayMayuscula(): AEIOU. Claramente, dentro del cuerpo de la función ArrayMayuscula(), ha cambiado el arreglo de regreso en la función main(). el siguiente ejemplo es una simple modificación de este algoritmo, sólo que en vez de pasar el arreglo completo, se pasa cada elemento individual: /* // ereArray2.xcode */ #include #include #define maxArray 5 void ElementosArrayMayuscula(char unChar); int main (int argc, char * const argv[]) { int desplazamiento; char Array[maxArray]= {'a','e','i','o','u'}; for(desplazamiento=0;desplazamiento<maxArray;desplazamiento++) std::cout<
6

std::cout<<"\n"; for(desplazamiento=0;desplazamiento<maxArray;desplazamiento++) ElementosArrayMayuscula(Array[desplazamiento]); for(desplazamiento=0;desplazamiento<maxArray;desplazamiento++) std::cout<
La salida del programa es: aeiou aeiou valarray has exited with status 0.

Apuntadores Definición 2 Un apuntador es una variable que contiene una dirección de memoria. Supongamos una variable de tipo entero que se llama contenidoRAM y otra variable que se llama que puede contener una variable de tipo entero. En C/C++ una variable precedida del operador & devuelve la dirección de la variable en lugar de su contenido. Así que para asignar la dirección de una variable a otra variable del tipo que contiene direcciones se usan sentencias como esta: direccionRAM

direccionRam = &contenidoRAM

Figura 2: contenidoRAM se asigna a la localidad de memoria con dirección 7751 En la figura 2 se ilustra el nombre de la variable contenidoRAM y se observa que se encuentra en la dirección 7751 de la memoria. El contenido de esta localidad no se muestra. Una variable que contiene una dirección, tal como direccionRAM, se llama variable apuntador o simplemente apuntador. Despues que la sentencia anterior se ejecuta, la dirección de contenidoRAM será asignada a la variable apuntador direccionRAM. La relación se expresa diciendo que direccionRAM apunta a contenidoRAM. La figura 3 ilustra esta relación.

7

Figura 3: Notación de flecha para los apuntadores El accceso al contenido de una celda cuya dirección está almacenada en la variable sencillo como poner al inicio de la variable apuntador un asterisco: se ha hecho es eliminar la referencia directa. Por ejemplo, si se ejecutan las siguientes dos sentencias, el valor de la celda llamada contenidoRAM será de 20 (véase la figura 4). direccionRAM es tan *direccionRAM. Lo que

direccionRAM = &contenidoRAM; *direccionRAM = 20;

Figura 4: A contenidoRAM se le asigna el valor entero 20

Declaraciones de variables apuntador C/C++ requiere una definición para direccionRAM que pueda contener la dirección

cada variable. Para definir una variable apuntador de una variable int, se escribe:

int *direccionRAM;

Realmente existen dos partes separadas en esta declaración. El tipo de dato de direccionRAM es: int *

y el identificador para la variable es direccionRAM

El asterisco que sigue a int significa ``apuntador a''. Esto es, el siguiente tipo de dato es una variable apuntador que puede contener una dirección a un int: int * En C/C++ una variable apuntador contiene la dirección de un tipo de dato particular: char *direccion_char; char *direccion_int;

8

El tipo de dato de direccion_char es diferente del tipo de dato de la variable apuntador direccion_int. En un programa que define un apuntador a un tipo de dato y utliza éste para apuntar a otro tipo de dato, pueden ocurrir errores en tiempo de ejecución y advertencias en tiempo de compilación. Una práctica de programación pobre sería definir un apuntador de una forma y luego utilizar éste de alguna otra forma. Por ejemplo: int *direccion_int; float un_float = 98.34; direccion_int = &un_float;

Utilización de punteros en sentencias sencillas Veamos el siguiente ejemplo: /* // changeVals.xcode */ (01) #include (02) (03) int main (int argc, char * const argv[]) { (04) int A_int=15, B_int=37, Temp_int; (05) int *direccion_int; (06) (07) std::cout<<"El contenido de A_int es:"<
En la línea (04) se han declarado tres variables de tipo entero, se da a cada celda un nombre y se inicializan 2 de éstas. Supondremos que la dirección de memoria asignada para la variable A_int es la dirección 5328, y la dirección en memoria RAM asignada para la variable B_int es la dirección 7916, y la celda llamada Temp_int se le ha asignado la dirección 2385. Véase la figura 5;

Figura 5: Descripción de las tres variables en la memoria

9

En la línea (05) se define un apuntador a un tipo de dato entero llamado direccion_int. La sentencia asigna la celda y da a ésta un nombre. Luego, en la línea (09), la tercera sentencia asigna a direccion_int la dirección de A_int (figura 6).

Figura 6: direccion_int dada la dirección de A_int

La línea (10) utiliza la expresión *direccion_int para acceder al contenido de la celda a la cual apunta direccion_int: Temp_int = *direccion_int;

Por consiguiente, el valor entero 15 se almacena en la variable Temp_int. Si no se pone el * enfrente de direccion_int;, la sentencia de asignación almacenaría ilegalmente el contenido de direccion_int en la celda nombrada Temp_int, pero se supone que Temp_int contiene un entero, no una dirección. Este puede ser un error muy difícil de localizar puesto que muchos compiladores no emiten ninguna advertencia/error. Para empeorar el asunto, la mayoría de los apuntadores son cercanos, lo que significa que ocupan 2 bytes (4 bytes para aplicaciones de 32-bits), el mismo tamaño que un entero en una PC. La sentencia (11) copia el contenido de la variable B_int en la celda apuntada por la dirección almacenada en direccion_int(figura 7): *direccion_int = B_int;

Figura 7: Se copia el contenido de B_int usando la notación de flecha de apuntadores

10

La última sentencia en la línea (12) simplemente copia el contenido de una variable entera, en otra variable entera B_int (figura 8 )

Temp_int

Figura 8: Se copia Temp_int en B_int utilizando asignación normal.

Debemos de asegurarnos de comprender la diferencia entre qué se referencia cuando una variable puntero está precedida por el operador de indirección y cuándo no está precedida por este operador. Para este ejemplo, la primera sintaxis es un apuntador a una celda que puede contener un valor entero. La segunda sintaxis referencia la celda que contiene la dirección de otra celda que puede contener un entero.

Utilización incorrecta del operador de dirección No se puede utilizar el operador de dirección sobre toda expresión C/C++ . El siguiente ejemplo demuestra aquellas situaciones donde no se puede aplicar el operador de dirección &. puedeAlmacenarDireccionDeConstante = &37; int RAM_int = 5; puedeAlmacenarDireccionDeExpresionTemp = &(RAM_int +15); puedeAlmacenarDireccionDeRegistro = &varRegistro;

La primera sentencia trata de obtener ilegalmente la dirección de un valor constante integrado. La sentencia no tiene sentido puesto que 37 no tiene una celda de memoria asociada con éste. La segunda sentencia de asignación intenta devolver la dirección de la expresión RAM_int+15. No existe dirección asociada con la expresión puesto que la expresión en sí misma es realmente un proceso de manipulación de pila. Normalmente, el último ejemplo respeta la demanda del programador para definir varRegistro como un registro más que como una celda de almacenamiento en la memoria interna. Por consiguiente, no podría devolverse y almacenarse la dirección de celda de memoria. El compilador C/C++ da la memoria de variable, no el almacenamiento de registro.

11

Estructuras

C/C++

Definición 3 Una estructura es un grupo de variables las cuales pueden ser de diferentes tipos sostenidas o mantenidas juntas en una sola unidad. La unidad es la estructura.

Sintaxis y reglas para estructuras en C/C++ En C/C++ se forma una estructura utilizando la palabra reservada struct, seguida por un campo etiqueta opcional, y luego una lista de miembros dentro de la estructura. La etiqueta opcional se utiliza para crear otras variables del tipo particular de la estructura: struct campo_etiqueta{ tipo_miembro miembro_1; tipo_miembro miembro_2; tipo_miembro miembro_3; : : tipo_miembro miembro_n; };

Un punto y coma finaliza la definición de una estructura puesto que ésta es realmente una sentencia C/C++ . Algunos de los ejemplos usan la estructura: struct stbarco{ char sztipo[iString15+iNull_char]; char szmodelo[iString15+iNull_char]; char sztitular[iString20+iNull_char]; int ianio; long int lhoras_motor; float fprecioventa; };

En un programa, podemos asociar una variable con una estructura utilizando una sentencia similar a la siguiente: struct stbarco stbarco_usado;

La sentencia define stbarco_usado de tipo struct stbarco. La declaración requiere el uso del campo etiqueta de la estructura. Si esta sentencia está contenida dentro de una función, entonces la estructura, llamada stbarco_usado, tiene un ámbito local a esa función. Si la sentencia está contenida fuera de todas las funciones de programa, la estructura tendrá un ámbito global. Es posible declarar una variable usando esta sintaxis: struct stbarco{ char sztipo[iString15+iNull_char]; char szmodelo[iString15+iNull_char]; char sztitular[iString20+iNull_char]; int ianio; long int lhoras_motor; float fprecioventa; } stbarco_usado;

Aquí la declaración de variable va antes del punto y coma final. Cuando se asocia sólo una variable con el tipo estructura, el campo etiqueta puede ser eliminado, por lo que sería posible escribir: struct {

12

char sztipo[iString15+iNull_char]; char szmodelo[iString15+iNull_char]; char sztitular[iString20+iNull_char]; int ianio; long int lhoras_motor; float fprecioventa; } stbarco_usado;

Utilización de miembros de estructuras Para accesar a los miembros de las estructuras se usa el punto u operador miembro (.). La sintaxis es: estructuraNombre.miembroNombre

Por ejemplo en: gets(stbarco_usado.szmodelo);

Aquí, stbarco_usado es el nombre asociado con la estructura, y szmodelo es una variable miembro de la estructura, otro ejemplo: std::cin rel="nofollow">> stbarco_usado.sztipo;

Esta sentencia leerá la marca del stbarco_usado en el arreglo de caracteres, mientras la próxima sentencia imprimirá el precio de venta de stbarco_usado en la pantalla. srd::cout<< stbarco_usado.fprecioventa;

Ejemplo de estructuras: /*

fractionStruct.cpp -

Programa para demostrar el uso de los tipos Struct en C++, este tipo de datos es util para los programadores para crear sus propias estructuras de tipos. */ #include using namespace std; // Definimos un nuevo tipo de estructura llamada Fraction // como la definicion se puso antes del "main" // los tipos Fraction se pueden usar como prototipos struct Fraction { // declaramos sus dos miembros int numerator; int denominator; }; // Note el punto y coma al final // funciones prototipos void getFraction(Fraction &f); void printFraction(const Fraction &f); int main (int argc, char * const argv[]) {

13

// declaramos variables de tipo Fraction Fraction f1, f2; // obtenemos dos fracciones y las desplegamos getFraction(f1); cout << "\nf1 = "; printFraction(f1); getFraction(f2); cout << "\nf2 = "; printFraction(f2); cout << endl; return 0; } // pedimos al usuario los valores del denominador y numerador // los almacenamos en su adecuado lugar en la estrcututra; checamos si // el valor del denominador es valido y lo ponemos en 1 si no lo es. void getFraction(Fraction &f) { cout << "\nEnter the numerator: "; cin >> f.numerator; cout << "Enter the denominator: "; cin >> f.denominator; if (f.denominator == 0) { cout << "\nIllegal denominator! Denominator is being set to 1.\n"; f.denominator = 1; } } // imprimimos la fraccion void printFraction(const Fraction &f) { cout << f.numerator << "/" << f.denominator << "\n"; }

Nota sobre las funciones prototipos: Las funciones prototipo tienen los siguientes usos importantes: Establecen el tipo devuelto para las funciones que devuelven otros tipos diferentes que int. Aunque las funciones que devuelven valores enteris no necesitan prototipos, se recomienda tener prototipos. Sin prototipos completos, se hacen las conversiones estándares, pero no se checan los tipos o los números de argumentos con el número de parámetros. Los prototipos se usan para inicializar apuntadores a funciones, antes de que las funciones sean definidas. La lista de parámetros se usa para checar la correspondencia de los argumentos en la llamada a la función con los parámetros en la definición de la función const en parámetros de funciones

El especificador const puede ser utilizado en la definición de parámetros de funciones. Esto resulta de especial utilidad en tres casos. En los tres el fin que se persigue es el mismo: indicar que la función no podrá cambiar dichos argumentos: Con parámetros de funciones que sean de tipo matriz (que se pasan por referencia). Ejemplo: int strlen(const char[]);

14

Cuando los parámetros son punteros (a fin de que desde dentro de la función no puedan ser modificados los objetos referenciados). Ejemplo: int printf (const char *format, ...); Cuando el argumento de la función sea una referencia, previniendo así que la función pueda modificar el valor referenciado. Ejemplo: int dimen(const X &x2);

Ejercicios de programación 1. El siguiente algoritmo es el método de inserción para ordenar elementos en un arreglo: 2. insertionSort(A) 3. for j:=2 to length[A] 4. do key:=A[j] 5. -> Inserta el elemento A[j] 6. -> en la secuencia ordenada A[1..j-1] 7. i:=j-1 8. while i>0 and A[i]>key 9. do A[i+1]=A[i] 10. i:=i-1 11. A[i+1]:=key 1. desarrolle un programa en C/C++ del método de inserción 2. ilustre cómo opera el algoritmo insertionSort(A) usando A=<31,41,59,26,41,58> 12. Reescriba el programa y nómbrelo insertionSortNondec para que

como entrada el arreglo ordene los elementos en

orden decreciente 13. Considere el siguiente problema de búsqueda: Input: Una secuencia de Output:

números

y un valor

.

Un índice tal que o el valor espacial si no ocurre en . Escriba un programa que resuelva este problema de búsqueda. 14. Considere el problema de sumar dos números binarios de longitud . Cada número se almacena en uno de los arreglos y de tamaño . La suma se almacena en un arreglo de tamaño , también como un número binario. Escriba un programa que resuelva este problema.

La pila Uno de los conceptos más útiles en las ciencias de la computación es el de pila. En esta sección vamos a definir este concepto de manera abstracta y veremos cómo se usa para convertirse en una herramienta concreta y de gran valor en las soluciones de problemas. La información contenida en esta sección se ha tomado de (TA83).

Definición y ejemplos Definición 4 Una pila (stack) es una colección ordenada de elementos en la cual se pueden insertar nuevos elementos por un extremo y se pueden retirar otros por el mismo extremo; ese extremo se llama ``la parte superior'' de la pila. Si tenemos un par de elementos en la pila, uno de ellos debe estar en la parte superior de la pila, que se considera ``el más alto'' en la pila que el otro. En la figura 9 el elemento F es el más alto de todos 15

los elementos que están en la pila. El elemento D es el más alto de los elementos A,B,C, pero es menor que los elementos E y F.

Figura 9: Pila con 6 elementos Para describir cómo funciona esta estructura, debemos agregar un nuevo elemento, el elemento G. Después de haber agregado el elemento G a la pila, la nueva configuración es la que se muestra en la figura 10.

Figura 10: Operación de insertar el elemento G en la pila P De acuerdo con la definición, existe solamente un lugar en donde cualquier elemento puede ser agregado a la pila. Después de haber insertado el nuevo elemento, G ahora es el elemento en la cima. Debemos aclarar en qué pila deseamos insertar elementos, puesto que es posible tener más de una pila al mismo tiempo. Cuando se desea retirar un elemento de la pila, solo basta ordenar que sea retirado un elemento; no podemos decir ``retira C de la pila'', porque C no está en la cima de la pila y solamente podemos retirar el elemento que está en la cima. Para que la sentencia ``retira C de la pila'' tenga sentido, debemos replantear las órdenes a algo como: Retira de la pila hasta que el elemento retirado sea C.

Ni siquiera es necesario decir: ``Retira un elemento de la pila...'' porque es sobreentendido que solamente se puede sacar un elemento a la vez. Siguiendo nuestro ejemplo, ahora deseamos retirar de la pila P. La configuración global de la pila es como se muestra en la figura 11

16

Figura 11: Operación de retirar de la pila P El concepto de pila es muy importante en computación y en especial en teoría de lenguajes de programación. En lenguajes procedurales como Pascal o C, la pila es una estructura indispensable, debido a las llamadas a función. Resulta que el flujo de instrucciones va de arriba hacia abajo, y cuando ocurre una llamada a alguna función, el estado global del sistema se almacena en un registro y éste en una pila. Así que la pila va a contener todas las llamadas a procedimientos que se hagan. Cuando se termina de ejecutar algún procedimiento, se recupera el registro que está en la cima de la pila. En ese registro están los valores de las variables como estaban antes de la llamada a la función, o algunas pueden haber cambiado si valor, dependiendo del ámbito de las variables. Cada elemento en la pila que es retirado, significa que se ha terminado de ejecutar alguna función. Cuando se termina de ejecutar el programa, la pila de llamadas a subprogramas debe haber quedado en 0 también, de otro modo podría causar algún tipo de error. Esto nos lleva a pensar en otras utilidades de la pila. La pila sirve para encontrar errores. La dinámica de la pila, es decir, la manera en cómo entran los datos a la estructura de datos y cómo salen, se denomina fifo, que viene del ingés first in first out (primero en entrar, primero en salir).

Figura 12: Dinámica de la pila P En la figura 12 se muestran ``fotografías'' en distintos momentos de la pila, cuando se desea insertar H justo debajo de F. Para hacer esto se requiere, retirar tantos elementos como sean necesarios, aquí se han retirado de la cima G y F para luego insertar H, que quedará posteriormente debajo de F. 17

Lo que sucede es que, cuando se retira el elemento G se debe hacer una evaluación para determinar si el elemento retirado es el elemento objetivo, en este caso el elemento objetivo es F, puesto que se desea insertar un elemento debajo de F. Después de haber insertado F, insertamos de nuevo los elementos F y G en ese orden, además de insertar finalmente el elemento I que queda en la cima de la pila. Enseguida veremos con más detalle las operaciones básicas de las pilas.

Operaciones básicas Las operaciones básicas de una pila son: 1. 2. 3. 4.

En la pila S, insertar un elemento e: push(S,e), Retirar un elemento de la pila S: pop(S), Verificar si la pila S está vacía: stackempty(S) y Saber cuál es el elemento en la cima de la pila S: stacktop(S). enseguida cada una de estas operaciones:

La operación push

Esta operación sirve para insertar un elemento e en la pila S, lo vamos a escribir como: push(S,e)

Después de hacer esta operación sucede que: El elemento en la cima de la pila S ahora es e La operación pop

Para retirar un elemento de la pila S y asignarlo a una variable del mismo tipo que el tipo de los elementos de la pila, usaremos la operación pop escribiéndola como: v=pop(S);

En donde v es una variable que almacena el valor del elemento que estaba en la cima de S. Hacer esta operación tiene algunas implicaciones: La variable v debe ser del mismo tipo que los elementos almacenados en la pila. Solamente se puede retirar un elemento de la pila a la vez. Antes de la operación, e era el elemento en la cima, ahora ya no lo es más. El apuntador ``cima'' decrece en una unidad. La operación stackempty

Esta operación toma como argumento una estructura del tipo stack (pila) y devuelve un valor booleano, devuelve un true si la pila está vacía y devuelve un false si la pila tiene al menos un elemento, es decir:

18

La operación stacktop

La operación stacktop(S) devuelve el valor del elemento en la cima de la pila S. Para hacer esta operación escribiremos: v=stacktop(S)

las implicaciones de usar esta operación son: Se hace una copia del elemento que está en la cima En realidad se hacen dos operaciones, primero se hace v=pop(S), luego un push(S,v), porque después de la operación stacktop, la pila S queda sin cambio alguno.

Ejemplo: Número de paréntesis Supongamos ahora la expresión ((5+6)*4)/(17+9), una de las condiciones para que sea una expresión aritmética correcta en que tengas sus paréntesis balanceados, así que deseamos saber si el número de paréntesis que abres es el mismo número de paréntesis que cierran. Para resolver este problema usaremos el concepto de pila. La idea es simple. Vamos a leer cada elemento de la expresión, si se trata de un paréntesis que abre, entonces lo insertaremos en una pila; si se trata de un paréntesis que cierra, entonces sacamos un elemento de la pila. Al terminar de leer la expresión revisaremos si la pila está vacía, en cuyo caso habremos concluido que el número de paréntesis que abre es el mismo que el número de paréntesis que cierra y la expresión tiene paréntesis balanceados. Veamos cómo funciona: `(' : push(S,`(') `(' : push(S,`(') `5' :

nada que hacer `+' : nada que hacer `6' : nada que hacer `)' : v=pop(S) `*' :

nada que hacer `4' : nada que hacer `)' : v=pop(S) `/' :

nada que hacer `(' : push(S,`(') `17':

19

nada que hacer `+' : nada que hacer `9' : nada que hacer `)' : v=pop(S)

Empezamos con un contador iniciado en 0, y por cada push aumentamos un contador, y por cada pop decrementamos el contador. Al final vemos el valor del contador, si el contador=0 entonces terminamos con éxito, de otro modo señalamos el error. En la figura 13 se muestra la actividad de la pila a medida que se van agregando y quitando elementos.

Figura 13: Evaluación del balance de paréntesis en una expresión aritmética

La estructura de datos Pila en

C/C++

Una pila está conformada por dos elementos: Un espacio suficientemente grande para almacenar los elementos insertados en la pila Una parte que nos señale cuál es el elemento en la cima de la pila. Estas partes las conformamos en una estructura, descrita como sigue: definir numero maximo de elementos en la pila definir nuevo tipo estructura llamado "stack" con item : un arreglo de 1 a maximos elementos enteros top : un numero de 0 a maximos elementos fin de la nueva estructura

Fácilmente podemos describir un código en C/C++ que represente lo anteriormente propuesto. // En la parte de definiciones #define maxElem 100 // En la parte de tipos struct stack { int item[maxElem]; int top; }; // En la parte de variables struct stack A;

20

La representación en

C/C++

de las operaciones de una pila

En esta sección veremos una implementación de las cuatro operaciones básicas de las pilas. Todas estas operaciones se han hecho desde un punto de vista de programación funcional, sin duda se pueden describir en un modelo orientado a objetos. La operación push

El siguiente segmento de código ilustra cómo se puede implementar la operación insertar un elemento en una pila. Hemos supuesto que la pila ya está definida como una estructura stack. (1) void push(struct stack *S,int e){ (2) S->top++; (3) S->item[S->top]=e; (4) }

En la línea (1) se observa que la operación push recibe dos parámetros: la dirección de una estructura de tipo pila y un elemento de tipo entero. La línea (2) incrementa el tope (cima) de la pila en una unidad, con el fin de agregar el elemento en una posición libre de la pila, lo cual se logra en la línea (3), asignando el valor e en la casilla S->top del arreglo item de la pila. La operación pop

La operación pop se escribe en forma de código en C/C++ con la siguiente secuencia de órdenes: (1) int pop(struct stack *S){ (2) int valReturn; (3) (4) valReturn=S->item[S->top]; (5) S->top--; (6) return valReturn; (7) }

La línea (1) describe que esta función devuelve un tipo entero, el tipo de elementos guardados en la pila; luego notamos que debemos dar sólo la dirección de alguna variable de tipo estructura de pila (struct stack *). Obtener la dirección se logra con el operador de indirección (&). Las líneas (4) y (5) hacen todo el trabajo de esta función, se almacena el valor que será devuelto en una variable de tipo entero y luego se decrementa el tope de la pila. La operación stackempty

La operación stackempty se describe en el siguiente segmento de código: (1) bool stackempty(struct stack *S){ (2) bool valorDevuelto; (3) if(S->top== -1) (4) valorDevuelto=true; (5) else (6) valorDevuelto=false; (7) return valorDevuelto; (8) }

21

El encabezado de la función que se muestra en la línea (1) establece que se devuelve un valor booleano, y que se debe dar un parámetro, que es la dirección de una localidad de memoria que almacena una estructura de tipo pila. El objetivo de esta función es claro: La línea (3) establece la veracidad o falsedad del predicado (S->top==-1), determinando si el nivel del tope es igual que -1, en cuyo caso devuelve un verdadero (4), de otro modo ha de devolver un valor falso (6). Se ha establecido un -1 como vacío porque el manejo de arreglos en C/C++ empieza en el índice 0, que a diferencia de otros lenguajes como Pascal, empiezan en 1. La operación stacktop

Este es un caso especial porque no se requiere hacer ningún código. Esta función debe devolver un número entero y dejar la pila sin cambio. Para lograr esto se debe hacer un pop(&A), mostrar el elemento y luego insertar de nuevo el elemento en la pila haciendo un push(&A,elemento), notemos que se han usado los operadores de dirección para dar la dirección de la variable que alberga una estructura de tipo pila. El siguiente segmento de código ilustra cómo se han usado las funciones antes creadas, por supuesto que se pueden separar y crear una nueva función que haga lo mismo: ... (1) case 4:{ (2) if(not stackempty(&A)){ (3) valor=pop(&A); (4) std::cout<<"La cima de la pila es: "<
Problemas de programación Los siguientes ejercicios deben ser resueltos en un prográma (en C/C++ ): 1. Expresiones entrefijas y prefijas. Las expresiones aritméticas pueden representarse de varias maneras, una de ellas, la más usual es la notación entrefija. La notación entrefija establece que en medio de dos operandos se escribe un operador, como por ejemplos: 1. , donde los operandos son y , y el operador es el símbolo ; Donde el paréntesis más interno establece la mayor prioridad, de manera que primero se debe evaluar , luego dando como resultado .

, luego

y fimalmente

,

2. No hay nada que hacer, pues es un operador unario. En las expresiones prefijas se establece que el orden de escritura debe ser, primero el operador y luego la lista de operandos: 3. , donde los operandos son y , y el operador es el símbolo ; 22

4.

Lo primero que hay que hacer es tomar el primer operador y tomar los operandos necesarios siguientes (dos si se trata de un operador binario y uno si es un operador unario). En este caso se trata de evaluar . Cada uno de los operandos debe ser tratado de nuevo como una expresion en prefijo, de manera que se repite lo anterior, tomar el operador y la lista de sus operandos y tratar cada uno de sus operandos

como

expresiones

en

prefijo:

,

luego

y finalmente y evaluar. Los paréntesis cuadrados son para ilustrar el ejemplo y no son necesarios para su evaluación. 5. No hay nada que hacer, pues es un operador unario. Haga un programa en C/C++ que transforme expresiones de entrefijo a prefijo, y de prefijo a entrefijo. Los caracteres válidos son: las letras mayúsculas y minúsculas, los números enteros, los paréntesis normales, los cuatro operadores

y el operador unario

.

Figura: Ilustración del estacionamiento mencionado en el problema 2 2. en cierto punto de la ciudad hay un estacionamiento como el que se muestra en la figura 14, en donde hay lugar para 9 vehículos. haga un programa que muestre el manejo de este estacionamiento, considerando los siguientes requisitos: 1. Los vehículos proporcionan la siguiente información: Placas (6 digitos), Estado (2-3 caracteres, p.e. SON, DF, CHI, YUC), Marca, Modelo, Año-Modelo, Nombre del propietario. 2. Al llegar un vehículo se acepta solamente si hay lugar disponible. 3. Validar todas las operaciones de la pila. 4. En cualquier momento se puede sacar algún vehículo del estacionamiento, regresando los vehículos en el orden en que estaban. 5. Toda la corrida del programa debe hacerse hacia/desde la terminal estándar. 3. Haga un programa que implemente 2 pilas en 1 arreglo A[1..n] de manera que ninguna pila se desborde a menos que el número de elementos en ambas pilas sea

Colas Definición 5 Las colas son una estructura de datos similar a las pilas. Recordemos que las pilas funcionan en un depósito en donde se insertan y se retiran elementos por el mismo extremo. En las colas sucede algo diferente, se insertan elementos por un extremo y se retiran elementos por el otro extremo. De hecho a este 23

tipo de dispositivos se les conoce como dispositivos ``fifo'' (first in, first out) porque funcionan como una tubería, lo que entra primero por un extremo, sale primero por el otro extremo.

En una cola hay dos extremos, uno es llamado la parte delantera y el otro extremo se llama la parte trasera de la cola. En una cola, los elementos se retiran por la parte delantera y se agregan por la parte trasera.

Figura 15: Dinámica de una cola. a) estado actual con una cola con tres elementos a,b,c; b) estado de la cola cuando se agrega el elemento d; c) estado de la cola cuando se elimina el elemento a del frente de la cola

En la figura 15 se muestra una actividad típica de la cola, en donde se muestra que se agregan datos por la parte trasera de la cola y se eliminana datos por el frente de la cola.

Si

es una cola y

es un elemento, se pueden hacer tres operaciones básicas con las colas:

1. insert(Q,x), que inserta el elemento x en la parte trasera de la cola Q. 2. x=remove(Q), que almacena en x el valor del elemento retirado de la parte frontal de la cola Q. 3. empty(Q), que es un predicado de valor booleano, y es cuando la cola Q tiene 0 elementos, y es cuando la cola Q tiene al menos un elemento, en cuyo caso, ese único elemento es la parte frontal y la parte trasera de la cola al mismo tiempo.

Teóricamente no hay límite para el tamaño de la cola, asi que siempre se debería poder insertar elementos a una cola, sin embargo, al igual que las pilas, normalmente se deja un espacio de memoria para trabajar con esta estructura. Por el contrario, la operación solamente se puede hacer si la cola no está vacía.

Estructura de las colas en

C/C++

De manera similar a las pilas, las colas definen una estructura no estándar, de manera que se debe crear un nuevo tipo de dado, el tipo cola, que debe tener los siguientes elementos: Un arreglo de elementos de algún tipo específico, puede incluso ser un tipo estándar o no. Un número que indica el elemento que está en la posición del frente de la cola. Un número que indica el elemento que está en la posición trasera de la cola. Suponiendo que los elementos son números enteros, una idea para representar una cola en C/C++ es usar un arreglo para contener los elementos y emplear otras dos variables para representar la parte frontal y trasera de la cola. 24

#define maxQueue 100 struct cola{ int items[maxQueue]; int front; int rear; };

Esta representación con arreglos es completamente válida, pero debemos tener cuidado con los límites del arreglo. Suponiendo que no existiera la posibilidad de caer en un desbordamiento del arreglo, es decir, que se insertaran más elementos de lo que el arreglo puede almacenar, la operación insert podría quedar como: void insert(struct cola *C, int e){ C->items[++C->rear]=e; } y al operación x=remove(Q) int remove(struct cola *C){ return C->items[C->front++]; } y finalmente la operación empty(Q): bool empty(struct cola *C){ if(C->front>C->rear) return true; else return false; }

Colas con prioridad Una cola con prioridad es una estructura de datos en la que se ordenan los datos almacenados de acuerdo a un criterio de prioridad. Hay dos tipos de colas de prioridad: Las colas de prioridad con ordenamiento descendente. Las colas de prioridad con ordenamiento ascendente. En las colas de prioridad ascendente se pueden insertar elementos en forma arbitraria y solamente se puede remover el elemento con menor prioridad. Si CPA es una cola de prioridad ascendente, la operación insert(CPA,x) inserta el elemento x en la cola CPA; y la operación x=minRemove(CPA) asigna a x el valor del elemento menor (de su prioridad) y lo remueve de la cola. En las colas de prioridad descendente es similar, pero sólo permite la supresión del elemento más grande. Las operaciones aplicables a la cola de prioridad descendente son insert(CPD,x) y x=maxRemove(CPD), cuando CPD es una cola de prioridad descendente y x es un elemento. La operación empty(C) se aplica a cualquier tipo de cola y determina si una cola de prioridad está vacía. Las operaciones de insertar y borrar se aplican solamente si la pila no está vacía. Los elementos de la cola de prioridad no necesitan ser números o caracteres para que puedan compararse directamente. Pueden ser estructuras complejas ordenadas en uno o varios campos. Por ejemplo, las agendas telefónicas constan de apellidos, nombres, direcciones y números de teléfono y están ordenadas por apellido. 25

A diferencia de las pilas y las colas, en las colas de prioridad se pueden sacar los elementos que no están en el primer sitio del extremo donde salen los elementos. Esto es porque el elemento a retirar puede estar en cualquier parte del arreglo. Cuando se requiere eliminar un dato de una cola de prioridad se necesita verificar cada uno de los elementos almacenados para saber cuál es el menor (o el mayor). Esto conlleva algunos problemas, el principal problema es que el tiempo necesario para eliminar un elemento puede crecer tanto como elementos tenga la cola. Para resolver este problema hay varias soluciones: 1. Se coloca una marca de ``vacío'' en la casilla de un elemento suprimido. Este enfoque realmente no es muy bueno, porque de cualquier modo se accesan los elementos para saber si es una localidad vacía o no lo es. Por otro lado, cuando se remueven elementos, se van creando lugares vacíos y después es necesario hacer una compactación, reubicando los elementos en el frente de la cola. 2. Cada supresión puede compactar el arreglo, cambiando los elementos depués del elemento eliminado en una posición y después decrementando rear en 1. La inserción no cambia. En promedio, se cambian la mitad de los elementos de una cola de prioridad para cada supresión, por lo que esta operación no es eficiente.

Ejercicio de programación 1. Modifique los procedimientos de insertar, retirar y verificar-cola-vacía para que considere aprovechar los espacios dejados al retirar elementos. 2. Un deque es un conjunto ordenado de elementos del cual pueden eliminarse elementos en cualquier extremo y en el cual pueden insertarse elementos en cualquier extremo. Llamemos a los dos extremos de un deque left (izquierdo) y right (derecho). ?'cómo se representa un deque en un arreglo en C/C++ ? escriba un programa que maneje un deque, y que considere las cuatro rutinas o o o o

removeLeft removeRight insertLeft insertRight

para remover e insertar elementos en los extemos izquierdo y derecho de un deque. Asegúrese de que las rutinas funcionan adecuadamente para que un deque vacío y que detectan desbordamiento y subdesbordamiento. 3. Programe las colas de prioridad ascendente y descendente. 4. Existe un estacionamiento que tiene un sólo carril que aloja hasta 10 carros. Los autos llegan por el extremo sur del estacionamiento y salen por el extremo norte del mismo. Si llega un cliente para recoger un carro que no está en el extremo norte, se sacan todos los automóviles de ese lado, se retira el auto y los otros coches se restablecen en el mismo orden que estaban. Cada vez que sale un auto, todos los autos del lado sur se mueven hacia adelante para que en todas las ocasiones todos los espacios vacíos estén en la parte sur del estacionamiento. Escriba un programa que lea un grupo de lineas de ingreso. Cada línea contiene una ``A'' para las llegadas y una ``D'' para las salidas y un número de placa. Se supone que los carros llegan y salen en el orden especificado en la entrada. El programa debe imprimir (en la terminal estándar) un mensaje cada vez que entra o sale un auto. Cuando llega un carro, el mensaje debe especificar si hay espacio o no para él en el estacionamiento. Si no hay espacio, el carro espera hasta que hay espacio o hasta que se lee una línea de salida para el auto. Cuando queda disponible espacio, debe imprimirse otro mensaje. Cuando salga un coche, el mensaje debe incluir la cantidad de veces 26

que se movió el auto dentro del estacionamiento, incluyendo la salida misma, pero no la llegada. Este número es 0 si el carro sale de la fila de espera.

Recursión Un tema fundamental para los próximos temas es el de recursión. La recursión es muy importante tanto en matemáticas como en computación, pues se usa recursión para definir procedimientos autosimilares. Definición 6 Decimos que un objeto es recursivo si en su definición se nombra a sí mismo.

En programación, una función es recursiva si en el ámbito de esa función hay una llamada a sí misma, C/C++ permite esta clase de acciones. Los algoritmos recursivos dan elegancia a las soluciones de los problemas. Un ejemplo clásico es el factorial de un número.

Una manera de definir el factorial de un número

es:

es decir, el producto de todos los números enteros menores o guales que él, lo que se puede resolver fácilmente con una función iterativa, esto es, una función con un ciclo que itere suficientes veces, incrementando un valor y entonces ir almacenando en una variable el resultado de esas multiplicaciones. Una implementación de esta definición iterativa es: (1) (2) (4) (5) (6) (7) (8)

int i,n; long double valorAc; valorAc=1.0; std::cout << "Numero entero:"; std::cin>> n; for(i=1; i<=n; i++) valorAc = valorAc*i; std::cout<<"El factorial de "<
El ciclo principal es en la línea (7). No hay ningún truco hasta aquí. La única observación importante es en la línea (2) en donde se declara el tipo long double para el valor del resultado, la razón para tal acción es que el número factorial crece muy rápido y aún con entradas en el rango de los caracteres (hasta 255), el factorial es muy grande. Este procedimiento computacional no hace uso de técnicas especiales empleadas para tratar números grandes. Sin embargo una solución más elegante es usar la definición recursiva, y esta es:

El programa en C/C++ es el que se muestra a continuación: ( 1) double factorial(double a){ ( 2) if (a<=1) return 1.0; ( 3) else return (a *factorial(a-1.0));

}

27

( 4) ( 5) int main (int argc, char * const argv[]) { ( 6) double n; ( 7) std::cout << "Numero entero:"; ( 8) std::cin>> n; ( 9) std::cout<<"El factorial de "<
Aquí hay varias cosas que señalar, en primer lugar se ha creado una nueva función, a diferencia de la definición iterativa en donde era suficiente trabajar en el programa principal. Esta función se llama factorial (como era de suponerse), y empieza su encabezado en la línea (1). Allí mismo en la misma línea (1), es de notar que hemos emplado ahora el tipo double tanto para el tipo devuelto como para el tipo del argumento, a diferencia de la versión iterativa en donde empleábamos tipos diferentes. La razón es que al iniciar la recursión el argumento es del tipo devuelto, así que deben ser del mismo tipo. Cada llamada recursiva genera una entrada a una pila, en donde se guardan (como elementos) los estados generales del sistema al momento de hacer la llamada, entonces, cuando se termina la función se recupera una entrada de la pila. En la figura 16 ilustra cómo funciona la recursividad cuando se intenta obtener el factorial(5).

Figura 16: Recursividad cuando se ejecuta factorial(5)

La serie Fibonacci

Una de las series más famosas es sin duda alguna la serie de Fibonacci:

Un poco de observación es suficiente para encontrar que cualquier número (a partir del tercero de la serie, o sea el segundo 1) es igual a la suma de los dos números anteriores. Daremos en primer lugar la versión iterativa. En este algoritmo deseamos encontrar el -ésimo número de la serie Fibonacci. Así si el resultado del algoritmo debe ser ; si el resultado debe ser . La versión iterativa empieza desde los primeros 1's, sumándolos y encontrando el tercero, luego para encontrar el cuarto número se suman el tercero (recién encontrado) y el segundo, y así en adelante hasta encontrar el número buscado. #include

28

int main (int argc, char * const argv[]) { int i,n,fib,fib1,fib2,fibx; std::cout<<"Un numero entero:"; std::cin>>n; fib1=2; fib2=1; i=3; if((n==1)||(n==2)) fib=1; else{ do{ fib = fib1 + fib2; fibx = fib1; i++; fib1 = fib; fib2 = fibx; }while(i
La definición recursiva para encontrar todos los

primeros números de la serie Fibonacci es:

En el siguiente código, la solución que propone la recursividad resulta en una programación elegante, aunque costosa. El código que hace esto es: ( 1) ( 2) ( 3) ( 4) ( 5) ( 6) ( 7) ( 8) ( 9) (10) (11) (12) (13) (14) (15) (16)

#include //==================== int fib(int val){ if ((val==1)||(val==2)) return 1; else return (fib(val-1)+fib(val-2)); } //==================== int main (int argc, char * const argv[]) { int n; std::cout<<"Numero entero:"; std::cin>>n; std::cout<<"\nEl "<< n <<"-esimo numero fibonacci es: "<< fib(n); return 0; }

Como regla general, cualquier algoritmo recursivo se puede reescribir en un algoritmo iterativo. La ventaja de tener un algoritmo iterativo es que no se usa una pila para guardar llamadas a la misma función de manera recursiva, esto es una ventaja porque el espacio de memoria destinado al uso de la pila es generalmente limitado, de manera que cuando se hacen demasiadas funciones push seguramente llegará el momento en que la pila ``se desborde'', que por cierto es un término usado en computación para decir que ya no hay más espacio disponible en la pila.

29

Peligros en la recursividad El principal peligro al usar recursividad, es no tener una manera de salir del paso recursivo, esto es peligroso porque se hacen llamadas a la misma función, lo que significa una entrada en la pila donde se almacenan los estados generales del programa. Para decidir hacer un programa recursivo se deben de tener al menos dos cosas muy claras: 1. El paso base: Esta es la clave para terminar la recursión, es cuando deja de hacer llamadas a la función recursiva y hace evaluaciones devolviendo los resultados. En el ejemplo de la serie de Fibonacci, el paso base está en la línea ( 5). Además se debe asegurar de que es posible entrar a este paso. 2. El paso recursivo: Es la parte de la definición que hace llamadas a esa misma función y que es la causante de las inserciones en la pila, almacenando en cada una de las llamadas, información del programa, del estado de sus variables locales y globales. En el mismo ejemplo de la serie Fibonacci, el paso recursivo se muestra en la línea ( 7). Otras cosas que se deben tener claras son por ejemplo si se pasa una variable como referencia o por valor, si las variables apuntadores son del tipo adecuado etc. Frecuentemente tanto el paso base como el paso recursivo, se encuentran en una sentencia condicional if, pero porsupuesto que es posible usar cualquier otra sentencia de control, dependiendo de las necesidades particulares del problema. El siguiente ejemplo ilustra este problema ( 1) ( 2) ( 3) ( 4) ( 5) ( 6) ( 7) ( 8) ( 9) (10) (11) (12)

#include int malaFuncion( int n ){ std::cout << "malaFuncion es una recursion infinita. n="<
Ejercicios de programación Los siguientes ejercicios deben de ser programados en C/C++ : 1. Búsqueda binaria: Considere un arreglo de elementos (números enteros está bien) en el cual los objetos ya estan ordenados, y se desea encontrar un elemento dentro de este arreglo. Es decir, se desea realizar una ``búsqueda''. La idea general de este método de búsqueda binaria es: o Si el arreglo tiene 1 elemento, se compara con el numero requerido y la búsqueda termina. o Si el arreglo tiene más de 1 elemento, tendremos que dividir en dos el arreglo y decidir en qué parte del arreglo buscar; luego buscarlo usando busqueda binaria 2. Escriba un programa para calcular la cantidad de maneras diferentes en las cuales un entero se puede expresar como la suma de dos enteros menores

y

tales que 30

Listas Hay dos desventajas serias con respecto a las estructuras estáticas de pilas y colas usando arreglos. Estas desventajas son que tienen un espacio limitado de memoria y la otra desventaja es que es posible no ocupar toda la memoria disponible, haciendo que se desperdicie espacio. Una solución es usar listas. Las listas son estructuras de datos que son dinámicas, esto significa que adquieren espacio y liberan espacio a medida que se necesita. Sin embargo, hay una advertencia. Como regla general siempre hay que tener cuidado al manejar direcciones de espacios de memoria, porque es posible que accedamos a una localidad de memoria de la cual no deseábamos cambiar su contenido. Antes de estudiar las listas, daremos una breve introducción a los grafos, pues las listas son un caso especial de los grafos.

Grafos Los grafos son una manera visual de representar las relaciones. Definición 7 Si y son dos conjuntos, decimos que está relacionado con si es verdadera una sentencia que considere a ambos elementos. Esta sentencia puede ser cualquier predicado, por ejemplo: ``es padre de'', ``debe dinero a'', ``toma el curso de'' etc.; si el predicado es verdadero para ese par de elementos, lo escribimos como , y si el predicado es falso, lo escribimos como

.

Así los ejemplos citados, si Si

es el conjunto de alumnos,

se puede leer: es el conjunto de materias y

es ``toma el curso'', entonces

se lee `` . En la figura 17 se puede apreciar esto en forma de diagramas de Venn. Si es el conjunto de personas y es también el conjunto de personas, y es ``debe dinero a''; significa que ``marisol debe dinero a rafaelle'' y de ningún modo es al contrario, es decir ``rafaelle no debe dinero a marisol''.

Figura 17: Relación ``toma el curso de'' para los conjuntos

de personas y

de materias. 31

Los elementos de la figura 17 definen un nuevo conjunto de elementos, el conjunto de pares de elementos que están relacionados. Así la relación ``toma el curso de'' es el siguiente:

Gráficamente podemos ilustrar el conjunto muestra en la figura 18.

de ``toma el curso de'' con un grafo como el que se

Figura 18: Grafo que ilustra la relación ``toma el curso de''. De manera que podemos definir un grafo como una representación gráfica de una relación. Definición 8 Para definir formalmente un grafo debemos establecer la siguiente tupla:

Donde es un conjunto de aristas y un conjunto no vacío de nodos. En el caso de conjunto es el conjunto de nodos y el conjunto de flechas es el conjunto de aristas.

, el

Notemos que el conjunto de aristas puede ser un conjunto vacío, pero de ningún modo hay grafo sin nodos, es decir el conjunto debe ser diferente que el conjunto vacío.

Supongamos ahora

y la siguiente relación en

:

Esta relación luce como aparece en la figura 20.

32

Figura: Relación

de A en A

y en forma de grafo es:

Figura: Grafo de la relación A esta clase de grafos, en las que cada nodo tiene a lo más una arista dirigida que sale y a lo más una arista dirigida que entra, se le llama lista.

Listas simplemente encadenadas Como vimos en la sección anterior, una lista es una relación de elementos, tales que cada elemento está relacionado con únicamente un elemento del conjunto, diferente a sí mismo. Como cada elemento puede tener a lo más una arista dirigida que sale y una arista dirigida que entra, bien puede tener 0 aristas que salen, o cero aristas que entran. Si el nodo tiene 0 aristas que salen, entonces es el final de la lista. Si el nodo tiene 0 aristas que entran, entonces es el inicio de la lista. Por razones prácticas, se dibujan una flecha que sale de un identificador de la lista y entra al inicio de la lista y otra flecha que sale del final de la lista y apunta a un símbolo que se llama NULO.

33

Figura: Grafo de la relación

con apuntadores del nombre de la lista listaLigada y hacia NULL

En C/C++ el identificador de la lista contiene la dirección del primer elemento de la lista, así como sucede con los arreglos. El valor NULO es útil para saber cuándo termina la lista, es una constante estándar y no tiene valor. El contenido de los nodos, como ya hemos visto, son los elementos de un conjunto. Si ese conjunto tiene elementos estructurados, también es válido usarlos. Normalmente cada nodo de la lista está estructurado con dos partes: 1. La parte de información. 2. La parte de dirección al siguiente nodo de la lista. El campo de información contiene el elemento real de la lista. El campo de dirección al siguiente contiene un apuntador al elemento con el cuál está relacionado, es decir, al elemento siguiente de la lista. La lista completa se accede mediante el identificador de la lista. El campo de la dirección del último nodo apunta a una dirección nula. La lista que no tiene elementos (solamente tiene un identificador que apunta a nulo) se llama lista nula o lista vacía. Una lista se inicializa a una lista vacía haciendo lista=null, recordemos que lista es un apuntador a una dirección de memoria que puede albergar una variable del tipo que se hayan definido los nodos; null es una dirección de cualquier tipo, así que el compilador asigna la dirección null a lista. Enseguida vamos a dar una lista de términos usados para manejar los elementos de una lista simplemente encadenada, aunque no son los que usa C/C++ , pero sí son bastante claros para hacer algoritmos. Si p es un apuntador a la dirección de una variable del tipo declarado para los nodos de una lista: node(p):

hace referencia al noso al que se apunta mediante p. info(p):

hace referencia a la información del nodo al que apunta p. next(p): hace referencia a la parte dirección siguiente y, por tanto, es un apuntador. 34

Así que la expresión info(next(p)) significa que se hace referencia a la sección de información del nodo siguiente al que apunta p. Insertar y eliminar nodos de una lista

En el uso de las listas ligadas se ven involucradas varias operaciones, entre ellas la de insertar un nuevo nodo a la lista y la operación de eliminar un nodo de la lista. En ambos casos debemos recordar que se trata de manejo de la memoria, así que insertar un nodo en la lista significa obtener un espacio de memoria disponible y relacionarlo con los elementos de la lista; así mismo, eliminar un nodo de la lista significa liberar la memoria que ocupa ese nodo sin perder la relación con el resto de los nodos de la lista. Insertar un elemento al inicio de la lista. La operación p=getnode(); obtiene un nodo vacío y establece el contenido de una variable nombrada p en la dirección de este nodo, como se muestra en la figura 22.a. Este nodo aún no pertenece a alguna lista, simplemente se ha logrado dedicar un especio de memoria que es apuntado por p, figura 22.b.

Figura 22: a) Creación de un nuevo nodo. b) El nuevo nodo debe de ir insertado al frente, atrás o en medio de la lista.

Una vez que se ha creado un nuevo espacio para el nuevo nodo, se debe de establecer la parte de información de ese nodo con la operación info(p), como se ilustra en el siguiente ejemplo con el dato 6. info(p)=6;

Después de esstablecer la parte de información es necesario establecer la parte siguiente de este nodo. Debido a que node(p) va a insertarse en la parte delantera de la lista, el nodo que sigue debe ser el primer nodo actual de la lista. Debido a que la variable lista (el identificador de la lista) contiene la dirección de ese primer nodo, node(p) se agrega a la lista ejecutando la operación next(p)=lista;

Esta operación coloca el valor de lista (la dirección del primer nodo en la lista) en el campo de node(p). Estos pasos se ilustran en la figura 23

siguiente

35

Figura 23: Operaciones involucradas en la inserción de un nuevo nodo al inicio de una lista: c) info(p). d) next(p)=list. e) list=p

Hasta ahora, p apunta a la lista con el elemento adicional incluido. Sin embargo, debido a que list es el apuntador externo a la lista deseada, su valor debe modificarse en la dirección del nuevo primer nodo de la lista. Esto se hace ejecutando la operación list=p;

En resumen, ya tenemos un algoritmo para insertar un elemento al inicio de una lista simplemente ligada, al reunir todos los pasos tenemos: p=getnode(); info(p)=6; next(p)=list; list=p;

Eliminar un elemento de la lista. Para eliminar un elemento del inicio de la lista, se siguen los mismos pasos que se usan para insertar un elemento, pero en un orden diferente: p=list; x=info(p); list=next(p);

Comentaremos cada una de estas tres líneas, que se pueden apreciar en la figura 24

36

Figura 24: Operaciones involucradas en la eliminación de un nodo al inicio de una lista: c) p=list). d) x=info(p). e) list=next(p)

Listas en C/C++ con arreglos

Vamos a empezar una primera implementación de listas usando arreglos, cada elemento del arreglo debe ser un elemento compuesto. Cada elemento debe contener una parte para la información y otra parte para apuntar al elemento siguiente: #include ( 1) #define numNodes 500 ( ( ( (

2) struct nodeType{ 3) int info; 4) int next; 5) };

( 6) struct nodeType node[numNodes]; int main (int argc, char * const argv[]) { std::cout << "Hello, World!\n"; return 0; }

En el programa anterior, en las líneas (2) a (5) se crea un nuevo tipo de dato, el tipo nodo. Cada nodo tiene dos partes, su parte de información y su parte de apuntador al siguiente. Como solamente tenemos 500 nodos (declarados en la línea (1), el tipo de siguiente es entero y hemos decidido almacenar números enteros solamente. En la línea (6) se ha declarado una variable global de tipo arreglo de estructura de nodos, es decir, se ha creado un arreglo de 500 nodos. En este esquema, el último nodo apunta a NULL, que se representa con el valor entero -1. Tenemos también los siguientes elementos de cada nodo: node[p] corresponde a next(p), por la 37

notación propia del lenguaje; también node[p].info para info(p) y finalmente node[p].next hace referencia al nodo siguiente next(p). Al principio todos los nodos están sin usar, porque solamente se ha creado el arreglo. Así que todos los nodos van a formar parte de una lista de nodos disponibles. Si se usa la variable global avail para apuntar a la lista disponible, podríamos organizar inicialmente esta lista como: void inicializaAvail(void){ int i; avail = 0; for(i=0; i
Cuando se requiere un nodo para usarlo en la lista, se obtiene de la lista disponible. Cuando ya no es necesario ese nodo, se devuelve a la lista disponible. Estas dos operaciones se implementan mediante las rutinas en C/C++ getnode y freenode: int getNode(void){ int p; if (avail==-1){ std::cout<<"Overflow\n"; exit(1); } p=avail; avail=node[avail].next; return p; }

Si avail es igual a -1 significa que no hay nodos disponibles, es decir, que el arreglo está completamente lleno. Esto significa que las estructuras de lista de un programa particular han desbordado el espacio disponible. La función freeNode acepta un apuntador (número entero) a un nodo y devuelve ese nodo a la lista de disponibles: void freeNode(int p){ node[p].next=avail; avail=p; }

Las operaciones primitivas para listas son versiones directas en C de los algoritmos correspondientes. La rutina insAfter acepta un apuntador p a un nodo y un elemento x como parámetros. Primero se asegura que p no sea nulo y después se inserta x en el nodo siguiente al indicado por p. void insAfter(int p, int x){ int q; if(p==-1){ std::cout<<"void insertion\n"; } else{ q=getNode(); node[q].info=x; node[q].next=node[p].next; node[p].next=q;

38

} }

La rutina delAfter(p,px), llamada por el enunciado delAfter(p,&x), suprime el nodo después de node(p) y almacena su contenido en x; void delAfter(int p, int *px){ int q; if((p==-1)||(node[p].next==-1)){ std::cout<<"void detection\n"; } else{ q=node[p].next; *px = node[q].info; node[p].next=node[q].next; freeNode(q); } }

Antes de llamar insAfter debemos asegurarnos de que ni p ni node[p].next sean nulos.

El uso de memoria dinámica en

C/C++

Como sabemos, en lenguaje C/C++ , &x es la dirección donde se almacena en memoria la variable x. Si p es un apuntador en C/C++, *p es el contenido de la localidad de memoria p. Si usamos C/C++ para implementar listas ligadas, podemos usar estos apuntadores. Sin embargo, primero analizaremos cómo asignar y liberar el almacenamiento en forma dinámica y cómo se accede al almacenamiento dinámico en C/C++. En C/C++ , una variable que debe contener la dirección en la memoria que almacena un número entero se crea mediante la declaración int *p;

Recordemos que esta declaración se divide en dos partes: la parte de tipo int *, que indica que se trata de un apuntador a un entero; y la parte de identificador, en este caso p. Una vez declarada la variable p como un apuntador a un tipo específico de dato, debe ser posible crear dinámicamente un objeto de este tipo específico y asignar su dirección a p. Esto se hace en C/C++ mediante la función de la biblioteca estándar malloc(size). La fucnión asigna de manera dinámica una parte de memoria de tamaño especificado en size y devuelve un apuntador a un elemento de tipo char. Consideremos las siguientes declaraciones malloc

extern char *malloc(); int *pi; float *pr;

La palabra clave extern especifica que una variable o función tiene un enlace externo. Esto significa que la variable o función a la que nos referimos está definida en algún otro archivo fuente, o más adelante en el mismo archivo. Sin embargo, en C/C++ podemos usar esta palabra clave extern con una cadena. La cadena indica que se está usando el convenio de enlace de otro lenguaje para los identificadores que se están definiendo. Para los programas C++ la cadena por defecto es ``C++''. 39

Los enunciados pi = (int *) malloc(sizeof(int)); pr = (float *) malloc(sizeof(float));

crean directamente la variable entera *pi y la variable real *pr. Estas se denominan variables dinámicas. Al ejecutar estos enunciados, el operador sizeof devuelve el tamaño en bytes de su operando. Esto se usa para conservar la independencia de máquina. Después, malloc crea un objeto de este tamaño. Por tanto, malloc(sizeof(int)) asigna almacenamiento para un entero, en tanto que malloc(sizeof(float)) asigna espacio necesario para un real. De igual manera, malloc devuelve un apuntados al almacenamiento que asigna. Este apuntador es al primer byte de este almacenamiento y es de tipo char *. Para obligar al apuntador a que señale a un entero, usamos el operador de cálculo (int *) ó (float *). El operador sizeof, devuelve un valor de tipo int, en tanto que la función malloc espera un parámetro de tipo unsigned. Para hacer que correspondan, debemos escribir pi=(int *)malloc((unsigned)(sizeof(int)));

Como ejemplo, vamos a considerar este breve código: #include int main (int argc, char * const argv[]) { ( 1) int *p, *q; ( 2) int x; ( 3) p = (int *)malloc(sizeof(int)); ( 4) *p = 3; ( 5) q = p; ( 6) std::cout<< *p << " " << *q << "\n"; ( 7) x = 7; ( 8) *q = x; ( 9) std::cout<< *p << " " << *q << "\n"; (10) p = (int *)malloc(sizeof(int)); (11) *p = 5; (12) std::cout<< *p << " " << *q << "\n"; return 0; }

En la línea (3), se crea una variable de tipo entero y su dirección se coloca en p. La línea (4) establece el valor de esa variable en 3. La línea (5) hace que la dirección q sea la misma dirección que p. El enunciado de la línea (5) es perfectamente válido, pues se asigna a una variable de tipo apuntador (q) el valor de otra variable del mismo tipo (p). En este momento *p y *q hacen referencia a la misma variable. Por tanto, la línea (6) imprime el contenido de esa variable (que ahora es 3) dos veces. En la línea (7), se almacena el valor 7 en la variable entera x. La línea (8) cambia el valor de *q al valor de x. sin embargo, dado que p y q apuntan a la misma variable, *p y *q tienen el valor 7. Por tanto la línea (9) imprime el número 7 dos veces. La línea (10) crea una nueva variable entera y coloca su dirección en p. Ahora *p hace referencia a la variable entera recién creada que todavía no ha recibido un valor. q no ha cambiado; por lo que el valor de *q sigue siendo 7. Observemos que *p no hace referencia a una variable específica única. Su valor cambia conforme se modifica el valor de p. La línea (11) establece el valor de esta variable recién creada en 5 y la línea 12 imprime los valores 5 y 7. Y así la salida del programa es: 40

3 7 5

3 7 7

mallocEjemplo has exited with status 0.

La función free se usa en C para liberar almacenamiento de una variable asignada dinámicamente. La orden free(p);

Invalida cualquier referencia futura a la variable *p (a menos que se asigne nuevo espacio de memoria a esa variable). Llamar free(p) hace que quede disponible para reúso el almacenamiento ocupado por *p, si es necesario. La función free espera un parámetro apuntador del tipo char *, para que no tengamos problemas de tipos, debemos hacer free((char *)p);

Consideremos el siguiente ejemplo para ilustrar el uso de free: #include int main (int argc, char * const argv[]) { int *p, *q; ( ( ( ( ( ( ( ( (

1) 2) 3) 4) 5) 6) 7) 8) 9)

p=(int *)malloc(sizeof(int)); *p=5; q=(int *)malloc(sizeof(int)); *q=8; free(p); p=q; q=(int *)malloc(sizeof(int)); *q=6; std::cout<<*p<<" "<<*q<<"\n"; return 0;

}

¿Qué se imprime a la salida del programa? Observemos que si se llama malloc dos veces sucesivas y se asigna su valor a la misma variable como en: p=(int *)malloc(sizeof(int)); *p=3; p=(int *)malloc(sizeof(int)); *p=7;

Se pierde la primera copia de *p, dado que su dirección no se guardó.

Listas ligadas usando memoria dinámica Para hacer las listas ligadas necesitamos un conjunto de nodos, cada uno de los cuales tiene dos campos: uno de información y un apuntador al siguiente nodo de la lista. Además, un apuntador externo señala el primer nodo de la lista. Usamos variables de apuntador para implementar apuntadores de listas. 41

Así que definimos el tipo de un apuntador y un nodo mediante struct node{ int info; struct node *next; }; typedef struct node *nodePtr;

Un nodo de este tipo es igual a los nodos de la implementación con arreglos, excepto que el campo next es un apuntador y no un entero. En lugar de declarar un arreglo, para que represente un conjunto acumulado de nodos, éstos se asignan y liberan según es necesario. Se elimina la necesidad de un conjunto de nodos previamente declarado. Si declaramos nodePtr p;

la ejecución de la orden p=getNode();

debe colocar la dirección de un nodo disponible en p: nodePtr getNode(void){ nodePtr p; p=(nodePtr)malloc(sizeof(struct node)); return(p); }

Para liberar la memoria utilizada usamos freeNode. void freeNode(nodePtr p){ free(p); }

Los procedimientos insAfter y delAfter usan la implementación dinámica de una lista ligada. Supongamos que list es una variable apuntador que señala al primer nodo de una lista (si lo hay) y es igual a NULL en el caso de una lista vacía. void insAfter(nodePtr p, int x){ nodePtr q; if(p==NULL){ std::cout<<"Insercion nula\n"; } else{ q=getNode(); q->info=x; q->next=p->next; p->next=q; } } void delAfter(nodePtr p, int *px){ nodePtr q; if((p==NULL)||(p->next==NULL)){

42

std::cout<<"Borrado prohibido\n"; } else{ q=p->next; *px=q->info; p->next=q->next; freeNode(q); } }

Ejercicios de programación 1. Implemente una pila usando memoria dinámica en listas ligadas. Implemente las operaciones push, pop, empty y stackTop. 2. Implemente una cola usando memoria dinámica en listas ligadas. Implemente las operaciones empty, insert y remove. 3. Desarrolle un programa para buscar un elemento en la lista (de números enteros) y borrar la primera ocurrencia de ese elemento. 4. Desarrolle un programa para buscar un elemento en la lista (de números enteros) y borrar todas las ocurrencias de ese elemento. 5. Las listas doblemente ligadas tienen nodos que están divididos en tres segmentos: 1. Anterior: Un apuntador a un nodo 2. Info: La información de un nodo 3. Siguiente: Un apuntador a un nodo Implemente las operaciones borrarNodo(p), insertarNodoAntes e insertarNodoDespues.

Árboles Los árboles son estructuras de datos útiles en muchas aplicaciones. Hay varias formas de árboles y cada una de ellas es práctica en situaciones especiales, en este capítulo vamos a definir algunas de esas formas y sus aplicaciones.

Concepto general de árbol Desde el punto de vista de estructuras de datos, un árbol es un concepto simple en su definición, sin embargo es muy ingenioso. Un árbol es un grafo con características muy especiales: Definición 9 Un árbol es un grafo

que tiene un único nodo llamado raíz que:

Tiene 0 relaciones, en cuyo caso se llama nodo hoja tiene un número finito de relaciones, en cuyo caso, cada una de esas relaciones es un subárbol Para empezar a estudiar los árboles, nos concentraremos en primer lugar en el caso en que el nodo raíz tenga 0, 1 ó 2 subárboles.

Árboles binarios Definición 10 Un árbol binario es una estructura de datos de tipo árbol en donde cada uno de los nodos del árbol puede tener 0, 1, ó 2 subárboles llamados de acuerdo a su caso como: 43

Si el nodo raíz tiene 0 relaciones se llama hoja. Si el nodo raíz tiene 1 relación a la izquierda, el segundo elemento de la relación es el subárbol izquierdo. Si el nodo raíz tiene 1 relación a la derecha, el segundo elemento de la relación es el subárbol derecho. La figura 25 muestra algunas configuraciones de grafos que sí son árboles binarios, y la figura 26 muestra algnas configuraciones de grafos que no son árboles binarios.

Figura 25: Grafos que son estructuras tipo árbol binario

Figura 26: Grafos que no son árboles binarios Vamos a dar una lista de teérminos que se usan frecuentemente cuando se trabaja con árboles: Si A es la raíz de un árbol y B es la raíz de su subárbol izquierdo (o derecho), se dice que A es el padre de B y se dice que B es el hijo izquierdo (o derecho) de A. Un nodo que no tiene hijos se denomina hoja El nodo a es antecesor del nodo b (y recíprocamente el nodo b es descendiente del nodo a), si a es el padre de b o el padre de algún ancestro de b. Un nodo b es un descendiente izquierdo del nodo a, si b es el hijo izquierdo de a o un descendiente del hijo izquierdo de a. Un descendiente derecho se define de la misma forma. Dos nodos son hermanos si son hijos izquierdo y derecho del mismo padre. Otros términos relacionados con árboles, tienen que ver con su funcionamiento y topología: Si cada nodo que NO es una hoja tiene un subárbol izquierdo y un subárbol derecho, entonces se trata de un árbol binario completo. 44

El nivel de un nodo es el número de aristas que se deben recorrer para llegar desde ese nodo al nodo raíz. De manera que el nivel del nodo raíz es 0, y el nivel de cualquier otro nodo es el nivel del padre más uno. La profundidad de un nodo es el máximo nivel de cualquier hoja en el árbol.

Si un árbol binario tiene nodos en el nivel , el máximo número de nodos en el nivel . Dado que un árbol binario sólo tiene un nodo en el nivel 0, puede contener un máximo de en el nivel . Un árbol binario completo de profundidad es el árbol que contiene exactamente

es nodos nodos

en cada nivel entre 0 y . La cantidad total de nodos en un árbol binario completo de profundidad , es igual a la suma de nodos en cada nivel entre 0 y , por tanto:

Usando inducción matemática se puede demostrar que todas las hojas en este árbol están en el nivel que no son hojas.

, el árbol contiene

Si conocemos el número total de nodos

. Dado que hojas y, por tanto,

nodos

en un árbol binario completo, podemos

calcular su profundidad , a partir de la expresión . Así sabemos que la profundidad es igual a 1 menos que el número de veces que 2 debe ser multiplicado por sí mismo para llegar a . Es decir, que en un árbol binario completo,

Definición 11 Un árbol binario es un árbol binario casi completo si: 1. Cualquier nodo a un nivel menor que tiene 2 hijos 2. Para cualquier nodo en el árbol con un descendiente derecho en el nivel izquierdo y cada descendiente izquierdo de : o es una hoja en el nivel ó o tiene dos hijos

debe tener un hijo

45

Figura 27: Comparación de un árbol binario y un árbol binario casi completo. El árbol mostrado en (A) no cumple la regla 2 de los árboles binarios casi completos. Los nodos en un árbol binario (completo, casi completo o incompleto) se pueden enumerar del siguiente modo. Al nodo raíz le corresponde el número 1, al hijo izquierdo le corresponde el doble del número asignado al padre y al hijo derecho le corresponde el doble más 1 del número asignado al padre. Operaciones con árboles binarios

Con los árboles binarios es posible definir algunas operaciones primitivas, estas operaciones son en el sentido de saber la información de un nodo y sirven para desplazarse en el árbol, hacia arriba o hacia abajo. info(p)

que devuelve el contenido del nodo apuntado por p. left(p)

devuelve un apuntador al hijo izquierdo del nodo apuntado por p, o bien, devuelve NULL si el nodo apuntado por p es una hoja. right(p)

devuelve un apuntador al hijo derecho del nodo apuntado por p, o bien, devuelve NULL si el nodo apuntado por p es una hoja. father(p)

devuelve un apuntador al padre del nodo apuntado por p, o bien, devuelve NULL si el nodo apuntado por p es la raíz. brother(p)

devuelve un apuntador al hermano del nodo apuntado por p, o bien, devuelve NULL si el nodo apuntado por p no tiene hermano.

Estas otras operaciones son lógicas, tienen que ver con la identidad de cada nodo: isLeft(p)

devuelve el valor true si el nodo actual es el hijo izquierdo del nodo apuntado por p, y false en caso contrario. isRight(p)

devuelve el valor true si el nodo actual es el hijo derecho del nodo apuntado por p, y false en caso contrario. isBrother(p)

devuelve el valor true si el nodo actual es el hermano del nodo apuntado por p, y false en caso contrario. 46

Como ejemplo, un algoritmo para el procedimiento isLeft es como sigue: q=father(p); if(q==NULL) return(false) /* porque p apunta a la raiz */ if (left(q)==p) return(true); return(false);

En la construcción de un árbol binario son útiles las operaciones makeTree, setLeft y setRight. La operación makeTree(x) crea un nuevo árbol binario que consta de un único nodo con un campo de información x y devuelve un apuntador a ese nodos. La operación setLeft(p,x) acepta un apuntador p a un nodo de árbol binario sin hijo izquierdo. Crea un nuevo hijo izquierdo de node(p) con el campo de información x. La operación setRight(p,x) es similar, excepto que crea un hijo derecho. Aplicaciones de árboles binarios

Un árbol binario es una estructura de datos útil cuando se trata de hacer modelos de procesos en donde se requiere tomar decisiones en uno de dos sentidos en cada parte del proceso. Por ejemplo, supongamos que tenemos un arreglo en donde queremos encontrar todos los duplicados. Esta situación es bastante útil en el manejo de las bases de datos, para evitar un problema que se llama redundancia. Una manera de encontrar los elementos duplicados en un arreglo es recorrer todo el arreglo y comparar con cada uno de los elementos del arreglo. Esto implica que si el arreglo tiene elementos, se deben hacer comparaciones, claro, no es mucho problema si es un número pequeño, pero el problema se va complicando más a medida que aumenta. Si usamos un árbol binario, el número de comparaciones se reduce bastante, veamos cómo. El primer número del arreglo se coloca en la raíz del árbol (como en este ejemplo siempre vamos a trabajar con árboles binarios, simplemente diremos árbol, para referirnos a un árbol binario) con sus subárboles izquierdo y derecho vacíos. Luego, cada elemento del arreglo se compara son la información del nodo raíz y se crean los nuevos hijos con el siguiente criterio: Si el elemento del arreglo es igual que la información del nodo raíz, entonces notificar duplicidad. Si el elemento del arreglo es menor que la información del nodo raíz, entonces se crea un hijo izquierdo. Si el elemento del arreglo es mayor que la información del nodo raíz, entonces se crea un hijo derecho.

Una vez que ya está creado el árbol, se pueden buscar los elementos repetidos. Si x el elemento buscado, se debe recorrer el árbol del siguiente modo: Sea k la información del nodo actual p. Si en caso contrario, en caso de que cambiar el nodo actual a left(p).

entonces cambiar el nodo actual a right(p),

informar una ocurrencia duplicada y en caso de que

El siguiente algoritmo leer numero buscado >> n tree=makeTree(n) while(hay numeros en el arreglo){ leeSiguienteNumero >> k p=q=tree;

47

while(k!=info(p)&&q!=NULL){ p=q if(k
Figura 28: Árbol binario para encontrar números duplicados

Para saber el contenido de todos los nodos en un árbol es necesario recorrer el árbol. Esto es debido a que solo tenemos conocimiento del contenido de la dirección de un nodo a la vez. Al recorrer el árbol es necesario tener la dirección de cada nodo, no necesariamente todos al mismo tiempo, de hecho normalmente se tiene la dirección de uno o dos nodos a la vez; de manera que cuando se tiene la dirección de un nodo, se dice que se visita ese nodo. Aunque hay un orden preestablecido (la enumeración de los nodos) no siempre es bueno recorrer el árbol en ese orden, porque el manejo de los apuntadores se vuelve más complejo. En su lugar se han adoptado tres criterios principales para recorrer un árbol binario, sin que de omita cualquier otro criterio diferente. Los tres criterios principales para recorrer un árbol binario y visitar todos sus nodos son, recorrer el árbol en: preorden: Se ejecutan las operaciones: 1. Visitar la raíz 2. recorrer el subárbol izquierdo en preorden 3. recorrer el subárbol derecho en preorden entreorden: Se ejecutan las operaciones: 1. recorrer el subárbol izquierdo en entreorden 2. Visitar la raíz 48

3. recorrer el subárbol derecho en entreorden postorden: Se ejecutan las operaciones: 1. recorrer el subárbol izquierdo en postorden 2. recorrer el subárbol derecho en postorden 3. Visitar la raíz

Al considerar el árbol binario que se muestra en la figura 28 usando cada uno de los tres criterios para recorrer el árbol se tienen las siguientes secuencias de nodos: En preorden: En entreorden: En postorden: Esto nos lleva a pensar en otra aplicación, el ordenamiento de los elementos de un arreglo. Para ordenar los elementos de un arreglo en sentido ascendente, se debe construir un árbol similar al árbol binario de búsqueda, pero sin omitir las coincidencias. El arreglo usado para crear el árbol binario de búsqueda fue <14,15,4,9,7,18,3,5,16,4,20,17,9,14,5>

El árbol de ordenamiento es el que se muestra en la figura 29

Figura 29: Árbol binario para ordenar una secuencia de números

Para ordenar los elementos de este arreglo basta recorrer el árbol en forma de entreorden. ¿Cuál sería el algoritmo para ordenarlo de manera descendente?

Representación en C/C++ de los árboles binarios Vamos a estudiar estas representaciones por partes, primero los nodos y el árbol; después las operaciones para el manejo del árbol. 49

Representación de los nodos

Los nodos de los árboles binarios son estructuras en C/C++ que están compuestas por tres partes: Un apuntador al subárbol izquierdo, left Un apuntador al subárbol derecho, right Una parte de información, que puede ser una estructura en sí misma, info. Adicionalmente es muy útil poner un apuntador al padre del nodo. father.

Usando una implementación de arreglos tenemos: #define numNodes 500 struct nodeType{ int info; int left; int right; int father; }; struct nodeType node[numNodes];

y usando una representación con memoria dinámica, los nodos de un árbol se puede representar tambien con una estructura en C/C++ : struct nodeType{ int info; struct nodeType *left; struct nodeType *right; struct nodeType *father; }; struct nodeType *nodePtr;

La operaciones info(p), left(p), right(p) y father(p) se implementarían mediante referencias a p->info, p->left, p->right y p->father respectivamente. Las rutinas getnode y freenode simplemente asignan y liberan nodos usando las rutinas malloc y free. nodePtr makeTree(int x){ nodePtr p; p = getNode(); p->info = x; p->left = NULL; p->right = NULL; return p; }

La rutina setLeft(p,x) establece un nodo con contenido x como el hijo izquierdo de node(p). void setLeft(nodePtr p, int x){ if(p == NULL) std::cout<<"Insercion nula\n"; else if(p->left != NULL) std::cout<<"Insercion no valida\n"; else p->left=maketree(x); }

La rutina para setRight(p,x) es similar a la rutina anterior. 50

Cuando se establece la diferencia entre los nodos de hojas y los no-hojas, los nodos que no son hojas se llaman nodos internos y los nodos que sí son hojas se llaman nodos externos. Recorridos de árbol binario en C/C++

Aquí usaremos recursividad para hacer estas rutidas de los recorridos de árboles binarios. Las rutinas se llaman preTr, inTr y postTr, que imprimen el contenido de los nodos de un árbol binario en orden previo, en orden y en orden posterior, respectivamente. El recorrido en pre orden se logra con esta rutina: void preTr(nodePtr tree){ if (tree != NULL){ std::cout<info; preTr(tree->left); preTr(tree->right); } }

El recorrido en entre-orden se logra con esta rutina: void inTr(nodePtr tree){ if (tree != NULL){ inTr(tree->left); std::cout<info; inTr(tree->right); } }

y el recorrido en post-orden se logra con esta rutina: void postTr(nodePtr tree){ if (tree != NULL){ postTr(tree->left); postTr(tree->right); std::cout<info; } }

Árboles Hasta ahora hemos visto los árboles binarios que son aquellos árboles que sus nodos solamente pueden tener un máximo de dos hijos. Cuando ocurre que los nodos tienen cualquier número finito de hijos, son árboles (en general). De manera que Definición 12 Un árbol es un conjunto finito no vacío de elementos en el cual un elemento se denomina la raíz y los restantes se dividen en subconjuntos disjuntos, cada uno de los cuales es por sí mismo un árbol. Cada elemento en un árbol se denomina un nodo del árbol Un nodo sin subárboles es una hoja. Usamos los términos padre, hijo, hermano, antecesor, descendiente, nivel y profundidad del mismo modo que en los árboles binarios. El grado de un nodo es en número máximo de hijos que algún nodo tiene. 51

Un árbol ordenado de define como un árbol en el que los subárboles de cada nodo forman un conjunto ordenado. En un árbol ordenado, podemos hablar del primero, segundo o último hijo de un nodo en particular. El primer hijo de un nodo en un árbol ordenado se denomina con frecuencia el hijo más viejo de este nodo y el último se denomina el hijo más joven. Véase la figura 30. Un bosque es un conjunto ordenado de árboles ordenados.

Figura 30: El árbol de la izquierda es ordenado y el árbol de la derecha es un árbol no ordenado. Representación dinámica en C de los árboles

Al igual que en los árboles binarios, los nodos en un árbol tienen una parte de información, un apuntador al padre y uno o más apuntadores a los hijos. De manera que una solución es crear una estructura que incluya una lista dinámica de apuntadores, como lo muestra la figura 31.

Figura 31: Representación con listas de los nodos de un árbol struct treeNode{ int info; struct treeNode *father; struct treeNode *son; struct treeNode *next; }; typedef struct treeNode *nodePtr;

Si todos los recorridos se realizan de un nodo a sus hijos se omite el campo father. Incluso si es necesario acceder al padre de un nodo, el campo father se omite colocando un apuntador al padre en el campo next del hijo más joven, en lugar de dejarlo en null. Se podría usar un campo lógico adicional para indicar si el campo next apunta al siguiente hijo ``real'' o al padre. 52

Si consideramos que son corresponde al apuntador left de un nodo de árbol binario y que next corresponde a su apuntador right, este método representa en realidad un árbol ordenado general mediante un árbol binario. Recorridos de árbol

Los métodos de recorrido para árboles binarios inducen métodos para recorrer los árboles en general. Si un árbol se representa como un conjunto de nodos de variables dinámicas con apuntadores son y next, una rutina en C/C++ para imprimir el contenido de sus nodos se escribiría como: void inTr(nodePtr tree){ if (tree != NULL){ inTr(tree->left); std::cout<info; inTr(tree->right); } }

Las rutinas para recorrer el árbol en los demás ordenes son similares. Estos recorridos también se definen directamente así: Orden previo: similar al caso binario. 1. Visitar la raíz 2. Recorrer en orden previo los subárboles de izquierda a derecha

Las demás rutinas son similares. Un bosque puede ser representado medianto un árbol binario. Para hacer esta representación, la raíz de cada árbol se coloca en una lista de apuntadores; luego para cada nodo en la lista (la raíz de cada árbol) se procede del siguiente modo: 1. Se crea una lista de subárboles izquierdos con los apuntadores a cada uno de los árboles en el bosque. 2. si un nodo tiene más de un hijo, entonces se crea un subárbol izquierdo y se forma una lista de subárboles izquierdos con todos los hijos de ese nodo.

Figura 32: Arriba: Un bosque de árboles. Abajo: El árbol binario que corresponde a ese bosque. 53

Para recorrer los nodos de un bosque, es preferible convertir todo el bosque en un árbol binario correspondiente, como se ilustra en la figura 32. Cuando ya se tiene el árbol binario que corresponde a ese bosque, entonces se aplican las rutinas ya conocidas. Si el bosque es un bosque ordenado, es decir, que todos los árboles del bosque son árboles ordenados; entonces un recorrido en entreorden dará como resultado una secuencia de nodos ordenada en sentido ascendente.

Ejercicios de programación 1. Escriba un programa que acepte un apuntador a un nodo y devuelva un valor verdadero si este nodo es la raíz de un árbol binario válido y falso en caso contrario. 2. Escriba un programa que acepte un apuntador a un árbol binario y un apuntador a un nodo del árbol, y devuelva el nivel del nodo en el árbol. 3. Escriba un programa para ejecutar el experimento siguiente: genere 100 números aleatorios. Conforme se genera cada número, insértelo en un árbol de búsqueda binaria inicialmente vacío. Después de insertar los 100 números, imprima el nivel de la hoja que tiene el nivel más grande y el nivel de la hoja que tiene el nivel más chico. Repita este proceso 50 veces. Imprima una tabla que indique cuántas veces de las 50 ejecuciones produjeron una diferencia entre el nivel de hoja máximo y mínimo de 0,1,2,3, y así sucesivamente. 4. Implemente los recorridos de los árboles binarios. 5. Si un bosque se representa mediante un árbol binario, muestre que el número de vínculos derechos nulos es 1 mayor que el número de no hojas del bosque.

Grafos En esta parte del curso vamos a retomar la idea de los grafos. Hasta ahora hemos visto las listas y los árboles como casos especiales de los grafos. Resumiendo, las listas son grafos en donde cada nodo tiene una arista que sale y una arista que llega, excepto un par de nodos, uno de esos nodos es el inicio de la lista que tiene no tiene arista que entra; y el otro nodo es el final de la lista que no tiene arista que sale; En los árboles, los nodos tienen una arista que llega (la del padre) y una o más aristas que salen (los hijos). Como veremos más adelante con mucho mayor detalle, los nodos en los grafos no tienen límite de aristas que salen o aristas que lleguen, por eso tanto las listas como los árboles son casos particulares de los grafos.

Recordatorio de las definiciones Un grafo consiste de una tupla , en donde es un conjunto de elementos llamados nodos; y es una relación, representada por un conjunto de pares ordenados de nodos. El conjunto de nodos debe de ser un conjunto no-vacío, esto significa que para que exista un grafo es necesario al menos un nodo. El conjunto de aristas puede ser el conjunto vacó. En la figura 33 se muestra un grafo y sus conjuntos de nodos y de aristas.

54

Figura 33: Grafo dirigido o digrafo Si las aristas de un grafo no están dirigidas se omiten las flechas, y se dice entonces que es un grafo (no un grafo dirigido). Cuando en las aristas no hay flechas, se entiende que hay una relación reflexiva, es decir, si para un grafo ; y se tiene que entonces no se dibujan las flechas. Porque la flecha indica el sentido de la relación. Si

,

es un grafo, los siguientes términos son frecuentemente usados al trabajar con

:

Nodo incidente: Si

entonces tanto el nodo

como el nodo

son nodos incidentes.

Grado de incidencia: Se define para cada nodo, y es su máximo numero de incidencias. También se conoce con el nombre de ``valencia''. Grado interno: También se define para cada nodo y es el número de aristas que llegan a ese nodo. Otro nombre para este término es ``valencia de entrada''. Grado externo: Para cada nodo es el número de aristas que salen del nodo. Se conoce también con el nombre de ``valencia de salida''. Adyacencia: Si

, el nodo

es adyacente al nodo

, entonces el nodo nodo

si

no es adyacente al nodo

. Note que si

, pero

, pero el nodo

si es adyacente al

.

Sucesor: Si el nodo

es adyacente al nodo

, entonces el nodo

es el sucesor del nodo

. 55

Antecesor: Si el nodo es adyacente al nodo , entonces el nodo es el antecesor del nodo . Es posible asociar una etiqueta a cada arista, como se muestra en la figura 34. La etiqueta asociada con cada arista se denomina peso.

Figura 34: Grafo dirigido con pesos Los grafos ponderados son relaciones definidas por un conjunto de elementos, en donde cada elemento es un trío ordenado

donde

y

, para algún conjunto

de pesos.

Con los grafos y grafos ponderados (los que tienen pesos) se pueden tener algunas operaciones básicas: Con grafos: join(a,b): Agrega una relación del nodo a al nodo b. Si la relación no existe, entonces crea una relación. removeArc(a,b): Quita un arco del nodo a al nodo b Con grafos ponderados: joinWt(a,b,w): Agrega una relación del nodo a al nodo b y le asocia el peso w. Si la relación no existe, entonces de crea la relación y le asocia el peso indicado. removeArcWt(a,b): Quita un arco del nodo a al nodo b con peso w. La operación isAdjacent(a,b) devuelve un valor TRUE si el nodo a es adyacente al nodo b, y devuelve un valor FALSE en caso contrario.

Una trayectoria de longitud nodos las

del nodo a al nodo b se define como una secuencia de

tal que

,

y isAdjacent(n

,n

)

para todas

.

56

Una trayectoria de longitud 1 un nodo a sí mismo es un autociclo. Si existe una trayectoria de longitud mayor que 1 de un nodo a sí mismo, entonces es un ciclo. Si el grafo es acíclico y dirigido, entonces se llama dag (directed acyclic graph).

Aplicación ejemplo Supongamos el grafo ponderado de la figura 35, este grafo tiene como conjunto de nodos

y una relación

Figura: Grafo Se desea saber si existe un camino entre un par de nodos dado.

Bibliografía LAT97 Yedidyah Langsam, Moshe J. Augenstein, and Aaron M. Tenenbaum. Estructura de datos con C y C++. Prentice-Hall, Inc., 2a edition, 1997. MP97 William H. Murray and Chris H. Pappas. Manual de Borland C++, volume ISBN: 0-07-882216-5. Osborne McGraw-Hill, 1997. TA83 Aaron M. Tenenbaum and Moshe J. Augenstein. Estructura de datos en Pascal. Phh-PrenticeHall, 1983.

57