17. Tipos de datos estructurados: tabla
Objetivos
- Entender la utilidad de las tablas (arrays, en C) para resolver problemas concretos de manera eficiente.
- Aprender a utilizar tablas correctamente: definición de tablas, acceso directo a un elemento de una tabla, etc.
- Aplicar esquemas para hacer un recorrido sobre todos los elementos de una tabla y para hacer búsquedas dentro de una tabla.
- Comprender la importancia de la ordenación de las tablas.
Introducción
Hemos visto que los vectores son estructuras de una sola dimensión, que pueden guardar n valores de un mismo tipo.
En los ejemplos que ya hemos visto, los vectores se definían de una medida y eso permitía guardar n valores del tipo definido y siempre se guardaban exactamente dicho número de valores.
Ahora bien, en el mundo real en muchas ocasiones nos encontramos que sabemos, por ejemplo, el máximo número de valores que queremos guardar, pero no sabemos cuántos elementos habrá guardados en el vector en un momento dado.
Por ejemplo, supongamos que en una sala caben hasta 250 personas y que a cada persona que entra a la sala se le pide su DNI, que queremos guardar en un vector. Si necesitamos saber si todavía hay espacio y cuántas posiciones libres quedan, necesitamos una variable de tipo entero que lo controle.
El conjunto del vector y el entero que controla la ocupación del vector forman un tipo estructurado al que llamamos tabla.
En esta unidad definiremos las tablas y veremos cómo se trabaja con ellas. Concretamente:
- Cómo definir (declarar) tablas.
- Cómo acceder a cada uno de los elementos de una tabla.
- Cómo insertar elementos en una tabla.
- Cómo recorrer todos los elementos de una tabla.
- Cómo buscar elementos dentro de la tabla.
- Algunos algoritmos para el tratamiento de tablas: ordenación y lectura ordenada.
1. Sintaxis para la declaración (definición) de una tabla
Una tabla es un tipo estructurado de datos. Los elementos que se necesitan para declarar una tabla son los siguientes:
• Un vector que defina la longitud de la tabla y el tipo de elemento que se guardará en la misma. Los elementos pueden ser de cualquier tipo definido previamente. Por ejemplo, podemos definir tablas de tipos:
- predefinidos en el lenguaje algorítmico (integer, real, char, boolean),
- tipos estructurados definidos por el usuario.
• Una variable de tipo entero que se utiliza para indicar el número de elementos que hay en cada momento en la tabla (la ocupación de la tabla).
La declaración que hacemos es la de un tipo estructurado (tupla) que después podemos utilizar para definir variables dentro del algoritmo.
[Ejemplo 17_01]
{constant definition - where length is a constant that defines the length of the vector}
const
MAX_ELEMENTS: integer = length;
end const
{type definition}
type
tExempleTable = record
elements: vector[MAX_ELEMENTS] of integer;
numElements: integer;
end record
end type
{var definition using the type}
var
aTable: tExampleTable;
end var
#define MAX_ELEMENTS length
typedef struct {
int elements[MAX_ELEMENTS];
int numElements;
} tExampleTable;
tExampleTable aTable;
Veamos un par de ejemplos de definición de tablas:
1.1. Ejemplo 17_02
Supongamos que queremos definir variables para guardar un cuadro de control para las puertas de un edificio de un complejo de edificios. Cada elemento de la tabla indica si la puerta correspondiente está abierta o cerrada. Sabemos que cada edificio tiene como máximo 40 puertas.
La declaración de la tabla sería:
const
MAX_GATES: integer = 40;
end const
type
tGates = record
stateGates: vector[MAX_GATES] of boolean;
numGates: integer;
end record
end type
var
building1: tGates;
building2: tGates;
end var
#define MAX_GATES 40
typedef enum { FALSE, TRUE } boolean;
typedef struct {
boolean stateGates[MAX_GATES];
int numGates;
} tGates;
tGates building1;
tGates building2;
1.2. Acceso a los elementos de la tabla
Ya hemos visto en los vectores cómo acceder a un elemento de la tabla. Siguiendo con el ejemplo 1 y, suponiendo que la acción fillTable carga con información los datos en una tabla de tipo tGates, podemos acceder a los diferentes elementos de la tabla de manera similar a como lo hacíamos con los vectores, pero teniendo en cuenta que se trata de una tupla.
Veamos diferentes ejemplos para acceder a los elementos de la tabla.
[Ejemplo 17_03]
const
K: integer = 10;
MAX_GATES: integer = 40;
end const
type
tGates = record
stateGates: vector[MAX_GATES] of boolean;
numGates: integer;
end record
end type
{header of fillTable}
action fillTable (inout Building: tGates);
algorithm checkDoors
var
building1: tGates;
building2: tGates;
p:integer;
b: boolean ;
c: boolean = true;
end var
fillTable(building1);
{the following statements treat the element of the table as variables}
{assigns the third element of the table building1 to the variable b}
b:= building1.stateGates[3];
{assigns the value of the variable c to the Kth gate of building1, assuming that K is a constant such that 1 ≤ K≤ 40}
building1.stateGates[K]:= c;
{assigns the value of the first gate of building1 to the gate 2*p +5 as long as 1 ≤ 2*p+5 ≤ 40}
building1.stateGates[2*p+5]:= building1.stateGates[1];
end algorithm
#define K 10
#define MAX_GATES 40
typedef enum { FALSE, TRUE } boolean;
typedef struct {
boolean stateGates[MAX_GATES];
int numGates;
} tGates;
void fillTable (tGates *Building);
int main(int argc, char** argv) {
tGates building1;
tGates building2;
int p;
boolean b;
boolean c = TRUE;
/* the following statements treat the elements of the table as variables */
fillTable(&building1);
/* assigns the third element of the table building1 to the variable b */
b = building1.stateGates[2];
/* assigns the value of the variable c to the kth gate of building1, assuming that k is a constant such that 1 ≤ K ≤ 40 */
building1.stateGates[K-1] = c;
/* assigns the value of the first gate of building1 to the gate 2*p +5 as long as 1 ≤ 2*p+5 ≤ 50 */
building1.stateGates[2*p+5-1] = building1.stateGates[0];
return 0;
}
Comentarios:
- Recordad que en lenguaje algorítmico las tablas se indexan empezando con el número 1 mientras que en C se indexan a partir del 0. Por lo tanto, tened en cuenta que para mantener la misma indexación que tenemos en lenguaje algorítmico hace falta restar 1 al índice de las tablas.
- Hay lenguajes de programación que permiten indexar cogiendo cualquier rango, por ejemplo, del 10 al 60. Por lo tanto, cuando se traduce el diseño de lenguaje algorítmico a lenguaje de programación, siempre es necesario adaptar la indexación al lenguaje de programación concreto que se esté usando.
- Durante la ejecución es importante controlar que el índice siempre esté dentro de los límites esperados para evitar errores durante la ejecución.
1.3. Ejemplo 17_04
Supongamos una empresa que dispone de diversos cines de tipo multisala, cada cine con diversas salas. Sabemos que el cine más grande tiene 20 salas, pero otras tienen menos.
Queremos definir una tabla para guardar la recaudación de cada sala pero que sirva para cualquiera de los cines. Por lo tanto, necesitamos definir una tabla que pueda guardar hasta 20 importes reales. La tabla no siempre se llenará ya que dependerá del número de salas que tenga cada cine.
La declaración será de la siguiente manera:
const
MAX_THEATERS: integer = 20;
end const
type
tTheater = record
collect: vector[MAX_THEATERS] of real;
numTheaters: integer;
end record
end type
var
santalo: tTheater;
sants: tTheater;
end var
/*definition of a constant to indicate the size of the table*/
#define MAX_THEATERS 20
typedef struct {
float collect[MAX_THEATERS];
int numTheaters;
} tTheater;
/* var declaration assuming two movies */
tTheater santalo;
tTheater sants;
2. Inicialización de una tabla
Las variables de tipo tabla, como todas las variables, deben inicializarse antes de ser utilizadas. En el caso de las tablas, la manera de inicializarlas es indicando que está vacía.
Lo hacemos asignado 0 al número de elementos ocupados en la tabla. Siguiendo con el ejemplo 2, si queremos decir que inicialmente los edificios building1 y building2 no tiene recaudación en ninguna sala escribiremos lo siguiente:
[Ejemplo 17_05]
const
MAX_THEATERS: integer = 20;
end const
type
tTheater = record
collect: vector[MAX_THEATERS] of real;
numTheaters: integer;
end record
end type
var
santalo: tTheater;
sants: tTheater;
end var
{table initialitation, setting the number of theater to 0}
santalo.numTheaters := 0;
sant.numTheaters := 0;
#define MAX_THEATERS 20
typedef struct {
float collect[MAX_THEATERS];
int numTheaters;
} tTheater;
/*var declaration*/
tTheater santalo;
tTheater sants;
int main(int argc, char** argv) {
/* table initialitation, setting the number of theather to 0 */
santalo.numTheaters = 0;
sant.numTheaters = 0;
return 0;
}
3. Carga de datos a partir de una secuencia
Una de las operaciones más típicas con las tablas es cargarla con información a base de leer datos del canal estándar de entrada.
Para ver cómo sería el algoritmo, seguimos con el ejemplo 2. Supongamos que queremos leer las recaudaciones de las salas del cine Santalo. Los datos vienen dados como una serie de reales (una secuencia de reales) que leemos del canal estándar y el valor -1.0 indica que es el final de los datos (fin de la secuencia de entrada).
Para ir estructurando un posible algoritmo más completo, que además de leer datos haga otras operaciones, aislaremos la lectura de la información en una acción.
[Ejemplo 17_06]
const
MAX_THEATERS: integer = 20;
END_SEQ: real = -1.0;
end const
type
tTheater = record
collect: vector[MAX_THEATERS] of real;
numTheaters: integer;
end record
end type
action fillTable(inout movieTheater: tTheater)
var
temp: real;
end var
{table initialization}
movieTheater.numTheaters:=0;
temp:= readReal(); {we read the first number}
{iteration while the read number is not -1}
while temp ≠ END_SEQ do
{Save the read number in the table.}
movieTheater.collect[movieTheater.numTheaters+1]:= temp;
movieTheater.numTheaters:= movieTheater.numTheaters + 1;
temp:= readReal();
end while
end action
#define END_SEQ -1
#define MAX_THEATERS 20
typedef struct {
float collect[MAX_THEATERS];
int numTheaters;
} tTheater;
void fillTable(tTheaters *movieTheater) {
/* var definition */
float temp;
/* table initialization */
movieTheater->numTheaters = 0;
scanf("%f", &temp); /* read the first number */
/* iteration while the read number is not -1 */
while (temp != END_SEQ) {
/*Save the read number in the table*/
movieTheater->collect[movieTheater->numTheaters] = temp;
movieTheater->numTheaters = movieTheater->numTheaters + 1;
scanf("%f", &temp);
}
}
Comentarios:
- Fijaos en que cada elemento del vector de la tabla se trata como una variable y, por lo tanto, le podemos asignar un valor o utilizarlo en una expresión. Podéis verlo en las líneas de código que hay dentro de la iteración de la acción fillTable.
- Antes de entrar en la iteración leemos el primer elemento. De esta manera, cuando entremos en la iteración ya podemos comprobar si el elemento es el -1.0 que indica final de los datos (final de secuencia) o no.
- Después iteramos hasta encontrar el final de secuencia. En cada iteración incrementamos el campo que controla el número de elementos que hay en la tabla de tal manera que apunte a la primera casilla libre de la tabla y llenamos dicha casilla con el valor leído.
- A la acción le pasamos un parámetro de entrada/salida de tipo tabla. La acción la rellena con los datos leídos y la devuelve rellena.
- En la traducción a C hemos de tener en cuenta que el índice de la tabla empieza en 0.
- También en la traducción a C, cuando se pasa una estructura como parámetro de entrada/salida para acceder a los campos de la tupla (record) en lugar de usar el punto (.) se utiliza la notación ->.
4. Recorrido de una tabla
Otra operación común con las tablas es tener que hacer algún tipo de operación con cada uno de los elementos de la tabla. Hacerlo implica realizar un recorrido sobre todos los elementos de la tabla. Veamos con un ejemplo sobre cómo se estructura un recorrido.
Seguimos con el ejemplo de los cines. Supongamos que, ahora que ya tenemos la recaudación de cada sala del cine Santalo cargada en la tabla, queremos hacer una simulación de cómo quedaría la recaudación si se aumenta el precio un 20%. Es decir, se quiere una acción que actualice la tabla añadiendo a cada elemento un 20%.
Como antes, aislamos en una acción la operación de recorrer la tabla para multiplicar cada uno de sus elementos por 1,20.
[Ejemplo 17_07]
const
MAX_THEATERS: integer = 20;
END_SEQ: real = -1.0;
end const
type
tTheater = record
collect: vector[MAX_THEATERS] of real;
numTheaters: integer;
end record
end type
action update(inout movieTheater: tTheater)
var
i: integer;
end var
{iteration. We can use a for ... do iteration because we know the exact number of element of the table}
for i:=1 to movieTheater.numTheaters do
movieTheater.collect[i] := movieTheater.collect[i] *1.20;
end for
end action
#define END_SEQ -1
#define MAX_THEATERS 20
typedef struct {
float collect[MAX_THEATERS];
int numTheaters;
} tTheater;
void update (tTheater *movieTheater) {
/* var definition */
int i;
/* iteration. We can use a for ... do iteration because we know the exact number of element of the table */
for (i = 0; i < movieTheater.numTheaters; i++) do
movieTheater->collect[i] = movieTheater->collect[i] *1.20;
}
}
Comentarios:
- Para hacer un recorrido completo, podemos hacerlo utilizando el for ... do para iterar sobre todos los elementos de la tabla ya que sabemos exactamente cuántos elementos hay presentes.
- En la traducción a C, la iteración se hace de 0 a (movieTheater.numScreens -1) ya que, recordemos de nuevo, el índice de las tablas empieza en 0.
4.1. Ejemplo: lectura y recorrido
Con las acciones definidas en los apartados anteriores, ahora podemos escribir un algoritmo que lea del canal estándar la secuencia con la recaudación de las salas del cine, la muestre por el canal estándar, calcule el porcentaje indicado de sus elementos y la vuelva a mostrar por el canal estándar de salida.
Para completar el algoritmo hace falta también una acción para mostrar el contenido de la tabla.
El algoritmo completo quedaría de la siguiente manera:
[Ejemplo 17_08]
const
MAX_THEATERS: integer = 20;
END_SEQ: real = -1.0;
end const
type
tTheater = record
collect: vector[MAX_THEATERS] of real;
numTheaters: integer;
end record
end type
algorithm simulation
var
santalo: tTheaters;
end var
fillTable(santalo);
printTable(santalo);
update(santalo);
printTable(santalo);
end algorithm
action fillTable(inout movieTheater: tTheater)
var
i: integer;
temp: real;
end var
{table initialization}
movieTheater.numTheaters:=0;
temp:= readReal(); {we read the first digit}
{iteration while the read number is not -1}
while temp ≠ END_SEQ do
{Save the read number in the table}
movieTheater.numTheaters:=movieTheater.numTheaters + 1;
movieTheater.collect[movieTheater.numTheaters]:= temp;
temp:= readReal();
end while
end action
action update(inout movieTheater: tTheater)
var
i: integer;
end var
{iteration. We can use a for ... do iteration because we know the exact number of element of the table}
for i:=1 to movieTheater.numTheaters do
movieTheater.collect[i]:= movieTheater.collect[i] * 1.20;
end for
end action
action printTable(in movieTheater: tTheater)
var
i: integer;
end var
{iteration. We can use a for ... do iteration because we know the exact number of element of the table}
for i:=1 to movieTheater.numTheaters do
writeInteger(movieTheater.collect[i]);
end for
end action
#define END_SEQ -1
#define MAX_THEATERS 20
typedef struct {
float collect[MAX_THEATERS];
int numTheaters;
} tTheater;
void fillTable(tTheater *movieTheater) {
/* var definition */
float temp;
/* table initialization */
movieTheater->numTheaters = 0;
scanf("%f", &temp); /* read the first dígit */
/* iteration while the read number is not -1 */
while (temp != END_SEQ) {
/* Save the read number in the table */
movieTheater->collect[movieTheater->numTheaters] = temp;
movieTheater->numTheaters = movieTheater->numTheaters + 1;
scanf("%f", &temp);
}
}
void update(tTheater *movieTheater) {
/* var definition */
int i;
/* iteration. We can use a for ... do iteration because we know the exact number of element of the table */
for (i = 0; i < movieTheater->numTheaters; i++) {
movieTheater->collect[i] = movieTheater->collect[i] *1.20 ;
}
}
void printTable(tTheater movieTheater) {
/* var definition */
int i;
/* iteration. We can use a for ... do iteration because we know the exact number of element of the table */
for (i=0; i< movieTheater.numTheaters; i++) {
printf("%f ", movieTheater.collect[i]);
}
}
int main(int argc, char** argv) {
tTheater santalo;
fillTable(&santalo);
printTable(santalo);
update(&santalo);
printTable(santalo);
return 0;
}
Comentarios:
- Hemos escrito un algoritmo completo que hemos estructurado con acciones donde cada acción hace una operación concreta sobre una tabla de valores de tipo real.
- Las acciones incluyen la inserción de elementos en la tabla y el control de cuántos se han insertado, un recorrido para aumentar la recaudación y otro recorrido para mostrar por el canal estándar los valores guardados en la tabla.
- En la acción de escritura, la tabla se pasa como parámetro solamente de entrada. Fijaos en que en C, en este caso, la notación utilizada para acceder a los campos de la tupla (record) es el punto (.).
5. Búsqueda de un elemento en una tabla
Otra operación que se puede hacer con tablas es buscar si en ella hay algún elemento en concreto. Es decir, realizar una búsqueda de un valor dado.
Vamos a ver cómo se enfocaría dicha búsqueda. Para hacerla, debemos hacer un recorrido de todos los elementos de la tabla, pero a diferencia del algoritmo de recorrido que hemos visto antes, en la búsqueda, cuando encontramos el elemento buscado podemos parar la iteración, y no hace falta continuar buscando. Por lo tanto, en la búsqueda vamos a cambiar el tipo de iteración que utilizamos.
Siguiendo con el ejemplo de los cines, escribimos una acción que busque en la tabla de recaudaciones si ha habido alguna sala con una recaudación superior a un valor dado, que leeremos por el canal estándar, y que devuelva su posición en la tabla o -1 para indicar que no se ha encontrado.
Tendríamos lo siguiente:
[Ejemplo 17_09]
const
MAX_THEATERS: integer = 20;
END_SEQ: real = -1.0;
end const
type
tTheater = record
collect: vector[MAX_THEATERS] of real;
numTheaters: integer;
end record
end type
algorithm simulation
var
movieTheater: tTheaters;
value: real;
position: integer;
end var
fillTable(movieTheater);
value:= readReal();
searchValue(movieTheater, value, position);
writeInteger(postion);
end algorithm
action fillTable(inout movieTheater: tTheater)
var
i: integer;
temp: real;
end var
{table initialization}
movieTheater.numTheaters:=0;
temp:= readReal(); {we read the first digit}
{iteration while the read number is not -1}
while temp ≠ END_SEQ do
{Save the read number in the table}
movieTheater.numTheaters:= movieTheater.numTheaters + 1;
movieTheater.collect[movieTheater.numTheaters]:= temp;
temp:=readReal();
end while
end action
action searchValue(in movieTheater, in value: real, inout position: integer)
var
i: integer;
found: boolean;
end var
{variable initialization. i is set to 1 to start searching in the table at postion 1 and found to false to indicate that so far value has not been found. The inout parameter position is set to -1 by default}
i:= 1;
found:= false;
position:= -1;
{iteration while there still are elements in the table and the value has not been found}
while i≤ movieTheater.numTheaters and not found do
if movieTheater.collect[i] ≥ value then
found:= true;
else
i:=i + 1;
end if
end while
if found then
position := i;
end if
end action
#define END_SEQ -1
#define MAX_THEATERS 20
typedef enum { FALSE, TRUE } boolean;
typedef struct {
float collect[MAX_THEATERS];
int numTheaters;
} tTheater;
void fillTable(tTheater *movieTheater) {
/* var definition */
float temp;
/* table initialization */
movieTheater->numTheaters = 0;
scanf("%f", &temp); /* read the first digit */
/* iteration while the read number is not -1 */
while (temp != END_SEQ) {
/*Save the read number in the table*/
movieTheater->collect[movieTheater->numTheaters] = temp;
movieTheater->numTheaters = movieTheater->numTheaters + 1;
scanf("%f", &temp);
}
}
void searchValue(tTheater movieTheater, float value, int *position) {
int i;
boolean found;
/*variable initialization. i is set to 1 to start searching in the table at postion 1 and found to false to indicate that so far value has not been found. The inout parameter position is set to -1 by default */
i = 0;
found = FALSE;
*position = -1;
/* iteration while there are still elements in the table and the value has not been found */
while (i < movieTheater.numTheaters && !found) {
if (movieTheater.collect[i] >= value) {
found = TRUE;
} else {
i++;
}
}
if (found) {
*position = i;
}
}
int main (int argc, char** argv) {
tTheater movieTheater;
float value;
int position;
fillTable(&movieTheater);
printf("%d", movieTheater.numTheaters);
scanf("%f", &value);
searchValue(movieTheater, value, &position);
printf("%d", position);
return 0;
}
Comentarios:
- Se inicializa el valor de la variable position a -1, que es el valor que se debe retornar si no encontramos el valor buscado.
- Para buscar el elemento hemos hecho una iteración sobre los elementos de la tabla, pero controlando si se encuentra o no el valor buscado. Si se encuentra, se acaba la iteración, no hace falta llegar al final de la tabla. Para hacer este control hemos declarado una variable booleana y hemos utilizado una iteración de tipo while … end while que nos permite finalizar la iteración cuando alguna de las condiciones se cumpla. No podemos usar un for ... end for ya que no sabemos en qué momento podemos encontrar el valor buscado.
- Recordemos de nuevo que en C debemos empezar en la posición 0.
- Fijaos en que el parámetro position es de salida, y por lo tanto en C se debe indicar utilizando el carácter * delante del nombre del parámetro.
6. Ordenación de las tablas
6.1. Inserción ordenada
En los ejemplos anteriores, se ha leído la información de las recaudaciones y se ha insertado en la tabla en el mismo orden en que se iba leyendo. Pero como veremos en el apartado siguiente, hay casos donde es importante disponer de una tabla ordenada por algún concepto para conseguir algoritmos más eficientes, sobre todo si hay que hacer muchas búsquedas sobre los elementos de la tabla.
Siguiendo con el ejemplo de los cines, ahora modificamos la acción de lectura de las recaudaciones de tal manera que se mantenga la tabla siempre ordenada.
[Ejemplo 17_10]
const
MAX_THEATERS: integer = 20;
END_SEQ: real = -1.0;
end const
type
tTheater = record
collect: vector[MAX_THEATERS] of real;
numTheaters: integer;
end record
end type
action fillTable(inout movieTheater: tTheater)
var
i, j: integer;
found: boolean;
temp: real;
end var
{table initialization}
movieTheater.numTheaters:=0;
temp:= readReal(); {we read the first digit}
{iteration while the read number is not -1}
while temp ≠ END_SEQ do
{find the right location}
i:=1;
found:=false;
{search for the right position}
while i ≤ movieTheater.numTheaters and not found do
if movieTheater.collect[i] ≤ value then
i:=i+1;
else
found:= true;
end if
end while
{all the values to the right of the position found must be moved to one position to the right}
for j:=movieTheaters.numTheaters to i step -1 do
movieTheater.collect[j+1]:= movieTheater.collect[j];
end for
{insert new value}
movieTheater.collect[i]:= temp;
movieTheaters.numTheaters:= movieTheaters.numTheaters + 1
temp:= readReal();
end while
end action
#define END_SEQ -1
#define MAX_THEATERS 20
typedef enum { FALSE, TRUE } boolean;
typedef struct {
float collect[MAX_THEATERS];
int numTheaters;
} tTheater;
void fillTable(tTheater *movieTheater) {
/* var definition */
float temp;
int i, j;
boolean found;
/* table initialization */
movieTheater->numTheaters =0;
scanf("%f", &temp); /* read the first digit */
/* iteration while the read number is not -1 */
while (temp !=END_SEQ) {
i=0;
found = FALSE;
while (i < movieTheater->numTheaters && ! found) {
if (movieTheater->collect[i] <= temp) {
i__;
} else {
found = TRUE;
}
}
/* move values to the right */
for (j = movieTheater->numTheaters; j >= i ; j--) {
movieTheater->collect[j ] = movieTheater->collect[j-1];
}
/* insert new value */
movieTheater->collect[i] = temp;
movieTheater->numTheaters = movieTheater->numTheaters _ 1 ;
scanf("%f", &temp);
}
}
int main (int argc, char** argv) {
tTheater santalo;
int i;
fillTable(&santalo);
for (i = 0; i < santalo.numTheaters; i__) {
printf("%f ", santalo.collect[i]);
}
return 0;
}
Comentarios:
- Para mantener la tabla ordenada cada vez que se inserte un valor nuevo, primero es necesario buscar el lugar adecuado que le corresponde según los valores que ya hay en la tabla y el que queremos insertar. Para encontrarlo usamos una búsqueda, que corresponde al while más interno.
- Una vez encontrado el sitio correcto, es necesario desplazar hacia la derecha 1 casilla todos los elementos que quedan a la derecha del punto donde se debe insertar. Para hacerlo, usamos una iteración de tipo for, ya que sabemos cuántos elementos se deben mover.
- En el algoritmo hemos supuesto que en la secuencia de entrada nunca habrá más números de los permitidos. Si no se sabe con seguridad, sería necesario añadir al algoritmo un control para evitar que se intente insertar un elemento fuera del rango de la tabla.
6.2. Algoritmo de ordenación
La ordenación de las tablas es un tema que requeriría toda una unidad para tratarlo en profundidad ya que hay diversos algoritmos de ordenación, algunos de ellos muy sofisticados. Presentarlos, entenderlos y compararlos queda fuera del alcance de esta asignatura.
Pero presentamos uno fácil de entender, aunque no sea de los más eficientes.
Si la tabla tiene n elementos, el algoritmo consiste en iterar n veces de la siguiente manera:
- La primera iteración es un recorrido por toda la tabla para encontrar el elemento menor. Cuando se ha identificado, se intercambian los elementos de la posición 1 y la posición del más pequeño, de tal manera que al acabar la primera iteración sabemos que el primer elemento de la tabla es el menor de todos.
- En la segunda iteración ya no hace falta recorrer toda la tabla, sino que podemos empezar en el segundo elemento y hacer el mismo proceso que hemos hecho en la iteración anterior, pero intercambiando el nuevo valor más pequeño con el que hay en la posición 2.
- En la tercera iteración se repite el procedimiento, pero empezando en la tercera posición de la tabla.
- Y así se repite el procedimiento hasta la última iteración en la que solamente nos queda un elemento.
El estado de la tabla después de cada iteración sería la que podemos ver en el siguiente gráfico, donde se han marcado en verde los valores que se intercambian en cada iteración:
Siguiendo con el ejemplo de los cines, rellenamos la tabla con las recaudaciones usando el algoritmo inicial y lo ordenamos con el algoritmo que acabamos de explicar.
[Ejemplo 17_11]
const
MAX_THEATERS: integer = 20;
END_SEQ: real = -1.0;
end const
type
tTheater = record
collect: vector[MAX_THEATERS] of real;
numTheaters: integer;
end record
end type
algorithm simulation
var
santalo: tTheaters;
end var
fillTable(santalo);
sort(santalo);
end algorithm
action fillTable(inout movieTheater:tTheater)
var
i: integer;
temp: real;
end var
{table initialization}
movieTheater.numTheater:=0;
temp:= readReal(); {we read the first dígit}
{iteration while the read number is not -1}
while temp ≠ END_SEQ do
{Save the read number in the table}
movieTheater.numTheater:=seqN movieTheater.numTheater + 1;
movieTheater.collect[movieTheater.numTheater]:= temp;
temp:= readReal();
end while
end action
action sort(inout movieTheater: tTheater)
var
i, j, posMin: integer;
aux:integer;
end var
i:=1;
while i <movieTheater.numTheaters do
posMin:=i;
j:= i + 1;
while j ≤ movieTheater.numTheaters do
if movieTheaters.collect[j] < movieTheaters.collect[posMin] then
posMin:=j;
end if
j:= j + 1;
end while
aux:= movieTheaters.collect[posMin];
movieTheaters.collect[posMin]:= movieTheaters.collect[i];
movieTheaters.collect[i]:= aux;
i:= i +1;
end while
end action
#define END_SEQ -1
#define MAX_THEATERS 20
typedef struct {
float collect[MAX_THEATERS];
int numTheaters;
} tTheater;
void fillTable(tTheater * movieTheater) {
/* var definition */
int i;
float temp;
/* table initialization */
movieTheater->numTheaters = 0;
scanf("%f", &temp); /* read the first digit */
/* iteration while the read number is not -1 */
while (temp !=END_SEQ) {
/*Save the read number in the table*/
movieTheater->collect[movieTheater->numTheaters] = temp;
movieTheater->numTheaters = movieTheater->numTheaters + 1;
scanf("%f", &temp);
}
}
void sort (tTheater *movieTheater) {
/* var definition */
int i, j, posMin;
int aux;
i=0;
while (i < movieTheater->numTheaters) {
posMin=i;
j=i+1;
while (j < movieTheater->numTheaters) {
if (movieTheater->collect[j] < movieTheater->collect[posMin]) {
posMin=j;
}
j=j+1;
}
aux = movieTheater->collect[posMin];
movieTheater->collect[posMin] = movieTheater->collect[i];
movieTheater->collect[i] = aux;
i = i +1;
}
}
int main (int argc, char** argv) {
tTheater santalo;
int i;
fillTable(&santalo);
sort(&santalo);
for (i = 0; i < santalo.numTheaters; i++) {
printf("%f ", santalo.collect[i]);
}
return 0;
}
6.3. Importancia del orden en las tablas
Hemos visto cómo se pueden buscar valores dentro de una tabla. Si analizamos el algoritmo de búsqueda que hemos usado, podemos observar que, en el peor caso, cuando el elemento buscado no se encuentra en la tabla se debe recorrer toda la tabla para saber si el elemento está o no presente. Este tipo de búsqueda se dice que tiene un orden lineal, ya que lo que hace es recorrer uno a uno todos los elementos de la tabla.
Hay maneras más óptimas de buscar elementos dentro de una tabla, pero requieren que la tabla esté ordenada, cosa que podemos obtener o bien insertando los elementos en la tabla de forma ordenada o bien ordenando la tabla posteriormente.
Si la tabla está ordenada, la búsqueda se puede plantear de otra manera. No empezamos la búsqueda en la primera posición de la tabla, sino que empezamos por en medio. El proceso es el siguiente:
1. Calculamos la posición que está en medio de la tabla.
2. Comparamos su contenido con el valor buscado.
3. Si el contenido es el valor buscado, se acaba la búsqueda. Si no, hacemos lo siguiente.
3.1. Si el elemento del medio es mayor que el buscado, podemos descartar la segunda mitad de la tabla. Si está el elemento, lo debemos buscar en la primera mitad (parte izquierda).
3.2. En caso contrario, descartamos la primera mitad, ya que, si está el elemento, estará en la segunda mitad.
4. Aplicamos el mismo procedimiento (volvemos al punto 1) pero trabajando solamente con la parte de la tabla que no hemos descartado.
6.3.1. Ejemplo 17_12
Supongamos que buscamos el valor 400 en la siguiente tabla
- Buscamos la posición que queda en medio de la tabla. En este caso será la posición 6.
2. Comparamos su contenido con el valor buscado, en este caso sería comparar el valor 200 con el 400.
3. Dado que el valor buscado es mayor que el contenido de la posición 6, sabemos con certeza que si el valor buscado está en la tabla, debe estar en la parte derecha, es decir, entre las posiciones 7 y 11.
4. Repetimos el proceso, pero solamente con la parte derecha de la tabla.
5. Ahora calculamos la posición central entre las posiciones 7 y 11, que será la posición 9.
6. Volvemos a repetir la comparación. Es decir, comparamos el contenido de la posición 9 con el valor buscado. En este caso sería comparar el valor de la posición 9 que es 457 con el buscado, que es 400.
7. Como el valor buscado es menor que el de la casilla 9, sabemos que si el valor buscado está en la tabla, debe estar en la parte izquierda del trozo donde hemos buscado. Es decir, entre las posiciones 7 y 8.
8. Volvemos a calcular el punto medio. Como no hay media exacta, cogemos la más próxima, que será la posición 7.
9. Comparamos con el contenido de la posición 7.
10. Como el valor buscado es mayor tenemos que coger la otra mitad de la tabla, que se limita a la posición 8.
11. Comparamos los valores y como tampoco son iguales y ya no quedan casillas por mirar, podemos asegurar que el valor buscado no se encuentra en la tabla.
Podemos ver que en lugar de tener que hacer 11 comparaciones para decidir que el valor buscado no está en la tabla, solamente han sido necesarias 4.
En este ejemplo teníamos pocos elementos, pero cuando las tablas son muy grandes, este tipo de búsqueda, llamada búsqueda dicotómica, es mucho más eficiente.
6.3.2. Ejemplo 17_13
Siguiendo con el ejemplo de los cines, supongamos que tenemos un cine y queremos buscar si ha habido alguna sala con una recaudación de 100€. En el ejemplo supondremos que la tabla está ordenada.
const
MAX_THEATERS: integer = 20;
end const
type
tTheater = record
collect: vector[MAX_THEATERS] of real;
numTheaters: integer;
end record
end type
action searchValue(in movieTheater:tTheater, in value: real, inout position: integer)
var
i: integer;
first, last, middle:integer;
end var
first:= 1;
position:= -1;
last:= movieTheater.numTheaters;
while ( first≠last) do
middle:= (first + last) div 2;
if movieTheater.collect[middle] < value then
first:= middle + 1;
else
last:=middle;
end if
end while
if movieTheater.collect[first] = value then
position:= first;
end if
end action
/* type definition for a table of 20 elements */
#define MAX_THEATERS 20
typedef struct {
float collect[MAX_THEATERS];
int numTheaters;
} tTheater;
void searchValue(tTheater movieTheater, float value, int *position) {
int i;
int first, last, middle;
first= 0;
*position= -1;
last= movieTheater.numTheaters-1;
while (first != last) {
middle = (first + last) / 2;
if (movieTheater.collect[middle] < value) {
first= middle + 1;
} else {
last=middle;
}
}
if (movieTheater.collect[first] == value) {
*position= first;
}
}
7. Tablas de tipos estructurados
7.1. Tablas de tuplas
Durante toda la unidad hemos estado utilizando una tabla de valores reales, pero las tablas pueden ser de cualquier tipo de datos, ya sean tipos básicos del lenguaje de programación o tipos estructurados definidos por el usuario.
Siguiendo con el ejemplo de los cines, podemos suponer que, además de la recaudación, queremos guardar más información de cada sala.
Tal como hemos trabajado hasta ahora, podríamos suponer que la recaudación de la posición 1 correspondía a la sala1, la de la 2 a la sala2, etc. Pero cuando hemos ordenado los importes, hemos perdido esta información. Ya no sabemos a qué salas corresponden cada uno de los importes. Ahora bien, si definimos primero una tupla con información de la sala, por ejemplo una tupla que tenga un entero para la capacidad de la sala, una cadena de caracteres para identificar el nombre de la sala, un real para la recaudación y la fecha de la recaudación, podemos definir una tabla de este tipo de tal manera que si movemos los elementos dentro de la tabla no perdemos información ya que la recaudación irá siempre ligada al nombre de la sala.
Veamos cómo quedaría la definición (declaración) y acceso a los elementos de la nueva tabla:
[Ejemplo 17_14]
const
MAX_THEATERS: integer = 20;
end const
type
{declaration of a type for dates}
tDate = record
day: integer;
month: integer;
year: integer;
end record;
{declaration of type for theater information}
tTheaterDescription = record
name: tString;
capaciy:integer;
collect: real;
date: tDate;
end record
{table with the information of each theater}
tTheater = record
movieTheaters: vector[MAX_THEATERS] of tTheaterDescription;
numTheaters: integer;
end record
end type
var
santalo: tTheater;
k: integer;
end var
{we can access the information in the folowing way}
{to access to the name of the third theater in santalo}
santalo.movieTheater[3].name;
{to access to the filed collect of the k th theater in santalo}
santalo.movieTheaters[k].collect;
{to access to the capacity of the last theater stored in the table santalo}
santalo.movieTheaters[santalo.numTheaters].capacity;
#define MAX_THEATERS 20
typedef struct {
int day;
int month;
int year;
} tDate;
typedef struct {
tString name;
int capaciy;
float collect;
tDate date;
} tTheaterDescription;
typedef struct {
tTheaterDescription movieTheathers[MAX_THEATERS];
int numTheaters;
} tTheater;
int main (int argc, char** argv) {
tTheater santalo;
int k;
/* we can access to be information in the folowing way */
/* to access to the name of the third theater in santalo */
santalo.movieTheater[3].name;
/* to access to the filed collect of the k th. theater in santalo */
santalo.movieTheaters[k].collect;
/* to access to the capacity of the last theater stored in the table santalo */
santalo.movieTheaters[santalo.numTheaters].capacity;
return 0;
}
Comentarios:
- Podemos ver que se ha definido una tabla como se había hecho anteriormente, pero ahora cada elemento de la tabla es una estructura con diversos campos.
- Dada una variable del tipo tTheater, podemos acceder a toda la información siguiendo la notación utilizada en las unidades anteriores para las tablas y las tuplas.
7.2. Tabla de tablas
Un caso concreto de tablas de tipos estructurados se da cuando el tipo definido es otra tabla.
Siguiendo con el ejemplo de los cines, hasta ahora hemos declarado y utilizado una variable de tipo tTheater de manera individual, pero lo más normal es que se quiera mantener la información de todos los cines en una única variable para facilitar su uso. Podemos definir un nuevo tipo de tabla, donde cada elemento sea una tabla con la recaudación de las salas de cada cine.
Para declararlo supondremos que, como máximo, la empresa tendrá 15 cines. La declaración sería la siguiente:
[Ejemplo 17_15]
const
MAX_THEATERS: integer = 20;
MAX_MOVIES: integer = 15;
end const
type
{declaration of a type for dates}
tDate = record
day: integer;
month: integer;
year: integer;
end record
{declaration of type for theater information}
tTheaterDescription = record
name: tString;
capaciy: integer;
collect: real;
date: tDate;
end record
{table with the information of each theater}
tTheater = record
movieTheaters: vector[MAX_THEATERS] of tTheaterDescription;
numTheaters: integer;
end record
{declaration of a table of tTheater}
tCompany = record
movies: vector[MAX_MOVIES] of tTheater;
numMovies: integer;
end record
end type
var
theMovieCompany: tCompany;
m, k: integer;
end var
{we can access the information in the folowing way}
{to access to the name of the third theater of the first movie}
theMovieCompany.movies[1].movieTheaters[3].name;
{to access to the filed collect of the k th theater of the m th movie}
theMovieCompany.movies[m].movieTheaters[k].collect;
{to access to the capacity of the last theater of the last movie}
theMovieCompany.movies[theMovieCompany.numMovies].movieTheaters[theMovieCompany.movies[theMovieCompany.numMovies].numTheaters].capacity;
#define MAX_THEATERS 20
#define MAX_MOVIES 15
typedef struct {
int day;
int month;
int year;
} tDate;
typedef struct {
tString name;
int capaciy;
float collect;
tDate date;
} tTheaterDescription;
typedef struct {
tTheaterDescription movieTheathers[MAX_THEATERS];
int numTheaters;
} tTheater;
/* declaration of a table of tTheater */
typedef struct {
tTheater movies [MAX_MOVIES];
int numMovies;
} tCompany;
int main (int argc, char** argv) {
tCompany theMovieCompany;
int m, k;
/* we can access to be information in the folowing way */
/* to access to the name of the third theater of the first movie */
theMovieCompany.movies[1].movieTheaters[3].name;
/* to access to the filed collect of the k th theater of the m th movie */
theMovieCompany.movies[m].movieTheaters[k].collect;
/* to access to the capacity of the last theater of the last movie */
theMovieCompany.movies[theMovieCompany.numMovies].movieTheaters[theMovieCompany.movies[theMovieCompany.numMovies].numTheaters].capacity;
return 0;
}
Resumen
La unidad presenta el concepto de tabla como una extensión del vector en el que se mantiene información sobre la ocupación de la tabla.
Mediante ejemplos, hemos visto cómo utilizar las tablas:
- La inicialización de una tabla.
- La lectura de datos y su inserción en la tabla.
- El recorrido sobre todos los elementos de una tabla.
- La búsqueda de elementos en una tabla.
- Un algoritmo para la ordenación de una tabla.
- La importancia del orden en las tablas.
- Tablas de tipos estructurados.