(:title Algoritmi e strutture dati - Specifiche: Liste:)

1. define MAXL 100

Torna alla pagina di Algoritmi e strutture dati

Torna alla pagina di Algoritmi e strutture dati

• 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.

Trasferisce la cella putanta da p nella cella prima di quella puntata da q.\\

• sposta:
  Trasferisce la cella putanta da p nella cella prima di quella puntata da q.\\

• inslista: \\

• canclista: \\

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;
}

L' = a₁, a₂, ... , a_n, a se i = n + 1

L' = a₁, a₂, ... , a_n se i = 0

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);
}

Post: L' = a₁, a₂, ... , a_i-1, a, a_i+1, ... , a_n se 1≤i≤n

• 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

(:title Algoritmi e strutture dati - Specifiche:) Torna alla pagina di Algoritmi e strutture dati - Specifiche

 :: Algoritmi e strutture dati - Specifiche ::

Liste

Sintassi

• crealiste: () -> lista
• listavuota: (lista) -> booleano
• primolista: (lista) -> posizione
• ultimolista: (lista) -> posizione
• succlista: (posizione, lista) -> posizione
• predlista: (posizione, lista) -> posizione
• finelista: (posizione, lista) -> booleano
• leggilista: (posizione, lista) -> tipoelem
• scrivilista: (tipoelem, posizione, lista) -> lista
• inslista: (tipoelem, posizione, lista) -> lista
• canclista: (posizione, lista) -> 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

Implementazione in C++

• creavettore: tipoelem v[n];
• leggivettore: v[i];
• scrivivettore: v[i] = e;

Torna alla pagina di Algoritmi e strutture dati - Specifiche