07. TAD en memòria dinàmica
Objectius
Els objectius d'aquest mòdul són:
- Repàs del concepte de tipus abstracte de dades (TAD).
- Repàs del concepte de memòria dinàmica i punters.
- Presentació d'operacions i primitives per manipular punters.
- Mostrar una implementació dels TAD piles, cues i llistes utilitzant memòria dinàmica.
Introducció
Recordem que un TAD queda definit a través d'un conjunt de valors o domini i una sèrie d'operacions que se li poden aplicar. La implementació de les operacions no s'especifica ja que només s'especifica com es comporten les operacions. Això significa que un mateix TAD pot implementar-se de formes diferents.
Els TAD tractats al mòdul de Fonaments de Programació han estat: piles, cues i llistes. S'ha vist també una implementació bàsica del tipus i les operacions utilitzant vectors.
La implementació utilitzant vectors té alguns desavantatges que s'enumeren a continuació:
- En la implementació proposada utilitzant vectors, tant en la inserció com en l'eliminació d'elements, s'han de desplaçar tots els elements cap a la dreta per generar un nou espai o cap a l'esquerra per emplenar l'espai de l'element recentment eliminat.
- No s'utilitza la memòria de forma òptima ja que es manté reservada una quantitat d'espai durant tota l'execució. D'altra banda si l'espai reservat no és suficient no és possible modificar-ho.
Com a alternativa de millora a la implementació amb vectors, en aquest mòdul es presenta una proposta d'implementació dels TAD pila, cua i llista utilitzant memòria dinàmica.
L'espai necessari per emmagatzemar una estructura dinàmica es reserva en temps d'execució. Això té l'avantatge de fer un ús òptim de la memòria però d'altra banda podria succeir que no hi hagués memòria disponible suficient per continuar l'execució.
Per treballar amb la memòria dinàmica serà necessària la utilització del tipus de dades punter. En aquest mòdul recordarem la definició del tipus de dades punter, treballarem amb memòria dinàmica i veurem també una nova proposta d'implementació dels TAD pila, cua i llista aplicant tots aquests conceptes.
Tipus de dades punter
Definició
Una variable x de tipus de dades punter a T, és un apuntador a un objecte de tipus de dades T. A través de la variable x és possible accedir a un objecte de tipus T.
Un punter és una variable, on el seu valor és l'adreça de memòria de començament de l'objecte apuntat.
Per exemple si la variable x és de tipus punter a enter, llavors la variable x apunta a un objecte de tipus enter. En la Figura 1 es mostra la representació conceptual de punter, on la variable x apunta a un objecte de tipus enter amb valor 10 i la representació física, on la variable x emmagatzema el valor 0136 que correspon a l'adreça de memòria de l'objecte apuntat amb valor 10.
Figura 1. Exemple d'un punter a enter (Imatge extreta de [1]).
[Exemple 07_01]
type
tExample = record
e: integer;
end record
tPointerExample = pointer to tExample;
end type
typedef struct {
int e;
} tExample;
typedef tExample *tPointerExample;
Operacions i primitives de punters
A continuació es defineixen les operacions per obtenir (getMemory) i alliberar (freeMemory) l'espai de memòria de forma dinàmica, així com d'altres primitives necessàries per a la manipulació de punters.
El valor null és un valor especial que indica que el punter no apunta a cap lloc. Si la funció getMemory no aconsegueix obtenir l'espai sol·licitat retorna el valor null. La funció freeMemory a més d'alliberar l'espai en memòria apuntat pel punter paràmetre, assigna el valor null al punter rebut com a paràmetre.
Obtenir espai
Aquesta funció que anomenem getMemory s'utilitza per sol·licitar al sistema operatiu una quantitat determinada d'espai en memòria durant l'execució d'un programa. Si la funció getMemory no aconsegueix obtenir l'espai sol·licitat retorna el valor null.
[Exemple 07_02]
var
p: tPointerExample;
end var
p := getMemory();
if p = null then
writeString("Error: not enough free memory");
end if
#include <malloc.h>
tPointerExample p;
p = (tPointerExample *)malloc(sizeof(tPointerExample));
if (p == NULL) {
printf("\n Error: not enough free memory\n");
}
Alliberar espai
Aquesta funció que anomenem freeMemory, s'utilitza per alliberar espai de memòria prèviament reservada durant l'execució del programa. La funció freeMemory a més d'alliberar l'espai en memòria apuntat pel punter paràmetre, assigna el valor null al punter rebut com a paràmetre.
[Exemple 07_03]
var
p: tPointerExample;
end var
{ ... }
{ p is a pointer to previously allocated memory }
freeMemory(p);
#include <malloc.h>
tPointerExample p;
/* ... */
/* p is a pointer to previously allocated memory */
free(p);
Alliberar espai ocupat indirectament
Per assegurar-nos que no es generen llocs de memòria sense referència o retalls (se suggereix referir-se a [1], pàgina 48: Referències penjades), es defineix aquesta funció que anomenem destroy. Aquesta funció no només allibera l'espai de l'objecte paràmetre, sinó que també si aquest objecte és una estructura amb punters que apunten a altres objectes, l'espai apuntat per aquests últims també és alliberat i així successivament en forma recursiva.
D'aquesta forma s'obté independència de la implementació del TAD. La implementació de la funció destroy és depenent de la implementació del TAD triada i de l'estructura de dades concreta. Per aquest motiu només es mostra el seu ús en llenguatge algorísmic.
[Exemple 07_04]
var
e: tExample;
end var
{ ... }
{ e is an object previously initialized }
destroy(p);
Duplicar espai
En una assignació clàssica de variables, per exemple: dues variables de tipus enter a i b, en efectuar l'assignació a:= b , el valor de la variable b es copia en la variable a. Ambdues variables ocupen llocs de memòria diferents i són independents.
El resultat de l'assignació d'un punter p1 a un altre punter p2, és a dir p2 := p1, dóna com a resultat que el valor del punter origen (p1) es copia en la variable destinació (p2). Després d'aquesta assignació tots dos punters tenen el mateix valor, la qual cosa significa que tots dos punters apunten al mateix objecte o lloc de memòria. Per tant qualsevol modificació d'aquesta àrea de memòria realitzada a través d'un punter, també serà visible si accedim a través de l'altre punter.
Si el que es desitja és realitzar una còpia de l'objecte e1, en un altre objecte e2, s'ha de duplicar l'espai ocupat per l'objecte e1 i assignar-li a e2 el valor de l'objecte original. Si aquest objecte és una estructura amb punters que apunten a altres objectes, els objectes apuntats per aquests últims també s'haurien de copiar i així successivament en forma recursiva. Per aconseguir aquest objectiu introduïm una nova operació que anomenem duplicate que realitza una còpia exacta d'un objecte sobre un altre del mateix TAD. Aquesta funció retorna el nou objecte resultat.
D'aquesta forma s'obté independència de la implementació del TAD. La còpia d'objectes es realitza amb la funció duplicate sense tenir en compte la implementació concreta del TAD.
La implementació de la funció duplicate és depenent de la implementació del TAD triada i de l'estructura de dades concreta. Per aquest motiu solament es mostra el seu ús en llenguatge algorísmic.
[Exemple 07_05]
var
e1, e2: tExample;
end var
{ ... }
{ e1 is an object previously initialized }
duplicate(e2, e1);
Comparació d'objectes
La comparació de dos objectes e1 i e2, no es pot reduir únicament a la comparació dels objectes e1 i e2. Si aquests objectes son una estructura amb punters que apunten a altres objectes, els objectes apuntats per aquests últims quedarien fora de la comparació. Per tant, a l'igual que en les operacions de duplicate i destroy, l'algorisme que implementa aquesta operació ha de contemplar aquesta recursivitat. Això significa que no és suficient amb aplicar l'operador d'igualtat: e1 = e2 per realitzar l'operació de comparació.
Per aquest motiu s'introdueix l'operació equal que realitza una comparació recursiva completa dels objectes passats com a paràmetre. Per a major informació referir-se a [1], pàgina 46: 2) Comparació.
D'aquesta forma, la funció equal independitza al codi de la implementació concreta del TAD i l'estructura. No obstant això, la implementació de la funció equal és depenent de la implementació del TAD triada i de l'estructura de dades concreta. Per aquest motiu solament es mostra el seu ús en llenguatge algorísmic.
[Exemple 07_06]
var
e1, e2: tExample;
end var
{ ... }
{ e1 and e2 are objects previously initialized }
if equal(e1, e2) then
{ ... }
end if
Implementació dels TAD utilitzant memòria dinàmica
En la implementació amb vectors tots els elements del TAD estaven emmagatzemats en posicions consecutives en memòria. En la implementació amb memòria dinàmica no necessàriament els elements estan en posicions consecutives de memòria. Això succeeix pel fet que cada posició es va reservant en forma dinàmica durant l'execució, per la qual cosa el gestor de memòria del sistema operatiu retorna un punter al primer lloc que troba amb l'espai demanat.
Per encadenar els diferents elements del TAD s'utilitzen els punters. Cada element del TAD té sempre almenys un camp que emmagatzema un punter al següent element en el TAD. Denominarem node a cada element d'una estructura implementada amb punters.
A continuació es presenta la implementació dels TAD pila, cua i llista utilitzant punters, és a dir memòria dinàmica. Per a aquesta implementació amb punters les funcions fullStack, fullQueue and fullList que s'utilitzaven en la implementació amb vectors, ja no s'utilitzen donat que no s'estableix un límit màxim d'elements.
Pila (tStack)
Recordem que el TAD pila és una seqüència lineal d'elements on només es pot inserir i eliminar elements pel cim de la pila. En la Taula 1 es llisten les operacions que defineixen aquest TAD.
Taula 1. Llista d'operacions sobre el TAD pila
| Operació | Descripció |
|---|---|
| createStack | Crea una pila buida |
| push | Empila un element a la pila |
| pop | Desempila un element de la pila |
| top | Retorna l'element situat al cim de la pila però no el treu |
| emptyStack | Retorna true si la pila està buida, altrament retorna false |
Implementació del tipus
La implementació proposada es basa en punters. El primer element de la pila, és a dir el que es troba en el cim és apuntat pel punter first, excepte quan la pila està buida, en aquest cas té el valor null.
A la Figura 2 es mostra a l'esquerra la representació gràfica d'una pila, on l'element en el cim (top) és el vn. A la dreta es mostra la representació de la pila utilitzant punters. L'element apuntat pel punter first és el que està en el cim de la pila. Cada element té un punter al següent element en la pila. L'element que està a la base de la pila (el primer que va ser inserit) té el punter al següent amb valor null.
Figura 2. Representació d'una pila (esquerra) i implementació utilitzant punters (dreta). Imatge extreta i adaptada de [1].
[Exemple 07_07]
type
tNode = record
e: elem;
next: pointer to tNode;
end record
tStack = record
first: pointer to tNode;
end record
end type
typedef struct tNode {
elem e;
struct tNode *next;
} tNode;
typedef struct {
tNode *first;
} tStack;
Implementació de les operacions
Tant en l'operació d'empilar (push), com en l'operació de desempilar (pop), la manipulació d'elements es realitza per l'extrem final de la seqüència, que és també el cim de la pila.
Figura 3. Implementació de l'operació desempilar (pop). Imatge extreta i adaptada de [1]
[Exemple 07_08]
function createStack(): tStack
var
s: tStack;
end var
s.first := null;
retorna s;
end function
action push(inout s: tStack; in e: elem)
var
tmp: pointer to tNode;
end var
tmp := getMemory();
if tmp = null then
writeString("error: not enough free memory");
else
duplicate(tmp^.e, e);
tmp^.next := s.first;
s.first := tmp;
end if
end action
action pop(inout s: tStack)
var
tmp: pointer to tNode;
end var
if s.first = null then
writeString("error: empty stack");
else
tmp := s.first;
s.first := (s.first)^.next;
destroy(tmp^.e);
freeMemory(tmp);
end if
end action
function top(s: tStack): elem
var
e: elem;
end var
if s.first = null then
writeString("error: empty stack");
else
duplicate(e, (s.first)^.e);
end if
return e;
end function
function emptyStack(s: tStack): boolean
return (s.first = null);
end function
void createStack(stack *s) {
s->first = NULL;
}
void push(stack *s, elem e) {
tNode *tmp;
tmp = getMemory();
if (tmp == NULL) {
printf("\n Error: not enough free memory\n");
} else {
duplicate(tmp->e, e);
tmp->next = s->first;
s->first = tmp;
}
}
void pop(stack *s) {
tNode *tmp;
if (s->first == NULL) {
printf("\n Error: empty stack\n");
} else {
tmp = s->first;
s->first = s->first->next;
destroy(tmp->e);
freeMemory(tmp);
}
}
elem top(stack s) {
elem e;
if (s.first == NULL) {
printf("\n Error: empty stack\n");
} else {
duplicate (e, s.first->e);
}
return e;
}
boolean emptyStack(stack s) {
return (s.first == NULL);
}
Exercici exemple
En aquest exercici exemple estenem el TAD pila amb una nova operació: popn. Aquesta operació retorna la pila sense els n primers elements, sent n un nombre enter major que zero. Si la pila conté menys de n elements, llavors retorna error.
Per resoldre-ho utilitzem la definició del tipus pila tal com es defineix en aquest mòdul. Es treballa directament amb la implementació del tipus pila. No s'utilitza cap de les operacions bàsiques del tipus (pop, top, push, ...).
[Exemple 07_09]
action popn(inout s: tStack; in n: integer)
var
tmp : pointer to tNode;
count: integer;
end var
if s.first = null then
writeString("error: empty stack");
else
count := 0;
while ((s.first)^.next ≠ NULL and count<n) do
tmp := s.first;
s.first := (s.first)^.next;
destroy(tmp^.e);
freeMemory(tmp);
count := count+1;
end while
if count < n then
writeString("error: stack with less than n elements");
end if
end if
end action
void popn(stack *s, int n) {
tNode *tmp;
int count;
if (s->first == NULL) {
printf("\n Error: empty stack\n");
} else {
count = 0;
while (s->first->next != NULL && count < n) {
tmp = s->first;
s->first = s->first->next;
destroy(tmp->e);
freeMemory(tmp);
count = count+1;
}
if (count < n) {
printf("\n Error: stack with less than n elements\n");
}
}
}
Cua (tQueue)
Recordem que una cua (queue) és una seqüència lineal d'elements amb la característica que els elements s'insereixen pel final de la cua i s'extreuen pel principi de la cua. En la Taula 2 es llisten les operacions que defineixen aquest TAD.
Taula 2. Llista d'operacions sobre el TAD queue
| Operació | Descripció |
|---|---|
| createQueue | Crea una cua buida |
| enqueue | Insereix un element en la cua |
| dequeue | Elimina un element de la cua |
| head | Retorna l'element situat al principi de la cua |
| emptyQueue | Retorna true si la cua està buida, altrament retorna false |
Implementació del tipus
La implementació proposada es basa en punters. El primer element de la cua, que és per on es treuen els elements, és apuntat pel punter first, i el final de la cua, que és l'extrem per on s'insereixen els elements, és apuntat pel punter last.
En la Figura 4 es mostra a l'esquerra la representació gràfica d'una cua, on el primer element (head) és v1. A la dreta es mostra la representació de la cua utilitzant punters. El punter first, indica el primer element (el següent a ser extret), mentre que l'element apuntat per last indica l'últim inserit. Cada element té un punter al següent element en la cua. L'últim element de la cua té el punter al següent amb valor null.
Figura 4. Representació d'una cua (esquerra) i implementació utilitzant punters (dreta). Imatge extreta i adaptada de [1]
[Exemple 07_10]
type
tNode = record
e: elem;
next: pointer to tNode;
end record
tQueue = record
first: pointer to tNode;
last: pointer to tNode;
end record
end type
typedef struct tNode {
elem e;
struct tNode *next;
} tNode;
typedef struct {
tNode *first;
tNode *last;
} tQueue;
Implementació de les operacions
Els elements s'encuen (operació enqueue) pel final de la cua i es desencuen (operació dequeue) pel principi de la cua (posició 1). Unicament s'han d'actualitzar els punters al primer element (en cas d'eliminar un element) o el punter al final de la cua (en cas d'inserir un element).
Figura 5. Operació encuar (enqueue). Imatge extreta i adaptada de [1]
En la Figura 5 es mostra gràficament l'algorisme seguit per encuar un element en la cua (enqueue). En la cua els
elements s'insereixen per l'extrem final. L'extrem final d'una cua està apuntat pel punter last. Per inserir un nou element, primer s'ha d'obtenir espai per al nou node, tmp en el dibuix, i a continuació s'han d'actualitzar el valor dels punters de forma d'enllaçar tmp a la cua. Finalment s'ha d'actualitzar el punter last, que apunta ara al nou element, és a dir l'últim inserit.
[Exemple 07_11]
function createQueue(): tQueue
var
q: tQueue;
end var
q.first := null;
q.last := null;
return q;
end function
action enqueue(inout q: tQueue; in e: elem)
var
tmp: pointer to tNode;
end var
tmp := getMemory();
if tmp = null then
writeString("error: not enough free memory");
else
duplicate(tmp^.e, e);
tmp^.next := null;
if q.first = null then
{ empty queue }
q.first := tmp;
else
(q.last)^.next := tmp;
end if
q.last := tmp;
end if
end action
action dequeue(inout q: tQueue)
var
tmp: pointer to tNode
end var
if q.first = null then
writeString("error: empty queue");
else
tmp := q.first;
q.first := (q.first)^.next;
if q.first = null then
q.last := null;
enf if
destroy(tmp^.e);
freeMemory(tmp);
end if
end action
function head(q: tQueue): elem
var
e: elem
end var
if q.first = null then
writeString("error: empty queue");
else
duplicate(e, (q.first)^.e);
end if
return e;
end function
function emptyQueue(q: tQueue): boolean
return (q.first = null);
end function
void createQueue(tQueue *q) {
q->first = NULL;
q->last = NULL;
}
void enqueue(tQueue *q, elem e) {
tNode *tmp;
tmp = getMemory();
if (tmp == NULL) {
printf("\n Error: not enough free memory\n");
} else {
duplicate (tmp->e, e);
tmp->next = NULL;
if (q->first == NULL) {
/* empty queue */
q->first = tmp;
} else {
q->last->next = tmp;
}
q->last = tmp;
}
}
void dequeue(tQueue *q) {
tNode *tmp;
if (q->first == NULL) {
printf("\n Error: empty queue\n");
} else {
tmp = q->first;
q->first = q->first->next;
if (q->first == NULL) {
q->last = NULL;
}
destroy(tmp->e);
freeMemory(tmp);
}
}
elem head(tQueue q) {
elem e;
if (q.first == NULL) {
printf("\n Error: empty queue\n");
} else {
duplicate(e, q.first->e);
}
return e;
}
boolean emptyQueue(tQueue q) {
return (q.first == NULL);
}
Exercici exemple
En aquest exercici exemple estenem el TAD cua amb una nova operació: swapFirst2. Aquesta operació retorna la cua amb els dos primers elements intercanviats de posició. Si la cua conté menys de 2 elements, llavors retorna error.
Per resoldre-ho utilitzem la definició del tipus cua tal com es defineix en aquest mòdul. Es treballa directament amb la implementació del tipus cua. No s'utilitza cap de les operacions bàsiques del tipus (enqueue, dequeue, head, ...).
[Exemple 07_12]
action swapfirst2(inout q: tQueue)
var
tmp: pointer to tNode;
end var
if q.first = null then
writeString("error: empty queue");
else
si (q.first)^.next = null then
writeString("error: queue with only one element");
else
tmp := q.first
q.first := (q.first)^.next;
tmp^.next:= (tmp.next)^.next;
(q.first)^.next := tmp;
end if
end if
end action
void swapFirst2(tQueue *q) {
tNode *tmp;
if (q->first == NULL) {
printf("\n Error: empty queue \n");
} else {
if (q->first->next == NULL) {
printf("\n Error: queue with only one element \n");
} else {
tmp = q->first;
q->first = q->first->next;
tmp->next = tmp->next->next;
q->first->next = tmp;
}
}
}
Llista (tList)
Recordem que una llista és una seqüència lineal d'elements amb la característica que és possible inserir, eliminar i consultar elements en qualsevol posició de la seqüència. En la Taula 3 es mostren les operacions que defineixen aquest TAD.
Taula 3. Llista d'operacions sobre el TAD list
| Operació | Descripció |
|---|---|
| createList | crea una cua buida |
| insert | insereix un element en la llista |
| delete | elimina un element de la llista |
| get | retorna l'element situat en una posició donada de la llista |
| end | retorna true si la posició donada és posterior a l'última, altrament retorna false |
| emptyList | retorna true si la llista està buida, altrament retorna false |
Implementació del tipus
La implementació proposada es basa en punters. Per a això es disposa d'un punter al primer element de la llista que anomenem first. Donat que tant la inserció com l'esborrat d'elements es poden realitzar en qualsevol posició de la llista, serà necessari desplaçar el punter del començament fins a la posició desitjada. No obstant això, no s'ha de perdre mai el punter al començament de la llista ja que els desplaçaments són solament en un sentit, per la qual cosa si es perd aquesta referència, no serà possible mai més tornar al començament de la llista.
Aquesta és una proposta d'implementació alternativa a la qual es troba en les anotacions de la bibliografia [1]. Les diferències principals són que en la implementació dels apunts [1] es manté un punter a l'element anterior a l'actual (punt d'interès) i un element fantasma. Aquest element fantasma existeix perquè la utilització i manteniment d'aquest punter a l'element anterior sigui homogènia, sense importar si l'element actual o punt d'interès és el primer element. D'aquesta forma es facilita la seva implementació i no cal diferenciar el primer cas en operacions com la inserció i l'esborrat d'elements.
Així mateix, a la implementació dels apunts la inserció i l'esborrat d'elements es realitzen a partir de la posició de l'element actual, mentre que en la proposada aquí la inserció i esborrat es realitzen en la posició explícita indicada com a paràmetre de l'operació.
A la Figura 6 es mostra a l'esquerra la representació gràfica d'una llista. A la dreta es mostra la representació de la llista utilitzant punters. El punter first, apunta al primer element de la llista. Cada element ocupa una posició (ordinal en la llista) indicada en la figura com index. Cada element té un punter al següent element en la llista. L'últim element de la llista té el punter al següent amb valor null.
Figura 6. Representació d'una llista (esquerra) i implementació utilitzant punters (dreta).
[Exemple 07_13]
type
tNode = record
e: elem;
next: pointer to tNode;
end record
tList = record
first: pointer to tNode;
end record
end type
typedef struct tNode {
elem e;
struct tNode *next;
} tNode;
typedef struct {
tNode *first;
} 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, unicament caldrà trobar la posició corresponent i modificar l'encadenat de punters. El mateix succeeix en eliminar un element de la llista: s'han d'actualitzar els punters al següent de l'element anterior a l'eliminat.
Figura 7. Operació eliminar (delete)
En la Figura 7 es mostra gràficament l'algorisme seguit per eliminar un element de la llista (delete). En l'exemple de la figura s'elimina l'element amb ordinal 2, és a dir el que està en la segona posició començant per l'element apuntat per first. Es recorre primer la llista buscant la posició amb index=2. Es manté un punter a l'element anterior (prev) per actualitzar després els punters de l'element anterior a l'element següent a l'eliminat. La memòria ocupada per l'element a eliminar (tmp) és alliberada
[Exemple 07_14]
function createList(): tList
l.first := null;
end function
action insert(inout l: tList; in e: elem; in index: integer)
var
tmp: pointer to tNode;
prev: pointer to tNode;
end var
tmp := getMemory();
si tmp = null then
writeString("error: not enough free memory");
else
duplicate(tmp^.e, e);
if index = 1 then
{ no previous element }
tmp^.next := l.first;
l.first := tmp;
else
prev := getNth(l, index-1);
if prev ≠ null then
{ standard case }
tmp^.next := prev^.next;
prev^.next := tmp;
else
writeString("error: not enough elements");
end if
end if
end if
end action
action delete(inout l: tList; in index: integer)
var
tmp: pointer to tNode;
prev: pointer to tNode;
end var
if index = 1 then
{ no previous element }
tmp := l.first;
if l.first = null then
writeString("error: empty list");
else
l.first := tmp^.next;
destroy(tmp^.e);
freeMemory(tmp);
end if
else
prev := getNth(l, index-1);
if prev ≠ null then
{ standard case }
tmp := prev^.next;
if tmp = null then
writeString("error: index position doesn't exist");
else
prev^.next := tmp^.next;
destroy(tmp^.e);
freeMemory(tmp);
end if
else
writeString("error: index position doesn't exist");
end if
end if
end action
function get(l: tList; index: integer): elem
var
e: elem;
curr: pointer to tNode;
end var
curr := getNth(l, index);
if curr = null then
writeString("error: index position doesn't exist");
else
duplicate(e, curr^.e);
end if
return e;
end function
function end(n: pointer to tNode): boolean
return (n = null);
end function
function emptyList(l: tList): boolean
return (l.first = null);
end function
{ Auxiliary function }
function getNth(l: tList; index: integer): pointer to tNode
var
i: integer;
prev: pointer to tNode;
end var
i := 1;
prev := l.first;
while i < index and prev ≠ null do
prev := prev^.next;
i := i+1;
end while
return prev;
end function
void createList(tList *l) {
l->first = NULL;
}
void insert(tList *l, elem e, int index) {
tNode *tmp;
tNode *prev;
tmp = getMemory();
if (tmp == NULL) {
printf("\n Error: Not enough free memory\n");
} else {
tmp->e = e;
if (index == 1) {
/* no previous element */
tmp->next = l->first;
l->first = tmp;
} else {
prev = getNth(l, index-1);
if (prev != NULL) {
/* standard case */
tmp->next = prev->next;
prev->next = tmp;
} else {
printf("\n Error: not enough elements \n");
}
}
}
}
void delete(tList *l, int index) {
tNode *tmp;
tNode *prev;
if (index == 1) {
/* no previous element */
tmp = l->first;
if (l->first == NULL) {
printf("\n Error: empty list\n");
} else {
l->first = tmp->next;
destroy(tmp->e);
freeMemory(tmp);
}
} else {
prev = getNth(l, index-1);
if (prev != NULL) {
/* standard case */
tmp = prev->next;
if (tmp == NULL) {
printf("\n Error: index position doesn't exist\n");
} else {
prev->next = tmp->next;
destroy(tmp->e);
freeMemory(tmp);
}
} else {
printf("\n Error: index position doesn't exist\n");
}
}
}
elem get(tList l, int index) {
tNode *curr;
curr = getNth(&l, index);
if (curr == NULL) {
printf("\n Error: index position doesn't exist\n");
} else {
return curr->e;
}
}
boolean end(tNode *n) {
return (n == NULL);
}
boolean emptyList(tList l) {
return (l.first == NULL);
}
{ Auxiliary function }
tNode *getNth(tList *l, int index) {
int i;
tNode *prev;
i=1;
prev = l->first;
while i<index && (prev != NULL) {
prev = prev->next;
i = i+1;
}
return prev;
}
Exercici exemple
En aquest exercici exemple complementem el tipus amb una nova funció: getindex. Aquesta funció retorna l'index on es troba l'element e. Si la llista no conté l'element llavors retorna error.
Per resoldre'l utilitzarem la definició del tipus lista segons es defineix en aquest mòdul. S'utilitza directament amb la implementació del tipus llista. No s'utilitza cap de les operacions bàsiques del tipus (insert, delete, get, ...).
[Exemple 07_15]
function getIndex(l: tList; e: elem): integer
var
res: integer;
i: integer;
current: pointer to tNode;
found: boolean
end var
found := false;
res := 0;
i := 0;
current := l.first;
while current ≠ null and found = false do
found := equal(current^.e, e);
i := i+1;
current := current^.next;
end while
if found = false then
writeString("error: element does not exist");
else
res := i;
end if
return res;
end function
int getIndex(tList l, elem e) {
int res;
int i;
tNode *current;
boolean found;
res = 0;
i = 0;
current = l.first;
found = FALSE;
while (current!=NULL && found==FALSE) {
found = equal(current->e, e);
i++;
current = current->next;
}
if (found == FALSE) {
printf("\n Error: element doesn't exist\n");
} else {
res = i;
}
return res;
}
Resum
En aquest mòdul hem recordat que significa un Tipus Abstracte de Dades (TAD) així com els TAD que respresentan
seqüències: piles, cues i llistes.
Així mateix s'ha recordat el concepte de punters i de memòria dinàmica.
S'ha mostrat una implementació dels TAD pila, cua i llistes utilitzant punters. Per a cada tipus de TAD es mostra un exercici exemple basat en afegir una operació més al TAD, on es treballa directament amb la implementació del TAD.
Bibliografia
[1] Estructuras de datos básicas: Secuencias. Xavier Sáez Pous. Material docente de la UOC.