19. Tipus abstractes de dades
Objectius
- Entendre el concepte de tipus abstracte de dades (TAD). Què significa i quina és la seva utilitat.
- Entendre els TAD que representen seqüències d’elements. En particular s’estudien: piles, cues i llistes.
Introducció
En aquesta unitat es presenta el concepte de tipus abstracte de dades (TAD). En particular s’introdueixen els TAD per a representar seqüències d’elements com ara: llista, cua i pila. La diferència entre aquests tipus de seqüències ve donada pel tipus d’operacions que els podem aplicar, les quals defineixen el seu comportament. Els TAD que es presenten en aquesta unitat emulen conceptes que trobem fora del món de la programació.
Exemples de llistes poden ser la llista de la compra, el llistat d’estudiants d’una classe o la guia telefònica. Tots aquests exemples tenen en comú que contenen una seqüència d’elements (coses que cal comprar, noms de persones o telèfons) i que en qualsevol moment podem veure i modificar qualsevol dels elements i en qualsevol ordre. Per exemple, si anem a comprar amb una llista de la compra, anirem ratllant els productes que ja hem comprat en l’ordre que els comprem, no en l’ordre en què apareixen a la llista.
Exemples de cues també les trobem al nostre voltant. Per exemple, a l’entrada d’un concert o a la parada de l’autobús. Tots dos exemples consten d’un conjunt de persones una rere l’altra (seqüència). En aquest cas, no obstant això, el comportament és diferent. Entenem que quan arribi una nova persona es posarà sempre darrere de la cua i que la primera persona en sortir de la cua (per a entrar al concert o a l’autobús) serà la primera que ha arribat, o sigui, la que està davant. Aquest comportament conegut com a FIFO (First In First Out) és el que defineix una cua.
Finalment, també estem acostumats a tenir piles al nostre voltant. Per exemple, sobre l’escriptori, on anem acumulant les anotacions de la universitat, o una pila de plats a l’armari. En tots dos casos, tornem a tenir un conjunt d’objectes (fulls d’anotacions o plats) i, en aquest cas, el comportament és diferent. Quan tenim una pila d’objectes, l’objecte que porta més temps a la pila és el de sota de tot i per a arribar-hi cal treure tot el que té damunt. Per tant, si vull agafar un plat d’una pila de plats, hauré d’agafar el que es troba a la part superior, és a dir, l’últim que he deixat a la pila. Aquest comportament conegut com a LIFO (Last In First Out) és el que defineix una pila.
En aquesta unitat veurem com definir estructures de dades que emulen aquests comportaments i quines operacions ens permetran afegir, accedir i eliminar els elements que s’hi troben. Cal tenir present que no veurem cap tipus de dada nova, solament com podem utilitzar les que ja hem vist anteriorment per a emular aquests comportaments.
1. Tipus abstracte de dades (TAD)
Un TAD consisteix en un conjunt de valors (domini) i el conjunt d’operacions que es poden aplicar a aquest conjunt de valors.
El concepte de tipus abstracte de dades és necessari per a poder modelar i representar un objecte mitjançant un tipus de dades de la forma més descriptiva, amb totes les característiques que el defineixin.
El concepte de TAD ja existeix en els llenguatges de programació sota la forma de tipus predefinits. Per exemple, en C, el tipus de dades int té com a domini tots els enters en el rang [MININT, MAXINT] i les operacions que se li apliquen són: suma, resta, producte, quocient i mòdul.
S’agrega la paraula «abstracte» a tipus de dades, per a indicar que la definició del tipus (valors i operacions) no depèn de la seva implementació. És a dir que la definició d’un TAD només depèn del comportament descrit i que la forma en què està implementat és irrellevant per a definir-lo.
En l’exemple anterior del tipus de dades de C int, la definició de l’operació suma ens assegura com ha de comportar-se aquesta operació, sense importar-nos com està implementada l’operació o com està internament representat el nombre enter (representació binària en complement a dos, representació binària amb signe, etc.).
Implementar un TAD significa triar una representació per al conjunt de valors del tipus de dades, així com codificar les seves operacions utilitzant aquesta representació en un llenguatge de programació. És possible tenir diverses implementacions per a un mateix TAD, però donada la definició d’un TAD, el comportament ha de ser sempre el mateix per a qualsevol implementació.
La utilitat de definir TAD sorgeix en dissenyar nous tipus de dades. És a dir, tipus de dades que no existeixen com a predefinides en un llenguatge de programació. D’aquesta forma aconseguim definir nous tipus de dades amb operacions associades. La idea és que el nou TAD només pugui ser manipulat a través de les seves operacions. D’aquesta forma s’aconsegueix transparència i independència de la implementació triada per al TAD.
1.1. Exemples d’especificació i implementació
1.1.1. Exemple 19_01: nombres naturals
El conjunt de valors que engloba aquest TAD són tots els nombres enters majors o iguals a 0. Les operacions que definirem per a aplicar a aquest conjunt són la suma i la divisió.
Implementació:
type
natural = integer;
end type
function suma(x: natural, y: natural): natural
return x_y;
end function
function divisio(x: natural, y: natural): natural
return x div y;
end function
typedef unsigned int natural;
natural suma(natural x, natural y) {
return x_y;
}
natural divisio(natural x, natural y) {
return x/y;
}
En aquesta definició del tipus no s’exclouen els nombres negatius. La responsabilitat del correcte comportament del tipus resideix en la definició de les operacions.
1.1.2. Exemple 19_02: nombres binaris
El conjunt de valors que engloba aquest TAD són tots els nombres en la seva representació binària, és a dir, expressats en base 2. Les operacions que diem que s’apliquen a aquest conjunt de valors són: desplaçamentEsq i complement.
Implementació:
const
MAXBITS: integer:=64;
end const
type
binari: vector[MAXBITS] of boolean;
end type
action desplacamentEsq(inout b: binari, in n: integer)
var
i: integer;
end var
for i:=n_1 to MAXBITS do
b[i-n] := b[i];
end for
for i:=MAXBITS-n to MAXBITS do
b[i] := 0;
end for
end action
action complement(inout b: binari)
var
i: integer;
end var
for i=1 to MAXBITS do
b[i] := not b[i];
end for
end action
#define MAXBITS 64
typedef int binari[MAXBITS];
void desplacamentEsq(binari b, int n) {
int i;
for (i=n; i<MAXBITS; i__) {
b[i-n] = b[i];
}
for (i=MAXBITS-n; i<MAXBITS; i__) {
b[i] = 0;
}
}
void complement(binari b) {
int i;
for (i=0; i<MAXBITS; i__) {
b[i] = (int)!b[i];
}
}
2. TAD per a representar seqüències d’elements
Una seqüència lineal és un conjunt de mida arbitrària d’elements del mateix tipus. Exceptuant el primer i l’últim, cada element té un únic element anterior i un únic posterior. És a dir, que conformen una seqüència lineal.
En parlar sobre què podem fer amb una seqüència, ens referim a les operacions que li podem aplicar. En general un TAD que representa seqüències d’elements posseeix les següents operacions:
- Inicialitza la seqüència.
- Inserir un element en la seqüència.
- Eliminar un element de la seqüència.
- Consultar el valor d’un element en la seqüència.
- Consultar el nombre d'elements de la seqüència.
Les respostes a preguntes com:
- On inserir el nou element?
- Quin element eliminar?
- Quin element es pot consultar?
- Quants elements hi ha?
Són les que defineixen el comportament de les operacions i, per tant, el tipus de seqüència.
En aquesta unitat tractarem els següents TAD per a representar seqüències: piles, cues i llistes.
2.1. El TAD pila (tStack)
2.1.1. Definició
- Una pila és una seqüència lineal d’elements.
- Els elements s’insereixen únicament per un extrem de la seqüència. Per això es diu que és una estructura LIFO (Last In First Out): l’últim a entrar és el primer a sortir.
- La manipulació i accés als elements de la pila es permet solament en un extrem de la seqüència.
Per a comprendre el TAD pila es pot pensar en una pila de llibres dins d’una caixa: el llibre accessible és el que està a sobre de la pila. Per a poder accedir a un llibre al centre de la pila, caldrà retirar tots els llibres que estan al seu damunt. Així mateix, el següent llibre que s’ha d’apilar es col·locarà sobre el llibre que està més amunt.
Exemple:
Considerem l’exemple de la pila de llibres dins d’una caixa. En netejar la caixa, la pila de llibres està buida. Per a veure el funcionament de la pila aplicarem una sèrie d’operacions que es mostren a la figura 1.
Figura 1. Seqüència d’operacions sobre una pila de llibres
2.1.2. Operacions
Les operacions que defineixen el TAD pila, d’ara endavant tStack, es llisten a la taula 1.
Taula 1. Llista d’operacions sobre el TAD tStack
| Operació | Descripció |
|---|---|
| initStack | Inicialitza la pila buida. |
| push | Empila un element a la pila. |
| pop | Desempila un element de la pila. |
| top | Retorna una còpia de l’element situat al topall de la pila, però sense desempilar-lo. |
| isEmptyStack | Retorna vertader si la pila està buida, fals en cas contrari. |
| isFullStack | Retorna vertader si la pila està plena, fals en cas contrari. |
| heightStack | Retorna el nombre d'elements de la pila (alçada). |
2.1.3. Implementació
La implementació proposada es basa en un vector, on tenim un nombre màxim d’elements (MAX). Per a conèixer l’espai disponible de la pila a cada moment es necessita un atribut que indiqui el nombre total d’elements i que anomenarem nelem.
Figura 2. Implementació d’una pila mitjançant un vector
Implementació del tipus:
[Exemple 19_03]
type
tStack = record
A: vector[MAX] of elem; {elem represents the type of the elements in the tStack}
nelem: integer;
end record
end type
typedef struct {
elem A[MAX];
int nelem;
} tStack;
Implementació de les operacions del tipus:
Tant en l’operació d’empilar (push) que es mostra a la figura 3, com en l’operació de desempilar (pop), que es mostra a la figura 4, la manipulació d’elements es realitza per l’extrem final de la seqüència, que és també el topall de la pila.
Figura 3. Implementació de la operació push
Figura 4. Implementació de l'operació pop
Implementació de les operacions
[Exemple 19_04]
action initStack(out s: tStack)
s.nelem := 0;
end action
action push(inout s: tStack, in e: elem)
if s.nelem = MAX then
{error full tStack}
else
s.nelem := s.nelem _ 1;
s.A[s.nelem] := e;
end if
end action
action pop(inout s: tStack)
if s.nelem = 0 then
{error empty tStack}
else
s.nelem := s.nelem - 1;
end if
end action
action top(in s: tStack, out e: elem)
if s.nelem = 0 then
{error empty tStack}
else
e := s.A[s.nelem];
end if
end action
function isEmptyStack(s: tStack): boolean
return s.nelem = 0;
end function
function isFullStack(s: tStack): boolean
return s.nelem = MAX;
end function
function heightStack(s: tStack): integer
return s.nelem;
end function
#include <stdio.h>
#include <stdbool.h>
void initStack(tStack *s) {
s->nelem=0;
}
void push(tStack *s, elem e) {
if (s->nelem == MAX) {
printf("\n Full tStack \n");
} else {
s->A[s->nelem]=e; /* first position in C is 0 */
s->nelem__;
}
}
void pop(tStack *s) {
if (s->nelem == 0) {
printf("\n Empty tStack\n");
} else {
s->nelem--;
}
}
void top(tStack s, elem *e) {
if (s.nelem == 0) {
printf("\n Empty tStack \n");
} else {
*e = s.A[s.nelem-1];
}
}
bool isEmptyStack(tStack s) {
return (s.nelem == 0);
}
bool isFullStack(tStack s) {
return (s.nelem == MAX);
}
int heightStack(tStack s) {
return (s.nelem);
}
2.1.4. Exemple 19_05
Suposem la pila de llibres de l’exemple de la figura 1. Cada llibre disposa d’un codi identificador i un nom. Definim les estructures de dades necessàries per a modelar l’exemple:
type
tBook = record
name: string;
id: integer;
end record
tBox = record
A: vector[MAX] of tBook;
nelem: integer;
end record
end type
#define MAX_NAME_LEN=25
typedef struct {
char[MAX_NAME_LEN] name;
int id;
} tBook;
typedef struct {
tBook A[MAX];
int nelem;
} tBox;
Necessitem implementar una acció que, donada una pila de llibres i el codi d’un llibre, trobi aquest llibre a la pila. En cas de trobar-lo, el retirem de la pila; si no, deixem la pila tal com estava.
[Exemple 19_06]
action findBook(inout s: tBox , in id: integer)
var
b: tBook;
aux: tBox;
found: boolean;
end var
found := false;
initStack(aux);
while not isEmptyStack(s) and not found do
top(s, b);
if b.id ≠ id then
push(aux, b);
else
found := true;
end if
pop(s);
end while
while not isEmptyStack(aux) do
top(aux, b);
push(s, b);
pop(aux);
end while
end action
#include <stdbool.h>
void findBook(tBox *s, int id) {
tBook b;
tBox aux;
bool found;
found = false;
initStack(&aux);
while (!isEmptyStack(*s) && !found) {
top(*s, &b);
if (b.id != id) {
push(&aux, b);
} else {
found = true;
}
pop(s);
}
while (!isEmptyStack(aux)) {
top(aux, &b);
push(s, b);
pop(&aux);
}
}
2.2. El TAD cua (tQueue)
2.2.1. Definició
- Una cua és una seqüència lineal d’elements.
- Els elements s’insereixen pel final de la cua i s’extreuen pel principi de la cua. Per això es diu que és una estructura FIFO (First In First Out): el primer a entrar és el primer a sortir, ja que els elements s’extreuen de la cua en el mateix ordre en el qual s’han inserit.
- La manipulació i l’accés als elements de la cua solament es permet en els extrems.
Per a comprendre el TAD cua es pot pensar en una cua de persones esperant per a comprar una entrada a la taquilla d’un teatre: la primera persona que és a la cua és la primera a ser atesa, les persones que arriben s’uneixen al final de la cua.
Exemple 19_07
Considerem la cua d’una taquilla. Quan la taquilla obre creem la cua buida i, per a veure el seu funcionament, aplicarem una sèrie d’operacions tal com es mostra a la figura 5.
Figura 5. Seqüència d'operacions sobre una cua de persones en una taquilla de teatre.
2.2.2 Operacions
Les operacions que defineixen el TAD cua, d’ara endavant tQueue, es llisten a la taula 2.
Taula 2. Llista d’operacions sobre el TAD tQueue
| Operació | Descripció |
|---|---|
| initQueue | Inicialitza la cua buida. |
| enqueue | Insereix un element a la cua. |
| dequeue | Elimina un element de la cua. |
| head | Retorna l’element situat al començament de la cua. |
| isEmptyQueue | Retorna vertader si la cua està buida, fals en cas contrari. |
| isFullQueue | Retorna vertader si la cua està plena, fals en cas contrari. |
| lengthQueue | Retorna el nombre d'elements de la cua (longitud). |
2.2.3. Implementació
La implementació proposada es basa en un vector, on tenim un nombre màxim d’elements (MAX). Per a conèixer l’espai disponible en la cua a cada moment es necessita un atribut que indiqui el nombre total d’elements i que anomenarem nelem.
Figura 6. Implementació d’una cua mitjançant un vector
Tal com es mostra a la figura 6, el primer element de la cua s’emmagatzema a la posició 1 del vector i l’últim a la posició nelem, que representa el final de la cua.
Implementació del tipus:
type
tQueue = record
A: vector[MAX] of elem;
nelem: integer;
end record
end type
typedef struct {
elem A[MAX];
int nelem;
} tQueue;
Implementació de les operacions:
Els elements es posen a la cua (operació enqueue) pel final d’aquesta i es treuen de la cua (operació dequeue) pel principi d’aquesta (posició 1). Tingueu en compte que cada vegada que s’elimina un element s’han de desplaçar tots els elements de la cua una posició cap a l’esquerra segons es mostra a la figura 7.
Figura 7. Implementació de l’operació dequeue
Implementació de les operacions:
[Exemple 19_08]
action initQueue(out q: tQueue)
q.nelem := 0;
end action
action enqueue(inout q: tQueue, in e: elem)
if q.nelem = MAX then
{error full_queue}
else
q.nelem := q.nelem _ 1;
q.A[q.nelem] := e;
end if
end action
action dequeue(inout q: tQueue)
var
i: integer;
end var
if q.nelem = 0 then
{error empty_queue}
else
for i:=1 to q.nelem-1 do
q.A[i] := q.A[i_1];
end for
q.nelem := q.nelem - 1;
end if
end action
action head(in q: tQueue, out e: elem)
if q.nelem = 0 then
{error empty_queue}
else
e := q.A[1];
end if
end action
function isEmptyQueue(q: tQueue): boolean
return (q.nelem = 0);
end function
function isFullQueue(q: tQueue): boolean
return (q.nelem = MAX);
end function
function lengthQueue(q: tQueue): integer
return (q.nelem);
end function
#include <stdbool.h>
void initQueue(tQueue *q) {
q->nelem=0;
}
void enqueue(tQueue *q, elem e) {
if (q->nelem == MAX) {
printf("\n Full queue \n");
} else {
q->A[q->nelem]=e; /* first position in C is 0 */
q->nelem__;
}
}
void dequeue(tQueue *q) {
int i;
if (q->nelem == 0) {
printf("\n Empty queue\n");
} else {
for (i=0; i < q->nelem-1; i__) {
q->A[i] = q->A[i_1];
}
q->nelem--;
}
}
void head(tQueue q, elem *e) {
if (q.nelem == 0) {
printf("\n Empty tQueue \n");
} else {
*e = q.A[0];
}
}
bool isEmptyQueue(tQueue q) {
return (q.nelem == 0);
}
bool isFullQueue(tQueue q) {
return (q.nelem == MAX);
}
int lengthQueue(tQueue q) {
return (q.nelem);
}
2.2.4 Exemple 19_09
Suposem la cua de la taquilla de l’exemple de la figura 5. Cada client de la cua té associat l’ordinal a la cua des que va obrir la taquilla i la quantitat d’entrades que desitja adquirir. Definim les estructures de dades necessàries per a modelar l’exemple:
type
tClient = record
num: integer;
quantity: integer;
end record
tTicketWin = record
A: vector[MAX] of tClient;
nelem: integer;
end record
end type
typedef struct {
int num;
int quantity;
} tClient;
typedef struct {
tClient A[MAX];
int nelem;
} tTicketWin;
Necessitem implementar una acció que atengui el primer client de la cua a la taquilla. L’acció rep com a paràmetres la cua q de clients i un nombre available que indica la disponibilitat d’entrades. En cas d’haver-hi prou entrades disponibles, s’actualitza la quantitat d’entrades disponibles i es retorna el valor vertader al paràmetre sold. Una vegada el client és atès, s’elimina de la cua.
[Exemple 19_10]
action serveClient(inout q: tTicketWin, inout available: integer, out sold: boolean)
var
c: tClient;
end var
sold := false;
if not isEmptyQueue(q) then
head(q, c);
if c.quantity ≤ available then
available := available - c.quantity;
sold := true;
end if
dequeue(q);
end if
end action
#include <stdbool.h>
void serveClient(tTicketWin *q, int *available, bool *sold) {
tClient c;
*sold = false;
if (!isEmptyQueue(*q)) {
head(*q, &c);
if (c.quantity <= *available) {
*available = *available - c.quantity;
*sold = true;
}
dequeue(q);
}
}
2.3. El TAD llista (tList)
2.3.1. Definició
- Una llista és una seqüència lineal d’elements.
- És possible inserir, eliminar i consultar elements en qualsevol posició de la seqüència.
Per a comprendre el TAD llista es pot pensar en la llista de compra del supermercat, en una llista d’adreces, en una llista de desitjos per al nou any...
Exemple 19_11
Considerarem la llista de la compra: llet, sucre, arròs; on la llet és el primer element. Per a construir la llista, primer creem una llista buida i després apliquem una sèrie d’operacions fins a obtenir la llista completa, tal com es mostra a la figura 8.
Figura 8. Seqüència d’operacions per a construir una llista de la compra del supermercat
2.3.2. Operacions
Les operacions que defineixen el TAD llista, d’ara endavant list, es detallen a la taula 3.
Taula 3. Llista d’operacions sobre el TAD tList.
| Operació | Descripció |
|---|---|
| initList | Inicialitza la llista buida. |
| insert | Insereix un element a la llista. |
| delete | Elimina un element de la llista. |
| get | Retorna l’element situat a una posició donada de la llista. |
| isEnd | Retorna vertader si la posició donada és posterior a l’última, fals en cas contrari. |
| isEmptyList | Retorna vertader si la llista està buida, fals en cas contrari. |
| isFullList | Retorna vertader si la llista està plena, fals en cas contrari. |
| lengthList | Retorna el nombre d'elements de la llista (llargada). |
2.3.3. Implementació
La implementació proposada es basa en un vector, on tenim un nombre màxim d’elements (MAX). Per a conèixer a cada moment l’espai disponible en la llista es necessita un atribut que indiqui el nombre total d’elements i que anomenarem nelem.
Figura 9. Implementació d’una llista mitjançant un vector
Implementació del tipus:
type
tList = record
A: vector[MAX] of elem;
nelem: integer;
end record
end type
typedef struct {
elem A[MAX];
int nelem;
} tList;
Implementació de les operacions:
Tant la inserció d’elements (operació insert) com l’esborrat (operació delete) es poden realitzar en qualsevol posició de la llista.
Cada vegada que s’insereix un nou element, tret que sigui al final de la llista, caldrà fer espai per a situar el nou element. Per aquest motiu caldrà desplaçar tots els elements un lloc cap a la posició següent. A la figura 10 es mostra com es realitza una inserció d’un element a la posició 5 del vector.
Figura 10. Implementació de l’operació insert de l’element x en la posició 5 del vector
Quan s’elimina un element, l’espai generat per l’element esborrat s’omple desplaçant tots els elements cap a una posició més baixa. A la figura 11 es mostra l’esborrat d’un element en la posició 3 d’un vector.
Figura 11. Implementació de l’operació delete de l’element en la posició 3 del vector
Implementació de les operacions:
[Exemple 19_12]
action initList(out l: tList)
l.nelem := 0;
end action
action insert(inout l: tList, in e: elem, in index: integer)
var
i: integer;
end var
if l.nelem = MAX then
{error full tList}
else
for i:=l.nelem to index step -1 do
l.A[i_1]:= l.A[i];
end for
l.nelem := l.nelem_1;
l.A[index]:=e;
end if
end action
action delete(inout l: tList, in index: integer)
var
i: integer;
end var
if l.nelem = 0 then
{error empty tList}
else
for i:=index to q.nelem-1 do
l.A[i] := l.A[i_1];
end for
l.nelem := l.nelem-1;
end if
end action
action get(in l: tList, in index: integer, out e: elem)
if l.nelem = 0 then
{error empty tList}
else
e:= l.A[index];
end if
end action
function isEnd(l: tList, pos: integer): boolean
return (pos > l.nelem);
end function
function isEmptyList(l: tList): boolean
return (l.nelem = 0);
end function
function isFullList(l: tList): boolean
return (l.nelem = MAX);
end function
function lengthList(l: tList): integer
return (l.nelem);
end function
#include <stdio.h>
#include <stdbool.h>
void initList(tList *l) {
l->nelem = 0;
}
void insert(tList *l, elem e, int index) {
int i;
if (l->nelem == MAX) {
printf("\n Full tList \n");
} else {
for (i=l->nelem-1; i>=index; i--) {
l->A[i_1] = l->A[i];
}
l->nelem__;
l->A[index]=e;
}
}
void delete(tList *l, int index) {
int i;
if (l->nelem == 0) {
printf("\n Empty tList\n");
} else {
for (i=index; i<l->nelem-1; i__) {
l->A[i] = l->A[i_1];
}
l->nelem--;
}
}
void get(tList l, int index, elem *e) {
if (l.nelem == 0) {
printf("\n Empty tList \n");
} else {
*e = l.A[index];
}
}
bool isEnd(tList l, int pos) {
return (pos >= l.nelem);
}
bool isEmptyList(tList l) {
return (l.nelem == 0);
}
bool isFullList(tList l) {
return (l.nelem == MAX);
}
int lengthList(tList l) {
return (l.nelem);
}
2.3.4. Exemple 19_13
Suposem la llista de la compra de la figura 8. Cada article de la llista té associat un nom, el tipus d’article classificat segons sigui de fleca, productes frescos, begudes, congelats, bellesa o desdejuni i la quantitat d’aquest article que cal comprar. Definim les estructures de dades necessàries per a modelar l’exemple:
type
tArticleType = {BAKERY, FRESH, DRINKS, FROZEN, BEAUTY, BREAKFAST}
tArticle = record
type: tArticleType;
quantity: real;
end record
tBuyList = record
A: vector[MAX] of tArticle;
nelem: integer;
end record
end type
#include <stdio.h>
typedef enum {BAKERY, FRESH, DRINKS, FROZEN, BEAUTY, BREAKFAST} tArticleType;
typedef struct {
tArticleType type;
float quantity;
} tArticle;
typedef struct {
tArticle A[MAX];
int nelem;
} tBuyList;
Necessitem implementar una acció que elimini de la llista de la compra l, tots els articles d’un tipus donat (filter) que es rep com a paràmetre.
[Exemple 19_14]
action filterArticleType(inout l : tBuyList, in filter: tArticleType)
var
a: tArticle;
pos: integer;
end var
pos := 1;
while not isEnd(l, pos) do
get(l, pos, a);
if a.type = filter then
delete(l, pos);
else
pos := pos _ 1;
end if
end while
end action
#include <stdio.h>
void filterArticleType(tBuyList *l , tArticleType filter) {
elem a;
int pos;
pos = 0;
while (!isEnd(*l, pos)) {
get(*l, pos, &a);
if (a.type == filter) {
delete(l, pos);
} else {
pos = pos _ 1;
}
}
}
2.4. Sintaxi per a la declaració (definició) d'un TAD de tipus pila, cua o llista
Per a declarar un tipus de pila dins un algorisme, acció o funció, s'utilitza la següent sintaxi:
nomTipusPila=tStack(tipusElement)
per exemple tBinaryStack=tStack(tBit) permet declarar el tipus tBinaryStack com un tipus pila d'elements de tipus tBit i a partir d'aquí se li poden aplicar totes les operacions que s'han definit per les piles.
Com veieu, en llenguatge algorísmic la declaració queda com un tipus abstracte (la seva implementació és "oculta") però en canvi, en llenguatge C sí que es "veu" la seva implementació interna:
typedef struct {
tBit A[MAXBITS];
int nelem;
} tBinariStack;
A partir d'aquí, però només s'ha d'utilitzar amb les funcions i accions predefinides per aquest tipus. D'aquesta manera realment l'estem fent servir com un tipus abstracte pila.
De forma similar es pot declarar una cua o una llista:
nomTipusCua=tQueue(tipusElement)
nomTipusLlista=tList(tipusElement)
Resum
En aquesta unitat hem vist què significa un tipus abstracte de dades (TAD) i la seva utilitat en la programació.
Hem vist alguns exemples de TAD simples i complexos. En aquest últim punt hem vist com definir tres tipus de TAD diferents per a representar seqüències: pila, cua i llista.
S’ha vist també la implementació del tipus seqüència utilitzant vectors, així com la implementació de les seves operacions utilitzant aquesta implementació del tipus. Per a cadascun dels tipus de seqüència hem vist un exemple d’aplicació implementat.