INFORMATICA TEORIA

Che cos’è l’informatica

DATO INFORMAZIONE

DATO: Elementi oggettivi riferiti ad un elemento o un evento

INFORMAZIONE: Dato dotato di rilevanza (collegamento fra dati) e finalità

(obiettivo)

ha l'obiettivo di creare una rappresentazione dei dati in modo da estrarre

conoscenza tramite la sua elaborazione oppure migliorare la loro
interpretazione da parte dell'utente

Modalità e forme in funzione degli obiettivi

Definizione della Association for Computer Machinery (ACM): «l’informatica è lo

studio sistematico degli algoritmi che descrivono e trasformano l’informazione:
la loro teoria, analisi, progetto, efficienza, realizzazione e applicazione.»

Sistema informatico
Ampia gamma di strumenti utilizzati per svolgere algoritmi in modo
automatico.

Hardware
Un computer è costituito da vari dispositivi fisici ( chiamati hardware) :
Tastiera, schermo, mouse, dischi a stato solido, dischi rigidi, memoria, lettori
DVD.

Software
Programmi eseguibili: istruzioni e dati che consentono all'hardware di compiere
determinate funzioni.

Modello astratto: La macchina di Von Neumann

  La CPU (Central Processing Unit ) esegue l’algoritmo seguendo il flusso di
controllo. La CPU è in grado di eseguire operazioni aritmetiche, logiche e
relazionali .
 La memoria permette di immagazzinare i dati che si stanno elaborando.
 Standard Input: Acquisisce i dati tramite la tastiera.
 Standard Output: Visualizza i risultati tramite il monitor.
 Il System Bus permette il trasferimento di dati tra le varie componenti →
collo di bottiglia.

L’architettura dell’esecutore

Elementi principali
 Memoria Centrale: -- Memorizza dati e programmi in esecuzione.
-- Può essere organizzata in vari livelli (es: cache)
-- Capacità limitata
 --Volatile le informazioni vengono tipicamente perse quando
l'alimentazione del computer viene spenta.
-- Accesso all’informazione molto rapido
 Memoria secondaria o memoria di massa:-- Memorizza grandi quantità di
dati e programmi
--Persistente
-- Accesso molto meno rapido della memoria centrale
--Con la memoria centrale e la cache forma una gerarchia di memoria
 Unità di elaborazione (CPU):-- Elabora dati, coordina trasferimento dei
dati
-- Esegue i programmi, cioè interpreta ed esegue le loro istruzioni.
Essa è composta da :
• Control Unit: dirige le operazioni delle altre unità mandando segnali di
comando e di timing. Gestisce anche il passaggio di dati con gli altri
componenti
• ALU( Aritmetic logic Unit ) : esegue le operazioni aritmetiche e logiche
(addizione, sottrazione, moltiplicazione, divisione, AND, OR,…)
• Register unit: un insieme di spazi di memoria molto piccoli e veloci.
Possono contenere istruzioni, dati o indirizzi. La ALU accede a questi
registri direttamente.

CODIFICA
CODIFICA BINARIA (BASE 2)
Codifica posizionale usata dal calcolatore per tutte le informazioni

Alfabeto: { 0 1 } ha il vantaggio di poter utilizzare direttamente sui calcolatori

• BIT (“BInary digIT”):

• unità elementare di informazione

• Facile da implementare: dispositivi che assumono due stati

• Acceso/spento corrispondente ai due valori di tensione

Numeri binari naturali

NUMERI NATURALI IN BINARIO

CONVERSIONE IN BINARIO: METODO DEI RESTI

Si calcolano i resti delle divisioni per due (cioè la «base»):

1. Stabilire se il numero sia pari (resto 0) oppure dispari (resto 1) e annotare il

resto

2. Dividere per 2 il numero (trascurando il resto)

3. Ripartire dal punto (1) fino a ottenere 0 come risultato della divisione

4. La codice binaria si compone dal «basso» verso l’«alto»

ESEMPIO:
Aumento e riduzione dei bit in bin
• Aumento dei bit: premettendo in modo progressivo un bit 0 a sinistra, il
valore del numero non muta. Esempio:

• Riduzione dei bit : cancellando in modo progressivo un bit 0 a sinistra, il

valore del numero non muta, ma bisogna arrestarsi quando si trova un bit 1!
Esempio:
Numeri interi in modulo e segno (m&s)
il primo bit a sinistra rappresenta il segno del numero (bit di segno), i bit
rimanenti rappresentano il valore:

• 0 per il segno positivo

• 1 per il segno negativo

Il bit di segno è applicato al numero rappresentato, ma non fa propriamente

parte del numero in quanto tale ( il bit di segno non ha significato numerico).

Operazioni –numeri binari naturali

OPERAZIONI CON NUMERI BINARI MODULO & SEGNO M&S

Somma di due numeri con stesso segno: Si sommano i valori assoluti dei due
numeri (sono due numeri naturali)

• Si aggiunge al risultato il segno dei due operandi

Somma di due numeri con segno discorde

• Si effettua la sottrazione tra il valore assoluto più grande e quello più piccolo
(sono due

numeri naturali)

• Si aggiunge al risultato il segno dell’operando con valore assoluto maggiore

La sottrazione funziona in modo simile

• Si inverte il segno del secondo operando

• Si esegue la somma secondo le regole mostrate sopra

RAPPRESENTAZIONE BINARIA IN COMPLEMENTO A C2

Numeri interi relativi in complemento a 2: il C2 è un sistema binario, ma il
primo bit (quello a sinistra, il più significativo) ha peso negativo, mentre tutti gli
altri bit hanno peso positivo.

--Il bit più a sinistra è ancora chiamato bit di segno .Determina se il peso del
primo bit è positivo o negativo.—
N.B. : in base al bit di segno lo zero è considerato positivo

Interi relativi in m&s e C2

Invertire un numero in C2
L’inverso additivo (o opposto) –N di un numero N rappresentato in C2 si
ottiene:

OSSERVAZIONI SUL C2 (IN COMPLEMENTO A 2)

Il segno è incorporato nel numero rappresentato in C2, non è semplicemente
applicato (come in M&S) . Si può eseguire l’estensione del numero di bit della
codifica replicando il bit più a sinistra . La riduzione si può effettuare fino a che
non si trova una sequenza 10 o 01 poiché il primo bit rappresenterà il segno.

--Il bit più significativo rivela il segno: 0 per numero positivo, 1 per numero
negativo (il numero zero è considerato positivo), ma…

--Se il numero è negativo, NON si può distaccare il bit più significativo e dire
che i bit rimanenti rappresentano il valore assoluto del numero

Aumento e riduzione dei bit in C2

LUNGHEZZA DELLA RAPPRESENTAZIONE C2

Qual è il numero minimo di bit che serve per rappresentare in binario C2 un
dato valore espresso in notazione decimale?

Il numero minimo di bit per rappresentare un numero N cambia a seconda che

il numero sia positivo o negativo
OPERAZIONI CON NUMERI IN C2
L’addizione di numeri in complemento a 2 è identico a quello dei numeri binari
naturali (il bit di segno è elaborato come gli altri bit)

La sottrazione viene eseguita con l’operazione di somma: A – B = A + (– B) = A

+ C2(B)

OVERFLOW CON NUMERI IN C2

Se gli addendi sono tra loro discordi (di segno diverso) non si verifica mai
overflow.

Se gli addendi sono tra loro concordi, si verifica se e solo se il risultato è

discorde.

RIPORTO E OVERFLOW IN C2

Si ha overflow quando il risultato corretto dell’addizione eccede il potere di

rappresentazione dei bit a disposizione . La definizione di overflow non cambia

Nelle operazioni su numeri C2, l’overflow non ha alcuna relazione con il riporto

• Si può avere overflow senza “riporto perduto”

• Capita quando da due addendi positivi otteniamo un risultato negativo, come

nell’esempio

precedente

• Si può avere un “riporto perduto” senza overflow

• Può essere un innocuo effetto collaterale

• Capita quando due addendi discordi generano un risultato positivo (provare a
sommare +12 e -7)

Rappresentazione ottale e esadecimale

Ottale o in base otto (oct): Si usano solo le cifre 0-7

Esadecimale o in base sedici (hex): Si usano le cifre 0-9 e le lettere A-F per i
valori 10-15

NUMERI RAZIONALI
Utilizzando opportune convenzioni possiamo pensare di rappresentare non solo
interi ma anche numeri razionali

STANDARD IEEE
  Precisione quadrupla su 128 bit:
o 1 bit di segno
o 15 di esponente
o 111 di mantissa

Convertire un numero in virgola mobile con precisione

singola

Non solo numeri – codifica dei caratteri

Codice ASCII (American Standard Computer Interchange Interface): utilizza n=7
bit per 128 caratteri.

