Tuples
Objectius
- Entendre el concepte de dada estructurada.
- Accedir i escriure informació en una dada estructurada.
- Identificar la correspondència amb la memòria i la seva representació en aquesta.
Introducció
Havíem vist que les variables eren objectes que emmagatzemaven un valor d’un cert tipus i que durant la seva vida en l’algorisme, o programa, podien canviar el valor que contenien. Això sí, a cada moment només podien emmagatzemar un valor.
En el tema anterior ampliem la potència del concepte de variable en incloure els vectors i les matrius. D’aquesta manera podíem tractar com una unitat una col·lecció de dades homogènia i creàvem vectors d’enters o matrius de reals o d’un altre tipus bàsic.
En aquesta unitat treballarem amb tuples. Es tracta de col·leccions heterogènies de dades, en les quals cada element de la col·lecció pot ser d’un tipus diferent. També veurem com es pot accedir a cadascuna de les dades individuals de la tupla i també com són emmagatzemades a la memòria de l’ordinador.
1. Tipus de dades tupla
Una tupla (record en anglès o també struct) és un objecte que conté altres objectes que denominarem camps. Cadascun dels camps té un nom per a identificar-lo i és d’un tipus de dades.
Pensem en la informació bàsica d’un documento d’identitat. Necessitaríem mantenir diverses variables per a emmagatzemar el nom, els cognoms, la data de naixement, el número del DNI i la lletra associada:
[Exemple 12_01]
var
prename: string;
name: string;
birthDay: integer;
birthMonth: integer;
birthYear: integer;
idNumber: integer;
idChar: char;
end var
#define MAX_NAME_LEN 25
int main(int argc, char** argv) {
/* Variable definition*/
char prename[MAX_NAME_LEN];
char name[MAX_NAME_LEN];
int birthDay;
int birthMonth;
int birthYear;
int idNumber;
char idChar;
}
Treballar amb aquestes dades pot ser complicat perquè hem de controlar diverses variables. Copiar, per exemple, la informació d’una sola persona requerirà unes quantes instruccions.
Una tupla permet definir una estructura en la qual poder reunir tota aquesta informació diferent i permet tractar cadascun dels camps individualment o, si ens interessa, tractar tot el conjunt com una unitat.
[Exemple 12_02]
type
people = record
prename: string;
name: string;
birthDay: integer;
birthMonth: integer;
birthYear: integer;
idNumber: integer;
idChar: char;
end record
end type
var
you: people;
end var
#define MAX_NAME_LEN 25
int main(int argc, char** argv) {
typedef struct {
char prename[MAX_NAME_LEN];
char name[MAX_NAME_LEN];
int birthDay;
int birthMonth;
int birthYear;
int idNumber;
char idChar;
} people;
/* Variable definition */
people you;
}
Per a accedir a un camp d’una variable de tipus estructurada en llenguatge algorísmic o en C s’empra el nom de la variable i el nom del camp units pel delimitador ‘.’ (punt). Per exemple, per a referir-nos a l’any de naixement emmagatzemat a you ens referiríem a you.birthYear i you.firstName seria la referència al nom de pila de la persona.
Per exemple, si volem omplir la fitxa d’una persona i escriure-la:
[Exemple 12_03]
algorithm loadData
type
people = record
prename: string;
name: string;
birthDay: integer;
birthMonth: integer;
birthYear: integer;
idNumber: integer;
idChar: char;
end record
end type
var
you: people;
end var
{read phase}
you.prename := readString();
you.name := readString();
you.birthDay := readInteger();
you.birthMonth := readInteger();
you.birthYear := readInteger();
you.idNumber := readInteger();
you.idChar := readChar();
{write phase}
writeString(you.name);
writeString(you.prename);
writeInteger(you.idNumber);
writeChar(you.idChar);
writeInteger(you.birthDay);
writeInteger(you.birthMonth);
writeInteger(you.birthYear);
end algorithm
#define MAX_NAME_LEN 25
int main(int argc, char** argv) {
/* Type definition */
typedef struct {
char prename[MAX_NAME_LEN];
char name[MAX_NAME_LEN];
int birthDay;
int birthMonth;
int birthYear;
int idNumber;
char idChar;
} people;
/* Variable definition */
people you;
/*read phase*/
scanf("%s %s %d %d %d %d %c", you.prename, you.name, &you.birthDay, &you.birthMonth, &you.birthYear, &you.idNumber, &you.idChar);
/*write phase*/
printf("Name: %s, %s \n", you.name, you.prename);
printf("Id: %d-%c \n", you.idNumber, you.idChar);
printf("BirthDay: %d - %d - %d \n", you.birthDay, you.birthMonth, you.birthYear);
return 0;
}
Pot semblar que l’ús de records és incòmode perquè genera uns identificadors molt llargs (nom_variable.nom_camp o nom_variable["nom_camp"]) i segurament per a programes molt senzills i amb poques dades pot ser cert. No obstant això, no cal anar a exemples molt complicats per veure que es faciliten les coses.
Vegem el cas d’haver d’ordenar les dades de dues persones segons la seva data de naixement.
[Exemple 12_04]
algorithm ageOrder
type
people = record
prename: string;
name: string;
birthDay: integer;
birthMonth: integer;
birthYear: integer;
idNumber: integer;
idChar: char;
end record
end type
var
old, young, temp: people;
end var
{read phase first people}
old.prename := readString();
old.name := readString();
old.birthDay := readInteger();
old.birthMonth := readInteger();
old.birthYear := readInteger();
old.idNumber := readInteger();
old.idChar := readChar();
{read phase second people}
young.prename := readString();
young.name := readString();
young.birthDay := readInteger();
young.birthMonth := readInteger();
young.birthYear := readInteger();
young.idNumber := readInteger();
young.idChar := readChar();
{age sort phase}
if ( (old.birthYear > young.birthYear)
or (old.birthYear = young.birthYear and old.birthMonth > young.birthMonth)
or (old.birthYear = young.birthYear and old.birthMonth = young.birthMonth and old.birthDay = young.birthDay) ) then
{copy old to temp}
temp.prename := old.prename;
temp.name := old.name;
temp.birthDay := old.birthDay;
temp.birthMonth := old.birthMonth;
temp.birthYear := old.birthYear;
temp.idNumber := old.idNumber;
temp.idChar := old.idChar;
{copy young to old}
old.prename := young.prename;
old.name := young.name;
old.birthDay := young.birthDay;
old.birthMonth := young.birthMonth;
old.birthYear := young.birthYear;
old.idNumber := young.idNumber;
old.idChar := young.idChar;
{copy temp to young}
young.prename := temp.prename;
young.name := temp.name;
young.birthDay := temp.birthDay;
young.birthMonth := temp.birthMonth;
young.birthYear := temp.birthYear;
young.idNumber := temp.idNumber;
young.idChar := temp.idChar;
end if
{write phase old people}
writeString(old.name);
writeString(old.prename);
writeInteger(old.idNumber);
writeChar(old.idChar);
writeInteger(old.birthDay);
writeInteger(old.birthMonth);
writeInteger(old.birthYear);
{write phase young people}
writeString(young.name);
writeString(young.prename);
writeInteger(young.idNumber);
writeChar(young.idChar);
writeInteger(young.birthDay);
writeInteger(young.birthMonth);
writeInteger(young.birthYear);
end algorithm
#include <string.h>
#define MAX_NAME_LEN 25
int main(int argc, char** argv) {
/* Type definition */
typedef struct {
char prename[MAX_NAME_LEN];
char name[MAX_NAME_LEN];
int birthDay;
int birthMonth;
int birthYear;
int idNumber;
char idChar;
} people;
/* Variable definition */
people young, old, temp;
/*read phase first people*/
scanf("%s %s %d %d %d %d %c", old.prename, old.name, &old.birthDay, &old.birthMonth, &old.birthYear, &old.idNumber, &old.idChar);
/*read phase second people*/
scanf("%s %s %d %d %d %d %c", young.prename, young.name, &young.birthDay, &young.birthMonth, &young.birthYear, &young.idNumber, &young.idChar);
/* age sort phase */
if ( (old.birthYear > young.birthYear)
||( (old.birthYear == young.birthYear) && (old.birthMonth > young.birthMonth))
|| ((old.birthYear == young.birthYear) && (old.birthMonth == young.birthMonth) && ( old.birthDay > young.birthDay))) {
/*copy old to temp*/
strcpy(temp.prename,old.prename);
strcpy(temp.name,old.name);
temp.birthDay = old.birthDay;
temp.birthMonth = old.birthMonth;
temp.birthYear = old.birthYear;
temp.idNumber = old.idNumber;
temp.idChar = old.idChar;
/*copy young to old*/
strcpy(old.prename,young.prename);
strcpy(old.name,young.name);
old.birthDay = young.birthDay;
old.birthMonth = young.birthMonth;
old.birthYear = young.birthYear;
old.idNumber = young.idNumber;
old.idChar = young.idChar;
/*copy temp to young*/
strcpy(young.prename,temp.prename);
strcpy(young.name,temp.name);
young.birthDay = temp.birthDay;
young.birthMonth = temp.birthMonth;
young.birthYear = temp.birthYear;
young.idNumber = temp.idNumber;
young.idChar = temp.idChar;
}
/*write phase old people*/
printf("Name: %s, %s \n", old.name, old.prename);
printf("Id: %d-%c \n", old.idNumber, old.idChar);
printf("BirthDay: %d - %d - %d \n", old.birthDay, old.birthMonth, old.birthYear);
/*write phase young people*/
printf("Name: %s, %s \n", young.name, young.prename);
printf("Id: %d-%c \n", young.idNumber, young.idChar);
printf("BirthDay: %d - %d - %d \n", young.birthDay, young.birthMonth, young.birthYear);
return 0;
}
Tingueu en compte que quan estudiem la modularitat podrem eliminar part del codi que es repeteix. La lectura, escriptura i còpia de les estructures de dades podran estar encapsulades i no serà necessari repetir el codi.
2. Representació en memòria
Tots els camps d’una dada estructurada es mantenen en la memòria ocupant posicions consecutives. Ho podem exemplificar amb una dada més simple que les anteriors, com el que podríem definir per a representar una data dd-mm-aaaa.
[Exemple 12_05]
type
date = record
day: integer;
month: integer;
year: integer;
end record
end type
var
today: date;
end var
int main(int argc, char** argv) {
/* Types definition */
typedef struct {
int day;
int month;
int year;
} date;
/* Variable definition */
date today;
}
La variable today conté tres camps de tipus enter. Si cada camp enter ocupa 4 bytes, la dada estructurada ocupa un total de 12 bytes consecutius. Si la dada s’emmagatzema a la memòria a partir d’una posició X, podríem veure:
Disposició en la qual el primer camp comença on comença el record, el segon camp definit comença 4 bytes més enllà de l’inici, ja que el camp anterior ha ocupat 4 bytes, i el tercer camp està a 8 bytes del principi (perquè els camps anteriors han ocupat 8 bytes).
Si la variable today contenia la data de l’últim dia del segle xx en memòria, tindríem:
Ha de comprendre’s que el lloc dins de la tupla on comença un determinat camp no té cap relació amb el tipus d’aquest camp, només depèn de l’espai ocupat pels camps anteriors.
Si haguéssim definit una tupla per a guardar documents d’identitat, els dos camps serien de tipus diferents:
[Exemple 12_06]
type
dni = record
idNumber: integer;
idChar: char;
end record
end type
var
identification: dni;
end var
int main(int argc, char** argv) {
/* Type definition*/
typedef struct {
int idNumber;
char idChar;
} dni;
/* Variable definition */
dni identification;
}
Com que un caràcter solament ocupa un byte a la memòria, la representació esquemàtica d’aquesta tupla, posada a partir de la posició de memòria X, seria:
Cada camp estaria emmagatzemat ocupant les posicions corresponents al seu tipus base.
Per exemple, pel DNI de valor 12345657-R, la representació seria:
3. Estructures complexes
Hem vist que un tipus estructurat de dades o tupla serveix per a agrupar camps d’informació per a representar algun objecte (per exemple, una persona). Un tipus estructurat de dades pot ser utilitzat com qualsevol altre tipus de dades bàsic i pot contenir qualsevol altre tipus de dades. A continuació, es mostra un exemple de les diferents combinacions possibles.
3.1. Tuples que contenen tuples
Quan es defineix una tupla no hi ha cap limitació per a declarar els seus camps. Res impedeix que un camp d’una tupla pugui ser, per la seva banda, una tupla. De fet, ja hem avançat una mica en aquest sentit perquè portem definits diversos tipus de tuples, però és interessant fixar-se en què les dues últimes que hem definit (date i dni), d’una banda, són tuples útils per si mateixes (en un programa gran que treballi amb dades de persones, molt sovint s’hauran de tractar documents d’identificació i també s’hauran de tractar dates) i la informació que contenen forma part de la tupla people que hem definit al principi.
Si considerem aquesta situació, la definició de people pot simplificar-se si ja tenim definits els tipus date i dni.
[Exemple 12_07]
type
date = record
day: integer;
month: integer;
year: integer;
end record
dni = record
idNumber: integer;
idChar: char;
end record
people = record
prename: string;
name: string;
birth: date;
id: dni;
end record
end type
var
you: people;
end var
#define MAX_NAME_LEN 25
int main(int argc, char** argv) {
typedef struct {
int day;
int month;
int year;
} date;
typedef struct {
int idNumber;
char idChar;
} dni;
typedef struct {
char prename[MAX_NAME_LEN];
char name[MAX_NAME_LEN];
date birth;
dni id;
} people;
/* Variable definition */
people you;
}
L’ús d’aquestes tuples amb tuples (tuples jeràrquiques) obliga també a utilitzar una notació jeràrquica per a accedir a aquests camps.
Posem, per exemple, la variable you del tipus tPeople definit en última instància.
- you.name és el cognom emmagatzemat.
- you.birth és una tupla, és a dir, la col·lecció de tres valors que configuren la data de naixement i, per a arribar a un dels seus camps, s’haurà d’emprar l’operador punt. Per a referir-nos al dia haurem d’emprar you.birth.day; per a fer-ho amb l’any, you.birth.year.
És interessant tenir clar a quin objecte es fa referència a cada moment. Quan emprem you.nom_del_camp estem indicant aquest camp. Si el camp és d’un tipus bàsic, ja tenim accés al valor d’aquest tipus. Si el camp en qüestió és una tupla, tenim accés a la tupla completa i per a arribar a un dels camps haurem d’emprar de nou l’operador punt, seguit del nom del camp al qual es vulgui accedir.
3.2. Vectors de tuples
Si en un programa les dades que fan referència a una entitat (per exemple, una persona) són prou complexos com per a crear tuples, és molt probable que els nostres algorismes o programes hagin de treballar amb col·leccions d’aquest tipus d’objecte. L’estructura de dades adequada per a fer-ho és el vector (o matriu). No hi ha cap problema en crear vectors de tuples.
Vegem-ne un exemple: volem mantenir la informació bàsica dels estudiants d’una aula.
[Exemple 12_08]
type
date = record
day: integer;
month: integer;
year: integer;
end record
dni = record
idNumber: integer;
idChar: char;
end record
people = record
prename: string;
name: string;
birth: date;
id: dni;
end record
end type
var
studentGroup: vector[50] of people;
end var
int main(int argc, char** argv) {
/* Types definition */
typedef struct {
int day;
int month;
int year;
} date;
typedef struct {
int idNumber;
char idChar;
} dni;
typedef struct {
char prename[MAX_NAME_LEN];
char name[MAX_NAME_LEN];
date birth;
dni id;
} people;
/* Variable definition */
people studentGroup[50];
}
També en aquest cas, en fer referència a una posició determinada del vector, ens estarem referint a un record complet i, per a accedir als seus camps, haurem d’emprar el punt i l’identificador del camp. Por exemple:
- studentGroup[12] és la tupla que conté tota la informació de l’estudiant que està a la posició 12 del vector.
- studentGroup[12].name és el camp de text que conté els cognoms de l’estudiant que està a la posició 12 del vector.
- studentGroup[12].birth.year és el camp que conté l’any de naixement de l’estudiant de la posició 12 del vector.
En cas que la declaració de la variable sigui d’una matriu, solament s’haurà de tenir en compte la doble indexació de la matriu. Vegem l’exemple d’una escola que té sis grups de cinquanta estudiants respectivament:
[Exemple 12_09]
type
date = record
day: integer;
month: integer;
year: integer;
end record
dni = record
idNumber: integer;
idChar: char;
end record
people = record
prename: string;
name: string;
birth: date;
id: dni;
end record
end type
var
school: matrix[6][50] of people;
end var
int main(int argc, char** argv) {
/* Types definition */
typedef struct {
int day;
int month;
int year;
} date;
typedef struct {
int idNumber;
char idChar;
} dni;
typedef struct {
char prename[MAX_NAME_LEN];
char name[MAX_NAME_LEN];
date birth;
dni id;
} people;
/* Variable definition */
people school[6][50];
}
En aquest cas, bé en llenguatge algorísmic o en C:
- school[2] fa referència a un vector, un grup complet d’estudiants (el de segona posició).
- school[2][12] fa referència a una tupla, la corresponent a l’estudiant 12 del grup 2.
- school[2][12].name serien els cognoms de l’estudiant 12 del grup 2.
- school[2][12].birth.year seria l’any de naixement de l’estudiant 12 del grup 2.
3.3. Tuples que contenen vectors
De manera similar, moltes vegades en què volem definir tuples per a representar una determinada entitat, trobem que una de les informacions que volem tenir és realment una col·lecció d’informacions més simples. Posem per cas que volem crear una dada estructurada per a mantenir la informació d’una assignatura. Segurament voldrem tenir el nom de l’assignatura, les qualificacions de les cinc activitats d’avaluació contínua (‘A’, ‘B’, etc.), la qualificació de l’examen i la qualificació final. Un record que correspon a aquestes necessitats podria ser:
[Exemple 12_10]
type
subject = record
name: string;
PAC: vector[5] of char;
test: real;
finalMark: real;
end record
end type
var
computerScience: subject;
end var
#define MAX_NAME_LEN 25
int main(int argc, char** argv) {
/* Type definition */
typedef struct {
char name[MAX_NAME_LEN];
char PAC[5];
float test;
float finalMark;
} subject;
/* Variable definition */
subject computerScience;
}
També en aquest cas haurem d'anar amb compte amb les referències:
- computerScience fa referència a la tupla completa; tota la informació de l'assignatura.
- computerScience.PEC fa referència a un vector que conté les qualificacions de totes les PAC.
- computerScience.PEC[3] en llenguatge algorísmic fa referència a la qualificació de l'activitat 3 obtinguda a l'assignatura (recordem que la primera té l'índex 1) i en llenguatge C fa referència a la qualificació de l'activitat 4 obtinguda a l'assignatura (recordem que la primera té l'índex 1).
3.4. I, generalitzant…
Veiem que aquesta estructuració de dades pot anar creixent en funció de les nostres necessitats. Podem crear un record que tingui algun camp on s’emmagatzemi una col·lecció de dades del mateix tipus (un vector) i que cada dada sigui alhora una dada estructurada.
Qualsevol entitat real d’una certa dimensió es pot representar mitjançant una estructura de dades de complexitat creixent. No inclourem el codi, però podem pensar en alguna cosa que ens resulta tan familiar com un hospital (no us penseu, un hospital petitó).
Haurem de guardar:
- Informació sobre la plantilla de metges (les dades personals de cada metge, l’especialitat mèdica, el compte de domiciliació bancària, la nòmina, etc.). Segurament val la pena definir un record per a guardar la informació d’un metge perquè de cada metge volem la mateixa informació. I un vector de records anirà bé per a emmagatzemar tota la plantilla.
- Informació sobre els pacients (les dades personals de cada pacient, el seu número d’assegurança mèdica i la companyia, l’historial mèdic, el compte d’on cobrar els extres de la seva estada, etc.). També sembla lògic utilitzar un vector de records.
- Informació sobre les habitacions (el número de cada habitació, la capacitat, quins pacients l’ocupen, etc.) També té lògica utilitzar un vector de records.
I, si ens fixem en les informacions que hem descrit com a camps de les tuples, veurem que moltes d’aquestes informacions tenen molta probabilitat de ser estructurades, per exemple:
- Les dades personals de metges i de pacients responen a la mateixa estructura, per tant, és convenient definir una tupla com la que hi ha descrita, del tipus tPeople i que podem utilitzar tant en metges com en pacients.
- L’historial mèdic no és més que la seqüència de diagnòstics i tractaments del pacient. Possiblement cada diagnòstic i cada tractament el podrem esquematitzar en un record. I un historial serà un vector de diagnòstics i tractaments.
- Segur que en moltes ocasions hi haurà dates per a emmagatzemar (ingrés en clínica, alta mèdica, etc.), per tant, el record tDate que hem definit serà molt útil, no solament com a integrant de la tupla de tipus tPeople.
I podriem continuar en aquesta tasca de refinament amb el convenciment que, si és necessari, tot un món es pot representar en una dada estructurada.
No obstant això, no siguem tan ambiciosos i creem solament les dades estructurades adequades per al tractament de la nostra informació. Hem de practicar el refinat art d’equilibrar els esforços i els resultats.
Resum
En aquesta unitat hem vist quin és el significat d’una dada estructurada, el record, especialment dedicat a agrupar dades més simples i heterogènies que són els camps i que es distingeixen, cadascun d’ells, per un nom identificador. Hem vist la seva definició en llenguatge algorísmic i també en llenguatge de programació.
També hem vist que l’estructuració de dades es pot fer créixer tantes vegades com sigui necessari i que els camps d’una dada estructurada poden ser també dades complexes, ja siguin per la seva banda records, vectors o matrius. A més, hem vist com referenciar una dada estructurada íntegrament o bé només alguna de les informacions discretes que conté.
Des del vessant més tècnic, també s’ha mostrat de quina manera es mantenen en memòria les dades estructurades i com s’hi localitza la ubicació d’un camp determinat.