11 Tipos de objetos III: Estructuras

Las estructuras son el segundo tipo de datos estructurados que veremos (valga la redundancia).

Al contrario que los arrays, las estructuras nos permiten agrupar varios datos, que mantengan algún tipo de relación, aunque sean de distinto tipo, permitiendo manipularlos todos juntos, usando un mismo identificador, o cada uno por separado.

Las estructuras son llamadas también muy a menudo registros, o en inglés records. Tienen muchos aspectos en común con los registros usados en bases de datos. Y siguiendo la misma analogía, cada objeto de una estructura se denomina a menudo campo, o field.

Sintaxis:

struct [<identificador>] {
   [<tipo> <nombre_objeto>[,<nombre_objeto>,...]];
} [<objeto_estructura>[,<objeto_estructura>,...];

El identificador de la estructura es un nombre opcional para referirse a la estructura.

Los objetos de estructura son objetos declarados del tipo de la estructura, y su inclusión también es opcional. Sin bien, aún siendo ambos opcionales, al menos uno de estos elementos debe existir.

En el interior de una estructura, entre las llaves, se pueden definir todos los elementos que consideremos necesarios, del mismo modo que se declaran los objetos.

Las estructuras pueden referenciarse completas, usando su nombre, como hacemos con los objetos que ya conocemos, y también se puede acceder a los elementos definidos en el interior de la estructura, usando el operador de selección (.), un punto.

Una vez definida una estructura, es decir, si hemos especificado un nombre para ella, se puede usar igual que cualquier otro tipo de C++. Esto significa que se pueden declarar más objetos del tipo de estructura en cualquier parte del programa. Para ello usaremos la forma normal de declaración de objetos, es decir:

[struct] <identificador> <objeto_estructura>
   [,<objeto_estructura>...];

En C++ la palabra struct es opcional en la declaración de objetos, al contrario de lo que sucede en C, en el que es obligatorio usarla.

Ejemplo:

struct Persona {
   char Nombre[65];
   char Direccion[65];
   int AnyoNacimiento;
} Fulanito;

Este ejemplo define la estructura Persona y declara a Fulanito como un objeto de ese tipo. Para acceder al nombre de Fulanito, por ejemplo para visualizarlo, usaremos la forma:

cout << Fulanito.Nombre;

Funciones en el interior de estructuras

C++, permite incluir funciones en el interior de las estructuras. Normalmente estas funciones tienen la misión de manipular los datos incluidos en la estructura, y su uso está muy relacionado con la programación orientada a objetos.

Aunque esta característica se usa casi exclusivamente con las clases, como veremos más adelante, también puede usarse en las estructuras. De hecho, en C++, las diferencias entre estructuras y clases son muy tenues.

Dos funciones muy particulares son las de inicialización, o constructor, y el destructor. Veremos con más detalle estas funciones cuando asociemos las estructuras y los punteros.

El constructor es una función sin tipo de retorno y con el mismo nombre que la estructura. El destructor tiene la misma forma, salvo que el nombre va precedido el símbolo "~".

Veamos un ejemplo sencillo para ilustrar el uso de constructores:

Forma 1:

struct Punto {
   int x, y;
   Punto() {x = 0; y = 0;} // Constructor
} Punto1, Punto2;

Forma 2:

struct Punto {
   int x, y;
   Punto(); // Declaración del constructor
} Punto1, Punto2;

// Definición del constructor, fuera de la estructura
Punto::Punto() {
   x = 0;
   y = 0;
}

Si no usáramos un constructor, los valores de x e y para Punto1 y Punto2 estarían indeterminados, contendrían la "basura" que hubiese en la memoria asignada a estas estructuras durante la ejecución. Con las estructuras éste será el caso más habitual, ya que si necesitamos usar constructores para asignar valores iniciales, será mucho más lógico usar clases que estructuras.

Mencionar aquí, sólo a título de información, que el constructor no tiene por qué ser único. Se pueden definir varios constructores, pero veremos esto mucho mejor y con más detalle cuando veamos las clases.

Usando constructores nos aseguramos los valores iniciales para los elementos de la estructura. Veremos que esto puede ser una gran ventaja, sobre todo cuando combinemos estructuras con punteros, en capítulos posteriores.

También podemos incluir otras funciones, que se declaran y definen como las funciones que ya conocemos.

Otro ejemplo:

#include <iostream>
using namespace std;

struct stPareja {
   int A, B;
   int LeeA() { return A;} // Devuelve el valor de A
   int LeeB() { return B;} // Devuelve el valor de B
   void GuardaA(int n) { A = n;} // Asigna un nuevo valor a A
   void GuardaB(int n) { B = n;} // Asigna un nuevo valor a B
} Par;

int main() {
   Par.GuardaA(15);
   Par.GuardaB(63);
   cout << Par.LeeA() << endl;
   cout << Par.LeeB() << endl;

   return 0;
}

En este ejemplo podemos ver cómo se define una estructura con dos campos enteros, y dos funciones para modificar y leer sus valores. El ejemplo es muy simple, pero las funciones de guardar valores se pueden elaborar para que no permitan determinados valores, o para que hagan algún tratamiento de los datos.

Por supuesto se pueden definir otras funciones y también constructores más elaborados e incluso, redefinir operadores. Y en general, las estructuras admiten cualquiera de las características de las clases, siendo en muchos aspectos equivalentes.

Veremos estas características cuando estudiemos las clases, y recordaremos cómo aplicarlas a las estructuras.

Inicialización de estructuras

De un modo parecido al que se inicializan los arrays, se pueden inicializar estructuras, tan sólo hay que tener cuidado con las estructuras anidadas. Por ejemplo:

struct A {
   int i;
   int j;
   int k;
};

struct B {
   int x;
   struct C {
      char c;
      char d;
   } y;
   int z;
};

A ejemploA = {10, 20, 30};
B ejemploB = {10, {'a', 'b'}, 20};

Cada nueva estructura anidada deberá inicializarse usando la pareja correspondiente de llaves "{}", tantas veces como sea necesario.

Asignación de estructuras

La asignación de estructuras está permitida, pero sólo entre objetos del mismo tipo de estructura, (salvo que se usen constructores), y funciona como la intuición nos dice que debe hacerlo.

Veamos un ejemplo:

struct Punto {
   int x, y;
   Punto() {x = 0; y = 0;}
} Punto1, Punto2;

int main() {
   Punto1.x = 10;
   Punto1.y = 12;
   Punto2 = Punto1;
}

La línea Punto2 = Punto1; equivale a Punto2.x = Punto1.x; Punto2.y = Punto1.y;.

Quizás te hayas quedado intrigado por el comentario anterior, que adelantaba que se pueden asignar estructuras diferentes, siempre que se usen los constructores adecuados.

Esto, en realidad, se puede extender a cualquier tipo, no sólo a estructuras. Por ejemplo, definiendo el constructor adecuado, podemos asignar un entero a una estructura. Veamos cómo hacer esto.

Hasta ahora, los constructores que hemos visto no usaban argumentos, pero eso no significa que no puedan tenerlos.

Crearemos como ejemplo, una estructura para manejar números complejos. Un número complejo está compuesto por dos valores reales, el primero contiene lo que se llama la parte real y el segundo la parte imaginaria.

struct complejo {
   double real;
   double imaginario;
};

Esta estructura es suficiente para muchas de las cosas que podemos hacer con números imaginarios, pero aprovechando que podemos crear funciones, podemos añadir algunas que hagan de una forma más directa cosas que de otro modo requieren añadir código externo.

Por ahora nos limitaremos a añadir unos cuantos constructores. El primero es el más lógico: un constructor por defecto:

struct complejo {
   complejo() { real=0; imaginario = 0; }
   double real;
   double imaginario;
};

Este construtor se usará, por ejemplo, si declaramos un array:

complejo array[10];

El constructor por defecto será llamado para cada elemento del array, aunque no aparezca tal llamada en ningún punto del programa.

Otro constructor nos puede servir para asignar un valor a partir de dos números:

struct complejo {
   complejo() { real=0; imaginario = 0; }
   complejo(double r, double i) { real=r; imaginario = i; }
   double real;
   double imaginario;
};

Mediante este constructor podemos asignar valores inciales en la declaración:

complejo c1(10.23, 213.22);

Los números reales se consideran un subconjunto de los imaginarios, en los que la parte imaginaria vale cero. Esto nos permite crear otro constructor que sólo admita un valor real:

struct complejo {
   complejo() { real=0; imaginario = 0; }
   complejo(double r, double i) { real=r; imaginario = i; }
   complejo(double r) { real=r; imaginario = 0; }
   double real;
   double imaginario;
};

Este constructor nos permite, como en el caso anterior, inicializar un valor de un complejo en la declaración, pero también nos permite asignar un valor double a un complejo, y por el sistema de promoción automático, también podemos asignar valores enteros o en coma flotante:

complejo c1(19.232);
complejo c2 = 1299.212;
int x = 10;
complejo c3 = x;

Este tipo de constructores se comportan como conversores de tipo, nada nos impide crear constructores con cualquier tipo de parámetro, y tales constructores se podrán usar para convertir cualquier tipo al de nuestra estructura.

Arrays de estructuras

La combinación de las estructuras con los arrays proporciona una potente herramienta para el almacenamiento y manipulación de datos.

Ejemplo:

struct Persona {
   char Nombre[65];
   char Direccion[65];
   int AnyoNacimiento;
} Plantilla[200];

Vemos en este ejemplo lo fácil que podemos declarar el array Plantilla que contiene los datos relativos a doscientas personas.

Podemos acceder a los datos de cada uno de ellos:

cout << Plantilla[43].Direccion;

O asignar los datos de un elemento de la plantilla a otro:

Plantilla[0] = Plantilla[99];

Estructuras anidadas

También está permitido anidar estructuras, con lo cual se pueden conseguir superestructuras muy elaboradas.

Ejemplo:

struct stDireccion {
   char Calle[64];
   int Portal;
   int Piso;
   char Puerta[3];
   char CodigoPostal[6];
   char Poblacion[32];
};

struct stPersona {
   struct stNombre {
      char Nombre[32];
      char Apellidos[64];
   } NombreCompleto;
   stDireccion Direccion;
   char Telefono[10];
};
...

En general, no es una práctica corriente definir estructuras dentro de estructuras, ya que tienen un ámbito local, y para acceder a ellas se necesita hacer referencia a la estructura más externa.

Por ejemplo para declarar un objeto del tipo stNombre hay que utilizar el operador de acceso (::):

stPersona::stNombre NombreAuxiliar;

Sin embargo para declarar un objeto de tipo stDireccion basta con declararla:

stDireccion DireccionAuxiliar;

Estructuras anónimas

Antes dijimos, al hablar sobre la sintaxis de las declaraciones de estructuras, que debe aparecer o bien el identificador de estructura, o bien declararse algún objeto de ese tipo en la declaración. Bien, eso no es del todo cierto. Hay situaciones donde se pueden omitir ambos identificadores.

Una estructura anónima es la que carece de identificador de tipo de estructura y de declaración de objetos del tipo de estructura.

Por ejemplo, veamos esta declaración:

struct stAnonima {
  struct {
    int x;
    int y;
  };
  int z;
};

Para acceder a los campos x o y se usa la misma forma que para el campo z:

   stAnonima Anonima;

   Anonima.x = 0;
   Anonima.y = 0;
   Anonima.z = 0;

Pero, ¿cual es la utilidad de esto?

Pues, la verdad, no mucha, al menos cuando se usa con estructuras. En el capítulo dedicado a las uniones veremos que sí puede resultar muy útil.

El método usado para declarar la estructura dentro de la estructura es la forma anónima, como verás no tiene identificador de tipo de estructura ni de campo. El único lugar donde es legal el uso de estructuras anónimas es en el interior de estructuras y uniones.

Operador sizeof con estructuras

Podemos usar el operador sizeof para calcular el espacio de memoria necesario para almacenar una estructura.

Sería lógico suponer que sumando el tamaño de cada elemento de una estructura, se podría calcular el tamaño de la estructura completa, pero no siempre es así. Por ejemplo:

#include <iostream>
using namespace std;

struct A {
   int x;
   char a;
   int y;
   char b;
};

struct B {
   int x;
   int y;
   char a;
   char b;
};

int main()
{
   cout << "Tamaño de int: "
        << sizeof(int) << endl;
   cout << "Tamaño de char: "
        << sizeof(char) << endl;
   cout << "Tamaño de estructura A: "
        << sizeof(A) << endl;
   cout << "Tamaño de estructura B: "
        << sizeof(B) << endl;

   return 0;
}

Ejecutar este código en OnlineGDB.

El resultado, que puede depender de la plataforma, es el siguiente:

Tamaño de int: 4
Tamaño de char: 1
Tamaño de estructura A: 16
Tamaño de estructura B: 12

Si hacemos las cuentas, en ambos casos el tamaño de la estructura debería ser el mismo, es decir, 4+4+1+1=10 bytes. Sin embargo en el caso de la estructura A el tamaño es 16 y en el de la estructura B es 12, ¿por qué?

La explicación es algo denominado alineación de bytes (byte-aling). Para mejorar el rendimiento del procesador no se accede a todas las posiciones de memoria. En el caso de microprocesadores de 32 bits (4 bytes), es mejor si sólo se accede a posiciones de memoria múltiplos de cuatro, de modo que el compilador intenta alinear los objetos con esas posiciones.

En el caso de objetos int es fácil, ya que ocupan cuatro bytes, pero con los objetos char no, ya que sólo ocupan uno.

Cuando se accede a datos de menos de cuatro bytes la alineación no es tan importante. El rendimiento se ve afectado sobre todo cuando hay que leer datos de cuatro bytes que no estén alineados.

En el caso de la estructura A hemos intercalado campos int con char, de modo que el campo int y, se alinea a la siguiente posición múltiplo de cuatro, dejando tres posiciones libres después del campo a. Lo mismo pasa con el campo b.

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
x				a	vacío			y				b	vacío

En el caso de la estructura B hemos agrupado los campos de tipo char al final de la estructura, de modo que se aprovecha mejor el espacio, y sólo se desperdician los dos bytes sobrantes después de b.

0	1	2	3	4	5	6	7	8	9	10	11
x				y				a	b	vacío

Campos de bits

Existe otro tipo de estructuras que consiste en empaquetar cada uno de los campos en el interior de valores enteros, usando bloques o subconjuntos de bits para cada campo.

Por ejemplo, un objeto char contiene ocho bits, de modo que dentro de ella podremos almacenar ocho campos de un bit, o cuatro de dos bits, o dos de tres y uno de dos, etc. En un objeto int de 16 bits podremos almacenar 16 campos de un bit, etc.

Para definir campos de bits debemos usar siempre valores de enteros sin signo, ya que el signo se almacena en un bit del entero, el de mayor peso, y puede falsear los datos almacenados en la estructura.

La sintaxis es:

struct [<nombre de la estructura>] {
   unsigned <tipo_entero> <identificador>:<núm_de_bits>;
   .
} [<lista_objetos>];

Existen algunas limitaciones, por ejemplo, un campo de bits no puede crearse a orcajadas entre dos objetos distintos, todos sus bits tienen que estar en el mismo valor entero.

Veamos algunos ejemplos:

struct mapaBits {
   unsigned char bit0:1;
   unsigned char bit1:1;
   unsigned char bit2:1;
   unsigned char bit3:1;
   unsigned char bit4:1;
   unsigned char bit5:1;
   unsigned char bit6:1;
   unsigned char bit7:1;
   };

struct mapaBits2 {
   unsigned short int campo1:3;
   unsigned short int campo2:4;
   unsigned short int campo3:2;
   unsigned short int campo4:1;
   unsigned short int campo5:6;
};

struct mapaBits3 {
   unsigned char campo1:5;
   unsigned char campo2:5;
};

En el primer caso se divide un valor char sin signo en ocho campos de un bit cada uno:

7	6	5	4	3	2	1	0
bit7	bit6	bit5	bit4	bit3	bit2	bit1	bit0

En el segundo caso dividimos un valor entero sin signo de dieciséis bits en cinco campos de distintas longitudes:

15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0
campo5						c4	campo3		campo2				campo1

Los valores del campo5 estarán limitados entre 0 y 63, que son los números que se pueden codificar con seis bits. Del mismo modo, el campo4 sólo puede valer 0 ó 1, etc.

unsigned char								unsigned char
7	6	5	4	3	2	1	0	7	6	5	4	3	2	1	0
			campo2								campo1

En este ejemplo vemos que como no es posible empaquetar el campo2 dentro del mismo char que el campo1, de modo que se añade un segundo valor char, y se dejan sin usar todos los bits sobrantes.

También es posible combinar campos de bits con campos normales, por ejemplo:

struct mapaBits2 {
   int numero;
   unsigned short int campo1:3;
   unsigned short int campo2:4;
   unsigned short int campo3:2;
   unsigned short int campo4:1;
   unsigned short int campo5:6;
   float n;
};

Los campos de bits se tratan, por norma general, igual que cualquier otro de los campos de una estructura. Se les puede asignar valores (dentro del rango que admitan por su tamaño), pueden usarse expresiones, imprimirse, etc.

#include <iostream>
#include <cstdlib>
using namespace std;

struct mapaBits2 {
   unsigned short int campo1:3;
   unsigned short int campo2:4;
   unsigned short int campo3:2;
   unsigned short int campo4:1;
   unsigned short int campo5:6;
};

int main()
{
   mapaBits2 x;

   x.campo2 = 12;
   x.campo4 = 1;
   cout << x.campo2 << endl;
   cout << x.campo4 << endl;

   return 0;
}

Lo que no es posible es leer valores de un campo de bits mediante cin. Para poder leer valores desde el teclado se debe usar una variable entera auxiliar, y posteriormente asignarla al campo de bits.

No es frecuente usar estas estructuras en programas, salvo cuando se relacionan con ciertos dispositivos físicos. Por ejemplo, para configurar un puerto serie en MS-DOS se usa una estructura empaquetada en un unsigned char, que indica el número de bits de datos, de bits de parada, la paridad, etc, es decir, todos los parámetros del puerto. En general, para programas que no requieran estas estructuras, es mejor usar estructuras normales, ya que son mucho más rápidas.

Otro motivo que puede decidirnos por estas estructuras es el ahorro de espacio, ya sea en disco o en memoria. Si conocemos los límites de los campos que queremos almacenar, y podemos empaquetarlos en estructuras de mapas de bits podemos ahorrar mucho espacio.

Palabras reservadas usadas en este capítulo

struct.

Problemas

1. Escribir un programa que almacene en un array los nombres y números de teléfono de 10 personas. El programa debe leer los datos introducidos por el usuario y guardarlos en memoria (en el array). Después debe ser capaz de buscar el nombre correspondiente a un número de teléfono y el teléfono correspondiente a una persona. Ambas opciones deben se accesibles a través de un menú, así como la opción de salir del programa. El menú debe tener esta forma, más o menos:

   a) Buscar por nombre
   b) Buscar por número de teléfono
   c) Salir
   
   Pulsa una opción:

   Nota:

   No olvides que para comparar cadenas se debe usar una función, no el operador ==.