Il codice ASCII a 7 bit è pensato per la lingua inglese. Si può estendere a 8 bit
per rappresentare il doppio dei caratteri. Si aggiungono così, ad esempio, le
lettere con i vari gradi di accento necessarie in molte lingue europee, e altri
simboli speciali ancora
Spesso, quando il codice ASCII a 7 bit è usato in un calcolatore avente parole di
memoria da un Byte (o suoi multipli), l’ottavo bit del Byte memorizzante il
carattere funziona come bit di parità • Il bit di parità serve per rilevare
eventuali errori che potrebbero avere alterato la sequenza di bit, purché siano
errori di tipo abbastanza semplice

Bit di parità (parity bit)

Si aggiunge un bit extra, in modo che il numero di bit uguali a 1 sia sempre

pari:

• Se per errore un (solo) bit si inverte, il conteggio dei bit uguali a 1 dà valore
dispari! • Così si può rilevare l’esistenza di un errore da un bit (ma non
localizzarne la posizione)

• Aggiungendo più bit extra (secondo schemi opportuni) si può anche

localizzare l’errore.

• Il bit di parità non rileva gli errori da due bit; ma sono meno frequenti di quelli
da un bit

Algebra di Boole ed elementi di Logica

OPERAZIONI ELEMENTARI
Ogni algoritmo assume un insieme di operazioni elementari che possono essere
eseguite.

• Dipendono dal linguaggio e dal calcolatore che si useranno

Non è possibile aggiungere operazioni elementari, ma è possibile combinarle

per creare:

• Espressioni: catene di operazioni per eseguire un calcolo complesso

• Blocchi: sequenze di operazioni per eseguire un calcolo specifico

OPERATORI LOGICI
Gli operatori logici servono a combinare valori logici (VERO, FALSO) per
ottenere preposizioni più complesse

Si basano sull'algebra di Boole (algebra le cui variabili assumono solo valore

VERO =1 o FALSO=0 )
ESPRESSIONI LOGICHE
Precedenza: l’operatore “not” precede l’operatore “and”, che a sua volta
precede l’operatore “or”

Tautologie e Contraddizioni
• Tautologia: Una espressione logica che è sempre vera, per qualunque
combinazione di valori delle variabili

• Contraddizione : Una espressione logica che è sempre falsa, per qualunque

combinazione di valori delle variabili

Due espressioni logiche si dicono equivalenti (e si indica con ) se hanno la

medesima tabella di verità. La verifica è algoritmica

Proprietà dell’algebra di Boole

 Leggi di De
Morgan:

 Proprietà associativa: A or (B or C) = (A or B) or C (idem per AND)

 Proprietà commutativa: A or B = B or A (idem per AND)

 Proprietà distributiva di AND rispetto a OR: A and (B or C) = A and B or A

and C

 Proprietà distributiva di OR rispetto a AND: A or B and C = (A or B) and

(A or C)

 Proprietà di assorbimento (A assorbe B): A or A and B = A

 Legge dell’elemento 1: not A or A = 1

Valutazione cortocircuitata
La valutazione cortocircuitata delle espressioni è una tecnica utilizzata in
programmazione elettronica e informatica per migliorare l'efficienza
nell'elaborazione di espressioni booleane.
• Valutazione cortocircuitata dell’AND: se il primo termine risulta falso,
l’espressione risulta falsa senza che gli altri termini vengano controllati

• Valutazione cortocircuitata dell’OR: se il primo termine risulta vero,

l’espressione è vera indipendentemente dagli altri valori

Gerarchia dei dati

I dati elaborati dai computer formano una gerarchia che cresce in grandezza e
complessità, partendo dai bit fino ad arrivare ai caratteri e i campi.

Caratteri
Le persone preferiscono lavorare con cifre decimali (0–9), lettere (A–Z e a–z) e
simboli speciali come:

Le cifre, le lettere e i simboli speciali sono noti come caratteri

Campi
• Un campo è un gruppo di caratteri o byte che trasmette un significato.

 nome di una persona : campo composto da lettere maiuscole e minuscole

 età di una persona in anni : campo composto da cifre decimali

Record
Diversi campi correlati possono essere utilizzati per comporre un record.

Files
Un file è un gruppo di record correlati e contiene dati arbitrari in formati
arbitrari.

 Alcuni sistemi operativi considerano un file semplicemente come una

sequenza di byte.

Databases
Un database è una raccolta di dati organizzata per un facile accesso e
manipolazione. Il modello più popolare è il database relazionale, in cui i dati
sono memorizzati in tabelle ( include record e campi )semplici.

Linguaggi di programmazione
I programmatori scrivono istruzioni in vari linguaggi di programmazione, alcuni
direttamente comprensibili dai computer e altri che richiedono passaggi
intermedi di traduzione. Oggi sono in uso centinaia di tali linguaggi, che
possono essere suddivisi in tre tipi generali:

• Linguaggio macchina: Ogni computer può comprendere direttamente il

proprio linguaggio macchina, definito dal suo design hardware. Esso
generalmente consiste di una stringa di numeri (0 e 1) che istruiscono il
computer su come eseguire le operazioni elementari una alla volta. I linguaggi
macchina sono machine-dependent – ognuno può essere utilizzato su un solo
tipo di macchina.

• Linguaggio assembly: usa abbreviazioni simili all'inglese per rappresentare

operazioni elementari. // • Furono sviluppati programmi traduttori chiamati
assembler per convertire i programmi in linguaggio assembly in linguaggio
macchina alla velocità del computer. //

• Linguaggio di alto livello: singole istruzioni possono realizzare compiti

sostanziali.
Un tipico programma in linguaggio di alto livello contiene molte istruzioni,
conosciute come codice sorgente del programma. I programmi traduttori
chiamati compilatori convertono il codice sorgente in linguaggio di alto livello in
linguaggio macchina

Interpreter
Gli interpreter eseguono i programmi in linguaggio di alto livello direttamente.
Evitano i ritardi della compilazione, ma il codice viene eseguito più lentamente
rispetto ai programmi compilati.

Sistemi operativi
I sistemi operativi sono software che rendono l'uso dei computer più comodo
per utenti, sviluppatori di software e amministratori di sistema. Forniscono
servizi che permettono alle applicazioni di eseguire in modo sicuro, efficiente e
simultaneo.

• Il software che contiene i componenti principali del sistema operativo è

chiamato kernel

• Linux, Windows e macOS sono sistemi operativi desktop popolari

Ognuno di essi è parzialmente scritto in C

Il linguaggio C
Pensato per sistemi operativi e compilatori, inventato nel 1972 nei Bell
Laboratories da Dennis Ritchie. E’ Hardware-independent, ovvero i programmi
scritti in C possono essere lanciate sulla maggior parte dei computer con poche
modifiche.

• Per ottimizzare performance:

• Sistemi operativi

• Sistemi embedded

• Sistemi di comunicazione

Sviluppo di un programma C
I sistemi C generalmente consistono di diverse parti:

• Un ambiente di sviluppo del programma

• Il linguaggio

• La libreria standard del C

I programmi C tipicamente passano attraverso sei fasi per essere eseguiti:

1. Modifica (Edit): Scrittura del codice sorgente

2. Preprocesso (Preprocess): Elaborazione del codice sorgente per includere file

e gestire macro

3. Compilazione (Compile): Traduzione del codice sorgente in codice oggetto

4. Collegamento (Link): Unione del codice oggetto con le librerie per creare
l'eseguibile

5. Caricamento (Load): Trasferimento dell'eseguibile in memoria

6. Esecuzione (Execute): Esecuzione del programma

LINGUAGGIO C
Identificatori
Gli identificatori assegnano i nomi alle entita' (variabili e funzioni). All'interno di
un programma un'entita' deve avere un identificatore univoco.

Regole e caratteristiche degli identificatori:

♦ case sensitive: distinzione maiuscolo/minuscolo;

♦ sintassi: deve iniziare o con una lettera o con l'underscore ('_') e puo'
proseguire con lettere, underscore o cifre.

Non puo' essere una parola chiave del C.

Le proprietà di una entità (variabile o funzione) vengono descritte durante la

sua definizione o dichiarazione. Con la dichiarazione, l'entità viene associata
all'identificatore (nome della variabile o della funzione) e ne viene dichiarata la
tipologia, ma non viene né riservata la memoria per le variabili, né specificato il
codice per le funzioni.
Con la definizione, oltre ad associare l'identificatore alla entità e definirne la
tipologia (es: variabile di tipo float), viene riservata memoria per le variabili, o
specificato il codice per le funzioni.

Variabili
Una variabile può essere descritta come un contenitore, il cui contenuto è
sempre a disposizione e rappresenta il valore della variabile stessa.

Ad ogni variabile e' associato:

• un nome (identificatore);

