08. TAD de TAD
Objectius
- Repàs de la manipulació dels TAD seqüències (piles, cues i llistes)
- Disseny de nous TAD a partir d'altres TAD ja coneguts com piles, cues i llistes
Introducció
En el mòdul anterior de TAD es va repasar el concepte d'un TAD, la necessitat de la seva utilització i es van mostrar l'implementació TAD per representar seqüències utilitzant memòria dinàmica.
Amb l'objectiu de modelar objectes de la realitat d'una forma més propera, és posible combinar els TAD ja coneguts per crear de nous TAD més complexos.
En aquest mòdul es presenten alguns exemples de nous TAD creats a partir de la combinació de TAD ja existents definits al mòdul TAD en memòria dinàmica.
Llista doblement encadenada
Definim el TAD tDoubleLinkedList que conté una llista doblement encadenada d'elements. Cada node de la llista está encadenat a l'element següent i a l'element previ. Això permet realitzar desplaçaments dintre de la llista en ambdos sentits. En el cas de la implementació utilitzant punters, els encadenaments a l'element següent i anterior s'implementen mitjançant dos punters: next y prev. El primer element de la llista és apuntat per first i el darrer element pel punter last.
Aquest TAD facilita l'algorisme d'operacions com l'esborrat d'elements, ja que per actualitzar els encadenaments, no és necessari buscar l'element anterior a l'element a esborrar donat que és possible accedir a ell directament des de l'element a esborrar.
En la figura 1 es mostra una representació de la llista doblement encadenada utilitzant punters:
Figura 1. Llista doblement encadenada amb punters
Definició del tipus
[Exemple 08_01]
type
tNode = record
e: elem;
prev: pointer to tNode;
next: pointer to tNode;
end record
tDoubleLinkedList = record
first: pointer to tNode;
last: pointer to tNode;
end record
end type
typedef struct tNode {
elem e;
struct tNode *prev;
struct tNode *next;
} tNode;
typedef struct {
tNode *first;
tNode *last;
} tDoubleLinkeList;
Exemple de manipulació: rotateLeft
A continuació és mostra la implementació de l'operació rotateLeft (dll, n), que realitza la rotació d'elements n llocs a l'esquerra en la llista dll. La rotació consisteix en moure tots els elements n posicions a l'esquerra dins de la seqüència de forma circular. Si un element arriba al principi de la seqüència, haurà de continuar pel final fins a completar els n desplaçaments.
Nota: si el nombre n és zero o la llista està buida o conté només un element es retorna la llista dll sense canvis.
[Exemple 08_02]
action rotateLeft(inout dll: tDoubleLinkedList; in n: integer)
var
first: pointer to tNode;
last : pointer to tNode;
times: integer;
end var
if n > 0 and (not equal(dll.first, dll.last)) then
times := 0;
while times < n do
first := dll.first;
last := dll.last;
dll.last := dll.first;
dll.first := (dll.first)^.next;
last^.next := first;
first^.prev := last;
(first^.next)^.prev := null;
first^.next := null;
times := times + 1;
end while
end if
end action
void rotateLeft(tDoubleLinkedList *dll, int n) {
tNode *first;
tNode *last;
int times;
if (n > 0 && dll->first != dll->last) {
times = 0;
while ( times < n ) {
first = dll->first;
last = dll->last;
dll->last = dll->first;
dll->first = dll->first->next;
last->next = first;
first->prev = last;
first->next->prev = NULL;
first->next = NULL;
times = times + 1;
}
}
}
Vector amb llista encadenada
Un vector amb una llista encadenada es tracta d'un conjunt d'elements emmagatzemats en un vector, on algun d'aquests elements també formen part d'una llista doblement encadenada implementada amb punters.
En la figura 2 es mostra una representació de vector amb una llista encadenada. El vector de l'exemple conté 7 elements (v1, v2, v3, v4, v5, v6 i v7) i la llista conté 3 elements i en aquest ordre: v2, v3, v6 i v4.
Figura 2. Vector amb llista encadenada.
Definició del tipus
[Exemple 08_03]
type
tNode = record
e: elem;
prev: pointer to tNode;
next: pointer to tNode;
end record
tDoubleLinkedList = record
first: pointer to tNode;
last: pointer to tNode;
end record
tVectorDll = vector[MAX] of tNode;
end type
typedef struct tNode {
elem e;
struct tNode *prev;
struct tNode *next;
} tNode;
typedef struct {
tNode *first;
tNode *last;
} tDoubleLinkeList;
typedef tNode tVectorDll[MAX];
Exemple de manipulació: deleteVecDll
A continuació es presenta l'operació deleteVecDll, que donat un index del vector, elimina un element de la llista doblement encadenada però no del vector.
El paràmetre index indica l'índex del vector on es troba l'element que volem esborrar de la llista doblement encadenada. Si l'índex és major que MAX o l'element no forma part de la llista, llavors retorna un error. S'assumeix que la llista no és buida i que MAX és igual o superior a 3.
Nota: un element no forma part de la llista si es compleix que el punter al següent i a l'anterior són nuls, i que no es tracta d'una llista encadenada amb un només element.
[Exemple 08_04]
action deleteVecDll(inout v: tVectorDll, in index: integer, inout first: pointer to tNode, inout last: pointer to tNode)
if index > MAX then
writeString("error: invalid index");
else
if (not equal(first, last)) and v[index].prev = null and v[index].next = null then
writeString("error: element doesn't belong to the list");
else
if not equal(first, last) then
v[index].prev^.next := v[index].next;
v[index].next^.prev := v[index].prev;
else
first := null;
last := null;
end if
end if
end if
end action
void deleteVecDll(tVectorDll *v, int index, tNode *first, tNode *last) {
if (index > MAX) {
printf("\n error: invalid index");
} else {
if (first != last && v[index].prev == NULL && v[index].next == NULL {
printf("\n error: element doesn't belong to the list");
} else {
if (first != last) {
v[index].prev->next = v[index]->next;
v[index].next->prev = v[index]->prev;
} else {
first = NULL;
last = NULL;
}
}
}
}
Vector de llistes
Un vector de llistes es tracta d'un vector, on cadascun dels seus elements és un punter a una llista d'elements emmagatzemats fora del vector.
La figura 3 mostra un exemple de representació d'un vector de llistes. Per exemple, la posició 1 conté un apuntador a una llista amb dos elements, la posició 2 conté un punter a una llista buida.
Figura 3. Vector de llistes
Definició del tipus
[Exemple 08_05]
type
tNode = record
e: elem;
next: pointer to tNode;
end record
tVectorList = vector[MAX] of pointer to tNode;
end type
typedef struct tNode {
elem e;
struct tNode *next;
} tNode;
typedef tNode *tVectorList[MAX];
Exemple de manipulació: insertVecList
A continuació es presenta l'operació insertVecList, que donat un index del vector i un element, ho insereix al començament de la llista apuntada pel punter de la posició del vector donada.
[Exemple 08_06]
action insertVecList(inout v: tVectorList, in index: integer, in e: elem)
if index > MAX then
writeString("error: invalid index");
else
insert(v[index], e);
end if
end action
void insertVecList(tVectorList v, int index, elem e) {
if (index > MAX) {
printf("\n error : invalid index");
} else {
insert(v[index], e);
}
}
Resum
En aquest mòdul s'han presentat exemples de definició de nous TAD a partir de TAD ja coneguts com piles, cues i llistes. Hem vist per cadascú dels exemples un cas de manipulació amb la implementació d'una operació nova sobre el TAD nou.