2. Para almacenar fechas podemos crear una estructura con tres campos: ano, mes y dia. Los días pueden tomar valores entre 1 y 31, los meses entre 1 y 12 y los años, dependiendo de la aplicación, pueden requerir distintos rangos de valores. Para este ejemplo consideraremos suficientes 128 años, entre 1960 y 2087. En ese caso el año se obtiene sumando 1960 al valor de ano. El año 2003 se almacena como 43.
   Usando estructuras, y ajustando los tipos de los campos, necesitamos un char para dia, un char para mes y otro para ano.
   Diseñar una estructura análoga, llamada fecha, pero usando campos de bits. Usar sólo un entero corto sin signo (unsigned short), es decir, un entero de 16 bits. Los nombres de los campos serán: dia, mes y anno.
3. Basándose en la estructura de bits del ejercicio anterior, escribir una función para mostrar fechas: void Mostrar(fecha);. El formato debe ser: "dd de mmmmmm de aaaa", donde dd es el día, mmmmmm el mes con letras, y aaaa el año. Usar un array para almacenar los nombres de los meses.
4. Basándose en la estructura de bits del ejercicio anterior, escribir una función bool ValidarFecha(fecha);, que verifique si la fecha entregada como parámetro es válida. El mes tiene que estar en el rango de 1 a 12, dependiendo del mes y del año, el día debe estar entre 1 y 28, 29, 30 ó 31. El año siempre será válido, ya que debe estar en el rango de 0 a 127.
   Para validar los días usaremos un array int DiasMes[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};. Para el caso de que el mes sea febrero, crearemos otra función para calcular si un año es o no bisiesto: bool Bisiesto(int); Los años bisiestos son los divisibles entre 4, al menos en el rango de 1960 a 2087 se cumple.
   

   Nota:

   Los años bisiestos son cada cuatro años, pero no cada 100, aunque sí cada 400. Por ejemplo, el año 2000, es múltiplo de 4, por lo tanto debería haber sido bisiesto, pero también es múltiplo de 100, por lo tanto no debería serlo; aunque, como también es múltiplo de 400, finalmente lo fue.

