TEMA 3 : Estructuras de datos estáticas
3.0 Introducción.
En este tema se describirán las herramientas que proporciona
el lenguaje C para trabajar con tipos y estructuras de datos,
flexibilizando de esta forma la creación de programas por parte del
programador.
3.1 Matrices Estáticas.
La matriz es una estructura de datos básica dentro de los
lenguajes de programación y conceptualmente son identicas a sus
homónimas matemáticas. Por tanto una matriz es un conjunto de datos
de un tamaño definido que se encuentran consecutivos en memoria y en
la que es posible el acceso al elemento que deseemos simplemente con
indicar su posición. La declaración de una matriz en lenguaje C es
como sigue:
tipo_de_dato identificador[tamaño1][tamaño2]...;
Dónde :
tipo_de_dato: Es el tipo de datos que contendrá la matriz.
Hasta ahora sólo conocemos los tipos básicos de datos; int, float,
double, char. Posteriormente veremos como definir nuestros propios
tipos de datos.
identificador: Es el nombre que le damos a la variable
matriz y po el cual la referenciaremos en nuestro programa.
[tamaño] : Indica el número de elementos de tipo
tipo_de_datos contendrá la matriz identificador. Si definimos dos
tamaños [tamaño1][tamaño2] nuestra matriz será bidimensional.
Algunas declaraciones de matrices serían:
/* Matriz de números reales de 10x10 */
float matriz[10][10];
/* Matriz tridimensional de números enteros 20x20x10 */
int Tridimensional[20][20][10];
Como ya se supondrá el acceso a cada elemento de la matriz
se realiza especificando su posición, pero ésta comienza a contarse
desde el valor 0, es decir, la primera matriz que hemos definido
(matriz) tendrá elementos desde el [0][0] al [9][9]. Esto puede
causar algunos mal entendidos cuando se trabaja con matrices
estáticas. Por ejemplo:
a = matriz [2][1];
/* A toma el valor del elemeto (2,1) comenzando a contar
desde 0 o del (3,2) si consideramos que el primer valor de la matriz
es el (1,1) */
tridimensional [5][16][1] = 67;
/* Introduce el valor 67 en la entrada de la matriz
especificada */
Las variables de tipo matriz como el resto de las
declaraciones, se pueden inicializar en el momento de su
declaración, ayudándose de las llaves ({}) para la inclusión de
inicializaciones múltiples.
int matriz[2][3] = {
{ 1,2,3 },
{ 4,5,6 }
};
Estas líneas nos declararían una matriz llamada "matriz" de
2x3 elementos inicializada con los valores indicados. Las matrices
son extremadamente útiles para trabajar con multitud de problemas
matemáticos que se formulan de esta forma o para mantener tablas de
datos a los que se accede con frecuencia y por tanto su referencia
tiene que ser muy rápida. Supongamos que estamos desarrollando un
programa para dibujar objetos en tres dimensiones y más que la
exactitud de la representación (aunque esto es muy relativo), nos
interesa la velocidad. En la representación de objetos
tridimensionales se hace continua referencia a las funciones
trigonométricas seno y coseno. El cálculo de un seno y un coseno
puede llevar bastante tiempo así que antes de comenzar la
representación calculamos todos los senos y cosenos que necesitemos
(por ejemplo con una resolución de 1 grado -360 valores-) cada vez
que necesitemos uno de estos valores accedemos a la matriz en lugar
de llamar a la función que nos lo calcula. Veamos como sería nuestro
programa (las funciones sin y cos se encuentran en la librería
estandar math.h y sus paramétros están en radianes).
#include <stdio.h>
#include <math.h>
main()
{
float senos[360]; /* Almacenamos senos */
float cosenos[360];
int i;
/* Inicializamos las matrices */
for (i=0;i<360;i++)
{
seno[i] = sin (3.14159*i/180);
coseno[i] = cos (3.14159*i/180);
}
printf ("\nEl coseno de 30 es : %f",coseno[30]);
printf ("\nEl seno de 30 es : %f",seno[30]);
}
3.2 Tipos compuestos
3.2.0 Introducción
En muchas ocasiones nos interesaría disponer de variables
compuestas de otras variables y trabajar con ellas como si se
tratasen de una sola. Un ejemplo típico es una ficha de datos de una
agenda. Necesitaríamos una variable que nos almacenase el nombre,
otra variable que nos almacenase la dirección, otra para el teléfono
y así sucesivamente para todos los datos que deseemos mantener.
Podríamos disponer de una variable para cada campo (cada una de las
informaciones que componen nuestra ficha) pero esto resultaría un
tanto engorroso a la hora de su programación.
El lenguaje C dispone de mecanismos para trabajar con
variables compuestas de otras variables con suma facilidad. Existen
dos tipos básicos: estructuras y uniones.
3.2.1 Estructuras de datos.
Se trata de la forma más versatil de trabajar con fichas de
información. Veamos como se definen y posteriormente comentaremos
todos los aspectos relevantes de ellas.
struct [Nombre_de_la_estructura]
{
tipo1 campo1;
tipo2 campo2;
.
.
tipoN campoN;
} [variable];
La palabra clave struct define una estructura. Por tratarse
de un tipo de datos puede utilizarse directamente para definir una
variable. La variable aparece entre corchetes puesto que puede ser
omitida. Si se especifica una variable, estaremos definiendo una
variable cuyo tipo será la estructura que la precede. Si la variable
no es indicada definimos un nuevo tipo de datos (struct
Nombre_de_la_estructura), que podremos utilizar posteriormente. Si
es el nombre de la estructura lo que se omite, tendremos que
especificar obligatoriamente una variable que tendrá esa estructura
y no podremos definir otras variables con esa estructura sin tener
que volver a especificar todos los campos. Lo que se encuentra
dentro de las llaves es una definición típica de variables con su
tipo y su identificador. Todo esto puede parecer un poco confuso
pero lo aclararemos con unos ejemplos.
struct punto
{
float x;
float y;
int color;
} punto_de_fuga;
Aquí estamos definiendo una variable llamada punto_de_fuga
cuyo tipo es una estructura de datos formada por tres campos y a la
que hemos llamado punto. Dos de ellos son de tipo float y
representan las coordenadas del punto, el tercer valor es un entero
que indica el color de ese punto. En este caso hemos definido una
variable y una estructura. Al disponer de un identificador para esta
última podemos definir nuevas variables de esta estructura.
struct punto origen1;
struct punto final1;
Donde origen1 y final1 son variables de tipo struct punto
que hemos definido anteriormente. Si en la definición de
punto_de_fuga no se hubiese incluído un identificador para la
estructura (en este caso el identificador es punto), no podríamos
definir nuevas variables con esa estructura ya que no estaría
identificada por ningún nombre.
También podríamos haber excluído el nombre de la variable
(punto_de_fuga). En este caso lo que definiríamos sería una
estructura llamada punto que pasaría a ser un nuevo tipo disponible
por el usuario. Así los tipos de variables de que dispondríamos
ahora serían:
int
float
double
char
struct punto
Por tanto podríamos definir cualquier variable con estos
tipos o incluso definir matriz de estos tipos.
struct punto matriz_de_puntos[30];
Así estaríamos definiendo una matriz de 30 elementos en la
que cada elemento es una struct punto con sus tres campos.
Lo que ahora nos interesa es saber como referenciar esos
campos y acceder o modificar, por tanto la información que
contienen. Esto se consigue separando el identificador del campo de
la variable mediante un punto. Así:
punto_de_fuga.x = 0;
punto_de_fuga.y = 0;
punto_de_fuga.color = 10;
inicializa la cada uno de los campos de la variable punto de
fuga con sus valores correspondientes. Está claro que para acceder a
los campos necesitamos alguna variable cuyo tipo sea nuestra
estructura. Si no tenemos variable no tenemos información (sería
como hacer int = 6).
En el caso de la matriz tenemos tantas variables de tipo
struct punto como las indicadas, puesto que el punto separa el
nombre de la variable del campo al que queremos acceder, la forma de
modificar una entrada de la matriz sería:
matriz_de_puntos[4].x = 6;
matriz_de_puntos.x[4] = 6; /* No sería correcto */
Esta última declaración se podría utilizar con una
estructura de un tipo como:
struct otra
{
float x[10];
} matriz_de_puntos;
Con lo cual accederíamos al cuarto elemento del campo x de
matriz_de_puntos que es una variable de tipo struct otra constituida
por una matriz de diez floats.
Para terminar con la declaración struct indicar que es
posible la declaración de estructuras anidadas, es decir, un campo
de una estructura puede ser otra estructura.
struct vector
{
float x;
float y;
float z;
};
struct poligono_cuadrado
{
struct vector p1;
struct vector p2;
struct vector p3;
struct vecto p4;
};
struct cubo
{
struct poligono_cuadrado cara[6];
int color;
struct vector posicion;
};
struct cubo mi_cubo;
Hemos declarado una variable (mi_cubo) de tipo struct cubo
que es una estructura conteniendo un valor entero que nos indica el
color de nuestro objeto, una variable de tipo struct vector
(posicion) indicando la posición del objeto en un espacio de tres
dimensiones (posicion tiene tres campos x,y,z por tratarse de una
struct vector) y una matriz de seis elemento en la que cada elemento
es un struct poligono_cuadrado, el cual está formado por cuadro
vectores que indican los cuatro vértices del cuadrado en 3D. Para
aceder a todos los campos de esta variable necesitaríamos sentencias
del tipo.
mi_cubo.color = 0;
mi_cubo.posicion.x = 3;
mi_cubo.posicion.y = 2;
mi_cubo.posicion.z = 6;
mi_cubo.cara[0].p1.x = 5;
/* Ahora acedemos a la coordenada 0 del tercer polígono
de la cara 0 de mi_cubo*/
mi_cubo.cara[0].p3.z = 6;
....
3.2.2 Estructuras solapadas. union
La definición de una union es analoga a la definición de una
estructura. La diferencia entre ambas es que los campos que
especifiquemos en una union ocupan todos la misma posicion de
memoria. Cuando se declara una union se reserva espacio para poder
almacenar el campo de mayor tamaño de los declarados y como ya se
dijo todos los campos ocupan la misma posición en la memoria. Veamos
un ejemplo.
union ejemplo
{
char caracter;
int entero;
} mi_var;
mi_var es una variable cuyo tipo es union ejemplo, y el
acceso a cada campo de los definidos se realiza igual que en las
struct mediante la utilización de un punto. Hasta aquí nada nuevo lo
que sucede es que carácter y entero (los dos campos) ocupan la misma
posición de memoria. Así:
mi_var.entero = 0; /* Como el tipo int ocupa más que el tipo
char ponemos a 0 toda la union */
mi_var.caracter = 'A'; /* El código ASCII de A es 65, por
tanto ahora mi_var.entero = 65 */
mi_var.entero = 0x00f10;
Esta última instrucción introduce un valor en hexadecimal en
la variable mi_var.entero. El código hexadecimal se representa en C
anteponiendo al número los caracteres 0x. Para comprender lo que
realiza esta instrucción veamos un poco como el ordenador representa
los número internamente.
Todos hemos oido alguna vez que el ordenador sólo entiende
ceros y unos, pues bien, lo único que significa ésto es que el
ordenador cuenta en base dos en lugar de hacerlo en base diez como
nosotros. Cuando contamos en base diez comenzamos en 0 y al llegar a
nueve añadimos una unidad a la izquierda para indicar que llegamos a
las centenas y así consecutivamente. Cada cifra de un número en base
diez representa esa cifra multiplicada por una potencia de diez que
depende de la posición del dígito. Es lo que se llama descomposición
factorial de un número.
63452 = 6*10^4+3*10^3+4*10^2+5*10^1+2*10^0=
= 60000+3000+400+50+2
Como nuestro ordenador en lugar de contar de diez en diez
cuenta de dos en dos cada cifra es una potencia de dos. El sistema
de numeración en base dos se denomina sistema binario.
b100101 = 1*2^5+0*2^4+0*2^3+1*2^2+0*2^1+1*2^0=
= 32 + 0 + 0 + 4 + 1 = 37
Así es como representa el ordenador el número 37 en su
sistema binario. Cada una de las cifras de un número binario se
denomina BIT (BInary digiT) y los ordenadores los suelen agrupar el
grupos de 8. Así 8 bits se denomina un byte, 16bits serían 2 bytes y
se denomina word o palabra y así sucesivamente.
El mayor número que podríamos representar en binario con 1
byte (8bits) sería:
b11111111 = 255
Este es el tamaño que el lenguaje C asigna al tipo char, que
sólo puede representar 256 valores distintos, desde 0 a 255. El tipo
int short suele ocupar una palabra es decir, 16 bits. Así con 16
bits el mayor número que podemos representar es:
b1111111111111111 = 65535
NOTA: El tamaño asociado a cada tipo de datos es muy
específico de cada compilador/ordenador. No debería darse nada por
supuesto...
Los números en binario rápidamente se hacen muy largos por
ello se utilizan otros sistemas de numeración que permitan una
escritura más compacta sin perter la información binaria en gran
medida. Esto sistemas son en general sistemas con bases que son
potencias de dos. Así tenemos el sistema octal (base 8) y el sistema
hexadecimal (base 16). Este último es el más ampliamente usado,
disponemos de 16 cifras de 0 a F(15) y la característica más
importante de este sistema es que cada cifra hexadecimal, representa
cuatro bits binarios, con lo cual el paso de un sistema al otro es
extremadamente fácil.
Volvamos ahora a la instrucción anteriormente indicada
mi_var.entero = 0x00f10;
Si pasamos este número a binario obtenemos:
0 -> 0000
f -> 1111 -> 15 en decimal
1 -> 0001 -> 1 en decimal
0f10 <-> 0000111100010000 -> 3856 en decimal
Como dijimos anteriormente un char ocupa 8 bits y un int
ocupa 16, como la union los solapa tendríamos un esquema en la
memoria del ordenador como éste:
int 0000111100010000 -> 3856
char 00010000 -> 65 ('A')
Así mi_var.caracter contendrá el valor A, pero mi_var.entero
contendrá el valor 3856.
NOTA: Como ya se indicó en la nota anterior, el tamaño
asignado a cada tipo depende del ordenador y del compilador. Además,
algunos ordenadores almacenan los números en formato Bajo/Alto (los
8 bits e Intel) y otros en formato Alto/Bajo (Motorola, Sparc,
etc.).
Este tipo de estructura se suele utilizar en aplicaciones a
bajo nivel en la que es necesario poder utilizar este tipo de
solapamiento de bits. Como ya se habrá podido comprobar para
compremder mínimamente como funciona esto es necesario bajar mucho
al nivel de la máquina con la consiguiente complicación de la
explicación.
3.2.3 Tipos definidos por el usuario.
Con las palabras clave struct y union, podemos definir
nuevos tipos de variables pero tenemos que indicar estos tipos con
todo su nombre, es decir, struct mi_struct. El lenguaje C dispone de
un comando que nos permite dar el nombre que nosotros deseemos a
cualquier tipo de variable. El comando es typedef y su forma de
utilización es como sigue:
typedef tipo nuevo_tipo
Algunos ejemplos para aclarar las cosas:
typedef unsigned char BYTE;
typedef struct cubo HEXAHEDRO;
Así con estas definiciones una declaración de las siguientes
variables:
BYTE var1,var2;
HEXAEDRO var3;
Sería equivalente a:
unsigned char var1,var2;
struct cubo var3;