Taules
Objectius
- Entendre la utilitat de les taules (arrays, en C) per a resoldre problemes concrets de manera eficient.
- Aprendre a utilitzar taules correctament: definició de taules, accés directe a un element d’una taula, etc.
- Aplicar esquemes per a fer un recorregut sobre tots els elements d’una taula i per a fer cerques dins d’una taula.
- Comprendre la importància de l’ordenació de les taules.
Introducció
Hem vist que els vectors són estructures d’una sola dimensió, que poden guardar n valors d’un mateix tipus.
En els exemples que ja hem vist, els vectors es definien d’una mesura i això permetia guardar n valors del tipus definit i sempre es guardaven exactament aquest nombre de valors.
Ara bé, al món real en moltes ocasions ens trobem que sabem, per exemple, el màxim nombre de valors que volem guardar, però no sabem quants elements hi haurà guardats en el vector en un moment donat.
Per exemple, suposem que en una sala hi caben fins a dues-centes cinquanta persones i que a cada persona que entra a la sala se li demana el seu DNI, que volem guardar en un vector. Si necessitem saber si encara hi ha espai i quantes posicions lliures queden, necessitem una variable de tipus enter que ho controli.
El conjunt del vector i l’enter que controla l’ocupació del vector formen un tipus estructurat al que anomenem taula.
En aquesta unitat definirem les taules i veurem com s’hi treballa. Concretament:
- Com definir (declarar) taules.
- Com accedir a cadascun dels elements d’una taula.
- Com inserir elements en una taula.
- Com recórrer tots els elements d’una taula.
- Com buscar elements dins de la taula.
- Alguns algorismes per al tractament de taules: ordenació i lectura ordenada.
1. Sintaxi per a la declaració (definició) d’una taula
Una taula és un tipus estructurat de dades. Els elements que es necessiten per a declarar una taula són els següents:
• Un vector que defineixi la longitud de la taula i el tipus d’element que s’hi guardarà. Els elements poden ser de qualsevol tipus definit prèviament. Per exemple, podem definir taules de tipus:
- predefinits en el llenguatge algorísmic (integer, real, char, boolean),
- tipus estructurats definits per l’usuari.
• Una variable de tipus enter que s’utilitza per a indicar el nombre d’elements que hi ha a cada moment a la taula (l’ocupació de la taula).
La declaració que fem és la d’un tipus estructurat (taula) que després podem utilitzar per a definir variables dins de l’algorisme.
[Exemple 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;
Vegem un parell d’exemples de definició de taules.
1.1. Exemple 17_02
Suposem que volem definir variables per a guardar un quadre de control per a les portes d’un edifici d’un complex d’edificis. Cada element de la taula indica si la porta corresponent està oberta o tancada. Sabem que cada edifici té com a màxim quaranta portes.
La declaració de la taula seria:
{definition of the maximum number of gates}
const
MAX_GATES: integer = 40;
end const
{definition of the type table}
type
tGates =record
stateGates: vector[MAX_GATES] of boolean;
numGates: integer;
end record
end type
{definition of variables for two buildings}
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. Accés als elements de la taula
Ja hem vist en els vectors com accedir a un element de la taula. Seguint amb l’exemple 1 i, suposant que l’acció fillTable carrega amb informació les dades en una taula de tipus tGates, podem accedir als diferents elements de la taula de manera similar a com ho fèiem amb els vectors, però tenint en compte que es tracta d’una tupla.
Vegem diferents exemples per a accedir als elements de la taula.
[Exemple 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 elements 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 ≤ 40 */
building1.stateGates[2*p+5-1] = building1.stateGates[0];
return 0;
}
Comentaris:
- Recordeu que en llenguatge algorísmic les taules s’indexen començant amb el número 1, mentre que en C s’indexen a partir del 0. Per tant, tingueu en compte que per a mantenir la mateixa indexació que tenim en llenguatge algorísmic cal restar 1 a l’índex de les taules.
2. Hi ha llenguatges de programació que permeten indexar agafant qualsevol rang, per exemple, del 10 al 60. Per tant, quan es tradueix el disseny de llenguatge algorísmic a llenguatge de programació, sempre és necessari adaptar la indexació al llenguatge de programació concret que s’estigui utilitzant.
3. Durant l’execució és important controlar que l’índex sempre estigui dins dels límits esperats per a evitar errors durant l’execució.
1.3. Exemple 17_04
Suposem una empresa que disposa de diversos cinemes de tipus multisala, cada cinema amb diverses sales. Sabem que el cinema més gran té vint sales, però d’altres en tenen menys.
Volem definir una taula per a guardar la recaptació de cada sala però que serveixi per a qualsevol dels cinemes. Per tant, necessitem definir una taula que pugui guardar fins a vint imports reals. La taula no sempre s’omplirà ja que dependrà del nombre de sales que tingui cada cinema.
La declaració serà de la manera següent:
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
/*type definition*/
typedef struct {
float collect[MAX_THEATERS];
int numTheaters;
} tTheater;
/* var declaration assuming two movies */
tTheater santalo;
tTheater sants;
2. Inicialització d’una taula
Les variables de tipus taula, com totes les variables, han d’inicialitzar-se abans de ser utilitzades. En el cas de les taules, la manera d’inicialitzar-les és indicant que està buida.
Ho fem assignant 0 al nombre d’elements ocupats a la taula. Seguint amb l’exemple 2, si volem dir que inicialment els edificis building1 i building2 no tenen recaptació a cap sala escriurem el següent:
[Exemple 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 theather 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. Càrrega de dades a partir d’una seqüència
Una de les operacions més típiques amb les taules és carregar-la amb informació a força de llegir dades del canal estàndard d’entrada.
Per a veure com seria l’algorisme, seguim amb l’exemple 2. Suposem que volem llegir les recaptacions de les sales del cinema Santaló. Les dades venen donades com una sèrie de reals (una seqüència de reals) que llegim del canal estàndard i el valor -1.0 indica que és el final de les dades (fi de la seqüència d’entrada).
Per a anar estructurant un possible algorisme més complet, que a més de llegir dades faci altres operacions, aïllarem la lectura de la informació en una acció.
[Exemple 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->numTheater = 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->numTheater = movieTheater->numTheater + 1;
scanf("%f", &temp);
}
}
Comentaris:
- Fixeu-vos en què cada element del vector de la taula es tracta com una variable i, per tant, li podem assignar un valor o utilitzar-lo en una expressió. Podeu veure-ho a les línies de codi que hi ha dins de la iteració de l’acció fillTable.
- Abans d’entrar en la iteració llegim el primer element. D’aquesta manera, quan entrem en la iteració ja podem comprovar si l’element és el -1.0, que indica final de les dades (final de seqüència) o no.
- Després iterem fins a trobar el final de seqüència. En cada iteració incrementem el camp que controla el nombre d’elements que hi ha a la taula, de tal manera que apunti a la primera casella lliure de la taula i omplim aquesta casella amb el valor llegit.
- A l’acció li passem un paràmetre d’entrada/sortida de tipus taula. L’acció l’omple amb les dades llegides i la retorna emplenada.
- A la traducció a C hem de tenir en compte que l’índex de la taula comença a 0.
- També a la traducció a C, quan es passa una estructura com a paràmetre d’entrada/sortida per a accedir als camps de la tupla (record) en lloc d’usar el punt (.) s’utilitza la notació ->
4. Recorregut d’una taula
Una altra operació comuna amb les taules és haver de fer algun tipus d’operació amb cada un dels elements de la taula. Fer-lo implica realitzar un recorregut sobre tots els elements de la taula. Vegem amb un exemple com s’estructura un recorregut.
Seguim amb l’exemple dels cinemes. Suposem que, ara que ja tenim la recaptació de cada sala del cinema Santaló carregada a la taula, volem fer una simulació de com quedaria la recaptació si s’augmenta el preu un 20%. És a dir, es vol una acció que actualitzi la taula afegint a cada element un 20%.
Com abans, aïllem en una acció l’operació de recórrer la taula per a multiplicar cadascun dels seus elements per 1,20.
[Exemple 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++) {
movieTheater->collect[i] = movieTheater->collect[i] *1.20;
}
}
Comentaris:
- Per a fer un recorregut complet, podem fer-lo utilitzant el for ... do per a iterar sobre tots els elements de la taula, ja que sabem exactament quants elements hi ha presents.
- A la traducció a C, la iteració es fa de 0 a (movieTheater.numScreens -1) ja que, recordem-ho de nou, l’índex de les taules comença en 0.
4.1. Exemple: lectura i recorregut
Amb les accions definides als apartats anteriors, ara podem escriure un algorisme que llegeixi del canal estàndard la seqüència amb la recaptació de les sales del cinema, la mostri pel canal estàndard, calculi el percentatge indicat dels seus elements i la torni a mostrar pel canal estàndard de sortida.
Per a completar l’algorisme cal també una acció per a mostrar el contingut de la taula.
L’algorisme complet quedaria de la manera següent:
[Exemple 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 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 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;
}
Comentaris:
- Hem escrit un algorisme complet que hem estructurat amb accions on cada acció fa una operació concreta sobre una taula de valors de tipus real.
- Les accions inclouen la inserció d’elements a la taula i el control de quants se n’han inserit, un recorregut per a augmentar la recaptació i un altre recorregut per a mostrar pel canal estàndard els valors guardats a la taula.
- En l’acció d’escriptura, la taula es passa com a paràmetre solament d’entrada. Fixeu-vos en què en C, en aquest cas, la notació utilitzada per a accedir als camps de la tupla (record) és el punt (.).
5. Cerca d’un element en una taula
Una altra operació que es pot fer amb taules és buscar si en aquestes hi ha algun element en concret. És a dir, realitzar una cerca d’un valor donat.
Ara veurem com s’enfocaria aquesta cerca. Per a fer-la, hem de fer un recorregut de tots els elements de la taula, però a diferència de l’algorisme de recorregut que hem vist abans, en la cerca, quan trobem l’element buscat podem parar la iteració, i no cal continuar buscant. Per tant, en la cerca canviarem el tipus d’iteració que utilitzem.
Seguint amb l’exemple dels cinemes, escrivim una acció que busqui en la taula de recaptacions si hi ha hagut alguna sala amb una recaptació superior a un valor donat, que llegirem pel canal estàndard, i que retorni la seva posició a la taula o -1 per a indicar que no s’ha trobat.
Tindríem el següent:
[Exemple 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: tTheater;
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 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 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;
}
Comentaris:
- S’inicialitza el valor de la variable position a -1, que és el valor que s’ha de retornar si no trobem el valor buscat.
- Per a buscar l’element hem fet una iteració sobre els elements de la taula, però controlant si es troba o no el valor buscat. Si es troba, s’acaba la iteració, no cal arribar al final de la taula. Per a fer aquest control hem declarat una variable booleana i hem utilitzat una iteració de tipus while … end while, que ens permet finalitzar la iteració quan alguna de les condicions es compleixi. No podem utilitzar un for ... end for ja que no sabem en quin moment podem trobar el valor buscat.
- Recordem de nou que en C hem de començar en la posició 0.
- Fixeu-vos que el paràmetre position és de sortida, i per tant en C s’ha d’indicar utilitzant el caràcter * davant del nom del paràmetre.
6. Ordenació de les taules
6.1. Inserció ordenada
En els exemples anteriors, s’ha llegit la informació de les recaptacions i s’ha inserit en la taula en el mateix ordre en què s’anava llegint. Però com veurem a l’apartat següent, hi ha casos on és important disposar d’una taula ordenada per algun concepte per a aconseguir algorismes més eficients, sobretot si cal fer moltes cerques sobre els elements de la taula.
Seguint amb l’exemple dels cinemes, ara modifiquem l’acció de lectura de les recaptacions de tal manera que es mantingui la taula sempre ordenada.
[Exemple 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;
}
Comentaris:
- Per a mantenir la taula ordenada cada vegada que s’insereixi un valor nou, primer és necessari buscar el lloc adequat que li correspon segons els valors que ja hi ha a la taula i el que hi volem inserir. Per a trobar-lo utilitzem una cerca, que correspon al while més intern.
- Una vegada trobat el lloc correcte, cal desplaçar cap a la dreta 1 casella tots els elements que queden a la dreta del punt on s’ha d’inserir. Per a fer-ho, usem una iteració de tipus for, ja que sabem quants elements s’han de moure.
- En l’algorisme hem suposat que en la seqüència d’entrada mai hi haurà més nombres dels permesos. Si no se sap amb seguretat, caldria afegir a l’algorisme un control per a evitar que s’intenti inserir un element fora del rang de la taula.
6.2. Algorisme d’ordenació
L’ordenació de les taules és un tema que requeriria tota una unitat per a tractar-ho en profunditat, ja que hi ha diversos algorismes d’ordenació, alguns d’ells molt sofisticats. Presentar-los, entendre’ls i comparar-los queda fora de l’abast d’aquesta assignatura.
Però en presentem un fàcil d’entendre, encara que no sigui dels més eficients.
Si la taula té n elements, l’algorisme consisteix a iterar n vegades de la següent manera:
- La primera iteració és un recorregut per tota la taula per a trobar l’element menor. Quan s’ha identificat, s’intercanvien els elements de la posició 1 i la posició del més petit, de tal manera que en acabar la primera iteració sabem que el primer element de la taula és el menor de tots.
- En la segona iteració ja no cal recórrer tota la taula, sinó que podem començar en el segon element i fer el mateix procés que hem fet en la iteració anterior, però intercanviant el nou valor més petit amb el que hi ha a la posició 2.
- En la tercera iteració es repeteix el procediment, però començant en la tercera posició de la taula.
- I així es repeteix el procediment fins a l’última iteració en la qual solament ens queda un element.
L’estat de la taula després de cada iteració seria la que podem veure en el gràfic següent, on s’han marcat en verd els valors que s’intercanvien en cada iteració:
Seguint amb l’exemple dels cinemes, emplenem la taula amb les recaptacions usant l’algorisme inicial i l’ordenem amb l’algorisme que acabem d’explicar.
[Exemple 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.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
actionsort(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. Importància de l’ordre en les taules
Hem vist com es poden cercar valors dins d’una taula. Si analitzem l’algorisme de cerca que hem usat, podem observar que, en el pitjor cas, quan l’element buscat no es troba a la taula s’ha de recórrer tota la taula per a saber si l’element hi és o no present. Aquest tipus de cerca es diu que té un ordre lineal, ja que el que fa és recórrer un per un tots els elements de la taula.
Hi ha maneres més òptimes de buscar elements dins d’una taula, però requereixen que la taula estigui ordenada, cosa que podem obtenir o bé inserint els elements en la taula de forma ordenada o bé ordenant la taula posteriorment.
Si la taula està ordenada, la cerca es pot plantejar d’una altra manera. No comencem la cerca en la primera posició de la taula, sinó que començarem pel mig. El procés és el següent:
- Calculem la posició que està al mig de la taula.
2. Comparem el seu contingut amb el valor buscat.
3. Si el contingut és el valor buscat, s’acaba la cerca. Si no, fem el següent.
3.1. Si l’element del mig és major que el buscat, podem descartar la segona meitat de la taula. Si està l’element, l’hem de buscar en la primera meitat (part esquerra).
3.2. En cas contrari, descartem la primera meitat, ja que, si està l’element, estarà en la segona meitat.
4. Apliquem el mateix procediment (tornem al punt 1) però treballant solament amb la part de la taula que no hem descartat.
6.3.1. Exemple 17_12
Suposem que busquem el valor 400 en la taula següent:
- Busquem la posició que queda enmig de la taula. En aquest cas serà la posició 6.
- Comparem el seu contingut amb el valor buscat, en aquest cas seria comparar el valor 200 amb el 400.
- Atès que el valor buscat és major que el contingut de la posició 6, sabem amb certesa que si el valor buscat és a la taula, ha d’estar a la part dreta, és a dir, entre les posicions 7 i 11.
- Repetim el procés, però solament amb la part dreta de la taula.
- Ara calculem la posició central entre les posicions 7 i 11, que serà la posició 9.
- Tornem a repetir la comparació. És a dir, comparem el contingut de la posició 9 amb el valor buscat. En aquest cas seria comparar el valor de la posició 9, que és 457, amb el buscat, que és 400.
- Com que el valor buscat és menor que el de la casella 9, sabem que si el valor buscat està a la taula, ha d’estar a la part esquerra del tros on hem buscat. És a dir, entre les posicions 7 i 8.
- Tornem a calcular el punt mitjà. Com que no hi ha mitjana exacta, agafem la més propera, que serà la posició 7.
- Comparem amb el contingut de la posició 7.
- Com que el valor buscat és major hem d’agafar l’altra meitat de la taula, que es limita a la posició 8.
- Comparem els valors i com que tampoc són iguals i ja no queden caselles per mirar, podem assegurar que el valor buscat no es troba a la taula.
Podem veure que en lloc d’haver de fer 11 comparacions per a decidir que el valor buscat no està a la taula, solament han estat necessàries 4.
En aquest exemple teníem pocs elements, però quan les taules són molt grans, aquest tipus de cerca, anomenada cerca dicotòmica, és molt més eficient.
6.3.2. Exemple 17_13
Seguint amb l’exemple dels cinemes, suposem que tenim un cinema i volem buscar si hi ha hagut alguna sala amb una recaptació de 100€. En l’exemple suposarem que la taula 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. Taules de tipus estructurats
7.1. Taules de tuples
Durant tota la unitat hem estat utilitzant una taula de valors reals, però les taules poden ser de qualsevol tipus de dades, ja siguin tipus bàsics del llenguatge de programació o tipus estructurats definits per l’usuari.
Seguint amb l’exemple dels cinemes, podem suposar que, a més de la recaptació, volem guardar més informació de cada sala.
Tal com hem treballat fins ara, podríem suposar que la recaptació de la posició 1 corresponia a la sala1, la de la 2 a la sala2, etc. Però quan hem ordenat els imports, hem perdut aquesta informació. Ja no sabem a quines sales corresponen cadascun dels imports. Ara bé, si definim primer una tupla amb informació de la sala, per exemple una tupla que tingui un enter per a la capacitat de la sala, una cadena de caràcters per a identificar el nom de la sala, un real per a la recaptació i la data de la recaptació, podem definir una taula d’aquest tipus de tal manera que si movem els elements dins de la taula no perdem informació, ja que la recaptació anirà sempre lligada al nom de la sala.
Vegem com quedaria la definició (declaració) i accés als elements de la nova taula:
[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 of santalo}
santalo.movieTheater[3].name;
{to access to the filed collect of the k th theater of 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 of santalo */
santalo.movieTheater[3].name;
/* to access to the filed collect of the k th. theater of 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;
}
Comentaris:
- Podem veure que s’ha definit una taula com s’havia fet anteriorment, però ara cada element de la taula és una estructura amb diversos camps.
- Donada una variable del tipus tTheater, podem accedir a tota la informació seguint la notació utilitzada en les unitats anteriors per a les taules i les tuples.
7.2. Taula de taules
Un cas concret de taules de tipus estructurats es dona quan el tipus definit és una altra taula.
Seguint amb l’exemple dels cinemes, fins ara hem declarat i utilitzat una variable de tipus tTheater de manera individual, però el més normal és que es vulgui mantenir la informació de tots els cinemes en una única variable per a facilitar-ne l’ús. Podem definir un nou tipus de taula, on cada element sigui una taula amb la recaptació de les sales de cada cinema.
Per a declarar-ho suposarem que, com a màxim, l’empresa tindrà quinze cinemes. La declaració seria la següent:
[Exemple 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
theMovieCo: 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}
theMovieCo.movies[1].movieTheaters[3].name;
{to access to the filed collect of the k th theater of the m th movie}
theMovieCo.movies[m].movieTheaters[k].collect;
{to access to the capacity of the last theater of the last movie}
theMovieCo.movies[theMovieCo.numMovies].movieTheaters[theMovieCo.movies[theMovieCo.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;
typedef struct {
tTheater movies[MAX_MOVIES];
int numMovies;
} tCompany;
int main (int argc, char** argv) {
tCompany theMovieCo;
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 */
theMovieCo.movies[1].movieTheaters[3].name;
/* to access to the filed collect of the k th theater of the m th movie */
theMovieCo.movies[m].movieTheaters[k].collect;
/* to access to the capacity of the last theater of the last movie */
theMovieCo.movies[theMovieCo.numMovies].movieTheaters[theMovieCo.movies[theMovieCo.numMovies].numTheaters].capacity;
return 0;
}
Resum
La unitat presenta el concepte de taula com una extensió del vector en el qual es manté informació sobre l’ocupació de la taula.
Mitjançant exemples, hem vist com utilitzar les taules:
- La inicialització d’una taula.
- La lectura de dades i la seva inserció en la taula.
- El recorregut sobre tots els elements d’una taula.
- La cerca d’elements en una taula.
- Un algorisme per a l’ordenació d’una taula.
- La importància de l’ordre en les taules.
- Taules de tipus estructurats.