5. Seguimos con el tema de las fechas. Ahora escribir dos funciones más. La primera debe responder a este prototipo: int CompararFechas(fecha, fecha);. Debe comparar las dos fechas suministradas y devolver 1 si la primera es mayor, -1 si la segunda es mayor y 0 si son iguales.
   La otra función responderá a este prototipo: int Diferencia(fecha, fecha);, y debe devolver la diferencia en días entre las dos fechas suministradas.

Ejemplos capítulos 10 y 11

Ejemplo 11.1

En el capítulo 10 sobre los arrays vimos cómo ordenarlo usando el método de la burbuja. Hay muchas formas de ordenar un array pero el objetivo suele ser siempre el mismo: poder localizar o al menos determinar si existe, un determinado valor dentro del array.

Hay varios métodos de búsqueda, pero el más conocido, es el de la "Búsqueda binaria" o "Busca dicotómica". Se trata además, un método muy bueno de búsqueda, ya que el tiempo de búsqueda disminuye exponencialmente con el número de iteraciones.

La idea es sencilla, se elige el elemento central del rango en el que debemos buscar. Pueden pasar tres cosas:

• Que el elemento elegido sea el buscado, con lo que ha terminado la búsqueda.
• Que el elemento elegido sea menor que el buscado, en ese caso, tomaremos el elemento siguiente al elegido como límite inferior de un nuevo rango, y repetiremos el proceso.
• Que el elemento elegido sea mayor. Ahora tomaremos el elemento anterior al elegido como nuevo límite superior de un nuevo rango, y repetiremos el proceso.

