Libro - Estructura De Datos.pdf

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

PRÓLOGO La presente obra se diseño principalmente como un texto de referencia para los estudiantes de Ingeniería de Sistemas e Informática de la Universidad Privada de Oruro, que necesitan de una guía práctica, proporcionándole información rápida y objetiva sobre la metodología a seguir en la codificación de programas en C++ y la Estructura de Datos.

El lenguaje seleccionado en el presente texto es C++ con el editor llamado

“Code::Blocks 10.05”, un

lenguaje básico y nada complejo en su comprensión y

utilización.

La Obra presente diversos problemas los mismos que han sido seleccionados no tanto por su utilidad práctica en el campo de la solución de problemas, sino por la forma y complejidad que estos despliegan en el proceso de codificación.

El texto cuenta con problemas que van desde lo más básico hasta los más complejos para que el programador pueda asimilar tanto el diseño de los problemas codificados en forma gradual y sistemática

El texto también cuenta con un CD interactivo en el cual se encuentran los problemas codificados y el instalador del Editor “Code::Blocks 10.05”. Para que el estudiante pueda verificar y comprar que los problemas son exactamente iguales a los que aparecen en el texto.

10

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

11

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

1. DECLARACION DE UNA VARIABLE Una característica de C++, es la necesidad de declarar las variables que se usarán en un programa. Esto resulta chocante para los que se aproximan al C++ desde otros lenguajes de programación en los que las variables de crean automáticamente la primera vez que se usan. Se trata, es cierto, de una característica de bajo nivel, más cercana al ensamblador que a lenguajes de alto nivel, pero en realidad una característica muy importante y útil de C++, ya que ayuda a conseguir códigos más compactos y eficaces, y contribuye a facilitar la depuración y la detección y corrección de errores y a mantener un estilo de programación elegante. Uno de los errores más comunes en lenguajes en los que las variables se crean de forma automática se produce al cometer errores ortográficos. Por ejemplo, en un programa usamos una variable llamada “prueba”, y en un punto determinado le asignamos un nuevo valor, pero nos equivocamos y escribimos “prubea”. El compilador o intérprete no detecta el error, simplemente crea una nueva variable, y continúa como si todo estuviese bien. En C++ esto no puede pasar, ya que antes de usar cualquier variable es necesario declararla, y si por error usamos una variable que no ha sido declarada, se producirá un error de compilación. 1.1 ¿QUE ES UNA VARIABLE? Es un nombre que representa el valor de un dato. Es una zona o posición de memoria en la computadora donde se almacena información. Un objeto de datos que el programador define y nombra explícitamente en un programa. Una variable simple es un objeto elemental de datos con nombre. El valor o valores de una variable es modificable por operaciones de asignación; es decir, el enlace de objeto de datos a valor puede cambiar durante su tiempo de vida. Las operaciones que se pueden realizar con dos o más valores exigen que éstas sean del mismo tipo de datos. No se puede sumar una variable carácter a otra numérica y/o viceversa. 1.2 TIPOS DE VARIABLES EN C++ Todos los programas gestionan algunos tipos de información que normalmente se pueden representar utilizando uno de los ocho (8) tipos de datos básicos de C y C++: texto o char, valores enteros o int, valores de coma flotante o float, valores en coma flotante de doble precisión o double (long double), enumerados o enum, sin valor o void, punteros y booleanos. Int: El tipo de dato int, tiene un tamaño de 32 bits y un rango entre -2.147.483.648 y 2.147.483.647. Este tipo de dato, es usado para números enteros (sin cifras decimales). A continuación alguna de sus combinaciones con los modificadores:

-

short int:

Tiene un tamaño de 16 bits y un rango entre -32.768 y 32.767.

-

unsigned short int:

Tiene un tamaño de 16 bits y un rango entre 0 y 65.535.

-

unsigned int:

Tiene un tamaño de 32 bits y un rango entre 0 y 4.294.967.295.

-

long long int:

Tiene un tamaño de 64 bits y un rango entre -9.223.372.775.808 y 9.223.375.775.807.

-

unsigned long long int:

Tiene un tamaño de 64 bits y un rango entre 0 y 18.446.744.073.709.551.615.

12

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

float: El tipo de dato float, tiene un tamaño de 32 bits, es usado comúnmente en números con 6 o menos cifras decimales. Tiene un rango entre 1.17549 e-38 hasta 3.40282 e+38. double: El tipo de dato double, tiene un tamaño de 64 bits, es usado para números de menos de 15 cifras decimales. Tiene un rango entre 2.22507 e-308 hasta 1.79769 e+308. long double: Tiene un tamaño de 96 bits y una precisión de 18 cifras decimales. Tiene un rango entre 3.3621 e-4932 hasta 1.18973 e+4932. bool: El tipo de dato bool, tiene un tamaño de 8 bits y un rango entre 0 y 1, en pocas palabras es cero o es uno (falso o verdadero). Este tipo de dato, es comúnmente usado en condicionales o variables al que se le puede asignar las constantes true (verdadero) y false (falso).

char: Esta constituido por caracteres simples, como (a-z / A-Z / 0-9) y cadenas, como “Esto es una prueba” (normalmente, de 8 bits o un byte por carácter, con un rango de 0 a 255). Las variables del tipo char, son digamos las variables problema del lenguaje C y C++, puesto que tienen una gran cantidad de restricciones y complicaciones, bastante molestas. Las variables de tipo char, en C y C++ son consideradas vectores y como quizá sabrás a los vectores se les debe declarar un tamaño máximo, entre corchetes “[ ]” lo cual restringe un poco al momento de no saber que tamaño podría llegar a tener una cadena de caracteres, y aunque hay formas de evadir esto, es bastante complicado, desde mi punto de vista personal recomiendo las variables de tipo string para las cadenas de caracteres, estas están incluidas en la librería #include <string.h> y son bastante fáciles de usar y muy flexibles a diferencia de los char. Muy bien, de igual forma pondré como se debe declarar un char y más abajo mencionare algunas otras molestias que este tipo de dato genera, pero explicare como se arreglan. Muy bien, la sintaxis es la siguiente: char nombre_char [tamaño_max]; También es válido y solo es válido de esta forma la asignación por medio del signo “=” para un char y es así: char char_nombre [tamaño_max] = “cadena”; Muy bien, como veras aquí lo único que hay extraño es lo del [tamaño_max], pues bien, ahí se debe poner un numero entero que no cambia es decir constante que nos indica el tamaño máximo que tendrá nuestra cadena de caracteres, si nos pasamos de ese número, tendremos problemas, así que recomiendo poner números grandes si no se sabe el tamaño que podría tener, pero bueno, esto nos podría desperdiciar memoria y recursos o todo lo contrario, nos podrían quedar faltando.

13

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

void: El tipo void, se utiliza para especificar valores que ocupan 0 bits y no tienen valor (este tipo también se puede utilizar para la creación de punteros genéricos). puntero: El tipo de dato puntero, no contiene información en el mismo sentido que el resto de los tipos de datos; en su lugar, cada puntero contiene la dirección de la posición de memoria que almacena el dato actual. 1.3 ¿CÓMO SE DECLARA UNA VARIABLE EN C++? El sistema es siempre el mismo, primero se especifica el tipo y a continuación una lista de variables y finalmente un punto y coma. La declaración de variables es uno de los tipos de sentencia de C++. La prueba más clara de esto es que la declaración terminará con un ";". Sintaxis: <lista de variables>;

También es posible inicializar las variables dentro de la misma declaración. Por ejemplo: int a = 1234; bool seguir = true, encontrado;

Declararía las variables “a, seguir y encontrado”; y además iniciaría los valores de “a y seguir” con los valores “1234 y true”, respectivamente. 1.4 REGLAS PARA LA DECLARACION DE VARIABLES Bien pues, ya sabemos que en la programación tenemos que estar muy atentos a la sintaxis (Estructura de una Palabra), pues es importantísimo, ya que si no está bien escrito un comando, no va a funcionar esa línea en el código del programa y peor aún, si esa línea está ligada a las líneas de más adelante pues no funcionará ni ésta ni las de más adelante (Como una Cadena). Entonces les diré algunas reglas para la declaración de variables, cuando veamos un lenguaje de programación especifico colocaré la sintaxis de sus comandos ya que las sintaxis cambia (La lógica no, ósea cambian las palabras pero la forma de realizar el ejercicio sigue siendo la misma), porque cada lenguaje tiene su dialecto. Comencemos:

14

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

Regla 1: Tener el mismo nombre que una “palabra reservada” del lenguaje. Explicación: Los lenguajes de programación tienen “palabras reservadas“, ósea que esas palabras solo pueden ser usadas por el programa, por eso llevan el nombre de “reservadas“, pues si supongamos el caso de que un lenguaje de programación “X” tiene sus palabras reservadas entre las cuales está: “ingresar“, entonces eso quiere decir que el usuario NO debe declarar una variable con el nombre “ingresar“, porque va a tener conflictos más adelante.

Regla 2: Sólo pueden ser letras, dígitos y el guión bajo ó subguión. Además debe tener no más de 40 caracteres. Explicación: Pues en los lenguajes de programación hay sintaxis que deben cumplirse al pie de la letra, entonces dice que las variables solo pueden llevar letras, números y el subguión.

Ejemplo: La siguiente variable está bien declarada: programando19 La siguiente variable está mal declarada:

%&programando-19

Vemos que insertó caracteres especiales, además de que uso el guión normal (no el subguión), por lo tanto puede que el programa entienda que es una resta, entonces está mal declarado por sintaxis.

Regla 3: Deben comenzar por un carácter (letra). Explicación: Por sintaxis como ya hemos visto, deben cumplir con estas reglas, entonces no se puede comenzar con un número, ya que se debe comenzar por una letra como dice la regla. Ejemplo: La siguiente variable está bien declarada: pasoApaso La siguiente variable está mal declarada:

89pasos

Regla 4: Deben iniciar con un carácter (no numero) como vimos en la Regla 3, y también puede comenzar con un guión bajo (_).

15

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

Ejemplo: La siguiente variable está bien declarada: _descuento La siguiente variable está mal declarada:

-descuento

La siguiente variable está mal declarada:

descuento-

Regla 5: No se les pueden asignar espacios en blanco. Explicación: Las variables no pueden llevar espacios en blanco, solo pueden ser separadas por un signo dedicado a ser usado como un espacio, el cual es el subguión (_), entonces en una variable cuando vean un subguión, prácticamente están separando algo (para que no parezca una ensalada). Ejemplo: La siguiente variable está bien declarada: eddy_19 La siguiente variable está mal declarada:

eddy 19

Regla 6: No pueden llevar acento (tilde). Ejemplo: La siguiente variable está bien declarada: numero La siguiente variable está mal declarada:

número

Esas son las “Reglas Base“, para la buena declaración de variables. 1.5 PALABRAS CLAVE DEL C++ En C++, como en cualquier otro lenguaje, existen una serie de palabras clave (keywords) que el usuario no puede utilizar como identificadores (nombres de variables y/o de funciones). Estas palabras sirven para indicar al computador que realice una tarea muy determinada (desde evaluar una comparación, hasta definir el tipo de una variable) y tienen un especial significado para el compilador. El C++ es un lenguaje muy conciso, con muchas menos palabras clave que otros lenguajes. A continuación se presenta la lista de las 32 palabras clave del ANSI C, para las que más adelante se dará detalle de su significado (algunos compiladores añaden otras palabras clave, propias de cada uno de ellos. Es importante evitarlas como identificadores):

16

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

auto

double

int

struct

break

else

long

switch

case

e num

register

typedef

char

extern

return

union

const

float

short

unsigned

continue

for

signed

void

default

goto

sizeof

volatile

do

if

static

while

2. ENTRADA Y SALIDA DE DATOS Cuando nos referimos a entrada/salida estándar (E/S estándar) queremos decir que los datos o bien se están leyendo del teclado, ó bien se están escribiendo en el monitor de video. Como se utilizan muy frecuentemente se consideran como los dispositivos de E/S por default y no necesitan ser nombrados en las instrucciones de E/S. En el lenguaje C++ tenemos varias alternativas para ingresar y/o mostrar datos, dependiendo de la librería que vamos a utilizar para desarrollar el programa, entre estas están: y . < IOSTREAM> Las operaciones de entrada y salida no forman parte del conjunto de sentencias de C++, sino que pertenecen al conjunto de funciones y clases de la biblioteca estándar de C++. Ellas se incluyen en los archivos de cabecera por lo que siempre que queramos utilizarlas deberemos introducir la línea de código: #include . Esta biblioteca es una implementación orientada a objetos y está basada en el concepto de flujos. A nivel abstracto un flujo es un medio de describir la secuencia de datos de una fuente a un destino o sumidero. Así, por ejemplo, cuando se introducen caracteres desde el teclado, se puede pensar en caracteres que fluyen o se trasladan desde el teclado a las estructuras de datos del programa. Los objetos de flujo que vienen predefinidos serán: cin, que toma caracteres de la entrada estándar (teclado); cout, pone caracteres en la salida estándar (pantalla); cerr y clog, ponen mensajes de error en la salida estándar.

17

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

Estos objetos se utilizan mediante los operadores << y >>. El operador << se denomina operador de inserción; y apunta al objeto donde tiene que enviar la información. Por lo tanto la sintaxis de cout será: cout<
No olvidemos que las cadenas de texto son variables y se ponen entre " " (comillas dobles). Por su parte >> se denomina operador de extracción, lee información del flujo cin (a la izquierda del operador) y las almacena en las variables indicadas a la derecha). La sintaxis sería la siguiente: cin>>variable1>>variable2>>….....>>variableN;

Un ejemplo de código utilizando ambos objetos podría ser el siguiente: #include using namespace std; int main () { int num; cout<<"Introduce un número: "; cin>>num; cout<<"Usted introdujo: "<
Que mostraría por pantalla la frase "Introduce un número" y posteriormente almacenaría el valor introducido por teclado en la variable num, para luego mostrar por pantalla la frase “Usted introdujo: “, seguidamente del dato almacenado en la variable num. 3. OPERADORES, EXPRESIONES Y SENTENCIAS. 3.1 OPERADORES.

Un operador es un carácter o grupo de caracteres que actúa sobre una, dos o más variables para realizar una determinada operación con un determinado resultado. Ejemplos típicos de operadores son la suma (+), la diferencia (-), el producto (*), etc. Los operadores pueden ser unarios, binarios y ternarios, según actúen sobre uno, dos o tres operandos, respectivamente. En C++ existen muchos operadores de diversos tipos (éste es uno de los puntos fuertes del lenguaje), que se verán a continuación. 3.1.1 OPERADORES ARITMÉTICOS Los operadores aritméticos son los más sencillos de entender y de utilizar. Todos ellos son operadores binarios. En C++ se utilizan los cinco operadores siguientes:

18

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

    

Suma: + Resta: Multiplicación: * División: / Modulo: %

Todos estos operadores se pueden aplicar a constantes, variables y expresiones. El resultado es el que se obtiene de aplicar la operación correspondiente entre los dos operandos. El único operador que requiere una explicación adicional es el operador modulo %. En realidad su nombre completo es resto de la división entera. Este operador se aplica solamente a constantes, variables o expresiones de tipo int. Aclarado esto, su significado es evidente: 23 % 4 es 3, puesto que el resto de dividir 23 por 4 es 3. Si a % b es cero, a es múltiplo de b. Como se verá más adelante, una expresión es un conjunto de variables y constantes y también de otras expresiones más sencillas relacionadas mediante distintos operadores. Un ejemplo de expresión en la que intervienen operadores aritméticos es el siguiente polinomio de grado 2 en la variable x: 5.0 + 3.0*x - x*x/2.0 Las expresiones pueden contener paréntesis (...) que agrupan a algunos de sus términos. Puede haber paréntesis contenidos dentro de otros paréntesis. El significado de los paréntesis coincide con el habitual en las expresiones matemáticas, con algunas características importantes que se verán más adelante. En ocasiones, la introducción de espacios en blanco mejora la legibilidad de las expresiones. 3.1.2 OPERADORES DE ASIGNACIÓN Los operadores de asignación atribuyen a una variable es decir, depositan en la zona de memoria correspondiente a dicha variable– el resultado de una expresión o el valor de otra variable (en realidad, una variable es un caso particular de una expresión). El operador de asignación más utilizado es el operador de igualdad (=), que no debe ser confundido con la igualdad matemática. Su forma general es: nombre_de_variable = expresion;

cuyo funcionamiento es como sigue: se evalúa expresión y el resultado se deposita en nombre_de_variable, sustituyendo cualquier otro valor que hubiera en esa posición de memoria anteriormente. Una posible utilización de este operador es como sigue: variable = variable + 1;

19

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

Desde el punto de vista matemático este ejemplo no tiene sentido (¡Equivale a 0 = 1!), pero sí lo tiene considerando que en realidad el operador de asignación (=) representa una sustitución; en efecto, se toma el valor de variable contenido en la memoria, se le suma una unidad y el valor resultante vuelve a depositarse en memoria en la zona correspondiente al identificador variable, sustituyendo al valor que había anteriormente. El resultado ha sido incrementar el valor de variable en una unidad. Así pues, una variable puede aparecer a la izquierda y a la derecha del operador (=). Sin embargo, a la izquierda del operador de asignación (=) no puede haber nunca una expresión: Tiene que ser necesariamente el nombre de una variable. Es incorrecto, por tanto, escribir algo así como: a + b = c; // incorrecto Existen otros cuatro operadores de asignación (+=, -=, *= y /=) formados por los cuatro operadores aritméticos seguidos por el carácter de igualdad. Estos operadores simplifican algunas operaciones recurrentes sobre una misma variable. Su forma general es: variable op= expresion; Donde “op” representa cualquiera de los operadores (+ - * /). La expresión anterior es equivalente a: variable = variable op expresion; A continuación se presentan algunos ejemplos con estos operadores de asignación: distancia += 1; rango /= 2.0 x *= 3.0 * y - 1.0

equivale a: equivale a: equivale a:

distancia = distancia + 1; rango = rango /2.0 x = x * (3.0 * y - 1.0)

3.1.3 OPERADORES INCREMENTALES Los operadores incrementales (++) y (--) son operadores unarios que incrementan o disminuyen en una unidad el valor de la variable a la que afectan. Estos operadores pueden ir inmediatamente delante o detrás de la variable. Si preceden a la variable, ésta es incrementada antes de que el valor de dicha variable sea utilizado en la expresión en la que aparece. Si es la variable la que precede al operador, la variable es incrementada después de ser utilizada en la expresión. A continuación se presenta un ejemplo de estos operadores: i = 2; j = 2; m = i++; // después de ejecutarse esta sentencia m=2 e i=3 n = ++j; // después de ejecutarse esta sentencia n=3 y j=3 Estos operadores son muy utilizados. Es importante entender muy bien por qué los resultados m y n del ejemplo anterior son diferentes.

20

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

3.1.4 OPERADORES RELACIONALES Este es un apartado especialmente importante para todas aquellas personas sin experiencia en programación. Una característica imprescindible de cualquier lenguaje de programación es la de considerar alternativas, esto es, la de proceder de un modo u otro según se cumplan o no ciertas condiciones. Los operadores relacionales permiten estudiar si se cumplen o no esas condiciones. Así pues, estos operadores producen un resultado u otro según se cumplan o no algunas condiciones que se verán a continuación. En el lenguaje natural, existen varias palabras o formas de indicar si se cumple o no una determinada condición. En inglés estas formas son (yes, no); (on, off); (true, false), etc. En Informática se ha hecho bastante general el utilizar la última de las formas citadas: (true, false). Si una condición se cumple, el resultado es true; en caso contrario, el resultado es false. En C++ un “0” representa la condición de “false”, y cualquier número distinto de 0 equivale a la condición “true”. Cuando el resultado de una expresión es true y hay que asignar un valor concreto distinto de cero, por defecto se toma un valor unidad. Los operadores relacionales de C++ son los siguientes:  Igual que: ==  Menor que: <  Mayor que: >  Menor o igual que: <=  Mayor o igual que: >=  Distinto que: != Todos los operadores relacionales son operadores binarios (tienen dos operandos), y su forma general es la siguiente: expresion1 op expresion2 Donde “op” es uno de los operadores (==, <, >, <=, >=, !=). El funcionamiento de estos operadores es el siguiente: se evalúan expresion1 y expresion2, y se comparan los valores resultantes. Si la condición representada por el operador relacional se cumple, el resultado es “1”; si la condición no se cumple, el resultado es “0”. A continuación se incluyen algunos ejemplos de estos operadores aplicados a constantes: (2==1) (3<=3) (3<3) (1!=1)

// Resultado=0 porque la condición no se cumple // Resultado=1 porque la condición se cumple // Resultado=0 porque la condición no se cumple // Resultado=0 porque la condición no se cumple

3.1.5 OPERADORES LÓGICOS Los operadores lógicos son operadores binarios que permiten combinar los resultados de los operadores relacionales, comprobando que se cumplen simultáneamente varias condiciones, que se cumple una u otra, etc. El lenguaje C tiene dos operadores lógicos: el operador Y (&&) y el operador O (||). En inglés son los operadores and y or. Su forma general es la siguiente:

21

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

expresion1 || expresion2 expresion1 && expresion2 El operador && devuelve un “1” si tanto expresion1 como expresion2 son verdaderas (o distintas de “0”), y “0” en caso contrario, es decir si una de las dos expresiones o las dos son falsas (iguales a “0”); por otra parte, el operador || devuelve “1” si al menos una de las expresiones es cierta. Es importante tener en cuenta que los compiladores de C++ tratan de optimizar la ejecución de estas expresiones, lo cual puede tener a veces efectos no deseados. Por ejemplo: Para que el resultado del operador && sea verdadero, ambas expresiones tienen que ser verdaderas; si se evalúa expresion1 y es falsa, ya no hace falta evaluar expresion2, y de hecho no se evalúa. Algo parecido pasa con el operador ||: si expresion1 es verdadera, ya no hace falta evaluar expresion2. Los operadores && y || se pueden combinar entre sí –quizás agrupados entre paréntesis, dando a veces un código de más difícil interpretación. Por ejemplo: (2==1) || (-1==-1) (2==2) && (3==-1) ((2==2) && (3==3)) || (4==0) ((6==6) || (8==0)) && ((5==5) && (3==2))

// el resultado es 1 // el resultado es 0 // el resultado es 1 // el resultado es 0

3.1.6 OTROS OPERADORES Además de los operadores vistos hasta ahora, el lenguaje C dispone de otros operadores. En esta sección se describen algunos operadores unarios adicionales. Operador menos (–). El efecto de este operador en una expresión es cambiar el signo de la variable o expresión que le sigue. Recuérdese que en C++ no hay constantes numéricas negativas. La forma general de este operador es: - expresión Operador más (+). Este es un nuevo operador unario introducido en el ANSI C, y que tiene como finalidad la de servir de complemento al operador (–) visto anteriormente. Se puede anteponer a una variable o expresión como operador unario, pero en realidad no hace nada. Operador sizeof( ). Este es el operador de C con el nombre más largo. Puede parecer una función, pero en realidad es un operador. La finalidad del operador sizeof( ) es devolver el tamaño, en bytes, del tipo de variable introducida entre los paréntesis. Recuérdese que este tamaño depende del compilador y del tipo de computador que se está utilizando, por lo que es necesario disponer de este operador para producir código portable. Por ejemplo: var_1 = sizeof(double)

