Programmazione 2

A cura di Giovanna Di Mauro

Capitolo 1: Operatori logici e bitwise

 Tipi

 Operatori Logici

 Operatori Bitwise

 Rappresentazione

 Uso operatori per effettuare moltiplicazioni e divisioni intere per 2

 Scambio di variabili

 Azzeramento dei bit meno significativi

 Uso operatori bitwise per estrarre bit da una variabile

 Function per la stampa dei bit di un numero di qualunque tipo

Capitolo 2: Tipo numerico intero

 Cambiamenti di base

 Tipo intero nei linguaggi di programmazione

 Range degli interi in C

Capitolo 3: Tipo numerico reale

 Sistema aritmetico floating-point

 Sistema standard 754

 Oggetti del Sistema Aritmetico Floating point

 Estrazione di alcuni bit dal contenuto di una variabile

 Schemi di Rounding

 Errori di Roundoff

 Unit in the Last Place

 Esempi di algoritmi che infrangono la massima accuratezza

Capitolo 4: Stringhe

 Function che restituisce il nome del mese

 I/O di caratteri e di stringhe

 Malloc

 Function della libreria <string.h>

 String Matching

Capitolo 5: Allocazione dinamica in C

 Allocazione dinamica di matrici in C

 Matrice Memorizzata per righe:

 Leading Dimension Array

Capitolo 7: Gestione dei file sequenziali in C

 File binari in C e funzioni di I/O:

 Funzioni di I/O per file di testo

 Fine di un file testo e binario

 Lettura bufferizzata

 String matching su file

 Ricerca diretta di un pattern definito in input in un file

 Lettura bufferizzata del testo da file

A cura di Giovanna Di Mauro

Capitolo 8: strutture dati dinamiche lineari

 Strutture dinamiche

 Operazioni sulle strutture dinamiche lineari:

 Principali strutture dinamiche lineari: pila e coda

 Principali strutture dinamiche lineari: lista

 Operazioni su lista lineare: visita

 Implementazione C di una lista lineare

 Puntatori a struttura

 Struttura autoriferente dinamica

 Creazione di una lista vuota:

 Operazioni di eliminazione e inserimento:

 Inserimento in testa

 Inserimento nel mezzo

 Programma ricorsivo per la costruzione di una lista

 Particolati organizzazioni dei dati per una lista lineare

 NODO SENTINELLA:

 LISTA LINEARE GENERICA:

 Applicazione delle liste ad altre strutture dati

 Lista circolare e lista bidirezionale

 Liste multiple: rappresentazioni matrici sparse

Capitolo 9: Strutture dati dinamiche gerarchiche

 Generalità sulla struttura dati albero

 Visita di un albero per livelli

 Alberi binari

 Algoritmi di visita di un albero binario

 Parsing

 Strutture dati per la rappresentazione di un albero binario

 Uso di array

 Uso di lista multipla

 Algoritmi di visita iterativi di un albero binario

 Algoritmi di visita ricorsivi di un albero binario

 Alberi tramati

 Alberi binari di ricerca

 Ricerca binaria mediante albero binario di ricerca

 Costruzione di un albero binario di ricerca

 Bilanciamento

 Struttura dati Heap

 Memorizzazione di un Heap

 Traduzione di un array in un heap – costruzione top-down

 Costruzione bottom-up di un heap

Capitolo 10: Strutture dati dinamiche reticolari

 Grafo orientato e non orientato

 Cammino di un grafo

 Rappresentazione in memoria di un grafo

 Matrice di adiacenze

A cura di Giovanna Di Mauro

 Lista di adiacenze

 Algoritmi di visita di una struttura reticolare – Parte 1

 Algoritmo DFS(depht-First-Search) per la visita di un grafo

 Versione iterativa dell’algoritmo DFS

 Algoritmi di visita di una struttura reticolare – Parte 2

 Algoritmo BFS (breadth-first-search, visita in ampiezza)

Capitolo 11: Tecniche di programmazione ricorsiva

 Tipi di ricorsione: classificazione

 Profondità di ricorsione

 ANALISI PROFONDITà DI RICORSIONE

 Esempi di algoritmi ricorsivi

 Algoritmo di Horner

 Costruzione ricorsiva di una lista lineare

 Visita ricorsiva di un albero binario

 Ricerca ricorsiva su un albero binario di ricerca

Capitolo 12: Algoritmi di ordinamento e complessità quadratica

 Selection sort

 Bubble Sort

 Insertion Sort

Capitolo 13: Algoritmi di ordinamento della classe “Divide et Impera”

 Merge Sort

 Quick Sort

 Heap Sort

A cura di Giovanna Di Mauro

A cura di Giovanna Di Mauro

Capitolo 1: Operatori logici e bitwise

Tipi

I tipi di dati scalari predefiniti sono:

1) Tipo logico o booleano