El proceso termina cuando encontramos el elemento, o cuando el rango de búsqueda resulte nulo, y la búsqueda habrá fracasado.

// Búsqueda binaria
// Agosto de 2009 Con Clase, Salvador Pozo
#include <iostream>
using namespace std;

int Binaria(int*, int, int, int);

int tabla[] = {
      1,   3,  12,  33,  42,  43,  44,  45,  54,  55,
     61,  63,  72,  73,  82,  83,  84,  85,  94,  95,
    101, 103, 112, 133, 142, 143, 144, 145, 154, 155,
    161, 163, 172, 173, 182, 183, 184, 185, 194, 195
};

int main() {
    int pos;
    int valor=141;

    pos = Binaria(tabla, valor, 0, sizeof(tabla)/sizeof(tabla[0])-1);
    if(pos > 0) cout << "Valor " << valor << " encontrado en posicion: " << pos << endl;
    else cout << "Valor " << valor << " no encontrado" << endl;
    return 0;
}

/* Función de búsqueda binaria:
   Busca el "valor" dentro del vector "vec" entre los márgenes
   inferior "i" y superior "s" */
int Binaria(int* vec, int valor, int i, int s) {
    int inferior = i;
    int superior = s;
    int central;

    do {
        central = inferior+(superior-inferior)/2;
        if(vec[central] == valor) return central;
        else if(vec[central] < valor) inferior = central+1;
        else superior = central-1;
    } while(superior >= inferior);
    return -1;
}