// var_1 contiene el tamaño // de una variable doublé

22

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

Operador negación lógica (!). Este operador devuelve un cero (false) si se aplica a un valor distinto de cero (true), y devuelve un 1 (true) si se aplica a un valor cero (false). Su forma general es: !expresion Operador coma (,). Los operandos de este operador son expresiones, y tiene la forma general: expresion = expresion_1, expresion_2 En este caso, expresion_1 se evalúa primero, y luego se evalúa expresion_2. El resultado global es el valor de la segunda expresión, es decir de expresion_2. Este es el operador de menos precedencia de todos los operadores de C++. Como se explicará más adelante, su uso más frecuente es para introducir expresiones múltiples en la sentencia FOR. Operadores dirección (&) e indirección (*). Aunque estos operadores se introduzcan aquí de modo circunstancial, su importancia en el lenguaje C++ es absolutamente esencial, resultando uno de los puntos más fuertes y quizás más difíciles de dominar de este lenguaje. La forma general de estos operadores es la siguiente: *expresion; &variable; El operador dirección & devuelve la dirección de memoria de la variable que le sigue. Por ejemplo: variable_1 = &variable_2; Después de ejecutarse esta instrucción variable_1 contiene la dirección de memoria donde se guarda el contenido de variable_2. Las variables que almacenan direcciones de otras variables se denominan punteros (o apuntadores), deben ser declaradas como tales, y tienen su propia aritmética y modo de funcionar. Se verán con detalle un poco más adelante. No se puede modificar la dirección de una variable, por lo que no están permitidas operaciones en las que el operador & figura a la izquierda del operador (=), al estilo de: &variable_1 = nueva_direccion; El operador indirección * es el operador complementario del &. Aplicado a una expresión que represente una dirección de memoria (puntero) permite hallar el contenido o valor almacenado en esa dirección. Por ejemplo: variable_3 = *variable_1;

23

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

El contenido de la dirección de memoria representada por la variable de tipo puntero variable_1 se recupera y se asigna a la variable variable_3. Como ya se ha indicado, las variables puntero y los operadores dirección (&) e indirección (*) serán explicados con mucho más detalle en una sección posterior. 3.2 EXPRESIONES Ya han aparecido algunos ejemplos de expresiones del lenguaje C++ en las secciones precedentes. Una expresión es una combinación de variables y/o constantes, y operadores. La expresión es equivalente al resultado que proporciona al aplicar sus operadores a sus operandos. Por ejemplo: 1+5 es una expresión formada por dos operandos (1 y 5) y un operador (el +); esta expresión es equivalente al valor 6, lo cual quiere decir que allí donde esta expresión aparece en el programa, en el momento de la ejecución es evaluada y sustituida por su resultado. Una expresión puede estar formada por otras expresiones más sencillas, y puede contener paréntesis de varios niveles agrupando distintos términos. En C++ existen distintos tipos de expresiones. 3.2.1 EXPRESIONES ARITMÉTICAS Están formadas por variables y/o constantes, y distintos operadores aritméticos e incrementales (+, -, *, /, %, ++, --). Como se ha dicho, también se pueden emplear paréntesis de tantos niveles como se desee, y su interpretación sigue las normas aritméticas convencionales. Por ejemplo, la solución de la ecuación de segundo grado:

Se escribe, en C++ en la forma:

=

− ±√

−

x= (-b + sqrt((b*b)-(4*a*c)))/(2*a); Donde, estrictamente hablando, sólo lo que está a la derecha del operador de asignación (=) es una expresión aritmética. El conjunto de la variable que está a la izquierda del signo (=), el operador de asignación, la expresión aritmética y el carácter (;) constituyen una sentencia. En la expresión anterior aparece la llamada a la función de librería sqrt(), que tiene como valor de retorno la raíz cuadrada de su único argumento. En las expresiones se pueden introducir espacios en blanco entre operandos y operadores; por ejemplo, la expresión anterior se puede escribir también de la forma: x= (-b + sqrt( ( b * b ) - ( 4 * a * c ) ) ) /(2*a);

3.2.2 EXPRESIONES LÓGICAS Los elementos con los que se forman estas expresiones son valores lógicos; verdaderos (true, o distintos de 0) y falsos (false, o iguales a 0), y los operadores lógicos ||, && y !. También se

24

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

pueden emplear los operadores relacionales (<, >, <=, >=, ==, !=) para producir estos valores lógicos a partir de valores numéricos. Estas expresiones equivalen siempre a un valor 1 (true) o a un valor 0 (false). Por ejemplo: a = ((b>c)&&(c>d))||((c==e)||(e==b)); Donde de nuevo la expresión lógica es lo que está entre el operador de asignación (=) y el (;). La variable a valdrá 1 si b es mayor que c y c mayor que d, ó si c es igual a e ó e es igual a b.

3.2.3 EXPRESIONES GENERALES Una de las características más importantes (y en ocasiones más difíciles de manejar) del C++ es su flexibilidad para combinar expresiones y operadores de distintos tipos en una expresión que se podría llamar general, aunque es una expresión absolutamente ordinaria de C++. Recuérdese que el resultado de una expresión lógica es siempre un valor numérico (un 1 ó un 0); esto permite que cualquier expresión lógica pueda aparecer como sub-expresión en una expresión aritmética. Recíprocamente, cualquier valor numérico puede ser considerado como un valor lógico: true si es distinto de 0 y false si es igual a 0. Esto permite introducir cualquier expresión aritmética como sub-expresión de una expresión lógica. Por ejemplo: (a - b*2.0) && (c != d) A su vez, el operador de asignación (=), además de introducir un nuevo valor en la variable que figura a su izquierda, deja también este valor disponible para ser utilizado en una expresión más general. Por ejemplo, supóngase el siguiente código que inicializa a 1 las tres variables a, b y c: a = b = c = 1; Que equivale a: a = (b = (c = 1)); En realidad, lo que se ha hecho ha sido lo siguiente. En primer lugar se ha asignado un valor unidad a c; el resultado de esta asignación es también un valor unidad, que está disponible para ser asignado a b; a su vez el resultado de esta segunda asignación vuelve a quedar disponible y se puede asignar a la variable a. 3.3 SENTENCIAS Las expresiones de C++ son unidades o componentes elementales de unas entidades de rango superior que son las sentencias. Las sentencias son unidades completas, ejecutables en sí mismas. Ya se verá que muchos tipos de sentencias incorporan expresiones aritméticas, lógicas o generales como componentes de dichas sentencias.

25

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

3.3.1 SENTENCIAS SIMPLES Una sentencia simple es una expresión de algún tipo terminada con un carácter (;). Un caso típico son las declaraciones o las sentencias aritméticas. Por ejemplo: float real; espacio = espacio_inicial + velocidad * tiempo; 3.3.2 SENTENCIA VACÍA Ó NULA En algunas ocasiones es necesario introducir en el programa una sentencia que ocupe un lugar, pero que no realice ninguna tarea. A esta sentencia se le denomina sentencia vacía y consta de un simple carácter (;). Por ejemplo:

; 3.3.3 SENTENCIAS COMPUESTAS O BLOQUES Muchas veces es necesario poner varias sentencias en un lugar del programa donde debería haber una sola. Esto se realiza por medio de sentencias compuestas. Una sentencia compuesta es un conjunto de declaraciones y de sentencias agrupadas dentro de llaves {...}. También se conocen con el nombre de bloques. Una sentencia compuesta puede incluir otras sentencias, simples y compuestas. Un ejemplo de sentencia compuesta es el siguiente: { int i = 1, j = 3, k; double masa; masa = 3.0; k = i + j; }

4. CONTROL DEL FLUJO DE EJECUCIÓN En principio, las sentencias de un programa en C se ejecutan secuencialmente, esto es, cada una a continuación de la anterior empezando por la primera y acabando por la última. El lenguaje C++ dispone de varias sentencias para modificar este flujo secuencial de la ejecución. Las más utilizadas se agrupan en dos familias: las bifurcaciones, que permiten elegir entre dos o más opciones según ciertas condiciones, y los bucles, que permiten ejecutar repetidamente un conjunto de instrucciones tantas veces como se desee, cambiando o actualizando ciertos valores. 4.1 BIFURCACIONES 4.1.1 OPERADOR CONDICIONAL El operador condicional es un operador con tres operandos (ternario) que tiene la siguiente forma general: expresion_1 ? expresion_2 : expresion_3; Explicación: Se evalúa expresion_1. Si el resultado de dicha evaluación es true (=1), se ejecuta expresion_2; si el resultado es false (=0), se ejecuta expresion_3.

26

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

4.1.2 SENTENCIA “IF” Esta sentencia de control permite ejecutar o no una sentencia simple o compuesta según se cumpla o no una determinada condición. Esta sentencia tiene la siguiente forma general: if (expresion) sentencia; Explicación: Se evalúa “expresion”. Si el resultado es true (=1), se ejecuta sentencia; si el resultado es false (=0), se salta sentencia y se prosigue en la línea siguiente. Hay que recordar que sentencia puede ser una sentencia simple o compuesta (bloque { ... }). EJEMPLO Nº 1 Realizar un programa que permita determinar si un número introducido por teclado es positivo. #include using namespace std; int main() { int num; cout<<"Introduzca un numero"<<endl; cin>>num; if (num>0) cout<<"Es positivo"; return 0; } 4.1.3 SENTENCIA “IF ... ELSE” Esta sentencia permite realizar una bifurcación, ejecutando una parte u otra del programa según se cumpla o no una cierta condición. La forma general es la siguiente: if (expresion) sentencia_1; else sentencia_2; Explicación: Se evalúa “expresion”. Si el resultado es true (=1), se ejecuta sentencia_1 y se prosigue en la línea siguiente a sentencia_2; si el resultado es false (=0), se salta sentencia_1, se ejecuta sentencia_2 y se prosigue en la línea siguiente. Hay que indicar aquí también que sentencia_1 y sentencia_2 pueden ser sentencias simples o compuestas (bloques { ... }).

EJEMPLO Nº 2 Diseñar un programa para determinar el mayor de dos números introducidos por teclado.

27

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

#include using namespace std; int main() { int num1,num2; cout<<"Introduzca el primer numero"<<endl; cin>>num1; cout<<"Introduzca el segundo numero"<<endl; cin>>num2; if (num1>num2) cout<<"l mayor es: "< using namespace std;

28

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

int main() { int num1,num2; cout<<"Introduzca un primer numero"<<endl; cin>>num1; cout<<"Introduzca un segundo numero"<<endl; cin>>num2; if (num2==(num1+1)) cout<
29

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

case expresion_cte_2: case expresion_cte_3:sentencia_2; break; default: sentencia_3; }

EJEMPLO Nº 4 Realizar un menú con las cuatro operaciones básicas de la aritmética. #include using namespace std; int main() { int a,b,op; cout<<"Inserte primer valor: "<<endl; cin>>a; cout<<"Inserte segundo valor: "<<endl; cin>>b; cout<<endl<<"Seleccione una opción: "<<endl; cout<<"1.- Sumar"<<endl; cout<<"2.- Restar"<<endl; cout<<"3.- Multiplicar"<<endl; cout<<"4.- Dividir"<<endl; cout<<"5.- Salir"<<endl; cout<<endl<<"Opcion: "; cin>>op; switch(op) { case 1: cout<<"La suma es: "<= b) if (b != 0.0) c = a/b; En ocasiones pueden aparecer dificultades de interpretación con sentencias if...else anidadas, como en el caso siguiente:

30

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

if (a >= b) if (b != 0.0) c = a/b; else c = 0.0; En principio se podría plantear la duda de a cuál de los dos if corresponde la parte else del programa. Los espacios en blanco las indentaciones de las líneas parecen indicar que la sentencia que sigue a else corresponde al segundo de los if, y así es en realidad, pues la regla es que el else pertenece al if más cercano. Sin embargo, no se olvide que el compilador de C++ no considera los espacios en blanco (aunque sea muy conveniente introducirlos para hacer más claro y legible el programa), y que si se quisiera que el else perteneciera al primero de los if no bastaría cambiar los espacios en blanco, sino que habría que utilizar llaves, en la forma: if (a >= b) { if (b != 0.0) c = a/b; } else c = 0.0; Recuérdese que todas las sentencias if e if...else, equivalen a una única sentencia por la posición que ocupan en el programa. EJEMPLO Nº 5 Dado tres números enteros determinar cuál de ellos es el número mayor. #include using namespace std; int main() { int num1,num2,num3; cout<<"Primer valor"<<endl; cin>>num1; cout<<"Segundo valor"<<endl; cin>>num2; cout<<"Tercer valor"<<endl; cin>>num3; if (num1>num2) { if(num1>num3) cout<<"El mayor es: "<
31

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

{ if (num2>num3) cout<<"El mayor es: "< using namespace std; int main() { int a, b; while (cin>>a>>b && a>0 && b>0) { cout<
32

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

} return 0; } 4.2.2 SENTENCIA “FOR” For es quizás el tipo de bucle más versátil y utilizado del lenguaje C++. Su forma general es la siguiente: for (inicialización; expresion_de_control; actualización) sentencia; Explicación: Posiblemente la forma más sencilla de explicar la sentencia for sea utilizando la construcción while que sería equivalente. Dicha construcción es la siguiente: inicializacion; while (expresion_de_control) { sentencia; actualizacion; } Donde sentencia puede ser una única sentencia terminada con (;), otra sentencia de control ocupando varias líneas (if, while, for, ...), o una sentencia compuesta o un bloque encerrado entre llaves {...}. Antes de iniciarse el bucle se ejecuta inicialización, que es una o más sentencias que asignan valores iniciales a ciertas variables o contadores. A continuación se evalúa expresion_de_control y si es false se prosigue en la sentencia siguiente a la construcción for; si es true se ejecutan sentencia y actualización, y se vuelve a evaluar expresion_de_control. El proceso prosigue hasta que expresion_de_control sea false. La parte de actualizacion sirve para actualizar variables o incrementar contadores. Un ejemplo típico puede ser el producto escalar de dos vectores a y b de dimensión n: for (pe =0.0, i=1; i<=n; i++) { pe += a[i]*b[i]; } Primeramente se inicializa la variable pe a cero y la variable i a 1; el ciclo se repetirá mientras que i sea menor o igual que n, y al final de cada ciclo el valor de i se incrementará en una unidad. En total, el bucle se repetirá n veces. La ventaja de la construcción for sobre la construcción while equivalente está en que en la cabecera de la construcción for se tiene toda la información sobre cómo se inicializan, controlan y actualizan las variables del bucle. Obsérvese que la inicialización consta de dos sentencias separadas por el operador (,).

EJEMPLO Nº 7 Diseñar un programa para generar la tabla de multiplicar de cualquier número introducido por teclado.

33

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

#include using namespace std; int main() { int num; cout<<"Inserte el numero que desa generar la tabla"<<endl; cin>>num; for (int i=1;i<=10;i++) { cout<>n; cout<<endl; do { cout<
34

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

if(t-2==n)a=0; }while (a); cout<<endl<<endl<<"La suma es: "<<s; return 0; } 4.3 GENERACIÓN DE NÚMEROS ALEATORIOS En C++, existe una función llamada rand(), que genera números aleatorios. El problema que tiene esta función es que siempre que reinicies el programa, aparecerán los mismos números. Para evitar esto, hay que darle un número “semilla”, el cual operará como base para la generación de la secuencia de números. El problema con esto, es que si le damos un número fijo, volvemos al problema anterior, ya que siempre utilizará la misma base definida y por ende la secuencia será la misma. Entonces, lo que necesitamos es darle un número “semilla” dinámico, esto es, que vaya cambiando cada vez que ejecutemos el programa. Sabiendo esto, la función que da la semilla a rand() es srand(), que recibe como parámetro (lo que va entre los paréntesis) el número semilla, que en este caso, será la hora del sistema en segundos. Así, a menos que el programa se ejecute 2 o más veces en menos de un segundo, los números cambiarán. La función para saber la hora actual del sistema es time(NULL). Sabiendo esto, vamos al código. Haremos un generador de números aleatorios, donde la cantidad de estos, la decidirá el usuario, ingresando esta cantidad por teclado. Así que lo primero que tenemos que hacer es incluir la librería: #include Luego inicializar los números aleatorios incluyendo esto: srand(time(NULL)); Solo hay que utilizar además la librería time.h: #include Luego guardar el número aleatorio en alguna parte: num=rand(); Eso es básicamente. Para ajustar el rango de número aleatorios podemos hacer varias cosas. Número aleatorios entre 0 y 50: num=rand()%51; Número aleatorios entre 1 y 100: num=1+rand()%(101-1);

35

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

Número aleatorios entre 250 y 420: num=250+rand()%(421-250); De forma general es: variable = limite_inferior + rand() % (limite_superior +1 - limite_inferior) ; EJEMPLO Nº 9 Realizar un programa que muestre 10 números aleatorios entre 1 y 10: #include #include #include using namespace std; int main() { int num,c; srand(time(NULL)); for(c=1;c<=10;c++) { num=1+rand()%(11-1);//Generando números aleatorio entre 1 y 10 cout<
36

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

PROBLEMAS PROPUESTOS Con los fundamentos necesarios de C++ que hemos aprendido, ya estás listo para resolver los siguientes problemas. 1. 2. 3. 4. 5.

Diseñar un programa para calcular la suma de dos números A y B Calcular el área de un triángulo de base B y altura H Calcular el área de un círculo de radio R Ingresar una nota por teclado y determinar si es de aprobación o reprobación Ingresar un número por teclado y determinar si es PAR o IMPAR

6. Determinar si una persona es "Niño – 1 a 10 años", "Adolescente – 11 a 17 años", "Joven – 18 a 29 años", "Adulto – 30 a 60 años", "Tercera Edad – 60 a 100 años", de acuerdo a su edad que es introducida por teclado. 7. Generar Aleatoriamente dos números enteros entre 0 y 100. Determinar cuál es el mayor de ellos. 8. Introducir tres números por teclado. Determinar cuál es el mayor de los tres 9. Visualizar cuatro operaciones aritméticas de dos números cualesquiera introducidos por teclado. 10. Ingresar un número cualquiera, determina si es POSITIVO, NEGATIVO ó CERO 11. Generar un numero aleatoriamente entre 1 a 1000 y determinar si es PAR o IMPAR 12. Introducir un número positivo por teclado. Si es negativo o cero rechazarlo, caso contrario, determinar si el número positivo es par o impar 13. Ingresar un número por teclado y determinar si es múltiplo de 10 14. Ingresar una nota por teclado y determinar su grado de aprovechamiento (0-10) Pésimo, (11-20) Muy Malo, (21-30) Malo, (31-40) regular, (41-50) Bueno, (51-60) Muy Bueno, (6170) Excelente 15. Simular un juego con un dado. Si se saca un 1 o un 6 e gana, caso contrario se pierde. 16. Simular un juego con dos dados. Si se saca un siete o un once se gana, caso contrario se pierde. 17. Visualizar la serie 1,3,5,7,…….n 18. Visualizar la serie 1,4,7,10,13,16……..n 19. Ingresar un número y visualizar su tabla de multiplicar

37

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

38

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

5. INTRODUCCION A LA ESTRUCTURA DE DATOS Una estructura de datos es una colección de datos que pueden ser caracterizados por su organización y las operaciones que se definen en ella. Las estructuras de datos son muy importantes en los sistemas de computadoras. Los tipos de datos más frecuentes utilizados en los diferentes lenguajes de programación son: Datos Simples

Estándar

entero (integer) real (real) carácter (char) lógico (boolean) Definido por el programador subrango (subrange) (No estándar) enumerativo (enumerated)

Datos Estructurados

Estáticos

arrays (vectores / matrices) registros (record) ficheros (archivos) conjuntos (set) cadenas (string) listas (pilas / colas) listas enlazadas árboles grafos

Dinámicos

5.1 ARRAYS UNIDIMENSIONALES: “VECTORES” Los vectores son una forma de almacenar datos que permiten contener una serie de valores del mismo tipo, cada uno de los valores contenidos tiene una posición asociada que se usará para accederlos. Está posición o índice será siempre un número entero positivo. En C++ la cantidad de elementos que podrá contener un vector es fijo, y en principio se define cuando se declara el vector. Los vectores se pueden declarar de la siguiente forma: tipo_elemento nombre[largo]; Esto declara la variable nombre como un vector de tipo_elementos que podrá contener largo cantidad de elementos, y cada uno de estos elemento podrá contener un valor de tipo tipo_elemento. Por ejemplo: double valores[128]; En este ejemplo declaramos un vector de 128 elementos del tipo double, los índices de los elementos irían entre 0 (para el primer elemento y 127 para el último). De la misma forma que con las otras declaraciones de variables que hemos visto se le puede asignar un valor iniciar a los elementos. O también se pueden declarar: tipo_elemento nombre[largo]={valor_0, valor_1, valor_2};

39

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

En este caso estamos asignándole valores a los primeros 3 elementos del vector nombre. Notar que largo debe ser mayor o igual a la cantidad de valores que le estamos asignando al vector, en el caso de ser la misma cantidad no aporta información, por lo que el lenguaje nos permite escribir: tipo_elemento nombre[]={valor_0, valor_1, valor_2}; Que declarará nombre como el vector de largo 3. Para acceder a un elemento accederemos a través de su posición. Es decir: tipo_elemento elemento[largo]; ... elemento[2] = valor_2; Asumiendo que tenemos guardando valor_2 en elemento[2].

el

vector

anterior

definido

estaríamos

