Strutture Dati

Strutture dati

Liste

Una lista è formata da elementi collegati da un puntatore. Ogni nodo ha una key e un puntatore al nodo successivo (Next). L'head è il puntatore al primo nodo, l'ultimo nodo punterà a NULL. Se la lista è doppia ha anche un puntatore all'elemento precedente (Prew). Nel caso di lista circolare, l'ultimo punta al primo elemento della lista, ed è possibile implementarla anche come lista doppia circolare.

Le operazioni sulle liste sono:

• ListInsert(L, x) [void] //inserimento elemento
• ListDelete(L, k) [type] //rimozione elemento
• ListSearch(L, k) [type] //ricerca elemento

Implementazione in pseudo-codice

x = alloc(size of("record")); //ALLOCAZIONE spazio fisico
free(x) //LIBERAZIONE spazio fisico

Inserimento

Il nuovo elemento viene inserito in testa e vi è un aggiornamento del puntatore di testa. È un algoritmo veloce perché inserisce subito senza scorrere la lista.

ListInsert(L, x) {
Next(x) = head[L]
Prew(x) = null //solo se la lista è doppia
Prew(head[L]) = x //solo se la lista è doppia
head[L] = x
}

Cancellazione

Viene cancellato l'elemento con la chiave corrispondente a quella passata, è necessario un aggiornamento dei puntatori. È un algoritmo lento perché deve scorrere la lista a catena, elemento per elemento.

ListDeleteSemplice (L, x) {
P = head[L]
while((P != null) && (Next(P) != x))
P = Next(P)
Next(P) = Next(x)
Free(x)
}

ListDeleteDoppia (L, x) { //sapendo già il punto dove si trova il nodo della lista
if (Prew(x) != null)
Next(Prew(x)) = Next(x)
else head[L] = Next(x)
if(Next(x) != null)
Prew(Next(x)) = Prew(x)
Free(x)
}

Ricerca

Viene ricercato l'elemento con la chiave corrispondente a quella passata. È un algoritmo lento perché deve scorrere la lista a catena, elemento per elemento.

ListSearch (L, k) {
p = head[L]
while(p != null) && (key(p) != k)
p = Next(p)
return p
}

Stack o Pile

Uno stack o pila è formato da elementi gestiti secondo la logica LIFO (Last In First Out), ovvero gli elementi vengono inseriti ed impilati man mano, quando andrò ad estrarli dalla pila sarà dal ultimo al primo. Cercando di togliere un elemento da una pila vuota ci sarà un errore di underflow, mentre cercando di aggiungere a una pila piena ci sarà un errore di overflow. È possibile implementarle anche tramite array e liste, volendo anche con le code.

Le operazioni sulle pile sono:

• Push(P, x) [void] //inserimento elemento
• Pop(P) [type] //rimozione elemento
• Top(P) [type] //restituisce valore elemento in cima
• StackEmpty(P) [boolean] //controlla se pila vuota

Implementazione in pseudo-codice

Array

Implementazione tramite ARRAY, usando index_S come indice per tenere traccia della posizione nella pila.

Inserimento

void Push(S[], k) {
if(index_S == S.length) error(overflow)
else { index_S++ S[index_S] = k }
}

Cancellazione

type Pop(S[]) {
if(index_S == 0) error(underflow)
else { r = S[index_S] index_S-- return (r) }
}

Primo elemento

type Top(S[]) {
if(index_S == 0) error("empty")
else { r = S[index_S] return (r) }
}

Controllo se vuota

boolean SE(S[]) {
if(index_S == 0) return true
else return false
}

Liste

Implementazione tramite LISTE, usando inserimento ed eliminazione in testa.

Inserimento

void Push(S, x) {
Next(x) = head[S]
head[S] = x
}

Cancellazione

type Pop(S) {
if(head[S] == null) error(underflow)
else { r = key(head[S]) p_temp = head[S] head[S] = Next(head[S]) Free(p_temp) return (r) }
}

Primo elemento

type Top(S) {
if(head[S] == null) error("empty")
else { r = key(head[S]) return (r) }
}

Controllo se vuota

boolean SE(S) {
if(head[S] == null) return true
else return false
}

Queue o Code

Una queue o coda è formata da elementi gestiti secondo la logica FIFO (First In First Out), ovvero gli elementi vengono inseriti ed impilati man mano, quando andrò ad estrarli dalla coda sarà dal primo al ultimo. Cercando di togliere un elemento da una pila vuota ci sarà un errore di underflow, mentre cercando di aggiungere a una pila piena ci sarà un errore di overflow. È possibile implementarle anche tramite array e liste, volendo anche con le pile.

Le operazioni sulle code sono:

• EnQueue(Q, k) [void] //inserimento elemento
• DeQueue(Q) [type] //rimozione elemento
• EmptyQueue(Q) [boolean] //controlla se pila vuota

Implementazione in pseudo-codice

Array

Implementazione tramite ARRAY, visto in modo circolare, usando indici H per posizione valorizzata e T per posizione prima vuota.

Inserimento

void EnQueue(Q[], k) {
if(T == H - 1) error(overflow)
else { Q[T] = k T = T++ }
}

Cancellazione

type DeQueue(Q[]) {
if(H == T) error(underflow)
else { r = Q[H] H = H++ return (r) }
}

Controllo se vuota

boolean EQ(Q[]) {
if(H == T) return true
else return false
}

Liste

Implementazione tramite LISTE, usando inserimento in coda e eliminazione in testa.

Inserimento

void EnQueue(Q, x) {
if(tail(Q) != null) {
Next(tail(Q)) = x tail(Q) = x
} else {
head[L] = x tail[L] = x
}
}

Cancellazione

type DeQueue(Q) {
if(head[Q] == null) error(underflow)
else { r = key(head[Q]) p_temp = head[Q] head[Q] = Next(head[Q]) Free(p_temp) return (r) }
}

Controllo se vuota

boolean EQ(Q) {
if(head[Q] == null) return true
else return false
}

Insiemi

Un insieme è una collezione di elementi distinti su cui è possibile effettuare le operazioni dell'insiemistica. È possibile implementarle tramite array e liste.

Operazioni consentite:

• A U B {x ∈ A or x ∈ B} [Unione]
• A ∩ B {x ∈ A and x ∈ B} [Intersezione]
• A - B {x ∈ A and x not ∈ B} [Differenza]

Implementazione in pseudo-codice

Array

Implementazione tramite ARRAY, con esempio su un mazzo di carte.

1^ tecnica

Vengono creati 2 array di stringa da 2 caratteri delle dimensioni del mazzo di carte che vengono riempiti con alcune carte ciascuno. Viene usato un terzo array su cui fare le operazioni. Questa tecnica tiene impegnati sempre degli array della dimensione massima che possono avere.