Ejecutar este código en OnlineGDB.

En el capítulo 24 veremos otro modo de implementar esta función, usando recursividad.

Ejemplo 11.2

Ya sabemos que el tamaño de los números enteros está limitado en C++. Con enteros de 64 bits con signo, el número más grande es 9223372036854775808, es decir, 19 dígitos.

En general, veremos que esto es más que suficiente para casi todas nuestras aplicaciones, pero es posible que a veces necesitemos más dígitos.

Hacer un programa que pueda sumar numeros enteros sin signo, almacenados en forma de cadena. La longitud de la cadena se almacenará en una constante cadmax de modo que pueda cambiar a nuestra conveniencia. En principio, usaremos 32 caracteres. Si el resultado no cabe en cadmax caracteres, retornar con false para indicar un error de desbordamiento. Si el resultado es correcto, retornar true.

Piensa sobre el problema, a partir de este punto lo analizaremos y sacaremos conclusiones para diseñar nuestro programa.

Lo primero que hay que tener en cuenta es que almacenamos los números en forma de caracteres, lo que es poco eficaz, pero es un ejercicio...

Cada carácter es un dígito, y para hacer la suma, empezaremos a sumar dígito a dígito, empezando por la derecha. Así, '1'+'1' debe dar '2'. Pero ya sabemos que se trata de códigos ASCII, de modo que si sumamos normalmente, tendremos que restar el valor ASCII de '0':