5.2. OPERACIONES CON VECTORES. Un vector, como ya se ha mencionado, es una secuencia ordenada de elementos como: x[1], x[2],………….., x[n]; El límite inferior no tiene por qué empezar en uno. El vector L. L[0], L[1], L[2], L[3], L[4], L[5]; Contiene seis elementos, en el que el primer elemento comienza en cero. El vector P, cuyo rango es 7 y sus límites inferior y superior son -3 y 3, es: P[-3, P[-2], P[-1], P[0], P[1], P[2], P[3];

Las operaciones que se pueden realizar con vectores durante el proceso de resolución de un problema son:  Asignación  Lectura / Escritura  Recorrido (Acceso secuencial)  Actualizar (Añadir, borrar, insertar)  Ordenación  Busqueda.

40

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

A continuación se presente un programa con todas las operaciones ya mencionadas. #include #include #include #include #include #include #include #include

<string.h>

using namespace std; int v[500]; int n; void mostrar() { for(int i=0;i>n; cout<<endl; memset(v,0,sizeof(v)); cout<<'\t'; mostrar(); system("cls"); } else { cout<<" VECTOR YA CREADO"<<endl<<endl; cout<<'\t'; mostrar(); system("cls"); } } void salir() { cout<<"GRACIAS!!! - SOFTWARE DESARROLLADO POR WILFREDO FUENTES"<<endl;; } void insertar_posicion() { int c,d; if (v[0]==-1) { cout<<"Vector no creado"<<endl; } else { cout<<"Inserte posicion del vector"<<endl; cin>>c; if (c>n) { cout<<"Posicion Inexistente"<<endl; cout<<"Introduzca la posicion del vector de "<>c; } cout<<"Introduzca el valor de la posicion"<<endl; cin>>d; } v[c-1]=d; cout<<endl; mostrar(); } void insertar_manual() { for(int i=0;i>v[i]; } cout<<endl; mostrar(); } void insertar_aleatorio() { int al; srand(time(NULL)); cout<<"Inserte el rango de numeros aleatorios"<<endl; cin>>al; for(int i=0;i
41

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE v[i]=1+rand()%(al-1); } cout<<endl; mostrar(); } void modificar_posicion() { int c,d; if (v[0]==-1) { cout<<"Vector no creado"<<endl; } else { cout<<"Que posicion desea modificar???"<<endl; cin>>c; if (c>n) { cout<<"Posicion Inexistente"<<endl; cout<<"Introduzca la posicion del vector de "<>c; } cout<<"Introduzca el nuevo valor de la posicion"<<endl; cin>>d; } cout<<"Vector Anterior"<<endl; mostrar(); v[c-1]=d; cout<<"Vector Modificado"<<endl; mostrar(); } void modificar_global() { for(int i=0;i>v[i]; } cout<<endl; mostrar(); } void eliminar_posicion() { int e; if (v[0]==-1) { cout<<"Vector no creado"<<endl; } else { cout<<"Inserte posicion del vector que desea eliminar"<<endl; cin>>e; if (e>n) { cout<<"Posicion Inexistente"<<endl; cout<<"Introduzca la posicion del vector de "<>e; } } v[e-1]=0; cout<<endl; mostrar(); }

void eliminar_global() { if (v[0]==-1) { cout<<"No existe vector para eliminar, debe crear Vector"<<'\n'<<endl; system("pause"); system("cls"); } else { cout<<"Usted Elimino Todo el Vector debera volver a crear otro"<<endl<<'\n'; system("pause"); system("cls"); memset(v,-1,sizeof(v)); } } void ordenar_ascendente() { cout<<"Vector Anterior"<<endl; for(int i=0;i
42

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE sort(v,v+n); } mostrar(); } void ordenar_descendente() { cout<<"Vector Anterior"<<endl; for(int i=0;i=0;i--) { sort(v,v+n,greater()); cout<<endl; } mostrar(); }

int main() { int op; memset(v,-1,sizeof(v)); while (op!=8) { cout<<'\t'<<"========================================="<<endl; cout<<'\t'<<" MENU VECTORES "<<endl; cout<<'\t'<<"========================================="<<endl; cout<<'\t'<<" 1.- CREAR "<<endl; cout<<'\t'<<" 2.- INSERTAR "<<endl; cout<<'\t'<<" 3.- MODIFICAR "<<endl; cout<<'\t'<<" 4.- ELIMINAR "<<endl; cout<<'\t'<<" 5.- ORDENAR "<<endl; cout<<'\t'<<" 6.- MOSTRAR "<<endl; cout<<'\t'<<" 7.- SALIR "<<endl; cout<<'\t'<<"========================================="<<endl; cout<<'\t'<<" OPCION: ";cin>>op; system("cls"); if (op!=8) { switch(op) { case 1: crear(); break; case 2: int b; if (v[0]==-1) { cout<<"El vector no existe"<<endl; system("pause"); system("cls"); } else if (v[0]>0) { cout<<"Vetor Lleno"<<endl; system("pause"); system("cls"); } else { cout<<'\t'<<"========================================="<<endl; cout<<'\t'<<" MENU VECTORES - INSERTAR "<<endl; cout<<'\t'<<"========================================="<<endl; cout<<'\t'<<" 1.- POR POSICION "<<endl; cout<<'\t'<<" 2.- GLOBAL "<<endl; cout<<'\t'<<" 3.- VOLVER "<<endl; cout<<'\t'<<"========================================="<<endl; cout<<'\t'<<" OPCION: ";cin>>b; system("cls"); switch(b) { case 1: insertar_posicion(); break; case 2: int h; cout<<'\t'<<"========================================="<<endl; cout<<'\t'<<" MENU VECTORES - GLOBAL "<<endl; cout<<'\t'<<"========================================="<<endl; cout<<'\t'<<" 1.- INSERTAR MANUALMENTE "<<endl; cout<<'\t'<<" 2.- INSERTAR ALEATORIAMENTE "<<endl; cout<<'\t'<<" 3.- VOLVER "<<endl; cout<<'\t'<<"========================================="<<endl; cout<<'\t'<<" OPCION: ";cin>>h; system("cls"); switch(h) { case 1: insertar_manual(); break; case 2: insertar_aleatorio(); break; case 3: break; } break; case 3: break; } } break;

43

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

case 3: int q; cout<<'\t'<<"========================================="<<endl; cout<<'\t'<<" MENU VECTORES - MODIFICAR "<<endl; cout<<'\t'<<"========================================="<<endl; cout<<'\t'<<" 1.- POR POSICION "<<endl; cout<<'\t'<<" 2.- GLOBAL "<<endl; cout<<'\t'<<" 3.- VOLVER "<<endl; cout<<'\t'<<"========================================="<<endl; cout<<'\t'<<" OPCION: ";cin>>q; system("cls"); switch(q) { case 1: modificar_posicion(); break; case 2: modificar_global(); break; case 3: break; } break; case 4: int o; cout<<'\t'<<"========================================="<<endl; cout<<'\t'<<" MENU VECTORES - ELIMINAR "<<endl; cout<<'\t'<<"========================================="<<endl; cout<<'\t'<<" 1.- POR POSICION "<<endl; cout<<'\t'<<" 2.- GLOBAL "<<endl; cout<<'\t'<<" 3.- VOLVER "<<endl; cout<<'\t'<<"========================================="<<endl; cout<<'\t'<<" OPCION: ";cin>>o; system("cls"); switch(o) { case 1: eliminar_posicion(); break; case 2: eliminar_global(); break; case 3: break; } break; case 5: int l; cout<<'\t'<<"========================================="<<endl; cout<<'\t'<<" MENU VECTORES - ORDENAR "<<endl; cout<<'\t'<<"========================================="<<endl; cout<<'\t'<<" 1.- ASCENDENTE "<<endl; cout<<'\t'<<" 2.- DESCENDENTE "<<endl; cout<<'\t'<<" 3.- VOLVER "<<endl; cout<<'\t'<<"========================================="<<endl; cout<<'\t'<<" OPCION: ";cin>>l; system("cls"); switch(l) { case 1: ordenar_ascendente(); break; case 2: ordenar_descendente(); break; case 3: break; } break; case 6: mostrar(); break; case 7: salir(); return 0; } } }

return 0; }

NOTA: Para el diseño del menú se utilizo la nueva librería de C++ llamada STL, la cual facilita al programador el ahorro de memoria en el código. ALGUNAS DIFERENCIAS ENTRE LA LIBRERÍA STL Y LA CLASICA DE C++: Método de Ordenación con la librería de C++ Clásica: int aux; for (int c2=0;c2lista[c2+1]) { aux=lista[c2]; lista[c2]=lista[c2+1]; lista[c2+1]=aux; } }

44

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

Método de Ordenación con la librería STL: int v[10]; for(int i=0;i<10;i++) { sort(v,v+10); } Llenado de un vector con la librería de C++ Clásica: int v[10]; for(int i=0;i<10;i++) { v[i]=0; cout<
45

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

La forma de acceder a los elementos de la matriz es utilizando su nombre e indicando los dos subíndices que van en los corchetes. Si Coloco int matriz[2][3]=10; estoy asignando al cuarto elemento de la tercera fila el valor 10. No olvidar que tanto filas como columnas se enumeran a partir de 0. Ejemplo: 0,0 1,0 2,0 3,0

0,1 1,1 2,1 3,1

0,2 1,2 2,2 3,2

0,3 1,3 2,3 3,3

FILA

COLUMNA 5.5 PUNTEROS No, no salgas corriendo todavía. Aunque vamos a empezar con un tema que suele asustar a los estudiantes de C++, no es algo tan terrible como se cuenta. Como se suele decir de los leones: no son tan fieros como los pintan. Los punteros proporcionan la mayor parte de la potencia al C++, y marcan la principal diferencia con otros lenguajes de programación. Una buena comprensión y un buen dominio de los punteros pondrá en tus manos una herramienta de gran potencia. Un conocimiento mediocre o incompleto te impedirá desarrollar programas eficaces. Por eso le dedicaremos mucha atención y mucho espacio a los punteros. Es muy importante comprender bien cómo funcionan y cómo se usan. Creo que todos sabemos lo que es un puntero, fuera del ámbito de la programación. Usamos punteros para señalar cosas sobre las que queremos llamar la atención, como marcar puntos en un mapa o detalles en una presentación en pantalla. A menudo, usamos el dedo índice para señalar direcciones o lugares sobre los que estamos hablando o explicando algo. Cuando un dedo no es suficiente, podemos usar punteros. Antiguamente esos punteros eran una vara de madera, pero actualmente se usan punteros laser, aunque la idea es la misma. Un puntero también es el símbolo que representa la posición del ratón en una pantalla gráfica. Estos punteros también se usan para señalar objetos: enlaces, opciones de menú, botones, etc. Un puntero sirve, pues, para apuntar a los objetos a los que nos estamos refiriendo. Pues en C++ un puntero es exactamente lo mismo. Probablemente habrás notado que a lo largo del curso nos hemos referido a variables, constantes, etc como objetos. Esto ha sido intencionado por el siguiente motivo: C++ está diseñado para la programación orientada a objetos (POO), y en ese paradigma, todas las entidades que podemos manejar son objetos. Los punteros en C++ sirven para señalar objetos, y también para manipularlos.

46

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

Para entender qué es un puntero veremos primero cómo se almacenan los datos en un ordenador. La memoria de un ordenador está compuesta por unidades básicas llamadas bits. Cada bit sólo puede tomar dos valores, normalmente denominados alto y bajo, ó 1 y 0. Pero trabajar con bits no es práctico, y por eso se agrupan. Cada grupo de 8 bits forma un byte u octeto. En realidad el microprocesador, y por lo tanto nuestro programa, sólo puede manejar directamente bytes o grupos de dos o cuatro bytes. Para acceder a los bits hay que acceder antes a los bytes. Cada byte de la memoria de un ordenador tiene una dirección, llamada dirección de memoria. Los microprocesadores trabajan con una unidad básica de información, a la que se denomina palabra (en inglés word). Dependiendo del tipo de microprocesador una palabra puede estar compuesta por uno, dos, cuatro, ocho o dieciséis bytes. Hablaremos en estos casos de plataformas de 8, 16, 32, 64 ó 128 bits. Se habla indistintamente de direcciones de memoria, aunque las palabras sean de distinta longitud. Cada dirección de memoria contiene siempre un byte. Lo que sucederá cuando las palabras sean, por ejemplo, de 32 bits es que accederemos a posiciones de memoria que serán múltiplos de 4. Por otra parte, la mayor parte de los objetos que usamos en nuestros programas no caben en una dirección de memoria. La solución utilizada para manejar objetos que ocupen más de un byte es usar posiciones de memoria correlativas. De este modo, la dirección de un objeto es la dirección de memoria de la primera posición que contiene ese objeto. Dicho de otro modo, si para almacenar un objeto se precisan cuatro bytes, y la dirección de memoria de la primera posición es n, el objeto ocupará las posiciones desde n a n+3, y la dirección del objeto será, también, n. Todo esto sucede en el interior de la máquina, y nos importa relativamente poco. Pero podemos saber qué tipo de plataforma estamos usando averiguando el tamaño del tipo int, y para ello hay que usar el operador sizeof, por ejemplo: cout << "Plataforma de " << 8*sizeof(int) << " bits";

Ahora veamos cómo funcionan los punteros. Un puntero es un tipo especial de objeto que contiene, ni más ni menos que, la dirección de memoria de un objeto. Por supuesto, almacenada a partir de esa dirección de memoria puede haber cualquier clase de objeto: un char, un int, un float, un array, una estructura, una función u otro puntero. Seremos nosotros los responsables de decidir ese contenido, al declarar el puntero. De hecho, podríamos decir que existen tantos tipos diferentes de punteros como tipos de objetos puedan ser referenciados mediante punteros. Si tenemos esto en cuenta, los punteros que apunten a tipos de objetos distintos, serán tipos diferentes. Por ejemplo, no podemos asignar a un puntero a char el valor de un puntero a int. Intentemos ver con mayor claridad el funcionamiento de los punteros. Podemos considerar la memoria del ordenador como un gran array, de modo que podemos acceder a cada celda de memoria a través de un índice. Podemos considerar que la primera posición del array es la 0 celda [0].

47

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

Si usamos una variable para almacenar el índice, por ejemplo: indice=0, entonces celda[0] == celda[indice]. Finalmente, si prescindimos de la notación de los arrays, podemos ver que el índice se comporta exactamente igual que un puntero. El puntero indice podría tener por ejemplo, el valor 3, en ese caso, el valor apuntado por indice tendría el valor 'val3'. Las celdas de memoria tienen una existencia física, es decir son algo real y existirán siempre, independientemente del valor del puntero. Existirán incluso si no existe el puntero. De forma recíproca, la existencia o no existencia de un puntero no implica la existencia o la inexistencia del objeto. De la misma forma que el hecho de no señalar a un árbol, no implica la inexistencia del árbol. Algo más oscuro es si tenemos un puntero para árboles, que no esté señalando a un árbol. Un puntero de ese tipo no tendría uso si estamos en medio del mar: tener ese puntero no crea árboles de forma automática cuando señalemos con él. Es un puntero, no una varita mágica. Del mismo modo, el valor de la dirección que contiene un puntero no implica que esa dirección sea válida, en el sentido de que no tiene por qué contener la dirección de un objeto del tipo especificado por el puntero. Supongamos que tenemos un mapa en la pared, y supongamos también que existen diferentes tipos de punteros láser para señalar diferentes tipos de puntos en el mapa (ya sé que esto suena raro, pero usemos la imaginación). Creamos un puntero para señalar ciudades. Nada más crearlo (o encenderlo), el puntero señalará a cualquier sitio, podría señalar incluso a un punto fuera del mapa. En general, daremos por sentado que una vez creado, el puntero no tiene por qué apuntar a una ciudad, y aunque apunte al mapa, podría estar señalando a un mar o a un río. Con los punteros en C++ ocurre lo mismo. El valor inicial del puntero, cuando se declara, podría estar fuera del mapa, es decir, contener direcciones de memoria que no existen. Pero, incluso señalando a un punto de la memoria, es muy probable que no señale a un objeto del tipo adecuado. Debemos considerar esto como el caso más probable, y no usar jamás un puntero que no haya sido inicializado correctamente. Dentro del array de celdas de memoria existirán zonas que contendrán programas y datos, tanto del usuario como del propio sistema operativo o de otros programas, el sistema operativo se encarga de gestionar esa memoria, prohibiendo o protegiendo determinadas zonas. Pero el propio puntero, como objeto que es, también se almacenará en memoria, y por lo tanto, también tendrá una dirección de memoria. Cuando declaramos un puntero estaremos reservando la memoria necesaria para almacenarlo, aunque, como pasa con el resto del los objetos, el contenido de esa memoria contendrá basura. En principio, debemos asignar a un puntero, o bien la dirección de un objeto existente, o bien la de uno creado explícitamente durante la ejecución del programa o un valor conocido que indique que no señala a ningún objeto, es decir el valor 0. El sistema operativo, cuanto más avanzado es, mejor suele controlar la memoria. Ese control se traduce en impedir el acceso a determinadas direcciones reservadas por el sistema.

48

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

5.5.1. DECLARACIÓN DE PUNTEROS Los punteros se declaran igual que el resto de los objetos, pero precediendo el identificador con un asterisco (*). El valor de todas las variables que manejamos en nuestros programas se almacenan en memoria y tienen una dirección. Un puntero es una variable especial que apunta a la dirección de memoria de una variable. El puntero tiene a su vez su propia dirección. Todas estas direcciones tienen un formato hexadecimal. Los punteros son herramientas muy poderosas con muchas utilidades y enormes ventajas como veremos más adelante. A grandes rasgos, un puntero me permite desplazarme en la memoria, apuntar, re direccionar a ciertas variables, funciones, métodos, objetos sin necesidad de mover grandes bloques de datos, lo cual nos ahorra muchísimo el consumo de memoria en los programas. Sintaxis: *; Ejemplos: int *pEntero; char *pCaracter; struct stPunto *pPunto;

Los punteros sólo pueden apuntar a objetos de un tipo determinado, en el ejemplo, pEntero sólo puede apuntar a un objeto de tipo int. La forma: * ; Con el (*) junto al tipo, en lugar de junto al identificador del objeto, también está permitida. De hecho, también es legal la forma: * ; Veamos algunos matices. Tomemos el primer ejemplo: int

*pEntero;

Equivale a: int*

pEntero;

49

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

Otro detalle importante es que, aunque las tres formas de situar el asterisco en la declaración son equivalentes, algunas de ellas pueden inducirnos a error, sobre todo si se declaran varios objetos en la misma línea: int* x, y; En este caso, x es un puntero a int, pero y no es más que un objeto de tipo int. Colocar el asterisco junto al tipo puede que indique más claramente que estamos declarando un puntero, pero hay que tener en cuenta que sólo afecta al primer objeto declarado, si quisiéramos declarar ambos objetos como punteros aint tendremos que hacerlo de otro modo: int* x, // O: int *x, // O: int* x; int* y;

*y; *y;

5.5.2. OBTENER PUNTEROS A OBJETOS Los punteros apuntan a objetos, por lo tanto, lo primero que tenemos que saber hacer con nuestros punteros es asignarles direcciones de memoria válidas de objetos. Para averiguar la dirección de memoria de cualquier objeto usaremos el operador de dirección (&), que leeremos como "dirección de". Por supuesto, los tipos tienen que ser "compatibles", no podemos almacenar la dirección de un objeto de tipo char en un puntero de tipo int. Por ejemplo: int A; int *pA; pA = &A;

Según este ejemplo, pA es un puntero a int que apunta a la dirección donde se almacena el valor del entero A. 5.5.3. OBJETO APUNTADO POR UN PUNTERO La operación contraria es obtener el objeto referenciado por un puntero, con el fin de manipularlo, ya sea modificando su valor u obteniendo el valor actual. Para manipular el objeto apuntado por un puntero usaremos el operador de indirección, que es un asterisco (*). En C++ es muy habitual que el mismo símbolo se use para varias cosas diferentes, este es el caso del asterisco, que se usa como operador de multiplicación, para la declaración de punteros y, como vemos ahora, como operador de indirección.

50

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

Como operador de indirección sólo está permitido usarlo con punteros, y podemos leerlo como "objeto apuntado por". Por ejemplo: int *pEntero; int x = 10; int y; pEntero = &y; *pEntero = x; // (1)

En (1) asignamos al objeto apuntado por pEntero en valor del objeto x. Como pEntero apunta al objeto y, esta sentencia equivale (según la secuencia del programa), a asignar a y el valor de x. 5.5.4. DIFERENCIA ENTRE PUNTEROS Y OTROS OBJETOS Debemos tener muy claro, en el ejemplo anterior, que pEntero es un objeto del tipo "puntero a int", pero que *pEntero NO es un objeto de tipo int, sino una expresión. ¿Por qué decimos esto? Pues porque, como pasa con todos los objetos en C++, cuando se declaran sólo se reserva espacio para almacenarlos, pero no se asigna ningún valor inicial, (recuerda que nuestro puntero para árboles no crea árbol cada vez que señalemos con él). El contenido del objeto permanecerá sin cambios, de modo que el valor inicial del puntero será aleatorio e indeterminado. Debemos suponer que contiene una dirección no válida. Si pEntero apunta a un objeto de tipo int, *pEntero será el contenido de ese objeto, pero no olvides que*pEntero es un operador aplicado a un objeto de tipo "puntero a int". Es decir, *pEntero es una expresión, no un objeto. Declarar un puntero no creará un objeto del tipo al que apunta. Por ejemplo: int *pEntero; no crea un objeto de tipo int en memoria. Lo que crea es un objeto que puede contener la dirección de memoria de un entero. Podemos decir que existe físicamente un objeto pEntero, y también que ese objeto puede (aunque esto no es siempre cierto) contener la dirección de un objeto de tipo int. Como todos los objetos, los punteros también contienen "basura" cuando son declarados. Es costumbre dar valores iniciales nulos a los punteros que no apuntan a ningún sitio concreto: int *pEntero = 0; // También podemos asignar el valor NULL char *pCaracter = 0;

51

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

NULL es una constante, que está definida como cero en varios ficheros de cabecera, como "cstdio" o "iostream". Sin embargo, hay muchos textos que recomiendan usar el valor 0 para asignar a punteros nulos, al menos en C++. 6. LISTAS ABIERTAS. 6.1. DEFINICIÓN La forma más simple de estructura dinámica es la lista abierta. En esta forma los nodos se organizan de modo que cada uno apunta al siguiente, y el último no apunta a nada, es decir, el puntero del nodo siguiente vale NULL. En las listas abiertas existe un nodo especial: el primero. Normalmente diremos que nuestra lista es un puntero a ese primer nodo y llamaremos a ese nodo la cabeza de la lista. Eso es porque mediante ese único puntero podemos acceder a toda la lista. Cuando el puntero que usamos para acceder a la lista vale NULL, diremos que la lista está vacía. El nodo típico para construir listas tiene esta forma: struct nodo \{ int dato; struct nodo *siguiente; };

En el ejemplo, cada elemento de la lista sólo contiene un dato de tipo entero, pero en la práctica no hay límite en cuanto a la complejidad de los datos a almacenar. 6.2. DECLARACIONES DE TIPOS PARA MANEJAR LISTAS EN C++ Normalmente se definen varios tipos que facilitan el manejo de las listas, en C, la declaración de tipos puede tener una forma parecida a esta: typedef struct _nodo \{ int dato; struct _nodo *siguiente; } tipoNodo; typedef tipoNodo *pNodo; typedef tipoNodo *Lista;

tipoNodo es el tipo para declarar nodos, evidentemente. pNodo es el tipo para declarar punteros a un nodo. Lista es el tipo para declarar listas, como puede verse, un puntero a un nodo y una lista son la misma cosa. En realidad, cualquier puntero a un nodo es una lista, cuyo primer elemento es el nodo apuntado.

Lista enlazada

52

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

Es muy importante que nuestro programa nunca pierda el valor del puntero al primer elemento, ya que si no existe ninguna copia de ese valor, y se pierde, será imposible acceder al nodo y no podremos liberar el espacio de memoria que ocupa. 6.3. OPERACIONES BÁSICAS CON LISTAS Con las listas tendremos un pequeño repertorio de operaciones básicas que se pueden realizar:  Añadir o insertar elementos.  Buscar o localizar elementos.  Borrar elementos.  Moverse a través de una lista, anterior, siguiente, primero. Cada una de estas operaciones tendrá varios casos especiales, por ejemplo, no será lo mismo insertar un nodo en una lista vacía, o al principio de una lista no vacía, o la final, o en una posición intermedia. 6.4. INSERTAR ELEMENTOS EN UNA LISTA ABIERTA Veremos primero los casos sencillos y finalmente construiremos un algoritmo genérico para la inserción de elementos en una lista. 6.4.1. INSERTAR UN ELEMENTO EN UNA LISTA VACÍA Este es, evidentemente, el caso más sencillo. Partiremos de que ya tenemos el nodo a insertar y, por supuesto un puntero que apunte a él, además el puntero a la lista valdrá NULL:

Lista vacía

El proceso es muy simple, bastará con que: 1. nodo->siguiente apunte a NULL. 2. Lista apunte a nodo. 6.4.2. INSERTAR UN ELEMENTO EN LA PRIMERA POSICIÓN DE UNA LISTA

Insertar al principio

Podemos considerar el caso anterior como un caso particular de éste, la única diferencia es que en el caso anterior la lista es una lista vacía, pero siempre podemos, y debemos considerar una lista vacía como una lista. De nuevo partiremos de un nodo a insertar, con un puntero que apunte a él, y de una lista, en este caso no vacía:

53

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

Insertado al principio

El proceso sigue siendo muy sencillo: 1. Hacemos que nodo->siguiente apunte a Lista. 2. Hacemos que Lista apunte a nodo. 6.4.3. INSERTAR UN ELEMENTO EN LA ÚLTIMA POSICIÓN DE UNA LISTA Este es otro caso especial. Para este caso partiremos de una lista no vacía:

Insertar al final

El proceso en este caso tampoco es excesivamente complicado: 1. Necesitamos un puntero que señale al último elemento de la lista. La manera de conseguirlo es empezar por el primero y avanzar hasta que el nodo que tenga como siguiente el valor NULL. 2. Hacer que nodo->siguiente sea NULL. 3. Hacer que ultimo->siguiente sea nodo.

Insertado al final

6.4.4. INSERTAR UN ELEMENTO A CONTINUACIÓN DE UN NODO CUALQUIERA DE UNA LISTA De nuevo podemos considerar el caso anterior como un caso particular de este. Ahora el nodo "anterior" será aquel a continuación del cual insertaremos el nuevo nodo:

Insertar dentro

Suponemos que ya disponemos del nuevo nodo a insertar, apuntado por nodo, y un puntero al nodo a continuación del que lo insertaremos.

54

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

El proceso a seguir será: 1. Hacer que nodo->siguiente señale a anterior->siguiente. 2. Hacer que anterior->siguiente señale a nodo.

Insertado dentro

6.5. LOCALIZAR ELEMENTOS EN UNA LISTA ABIERTA Muy a menudo necesitaremos recorrer una lista, ya sea buscando un valor particular o un nodo concreto. Las listas abiertas sólo pueden recorrerse en un sentido, ya que cada nodo apunta al siguiente, pero no se puede obtener, por ejemplo, un puntero al nodo anterior desde un nodo cualquiera si no se empieza desde el principio. Para recorrer una lista procederemos siempre del mismo modo, usaremos un puntero auxiliar como índice: 1. Asignamos al puntero índice el valor de Lista. 2. Abriremos un bucle que al menos debe tener una condición, que el índice no sea NULL. 3. Dentro del bucle asignaremos al índice el valor del nodo siguiente al índice actual. Por ejemplo, para mostrar todos los valores de los nodos de una lista, podemos usar el siguiente bucle en C++: typedef struct _nodo \{ int dato; struct _nodo *siguiente; } tipoNodo; typedef tipoNodo *pNodo; typedef tipoNodo *Lista; ... pNodo indice; ... indice = Lista; while(indice) \{ printf("%d\n", indice->dato); indice = indice->siguiente; } ...

Supongamos que sólo queremos mostrar los valores hasta que encontremos uno que sea mayor que 100, podemos sustituir el bucle por: ... indice = Lista; while(indice && indice->dato <= 100) \{ printf("%d\n", indice->dato); indice = indice->siguiente;

55

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

} ...

Si analizamos la condición del bucle, tal vez encontremos un posible error: ¿Qué pasaría si ningún valor es mayor que 100, y alcancemos el final de la lista?. Podría pensarse que cuando indice sea NULL, si intentamos acceder a indice->dato se producirá un error. En general eso será cierto, no puede accederse a punteros nulos. Pero en este caso, ese acceso está dentro de una condición y forma parte de una expresión "and". Recordemos que cuando se evalúa una expresión "and", se comienza por la izquierda, y la evaluación se abandona cuando una de las expresiones resulta falsa, de modo que la expresión "indice->dato <= 100" nunca se evaluará si indice es NULL. Si hubiéramos escrito la condición al revés, el programa nunca funcionaría bien. Esto es algo muy importante cuando se trabaja con punteros. 6.6. ELIMINAR ELEMENTOS EN UNA LISTA ABIERTA De nuevo podemos encontrarnos con varios casos, según la posición del nodo a eliminar. 6.6.1. ELIMINAR EL PRIMER NODO DE UNA LISTA ABIERTA

Eliminar primer nodo

Es el caso más simple. Partiremos de una lista con uno o más nodos, y usaremos un puntero auxiliar, nodo: 1. Hacemos que nodo apunte al primer elemento de la lista, es decir a Lista. 2. Asignamos a Lista la dirección del segundo nodo de la lista: Lista->siguiente. 3. Liberamos la memoria asignada al primer nodo, el que queremos eliminar. Si no guardamos el puntero al primer nodo antes de actualizar Lista, después nos resultaría imposible liberar la memoria que ocupa. Si liberamos la memoria antes de actualizar Lista, perderemos el puntero al segundo nodo.

Primer nodo eliminado

Si la lista sólo tiene un nodo, el proceso es también válido, ya que el valor de Lista->siguiente es NULL, y después de eliminar el primer nodo la lista quedará vacía, y el valor de Lista será NULL. De hecho, el proceso que se suele usar para borrar listas completas es eliminar el primer nodo hasta que la lista esté vacía.

56

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

6.6.2. ELIMINAR UN NODO CUALQUIERA DE UNA LISTA ABIERTA En todos los demás casos, eliminar un nodo se puede hacer siempre del mismo modo. Supongamos que tenemos una lista con al menos dos elementos, y un puntero al nodo anterior al que queremos eliminar. Y un puntero auxiliar nodo.

Eliminar un nodo

El proceso es parecido al del caso anterior: 1. Hacemos que nodo apunte al nodo que queremos borrar. 2. Ahora, asignamos como nodo siguiente del nodo anterior, el siguiente al que queremos eliminar: anterior->siguiente = nodo->siguiente. 3. Eliminamos la memoria asociada al nodo que queremos eliminar.

Nodo eliminado

Si el nodo a eliminar es el último, es procedimiento es igualmente válido, ya que anterior pasará a ser el último, y anterior->siguiente valdrá NULL. 6.7. MOVERSE A TRAVÉS DE UNA LISTA ABIERTA Sólo hay un modo de moverse a través de una lista abierta, hacia delante. Aún así, a veces necesitaremos acceder a determinados elementos de una lista abierta. Veremos ahora como acceder a los más corrientes: el primero, el último, el siguiente y el anterior. 6.7.1. PRIMER ELEMENTO DE UNA LISTA El primer elemento es el más accesible, ya que es a ese a que apunta el puntero que define la lista. Para obtener un puntero al primer elemento bastará con copiar el puntero Lista. 6.7.2. ELEMENTO SIGUIENTE A UNO CUALQUIERA Supongamos que tenemos un puntero nodo que señala a un elemento de una lista. Para obtener un puntero al siguiente bastará con asignarle el campo "siguiente" del nodo, nodo>siguiente. 6.7.3. ELEMENTO ANTERIOR A UNO CUALQUIERA Ya hemos dicho que no es posible retroceder en una lista, de modo que para obtener un puntero al nodo anterior a uno dado tendremos que partir del primero, e ir avanzando hasta que el nodo siguiente sea precisamente nuestro nodo. 6.7.4. ÚLTIMO ELEMENTO DE UNA LISTA Para obtener un puntero al último elemento de una lista partiremos de un nodo cualquiera, por ejemplo el primero, y avanzaremos hasta que su nodo siguiente sea NULL.

57

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

6.7.5. SABER SI UNA LISTA ESTÁ VACÍA Basta con comparar el puntero Lista con NULL, si Lista vale NULL la lista está vacía. 6.8. BORRAR UNA LISTA COMPLETA El algoritmo genérico para borrar una lista completa consiste simplemente en borrar el primer elemento sucesivamente mientras la lista no esté vacía. 6.9. EJEMPLO DE LISTA ABIERTA ORDENADA EN C Supongamos que queremos construir una lista para almacenar números enteros, pero de modo que siempre esté ordenada de menor a mayor. Para hacer la prueba añadiremos los valores 20, 10, 40, 30. De este modo tendremos todos los casos posibles. Al comenzar, el primer elemento se introducirá en una lista vacía, el segundo se insertará en la primera posición, el tercero en la última, y el último en una posición intermedia. Insertar un elemento en una lista vacía es equivalente a insertarlo en la primera posición. De modo que no incluiremos una función para asignar un elemento en una lista vacía, y haremos que la función para insertar en la primera posición nos sirva para ese caso también. 6.9.1. ALGORITMO DE INSERCIÓN 1. El primer paso es crear un nodo para el dato que vamos a insertar. 2. Si Lista es NULL, o el valor del primer elemento de la lista es mayor que el del nuevo, insertaremos el nuevo nodo en la primera posición de la lista. 3. En caso contrario, buscaremos el lugar adecuado para la inserción, tenemos un puntero "anterior". Lo inicializamos con el valor de Lista, y avanzaremos mientras anterior>siguiente no sea NULL y el dato que contiene anterior->siguiente sea menor o igual que el dato que queremos insertar. 4. Ahora ya tenemos anterior señalando al nodo adecuado, así que insertamos el nuevo nodo a continuación de él. void Insertar(Lista *lista, int v) \{ pNodo nuevo, anterior; /* Crear un nodo nuevo */ nuevo = (pNodo)malloc(sizeof(tipoNodo)); nuevo->valor = v; /* Si la lista está vacía */ if(ListaVacia(*lista) || (*lista)->valor > v) \{ /* Añadimos la lista a continuación del nuevo nodo */ nuevo->siguiente = *lista; /* Ahora, el comienzo de nuestra lista es en nuevo nodo */ *lista = nuevo; } else \{ /* Buscar el nodo de valor menor a v */ anterior = *lista; /* Avanzamos hasta el último elemento o hasta que el siguiente tenga un valor mayor que v */ while(anterior->siguiente && anterior->siguiente->valor <= v) anterior = anterior->siguiente; /* Insertamos el nuevo nodo después del nodo anterior */

58

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

nuevo->siguiente = anterior->siguiente; anterior->siguiente = nuevo; } }

6.9.2. ALGORITMO PARA BORRAR UN ELEMENTO Después probaremos la función para buscar y borrar, borraremos los elementos 10, 15, 45, 30 y 40, así probaremos los casos de borrar el primero, el último y un caso intermedio o dos nodos que no existan. Recordemos que para eliminar un nodo necesitamos disponer de un puntero al nodo anterior. 1. Lo primero será localizar el nodo a eliminar, si es que existe. Pero sin perder el puntero al nodo anterior. Partiremos del nodo primero, y del valor NULL para anterior. Y avanzaremos mientras nodo no sea NULL o mientras que el valor almacenado en nodo sea menor que el que buscamos. 2. Ahora pueden darse tres casos: 3. Que el nodo sea NULL, esto indica que todos los valores almacenados en la lista son menores que el que buscamos y el nodo que buscamos no existe. Retornaremos sin borrar nada. 4. Que el valor almacenado en nodo sea mayor que el que buscamos, en ese caso también retornaremos sin borrar nada, ya que esto indica que el nodo que buscamos no existe. 5. Que el valor almacenado en el nodo sea igual al que buscamos. 6. De nuevo existen dos casos: 7. Que anterior sea NULL. Esto indicaría que el nodo que queremos borrar es el primero, así que modificamos el valor de Lista para que apunte al nodo siguiente al que queremos borrar. 8. Que anterior no sea NULL, el nodo no es el primero, así que asignamos a anterior>siguiente la dirección de nodo->siguiente. 9. Después de 7 u 8, liberamos la memoria de nodo. void Borrar(Lista *lista, int v) \{ pNodo anterior, nodo; nodo = *lista; anterior = NULL; while(nodo && nodo->valor < v) \{ anterior = nodo; nodo = nodo->siguiente; } if(!nodo || nodo->valor != v) return; else \{ /* Borrar el nodo */ if(!anterior) /* Primer elemento */ *lista = nodo->siguiente; else /* un elemento cualquiera */

59

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

anterior->siguiente = nodo->siguiente; free(nodo); } }

6.9.3. CODIGO COMPLETO #include #include typedef struct _nodo \{ int valor; struct _nodo *siguiente; } tipoNodo;

typedef tipoNodo *pNodo; typedef tipoNodo *Lista; /* Funciones con listas: */ void Insertar(Lista *l, int v); void Borrar(Lista *l, int v); int ListaVacia(Lista l); void BorrarLista(Lista *); void MostrarLista(Lista l); int main() \{ Lista lista = NULL; pNodo p; Insertar(&lista, Insertar(&lista, Insertar(&lista, Insertar(&lista,

20); 10); 40); 30);

MostrarLista(lista); Borrar(&lista, Borrar(&lista, Borrar(&lista, Borrar(&lista, Borrar(&lista,

10); 15); 45); 30); 40);

MostrarLista(lista); BorrarLista(&lista); getchar(); return 0; } void Insertar(Lista *lista, int v) \{

60

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

pNodo nuevo, anterior; /* Crear un nodo nuevo */ nuevo = (pNodo)malloc(sizeof(tipoNodo)); nuevo->valor = v; /* Si la lista está vacía */ if(ListaVacia(*lista) || (*lista)->valor > v) \{ /* Añadimos la lista a continuación del nuevo nodo */ nuevo->siguiente = *lista; /* Ahora, el comienzo de nuestra lista es en nuevo nodo */ *lista = nuevo; } else \{ /* Buscar el nodo de valor menor a v */ anterior = *lista; /* Avanzamos hasta el último elemento o hasta que el siguiente tenga un valor mayor que v */ while(anterior->siguiente && anterior->siguiente->valor <= v) anterior = anterior->siguiente; /* Insertamos el nuevo nodo después del nodo anterior */ nuevo->siguiente = anterior->siguiente; anterior->siguiente = nuevo; } } void Borrar(Lista *lista, int v) \{ pNodo anterior, nodo; nodo = *lista; anterior = NULL; while(nodo && nodo->valor < v) \{ anterior = nodo; nodo = nodo->siguiente; } if(!nodo || nodo->valor != v) return; else \{ /* Borrar el nodo */ if(!anterior) /* Primer elemento */ *lista = nodo->siguiente; else /* un elemento cualquiera */ anterior->siguiente = nodo->siguiente; free(nodo); } } int ListaVacia(Lista lista) \{ return (lista == NULL); } void BorrarLista(Lista *lista) \{ pNodo nodo; while(*lista) \{ nodo = *lista; *lista = nodo->siguiente; free(nodo);

61

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

} } void MostrarLista(Lista lista) \{ pNodo nodo = lista; if(ListaVacia(lista)) printf("Lista vacía\n"); else \{ while(nodo) \{ printf("%d -> ", nodo->valor); nodo = nodo->siguiente; } printf("\n"); } }

6.10. EJEMPLO DE LISTA ABIERTA EN C++ USANDO CLASES Usando clases el programa cambia bastante, aunque los algoritmos son los mismos. Para empezar, necesitaremos dos clases, una para nodo y otra para lista. Además la clase para nodo debe ser amiga de la clase lista, ya que ésta debe acceder a los miembros privados de nodo. class nodo \{ public: nodo(int v, nodo *sig = NULL) \{ valor = v; siguiente = sig; } private: int valor; nodo *siguiente; friend class lista; }; typedef nodo *pnodo; class lista \{ public: lista() \; } ~lista(); void Insertar(int v); void Borrar(int v); bool ListaVacia() \; } void Mostrar(); void Siguiente(); void Primero(); void Ultimo(); bool Actual() \; } int ValorActual() \ private:

62

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

pnodo primero; pnodo actual; };

Hemos hecho que la clase para lista sea algo más completa que la equivalente en C, aprovechando las prestaciones de las clases. En concreto, hemos añadido funciones para mantener un puntero a un elemento de la lista y para poder moverse a través de ella. Los algoritmos para insertar y borrar elementos son los mismos que expusimos para el ejemplo C, tan sólo cambia el modo de crear y destruir nodos. 6.11. CÓDIGO DEL EJEMPLO COMPLETO #include using namespace std; class nodo \{ public: nodo(int v, nodo *sig = NULL) \{ valor = v; siguiente = sig; } private: int valor; nodo *siguiente; friend class lista; }; typedef nodo *pnodo; class lista \{ public: lista() \; } ~lista(); void Insertar(int v); void Borrar(int v); bool ListaVacia() \; } void Mostrar(); void Siguiente() \ void Primero() \ void Ultimo() \ bool Actual() \; } int ValorActual() \ private: pnodo primero; pnodo actual; }; lista::~lista() \{

63

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

pnodo aux; while(primero) \{ aux = primero; primero = primero->siguiente; delete aux; } actual = NULL; } void lista::Insertar(int v) \{ pnodo anterior; // Si la lista está vacía if(ListaVacia() || primero->valor > v) \{ // Asignamos a lista un nuevo nodo de valor v y // cuyo siguiente elemento es la lista actual primero = new nodo(v, primero); } else \{ // Buscar el nodo de valor menor a v anterior = primero; // Avanzamos hasta el último elemento o hasta que el siguiente tenga // un valor mayor que v while(anterior->siguiente && anterior->siguiente->valor <= v) anterior = anterior->siguiente; // Creamos un nuevo nodo después del nodo anterior, y cuyo siguiente // es el siguiente del anterior anterior->siguiente = new nodo(v, anterior->siguiente); } } void lista::Borrar(int v) \{ pnodo anterior, nodo; nodo = primero; anterior = NULL; while(nodo && nodo->valor < v) \{ anterior = nodo; nodo = nodo->siguiente; } if(!nodo || nodo->valor != v) return; else \{ // Borrar el nodo if(!anterior) // Primer elemento primero = nodo->siguiente; else // un elemento cualquiera anterior->siguiente = nodo->siguiente; delete nodo; } } void lista::Mostrar() \{ nodo *aux; aux = primero; while(aux) \{

64

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

cout << aux->valor << "-> "; aux = aux->siguiente; } cout << endl; } int main() \{ lista Lista; Lista.Insertar(20); Lista.Insertar(10); Lista.Insertar(40); Lista.Insertar(30); Lista.Mostrar(); cout << "Lista de elementos:" << endl; Lista.Primero(); while(Lista.Actual()) \{ cout << Lista.ValorActual() << endl; Lista.Siguiente(); } Lista.Primero(); cout << "Primero: " << Lista.ValorActual() << endl; Lista.Ultimo(); cout << "Ultimo: " << Lista.ValorActual() << endl; Lista.Borrar(10); Lista.Borrar(15); Lista.Borrar(45); Lista.Borrar(30); Lista.Borrar(40); Lista.Mostrar(); cin.get(); return 0; }

7. PILAS 7.1. DEFINICIÓN Una pila es un tipo especial de lista abierta en la que sólo se pueden insertar y eliminar nodos en uno de los extremos de la lista. Estas operaciones se conocen como "push" y "pop", respectivamente "empujar" y "tirar". Además, las escrituras de datos siempre son inserciones de nodos, y las lecturas siempre eliminan el nodo leído. Estas características implican un comportamiento de lista LIFO (Last In First Out), el último en entrar es el primero en salir. El símil del que deriva el nombre de la estructura es una pila de platos. Sólo es posible añadir platos en la parte superior de la pila, y sólo pueden tomarse del mismo extremo. El nodo típico para construir pilas es el mismo que vimos en el capítulo anterior para la construcción de listas: struct nodo \{ int dato;

65

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

struct nodo *siguiente; };

7.2. DECLARACIONES DE TIPOS PARA MANEJAR PILAS EN C++ Los tipos que definiremos normalmente para manejar pilas serán casi los mismos que para manejar listas, tan sólo cambiaremos algunos nombres: typedef struct _nodo \{ int dato; struct _nodo *siguiente; } tipoNodo; typedef tipoNodo *pNodo; typedef tipoNodo *Pila;

tipoNodo es el tipo para declarar nodos, evidentemente. pNodo es el tipo para declarar punteros a un nodo. Pila es el tipo para declarar pilas.

Pila

Es evidente, a la vista del gráfico, que una pila es una lista abierta. Así que sigue siendo muy importante que nuestro programa nunca pierda el valor del puntero al primer elemento, igual que pasa con las listas abiertas. Teniendo en cuenta que las inserciones y borrados en una pila se hacen siempre en un extremo, lo que consideramos como el primer elemento de la lista es en realidad el último elemento de la pila. 7.3. OPERACIONES BÁSICAS CON PILAS Las pilas tienen un conjunto de operaciones muy limitado, sólo permiten las operaciones de "push" y "pop":  Push: Añadir un elemento al final de la pila.  Pop: Leer y eliminar un elemento del final de la pila. 7.4. PUSH, INSERTAR ELEMENTO Las operaciones con pilas son muy simples, no hay casos especiales, salvo que la pila esté vacía. 7.4.1. PUSH EN UNA PILA VACÍA Partiremos de que ya tenemos el nodo a insertar y, por supuesto un puntero que apunte a él, además el puntero a la pila valdrá NULL:

66

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

Push en vacía

El proceso es muy simple, bastará con que: 1. nodo->siguiente apunte a NULL. 2. Pila apunte a nodo. 7.4.2. PUSH EN UNA PILA NO VACÍA

Push en pila no vacía

Podemos considerar el caso anterior como un caso particular de éste, la única diferencia es que podemos y debemos trabajar con una pila vacía como con una pila normal. De nuevo partiremos de un nodo a insertar, con un puntero que apunte a él, y de una pila, en este caso no vacía:

Resultado

El proceso sigue siendo muy sencillo: 1. Hacemos que nodo->siguiente apunte a Pila. 2. Hacemos que Pila apunte a nodo. 7.5. POP, LEER Y ELIMINAR UN ELEMENTO

Pop

Ahora sólo existe un caso posible, ya que sólo podemos leer desde un extremo de la pila. Partiremos de una pila con uno o más nodos, y usaremos un puntero auxiliar, nodo:

Resultado

67

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

1. Hacemos que nodo apunte al primer elemento de la pila, es decir a Pila. 2. Asignamos a Pila la dirección del segundo nodo de la pila: Pila->siguiente. 3. Guardamos el contenido del nodo para devolverlo como retorno, recuerda que la operación pop equivale a leer y borrar. 4. Liberamos la memoria asignada al primer nodo, el que queremos eliminar. Si la pila sólo tiene un nodo, el proceso sigue siendo válido, ya que el valor de Pila->siguiente es NULL, y después de eliminar el último nodo la pila quedará vacía, y el valor de Pila será NULL. 7.6 EJEMPLO DE PILA EN C++ USANDO CLASES Al igual que pasaba con las listas, usando clases el programa cambia bastante. Las clases para pilas son versiones simplificadas de las mismas clases que usamos para listas. Para empezar, necesitaremos dos clases, una para nodo y otra para pila. Además la clase para nodo debe ser amiga de la clase pila, ya que ésta debe acceder a los miembros privados de nodo.

