Torna alla pagina di Algoritmi e strutture dati

 :: Algoritmi e strutture dati - Specifiche ::

Liste

Sintassi

• crealiste: () -> lista
  Crea ed inizializza una lista ad un particolare valore, di solito la sequenza vuota.
• listavuota: (lista) -> booleano
  Restituisce vero o falso a seconda che la lista sia vuota o no.
• primolista: (lista) -> posizione
  Permette di accedere al primo elemento della lista.
• ultimolista: (lista) -> posizione
  Permette di accedere all'ultimo elemento della lista.
• succlista: (posizione, lista) -> posizione
  Permette di passare all'elemento successivo della lista rispetto alla posizione indicata.
• predlista: (posizione, lista) -> posizione
  Permette di passare all'elemento precedente della lista rispetto alla posizione indicata.
• finelista: (posizione, lista) -> booleano
  Restituisce vero o falso a seconda che la posizione sia o no l'ultima della lista.
• leggilista: (posizione, lista) -> tipoelem
  Legge il valore dell'elemento nella posizione specificata della lista.
• scrivilista: (tipoelem, posizione, lista) -> lista
  Cambia il valore dell'elemento nella posizione specificata della lista.
• inslista: (tipoelem, posizione, lista) -> lista
  Inserisce un nuovo elemento nella lista.
• canclista: (posizione, lista) -> lista
  Cancella l'elemento nella posizione specificata della lista.

Semantica

• crealista() = L'
  Post: L' = Λ
• listavuota(L) = b
  Post: b = vero, se L = Λ; b = falso altrimenti
• primolista(L) = p
  Post: p = pos₁
• ultimolista(L) = p
  Post: p = pos_n
• succlista(p, L) = q
  Pre: L = a₁, a₂, ... , a_n e p = pos_i per un i, 1≤i≤n
  Post: q = pos_i+1
• predlista(p, L) = q
  Pre: L = a₁, a₂, ... , a_n e p = pos_i per un i, 1≤i≤n
  Post: q = pos_i-1
• finelista(p, L) = b
  Pre: L = a₁, a₂, ... , a_n e p = pos_i per un i, 1≤i≤n+1
  Post: b = vero, se p = pos₀ o p = pos_n+1 ; b = falso altrimenti
• leggilista(p, L) = a
  Pre: L = a₁, a₂, ... , a_n e p = pos_i per un i, 1≤i≤n
  Post: a = a_i
• scrivilista(a, p, L) = L'
  Pre: L = a₁, a₂, ... , a_n e p = pos_i per un i, 1≤i≤n
  Post: L' = a₁, a₂, ... , a_i-1, a, a_i+1, ... , a_n
• inslista(a, p, L) = L'
  Pre: L = a₁, a₂, ... , a_n e p = pos_i per un i, 1≤i≤n+1
  Post: L' = a₁, a₂, ... , a_i-1, a, a_i+1, ... , a_n se 1≤i≤n
  L' = a₁, a₂, ... , a_n, a se i = n + 1
  L' = a₁, a₂, ... , a_n se i = 0
• canclista(p, L) = L'
  Pre: L = a₁, a₂, ... , a_n e p = pos_i per un i, 1≤i≤n
  Post: L' = a₁, a₂, ... , a_i-1, a_i+1, ... , a_n

Implementazione in C++

Si condidera una lista bidirezionale circolare con sentinella

Realizzazione con puntatori

typedef struct _cella {
   tipoelem elemento;
   struct _cella *next, *prev;
} cella;

typedef cella posizione, lista;
typedef short boolean;

• inslista:
  

  
  void inslista (tipoelem a, posizione *p) {
     posizione *q;
     q = malloc (sizeof(cella));
     q->elemento = a;
     q->prev = p->prev;
     q->next = p;
     p->prev->next = q;
     p->prev = q;
  }
  
• canclista:
  

  
  void canclista (posizione **p) {
     posizione *q;
     q = *p;
     q->prev->next = q->next;
     q->next->prev = q->prev;
     *p = q->next;
     free(q);
  }
  

Realizzazione con cursori

#define MAXL 100

typedef int lista, posizione;
typedef struct _cella {
   posizione prev, next;
   tipoelem elemento;
} cella;

lista listalibera;
cella spazio[MAXL];

• inizializzare:
  

  
  void inizializza () {
     int i; 
     listalibera = 0;
     spazio[0].next = 1;
     spazio[0].prev = MAXL - 1;
     for (i=1; i<MAXL; i++) {
        spazio[i].next = (i+1) % MAXL;
        spazio[i].prev = (i-1) % MAXL;
     }
  }
  
• sposta:
  Trasferisce la cella putanta da p nella cella prima di quella puntata da q.
  

  
  void sposta (posizione *p, posizione *q) {
     posizione t;
     t = spazio[p].next;
     spazio[spazio[p].prev].next = spazio[p].next;
     spazio[spazio[p].next].prev = spazio[p].prev;
     spazio[p].prev = spazio[q].prev;
     spazio[spazio[q].prev].next = p;
     spazio[p].next = q;
     spazio[q].prev = p;
     q = p;
     p = t;
  }
  

Torna alla pagina di Algoritmi e strutture dati