cout << char('1'+'1') << endl;

El resultado de esta operación es 'b'.

cout << char('1'+'1'-'0') << endl;

Y el resultado de esta es '2'.

Hay otro problema añadido. Si la suma de los dígitos es mayor que '9', no tendremos un dígito:

cout << char('7'+'8'-'0') << endl;

El resultado de esta suma es '?'. No es que el compilador no sepa sumar. Lo que pasa es que se ha producido un desbordamiento. 7+8 son 15, es decir, 5, "y nos llevamos 1". Ese 1 es un desbordamiento o acarreo. Es decir, debemos tener en cuenta el acarreo en la suma del siguiente dígito. La operación se complica un poco más:

int acarreo=0;
int resultado = char('7'+'8'-'0'+acarreo);
if(resultado < '9') { resultado-=10; acarreo = 1; }
else acarreo = 0;
cout << resultado << endl;

El segundo detalle a considerar es que empezar a recorrer cadenas desde la derecha no es tan simple como pueda parecer al principio, sobre todo si las cadenas tienen distinta longitud.

const unsigned int cadmax = 32;
typedef char numero[cadmax];
numero suma;
numero n1 = "8988989";
numero n2 = "7763";

Si queremos sumar n1 y n2, deberemos empezar por los dígitos '9' y '3', respectivamente, es decir, por n1[6] y n2[3]. El resultado se almacena en la posición 6 de la cadena suma. Pasamos al siguiente dígito: n1[5] y n2[2], etc. Cuando llegamos a n1[3] y n2[0] tropezamos con un problema. El siguiente dígito de n2 no existe. Cuando pase eso, para cualquiera de las dos cadenas, deberemos tomar el valor '0' para esos dígitos.

Aún hay otro inconveniente que debemos salvar. Por ejemplo:

const unsigned int cadmax = 32;
typedef char numero[cadmax];
numero suma;
numero n1 = "9";
numero n2 = "3";

En este caso, el resultado de '9'+'3' es '2' y el acarreo queda con valor 1. La cadena resultante contiene "2", que evidentemente es un resultado erróneo. En este caso, deberemos desplazar todos los dígitos de suma a la derecha, y añardir el dígito '1' al principio.