class nodo \{ public: nodo(int v, nodo *sig = NULL) \{ valor = v; siguiente = sig; } private: int valor; nodo *siguiente; friend class pila; }; typedef nodo *pnodo; class pila \{ public: pila() : ultimo(NULL) \{} ~pila(); void Push(int v); int Pop(); private: pnodo ultimo; };

68

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

7.6.1. CÓDIGO DEL EJEMPLO COMPLETO #include using namespace std; class nodo \{ public: nodo(int v, nodo *sig = NULL) \{ valor = v; siguiente = sig; } private: int valor; nodo *siguiente; friend class pila; }; typedef nodo *pnodo; class pila \{ public: pila() : ultimo(NULL) \{} ~pila(); void Push(int v); int Pop(); private: pnodo ultimo; }; pila::~pila() \{ while(ultimo) Pop(); } void pila::Push(int v) \{ pnodo nuevo; /* Crear un nodo nuevo */ nuevo = new nodo(v, ultimo); /* Ahora, el comienzo de nuestra pila es en nuevo nodo */ ultimo = nuevo; } int pila::Pop() \{ pnodo nodo; /* variable auxiliar para manipular nodo */ int v; /* variable auxiliar para retorno */ if(!ultimo) return 0; /* Si no hay nodos en la pila retornamos 0 */ /* Nodo apunta al primer elemento de la pila */ nodo = ultimo; /* Asignamos a pila toda la pila menos el primer elemento */

69

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

ultimo = nodo->siguiente; /* Guardamos el valor de retorno */ v = nodo->valor; /* Borrar el nodo */ delete nodo; return v; } int main() \{ pila Pila; Pila.Push(20); cout << "Push(20)" Pila.Push(10); cout << "Push(10)" cout << "Pop() = " Pila.Push(40); cout << "Push(40)" Pila.Push(30); cout << "Push(30)" cout << "Pop() = " cout << "Pop() = " Pila.Push(90); cout << "Push(90)" cout << "Pop() = " cout << "Pop() = "

<< endl; << endl; << Pila.Pop() << endl; << endl; << endl; << Pila.Pop() << endl; << Pila.Pop() << endl; << endl; << Pila.Pop() << endl; << Pila.Pop() << endl;

cin.get(); return 0; }

7.7 EJEMPLO DE PILA EN C++ USANDO PLANTILLAS Veremos ahora un ejemplo sencillo usando plantillas. Ya que la estructura para pilas es más sencilla que para listas abiertas, nuestro ejemplo también será más simple. Seguimos necesitando dos clases, una para nodo y otra para pila. Pero ahora podremos usar esas clases para construir listas de cualquier tipo de datos. 7.7.1. CÓDIGO DEL EJEMPLO COMPLETO Veremos primero las declaraciones de las dos clases que necesitamos: template class pila;

template class nodo \{ public: nodo(TIPO v, nodo<TIPO> *sig = NULL) \{ valor = v; siguiente = sig; } private: TIPO valor; nodo<TIPO> *siguiente;

70

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

friend class pila<TIPO>; }; template class pila \{ public: pila() : ultimo(NULL) \{} ~pila(); void Push(TIPO v); TIPO Pop(); private: nodo<TIPO> *ultimo; };

La implementación de las funciones es la misma que para el ejemplo de la página anterior. template pila<TIPO>::~pila() \{ while(ultimo) Pop(); } template void pila<TIPO>::Push(TIPO v) \{ nodo<TIPO> *nuevo; /* Crear un nodo nuevo */ nuevo = new nodo<TIPO>(v, ultimo); /* Ahora, el comienzo de nuestra pila es en nuevo nodo */ ultimo = nuevo; } template TIPO pila<TIPO>::Pop() \{ nodo<TIPO> *Nodo; /* variable auxiliar para manipular nodo */ TIPO v; /* variable auxiliar para retorno */ if(!ultimo) return 0; /* Si no hay nodos en la pila retornamos 0 */ /* Nodo apunta al primer elemento de la pila */ Nodo = ultimo; /* Asignamos a pila toda la pila menos el primer elemento */ ultimo = Nodo->siguiente; /* Guardamos el valor de retorno */ v = Nodo->valor; /* Borrar el nodo */ delete Nodo; return v; }

71

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

Eso es todo, ya sólo falta usar nuestras clases para un ejemplo práctico: #include #include "CCadena.h" using namespace std; template class pila; template class nodo \{ public: nodo(TIPO v, nodo<TIPO> *sig = NULL) \{ valor = v; siguiente = sig; } private: TIPO valor; nodo<TIPO> *siguiente; friend class pila<TIPO>; }; template class pila \{ public: pila() : ultimo(NULL) \{} ~pila(); void Push(TIPO v); TIPO Pop(); private: nodo<TIPO> *ultimo; }; template pila<TIPO>::~pila() \{ while(ultimo) Pop(); } template void pila<TIPO>::Push(TIPO v) \{ nodo<TIPO> *nuevo; /* Crear un nodo nuevo */ nuevo = new nodo<TIPO>(v, ultimo); /* Ahora, el comienzo de nuestra pila es en nuevo nodo */ ultimo = nuevo; } template TIPO pila<TIPO>::Pop() \{

72

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

nodo<TIPO> *Nodo; /* variable auxiliar para manipular nodo */ TIPO v; /* variable auxiliar para retorno */ if(!ultimo) return 0; /* Si no hay nodos en la pila retornamos 0 */ /* Nodo apunta al primer elemento de la pila */ Nodo = ultimo; /* Asignamos a pila toda la pila menos el primer elemento */ ultimo = Nodo->siguiente; /* Guardamos el valor de retorno */ v = Nodo->valor; /* Borrar el nodo */ delete Nodo; return v; } int main() \{ pila iPila; pila fPila; pila<double> dPila; pila cPila; pila sPila; // Prueba con iPila.Push(20); iPila.Push(10); cout << iPila.Pop() << ","; iPila.Push(40); iPila.Push(30); cout << iPila.Pop() cout << iPila.Pop() iPila.Push(90); cout << iPila.Pop() cout << iPila.Pop()

<< ","; << ","; << ","; << endl;

// Prueba con fPila.Push(20.01); fPila.Push(10.02); cout << fPila.Pop() << ","; fPila.Push(40.03); fPila.Push(30.04); cout << fPila.Pop() cout << fPila.Pop() fPila.Push(90.05); cout << fPila.Pop() cout << fPila.Pop()

<< ","; << ","; << ","; << endl;

// Prueba con <double> dPila.Push(0.0020); dPila.Push(0.0010); cout << dPila.Pop() << ","; dPila.Push(0.0040); dPila.Push(0.0030);

73

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

cout << dPila.Pop() cout << dPila.Pop() dPila.Push(0.0090); cout << dPila.Pop() cout << dPila.Pop()

<< ","; << ","; << ","; << endl;

// Prueba con cPila.Push('x'); cPila.Push('y'); cout << cPila.Pop() << ","; cPila.Push('a'); cPila.Push('b'); cout << cPila.Pop() cout << cPila.Pop() cPila.Push('m'); cout << cPila.Pop() cout << cPila.Pop()

<< ","; << ","; << ","; << endl;

// Prueba con sPila.Push("Hola"); sPila.Push("somos"); cout << sPila.Pop() << ","; sPila.Push("programadores"); sPila.Push("buenos"); cout << sPila.Pop() cout << sPila.Pop() sPila.Push("!!!!"); cout << sPila.Pop() cout << sPila.Pop()

<< ","; << ","; << ","; << endl;

cin.get(); return 0; }

8. COLAS 8.1. DEFINICIÓN Una cola es un tipo especial de lista abierta en la que sólo se pueden insertar nodos en uno de los extremos de la lista y sólo se pueden eliminar nodos en el otro. Además, como sucede con las pilas, las escrituras de datos siempre son inserciones de nodos, y las lecturas siempre eliminan el nodo leído. Este tipo de lista es conocido como lista FIFO (First In First Out), el primero en entrar es el primero en salir. El símil cotidiano es una cola para comprar, por ejemplo, las entradas del cine. Los nuevos compradores sólo pueden colocarse al final de la cola, y sólo el primero de la cola puede comprar la entrada. El nodo típico para construir pilas es el mismo que vimos en los capítulos anteriores para la construcción de listas y pilas:

74

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

struct nodo \{ int dato; struct nodo *siguiente; };

8.2. DECLARACIONES DE TIPOS PARA MANEJAR COLAS EN C++ Los tipos que definiremos normalmente para manejar colas serán casi los mismos que para manejar listas y pilas, tan sólo cambiaremos algunos nombres: typedef struct _nodo \{ int dato; struct _nodo *siguiente; } tipoNodo; typedef tipoNodo *pNodo; typedef tipoNodo *Cola;

tipoNodo es el tipo para declarar nodos, evidentemente. pNodo es el tipo para declarar punteros a un nodo. Cola es el tipo para declarar colas.

Cola

Es evidente, a la vista del gráfico, que una cola es una lista abierta. Así que sigue siendo muy importante que nuestro programa nunca pierda el valor del puntero al primer elemento, igual que pasa con las listas abiertas. Además, debido al funcionamiento de las colas, también deberemos mantener un puntero para el último elemento de la cola, que será el punto donde insertemos nuevos nodos. Teniendo en cuenta que las lecturas y escrituras en una cola se hacen siempre en extremos distintos, lo más fácil será insertar nodos por el final, a continuación del nodo que no tiene nodo siguiente, y leerlos desde el principio, hay que recordar que leer un nodo implica eliminarlo de la cola. 8.3. OPERACIONES BÁSICAS CON COLAS De nuevo nos encontramos ante una estructura con muy pocas operaciones disponibles. Las colas sólo permiten añadir y leer elementos:  Añadir: Inserta un elemento al final de la cola.  Leer: Lee y elimina un elemento del principio de la cola.

75

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

8.4. AÑADIR UN ELEMENTO Las operaciones con colas son muy sencillas, prácticamente no hay casos especiales, salvo que la cola esté vacía. 8.4.1. AÑADIR ELEMENTO EN UNA COLA VACÍA

Cola vacía

Partiremos de que ya tenemos el nodo a insertar y, por supuesto un puntero que apunte a él, además los punteros que definen la cola, primero y último que valdrán NULL:

Elemento encolado

El proceso es muy simple, bastará con que: 1. Hacer que nodo->siguiente apunte a NULL. 2. Que el puntero primero apunte a nodo. 3. Y que el puntero último también apunte a nodo. 8.4.2. AÑADIR ELEMENTO EN UNA COLA NO VACÍA

Cola no vacía

De nuevo partiremos de un nodo a insertar, con un puntero que apunte a él, y de una cola, en este caso, al no estar vacía, los punteros primero y último no serán nulos:

Elemento encolado

76

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

El proceso sigue siendo muy sencillo: 1. Hacemos que nodo->siguiente apunte a NULL. 2. Después que ultimo->siguiente apunte a nodo. 3. Y actualizamos último, haciendo que apunte a nodo. 8.4.3. AÑADIR ELEMENTO EN UNA COLA, CASO GENERAL Para generalizar el caso anterior, sólo necesitamos añadir una operación: 1. Hacemos que nodo->siguiente apunte a NULL. 2. Si ultimo no es NULL, hacemos que ultimo->siguiente apunte a nodo. 3. Y actualizamos último, haciendo que apunte a nodo. 4. Si primero es NULL, significa que la cola estaba vacía, así que haremos que primero apunte también a nodo. 8.5. LEER UN ELEMENTO DE UNA COLA, IMPLICA ELIMINARLO Ahora también existen dos casos, que la cola tenga un solo elemento o que tenga más de uno. 8.5.1. LEER UN ELEMENTO EN UNA COLA CON MÁS DE UN ELEMENTO Usaremos un puntero a un nodo auxiliar:

Cola con más de un elemento

1. Hacemos que nodo apunte al primer elemento de la cola, es decir a primero. 2. Asignamos a primero la dirección del segundo nodo de la pila: primero->siguiente. 3. Guardamos el contenido del nodo para devolverlo como retorno, recuerda que la operación de lectura en colas implican también borrar. 4. Liberamos la memoria asignada al primer nodo, el que queremos eliminar.

Elemento desencolado

77

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

8.5.2. LEER UN ELEMENTO EN UNA COLA CON UN SOLO ELEMENTO

Cola con un elemento

También necesitamos un puntero a un nodo auxiliar: 1. Hacemos que nodo apunte al primer elemento de la pila, es decir a primero.

Elemento desencolado

2. Asignamos NULL a primero, que es la dirección del segundo nodo teórico de la cola: primero>siguiente. 3. Guardamos el contenido del nodo para devolverlo como retorno, recuerda que la operación de lectura en colas implican también borrar. 4. Liberamos la memoria asignada al primer nodo, el que queremos eliminar. 5. Hacemos que ultimo apunte a NULL, ya que la lectura ha dejado la cola vacía. 8.5.3. LEER UN ELEMENTO EN UNA COLA CASO GENERAL 1. Hacemos que nodo apunte al primer elemento de la pila, es decir a primero. 2. Asignamos a primero la dirección del segundo nodo de la pila: primero->siguiente. 3. Guardamos el contenido del nodo para devolverlo como retorno, recuerda que la operación de lectura en colas implican también borrar. 4. Liberamos la memoria asignada al primer nodo, el que queremos eliminar. 5. Si primero es NULL, hacemos que ultimo también apunte a NULL, ya que la lectura ha dejado la cola vacía. 8.6 EJEMPLO DE COLA EN C++ USANDO CLASES Ya hemos visto que las colas son casos particulares de listas abiertas, pero más simples. Como en los casos anteriores, veremos ahora un ejemplo de cola usando clases. Para empezar, y como siempre, necesitaremos dos clases, una para nodo y otra para cola. Además la clase para nodo debe ser amiga de la clase cola, ya que ésta debe acceder a los miembros privados de nodo. class nodo \{ public: nodo(int v, nodo *sig = NULL) \{

78

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

valor = v; siguiente = sig; } private: int valor; nodo *siguiente; friend class cola; }; typedef nodo *pnodo; class cola \{ public: cola() : ultimo(NULL), primero(NULL) \{} cola(); void Anadir(int v); int Leer(); private: pnodo primero, ultimo; };

8.6.1. CÓDIGO DEL EJEMPLO COMPLETO #include using namespace std; class nodo \{ public: nodo(int v, nodo *sig = NULL) \{ valor = v; siguiente = sig; } private: int valor; nodo *siguiente; friend class cola; }; typedef nodo *pnodo; class cola \{ public: cola() : ultimo(NULL), primero(NULL) \{} ~cola(); void Push(int v);

79

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

int Pop(); private: pnodo ultimo; }; cola::~cola() \{ while(primero) Leer(); } void cola::Anadir(int v) \{ pnodo nuevo; /* Crear un nodo nuevo */ nuevo = new nodo(v); /* Si la cola no estaba vacía, añadimos el nuevo a continuación de ultimo */ if(ultimo) ultimo->siguiente = nuevo; /* Ahora, el último elemento de la cola es el nuevo nodo */ ultimo = nuevo; /* Si primero es NULL, la cola estaba vacía, ahora primero apuntará también al nuevo nodo */ if(!primero) primero = nuevo; } int cola::Leer() \{ pnodo nodo; /* variable auxiliar para manipular nodo */ int v; /* variable auxiliar para retorno */ /* Nodo apunta al primer elemento de la pila */ nodo = primero; if(!nodo) return 0; /* Si no hay nodos en la pila retornamos 0 */ /* Asignamos a primero la dirección del segundo nodo */ primero = nodo->siguiente; /* Guardamos el valor de retorno */ v = nodo->valor; /* Borrar el nodo */ delete nodo; /* Si la cola quedó vacía, ultimo debe ser NULL también*/ if(!primero) ultimo = NULL; return v; } int main() \{ cola Cola; Cola.Anadir(20); cout << "Añadir(20)" << endl; Cola.Anadir(10); cout << "Añadir(10)" << endl; cout << "Leer: " << Cola.Leer() << endl; Cola.Anadir(40); cout << "Añadir(40)" << endl; Cola.Anadir(30); cout << "Añadir(30)" << endl;

80

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

cout << "Leer: " << Cola.Leer() cout << "Leer: " << Cola.Leer() Cola.Anadir(90); cout << "Añadir(90)" << endl; cout << "Leer: " << Cola.Leer() cout << "Leer: " << Cola.Leer()

<< endl; << endl;

<< endl; << endl;

cin.get(); return 0; }

9. ARBOLES 9.1 DEFINICIÓN Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos. También se suele dar una definición recursiva: un árbol es una estructura en compuesta por un dato y varios árboles. Esto son definiciones simples. Pero las características que implican no lo son tanto.

Árbol

Definiremos varios conceptos. En relación con otros nodos:  Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol. En el ejemplo, 'L' y 'M' son hijos de 'G'.  Nodo padre: nodo que contiene un puntero al nodo actual. En el ejemplo, el nodo 'A' es padre de 'B', 'C' y 'D'. Los árboles con los que trabajaremos tienen otra característica importante: cada nodo sólo puede ser apuntado por otro nodo, es decir, cada nodo sólo tendrá un padre. Esto hace que estos árboles estén fuertemente jerarquizados, y es lo que en realidad les da la apariencia de árboles. En cuanto a la posición dentro del árbol:  Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para referirnos al árbol. En el ejemplo, ese nodo es el 'A'.  Nodo hoja: nodo que no tiene hijos. En el ejemplo hay varios: 'F', 'H', 'I', 'K', 'L', 'M', 'N' y 'O'.  Nodo rama: aunque esta definición apenas la usaremos, estos son los nodos que no pertenecen a ninguna de las dos categorías anteriores. En el ejemplo: 'B', 'C', 'D', 'E', 'G' y 'J'.

81

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

Otra característica que normalmente tendrán nuestros árboles es que todos los nodos contengan el mismo número de punteros, es decir, usaremos la misma estructura para todos los nodos del árbol. Esto hace que la estructura sea más sencilla, y por lo tanto también los programas para trabajar con ellos. Tampoco es necesario que todos los nodos hijos de un nodo concreto existan. Es decir, que pueden usarse todos, algunos o ninguno de los punteros de cada nodo. Un árbol en el que en cada nodo o bien todos o ninguno de los hijos existe, se llama árbol completo. En una cosa, los árboles se parecen al resto de las estructuras que hemos visto: dado un nodo cualquiera de la estructura, podemos considerarlo como una estructura independiente. Es decir, un nodo cualquiera puede ser considerado como la raíz de un árbol completo. Existen otros conceptos que definen las características del árbol, en relación a su tamaño: • Orden: es el número potencial de hijos que puede tener cada elemento de árbol. De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres será de orden tres, etc. • Grado: el número de hijos que tiene el elemento con más hijos dentro del árbol. En el árbol del ejemplo, el grado es tres, ya que tanto 'A' como 'D' tienen tres hijos, y no existen elementos con más de tres hijos. • Nivel: se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El nivel de la raíz es cero y el de sus hijos uno. Así sucesivamente. En el ejemplo, el nodo 'D' tiene nivel 1, el nodo 'G' tiene nivel 2, y el nodo 'N', nivel 3. • Altura: la altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol, también podemos hablar de altura de ramas. El árbol del ejemplo tiene altura 3, la rama 'B' tiene altura 2, la rama 'G' tiene altura 1, la 'H' cero, etc. Los árboles de orden dos son bastante especiales, de hecho les dedicaremos varios capítulos. Estos árboles se conocen también como árboles binarios. Frecuentemente, aunque tampoco es estrictamente necesario, para hacer más fácil moverse a través del árbol, añadiremos un puntero a cada nodo que apunte al nodo padre. De este modo podremos avanzar en dirección a la raíz, y no sólo hacia las hojas. Es importante conservar siempre el nodo raíz ya que es el nodo a partir del cual se desarrolla el árbol, si perdemos este nodo, perderemos el acceso a todo el árbol. El nodo típico de un árbol difiere de los nodos que hemos visto hasta ahora para listas, aunque sólo en el número de nodos. Veamos un ejemplo de nodo para crear árboles de orden tres: struct nodo \{ int dato; struct nodo *rama1; struct nodo *rama2; struct nodo *rama3; };

82

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

O generalizando más: #define ORDEN 5 struct nodo \{ int dato; struct nodo *rama[ORDEN]; };

9.2 DECLARACIONES DE TIPOS PARA MANEJAR ÁRBOLES EN C++ Para C++, y basándonos en la declaración de nodo que hemos visto más arriba, trabajaremos con los siguientes tipos: typedef struct _nodo \{ int dato; struct _nodo *rama[ORDEN]; } tipoNodo; typedef tipoNodo *pNodo; typedef tipoNodo *Arbol;

Al igual que hicimos con las listas que hemos visto hasta ahora, declaramos un tipo tipoNodo para declarar nodos, y un tipo pNodo para es el tipo para declarar punteros a un nodo. Árbol es el tipo para declarar árboles de orden ORDEN.

Árbol

El movimiento a través de árboles, salvo que implementemos punteros al nodo padre, será siempre partiendo del nodo raíz hacia un nodo hoja. Cada vez que lleguemos a un nuevo nodo podremos optar por cualquiera de los nodos a los que apunta para avanzar al siguiente nodo. En general, intentaremos que exista algún significado asociado a cada uno de los punteros dentro de cada nodo, los árboles que estamos viendo son abstractos, pero las aplicaciones no tienen por qué serlo. Un ejemplo de estructura en árbol es el sistema de directorios y ficheros de un sistema operativo. Aunque en este caso se trata de árboles con nodos de dos tipos, nodos directorio y nodos fichero, podríamos considerar que los nodos hoja son ficheros y los nodos rama son directorios. Otro ejemplo podría ser la tabla de contenido de un libro, por ejemplo de este mismo curso, dividido en capítulos, y cada uno de ellos en subcapítulos. Aunque el libro sea algo lineal, como

83

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

una lista, en el que cada capítulo sigue al anterior, también es posible acceder a cualquier punto de él a través de la tabla de contenido. También se suelen organizar en forma de árbol los organigramas de mando en empresas o en el ejército, y los árboles genealógicos. 9.3 OPERACIONES BÁSICAS CON ÁRBOLES Salvo que trabajemos con árboles especiales, como los que veremos más adelante, las inserciones serán siempre en punteros de nodos hoja o en punteros libres de nodos rama. Con estas estructuras no es tan fácil generalizar, ya que existen muchas variedades de árboles. De nuevo tenemos casi el mismo repertorio de operaciones de las que disponíamos con las listas:  Añadir o insertar elementos.  Buscar o localizar elementos.  Borrar elementos.  Moverse a través del árbol.  Recorrer el árbol completo. Los algoritmos de inserción y borrado dependen en gran medida del tipo de árbol que estemos implementando, de modo que por ahora los pasaremos por alto y nos centraremos más en el modo de recorrer árboles. 9.4 RECORRIDOS POR ÁRBOLES El modo evidente de moverse a través de las ramas de un árbol es siguiendo los punteros, del mismo modo en que nos movíamos a través de las listas. Esos recorridos dependen en gran medida del tipo y propósito del árbol, pero hay ciertos recorridos que usaremos frecuentemente. Se trata de aquellos recorridos que incluyen todo el árbol. Hay tres formas de recorrer un árbol completo, y las tres se suelen implementar mediante recursividad. En los tres casos se sigue siempre a partir de cada nodo todas las ramas una por una. Supongamos que tenemos un árbol de orden tres, y queremos recorrerlo por completo. Partiremos del nodo raíz: RecorrerArbol(raiz);