• un tipo (insieme dei valori che puo' assumere);

• un'area di memoria (per contenere il valore assunto);

• un indirizzo (riferimento all'area di memoria);

• un valore (in istanti diversi la variabile può assumere valori differenti, purché
coerenti con il tipo).

ATTENZIONE !! : DUE VARIABILI NON POSSONO AVERE LO STESSO NOME.

Si definisce una variabile con la sintassi: tipo identificatore1 [= inizializzazione1

]

Tipi di dato fondamentali

Per tipo di dato si intende un insieme di valori e un insieme di operazioni che
possono essere applicati. Ogni tipo di dato ha una propria rappresentazione in
memoria (codifica binaria) che utilizza un certo numero di celle di memoria.
Tuttavia l’uso nei programmi dei tipi di dato consente di trattare le informazioni
in maniera astratta, cioè prescindendo dalla loro rappresentazione nella
macchina. L’uso di variabili con tipo ha importanti conseguenze:

• per ogni variabile è possibile determinare a priori l’insieme dei valori

ammissibili e l’insieme delle operazioni applicabili;

• per ogni variabile è possibile determinare a priori la quantità di memoria

necessaria;

• è possibile rilevare a priori (a tempo di compilazione) errori nell’uso delle

variabili all’interno di operazioni non lecite per il tipo corrispondente.

I tipi di dato si dividono in:

• tipi semplici ( char , int , float , double)

• tipi strutturati ( vettori, matrici , archivi , rubriche )

Rappresentazione numerica
I tipi di dato predefiniti del C, adatti a rappresentare numeri, si differenziano tra
tipi per numeri interi oppure con virgola e per il numero di bit che sono
utilizzati nella loro rappresentazione nell’elaboratore.

INTERI CON SEGNO (INT) -- esistono 3 tipi di interi con segno:

• short (dichiarabile nei seguenti modi short int, signed short, signed short int);

• int (dichiarabile nei seguenti modi signed int, signed);

• long (dichiarabile nei seguenti modi long int, signed long, signed long int).

Analizzando la loro occupazione in memoria (direttamente legata al numero di

bit con il quale il dato è memorizzato e quindi all’intervallo di
rappresentazione), valgono le seguenti relazioni:

• sizeof(short) <= sizeof(int) <= sizeof(long);

• sizeof(short) >= 2 (ovvero, almeno 16 bit);

• sizeof(long) >= 4 (ovvero, almeno 32 bit).

--L’operatore sizeof() in C ritorna il numero di byte occupati da una variabile o

da un tipo di dato che gli viene passato come operando.

-- I valori limite sono contenuti nel file limits.h, che definisce le costanti:
SHRT_MIN, SHRT_MAX, INT_MIN, INT_MAX, LONG_MIN, LONG_MAX .
Queste costanti possono ad esempio servire in un programma per controllare
se il dato immesso da un utente cade nell’intervallo di rappresentazione. Se
non lo fosse, possiamo segnalarlo all’utente al posto che far continuare
l’esecuzione e generare quindi un probabile errore di overflow/underflow.

OPERATORI
Gli operatori utilizzabili sono:

Operatori aritmetici

+ Operatore aritmetico di somma.

Effettua l'operazione di somma fra 2 espressioni.

- Operatore aritmetico di sottrazione.

Effettua l'operazione di differenza fra 2 espressioni.

* Operatore aritmetico di moltiplicazione.

Effettua l'operazione di moltiplicazione fra 2 espressioni.

/ Operatore aritmetico di divisione.

Effettua l'operazione di divisione fra 2 espressioni.
%
Operatore aritmetico di modulo.
Calcola il resto della divisone fra la 1° ed la 2° espressione.
Funziona con espressioni che tornino valori interi (char, int, long).

-
Operatore unario di cambio segno.
-espressione
Cambia il segno all'intera espressione.

+
Operatore unario +
+espressione
Equivale a espressione.

Operatore di incremento.
++ Puo' essere impiegato sia in forma postfissa (es: variabile++) che
in forma prefissa (es: ++variabile).
In entrambi i casi le due forme sono equivalenti a:

variabile = variabile + 1;

Nella forma postfissa l'incremento viene

effettuato dopo dell'utilizzo della variabile.
Nella forma prefissa l'incremento viene
effettuato prima dell'utilizzo della variabile.

--
Operatore di decremento.
Valgono le stesse considerazioni effettuate per l'operatore di
incremento ++, tranne il fatto che le forme variabile-- e --
variabile equivalgono a:

variabile = variabile - 1;

Operatori relazionali
Operatore relazionale di uguaglianza.
== Ritorna 1 (vero) se le 2 espressioni ritornano valori uguali.
Ritorna 0 (falso) in caso contrario.
Operatore relazionale di disuguaglianza.
!= Ritorna 1 (vero) se le 2 espressioni ritornano valori
differenti.
Ritorna 0 (falso) in caso contrario.
Operatore relazionale di minoranza.

< Ritorna 1 (vero) se il valore ritornato dalla 1° espressione e'

minore del valore ritornato dalla 2° espressione.
Ritorna 0 (falso) in caso contrario.
Operatore relazionale di minoranza o uguaglianza.

<= Ritorna 1 (vero) se il valore ritornato dalla 1° espressione e'

minore o uguale (cioe' non maggiore) al valore ritornato
dalla 2° espressione.
Ritorna 0 (falso) in caso contrario.
Operatore relazionale di maggioranza.

> Ritorna 1 (vero) se il valore ritornato dalla 1° espressione e'

maggiore del valore ritornato dalla 2° espressione.
Ritorna 0 (falso) in caso contrario.
Operatore relazionale di maggioranza o uguaglianza.

>= Ritorna 1 (vero) se il valore ritornato dalla 1° espressione e'

maggiore o uguale (cioe' non minore) al valore ritornato
dalla 2° espressione.
Ritorna 0 (falso) in caso contrario.
 Operatori logici
Operatore logico di negazione. (unario)
! !espressione ritorna 0 se espressione ritorna un valore
diverso da 0; ritorna 1 se espressione ritorna il valore uguale
a 0.
Operatore logico and.

&& Esegue l'and logico fra 2 espressioni.

Valuta la prima espressione e se questa e' falsa,
ritorna 0 senza valutare la seconda; altrimenti valuta la
seconda espressione. Se quest'ultima e' falsa
ritorna 0 altrimenti ritorna 1.
Operatore logico or.
|| Esegue l'or logico fra 2 espressioni.
Valuta la prima espressione e se questa e' vera,
ritorna 1 senza valutare la seconda; altrimenti valuta la
seconda espressione. Se quest'ultima e' vera
ritorna 1 altrimenti ritorna 0.
Operatori bit a bit
~ Operatore complemento ad 1 (unario).
~espressione ritorna il complemento ad 1 del
valore tornato da espressione.
Il complemento ad 1 consiste nel cambio di
ciascun bit con il suo complemento, ovvero ogni
bit posto ad 1 viene cambiato a 0 ed ogni bit posto
a 0 viene cambiato ad 1.
& Operatore and bit a bit.
Ritorna il valore dell'and effettuato bit a bit sui
valori ritornati dalle 2 espressioni.
Esempio:
int a=10; /*
rappresentazione binaria (8 bit):
00001010 */
int b=12; /*
rappresentazione binaria (8 bit):
00001100 */
int c;

c = a&b; /* 00001010 a
* 00001100 b
* --------
* 00001000 c
= a&b */

N.B. - Per semplicita' di trattazione, sono stati

considerati gli interi come costituiti da 8 bit,
anziche' 16 o 32 bit come avviene in realta' sugli
elaboratori.
| Operatore or (inclusivo) bit a bit.
Ritorna il valore dell'or effettuato bit a bit sui
valori ritornati dalle 2 espressioni.
^ Operatore or esclusivo (ex-or) bit a bit.
Ritorna il valore dell'ex-or effettuato bit a bit sui
valori ritornati dalle 2 espressioni.
 << Operatore shift a sinistra.
espr_1 << espr_2
Ritorna il valore della traslazione a sinistra
di espr_2 bit sui bit del valore ritornato da espr_1.
I nuovi bit che entrano a destra sono posti a 0.
>> Operatore shift a destra.
espr_1 >> espr_2
Ritorna il valore della traslazione a destra
di espr_2 bit sui bit del valore ritornato da espr_1.
I nuovi bit che entrano a sinistra possono
dipendere dall'architettura dell'elaboratore e/o dalla
implementazione del compilatore. Non e' garantito
che siano sempre posti a 0 anche per valori
negativi di espr_1; per evitare cio' e' bene
assicurarsi che il valore ritornato da espr_1 sia di
tipo unsigned

assegnazione bit a bit

-- Per quanto riguarda le funzioni di ingresso/uscita si usano le funzioni printf e

scanf, con i seguenti indicatori di formato (dove d indica “decimale”):

• %hd per short

• %d per int

• %ld per long (con l minuscola)

INTERI SENZA SEGNO (unsigned)

In C esistono 3 tipi di interi senza segno:

• unsigned short (oppure: unsigned short int);

• unsigned int;

• unsigned long (dichiarabile nei seguenti modi long int, unsigned long,
unsigned long int).

Ingresso/uscita: tramite printf e scanf, con i seguenti specificatori di formato:

• %u per numeri in decimale; • %o per numeri in ottale;

• %x per numeri in esadecimale con cifre 0, . . . , 9, a, . . . , f;

• %X per numeri in esadecimale con cifre 0, . . . , 9, A, . . . , F.

!! : Per interi short si antepone h e per interi long si antepone l (minuscola).

TIPI REALI o FLOATING POIN (float)

In C i tipi reali vengono rappresentati mediante virgola e ne esistono 3 tipi:

• float (dimensione in memoria 4 byte);

• double (dimensione in memoria 8 byte);

• long double (dimensione in memoria 12 byte).

In particolare questa notazione si chiama in virgola mobile. Le grandezze e gli

intervalli di questi tipi di dato sono scritte nel file float.h di libreria e dipendono
dal compilatore. Se si vuole dichiarare una costante si scriveranno gli interi
semplicemente in decimale USANDO SEMPRE IL PUNTO

Per quanto riguarda l’output di variabili float mediante printf:

• se si usa %f si stampa il numero in virgola fissa;

• se si usa %8.3f si stampano 8 cifre complessive, di cui 3 cifre decimali;

• se si usa %e si stampa in forma esponenziale.

Si può stampare anche in forma ottimizzata usando %g (oppure %G) che

sceglie la forma più compatta fra la notazione esponenziale (%e) e quella di %f.
Per quanto riguarda l’input con scanf nel caso dei float si può usare
tranquillamente %f.

Rappresentazione dei caratteri

I caratteri alfanumerici del codice ASCII (American Standard Code For
Information Interchange) compongono praticamente tutti i nostri file di testo e
moltissimi altri file. Questi caratteri vengono rappresentati in C mediante la
dichiarazione di variabili di tipo char.
In C esistono 3 tipi di caratteri:

• char;

• signed char (rappresentato in complemento a 2);

• unsigned char.

I tipi signed ed unsigned char sono esattamente rappresentati come interi.

Tipicamente vale sizeof(char) = sizeof(int) ove sizeof(char) vale 8 bit. Tutti gli
operatori definiti su int (+, -, *, /, %, ==, !=, <, >, <=, >=) valgono sui
caratteri.

Le operazioni di input e output dei caratteri si realizzano sempre con scanf e

printf usando nella stringa di controllo %c .

Costanti
Costanti intere:

• decimali: la prima cifra deve essere significativa.

• ottali: 0oooo Prefisso 0 (zero). o= cifra ottale ([0..7]).

• esadecimali: 0xhhhh Prefisso 0x o 0X.

- suffisso:

• U o u: indica interi di tipo unsigned. (Es.: 50000U, 0xf000U)

• L o l: indica interi di tipo long. (Es.: 34L, 50000000L)

• UL o ul: indica interi di tipo unsigned long. (Es.: 34UL)

Costanti reali:

• per default sono di tipo double.

• il suffisso F o f indica numeri reali di tipo float .

• L o l indica numeri reali di tipo long double.

Costanti carattere:

Le costanti carattere sono indicate fra apici.

Ad esempio: ‘a’, ‘F’.

Vi sono alcune costanti carattere speciali (utilizzabili soprattutto nelle printf):

'\a' segnale di “alert” <BELL> (beep)

'\b' spazio indietro <BS> (backspace)

'\f' salto pagina <FF> (form feed)

'\n' a capo <LF> new line (line feed)

'\r' ritorno a inizio riga <CR> (carriage return)

'\t' tabulazione orizzontale <TAB>

'\v' tabulazione verticale <VT> (vertical tab)

'\?' ? (punto interrogativo)

'\\' \ (back slash)

'\'' ' (apice singolo)

'\"' " (apice doppio)

'\0' <NUL> (carattere NULL)

Strutture di controllo
Le istruzioni di controllo del flusso specificano l’ordine secondo il quale i calcoli
devono essere effettuati. La maggior parte delle istruzioni sono istruzioni-
espressione, sono cioe' delle espressioni seguite dal ; (punto e virgola). La
sintassi è la seguente:

espressione;

--Il ; (punto e virgola) e' il terminatore di istruzione.

Il valore dell'espressione viene trascurato, mentre di fondamentale importanza

sono gli effetti collaterali che modificano i valori delle variabili o aree di
memoria. Gli effetti collaterali sono valutati completamente prima che venga
eseguita la successiva istruzione.

Esempio: ;

Questo è il caso dell'istruzione nulla ed il suo impiego e' tipico laddove la

sintassi richieda una istruzione, ma il programma non debba eseguire alcuna
azione.

Blocchi
In C i blocchi sono realizzati mediante l'uso delle parentesi graffe dentro le
quali vi è una sequenza di istruzioni. E' possibile dichiarare delle variabili locali
all'interno di un blocco di istruzioni C. I blocchi possono essere innestati uno
dentro l’altro a piacere: le dichiarazioni delle variabili locali seguono
immediatamente la parentesi sinistra e

precedono la parte eseguibile del blocco. { dichiarazioni

istruzioni }

L'impiego dei blocchi è finalizzato alla:

• scrittura di un insieme di istruzioni (nei casi in cui la sintassi permetta
l'inserimento di solamente una istruzione);

• definizione del corpo di una funzione.

Istruzioni di selezione
Il C mette a disposizione due istruzioni di selezione:

• il costrutto IF

• il costrutto SWITCH

Costrutto IF
E’ composto da una espressione e uno/due/tre/enne blocchi di codice (chiamati
i "rami" dell'if). Le due forme tipiche in cui si può presentare la sintassi relativa
al costrutto IF sono le seguenti:

 1° caso:

if (espressione)
istruzione_1
 2° caso:

if (espressione)
istruzione_1
else
istruzione_2
istruzione_1 viene eseguita se espressione, una volta valutata assieme a tutti i
suoi effetti collaterali, torna un valore vero (cioè non zero); altrimenti se
espressione torna un valore falso (cioe' uguale a zero) viene eseguita
istruzione_2, se esistente.

Nel caso di IF innestate, la parte else viene abbinata sempre all'ultima if posta
nello stesso blocco della else, ma non gia' abbinata ad una precedente else.
Per evitare possibili ambiguita' nelle IF innestate, e' possibile l'utilizzo di blocchi
per racchiudere i costrutti piu' interni.

Costrutto SWITCH
Il costrutto SWITCH è solitamente impiegato quando si devono controllare molti
casi. In questo modo il codice risulta essere più ordinato. Il costrutto è
composto da etichette (CASE) e da un caso generale (DEFAULT). Le etichette
del case devono essere delle costanti. La forma tipica della sintassi relativa al
costrutto SWITCH è la seguente :
switch (espressione)

{
case espr_costante_1:
[istruzioni]
...
case espr_costante_2:
[istruzioni]
...
default:
[istruzioni]
...
}
N.B. – L’etichetta default e le istruzioni ad essa relativa, sono opzionali, così
pure è opzionale la lista di istruzioni che seguono ogni etichetta (label) del
case. L'espressione viene valutata assieme ai suoi effetti collaterali ed il valore
ritornato da essa, che deve essere di tipo intero (char, int, long) viene
confrontato con le espressioni costanti associate alle case. In caso di
corrispondenza il controllo viene passato alle istruzioni ad essa associate, e
continua fino al termine dell'istruzione SWITCH (quindi fino al raggiungimento
della parentesi } di chiusura dell'istruzione). Se il valore dell'espressione non
corrisponde a nessuna delle espressioni costanti, allora il controllo viene
trasferito alla prima istruzione associata alla label default, e prosegue fino al
raggiungimento del termine dell'istruzione SWITCH. Se nemmeno la label
default è specificata, la SWITCH termina immediatamente.

E' permesso l'innestamento dei costrutti SWITCH.

Tra gli statement che compongono il corpo dello SWITCH e' permesso l'utilizzo
dell'istruzione di salto BREAK. Quando tale istruzione viene incontrata, essa
causa il termine dell'esecuzione dell'istruzione SWITCH ed il controllo passa
all'istruzione successiva.
Esempio:

// conteggio dei tipi di caratteri

char c;
int n_cifre, n_separatori, n_altri;
...
c = ....; // sia c il carattere da esaminare
switch (c)
{
case '0':
n_cifre = n_cifre + 1;
break;
case '1':
n_cifre = n_cifre + 1;
break;
.....
case '9':
n_cifre = n_cifre + 1;
break;
case ' ':
n_separatori = n_separatori + 1;
break;
case '\n':
n_separatori = n_separatori + 1;
break;
case '\t':
n_separatori = n_separatori + 1;
break;
default:
n_altri = n_altri + 1;
}

Istruzioni di Iterazione
Il C mette a disposizione tre istruzioni di iterazione:
• il costrutto WHILE
• il costrutto DO-WHILE
• il costrutto FOR

Costrutto WHILE
E’ il costrutto più generale, da cui si possono ottenere tutti gli altri costrutti per
l’iterazione. La sua struttura è la seguente:

while (espressione)
istruzione
oppure:
while (espressione)
{
istruzione1
istruzione2
....
istruzionen
}
L'espressione viene valutata e, se ha valore diverso da 0 (vero), viene eseguita
l'istruzione successiva (che può anche essere un intero blocco di istruzioni,
opportunamente delimitato dalle parentesi graffe). Una volta che quest'ultima
è terminata, l'espressione viene valutata nuovamente e, se è nuovamente
vera, si ripete l'istruzione. Ciò si replica fino a quando l'espressione ha valore 0
(falso), e in questo caso il controllo si trasferisce all'istruzione successiva, al
while. Un ciclo while può essere eseguito zero o più volte, poiché l'espressione
potrebbe essere falsa già la prima volta. Si tratta di un ciclo a condizione
iniziale: prima di eseguire il ciclo si valuta la condizione. Il problema principale
delle strutture iterative è che possono entrare in ciclo infinito. Questo accade
se per un errore di programmazione o per qualche condizione esterna alla
espressione del while rimane sempre vera.

All'interno del blocco di istruzioni puo' comparire l'istruzione BREAK che, se

eseguita, provoca il termine del WHILE nonché l'istruzione CONTINUE che, una
volta invocata, forza l’inizio dell’iterazione successiva del ciclo, provoca cioè
l’esecuzione immediata della parte di controllo del ciclo. In caso di cicli
innestati, entrambe le istruzioni BREAK e CONTINUE non hanno influenza sui
cicli piu' esterni.

Costrutto DO-WHILE
Il costrutto DO-WHILE presenta la seguente sintassi:

do
istruzione
while (espressione);

Per ogni ciclo viene eseguita l’istruzione, poi viene valutata l'espressione. Se
risulta vera (diversa da zero) il ciclo viene riavviato, altrimenti l'istruzione DO-
WHILE ha termine. L’istruzione viene eseguita almeno una volta: infatti il
costrutto do-while è un ciclo a condizione finale: prima di valutare la condizione
si esegue il ciclo. Quindi il corpo del ciclo viene eseguito sempre almeno una
volta Al posto dell’istruzione può esserci un blocco.

All’interno di un blocco di istruzioni può comparire l'istruzione BREAK che, se

eseguita, provoca il termine del DO-WHILE nonche' l'istruzione CONTINUE che,
una volta invocata, forza l’inizio dell’iterazione successiva del ciclo, provoca
cioè l’esecuzione immediata della parte di controllo del ciclo. In caso di cicli
innestati, entrambe le istruzioni BREAK e CONTINUE non hanno influenza sui
cicli piu' esterni.

Costrutto FOR
Il costrutto FOR è equivalente al costrutto WHILE, ma l’uso è consigliato solo
nel caso in cui il numero di iterazioni SIA NOTO A PRIORI.

Per esempio, se si deve scandire una struttura dati che ha sempre N elementi,
allora si userà un ciclo FOR. Nel caso in cui si debba continuare a chiedere
all’utente di digitare un numero finché non viene immesso un numero pari a
zero, allora si userà un costrutto WHILE in quanto il numero di iterazioni non è
noto a priori.

Il costrutto FOR è composto nel seguente modo:

for ( expr1 ; expr2 ; expr3 )

istruzione
Se si vuole iterare un blocco di codice, il costrutto FOR è composto nel
seguente modo:

for ( expr1 ; expr2 ; expr3 )

{
istruzione1
istruzione2
...
istruzionen
}
in cui:

• expr1 è l’espressione iniziale,

• expr2 è l’espressione booleana (del ciclo),

• expr3 è l’espressione incremento.

L'espressione iniziale permette di inizializzare le variabili di ciclo e viene
eseguita una volta sola, prima di qualsiasi altra operazione.

ISTRUZIONI DI INPUT/OUTPUT:
Output: printf
Obiettivo: dichiarare una variabile i intera, assegnarvi un valore e stamparla a
video.

Un semplice programma che esegue queste azioni è il seguente:

#include <stdio.h>
int main()
{
int i;
i = 3;
printf("%d", i);
}
Nella parte dichiarativa si dichiara la variabile i come variabile intera (int). Nella
prima riga della parte esecutiva si assegna il valore 3 alla variabile i. La terza
riga del main chiama la funzione printf che permette di stampare la variabile i
passata (alla destra della virgola) a terminale. Alla sinistra della virgola è
presente una stringa chiamata stringa di controllo. Essa ha il compito di
definire in che modo il contenuto della variabile i debba essere stampato. Ad
esempio “%d” significa che i verrà stampata come un intero: a monitor
comparirà il numero 3. Se invce si scrive:

printf("Il valore contenuto e’: %d", i)

compare a monitor: Il valore contenuto e’: 3

Questo accade poiché la funzione printf stampa la stringa di controllo e
sostituisce alle parti della stringa che iniziano con % (in questo caso %d) i
valori delle variabili passati alla destra della virgola (il valore di i).

Input: scanf
Obiettivo: dichiarare una variabile i intera, leggere un valore dalla tastiera e
copiarlo in una variabile. Un semplice programma che esegue queste azioni è il
seguente:

#include <stdio.h>
int main()
{
int i;
printf("immetti un numero intero :");
scanf("%d", &i);
printf("il valore memorizzato e’ %d", i); /* lo stampiamo per controllo */
}
Nella parte dichiarativa si dichiara la variabile i come intera (int). Nella prima
riga della parte esecutiva si stampa un messaggio per l’utente affinché capisca
che gli stiamo chiedendo di battere un numero intero sulla tastiera.
L’immissione si conclude automaticamente con la pressione del tasto enter
(invio). La terza riga del main chiama la funzione scanf che permette di copiare
il numero letto da tastiera nella variabile i.

Alla sinistra della virgola è scritto come deve essere letto il dato immesso dalla
tastiera. In questo caso l’indicazione “%d” indica che deve essere letto come
un numero intero. Questa considerazione non è banale. Infatti se l’utente
digitasse 1024 sulla tastiera seguito dalla pressione dell’enter, il sistema
potrebbe interpretare questo dato sia come il numero intero 1024 ma anche
come la stringa composta dai caratteri ‘1’, ‘0’, ‘2’ e ‘4’. Indicando %d, si toglie
ogni possibilità sull’interpretazione di come il dato debba essere letto ossia
come un numero intero.

Alla destra della virgola è presente l’indirizzo dove il valore letto deve essere
memorizzato (&i significa “all’indirizzo di i”).

Attenzione, non è corretto scrivere scanf("%d", i); senza &.

L’ultima riga del main stampa il valore immesso. In questo modo è possibile
effettuare una verifica secondo le modalità già descritte a proposito della
funzione printf.

LIBRERIE
- #include <stdio.h> // libreria standard

- getchar() //leggere un singolo carattere sul monitor

- putchar() //visualizzare un solo carattere sul monitor- sono tipo una scanf e
una printf per singoli caratteri.

- #include <stdlib.h> // libreria per avere numeri casuali (e anche altre cose ->
vedi memoria dinamica)

- int exit(int); //funzione chiamata dal sistema operativo per chiudere un

processo (chiude il main, fa finire il programma), ritorno l’intero che io ci metto
dentro.

- #include <time.h > // 1. invocare la funzione srand(time(0)); per inizializzare

il generatore di numeri casuali 2. utilizzare la funzione rand(); per
generare un numero casuale.

- #include <string.h> //operazioni con le stringhe *vedi parte sulle stringhe

- #include <math.h> //contiene funzioni matematiche

ARRAY
vettori di elementi indicizzati, omogenei, memorizzati in celle di memora
consecutive.

int array[N];

La lunghezza dell’array deve essere per forza dichiarata. Questo array avrà
lunghezza N. l’ultimo elemento si trova nella cella N-1. (l’array riempie dalla
cella 0 alla cella N-1)

Operazione sugli array: - Non è possibile operare sull’intero array, si opera un

elemento per volta.

Un array può essere considerato come un puntatore !!! (come un puntatore che
punta alla prima cella dell’array (la cella 0)). Il nome di un array è una costante
di tipo puntatore.

Come ordinare un array: diversi modi

a. Bubble sort: confronto uno a uno gli elementi uno di fianco all’altro e
posiziono prima quello minore. Ripete l’operazione quanti sono gli
elementi del vettore.
Es: void bubblesort(int v[], int n) {
int i,k;
int temp;
for(i = 0; i<n-1; i++) {
for(k = 0; k<n-1-i; k++) {
if(v[k] > v[k+1]) {
temp = v[k];
v[k] = v[k+1];
v[k+1] = temp;
 }
}
}
}

b. Selection Sort: trovo il minimo dei valori e lo metto nella prima

posizione, poi trovo il minimo tra gli altri valori e lo mettonella seconda
posizione ecc…
Es:

STRINGA
STRINGA ≠ ARRAY

Una stringa è un vettore di caratteri il cui ultimo elemento è un carattere

terminatore (o di fine stringa), codificato dal carattere di codice e
rappresentato in C dal carattere '\0'. Quando scrivo una stringa mi conta anche
il carattere terminatore: NON DIMENTICARTELO!!

 strlen(s) = (conta anche dallo zero a N-1, sono i caratteri effettivamente

scritti, senza il carattere terminatore)

Funzioni di #include <string.h> :

int strcmp(s1, s2); //confronta se due stringhe sono uguali. Restituisce 0 se

sono uguali, un altro numero se non sono uguali.

o Restituisce un numero > di 0 se il primo carattere diverso della stringa s1

viene dopo il carattere della stringa s2.

o Restituisce un numero <0 se il primo carattere diverso della stringa s1

viene prima del primo carattere diverso della stringa s2.

- strlen( str ); //misurare la lunghezza di una stringa (senza contare il

carattere terminatore- conta i caratteri effettivamente scritti)

- char *strcpy(char *str1, char *str2); // copia la stringa2 nella stringa1.

Ritorna un puntatore alla str1 (stringa di destinazione).

- sprintf() // mi stampa una scritta non a schermo ma in una variabile (è tipo

una printf ma dentro la variabile)

- char * strtok(*punt, “caratteri_separatori” ) ; //estrapola ogni singola parola

e la salva come token (oggettino che poi gli servirà). Nel momento in cui
incontra uno dei caratteri separatori lo scarta. Aggiunge un ‘\0’ alla fine del
token estrapolato e restituisce un puntatore che punta al primo carattere
della stringa.
 o Metto in ingresso *punt che è la stringa da campionare (stringa dalla quale
voglio estrarre le parole). Sostanzialmente posso inserire una stringa s[]
come primo parametro perché le stringhe si comportano come puntatori!!!!

o Il punto in cui è stato trovato l’ultimo token è mantenuto internamente

dalla funzione da utilizzare alla prossima chiamata Caratteri separatori:

o se voglio ‘\’ devo scrivere ‘\\’

o se voglio “ devo scrivere ‘ \” ‘

o \n, \t ecc

Dopo aver usato la strtok devo riusarla mettendo come primo parametro un
puntatore a NULL, se no entro in un loop (mi legge sempre la prima parola
della stringa che sto analizzando).

-char *strtok(NULL, “caratteri_separatori”); //in questo modo posso passare

alla parola successiva (è così per definizione).

//per leggere la prima parola uso strtok(parametro, caratteri_sep); , invece per

salvare tutte le altre parole devo usare la strtok(NULL, caratteri_sep); . è così
per definizione, non ci puoi fare nulla.

- strcat(s1,s2); //appende due stringhe

es: char s1 {‘c’,’i’};

char s2={‘a’,’o’};
strcat(s1,s1)={‘c’,’i,’a’,’o’};

MATRICI
schieramento rettangolare di oggetti (di solito numeri) organizzati in righe e
colonne Matrice[righe][colonne]; (Matrice righeXcolonne )
OPERAZIONI:
- Somma: due matrici si possono sommare se hanno le stesse dimensioni
- Moltiplicazione Per uno scalare: 2xMAT[i,j]-> moltiplico ogni elemento per 2
- Moltiplicazione Tra due matrici: avviene solo se il numero di righe m di B
coincide con il numero di colonne n di A. => il risultato sarà una matrice di m
righe e n colonne.

Matrice quadrata: M[N][N]. stesso numero di righe e colonne.

o Traccia: somma di elementi della diagonale
o Operazione di trasposizione: A-> At (si ribalta la matrice intorno alla sua
diagonale ) . Ai,j -> Aj,i
- Matrice simmetrica- Ai,j=Aj,i
TIPI
typedef ≠ struct
TYPEDEF: Un nuovo tipo può essere definito semplicemente dando un nuovo
nome ad un tipo già esistente. Poi posso usare il nuovo tipo come se fosse un
tipo già esistente (lo uso tipo come uso int)
Typedef int pippo; -> sto creando un nuovo tipo di dato che chiamo pippo di
tipo intero
int a, pippo a;

tipi enumerativi: tipo costituito elencando al suo interno tutti i suoi valori
( scritti tra le {}).

ES: Typedef enum {lun, mar, mer, gio, ven, sab,dom} Giornodellasettimana;

- Il compilatore assegna ad ogni dato un numero (lun=0, mar=1, mer=2…).

Tale valore viene considerato per la valutazione di espressioni, relazioni e
assegnamenti. (<>=!=+- */…)

- Possiamo costruire il tipo boolean Typedef enum {false, true } boolean;

//False= 0, true = 1

STRUCT
(chiamate anche record) Corrisponde a collezioni di variabili eterogenee.
Aggregati di dati, ogni dato è chiamato campo.
Es:
typedef struct {
char titolo[30];
int anno[4];
char regista[30];
}t_film //nome della struct

- Dimensione di una variabile/di un tipo: printf(“ la dimensione della variabile è

%d, sizeof(variabile)”) -> quando lo stampo potrebbe essere ≠ da quello che
ho calcolato In generale potrebbe essere un numero maggiore della
dimensione che ho calcolato. La memoria lascia degli “spazi”, detti pudding, tra
una variabile e l’altra.

Per calcolare manualmente la dimensione di una variabile di tipo struct posso

sommare le
dimensioni di ogni campo.
- Per accedere alla variabile titolo (es) si fa film.titolo
- Se ho due variabili di tipo struct identiche (con gli stessi campi), se scrivo
struct2=struct1
tutti i valori della struct1 vengono copiati nella struct2. Se invece hanno
strutture ≠
l’assegnamento non ha senso.
Sintassi per accedere ad un puntatore tramite una struct:
- (*ptr).campo;
- ptr->campo;
come riempire le variabili di una struct dal
programma:

PUNTATORI
- & : operatore di referenziazione, ci permette di accedere all’indirizzo di una
variabile
- Puntatori: variabili il cui valore è l’indirizzo di un’altra variabile.

ES:
Int x=3;
int *punt;
Punt = &x; //al valore di punt corrisponde l’indirizzo di x

- Referenziazione: data una variabile a, con &a si ottiene l’indirizzo di a. Int

*punt = &a;

- Dereferenziazione: estrae il valore contenuto nella cella puntata.

* -operatore di derefenziazione
int x=3;
int *p;
p=&x;

printf(“il valore di x è %d”, *p); //stampa 3, dereferenziazione.

*P indica la cella di memoria il cui indirizzo è contenuto in P

DOPPIO PUNTATORE

int **c; //la variabile c punta ad una variabile che a sua volta punta ad una
variabile di tipo int.

Attenzione al tipo- un puntatore che punta ad una variabile a di tipo1 non può
puntare anche ad una variabile b di un altro tipo.
 NULL- costante simbolica rappresenta un valore speciale che può essere
assegnata ad un puntatore. Significa che il puntatore non punta a niente. Il
valore iniziale di un puntatore dovrebbe essere NULL. ( Si ha la costante NULL -
#include <stdlib.h> )

Standard ANSI impone che NULL rappresenti il valore 0.

o Test di nullità: if (p==NULL), oppure if(!p)
o Test di non nullità: if(p!=NULL), oppure if(p)
o È errore dereferenziare un puntatore a NULL

FUNZIONI

tipo_funzione nome_funzione (tipo_variabile variabile, tipo_variabile variabile);

//dichiarazione

es: int somma_interi (int addendo1, int addendo2);

- Dichiaro la funzione prima del main (dichiarazione)

- Specifico i passaggi della funzione dopo il main (definizione). La funzione

restituisce un valore (return valore;) dello stesso tipo della funzione. Le funzioni
che non restituiscono valori sono di tipo void (dette anche procedure)->
l’istruzione del return è assente, la funzione termina quando il flusso di
esecuzione arriva alla } finale.

- Invocazione: quando uso la funzione all’interno del main. Nel prototipo non è
necessario specificare un nome per i parametrI (( int somma_interi(int, int);
equivale a scrivere int somma_interi (int addendo1, int addendo2); ))

- parametri formali: parametri dati nella definizione. int nome_funzione (int,

int);

- parametri attuali: parametri dati al momento dell’invocazione.

int a, b;
media = funz_media(a, b);
i tipi devono corrispondere (il primo con il primo ecc)

risultato:
- non può essere un array
- può essere una struct anche se questa contiene degli array al suo interno
parametri:
- non sono modificabili ad eccezione degli array.

Esistono 3 tipi di funzione:

1. procedure senza valore di ritorno
2. funzioni con valore di ritorno
3. funzione/procedure con effetti collaterali -> perché una variabile dichiarata
in una
funzione sia modificata nell’ambiente della chiamante occorre usare i puntatori.
(( Uso i puntatori quando non ho un valore di ritorno. In questo modo non
ritorno nulla ma
vado direttamente a modificare un parametro nel main, che è ciò che io voglio
trovare.Inoltre uso i puntatori quando voglio modificare più variabili – non posso
utilizzare una funzione con
valore di ritorno ma devo usare una void. ))
Es: - funzioni con puntatori
Void modifica_dato(int *dato){
*dato=4;
}
int nuovo_dato(int dato){
Dato=1;
Return dato; }
Int main(){
Int dato =0;
printf(“dato: %d\n”, dato);
nuovo_dato(dato); //il valore della variabile nel main rimasto zero. Perché non
ho assegnato il
valore di ritorno della funzione a nessuna variabile.
printf(“dato: %d\n”, dato);
dato= nuovo_dato(dato); //ho assegnato il valore di ritorno della funzione alla
variabile.
Quindi la mia variabile ha cambiato valore.
printf(“dato: %d\n”, dato); //stampa 1
modifica_dato(&dato); //modifico il dato anche senza avere un valore di ritorno.
E senza
assegnare a nessuna variabile il mio valore di ritorno (è una
funzione void)
printf(“dato: %d\n”, dato); //qui il dato si modifica – mi stampa 4. Il dato è stato
modificato nel
main
//quando io uso i puntatori modifico la variabile a livello globale (nel main). }

--Modifica di parametri attuali

1. Nella definizione della funzione il parametro deve essere di tipo puntore (*p)

2. Nella chiamata si deve passare l’indirizzo (usando &) del parametro attuale
da modificare (&varLocale)

3. Nel corpo della funzione si usa l’operatore "* " di dereferenziazione per
riferirsi al valore del parametro (*p)
Esempio:
#include "stdio.h"
void swap(int * , int *);
int main(){
int a=4, b=9;
swap( &a, &b); //quando chiami la funzione non devi specificare il tipo di
funzione
printf("a= %d, b=%d", a, b);
return 0;
}
void swap (int *a, int *b){
int temp=0;
temp= *a;
*a=*b;
*b=temp;

FUNZIONI RICORSIVE
Funzioni ricorsive: una funzione che chiama se stessa. Per ottimizzare una
funzione in poche
righe.
Bisogna definire due casistiche fondamentali:
1. Caso base. (quando faccio terminare la mia funzione ricorsiva).
2. Passi induttivi. Quelli che si ripetono.

STRUTTURE DI DATI
strutture di dati dinamiche che possono crescere e ridursi durante l’esecuzione
• Liste collegate (linked list) :
--Collezioni di elementi di dati «allineati in una riga»
-- Permettono di inserire ed eliminare elementi da qualsiasi punto
• Pile (stack)
-- Utilizzate nei compilatori e nei sistemi operativi
--Permettono di inserire ed eliminare elementi solo dalla cima della pila
• Code (queue)
-- Rappresentano le file di attesa
-- Permettono di inserire elementi solo alla fine della coda ed eliminarli solo
dalla testa
• Alberi binari (binary tree)
-- Facilitano la ricerca e l’ordinamento dei dati ad alta velocità
-- Permettono l’eliminazione efficiente dei dati duplicati
-- Utilizzati per la compilazione di espressioni nel linguaggio macchina

Strutture dinamiche necessitano una gestione dinamica della memoria. La

gestione dinamica della memoria ha due componenti
• Ottenere ulteriore spazio di memoria per contenere nuovi nodi

• Liberare spazio non più necessario

Per la gestione della memoria sono essenziali:

• La funzione malloc: La funzione malloc serve a chiedere una nuova zona di

memoria da usare. Quello che succede quando viene chiamata la funzione è
che il calcolatore individua una zona di memoria libera, ossia una zona che non
è attualmente occupata da variabili o usata in altro modo, e ne restitusce
l'indirizzo iniziale.

void* malloc (n°di byte da allocare); //alloca size byte nella memoria e ne
ritorna il puntatore void.
Il puntatore punta ad una variabile che non ha nome: può essere utilizzata solo
tramite il suo puntatore. crea in memoria una variabile di TipoDato e restituisce
l’indirizzo del primo byte riservato alla variabile. Se P è una variabile di tipo
puntatore TipoDato, l’istruzione è
P= malloc(sizeof(TipoDato));
si può fare riferimento ad una variabile creata dinamicamente solo tramite
puntatore. Se non c’è più memoria disponibile la malloc restituisce NULL.

Cast esplicito: malloc restituisce un puntatore void. Per specificare che il

programmatore è consapevole che il puntatore è convertito da void ed un altro
tipo (ad esempio int) si usa il cast esplicito.

• La funzione free : Questa funzione dice che la zona di memoria non ci serve
più, e che può quindi venire usata in altro modo. Il vantaggio di chiamare la
funzione free è che, in questo modo, la memoria non più utilizzata dal
programma può venire ``riciclata'', ossia riutilizzata.

void free (void *ptr); //libera la memoria precedentemente allocata per il

puntatore ptr. La memoria fisica è resa nuovamente
disponibile. ! la funzione free deve ricevere, come parametro di ingresso, un
puntatore al quale era stato assegnato come valore l’indirizzo restituito da una
funzione di allocazione dinamica (malloc).

• L’operatore sizeof

--- altre funzioni---

- void* calloc (size_t num, size_t size); //alloca num elementi di dimensione size
allocati a 0

- void* realloc(void *ptr, size_t new_size); //permette di cambiare la simensione

del blocca di memoria allocata puntata da ptr.
Liste collegate

Una lista collegata è una collezione con organizzazione lineare di oggetti struct
autoreferenziali chiamati nodi. Sono connessi da collegamenti di puntatori. Si
accede a una lista collegata tramite un puntatore al suo primo nodo. Si accede
ai nodi successivi tramite il puntatore di collegamento memorizzato in ogni
nodo.

Idati sono memorizzati dinamicamente in una lista collegata creando ogni nodo
quando necessario. Un nodo può contenere dati di ogni tipo. Le pile e le code
sono strutture lineari di dati. Sono versioni vincolate di liste collegate.

Array vs liste collegate

Le liste di dati possono essere memorizzate in array, ma le liste collegate

presentano diversi vantaggi. Una lista collegata è appropriata quando il numero
di elementi da rappresentare nella struttura di dati non è noto a priori. A
differenza degli array, le liste collegate sono dinamiche: la loro lunghezza può
aumentare o diminuire quando necessario. Gli array, invece, hanno una
dimensione fissa e possono essere dichiarati con più elementi di quelli attesi,
causando uno spreco di memoria. L’uso di liste collegate e dell’allocazione
dinamica di memoria per strutture che crescono e si riducono durante
l’esecuzione consente di risparmiare memoria. Tuttavia, ci sono alcuni
svantaggi: i puntatori ai nodi occupano memoria aggiuntiva, e l’allocazione
dinamica espone al rischio di un sovraccarico di chiamate a funzioni. Le liste
collegate possono essere mantenute in ordine inserendo ogni nuovo elemento
nel punto corretto della lista, mentre negli array ordinati, gli inserimenti e le
cancellazioni richiedono tempo. Quando si inserisce o si cancella un elemento
in un array, tutti gli elementi successivi devono essere spostati.

In termini di accesso, gli array offrono un vantaggio: gli elementi sono registrati
in memoria in modo contiguo, consentendo un accesso immediato calcolando
l’indirizzo in base alla posizione. Al contrario, le liste collegate non offrono
accesso immediato ai loro elementi, rendendo l’operazione più lenta in
confronto.

Implementare una lista collegata richiede diversi passaggi. Si definisce la

struttura autoreferenziale struct listNode, utilizzata per costruire una lista
collegata. La definizione di typedef è inclusa per rendere il codice più leggibile.
La variabile startPtr viene inizializzata a NULL per indicare una lista vuota.

Le funzioni principali includono:

--insert, per l'inserimento di elementi: La funzione insert riceve come

argomenti l’indirizzo del puntatore al primo nodo della lista e un carattere da
inserire. Questo permette alla funzione di modificare il puntatore al primo nodo
della lista della funzione chiamante.

--delete, per la cancellazione di elementi: Se il carattere da cancellare

corrisponde al carattere nel primo nodo, dobbiamo eliminare il primo nodo. Si
avanza finché non si localizza il carattere da cancellare. Se il carattere è nella
lista, si dealloca la memoria puntata da tempPtr e si restituisce il carattere che
è stato cancellato.

Pile
Una pila o stack può essere implementata come versione vincolata di una lista
collegata. In una pila, è possibile aggiungere nuovi nodi ed eliminare quelli
esistenti solo in cima. Questa struttura di dati segue il principio Last-In, First-
Out (LIFO), dove il primo elemento a uscire è l’ultimo che è stato inserito. Una
pila si rappresenta tramite un puntatore all’elemento in cima. Il membro link
nell’ultimo nodo della pila è impostato a NULL, indicando il fondo della pila. Non
terminare una pila con NULL può causare errori in fase di esecuzione.

Nelle pile, stackPtr punta all’elemento in cima. Si tratta di una lista collegata in
cui inserimenti e cancellazioni possono avvenire solo sulla cima. Le principali
funzioni per manipolare una pila sono push e pop.

--La funzione push crea un nuovo nodo e lo colloca in cima alla pila.

-- La funzione pop rimuove il nodo in cima alla pila, libera la memoria occupata
e restituisce il valore del nodo rimosso.

Le pile hanno molte applicazioni. Quando viene effettuata una chiamata a

funzione, l’indirizzo di ritorno è inserito con un push in una pila per consentire
alla funzione chiamata di ritornare a quella chiamante. Se si ha una serie di
chiamate, queste seguono un ordine last-in, first-out. Le pile mantengono lo
spazio creato per le variabili locali in ogni invocazione. Quando una funzione
ritorna, lo spazio viene eliminato con un pop. Inoltre, le pile possono essere
utilizzate dai compilatori per valutare espressioni e generare codice in
linguaggio macchina.

CODE
Una coda è simile alla fila davanti alla cassa del supermercato. La prima
persona in fila è servita per prima, mentre i nuovi clienti si aggiungono alla fine
della coda. I nodi della coda possono essere estratti solo dalla testa della coda
e inseriti solo alla fine. Questa struttura segue il principio First-In, First-Out
(FIFO).

Le operazioni principali sono enqueue, per l'inserimento di nodi, e dequeue,

per l'estrazione di nodi.
 La funzione enqueue inserisce un nodo nella coda. La funzione dequeue
elimina un nodo dalla coda.

Le code trovano diverse applicazioni. Nei computer con un solo processore, è

possibile servire un utente alla volta. Le richieste degli altri utenti sono poste in
una coda e avanzano verso la testa man mano che le richieste precedenti
vengono soddisfatte. Nei sistemi multicore moderni, i programmi vengono
collocati in una coda finché uno dei processori non diventa disponibile. Le code
supportano anche lo spooling di stampa: in un ufficio con un'unica stampante, i
documenti vengono messi in coda se la stampante è occupata. Su internet, i
pacchetti aspettano in coda per essere instradati al nodo successivo della rete.
Ogni nodo inoltra un pacchetto alla volta, mentre gli altri rimangono in attesa.

ALBERI
Gli alberi sono strutture dati non lineari. A differenza di liste, pile e code, gli
alberi permettono ai nodi di avere due o più collegamenti. Un albero binario è
una struttura in cui ogni nodo ha al massimo due figli. Il nodo radice è il primo
nodo dell’albero. Ogni collegamento di un nodo si riferisce a un figlio, e due figli
dello stesso nodo sono chiamati fratelli. Un nodo senza figli è una foglia, e i
nodi foglia hanno i collegamenti ai nodi figli impostati a NULL.

Implementare un albero di ricerca binaria consente di creare una struttura in

cui i duplicati non vengono inseriti.

I nodi dell’albero possono essere attraversati in tre modi principali:

-- in ordine,
-- in pre-ordine
-- post-ordine.
La ricerca in un albero binario è veloce, specialmente se l’albero è ben
organizzato. Ogni livello contiene il doppio degli elementi del livello
precedente, e una ricerca in un albero con n elementi richiede al massimo log n
livelli. Ad esempio, in un albero con 1.000.000 di nodi, sono necessari circa 20
confronti per trovare un nodo o determinare che non esiste.

Algoritmi di ordinamento e O grande

Abbiamo già analizzato come sia possibile ordinare un array di dati in ordine
crescente o decrescente utilizzando il metodo Bubble Sort. Ci si può chiedere,
tuttavia, se esistano algoritmi più efficienti. La notazione "O grande" è uno
strumento utile che consente di stimare il tempo di esecuzione di un algoritmo
nel caso peggiore. Nel corso della trattazione esamineremo diversi algoritmi di
ordinamento, confrontandoli sia per il tempo di esecuzione che per l'uso della
memoria.

La notazione O grande è utilizzata per descrivere lo sforzo richiesto a un

algoritmo, indicando la quantità di lavoro necessaria per risolvere un problema.
Nel caso degli algoritmi di ricerca e ordinamento, questa notazione dipende
principalmente dal numero di elementi nei dati da elaborare. Inoltre, la
notazione O grande è uno strumento fondamentale per descrivere i tempi di
esecuzione degli algoritmi di ordinamento nel loro caso peggiore.

--Algoritmi O(1) Considera un algoritmo che controlla se il primo elemento

di un array è uguale al secondo:

• Se l’array ha 10 elementi, richiede un confronto

• Se l’array ha 1000 elementi, richiede ancora un confronto

 Il numero di operazioni dell’algoritmo è indipendente dal numeri di elementi
dell’array Questo tipo di algoritmi ha un tempo di esecuzione costante:

• O(1) non implica solo un confronto, ma un numero costante di operazioni

• Un algoritmo che confronta il primo elemento con i tre successivi, richiede

ancora tempo O(1) anche se richiede tre confronti.

--Algoritmi O(n) Un algoritmo che controlla se il primo elemento di un array

è uguale a un qualsiasi altro elemento richiede al massimo n-1 confronti

• Se l’array ha 10 elementi, richiede fino a 9 confronti

• Se l’array ha 1.000 elementi, richiede fino a 999 confronti

Al crescere di n, la parte dominante in n-1 sarà n (( Sottrarre 1 diventa

trascurabile))

La notazione O grande sottolinea i termini dominanti e ignora quelli

trascurabili. Un algoritmo che richiede n-1 confronti viene detto O(n). Un
algoritmo O(n) ha un tempo di esecuzione lineare.

--Algoritmi O(n2) Un algoritmo che controlla se tutti gli elementi di un array

sono duplicati

• Confronta il primo elemento con tutti gli altri

• Poi il secondo con i restanti, e così via

Ordinamento per selezione

L'ordinamento per selezione (selection sort) è un algoritmo semplice ma

inefficiente. Durante la prima iterazione, seleziona l'elemento più piccolo
nell'array e lo scambia con il primo elemento. Nella seconda iterazione,
individua il secondo elemento più piccolo, ovvero il più piccolo tra i rimanenti, e
lo scambia con il secondo elemento. Questo processo continua fino all'ultima
iterazione, durante la quale viene selezionato il secondo elemento più grande e
scambiato con il penultimo, lasciando l'elemento più grande in ultima
posizione.

Efficienza ordinamento per selezione

L’algoritmo di ordinamento per selezione Si esegue in un tempo

Funzione selectionSort : Il ciclo esterno elabora i primi 𝑛 − 1 elementi

ciclo interno cerca l’elemento più piccolo tra quelli rimanenti ((Viene eseguito 𝑛
((Inserisce l’elemento più piccolo rimanente nella sua posizione ordinata)). Il

− 1 volte nella prima iterazione del ciclo esterno, 𝑛 − 2 volte nella seconda
iterazione; Il numero totale di iterazioni del ciclo interno sono

--Ordinamento per inserzione: L'ordinamento per inserzione (insertion sort) è

un algoritmo di ordinamento semplice ma inefficiente. Durante la prima
iterazione, il secondo elemento dell'array viene confrontato con il primo, e se è
minore, i due elementi vengono scambiati. Nella seconda iterazione, il terzo
elemento viene considerato e inserito nella posizione corretta rispetto ai primi
due. Alla i-esima iterazione, i primi i elementi dell'array originario risultano
ordinati.

--Efficienza ordinamento per inserzione: L'algoritmo di ordinamento per

inserzione si esegue in un tempo di O(n²). La funzione insertionSort utilizza un
ciclo esterno che itera n−1 volte, inserendo un elemento nella posizione
corretta tra quelli già ordinati. Il ciclo interno analizza gli elementi già ordinati
dell'array e, nel caso peggiore, può richiedere fino a n−1 confronti. Ogni
iterazione del ciclo interno richiede un tempo di O(n), e il numero totale di
iterazioni complessive è pari a O(n²) poiché il ciclo interno viene eseguito O(n)
volte. Ignorando i termini meno significativi e le costanti nella notazione O
grande, il tempo di esecuzione risulta essere O(n²).

Ordinamento per fusione

L'ordinamento per fusione (merge sort) è un algoritmo di ordinamento

efficiente ma complesso. Funziona suddividendo un array in due sottoarray di
dimensioni uguali, ordinando ciascuno di essi e poi fondendoli in un array più
grande. L'implementazione di questo algoritmo è ricorsiva. Il caso base si
verifica quando l'array ha un solo elemento, considerato sempre ordinato. Nel
passo ricorsivo, un array composto da due o più elementi viene suddiviso in
due sottoarray, che vengono ordinati ricorsivamente prima di essere fusi
insieme.

Es:
--Efficienza merge sort: L'ordinamento per fusione è più efficiente rispetto a
quello per inserzione e selezione. La prima chiamata alla funzione sortSubArray
genera due chiamate ricorsive alla stessa funzione, ciascuna con un sottoarray
di dimensioni circa pari alla metà dell'array originale, seguite da una chiamata

confronti, ossia 𝑂(𝑛). Le due chiamate ricorsive alla funzione sortSubArray

alla funzione merge. Nel caso peggiore, la funzione merge richiede n−1

generano altre quattro chiamate ricorsive, ciascuna con un sottoarray di

dimensioni circa pari a un quarto di quelle originali, oltre a due ulteriori

l'array in elementi singoli. Il numero di "livelli" è logaritmico in 𝑛, poiché le

chiamate alla funzione merge. Questo processo continua fino a suddividere

dimensioni degli array si dimezzano a ogni livello. Il tempo di esecuzione totale

risulta quindi pari a O(nlogn).

Confronto tra diversi ordini