20. Navegación de TAD
Objetivos
- Ejercitar la manipulación de los TAD secuencias (pilas, colas y listas).
- Ejercitar el diseño de operaciones sobre los TAD secuencias (pilas, colas y listas).
Introducción
En la unidad anterior de TADs se definió un TAD, la necesidad de su utilización y se estudiaron TADs para representar secuencias. En particular se analizaron los TADs: pilas, colas y listas.
En esta unidad veremos ejemplos de utilización de TADs sobre secuencias.
Asimismo, veremos ejercicios de autoevaluación sobre diseño e implementación de TADs en secuencias para representar y manipular elementos del mundo real, tales como una cola de trabajos de una impresora, una lista de facturas, etc.
1. Ejemplos sobre el TAD pila
1.1. Ejemplo 20_01
Se pide lo siguiente: diseñad una acción que muestre la representación binaria de un número recibido como parámetro. Para hacerlo, utilizad una pila que almacene los resultados de las divisiones parciales por la base (que es 2). Por ejemplo, si la entrada es el número 77, entonces la salida debería ser 1 0 0 1 1 0 1.
La cabecera de la acción sería:
action dec2bin (in n: integer);
(Tenéis que utilizar las acciones y funciones que ya se definieron para el tipo estructurado).
Solución:
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. Ejemplo 20_02
Se modela el historial de accesos a un conjunto de páginas web como un TAD pila de páginas web: la última página accedida está en la cima de la pila y si nos movemos hacia atrás en el historial iremos accediendo en orden desde el acceso más reciente al más antiguo.
En el historial cada página tiene la siguiente información: un identificador único de tipo entero, una dirección de memoria donde se encuentra el código de la página y la fecha de último acceso en formato aaaammdd.
Se pide lo siguiente: diseñad e implementad la acción clearRecentHistory que elimina todas las páginas web del historial que tienen último acceso posterior a una fecha dada.
La cabecera de la acción es la siguiente:
action clearRecentHistory(inout s: tHistory; in date: integer);
Solución:
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. Ejemplo 20_03
Consideramos el historial de accesos a páginas web del ejercicio anterior.
Se pide lo siguiente: diseñad e implementad la acción pushupWebPage que recarga el acceso a una página dada. Esto significa que sube su posición en la pila hasta la cima, para pasar a ser la de acceso más reciente.
La cabecera de la acción es la siguiente:
action pushupWebPage(inout s: tHistory, in id: integer);
Solución:
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. Ejemplos sobre el TAD cola
2.1. Ejemplo 20_04
Se modela la cola de trabajos de una impresora como un TAD cola de trabajos. Los trabajos nuevos se insertan al final de la secuencia de trabajos y el primer trabajo de la secuencia es el primero en enviarse a imprimir.
Cada trabajo tiene la siguiente información: un identificador único de tipo entero, la dirección donde se encuentra almacenado el trabajo a imprimir, el tamaño en bytes y el tipo de impresión (a doble o a simple cara).
Se pide lo siguiente: diseñad e implementad la función countBig que devuelve el número de trabajos de la cola de impresión cuyo tamaño es superior a un límite dado en bytes.
La cabecera de la función es la siguiente:
function countBig (q: tPrinterQueue, limit: integer) : integer;
Solución:
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. Ejemplo 20_05
Consideramos la cola de trabajos de la impresora del ejercicio anterior.
Se pide lo siguiente: diseñad e implementad la acción concatQueues que, dadas dos colas de trabajos, concatena la segunda cola con la primera y vacía la segunda cola de trabajos. Si la primera cola de trabajos se llena, los trabajos que no se hayan concatenado se quedarán en la segunda cola y el parámetro de salida completed devolverá falso. Si se ha podido completar la concatenación, el parámetro completed devuelve verdadero.
La cabecera de la acción es la siguiente:
action concatQueues(inout q1 : tPrinterQueue, inout q2 : tPrinterQueue, out completed: boolean)
Solución:
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. Ejemplo 20_06
Consideramos la cola de trabajos de impresión del ejercicio anterior.
Se pide lo siguiente: diseñad e implementad la acción serveDoubleSide, que envía a imprimir todos los trabajos cuyo tipo de impresión es doble cara. Se devuelve en el parámetro qsingle, una cola creada con todos los trabajos no enviados a imprimir, es decir, los que son de tipo simple cara.
Para enviar un trabajo a imprimir se dispone de la acción printWork, que recibe como parámetro el trabajo a imprimir con todos sus datos (identificador, dirección, tamaño y tipo de impresión).
La cabecera de la acción es la siguiente:
action serveDoubleSide(inout q: tPrinterQueue, inout qsingle: tPrinterQueue);
Solución:
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. Ejemplos sobre el TAD lista
3.1. Ejemplo 20_07
Se modela la lista de asientos disponibles de un vuelo concreto mediante una lista de asientos. Se ha optado por una lista dado que cualquier asiento puede dejar de estar disponible (es asignado) y, por lo tanto, se da de baja de la lista o podría haber cualquier modificación de asientos (baja y alta). Cada asiento tiene la siguiente información: número entero que lo identifica y tipo de asiento (regular o puerta de emergencia). Los asientos de tipo puerta de emergencia no se asignan a pasajeros con 12 años o menos. De cada pasajero se conoce su identificador de tipo entero, el número de maletas que ha facturado y su edad.
Se pide lo siguiente: diseñad e implementad la acción seatAssign que, dada una lista de asientos disponibles y la información de un pasajero, devuelve el asiento que se le ha asignado y el parámetro found con valor verdadero. Si no ha sido posible asignarle un asiento, el parámetro found devuelve el valor falso.
La cabecera de la acción es la siguiente:
action seatAssign (inout l: tListSeat, in p: tPerson, inout s : tSeat, inout found : boolean);
Solución:
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. Ejemplo 20_08
Se modela un conjunto de facturas de una empresa mediante una lista. Las facturas no siguen un orden especial en el alta del conjunto y es posible dar de baja cualquier factura del conjunto.
De cada factura se conoce la siguiente información: un identificador único de tipo entero, la cantidad de dinero de tipo real y la fecha de la factura en formato aaaammdd.
Se pide lo siguiente: diseñad e implementad la función countSmallAmounts, que devuelve el número de facturas con cantidad de dinero menor a una cantidad dada.
La cabecera de la función es la siguiente:
function countSmallAmounts (l : tInvoiceList, a : real) : integer
Solución:
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. Ejemplo 20_09
Consideramos el conjunto de facturas del ejercicio anterior.
Se pide lo siguiente: diseñad e implementad la acción findInvoice que, dado el identificador de una factura, devuelve el parámetro found verdadero si la factura está en el conjunto de facturas así como su posición en la lista. En caso contrario, la acción devuelve el parámetro found con valor falso.
La cabecera de la acción es la siguiente:
action findInvoice (in l: tInvoices, in id: integer, out found: boolean, out pos: integer);
Solución:
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)++;
}
}
}
Resumen
En esta unidad hemos visto diversos ejemplos sobre el uso de pilas, colas y listas.