2) Tipo carattere o stringa

3) Tipo numerico (intero o reale)

Le informazioni sono presenti nel calcolatore in forma binaria, ossia in forma di

sequenze di 0 e 1.

Per comprendere il significato dei bit bisogna conoscere la rappresentazione binaria

di un tipo. Prima di tutto dobbiamo quantificare lo spazio occupato da un dato tipo

in memoria.

Abbiamo una function adatta alla situazione:

void main()

{ printf(“sizeof(char) = d%\n”, sizeof(char));

}

Possiamo utilizzare la funzione sizeof per qualsiasi tipo. L’argomento della sizeof è

un dato tipo e come output è restituito il numero di byte che occupa.

Sappiamo che i tipi occupano diversi tipi di spazi che sono:

- Char -> 1 byte

- Short Int -> 2 byte

- Long Int -> 4 byte

- Puntatore -> 4 byte

Il puntatore occupa 4 byte poiché i processori con cui lavoriamo attualmente

possono lavorare con parole di un massimo di 32 bit.

Operatori Logici

Come sappiamo in C il tipo logico non esiste. Il valore di una qualsiasi variabile viene

interpretato con 0 e 1 (falso e vero).

Il C permette l’uso di operatori logici che hanno il seguente ordine:

1) !A -> not (negazione) è un operatore unario, agisce su un solo

operando(cambia il valore di verità)

2) A&&B -> and (congiunzione) vera solo se due operandi sono

contemporaneamente veri

3) A||B -> or (disgiunzione) risulta falsa solo se i due operandi sono falsi

Come li applichiamo:

A cura di Giovanna Di Mauro

Le variabili sono utilizzate come se fossero di tipo logico. Se abbiamo un tipo

short ad esempio se associamo ad A il valore 5 e lo confrontiamo con 5, assume

valore di vero ossia 1, un qualsiasi valore diverso da 0 ha come valore booleano 1

ossia vero. Se fosse confrontato con 6, assumerebbe valore falso ossia 0.

Void main()

{ Float F; short A, B, C; notA, notB, notC, notD, notF;

A = 5 == 5; /* A è true */

B = 5 == 6; /* B è false */

C=10; D=-7; F=1.6f; /* C, D, F */

Printf(“\nA = %d\tB= %d\tC = %d\t D = %d\t F = %f\n”, A, B, C, D, F);

notA= !A; notB = !B; notC = !C; notD = !D; notF = !F;

printf(“\nnotA = %d\tnotB= %d\tnotC = %d\t notD = %d\t notF = %f\n”, notA, notB, notC,

notD, notF);

}

Una tipica applicazione booleana è il costrutto If-else (se è vero if se è falso else).

Possiamo talvolta creare il tipo logical con il costruttore TYPEDEF:

enum boolean {false; true}; /* il tipo enum associa a quello in parentesi i numeri naturali*/

typedef enum boolean LOGICAL;

LOGICAL falso, vero;

Operatori Bitwise

Il linguaggio C consente di operare sui singoli bit di una variabile usando i bitwise.

Questi operatori agiscono sui bit degli operandi di tipo intero(char, short, long e int)

signed e unsigned:

1) Il tilde è l’operatore di complemento NOT-> ~A

2) L’umperstand è l’operatore AND -> A&B

3) L’OR inclusivo -> A|B

4) L’OR esclusivo -> A^B

5) Operatori di shift -> << e >>

Le differenze tra gli operatori bitwise e operatori logici sono:

1) Utilizzo di operatori diversi

A cura di Giovanna Di Mauro

2) Gli operandi degli operatori logici sono le voci intere, valore associato ad una

variabile, gli operandi bitwise sono i singoli bit della voce associata ad una

variabile. Ossia nel primo caso dobbiamo considerare tutta l’interezza dei bit

nel secondo dobbiamo considerare bit per bit.

Facciamo un esempio:

- Se abbiamo 0110 && 0011 dobbiamo considerare l’interezza dei bit, visto che

stiamo considerando un operatore logico. Quindi sapendo che 0000 è l’unica

condizione di false avremo che entrambe le quaterne sono vere e quindi un

operatore AND con due quaterne vere quindi il risultato sarà vero, ossia:

0001 -> inteso come valore vero

- L’operatore bitwise sappiamo che agisce bit su bit (li calcoliamo ad incrocio):

1) 0&1 -> 0

2) 1&1 -> 1

3) 1&0 -> 0

4) 0&0 -> 0

I risultati sono differenti infatti.

Gli operatori di shifting, di scorrimento, non fanno altro che prendere i bit di una

variabile e traslarli verso destra o sinistra, riempiendo gli spazi creatisi con dei bit 0.

A<<4 produce lo spostamento di tutti i bit della variabile intera A di 4 posizioni verso

sinistra. Mentre B>>3 produce lo spostamento di tutti i bit della variabile intera B di