La función RecorrerArbol, aplicando recursividad, será tan sencilla como invocar de nuevo a la función RecorrerArbol para cada una de las ramas: void RecorrerArbol(Arbol a) \{ if(a == NULL) return; RecorrerArbol(a->rama[0]); RecorrerArbol(a->rama[1]); RecorrerArbol(a->rama[2]); }

84

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

Lo que diferencia los distintos métodos de recorrer el árbol no es el sistema de hacerlo, sino el momento que elegimos para procesar el valor de cada nodo con relación a los recorridos de cada una de las ramas.

Árbol

Los tres tipos son: 9.4.1. PRE-ORDEN En este tipo de recorrido, el valor del nodo se procesa antes de recorrer las ramas: void PreOrden(Arbol a) \{ if(a == NULL) return; Procesar(dato); RecorrerArbol(a->rama[0]); RecorrerArbol(a->rama[1]); RecorrerArbol(a->rama[2]); }

Si seguimos el árbol del ejemplo en pre-orden, y el proceso de los datos es sencillamente mostrarlos por pantalla, obtendremos algo así: ABEKFCGLMDHIJNO 9.4.2. IN-ORDEN En este tipo de recorrido, el valor del nodo se procesa después de recorrer la primera rama y antes de recorrer la última. Esto tiene más sentido en el caso de árboles binarios, y también cuando existen ORDEN-1 datos, en cuyo caso procesaremos cada dato entre el recorrido de cada dos ramas (este es el caso de los árboles-b): void InOrden(Arbol a) \{ if(a == NULL) return; RecorrerArbol(a->rama[0]); Procesar(dato); RecorrerArbol(a->rama[1]); RecorrerArbol(a->rama[2]);

85

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

}

Si seguimos el árbol del ejemplo en in-orden, y el proceso de los datos es sencillamente mostrarlos por pantalla, obtendremos algo así: KEBFALGMCHDINJO 9.4.3. POST-ORDEN En este tipo de recorrido, el valor del nodo se procesa después de recorrer todas las ramas: void PostOrden(Arbol a) \{ if(a == NULL) return; RecorrerArbol(a->rama[0]); RecorrerArbol(a->rama[1]); RecorrerArbol(a->rama[2]); Procesar(dato); }

Si seguimos el árbol del ejemplo en post-orden, y el proceso de los datos es sencillamente mostrarlos por pantalla, obtendremos algo así: KEFBLMGCHINOJDA 9.5 ELIMINAR NODOS EN UN ÁRBOL El proceso general es muy sencillo en este caso, pero con una importante limitación, sólo podemos borrar nodos hoja: El proceso sería el siguiente: 1. Buscar el nodo padre del que queremos eliminar. 2. Buscar el puntero del nodo padre que apunta al nodo que queremos borrar. 3. Liberar el nodo. 4. padre->nodo[i] = NULL;. Cuando el nodo a borrar no sea un nodo hoja, diremos que hacemos una "poda", y en ese caso eliminaremos el árbol cuya raíz es el nodo a borrar. Se trata de un procedimiento recursivo, aplicamos el recorrido Post-Orden, y el proceso será borrar el nodo. El procedimiento es similar al de borrado de un nodo: 1. Buscar el nodo padre del que queremos eliminar. 2. Buscar el puntero del nodo padre que apunta al nodo que queremos borrar. 3. Podar el árbol cuyo padre es nodo. 4. padre->nodo[i] = NULL;. En el árbol del ejemplo, para podar la rama 'B', recorreremos el subárbol 'B' en post-orden, eliminando cada nodo cuando se procese, de este modo no perdemos los punteros a las ramas apuntadas por cada nodo, ya que esas ramas se borrarán antes de eliminar el nodo. De modo que el orden en que se borrarán los nodos será: KEFyB

86

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

9.6 ÁRBOLES ORDENADOS A partir del siguiente capítulo sólo hablaremos de árboles ordenados, ya que son los que tienen más interés desde el punto de vista de TAD, y los que tienen más aplicaciones genéricas. Un árbol ordenado, en general, es aquel a partir del cual se puede obtener una secuencia ordenada siguiendo uno de los recorridos posibles del árbol: in-orden, pre-orden o post-orden. En estos árboles es importante que la secuencia se mantenga ordenada aunque se añadan o se eliminen nodos. Existen varios tipos de árboles ordenados, que veremos a continuación: • árboles binarios de búsqueda (ABB): son árboles de orden 2 que mantienen una secuencia ordenada si se recorren en in-orden. • árboles AVL: son árboles binarios de búsqueda equilibrados, es decir, los niveles de cada rama para cualquier nodo no difieren en más de 1. • árboles perfectamente equilibrados: son árboles binarios de búsqueda en los que el número de nodos de cada rama para cualquier nodo no difieren en más de 1. Son por lo tanto árboles AVL también. • árboles 2-3: son árboles de orden 3, que contienen dos claves en cada nodo y que están también equilibrados. También generan secuencias ordenadas al recorrerlos en in-orden. • árboles-B: caso general de árboles 2-3, que para un orden M, contienen M-1 claves. 10. ARBOLES BINARIOS DE BUSQUEDA 10.1 DEFINICIÓN Se trata de árboles de orden 2 en los que se cumple que para cada nodo, el valor de la clave de la raíz del subárbol izquierdo es menor que el valor de la clave del nodo y que el valor de la clave raíz del subárbol derecho es mayor que el valor de la clave del nodo.

Árbol binario de búsqueda

10.2 OPERACIONES EN ABB El repertorio de operaciones que se pueden realizar sobre un ABB es parecido al que realizábamos sobre otras estructuras de datos, más alguna otra propia de árboles:

87

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

Buscar un elemento. Insertar un elemento. Borrar un elemento. Movimientos a través del árbol:  Izquierda.  Derecha.  Raíz.  Información:  Comprobar si un árbol está vacío.  Calcular el número de nodos.  Comprobar si el nodo es hoja.  Calcular la altura de un nodo.  Calcular la altura de un árbol.    

10.3 BUSCAR UN ELEMENTO Partiendo siempre del nodo raíz, el modo de buscar un elemento se define de forma recursiva. • Si el árbol está vacío, terminamos la búsqueda: el elemento no está en el árbol. • Si el valor del nodo raíz es igual que el del elemento que buscamos, terminamos la búsqueda con éxito. • Si el valor del nodo raíz es mayor que el elemento que buscamos, continuaremos la búsqueda en el árbol izquierdo. • Si el valor del nodo raíz es menor que el elemento que buscamos, continuaremos la búsqueda en el árbol derecho. El valor de retorno de una función de búsqueda en un ABB puede ser un puntero al nodo encontrado, o NULL, si no se ha encontrado. 10.4 INSERTAR UN ELEMENTO Para insertar un elemento nos basamos en el algoritmo de búsqueda. Si el elemento está en el árbol no lo insertaremos. Si no lo está, lo insertaremos a continuación del último nodo visitado. Necesitamos un puntero auxiliar para conservar una referencia al padre del nodo raíz actual. El valor inicial para ese puntero es NULL.  Padre = NULL  nodo = Raíz  Bucle: mientras actual no sea un árbol vacío o hasta que se encuentre el elemento.  Si el valor del nodo raíz es mayor que el elemento que buscamos, continuaremos la búsqueda en el árbol izquierdo: Padre=nodo, nodo=nodo->izquierdo.  Si el valor del nodo raíz es menor que el elemento que buscamos, continuaremos la búsqueda en el árbol derecho: Padre=nodo, nodo=nodo->derecho.  Si nodo no es NULL, el elemento está en el árbol, por lo tanto salimos.  Si Padre es NULL, el árbol estaba vacío, por lo tanto, el nuevo árbol sólo contendrá el nuevo elemento, que será la raíz del árbol.

88

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

 Si el elemento es menor que el Padre, entonces insertamos el nuevo elemento como un nuevo árbol izquierdo de Padre.  Si el elemento es mayor que el Padre, entonces insertamos el nuevo elemento como un nuevo árbol derecho de Padre. Este modo de actuar asegura que el árbol sigue siendo ABB. 10.5 BORRAR UN ELEMENTO Para borrar un elemento también nos basamos en el algoritmo de búsqueda. Si el elemento no está en el árbol no lo podremos borrar. Si está, hay dos casos posibles: 1. Se trata de un nodo hoja: en ese caso lo borraremos directamente. 2. Se trata de un nodo rama: en ese caso no podemos eliminarlo, puesto que perderíamos todos los elementos del árbol de que el nodo actual es padre. En su lugar buscamos el nodo más a la izquierda del subárbol derecho, o el más a la derecha del subárbol izquierdo e intercambiamos sus valores. A continuación eliminamos el nodo hoja. Necesitamos un puntero auxiliar para conservar una referencia al padre del nodo raíz actual. El valor inicial para ese puntero es NULL.  Padre = NULL  Si el árbol está vacío: el elemento no está en el árbol, por lo tanto salimos sin eliminar ningún elemento.  Si el valor del nodo raíz es igual que el del elemento que buscamos, estamos ante uno de los siguientes casos:  El nodo raíz es un nodo hoja:  Si 'Padre' es NULL, el nodo raíz es el único del árbol, por lo tanto el puntero al árbol debe ser NULL.  Si raíz es la rama derecha de 'Padre', hacemos que esa rama apunte a NULL.  Si raíz es la rama izquierda de 'Padre', hacemos que esa rama apunte a NULL.  Eliminamos el nodo, y salimos.  El nodo no es un nodo hoja:  Buscamos el 'nodo' más a la izquierda del árbol derecho de raíz o el más a la derecha del árbol izquierdo. Hay que tener en cuenta que puede que sólo exista uno de esos árboles. Al mismo tiempo, actualizamos 'Padre' para que apunte al padre de 'nodo'.  Intercambiamos los elementos de los nodos raíz y 'nodo'.  Borramos el nodo 'nodo'. Esto significa volver a (1), ya que puede suceder que 'nodo' no sea un nodo hoja. (Ver ejemplo 3)  Si el valor del nodo raíz es mayor que el elemento que buscamos, continuaremos la búsqueda en el árbol izquierdo.  Si el valor del nodo raíz es menor que el elemento que buscamos, continuaremos la búsqueda en el árbol derecho.

89

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

EJEMPLO 1: BORRAR UN NODO HOJA En el árbol de ejemplo, borrar el nodo 3. 1. Localizamos el nodo a borrar, al tiempo que mantenemos un puntero a 'Padre'. 2. Hacemos que el puntero de 'Padre' que apuntaba a 'nodo', ahora apunte a NULL. 3. Borramos el 'nodo'.

Borrar un nodo hoja

EJEMPLO 2: BORRAR UN NODO RAMA CON INTERCAMBIO DE UN NODO HOJA. En el árbol de ejemplo, borrar el nodo 4. 1. Localizamos el nodo a borrar ('raíz'). 2. Buscamos el nodo más a la derecha del árbol izquierdo de 'raíz', en este caso el 3, al tiempo que mantenemos un puntero a 'Padre' a 'nodo'. 3. Intercambiamos los elementos 3 y 4. 4. Hacemos que el puntero de 'Padre' que apuntaba a 'nodo', ahora apunte a NULL. 5. Borramos el 'nodo'.

Borrar con intercambio de nodo hoja

EJEMPLO 3: BORRAR UN NODO RAMA CON INTERCAMBIO DE UN NODO RAMA. Para este ejemplo usaremos otro árbol. En éste borraremos el elemento 6.

90

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

Árbol binario de búsqueda

1. Localizamos el nodo a borrar ('raíz'). 2. Buscamos el nodo más a la izquierda del árbol derecho de 'raíz', en este caso el 12, ya que el árbol derecho no tiene nodos a su izquierda, si optamos por la rama izquierda, estaremos en un caso análogo. Al mismo tiempo que mantenemos un puntero a 'Padre' a 'nodo'. 3. Intercambiamos los elementos 6 y 12. 4. Ahora tenemos que repetir el bucle para el nodo 6 de nuevo, ya que no podemos eliminarlo.

Borrar con intercambio de nodo rama (1)

5. Localizamos de nuevo el nodo a borrar ('raíz'). 6. Buscamos el nodo más a la izquierda del árbol derecho de 'raíz', en este caso el 16, al mismo tiempo que mantenemos un puntero a 'Padre' a 'nodo'. 7. Intercambiamos los elementos 6 y 16. 8. Hacemos que el puntero de 'Padre' que apuntaba a 'nodo', ahora apunte a NULL. 9. Borramos el 'nodo'.

91

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

Borrar con intercambio de nodo rama (2)

Este modo de actuar asegura que el árbol sigue siendo ABB. 10.6 MOVIMIENTOS A TRAVÉS DEL ÁRBOL No hay mucho que contar. Nuestra estructura se referenciará siempre mediante un puntero al nodo Raíz, este puntero no debe perderse nunca. Para movernos a través del árbol usaremos punteros auxiliares, de modo que desde cualquier puntero los movimientos posibles serán: moverse al nodo raíz de la rama izquierda, moverse al nodo raíz de la rama derecha o moverse al nodo Raíz del árbol. 10.7 INFORMACIÓN Hay varios parámetros que podemos calcular o medir dentro de un árbol. Algunos de ellos nos darán idea de lo eficientemente que está organizado o el modo en que funciona. 10.7.1. COMPROBAR SI UN ÁRBOL ESTÁ VACÍO. Un árbol está vacío si su raíz es NULL. 10.7.2. CALCULAR EL NÚMERO DE NODOS. Tenemos dos opciones para hacer esto, una es llevar siempre la cuenta de nodos en el árbol al mismo tiempo que se añaden o eliminan elementos. La otra es, sencillamente, contarlos. Para contar los nodos podemos recurrir a cualquiera de los tres modos de recorrer el árbol: inorden, pre-orden o post-orden, como acción sencillamente incrementamos el contador. 10.7.3. COMPROBAR SI EL NODO ES HOJA. Esto es muy sencillo, basta con comprobar si tanto el árbol izquierdo como el derecho están vacíos. Si ambos lo están, se trata de un nodo hoja. 10.7.4. CALCULAR LA ALTURA DE UN NODO. No hay un modo directo de hacer esto, ya que no nos es posible recorrer el árbol en la dirección de la raíz. De modo que tendremos que recurrir a otra técnica para calcular la altura.

92

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

Lo que haremos es buscar el elemento del nodo de que queremos averiguar la altura. Cada vez que avancemos un nodo incrementamos la variable que contendrá la altura del nodo. • Empezamos con el nodo raíz apuntando a Raíz, y la 'Altura' igual a cero. • Si el valor del nodo raíz es igual que el del elemento que buscamos, terminamos la búsqueda y el valor de la altura es 'Altura'. • Incrementamos 'Altura'. • Si el valor del nodo raíz es mayor que el elemento que buscamos, continuaremos la búsqueda en el árbol izquierdo. • Si el valor del nodo raíz es menor que el elemento que buscamos, continuaremos la búsqueda en el árbol derecho. 10.7.5. CALCULAR LA ALTURA DE UN ÁRBOL. La altura del árbol es la altura del nodo de mayor altura. Para buscar este valor tendremos que recorrer todo el árbol, de nuevo es indiferente el tipo de recorrido que hagamos, cada vez que cambiemos de nivel incrementamos la variable que contiene la altura del nodo actual, cuando lleguemos a un nodo hoja compararemos su altura con la variable que contiene la altura del árbol si es mayor, actualizamos la altura del árbol. • Iniciamos un recorrido del árbol en postorden, con la variable de altura igual a cero. • Cada vez que empecemos a recorrer una nueva rama, incrementamos la altura para ese nodo. • Después de procesar las dos ramas, verificamos si la altura del nodo es mayor que la variable que almacena la altura actual del árbol, si es así, actualizamos esa variable. 10.8 ÁRBOLES DEGENERADOS Los árboles binarios de búsqueda tienen un gran inconveniente. Por ejemplo, supongamos que creamos un ABB a partir de una lista de valores ordenada: 2, 4, 5, 8, 9, 12 Difícilmente podremos llamar a la estructura resultante un árbol:

Árbol binario de búsqueda degenerado

93

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

Esto es lo que llamamos un árbol binario de búsqueda degenerado. 10.9. DECLARACIÓN DE CLASE ARBOL ABB Declaramos dos clases, una para nodo y otra para ArbolABB, la clase nodo la declararemos como parte de la clase ArbolABB, de modo que no tendremos que definir relaciones de amistad, y evitamos que otras clases o funciones tengan acceso a los datos internos de nodo. class ArbolABB \{ private: //// Clase local de Lista para Nodo de ArbolBinario: class Nodo \{ public: // Constructor: Nodo(const int dat, Nodo *izq=NULL, Nodo *der=NULL) : dato(dat), izquierdo(izq), derecho(der) \{} // Miembros: int dato; Nodo *izquierdo; Nodo *derecho; }; // Punteros de la lista, para cabeza y nodo actual: Nodo *raíz; Nodo *actual; int contador; int altura; public: // Constructor y destructor básicos: ArbolABB() : raíz(NULL), actual(NULL) \{} ~ArbolABB() \ // Insertar en árbol ordenado: void Insertar(const int dat); // Borrar un elemento del árbol: void Borrar(const int dat); // Función de búsqueda: bool Buscar(const int dat); // Comprobar si el árbol está vacío: bool Vacio(Nodo *r) \ // Comprobar si es un nodo hoja: bool EsHoja(Nodo *r) \ // Contar número de nodos: const int NumeroNodos(); const int AlturaArbol(); // Calcular altura de un int: int Altura(const int dat); // Devolver referencia al int del nodo actual: int &ValorActual() \

94

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

// Moverse al nodo raíz: void Raiz() \ // Aplicar una función a cada elemento del árbol: void InOrden(void (*func)(int&) , Nodo *nodo=NULL, bool r=true); void PreOrden(void (*func)(int&) , Nodo *nodo=NULL, bool r=true); void PostOrden(void (*func)(int&) , Nodo *nodo=NULL, bool r=true); private: // Funciones auxiliares void Podar(Nodo* &); void auxContador(Nodo*); void auxAltura(Nodo*, int); };

10.10. DEFINICIÓN DE LAS FUNCIONES MIEMBRO Las definiciones de la función miembro de la clase no difieren demasiado de las que creamos en C. Tan solo se han sustituido algunos punteros por referencias, y se usa el tipo bool cuando es aconsejable. Por ejemplo, en las funciones de recorrido de árboles, la función invocada acepta ahora una referencia a un entero, en lugar de un puntero a un entero. 11. GRAFOS 11.1. INTRODUCCIÓN El origen de la palabra grafo es griego y su significado etimológico es "trazar". Aparece con gran frecuencia como respuesta a problemas de la vida cotidiana, algunos ejemplos podrían ser los siguientes: un gráfico de una serie de tareas a realizar indicando su secuenciación (un organigrama), grafos matemáticos que representan las relaciones binarias, una red de carreteras, la red de enlaces ferroviarios o aéreos o la red eléctrica de una ciudad, (ver la figura 1). En cada caso es conveniente representar gráficamente el problema dibujando un grafo como un conjunto de puntos (nodos o vértices) con líneas conectándolos (arcos).

De aquí se podría deducir que un grafo es básicamente un objeto geométrico aunque en realidad sea un objeto combinatorio, es decir, un conjunto de puntos y un conjunto de líneas tomado de entre el conjunto de líneas que une cada par de vértices. Por otro lado, debido a su generalidad y

95

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

a la gran diversidad de formas que pueden usarse, resulta complejo tratar con todas las ideas relacionadas con un grafo. Para facilitar el estudio de este tipo de dato, a continuación se realizará un estudio de la teoría de grafos desde el punto de vista de las ciencias de la computación, considerando que dicha teoría es compleja y amplia, aquí sólo se realizará una introducción a la misma, describiéndose el grafo como un tipo de dato y mostrándose los problemas típicos y los algoritmos que permiten solucionarlos usando un ordenador. Los grafos son estructuras de datos no lineales que tienen una naturaleza generalmente dinámica, u estudio podría dividirse en dos grandes bloques; grafos dirigidos y grafos no dirigidos (pueden ser considerados un caso particular de los anteriores). Un ejemplo de grafo dirigido lo constituye la red de aguas de una ciudad ya que cada tubería sólo admite que el agua la recorra en un único sentido, por el contrario, la red de carreteras de un país representa en general un grafo no dirigido, puesto que una misma carretera puede ser recorrida en ambos sentidos. No obstante, podemos dar unas definiciones generales para ambos tipos. A continuación daremos definiciones de los dos tipos de grafos y de los conceptos que llevan asociados. 11.2. NOTACIÓN Y CONCEPTOS Un grafo G es un conjunto en el que hay definida una relación binaria, es decir, G = (V,A) tal que V es un conjunto de objetos a los que denominaremos vértices o nodos y A ⊆ V x V es una relación binaria a cuyos elementos denominaremos arcos o aristas. Dados x, y ∈ V, puede ocurrir que:  (x, y) 

(x, y)

∈ A, en cuyo caso diremos que x e y están unidos mediante un arco y, ∉ A, en cuyo caso diremos que no lo están.

Si las aristas tienen asociada una dirección (las aristas (x,y) y (y,x) no son equivalentes) diremos que el grafo es dirigido, en otro caso ((x,y)=(y,x)) diremos que el grafo es no dirigido.

96

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

VEAMOS ALGUNOS CONCEPTOS SOBRE GRAFOS:  Diremos que un grafo es completo si A=VxV, o sea, si para cualquier pareja de vértices existe una arista que los une(en ambos sentidos si el grafo es no dirigido).El número de aristas será: Para grafos dirigidos:

Para grafos no dirigidos:

Donde n=|V|.

 A también aparece la arista (y,  A implica que (y, x)  A.

 Un grafo dirigido es simétrico si para toda arista (x, y) x)

A y es anti simétrico si dada una arista (x, y)

 Tanto a las aristas como a los vértices les puede ser asociada información, a esta información se le llama etiqueta, si la etiqueta que se asocia es un número se le llama peso, costo o longitud, un grafo cuyas aristas o vértices tienen pesos asociados recibe el nombre de grafo etiquetado o ponderado.  El número de elementos de V se denomina orden del grafo, un grafo nulo es un grafo de orden cero.  Se dice que un vértice x es incidente a un vértice y si existe un arco que vaya de x a y ((x, y)  A), a “x” se le denomina origen del arco y a “y” extremo del mismo, de igual forma se dirá que y es adyacente a x, en el caso de que el grafo sea no dirigido si x es adyacente (resp. incidente) a y entonces y también es adyacente (resp. incidente) a x.  Se dice que dos arcos son adyacentes cuando tienen un vértice común que es a la vez origen de uno y extremo del otro.  Se denomina camino (algunos autores lo llaman cadena si se trata de un grafo no dirigido) en un grafo dirigido a una sucesión de arcos adyacentes:

97

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

C= {(v1,v2),(v2,v3),...,(vn-1,vn), vi  V}.  La longitud del camino es el número de arcos que comprende y en el caso en el que el grafo sea ponderado se calculará como la suma de los pesos de las aristas que lo constituyen.  Un camino se dice simple cuando todos sus arcos son distintos y se dice elemental cuando no utiliza un mismo vértice dos veces. Por tanto todo camino elemental es simple y el recíproco no es cierto.  Un camino se dice Euleriano si es simple y además contiene a todos los arcos del grafo.  Un circuito (o ciclo para grafos no dirigidos) es un camino en el que coinciden los vértices inicial y final, un circuito se dice simple cuando todos los arcos que lo forman son distintos y se dice elemental cuando todos los vértices por los que pasa son distintos. La longitud de un circuito es el número de arcos que lo componen. Un bucle es un circuito de longitud 1 (están permitidos los arcos de la forma (i, i) y notemos que un grafo anti simétrico carecería de ellos).  Un circuito elemental que incluye a todos los vértices de un grafo lo llamaremos circuito Hamiltoniano.  Un grafo se denomina simple si no tiene bucles y no existe más que un camino para unir dos nodos.  Diremos que un grafo no dirigido es bipartido si el conjunto de sus vértices puede ser dividido en dos subconjuntos (disjuntos) de tal forma que cualquiera de las aristas que componen el grafo tiene cada uno de sus extremos en un subconjunto distinto, un grafo no dirigido será bipartido si y sólo si no contiene ciclos con un número de aristas par.  Dado un grafo G=(V,A),diremos que G'=(V,A' ) con A' ⊂ A es un grafo parcial de G y un subgráfo de G es todo grafo G'=(V',A') con V' ⊆ V y A' ⊆ A donde A' será el conjunto de todas aquellas aristas que unían en el grafo G dos vértices que están en V ', se podrían combinar ambas definiciones dando lugar a lo que llamaremos subgráfo parcial .

