Category Archives: PROBLEMI

Unità Insiemi

Analisi

Unità

oppure, senza incapsulare …

Unità Complessi

Analisi

Unità

Test

Unità Date

Analisi

Unità

Test

Unità Logici

Analisi

  • Elementi: VERO, FALSO
  • Struttura: semplice
  • Dominio: VERO, FALSO
  • Operazioni: Leggi(), Scrivi(), MyAnd(), MyOr(), MyNot(), MyXor()

Specifica delle operazioni

LEGGI()
  • Interfaccia: Procedure LEGGI(A: LOGICO);
  • Effetti: inserimento del valore logico VERO(1) o FALSO (0) in A
  • Prerequisiti: input controllato di una stringa di tipo ‘Vero’/’Falso’
  • Esempio: Leggi(A);
SCRIVI()
  • Interfaccia: Procedure SCRIVI(A: LOGICO);
  • Effetti: stampa il valore logico associato alla variabile A
  • Prerequisiti: – – –
  • Esempio: Scrivi(A);
MYAND()
  • Interfaccia: Function MYAND(A, B: LOGICO): LOGICO;
  • Effetti: Simula la funzione AND
  • Prerequisiti: – – –
  • Esempio: C:=MYAND(A,B);
MYOR()
  • Interfaccia: Function MYOR(A, B: LOGICO): LOGICO;
  • Effetti: Simula la funzione OR
  • Prerequisiti: – – –
  • Esempio: C:=MYOR(A,B);
MYNOT()
  • Interfaccia: Function MYNOT(A: LOGICO): LOGICO;
  • Effetti: Simula la funzione NOT
  • Prerequisiti: – – –
  • Esempio: A:=MYNOT(A);
MYXOR()
  • Interfaccia: Function MYXOR(A, B: LOGICO): LOGICO;
  • Effetti: Simula la funzione XOR
  • Prerequisiti: – – –
  • Esempio: C:=MYXOR(A,B);

Unità

Test

Lista multipla

Una possibile combinazione di lista multipla è la seguente

  • lista primaria (A-B-C): a doppi puntatori con puntatore di testa e puntatore di coda
  • liste secondarie (p, q-r-s, …): semplici con puntatore di testa e puntatore di coda

image

Dichiarazioni

Lista bidirezionale

Puntatore di testa, puntatore di coda e tre nodi con puntatori nelle due direzioni

image

Dichiarazioni

Operazioni

Aggiungere un nodo in Testa

Aggiungere un nodo in Coda

Aggiungere un nodo in Ordine

Lista circolare

Puntatore di testa e tre nodi con informazioni A-B-C

image

o meglio, con puntatore di coda…

image

Dichiarazioni

Operazioni

Aggiungere un nodo in Testa


Aggiungere un nodo in Coda


Aggiungere un nodo in Ordine

Lista con testa e coda

Puntatore di testa, puntatore di coda e tre nodi con informazioni A-B-C
image

Dichiarazioni

Operazioni

Aggiungere un nodo in Testa

Aggiungere un nodo in Coda

Aggiungere un nodo in Ordine

Eliminare un nodo in Testa

Lista semplice

Puntatore di testa e tre nodi con informazioni A-B-C

image

Dichiarazioni

Operazioni

Aggiungere un nodo in TESTA

Aggiungere un nodo in CODA

Aggiungere un nodo in ORDINE

Aggiungere un nodo DOPO un certo nodo

Per ipotesi Q esiste.

Eliminare un nodo in TESTA

Eliminare un nodo DOPO un certo nodo

Per ipotesi Q esiste mentre Q^.Succ…

Contare i nodi

Eliminare TUTTI i nodi

Confronta

Esercizi

  1. Visualizzare il contenuto della lista
  2. Quanti nodi con una certa informazione?
  3. Ricerca sequenziale (puntatore e/o indice…)
  4. Minimo, massimo, …, totale, media?
  5. Copiare, appendere, concatenare
  6. Eliminare un nodo con chiave, con puntatore
  7. Scambiare le informazioni di due nodi
  8. Ordinare

Insertion sort

Algoritmo alternativo al bubble sort ma più complesso…

A ogni passata l’elemento i-esimo viene parcheggiato in X.
Gli elementi più grandi, che lo precedono, vengono spostati in avanti di una posizione e X viene posizionato al posto giusto.
In questo modo il sottovettore da 1 a i è sicuramente ordinato.

Osserva…

is1