Por último, hay un caso especial más. Supongamos que el resultado de la suma de los dos números no cabe en el número de caracteres usado para almacenarlos. En ese caso, debemos retornar false.

El resultado es un programa como este:

// Sumar números enteros sin signo almacenados en cadenas
// Agosto de 2009 Con Clase, Salvador Pozo
#include <iostream>
#include <cstring>

using namespace std;

const unsigned int cadmax = 32;
typedef char numero[cadmax];

bool Sumar(numero, numero, numero);
int max(int, int);

int main()
{
    numero n1="999999999999999999";
    numero n2="1";
    numero suma;

    Sumar(n1, n2, suma);
    cout << n1 << " + " << n2 << " = " << suma << endl;
    return 0;
}

bool Sumar(numero n1, numero n2, numero r) {
  // Primero, buscar los dígitos de la derecha:
  char c1,c2;
  int acarreo = 0;
  int lon1=strlen(n1);
  int lon2=strlen(n2);
	// Colocar el terminador de la cadena resultado:
  r[max(lon1, lon2)] = 0;
  // Hacer la suma, digito a digito:
	do {
    lon1--;
    lon2--;
    if(lon1 < 0) c1 = '0'; else c1 = n1[lon1];
    if(lon2 < 0) c2 = '0'; else c2 = n2[lon2];
    r[max(lon1, lon2)] = acarreo+c1+c2-'0';
    if(r[max(lon1, lon2)] > '9') { r[max(lon1, lon2)]-=10; acarreo=1; }
    else acarreo = 0;
  } while(lon1 > 0 || lon2 > 0);

  // Desbordamiento:
  if(acarreo) {
    if(strlen(r) < cadmax) {
      for(int i=strlen(r)+1; i > 0; i--) r[i] = r[i-1];
      r[0] = '1';
      return false;
    }
  }
  return true;
}

int max(int a, int b) {
    if(a > b) return a;
    return b;
}

Ejecutar este código en OnlineGDB.

Ejemplo 11.3

Seamos más inteligentes con el uso de recursos. Usando caracteres, cada byte puede almacenar sólo diez valores diferentes. Una cadena de 32 bytes puede almacenar números positivos sin signo hasta 10³² dígitos (eso sin tener en cuenta el caracter nulo usado como fin de cadena). Pero si aprovechamos cada bit, con cada carácter hay 256 posibilidades, en lugar de 10, y el resultado es que podemos almacenar números hasta 256³², o lo que es lo mismo, 2²⁵⁶. Eso significa, enteros con 77 dígitos significativos.

Escribamos el programa anterior aprovechando cada bit. Por comodidad, usaremos el modo de almacenamiento Little-Endian.

El formato Little-Endian tiene la ventaja, para nosotros, de que es más facil sumar números usando índices que crecen en el orden natural, de menor a mayor. La desventaja es que, cuando se usan enteros con signo, éste se almacena en el último lugar.

La aritmética binaria hace que, además, nuestro programa sume correctamente tanto números positivos como negativos, algo que no pasaba en el ejemplo anterior.

La rutina de suma se simplifica notablemente, aunque no será tan sencillo visualizar los resultados. Además, deberemos usar unsigned char para almanenar los datos, con el fin de que los resultados de las sumas no se convientan en negativos al sumar ciertos valores positivos.

typedef unsigned char numero[cadmax];
...
bool Sumar(numero n1, numero n2, numero r) {
    int acarreo = 0;
    int c;

    for(unsigned int i = 0; i < cadmax; i++) {
        c = acarreo+n1[i]+n2[i];
        if(c > 0xff) { c-=256; acarreo=true; }
        else acarreo=false;
        r[i] = c;
    }
    return !acarreo;
}

Ejecutar este código en OnlineGDB.

Evidentemente, visualizar en pantalla números almacenados en este formato es un problema. Tendremos que calcular el módulo de dividir entre 10 sucesivamente para obtener los dígitos decimales de derecha a izquierda. Hasta ahora sólo sabemos sumar, lo que convierte este problema en algo no trivial.

Ejemplo 11.4

Vamos a trabajar ahora un poco con estructuras. Crearemos una estructura sencilla para almacenar fracciones:

struct fraccion {
    int num;
    int den;
};

Ya dije que sería sencilla.

Bueno, este ejemplo consiste en crear un programa que simplifique fracciones, o más concretamente, que use una función que devuelva una fracción simplificada de la que proporcionamos como parámetro de entrada.

Repasemos un poco. Para cada fracción existe un número infinitos de equivalencias, basta multiplicar el numerador y el denominador por un mismo número:

  1     2     3     4      5
 --- = --- = --- = --- = ---- = ...
  2     4     6     8     10