3 posizioni verso destra.

Rappresentazione

Per visualizzare un tipo char, ad esempio z, se usiamo il codice:

1) %c visualizzeremo il contenuto della variabile come carattere (‘z’)

2) %d visualizzeremo il contenuto della variabile come decimale

3) %x visualizzeremo il contenuto della variabile come esadecimale (7A)

Quindi per eseguire la visualizzazione della rappresentazione binaria abbia bisogno

di: 1) Creare due gruppi: abbiamo 8 bit, estrapoliamo le cifre significative usando

l’operatore di shift. I 4 bit più significativi si ottengono shiftando a destra i 4

bit più significativi: 0111 1010 -> 0000 0111. Per estrasse i 4 bit meno

significativi shiftiamo a sinistra di 4 bit e poi di nuovo di 4 bit a destra

ottenendo quindi: 0111 1010 -> 1010 0000 -> 0000 1010

2) Conversione dei due gruppi: Una volta estratti i due gruppi da 4 bit ciascuno,

si salvano i valori numerici interi in due variabili (A e B ad esempio)

A cura di Giovanna Di Mauro

3) Valore ottenuto come indice nell’array bit di stringhe: si utilizzano i due valori

ottenuti come indici per accedere alle sue componenti. A questo punto

stampando nell’ordine giusto le stringhe così selezionate, si ottiene la

soluzione al problema iniziale.

Uso operatori per effettuare moltiplicazioni e divisioni intere per 2

Nel sistema binario moltiplicare un numero per 2 significa porre uno 0 nella

posizione della cifra meno significativa (sulla destra), ossia uno shift verso sinistra di

1 posizione. La divisione di un numero per 2 significa porre uno 0 nella posizione più

significativa (sulla sinistra) ossia uno shift verso destra di una posizione.

Scambio di variabili

Per effettuare lo scambio di variabili abbiamo bisogno di una variabile di appoggio in

cui si salva il contenuto che andrebbe perso.

Possiamo utilizzare gli operatori bitwise (che sono meno convenienti) infatti

utilizzando uno XOR è possibile ottenere lo scambio.

Int x, y;

x=…; y=…;

x=x^y;

y= x^y;

x=x^y;

Azzeramento dei bit meno significativi

Per azzerare i bit meno significativi è necessario predisporre una costante che abbia

una configurazione di bit appropriata affinché l’operatore bitwise ‘&’ azzeri

effettivamente i bit voluti. Ossia si costruisce una costante con tutti 1 quanti sono i

bit che si vogliono azzerare e poi la si completa utilizzando l’operatore NOT.

Esempio 1: in caso di variabile di tipo char (8 bit), con valore 125 decimale, per

realizzare tale operazione occorre una costante avente 8 bit di cui: 6 bit meno

significativi posti a 0 e i due rimanenti posti a 1. Bisogna poi effettuare l’AND tra

variabile e la costante.

Esempio 2: in caso di variabile di tipo short (16 bit) e che ha valore 29125 decimale

occorre una costante da 16 bit di cui: i 6 bit meno significativi a 0 e il restante dei 10

a 1. Infine si fa l’AND.

In entrambi i casi otteniamo un numero ottale.

A cura di Giovanna Di Mauro

Uso operatori bitwise per estrarre bit da una variabile

Per estrasse i bit c’è bisogno di creare delle maschere che fungono da selettori di bit

(insieme agli operatori). La variabile mask si costruisce azzerando tutti i bit meno

quelli che vogliamo estrarre (quindi poniamo questi a 1) e facciamo un AND tra la

variabile e il valore della maschera.

Considerando l’estrazione dei 5 bit meno significativi abbiamo diversi metodi per

costruire una maschera: n

1) Nel primo metodo: applico semplicemente la formula 2 -1

2) Nel secondo metodo: Utilizziamo costanti, che possono essere esadecimali,

decimali, ottali

3) Nel terzo metodo: Si inizializza la maschera a 0, poi si itera per un numero pari

a quello dei bit che vogliamo estrarre. Ad ogni iterazione aggiungiamo un 1 e

shiftiamo verso sinistra di 1.

Per estrarre bit più significativi:

Proseguiamo come detto sopra, quindi azzerando la maschera e iterando

aggiungendo degli 1. Poiché dobbiamo capire quali sono i bit più significativi,

utilizziamo la funzione SIZEOF (che ci indica il numero di byte e non di bit!).

Function per la stampa dei bit di un numero di qualunque tipo

Abbiamo bisogno di un costrutto UNION.

Il costrutto UNION è simile alla struct, l’unica differenza è l’allocazione di byte della

memoria per ciascun tipo di dato. Il size di una struct è dato dalla somma dei singoli

size dei campi mentre il costrutto UNION alloca la stessa quantità di memoria per le