98

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

 Se denomina grado de entrada de un vértice x al número de arcos incidentes en él, se denota

δe (x).

 Se denomina grado de salida de un vértice x al número de arcos adyacentes a él, se denota δs (x).  Para grafos no dirigidos tanto el grado de entrada como el de salida coinciden y hablamos entonces de grado y lo notamos por δ (x).  A todo grafo no dirigido se puede asociar un grafo denominado dual construido de la siguiente forma: G (V, A) ------> G' (V', A' ) Donde A' está construido de la siguiente forma: si e1,e2 ∈ a A son adyacentes --> (e1,e2) ∈a A' con e1,e2 ∈a V', en definitiva, para construir un grafo dual se cambian vértices por aristas y viceversa.

99

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

 Dado un grafo G, diremos que dos vértices están conectados si entre ambos existe un camino que los une.  Llamaremos componente conexa a un conjunto de vértices de un grafo tal que entre cada par de vértices hay al menos un camino y si se añade algún otro vértice esta condición deja de verificarse. Matemáticamente se puede ver como que la conexión es una relación de equivalencia que descompone a V en clases de equivalencia, cada uno de los subgráfos a los que da lugar cada una de esas clases de equivalencia constituiría una componente conexa. Un grafo diremos que es conexo si sólo existe una componente conexa que coincide con todo el grafo.

11.3. BÚSQUEDA DE CAMINOS MÍNIMOS EN GRAFOS Supongamos que tenemos un grafo dirigido sencillo etiquetado G = {V, A} de grado n, V = {1,..., n} y con etiquetas en los arcos no negativas. 11.3.1. ENTRE UN VÉRTICE Y TODOS LOS DEMÁS VÉRTICES DEL GRAFO Nos planteamos el problema de dado un vértice determinar el camino de costo mínimo de ese vértice a todos los demás vértices de V. Para resolver el problema aplicaremos un algoritmo debido a Dijkstra que esencialmente era a partir de un conjunto S de vértices (S V) cuya distancia más corta desde el origen es conocida y en cada paso se agrega un nuevo vértice v a S cuya distancia a su vez desde el origen sea la más corta posible. Si la suposición que hacíamos de que las etiquetas son siempre no negativas se cumple, puede comprobarse que siempre es posible encontrar un camino más corto desde el origen y un vértice v que sólo pase a través de los vértices de S (camino "inherente"). Si se utiliza además un vector D donde se almacena las longitudes de los caminos inherentes más cortos a cada vértice, una vez que S incluya a todos los vértices, todos los caminos son inherentes de forma que D contendrá la distancia más corta del origen a cada vértice. Notación:  Origen = vértice 1 (obviamente esto no es una condición)  Sea S un vector de n componentes representando el conjunto de vértices cuya distancia más corta desde el origen ya es conocida.  D es un vector de n componentes donde D [i] indica en cada paso la distancia más corta entre el origen y el vértice i: a. bien mediante el camino directo si existe el arco (i,j).

100

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

b. bien a través de los vértices de S (de los que se conoce su distancia más corta al origen), Al final D contendrá el costo del camino mínimo entre el origen y cada vértice.  C es la matriz de costos del grafo. C [1,i] representa el costo del arco (1,i). Si el arco no existe, se le asigna un valor fuera de rango (∞)  P es un vector de dimensión n a través del cual reconstruiremos el camino más corto del origen al resto de los vértices. Así P[i] contiene el vértice inmediato anterior a i en el camino más corto. Inicialmente es evidente que S = {1} y i D[i] = C[1 i] con P[i] = 1 Con estas premisas el algoritmo de Dijkstra se puede esquematizar así: Algoritmo Dijkstra () 1. S = {1} 2. for (i = 2; i<=n; i++ ) { D[i] = C[I,i] P[i] = 1 } 3. while ( S ≠ V ) { elegir w ∈ V-S / D[w] sea mínimo S= S U{w} for (cada vértice v V -S) if (D[v] > D[w] + C[w, v]) { D[v] = D[w] + C[w, v] P[v] = w } }

Veamos un ejemplo del algoritmo, supongamos que queremos encontrar los caminos mínimos del vértice 1 al resto en el grafo siguiente:

101

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

En principio: 

S= {1}



D [2] = 60; D [3] = 10; D [4] = 100; D [5] = ∞



P[i] = 1 ∀i

ITERACIÓN 1: V -S = {2,3,4,5} w = 3 -> S = {1,3} -> V -S = {2,4,5} D [2] = min(D [2] , D [3] + C [3,2]) = min(60, 50) = 50 -> P [2] = 3 D [4] = min(D [4] , D [3] + C [3,4]) = min(100, 40) = 40 -> P [4] = 3 D [5] = min(D [5] , D [3] + C [3,5]) = min (∞,∞) = ∞ Así D [2] = 50; D [4] = 40; D [5] = 00; P [2] = 3; P [4] = 3; P [5] = 1 ITERACIÓN 2: V -S = {2,4,5} w = 4 -> S = {1,3,4} -> V- S = {2,5} D [2] = min(D [2] , D [4] + C [4,2]) = min(50, 00) = 50 -> P [2] = 3 D [5] = min(D [5] , D [4] + C [4,5]) = min( 00,60) = 60 -> P [5] = 4 Así D [2] = 50; D [5] = 60; p [2] = 3; P [5] = 4

102

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

ITERACIÓN 3: V -S = {2,5} w = 2 -> S = {1,3,4,2} -> V- S = {5} D [5] = min(D [5] , D[2] + C [2,5]) = min(60, 55) = 55 -> P [5] = 2 Así D [5] = 55; P[5] = 2 Finalmente w = 5 -> S = {1,3,4,2,5} -> FIN DEL ALGORITMO Para reconstruir el camino más corto del origen a cada vértice, se asignan los predecesores en orden inverso. Por ejemplo, si se quiere conocer el camino desde el origen al vértice S, se, tiene que: P [5] = 2-+ P [2] = 3-+ P [3] = 1 siendo por tanto el camino (1,3,2,5) con costo 55 . Aunque la implementación de este algoritmo es simple si la realizamos en base a una matriz de adyacencia, en la práctica se utiliza normalmente una implementación en base a listas de adyacencia. La razón de esta elección es que en la primera la eficiencia es O(n2) para cualquier grafo; sin embargo la mayoría de los grafos que nos encontramos en la práctica tiene un número de aristas bastante pequeño (grafos que podemos denominar dispersos o no densos ) y por tanto el uso de listas de adyacencia se presenta como una solución más eficiente. Para conseguir una mejor eficiencia en esta implementación del algoritmo de Dijkstra se ha echado mano de una estructura de datos formada por un APO que tiene como etiqueta los vértices del grafo y como clave el coste de ir desde el vértice inicial en el problema a ese vértice de tal forma que obtener el vértice con mínimo coste sería O(log n). 11.3.2. ENTRE CADA PAR DE VÉRTICES DEL GRAFO En lugar de buscar los caminos mínimos de un vértice a los demás nos podemos plantear buscar el camino más corto entre cualquier pareja de vértices, es decir, dado un grafo dirigido etiquetado G = {V, A} en el que las etiquetas son no negativas encontrar el camino de longitud " más corta entre dos vértices cualesquiera de ese grafo. Podría pensarse, para resolver el problema, en aplicar el algoritmo de Dijkstra n veces, una por vértice, pero en lugar de eso, aplicaremos un nuevo algoritmo creado por Floyd que va encontrando los caminos de forma iterativa. NOTACIÓN: 

V = {1, ..., n} conjunto de vértices.

103

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE



A es una matriz de tamaño n x n en la que se calculará en cada Aij la longitud más corta del camino que va de i a j.



P es una matriz de tamaño n x n que utilizaremos para recuperar los caminos más cortos.



C es una matriz de dimensión n x n conteniendo los costos de los arcos. Si no existe arco de un vértice i a otro j el correspondiente valor C [i,j] = ∞.

Inicialmente A [i,j] = { C[i,j] si i ≠ j, 0 si i = j }. A continuación se itera sobre A n veces de forma que tras hacer la k iteración A[i,j] tiene un valor correspondiente a la longitud más pequeña de cualquier camino de i a j que no pase por un vértice de índice mayor que k, es decir, cualquier vértice intermedio entre i y j (extremos del camino) ha de ser menor o igual que k. Por tanto en cada iteración k se usará la siguiente fórmula: Ak [i,j] = min(Ak-1 [i,j] ,Ak-1 [i,k] +Ak-1l [k,j])3 Es decir, cada Ak [i,j] se obtiene comparando Ak-1 [i,j], el coste de ir de i a j sin pasar por k o cualquier vértice de índice mayor, con Ak-1 [i,k] +Ak-1 [k,j], el costo de ir primero de i a k y después de k a j sin pasar por un vértice de índice mayor que k de forma que si el paso por el vértice k produce un camino i más corto que el indicado por Ak-1 [i,j], se elige ese coste para Ak [i,j] .Así mismo, cada iteración P [i,j] contendrá el vértice k que permitió al algoritmo de Floyd encontrar el valor más pequeño de A[i, j] .Inicialmente P[i,j] = 0, puesto que inicialmente el camino más corto de i a j es el propio arco. El algoritmo sería el siguiente: Algoritmo Floyd () 1. for (i = 1; i <= n; i++ ) for (j = 1; j <=n ; j++) { A[i, j]= C[i, j] P[i, j]= 0 } 2. for (i = 1; i <= n; i++) A[i, i]= 0 3. for (k = 1; k <= n; k++) for (i = 1; i <= n; i++)

104

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

for (j = l; j <=n ; j++) if ((i ≠ j) && (A[i,k]+A[k,j] < A[i, j])) { A[i, j]= A[i, k]+A[k, j] P[i, j]= k } Algoritmo recuperar_camino (i, j de tipo vértice) 1. k= P[i, j] 2. if (k ≠ 0) { recuperar_camino (i, k) escribir (k) recuperar_camino (k, j) } Por ejemplo, el camino más corto entre los vértices 2 y 4 se determinaría llamando a: recuperar-camino (2,4) k = 3 -> recuperar-camino (2,3) -> 0 [3] recuperar-camino (3,4) -> k = 1 -> recuperar-camino (3,1) -> 0 [1] recuperar-camino (1,4) -> 0 con la que el camino es (2,3,1,4) con costo 12. 11.4. PRIMITIVAS DEL GRAFO Dentro del TDA Grafo hemos propuesto las siguientes primitivas: 

Grafo ( ) -> constructor del grafo, reserva los recursos e inicializa el grafo a vacío.

Nodo LocalizaLabel (const Tbase e) -> localiza la etiqueta, devuelve el nodo asociado a la etiqueta e. PARÁMETROS: e -> etiqueta asociada al nodo a encontrar. 

Bool ExisteArco (nodo o, nodo d) -> nos dice si existe un arco, devuelve true si existe el arco o false en otro caso. PARÁMETROS: o -> nodo origen del arco. d -> nodo destino del arco. 

105

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE



Int GrafoVacio () -> devuelve 0 si el grafo esta vacio, si no devuelve 1 en otro caso.

Float EtiqArco (nodo o, nodo d) -> devuelve la etiqueta asociada a un arco, es decir el peso del arco. PARÁMETROS: o -> nodo origen del arco. d -> nodo destino del arco. 

Void InsertarNodo (const Tbase dato) -> inserta un nodo nuevo en el grafo. PARÁMETROS: dato -> etiqueta del nuevo nodo. 

Void InsertarArco (nodo o, nodo d, int valor) -> inserta un arco entre el nodo o y el d, asociado al arco le podemos dar un valor o peso. PARÁMETROS: o -> nodo origen del arco. d -> nodo destino del arco. valor -> peso del del arco. 

Void BorrarArco (nodo o, nodo d) -> borra el arco existente entre los nodos o y d. PARÁMETROS: o -> nodo origen del arco. d -> nodo destino del arco. 

Void DesconectarNodo (nodo a_eliminar) -> elimina un nodo del grafo receptor, todos los arcos que entran o salen del nodo a eliminar tambien desaparecen. PARÁMETROS: a_eliminar -> nodo a eliminar del grafo.  Void CopiarGrafo (Grafo gr) -> copia el grafo gr en el receptor. PARÁMETROS: gr -> grafo a copiar. 



~Grafo () -> destructor, destruye el grado liberando todos los recursos.

11.5. EJEMPLOS DE USO IMPRIMIR UN GRAFO Esta función nos imprime en pantalla el contenido de un grafo con etiquetas enteras. Grafo g; Void Imprimir () { nodo n1, n2; arco a; int cont = 1; printf (“Arcos : \n”); for (n1=g.inicio; n1 != 0; n = n->sig) { if (n1->etiqueta != 0) { for (a = n1->ady; a != 0; a = a->sig)

106

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

{ n2 = a->destino; printf (“%3d -> %3d (%d)”, n1->etiqueta, n2->etiqueta, a->valor); } if (cont % 4) printf (“,”); else printf (“ \n ”); cont++; } } if ((cont % 4) != 0) printf (“ \n ”); }

11.6. IMPLEMENTACIÓN DEL GRAFO Existen diversas representaciones de naturaleza muy diferente que resultan adecuadas para manejar un grafo,y en la mayoría de los casos no se puede decir que una sea mejor que otra siempre ya que cada una puede resultar más adecuada dependiendo del problema concreto al que se desea aplicar, así,si existe una representación que es peor que otra para todas las operaciones excepto una es posible que aún así nos decantemos por la primera porque precisamente esa operación es la única en la que tenemos especial interés en que se realice de forma eficiente. A continuación veremos dos de las representaciones más usuales: 11.6.1. MATRIZ DE ADYACENCIA GRAFOS DIRIGIDOS G=(V,A) un grafo dirigido con |V|=n .Se define la matriz de adyacencia o booleana asociada a G como Bnxn con : b i,j = { 1 si (i,j)  A, 0 en otro caso } Como se puede ver se asocia cada fila y cada columna a un vértice y los elementos bi,j de la matriz son 1 si existe el arco (i,j) y 0 en caso contrario. GRAFOS NO DIRIGIDOS G=(V,A) un grafo no dirigido con |V|=n .Se define la matriz de adyacencia o booleana asociada a G como Bnxn con: b i,i = { 1 si (i,j) A, 0 en otro caso } La matriz B es simétrica con 1 en las posiciones ij y ji si existe la arista (i,j).

107

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

Veamos ahora un ejemplo:

Si el grafo es etiquetado, entonces tanto bi,j como bi,j representan al coste o valor asociado al arco (i,j) y se suelen denominar matrices de coste. Si el arco (i,j) no pertenece a A entonces se asigna bi,j o bi,j un valor que no puede ser utilizado como una etiqueta valida. La principal ventaja de la matriz de adyacencia es que el orden de eficiencia de las operaciones de obtención de etiqueta de un arco o ver si dos vértices están conectados son independientes del número de vértices y de arcos, por el contrario, existen dos grandes inconvenientes: 

Es una representación orientada hacia grafos que no modifica el número de sus vértices ya que una matriz no permite que se le o supriman filas o columnas.



Se puede producir un gran derroche de memoria en grafos poco densos (con gran número de vértices y escaso número de arcos).

Para evitar estos inconvenientes se introduce otra representación: las listas de adyacencia. 11.6.2. LISTA DE ADYACENCIA En esta estructura de datos la idea es asociar a cada vértice i del grafo una lista que contenga todos aquellos vértices j que sean adyacentes a él. De esta forma sólo reservará memoria para los arcos adyacentes a i y no para todos los posibles arcos que pudieran tener como origen i, el grafo, por tanto, se representa por medio de un vector de n componentes (si |V|=n) donde cada componente va a ser una lista de adyacencia correspondiente a cada uno de los vértices del grafo. Cada elemento de la lista consta de un campo indicando el vértice adyacente. En caso de que el grafo sea etiquetado, habrá que añadir un segundo campo para mostrar el valor de la etiqueta.

108

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

Veamos un ejemplo a continuación:

Esta representación requiere un espacio proporcional a la suma del número de vértices, más el número de arcos, y se suele usar cuando el número de arcos es mucho menor que el número de arcos de un grafo completo. Una desventaja es que puede llevar un tiempo O(n) determinar si existe un arco del vértice i al vértice j, ya que puede haber n vértices en la lista de adyacencia asociada al vértice i. Mediante el uso del vector de listas de adyacencias sólo se reserva memoria para los arcos existentes en el grafo con el consiguiente ahorro de la misma, sin embargo, no permite que haya vértices que puedan ser añadidos o suprimidos del grafo, debido a que la dimensión del grafo debe ser predeterminado y fija. Para solucionar esto se puede usar una lista de listas de adyacencia, sólo los vértices del grafo que sean origen de algún arco aparecerán en la lista, de esta forma se pueden añadir y suprimir arcos sin desperdicio de memoria ya que simplemente habrá que modificar la lista de listas para reflejar los cambios.

109

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

Como puede verse en el ejemplo de las figuras anteriores tanto el vector de listas de adyacencias como en la lista de listas se ha razonado en función de los vértices que actúan como orígenes de los arcos. Análogamente se podía haber hecho con los vértices destino, y combinando ambas representaciones podría pensarse en utilizar dos vectores de listas de adyacencia o dos listas de listas de adyacencia. Nuestra implementación es con listas de adyacencia donde sólo usamos los arcos adyacentes y no los incidentes, es una simplificación considerable ya que no tenemos mucho tiempo. Usamos una estructura nodo que simula lo que sería un vértice o nodo del grafo, contiene un elemento de tipo Tbase que es la etiqueta, un entero nodo que identifica unívocamente al nodo, un puntero sig al siguiente nodo de la lista y un puntero ady a la lista de adyacencia del nodo en cuestión. Podría tener como hemos comentado antes un puntero a la lista de arcos incidentes pero hemos simplificado el problema. También tenemos otra estructura para simular el comportamiento de un arco o arista del grafo, esta estructura tiene un valor que es el peso que tiene el arco tratado, un puntero sig al siguiente arco de la lista, un puntero al nodo origen del arco y otro al destino del mismo. El grafo se compone de un nodo inicio que es el primer nodo del grafo, del cual cuelgan el resto de los nodos y del nnodos que nos da el número de nodos del grafo. Para el grafo de la siguiente figura:

La representación según nuestra implementación sería:

110

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

Vamos a ver la especificación tanto de la función de abstracción como del invariante de la representación del grafo: FUNCIÓN DE ABSTRACCIÓN Dado el objeto del tipo rep r, r = {inicio, nnodos}, el objeto abstracto al que representa es: g = < r.inicio, r.inicio->sig, r.inicio->sig->sig ..., r.inicio->sig... nnodos...->sig > INVARIANTE DE REPRESENTACIÓN 0 <= r.nnodos < 5 De manera que la clase Grafo en C++ tendría el siguiente aspecto: Class Grafo { Public: struct nodo { Tbase etiqueta; int nodo; struct nodo *sig; struct arco *ady;

111

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

} struct arco { int valor; struct nodo *origen; struct nodo *destino; struct arco *sig; } struct nodo *inicio; int nnodos; Grafo (); nodo LocalizaLabel (const Tbase e); bool ExisteArco (nodo o, nodo d); int GrafoVacio (); float EtiqArco (nodo o, nodo d); void InsertarNodo (const Tbase dato); void InsertarArco (nodo o, nodo d, int valor); void BorrarArco (nodo o, nodo d); void DesconectarNodo (nodo a_eliminar); void CopiarGrafo (Grafo gr); ~Grafo(); }

Debemos aclarar un par de cosas sobre la implementación en C++; sólo tenemos miembros públicos para facilitar el acceso a los mismos de forma rápido, aunque esta no sea la filosofía más apropiada tratándose de un lenguaje con orientación a objetos, esto se ha hecho así para simplificar en gran medida tanto las primitivas como el código asociado a ellas ya que en la confección de este tutorial no hemos tenido tiempo suficiente para hacer una clase Grafo como dios manda. Si se quiere hacer una clase grafo donde tengamos miembros privados como inicio y nnodos, debemos elaborar primitivas que nos devuelvan cada elemento de una estructura nodo y arco en este caso, serían muchas primitivas pequeñas, luego el resto (las que hemos elegido aquí) habría que modificarlas en base a las nuevas primitivas elaboradas. Pasemos ahora a ver la implementación de cada una de las primitivas enunciadas con anterioridad en C++: CODIGO EN C++ template Grafo::Grafo() { inicio = new nodo;

112

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

inicio->etiqueta = 0; inicio->nodo = 1; inicio->ady = 0; inicio->sig = 0; } template nodo Grafo::LocalizaLabel(const Tbase e) { nodo n; int enc=0; for (n=this.inicio; n!=0 && !enc; ) { if (n->etiqueta == e) enc = 1; else n = n->sig; } return n; } template bool Grafo::ExisteArco(nodo o, nodo { arco a;

d)

a=o->ady; while (a!=0) { if ((a->origen==o) && (a->destino==d)) return true; else a = a->sig; } return false; } template int Grafo::GrafoVacio() { return(this.inicio == 0); } template float Grafo::EtiqArco(nodo o, nodo d) { arco a; a=o->ady; while (a!=0) { if ((a->origen == o) && (a->destino == d)) return (a->valor); else a = a->sig;

113

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

} return 0; } template void Grafo::InsertarNodo(const Tbase dato) { nodo aux,p; aux = new nodo; p=this.inicio; while(p->sig != 0) p = p->sig; aux->etiqueta = dato; aux->nodo = (p->nodo)+1; aux->ady = 0; aux->sig = 0; p->sig = aux; (this.nnodos)++; } template void Grafo::InsertarArco (nodo , nodo d, int valor) { arco aux; aux = new arco; aux->origen = o; aux->destino = d; aux->valor = valor; aux->sig= o->ady; o->ady = aux; } template void Grafo::BorrarArco(nodo o, nodo d) { arco a,ant; int enc=0; if (o->ady==0) return; else if (o->ady->destino==d) { a = o->ady; o->ady = a->sig; delete a; } else { ant = o->ady; a = ant->sig; while (!enc && (a!=0)) { if (a->destino==d)

114

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

enc=1; else { a = a->sig; ant = ant->sig; } } if (a==0) return; else { ant->sig = a->sig; delete a; } } } template Void Grafo::DesconectarNodo(nodo a_eliminar) { Grafo g_nd; nodo n,org,dst,o,d; arco a; g_nd = new Grafo; for (n=this.inicio; n!=0; n=n->sig) g_nd.InsertarNodo(n->etiqueta); for (n=this.inicio; n!=0; n=n->sig) for (a=n->ady; a!=0; a=a->sig) { org = a->origen; dst = a->destino; o = g_nd.LocalizaLabel(org->etiqueta); d = g_nd.LocalizaLabel(dst->etiqueta); if ((org!=a_eliminar) && dst!=a_eliminar)) g_nd.InsertarArco(o,d,a->valor); } this.CopiarGrafo(g_nd); } template Void Grafo::CopiarGrafo(Grafo gr) { nodo n,org,dest,o,d; arco a; this.Destruir(); this = new Grafo; for (n=gr.inicio; n!=0; n=n->sig) this.InsertarNodo(n->etiqueta); for (n=gr.inicio; n!=0; n=n->sig) for (a=n->ady; a!=0; a=a->sig) { org = a->origen; dest = a->destino; o = g_nd.LocalizaLabel(org->etiqueta); d = g_nd.LocalizaLabel(dest->etiqueta);

115

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

this.InsertarArco(o,d,a->valor); } } template Grafo::~Grafo() { nodo n; arco aux; while ((this.inicio)->sig != 0) { n = (this.inicio)->sig; while (n->ady != 0) { aux = n->ady; n->ady = aux->sig; delete aux; } (this.inicio)->sig = n->sig; delete n; } delete (this.inicio); }