Simplificar una fracción significa expresarla de la forma más simple, es decir, para los valores mínimos de numerador y denominador.

Para ello necesitamos encontrar el máximo común divisor (MCD) del numerador y del denominador, es decir, el mayor número entero que divide tanto al numerador como al denominador.

Generalmente, el método consiste en descomponer en factores primos los dos números y seleccionar todos los comunes. Su producto será el MCD.

Esto es lo que haremos con nuestro programa:

// Simplificación de fracciones
// Agosto de 2009 Con Clase, Salvador Pozo
#include <iostream>
using namespace std;

struct fraccion {
    int num;
    int den;
};

fraccion Simplificar(fraccion);

int MCD(int, int);

int main() {
    fraccion f, s;
    f.num = 1204;
    f.den = 23212;

    s = Simplificar(f);
    cout << "Simplificar(" << f.num << "/" << f.den << ") = ";
	  cout << s.num << "/" << s.den << endl;

    return 0;
}

fraccion Simplificar(fraccion f) {
    int mcd = MCD(f.num,f.den);
    f.num /= mcd;
    f.den /= mcd;
    return f;
}

int MCD(int n1, int n2) {
    // Buscar los factores primos que dividen tanto a n1 como a n2
    int resultado = 1; // El 1 siempre es un CD
    int factor = 2;    // Empezamos en 2

    while(factor <= n1 || factor <= n2) {
        while(!(n1 % factor) && !(n2 % factor)) {
            resultado *= factor;
            n1 /= factor;
            n2 /= factor;
        }
        if(factor == 2) factor++;  // Si factor es 2, el siguiente primo es 3
        else factor+=2;            // Si no, elegimos el siguiente número impar
    }
    return resultado;
}

Ejecutar este código en OnlineGDB.

Ejemplo 11.5

Siguiendo con este tema, ahora que sabemos simplificar fracciones, vamos a hacer un programa que las sume.

Volviendo al repaso, recordemos que sólo es posible sumar dos fracciones si tienen el mismo denominador. En ese caso, basta con sumar los numeradores, y mantener el denominador común.

Generalmente, se usan dos métodos para sumar dos fracciones. Uno consiste en calcular el mínimo común denominador de las dos fracciones, recalcular los numeradores de las dos fracciones equivalentes, y finalmente sumarlas.

   n1     n2     n1*mcd/d1     n2*mcd/d2     n1*mcd/d1+n2*mcd/d2
  ---- + ---- = ----------- + ----------- = ---------------------
   d1     d2        mcd           mcd               mcd

El segundo método consiste en encontrar un común denominador más sencillo, que es directamente el producto de los denominadores, y simplificar, si es posible, la fracción resultante:

   n1     n2     n1*d1*d2/d1     n2*d1*d2/d2     n1*d2     n2*d1     n1*d2+n2*d1
  ---- + ---- = ------------- + ------------- = ------- + ------- = ------------- => Simplificar
   d1     d2        d1*d2           d1*d2        d1*d2     d1*d2        d1*d2

Usaremos este segundo método:

// Suma de fracciones
// Agosto de 2009 Con Clase, Salvador Pozo
#include <iostream>
using namespace std;

struct fraccion {
    int num;
    int den;
};

fraccion Simplificar(fraccion);
fraccion Sumar(fraccion, fraccion);
int MCD(int, int);

int main() {
    fraccion f, g, s;

	f.num=10;
    f.den=3;
    g.num=5;
    g.den=6;
    s = Sumar(f, g);
    cout << "Sumar(" << f.num << "/" << f.den << "," << g.num << "/" << g.den << ") = ";
    cout << s.num << "/" << s.den << endl;

    return 0;
}

fraccion Simplificar(fraccion f) {
    int mcd = MCD(f.num,f.den);
    f.num /= mcd;
    f.den /= mcd;
    return f;
}

int MCD(int n1, int n2) {
    // Buscar los factores primos que dividen tanto a n1 como a n2
    int resultado = 1; // El 1 siempre es un CD
    int factor = 2;    // Empezamos en 2

    while(factor <= n1 || factor <= n2) {
        while(!(n1 % factor) && !(n2 % factor)) {
            resultado *= factor;
            n1 /= factor;
            n2 /= factor;
        }
        if(factor == 2) factor++;  // Si factor es 2, el siguiente primo es 3
        else factor+=2;            // Si no, elegimos el siguiente número impar
    }
    return resultado;
}

fraccion Sumar(fraccion f1, fraccion f2) {
    fraccion resultado;

    resultado.num = f1.num*f2.den+f1.den*f2.num;
    resultado.den = f1.den*f2.den;
    return Simplificar(resultado);
}

Ejecutar este código en OnlineGDB.