union word32bit {long la; /*union word32bit è il tipo*/

short sa[2]; /* la, sa, ca sono variabili*/

char ca[4];

} w;

Per quanto riguarda la memoria la union alloca 32 byte (in questo caso) quindi:

1) La -> è un intero long, utilizza 32 bit;

2) Sa -> è un array di 2 componenti short, 16x2= 32 bit;

3) Ca -> è un aray di 4 componenti char, 4x8= 32 bit;

La, ca e sa fanno riferimento alle stesse locazioni di memoria, soltanto raggruppate e

quindi interpretate con lunghezze diverse.

A cura di Giovanna Di Mauro Si noti come il costrutto UNION permetta

la dichiarazione di una variabile “word”,

che a seconda dell’interpretazione può

essere una variabile float, long, char o

short (lo spazio allocato deve essere

sempre 32 bit). Il programma esegue una

semplice acquisizione della variabile che si

vuole stampare. Mediante lo switch case

viene selezionata (a seconda del tipo) una

diversa interpretazione della variabile

(decimale, esadecimale e binaria).

Per accedere ai campi della UNION

utilizziamo bit_show, che visualizza i bit di

variabili per un massimo di 32 bit.

Consente di estrarre i bit a blocchi di byte

(massimo 4).

Il primo FOR azzera la variabile, il secondo

compie tante iterazioni quanti sono i byte

necessari per rappresentare il tipo.

L’estrazione dei bit avviene tramite il ciclo

FOR più interno che come visto prima

procede estraendo il bit meno significativo

e shiftandolo verso destra.

Alla fine viene eseguito un ciclo di stampa

(con il while del main).

A cura di Giovanna Di Mauro

Capitolo 2: Tipo numerico intero

Il sistema di numerazione decimale dipende dalla rappresentazione posizionale,

ossia in base alla posizione le cifre hanno un peso diverso. Un qualsiasi sistema che

dipende dalla rappresentazione posizionale è a tutti gli effetti una combinazione

lineare: α b + α b + … + α b

1 1 2 2 n n

b -> rappresenta l’elemento (ossia la base)

α -> rappresenta la variabile

Cambiamenti di base

1) Da base diversa da 10 a base 10: si deve scriverlo sotto forma di polinomiale

quindi avendo (1010) lo scriviamo in forma polinomiale ->

2

3 2 1 0

1x2 +0x2 +1x2 +0x2 quindi avremo -> 8 + 0 + 2 + 0 -> ossia 10 in base 10.

2) Da base 10 a una base diversa da 10: dobbiamo semplicemente applicare

delle divisioni successive per la base interessata e poi considerare i resti.

Scrivendo i resti dall’ultimo al primo otteniamo il numero desiderato.

3) Da base 10 a una base diversa da 10 (parte frazionaria): moltiplichiamo la

parte frazionaria per la nuova base considerata, la parte intera servirà come

cifra del numero mentre la parte frazionaria sarà soggetta ad una nuova

moltiplicazione.

4) Da base 2 a una base potenza di 2: suddividiamo il numero in gruppi di n bit

dove n è pari a log . Se nel numero vi sono presenti meno bit di quanti ne

2

occorrano, si aggiungeranno degli zeri non significativi fino a raggiungere il

numero richiesto.

5) Da base potenza di 2 a base 2: si procede in modo inverso in quanto descritto

sopra.

Tipo intero nei linguaggi di programmazione

Per definire un sistema aritmetico abbiamo bisogno di definire delle operazioni

aritmetiche sui criteri di rappresentazione di memoria di dati di un tipo numerico.

Abbiamo due tipi di sistemi aritmetici per quanto riguarda i calcolatori:

1) Sistema Aritmetico Intero: se utilizziamo un programma che, avendo una

variabile short e copiandola nella variabile di tipo unsigned short, noteremo

una complicanza. Immettendo un numero, ad esempio 13, noteremo che il

valore che apparirà sullo schermo sarà proprio 13. Ma immettendo -13

noteremo un valore diverso. Questo perché si va in overflow

(traboccamento). Infatti è possibile rappresentare solo i numeri compresi in

A cura di Giovanna Di Mauro

un certo intervallo e dopo quell’intervallo i numeri rappresentati saranno per

N

complemento di 2. Intervallo: [ 0; 2 -1]

I tipi di rappresentazione utilizzati dai Sistemi Aritmetici Interi dei computer sono:

1) Rappresentazione per segno e modulo: Viene usata per il campo mantissa

(parte decimale) di un numero reale floating-point. Per rappresentarli

prendiamo il numero e ci avvaliamo di un bit per il segno (0 equivale a – e 1 a

N-1 N-1

+) e il restante per rappresentare il numero. Il range è limitato: [-(2 -1), 2 -

1]

2) Rappresentazione per complemento a 2: Viene usata per memorizzare i