12. MANEJO DE ARCHIVOS Así como hemos revisado la salida y entrada por pantalla y teclado respectivamente, veremos ahora la entrada y/o salida de datos utilizando ficheros, lo cual será imprescindible para un gran número de aplicaciones que deseemos desarrollar. 12.1. FICHEROS El estándar de C++ contiene varias funciones para la edición de ficheros, estas están definidas en la cabecera #include y por lo general empiezan con la letra f, haciendo referencia a file. Adicionalmente se agrega un tipo FILE, el cual se usará como apuntador a la información del fichero. La secuencia que usaremos para realizar operaciones será la siguiente: Crear un apuntador del tipo FILE * Abrir el archivo utilizando la función fopen y asignándole el resultado de la llamada a nuestro apuntador. Hacer las diversas operaciones (lectura, escritura, etc). Cerrar el archivo utilizando la función fclose. 12.1.1. FOPEN Esta función sirve para abrir y crear ficheros en disco. El prototipo correspondiente de fopen es: FILE * fopen (const char *filename, const char *opentype);

Los parámetros de entrada de fopen son:

116

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

filename: una cadena que contiene un nombre de fichero válido. opentype: especifica el tipo de fichero que se abrirá o se creará. Una lista de parámetros opentype para la función fopen son: "r”: Abrir un archivo para lectura, el fichero debe existir. "w”: abrir un archivo para escritura, se crea si no existe o se sobre escribe si existe. "a”: abrir un archivo para escritura al final del contenido, si no existe se crea. "r+”: abrir un archivo para lectura y escritura, el fichero debe existir. "w+”: crear un archivo para lectura y escritura, se crea si no existe o se sobre escribe si existe. "r+b ó rb+”: Abre un archivo en modo binario para actualización (lectura y escritura). "rb”: Abre un archivo en modo binario para lectura. Adicionalmente hay tipos utilizando "b" (binary) los cuales no serán mostrados por ahora y que solo se usan en los sistemas operativos que no pertenecen a la familia de Unix. 12.1.2 FCLOSE Esta función sirve para poder cerrar un fichero que se ha abierto. El prototipo correspondiente de fclose es: int fclose (FILE *stream);

Un valor de retorno cero indica que el fichero ha sido correctamente cerrado, si ha habido algún error, el valor de retorno es la constante EOF. Un ejemplo pequeño para abrir y cerrar el archivo llamado fichero.in en modo lectura: #include #include using namespace std; int main(int argc, char** argv) { FILE *fp; fp = fopen ( "fichero.in", "r" ); fclose ( fp ); return 0; }

Como vemos, en el ejemplo se utilizó el opentype "r", que es para la lectura. Otra cosa importante es que el lenguaje C++ no tiene dentro de sí una estructura para el manejo de excepciones o de errores, por eso es necesario comprobar que el archivo fue abierto con éxito "if (fp == NULL)". Si fopen pudo abrir el archivo con éxito devuelve la referencia al archivo (FILE *), de lo contrario devuelve NULL y en este caso se deberá revisar la dirección del archivo o los permisos del mismo. En estos ejemplos solo vamos a dar una salida con un retorno de 1 que sirve para señalar que el programa termino por un error.

117

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

12.1.3 FEOF Esta función sirve para determinar si el cursor dentro del archivo encontró el final (end of file). Existe otra forma de verificar el final del archivo que es comparar el carácter que trae fgetc del archivo con el macro EOF declarado dentro de , pero este método no ofrece la misma seguridad (en especial al tratar con los archivos "binarios"). La función feof siempre devolverá cero (Falso) si no es encontrado EOF en el archivo, de lo contrario regresará un valor distinto de cero (Verdadero). El prototipo correspondiente de feof es: int feof(FILE *fichero);

12.1.4 REWIND Literalmente significa "rebobinar", sitúa el cursor de lectura/escritura al principio del archivo. El prototipo correspondiente de rewind es: void rewind(FILE *fichero);

12.2 LECTURA Un archivo generalmente debe verse como un string (una cadena de caracteres) que está guardado en el disco duro. Para trabajar con los archivos existen diferentes formas y diferentes funciones. Las funciones que podríamos usar para leer un archivo son: char fgetc(FILE *archivo) char *fgets(char *buffer, int tamano, FILE *archivo) size_t fread(void *puntero, size_t tamano, size_t cantidad, FILE *archivo); int fscanf(FILE *fichero, const char *formato, argumento, ...);

Las primeras dos de estas funciones son muy parecidas entre sí. Pero la tercera, por el número y el tipo de parámetros, nos podemos dar cuenta de que es muy diferente, por eso la trataremos aparte junto al fwrite que es su contraparte para escritura. 12.2.1 FGETC Esta función lee un carácter a la vez del archivo que está siendo señalado con el puntero *archivo. En caso de que la lectura sea exitosa devuelve el carácter leído y en caso de que no lo sea o de encontrar el final del archivo devuelve EOF. El prototipo correspondiente de fgetc es: char fgetc(FILE *archivo);

Esta función se usa generalmente para recorrer archivos de texto. A manera de ejemplo vamos a suponer que tenemos un archivo de texto llamado "prueba.txt" en el mismo directorio en que se encuentra la fuente de nuestro programa. Un pequeño programa que lea ese archivo será:

118

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

#include #include #include using namespace std; int main() { FILE *archivo; char caracter; archivo = fopen("prueba.txt","r"); if (archivo == NULL){ printf("\nError de apertura del archivo. \n\n"); }else {

printf("\nEl contenido del archivo de prueba es \n\n"); while (feof(archivo) == 0) { caracter = fgetc(archivo); printf("%c",caracter); } } fclose(archivo); return 0; }

12.2.2 FGETS Esta función está diseñada para leer cadenas de caracteres. Leerá hasta n-1 caracteres o hasta que lea un cambio de línea '\n' o un final de archivo EOF. En este último caso, el carácter de cambio de línea '\n' también es leído. El prototipo correspondiente de fgets es: char *fgets(char *buffer, int tamaño, FILE *archivo);

El primer parámetro buffer lo hemos llamado así porque es un puntero a un espacio de memoria del tipo char (podríamos usar un arreglo de char). El segundo parámetro es tamaño que es el límite en cantidad de caracteres a leer para la función fgets. Y por último el puntero del archivo por supuesto que es la forma en que fgets sabrá a que archivo debe leer. #include #include #include using namespace std;

119

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

int main() { FILE *archivo; char caracteres[100]; archivo = fopen("prueba.txt","r"); if (archivo == NULL) exit(1); printf("\nEl contenido del archivo de prueba es \n\n"); while (feof(archivo) == 0) { fgets(caracteres,100,archivo); printf("%s",caracteres); } system("PAUSE"); fclose(archivo); return 0; }

Este es el mismo ejemplo de antes con la diferencia de que este hace uso de fgets en lugar de fgetc. La función fgets se comporta de la siguiente manera, leerá del archivo apuntado por archivo los caracteres que encuentre y a ponerlos en buffer hasta que lea un carácter menos que la cantidad de caracteres especificada en tamaño o hasta que encuentre el final de una línea (‘\n’) o hasta que encuentre el final del archivo (EOF). En este ejemplo no vamos a profundizar más que para decir que caracteres es un buffer, los por menores serán explicados en la sección de manejo dinámico de memoria. El beneficio de esta función es que se puede obtener una línea completa a la vez. 12.2.3 FREAD size_t fread ( void * ptr, size_t size, size_t count, FILE * stream );

Esta función lee un bloque de una "stream" de datos. Efectúa la lectura de un arreglo de elementos "count", cada uno de los cuales tiene un tamaño definido por "size". Luego los guarda en el bloque de memoria especificado por "ptr". El indicador de posición de la cadena de caracteres avanza hasta leer la totalidad de bytes. Si esto es exitoso la cantidad de bytes leídos es (size*count). PARAMETROS: ptr : Puntero a un bloque de memoria con un tamaño mínimo de (size*count) bytes. size : Tamaño en bytes de cada elemento (de los que voy a leer). count : Número de elementos, los cuales tienen un tamaño "size". stream: Puntero a objetos FILE, que especifica la cadena de entrada.

120

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

12.2.4 FSCANF La función fscanf funciona igual que scanf en cuanto a parámetros, pero la entrada se toma de un fichero en lugar del teclado. El prototipo correspondiente de fscanf es: int fscanf(FILE *fichero, const char *formato, argumento, ...);

Podemos ver un ejemplo de su uso, abrimos el documento "fichero.txt" en modo lectura y leyendo dentro de él. #include #include using namespace std; int main ( int argc, char **argv ) { FILE *fp; char buffer[100]; fp = fopen ( "fichero.txt", "r" ); fscanf(fp, "%s" ,&buffer); printf("%s",buffer); fclose ( fp ); return 0; }

12.3 ESCRITURA Así como podemos leer datos desde un fichero, también se pueden crear y escribir ficheros con la información que deseamos almacenar, Para trabajar con los archivos existen diferentes formas y diferentes funciones. Las funciones que podríamos usar para escribir dentro de un archivo son: int fputc(int caracter, FILE *archivo) int fputs(const char *buffer, FILE *archivo) size_t fwrite(void *puntero, size_t tamano, size_t cantidad, FILE *archivo); int fprintf(FILE *archivo, const char *formato, argumento, ...);

12.3.1 FPUTC Esta función escribe un carácter a la vez del archivo que está siendo señalado con el puntero *archivo. El valor de retorno es el carácter escrito, si la operación fue completada con éxito, en caso contrario será EOF. El prototipo correspondiente de fputc es:

121

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

int fputc(int carácter, FILE *archivo);

Mostramos un ejemplo del uso de fputc en un "fichero.txt", se escribirá dentro del fichero hasta que presionemos la Tecla Enter. #include #include using namespace std; int main ( int argc, char **argv ) { FILE *fp; char caracter; fp = fopen ( "fichero.txt", "r+" ); printf("\nIntrouce un texto al fichero: "); while((caracter = getchar()) != '\n') { printf("%c", fputc(caracter, fp)); } fclose ( fp ); return 0; }

12.3.2 FPUTS La función fputs escribe una cadena en un fichero. No se añade el carácter de retorno de línea ni el carácter nulo final. El valor de retorno es un número no negativo o EOF en caso de error. Los parámetros de entrada son la cadena a escribir y un puntero a la estructura FILE del fichero donde se realizará la escritura. El prototipo correspondiente de fputs es: int fputs(const char *buffer, FILE *archivo)

Para ver su funcionamiento mostramos el siguiente ejemplo: #include #include using namespace std; int main ( int argc, char **argv ) { FILE *fp; char cadena[] = "Mostrando el uso de fputs en un fichero.\n";

122

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

fp = fopen ( "fichero.txt", "r+" ); fputs( cadena, fp ); fclose ( fp ); return 0; }

12.3.3 FWRITE Esta función está pensada para trabajar con registros de longitud constante y forma pareja con fread. Es capaz de escribir hacia un fichero uno o varios registros de la misma longitud almacenados a partir de una dirección de memoria determinada. El valor de retorno es el número de registros escritos, no el número de bytes. Los parámetros son: un puntero a la zona de memoria de donde se obtendrán los datos a escribir, el tamaño de cada registro, el número de registros a escribir y un puntero a la estructura FILE del fichero al que se hará la escritura. El prototipo correspondiente de fwrite es: size_t fwrite(void *puntero, size_t tamano, size_t cantidad, FILE *archivo);

Un ejemplo concreto del uso de fwrite con su contraparte fread y usando funciones es: /* * * * * * * */

FicheroCompleto.cpp Copyright 2012 Alain Wilfredo Fuentes Garcia Cel: 60413636 E-mail: [email protected]>

#include #include using namespace std; void void void void

menu(); CrearFichero(FILE *Fichero); InsertarDatos(FILE *Fichero); VerDatos(FILE *Fichero);

struct sRegistro { char Nombre[25]; int Edad; float Sueldo; } registro; int main() { int opcion; int exit = 0; FILE *fichero; while (!exit) {

123

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

menu(); printf("\nOpcion: "); scanf("%d", &opcion); switch(opcion) { case 1: CrearFichero(fichero); break; case 2: InsertarDatos(fichero); break; case 3: VerDatos(fichero); break; case 4: exit = 1; break; default: printf("\n opcion no valida"); } } return 0; } void menu() { printf("\nMenu:"); printf("\n\t1. Crear fichero"); printf("\n\t2. Insertar datos"); printf("\n\t3. Ver datos"); printf("\n\t4. Salir"); } void CrearFichero(FILE *Fichero) { Fichero = fopen("fichero", "r"); if(!Fichero) { Fichero = fopen("fichero", "w"); printf("\nArchivo creado!"); } else { printf("\nEl fichero ya existe!"); } fclose (Fichero); return; } void InsertarDatos(FILE *Fichero) { Fichero = fopen("fichero", "a+"); if(Fichero == NULL) { printf("\nFichero no existe! \nPor favor creelo"); return;

124

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

} printf("\nDigita el nombre: "); scanf("%s", ®istro.Nombre); printf("\nDigita la edad: "); scanf("%d", ®istro.Edad); printf("\nDigita el sueldo: "); scanf("%f", ®istro.Sueldo); fwrite(®istro, sizeof(struct sRegistro), 1, Fichero); fclose(Fichero); return; } void VerDatos(FILE *Fichero) { int numero = 1; Fichero = fopen("fichero", "r"); if(Fichero == NULL) { printf("\nFichero no existe! \nPor favor creelo"); return; } fread(®istro, sizeof(struct sRegistro), 1, Fichero); printf("\nNumero \tNombre \tEdad \tSueldo"); while(!feof(Fichero)) { printf("\n%d \t%s \t%d \t%.2f", numero, registro.Nombre, registro.Edad, registro.Sueldo); fread(®istro, sizeof(struct sRegistro), 1, Fichero); numero++; } fclose(Fichero); return; }

12.3.4 FPRINTF La función fprintf funciona igual que printf en cuanto a parámetros, pero la salida se dirige a un archivo en lugar de a la pantalla. El prototipo correspondiente de fprintf es: int fprintf(FILE *archivo, const char *formato, argumento, ...); Podemos ver un ejemplo de su uso, abrimos el documento "fichero.txt" en modo lectura/escritura y escribimos dentro de él. #include #include using namespace std;

125

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

int main ( int argc, char **argv ) { FILE *fp; char buffer[100] = "Esto es un texto dentro del fichero."; fp = fopen ( "fichero.txt", "r+" ); fprintf(fp, buffer); fprintf(fp, "%s", "\nEsto es otro texto dentro del fichero."); fclose ( fp ); return 0; }

126

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

SOLUCIONARIO PROBLEMAS PROPUESTOS 1. Diseñar un programa para calcular la suma de dos números A y B #include using namespace std; int main() { int a,b; cout<<"Inserte primer valor: "; cin>>a; cout<<"Inserte segundo valor: "; cin>>b; cout<<endl<<"La Suma es: "<
2. Calcular el área de un triángulo de base B y altura H #include using namespace std; int main() { int b,h; cout<<"Inserte Base: "; cin>>b; cout<<"Inserte Altura: "; cin>>h; cout<<"El area del triangulo es: "<<(b*h)/2<<endl; return 0; }

127

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

3. Calcular el área de un círculo de radio R #include using namespace std; int main() { int r; cout<<"Inserte Radio: "; cin>>r; cout<<"El area de "<<3.1416*(r*r)<<endl; return 0; }

la

circunferencia

4. Ingresar una nota por teclado y determinar si es de aprobación o reprobación

#include using namespace std; int main() { int nota; cout<<"LA NOTA MINIMA DE APROBACION ES DE 51"<<endl<<endl; cout<<"Introduzca Nota: "; cin>>nota; cout<<endl; if (nota>=51) cout<<"Es una nota de aprobacion"; else cout<<"Es una nota de reprobacion"; return 0; }

5. Ingresar un número por teclado y determinar si es PAR o IMPAR

#include using namespace std; int main() { int num; cout<<"Itroduzca un numero: ";

128

es:

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

cin>>num; cout<<endl; if (num % 2==0) cout<<"El numero introducido es par"; else cout<<"El numero introducido es impar"; return 0; }

6. Determinar si una persona es "Niño – 1 a 10 años", "Adolescente – 11 a 17 años", "Joven – 18 a 29 años", "Adulto – 30 a 60 años", "Tercera Edad – 60 a 100 años", de acuerdo a su edad que es introducida por teclado.

#include using namespace std; int main() { int edad; cout<<"Introduzca su edad para realizar el analisis: "; cin>>edad; cout<<endl; if (edad <= 10) cout<<"Es un Niño"; else if (edad <= 17) cout<<"Es un Adolescente"; else if (edad <= 29) cout<<"Es un joven"; else if (edad <= 60) cout<<"Es una persona Adulta"; else if (edad <= 100) cout<<"Es una persona de la Tercera Edad"; else cout<<"MUCHAS FELICIDADES!!!"; return 0; }

129

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

7. Generar Aleatoriamente dos números enteros entre 0 y 100. Determinar cuál es el mayor de ellos.

#include #include #include

using namespace std; int main() { int a,b; srand(time(NULL)); a=rand()%101; b=rand()%101; cout<b) cout<
#include using namespace std; int main() { int a,b,c; cout<<"Primer valor: "; cin>>a; cout<<"Segundo valor: "; cin>>b; cout<<"Tercer valor: "; cin>>c; cout<<endl; if (a>b)

130

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

{ if (a>c) cout<<"El mayor es: "<c) cout<<"El mayor es: "<
#include using namespace std; int main() { int a,b; cout<<"Inserte primer valor: "; cin>>a; cout<<"Inserte segundo valor: "; cin>>b; cout<<endl<<endl; cout<<"La Suma es: "<
10. Ingresar un número cualquiera, determina si es POSITIVO, NEGATIVO ó CERO

#include using namespace std; int main() { int num;

131

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

cout<<"Introduzca numero: "; cin>>num; if (num==0) cout<<"Es cero"; else if (num<0) cout<<"Es un numero negativo"; else cout<<"Es positivo"; return 0; }

11. Generar un numero aleatoriamente entre 1 a 1000 y determinar si es PAR o IMPAR

#include #include #include

using namespace std; int main() { int a; srand(time(NULL)); a=1+rand()%(1001-1); cout<
#include using namespace std; int main() { int n; cout<<"Inserte numero: "; while (cin>>n && n!=0 && n>0) {

132

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

if (n%2==0) cout<<"Es par"<<endl; else cout<<"Es impar"<<endl; } return 0; } 13. Ingresar un número por teclado y determinar si es múltiplo de 10

#include using namespace std; int main() { int n; cout<<"Inserte numero: "; cin>>n; cout<<endl; if (n%10==0) cout<<"Es multiplo de 10"<<endl; else cout<<"No es multiplo de 10"<<endl; return 0; } 14. Ingresar una nota por teclado y determinar su grado de aprovechamiento (0-10) Pésimo, (11-20) Muy Malo, (21-30) Malo, (31-40) regular, (41-50) Bueno, (51-60) Muy Bueno, (61-70) Excelente

#include using namespace std; int main() { int nota; cout<<"Introduzca su nota para realizar el analisis: "; cin>>nota; cout<<endl; if (nota <= 10) cout<<"Es una nota Pesima"; else if (nota <= 20) cout<<"Es una nota Muy mala"; else if (nota <= 30) cout<<"Es una nota Mala"; else if (nota <= 40)

133

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

cout<<"Es una nota Regular"; else if (nota <= 50) cout<<"Es una nota Buena"; else if (nota <= 60) cout<<"Es una nota Muy buena"; else if (nota <= 70) cout<<"Es una nota Excelente"; else cout<<"No me mientas!!!"; return 0; } 15. Simular un juego con un dado. Si se saca un 1 o un 6 e gana, caso contrario se pierde.

#include #include #include using namespace std; int main() { int d; srand(time(NULL)); d=1+rand()%(7-1); cout<
#include #include #include using namespace std; int main() { int d1,d2; srand(time(NULL)); d1=1+rand()%(7-1); d2=1+rand()%(7-1);

134

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

cout<<"Dado 1: "<
#include using namespace std; int main() { int r; cout<<"Inserte el tamaño de la Serie: "; cin>>r; for (int i=1;i<=r;i++) { cout<<(i*2)-1<<" "; } return 0; } 18. Visualizar la serie 1,4,7,10,13,16……..n

#include using namespace std; int main() { int r; cout<<"Inserte el tamaño de la Serie: "; cin>>r; for (int i=1;i<=r;i++) { cout<<(i*3)-2<<" "; } return 0; }

135

Tec. Sup. Alain Wilfredo Fuentes Garcia ESTRUCTURA DE DATOS

HARDWARE - SOFTWARE

19. Ingresar un número y visualizar su tabla de multiplicar

#include using namespace std; int main() { int num; cout<<"Inserte el numero que desa generar la tabla"<<endl; cin>>num; for (int i=1;i<=10;i++) { cout<

Libro - Estructura De Datos.pdf

May 2020 4

Estructura De Datos Y Algoritmos - Libro Texto

June 2020 6

Estructura

June 2020 24

Estructura

October 2019 56

Estructura

October 2019 46

Estructura

November 2019 55