Navegació de TAD
Objectius
- Exercitar la manipulació dels TAD seqüències (piles, cues i llistes).
- Exercitar el disseny d’operacions sobre els TAD seqüències (piles, cues i llistes).
Introducció
En la unitat anterior de TADs es va definir un TAD, la necessitat de la seva utilització i es van estudiar TADs per a representar seqüències. En particular es van analitzar els TADs: piles, cues i llistes.
En aquesta unitat veurem exemples d’utilització de TADs sobre seqüències.
Així mateix, veurem exercicis d’autoavaluació sobre disseny i implementació de TADs en seqüències per a representar i manipular elements del món real, com ara una cua de treballs d’una impressora, una llista de factures, etc.
1. Exemples sobre el TAD pila
1.1. Exemple 20_01
Es demana el següent: dissenyeu una acció que mostri la representació binària d’un número rebut com a paràmetre. Per a fer-ho, utilitzeu una pila que emmagatzemi els resultats de les divisions parcials per la base (que és 2). Per exemple, si l’entrada és el número 77, llavors la sortida hauria de ser 1 0 0 1 1 0 1.
La capçalera de l’acció seria:
action dec2bin(in n: integer);
(Heu d’utilitzar les accions i funcions que ja es van definir per al tipus estructurat).
Solució:
type
tBit = integer;
tBinariStack = stack (tBit);
end type
action dec2bin(in n: integer)
var
b: tBinariStack;
res, bit: integer;
end var
b := createStack();
res := n;
while res ≠ 0 do
bit := res mod 2;
res := res / 2;
push(b, bit);
end while
while not emptyStack(b) do
bit := top(b);
writeInteger (bit);
pop(b);
end while
end action
typedef int tBit;
typedef struct {
tBit A[MAXBITS];
int nelem;
} tBinariStack;
typedef tBit elem;
typedef tBinariStack stack;
void dec2bin(int n) {
tBinariStack b;
int res, bit;
createStack(&b);
res = n;
while (res!=0) {
bit = res % 2;
res = res / 2;
push(&b, bit);
}
printf("\n");
while (!emptyStack(b)) {
bit = top(b);
printf(" %d ", bit);
pop(&b);
}
printf("\n");
}
1.2. Exemple 20_02
Es modela l’historial d’accessos a un conjunt de pàgines web com un TAD pila de pàgines web: l’última pàgina accedida és a dalt de la pila i si ens movem cap enrere en l’historial anirem accedint en ordre des de l’accés més recent fins al més antic.
En l’historial cada pàgina té la següent informació: un identificador únic de tipus enter, una adreça de memòria on es troba el codi de la pàgina i la data d’últim accés en format aaaammdd.
Es demana el següent: dissenyeu i implementeu l’acció clearRecentHistory, que elimina totes les pàgines web de l’historial que tenen últim accés posterior a una data donada.
La capçalera de l’acció és la següent:
action clearRecentHistory (inout s: tHistory; in date: integer);
Solució:
type
tWebPage = record
id : integer;
address : integer;
lastAccess : integer;
end record
tHistory = stack(tWebPage);
end type
action clearRecentHistory (inout s: tHistory, in date: integer)
var
end : boolean;
p : tWebPage;
end var
end := false;
while not emptyStack(s) and not end do
p := top(s);
if p.lastAccess > date then
pop(s);
else
end := true;
fsi
end while
end action
typedef enum {FALSE, TRUE} boolean;
typedef struct {
int id;
int address;
int lastAccess;
} tWebPage;
typedef struct {
tWebPage A[MAX];
int nelem;
} tHistory;
typedef tWebPage elem;
typedef tHistory stack;
void clearRecentHistory(tStack *s, int date) {
boolean end;
elem p;
end = FALSE;
while (!emptyStack(*s) && !end) {
p = top(*s);
if (p.lastAccess > date) {
pop(s);
} else {
end = TRUE;
}
}
}
1.3. Exemple 20_03
Considerem l’historial d’accessos a pàgines web de l’exercici anterior.
Es demana el següent: dissenyeu i implementeu l’acció pushupWebPage, que recarrega l’accés a una pàgina donada. Això significa que puja la seva posició en la pila fins al cim, i passa a ser la d’accés més recent.
La capçalera de l’acció és la següent:
action pushupWebPage (inout s: tHistory, in id: integer);
Solució:
action pushupWebPage(inout s: tHistory, in id: integer)
var
aux : tHistory;
found: boolean;
tmp, p: tWebPage;
end var
found := false;
aux := createStack();
while (not emptyStack(s) and not found) do
p := top(s);
if p.id = id then
pop(s);
found := true;
else
pop(s);
push(aux, p);
end if
end while
while not emptyStack(aux) do
tmp := top(aux);
pop(aux);
push(s, tmp);
end while
if found = true then
push(s, p);
end if
end action
typedef enum {FALSE, TRUE} boolean;
void pushupWebPage (tStack *s, int id) {
tStack aux;
boolean found;
tWebPage tmp, p;
found = FALSE;
createStack (&aux);
while (!emptyStack(*s) && !found) {
p = top(*s);
if (p.id == id) {
pop(s);
found = TRUE;
} else {
pop(s);
push(&aux, p);
}
}
while (!emptyStack(aux)) {
tmp = top(aux);
pop(&aux);
push(s, tmp);
}
if (found == TRUE) {
push(s, p);
}
}
2. Exemples sobre el TAD cua
2.1. Exemple 20_04
Es modela la cua de treballs d’una impressora com un TAD cua de treballs. Els treballs nous s’insereixen al final de la seqüència de tasques i el primer treball de la seqüència és el primer a enviar-se a imprimir.
Cada treball té la informació següent: un identificador únic de tipus enter, l’adreça on es troba emmagatzemat el treball que cal imprimir, la mida en bytes i el tipus d’impressió (a doble o a simple cara).
Es demana el següent: dissenyeu i implementeu la funció countBig que retorna el nombre de treballs de la cua d’impressió, que té una mida superior a un límit donat en bytes.
La capçalera de la funció és la següent:
function countBig (q: tPrinterQueue, limit: integer) : integer;
Solució:
type
tWork = record
id : integer;
address : integer;
size : integer;
doubleSide : boolean;
end record
tPrinterQueue = queue (tWork);
end type
function countBig(q: tPrinterQueue, limit: integer) : integer
var
w : tWork;
ini, count : integer;
end : boolean;
end var
count :=0;
if not emptyQueue(q) then
w := head(q);
ini := w.id;
if w.size > limit then
count := count+1;
end if
dequeue(q);
enqueue(q, w);
end := false;
while not end do
w := head(q);
if w.id = ini then
end := true;
else
if w.size > limit then
count := count+1;
end if
dequeue(q);
enqueue(q, w);
end if
end while
end if
return count;
end function
typedef enum {FALSE, TRUE} boolean;
typedef struct {
int id;
int address;
int size;
boolean doubleSide;
} tWork;
typedef struct {
tWork A[MAX];
int nelem;
} tPrinterQueue;
typedef tWork elem;
typedef tPrinterQueue queue;
int countBig(tQueue q, int limit) {
elem w;
int ini;
int count;
boolean end;
count=0;
if (!emptyQueue(q)) {
w= head(q);
ini = w.id;
if (w.size > limit) {
count++;
}
dequeue(&q);
enqueue(&q, w);
end = FALSE;
while (!end) {
w = head(q);
if (w.id == ini) {
end = TRUE;
} else {
if (w.size > limit) {
count++;
}
dequeue(&q);
enqueue(&q, w);
}
}
}
return count;
}
2.2. Exemple 20_05
Considerem la cua de treballs de la impressora de l’exercici anterior.
Es demana el següent: dissenyeu i implementeu l’acció concatQueues que, donades dues cues de treballs, concatena la segona cua amb la primera i buida la segona cua de treballs. Si la primera cua de treballs s’omple, els treballs que no s’hagin concatenat es quedaran a la segona cua i el paràmetre de sortida completed retornarà fals. Si s’ha pogut completar la concatenació, el paràmetre completed retorna vertader.
La capçalera de l’acció és la següent:
action concatQueues (inout q1 : tPrinterQueue, inout q2 : tPrinterQueue, out completed: boolean)
Solució:
action concatQueues(inout q1: tPrinterQueue, inout q2: tPrinterQueue, out completed: boolean)
var
w : tWork;
end var
while (not emptyQueue(q2) and not fullQueue(q1)) do
w := head(q2);
enqueue(q1, w);
dequeue(q2);
end while
completed := emptyQueue(q2);
end action
void concatQueues(tQueue *q1, tQueue *q2, int *completed) {
tWork w;
while (!emptyQueue(*q2) && !fullQueue(*q1)) {
w = head (*q2);
enqueue (q1, w);
dequeue (q2);
}
*completed = emptyQueue(*q2);
}
2.3. Exemple 20_06
Considerem la cua de treballs d’impressió de l’exercici anterior.
Es demana el següent: dissenyeu i implementeu l’acció serveDoubleSide, que envia a imprimir tots els treballs amb el tipus d’impressió de doble cara. Es retorna en el paràmetre qsingle, una cua creada amb tots els treballs no enviats a imprimir, és a dir, els que són de tipus simple cara.
Per a enviar un treball a imprimir es disposa de l’acció printWork, que rep com a paràmetre el treball a imprimir amb totes les seves dades (identificador, adreça, mida i tipus d’impressió).
La capçalera de l’acció és la següent:
action serveDoubleSide (inout q: tPrinterQueue, inout qsingle: tPrinterQueue);
Solució:
action serveDoubleSide(inout q: tPrinterQueue, inout qsingle: tPrinterQueue)
var
w : tWork;
end var
qsingle := createQueue();
while not emptyQueue(q) do
w := head(q);
if w.doubleSide = true then
printWork(w);
else
enqueue(qsingle, w);
end if
dequeue(q);
end while
end action
typedef enum {FALSE, TRUE} boolean;
void serveDoubleSide (tQueue *q, tQueue *qsingle) {
elem w;
createQueue(qsingle);
while (!emptyQueue(*q)) {
w = head(*q);
if (w.doubleSide == TRUE) {
printWork(w);
} else
enqueue(qsingle, w);
}
dequeue(q);
}
}
3. Exemples sobre el TAD llista
3.1. Exemple 20_07
Es modela la llista de seients disponibles d’un vol concret mitjançant una llista de seients. S’ha optat per una llista atès que qualsevol seient pot deixar d’estar disponible (és assignat) i, per tant, es dona de baixa de la llista o podria haver-hi qualsevol modificació de seients (baixa i alta). Cada seient té la informació següent: nombre enter que l’identifica i tipus de seient (regular o porta d’emergència). Els seients de tipus porta d’emergència no s’assignen a passatgers amb dotze anys o menys. De cada passatger es coneix el seu identificador de tipus enter, el nombre de maletes que ha facturat i la seva edat.
Es demana el següent: dissenyeu i implementeu l’acció seatAssign, que, donada una llista de seients disponibles i la informació d’un passatger, retorna el seient que se li ha assignat i el paràmetre found amb valor vertader. Si no ha estat possible assignar-li un seient, el paràmetre found retorna el valor fals.
La capçalera de l’acció és la següent:
action seatAssign (inout l: tListSeat, in p: tPerson, inout s : tSeat, inout found : boolean);
Solució:
type
tPerson = record
id : integer;
numBags : integer;
age : integer;
end record
tSeatType = { regular, emergencyDoor };
tSeat = record
num : integer;
type : tSeatType;
end record
tListSeats = list(tSeat);
end type
action seatAssign (inout l: tListSeat, in p : tPerson, inout s : tSeat, inout found : boolean)
var
pos : integer;
found : boolean;
end var
pos := 1;
found := false;
while (pos ≤ l.nelem and not found) do
s := get(l, pos);
if (p.age > 12 or (p.age ≤ 12 and s.type ≠ emergencyDoor) then
found := true;
delete(l, pos);
else
pos := pos+1;
end if
end while
end action
typedef enum {FALSE, TRUE} boolean;
typedef struct {
int id;
int numBags;
int age;
} tPerson;
typedef enum { regular, emergencyDoor } tSeatType;
typedef struct {
int num;
tSeatType type;
} tSeat;
typedef struct {
tSeat A[MAX];
int nelem;
} tListSeats;
typedef tSeat elem;
typedef tListSeats list;
void seatAssign (tListSeats *l, tPerson p, tSeat *s, boolean *found) {
int pos;
pos = 0;
*found = FALSE;
while (pos < l->nelem && !found) {
*s = get(*l, pos);
if (p.age > 12 || (p.age <= 12 && s->type != emergencyDoor)) {
*found = TRUE;
delete(l, pos);
} else {
pos = pos+1;
}
}
}
3.2. Exemple 20_08
Es modela un conjunt de factures d’una empresa mitjançant una llista. Les factures no segueixen un ordre especial en l’alta del conjunt i és possible donar de baixa qualsevol factura del conjunt.
De cada factura es coneix la informació següent: un identificador únic de tipus enter, la quantitat de diners de tipus real i la data de la factura en format aaaammdd.
Es demana el següent: dissenyeu i implementeu la funció countSmallAmounts, que retorna el nombre de factures amb quantitat de diners menors a una quantitat donada.
La capçalera de la funció és la següent:
function countSmallAmounts (l : tInvoiceList, a : real) : integer
Solució:
type
tInvoice = record
id : integer;
amount : real;
date : integer;
end record
tInvoiceList = list(tInvoice);
end type
function countSmallAmounts(l : tInvoiceList, a : real) : integer
var
inv : tInvoice;
total : integer;
pos : integer;
end var
pos := 1;
total := 0;
while pos ≤ l.nelem do
inv := get(l, pos);
if inv.amount < a then
total := total + 1;
end if
pos := pos + 1;
end while
return total;
end function
typedef struct {
int id;
float amount;
int date; /* aaaammdd */
} tInvoice;
typedef struct {
tInvoice A[MAX];
int nelem;
} tInvoiceList;
typedef tInvoice elem;
typedef tInvoiceList list;
int countSmallAmounts(tInvoiceList l, float a) {
tInvoice inv;
int total;
int pos;
pos = 0;
total = 0;
while (pos < l.nelem) {
inv = get(l, pos);
if (inv.amount < a) {
total = total + 1;
}
pos = pos + 1;
}
return total;
}
3.3. Exemple 20_09
Considerem el conjunt de factures de l’exercici anterior.
Es demana el següent: dissenyeu i implementeu l’acció findInvoice que, donat l’identificador d’una factura, retorna el paràmetre found vertader si la factura està en el conjunt de factures, així com la seva posició a la llista. En cas contrari, l’acció retorna el paràmetre found amb valor fals.
La capçalera de l’acció és la següent:
action findInvoice (in l: tInvoices, in id: integer, out found: boolean, out pos: integer);
Solució:
action findInvoice(in l: tInvoices, in id: integer, out found: boolean, out pos: integer)
var
inv: tInvoice;
end var
found := false;
pos := 1;
while (pos ≤ l.nelem and not found) do
inv := get(l, pos);
if inv.id = id then
found := true;
else
pos := pos + 1;
end if
end while
end action
typedef enum {FALSE, TRUE} boolean;
void findInvoice(tInvoices l, int id, boolean *found, int *pos)
tInvoice inv;
*found = FALSE;
*pos = 0;
while (*pos < l.nelem && !(*found)) {
inv = get (l, *pos);
if (inv.id == id) {
*found = TRUE;
} else {
(*pos)++;
}
}
}
Resum
En aquesta unitat hem vist diversos exemples sobre l’ús de piles, cues i llistes.