Programmazione e strutture dati – Appunti completi (algoritmi) di Programmazione C

Antonio Wang - PEU-Z

Programmazione e Strutture Dati

Spiegazione

Sviluppo di Programmi - Analisi e Progettazione

Lo sviluppo di un programma solamente la componente dello scrivere il codice

(anzi, è probabilmente il minore dei problemi) ma include una serie di tematiche

e problemi che vanno affrontati prima di tutto.

Un algoritmo è una descrizione astratta di una soluzione

Cos’è un algoritmo?

ad un problema. Esso è caratterizzato da un numero di passi logici finiti in

maniera precisa e non ambigua.

Lo sviluppo di un programma deve seguire un

Sviluppo dei programmi

determinato schema, e tendenzialmente segue uno schema ben preciso:

• Analisi e specifica;

• Progettazione;

• Codifica;

• Verifica. Le specifiche sono di vitale importanza e le prime cose

Analisi e specifica

che vanno descritte in un programma.

• le condizioni che devono essere soddisfatte per quanto

Precondizione:

riguarda l’input affinché il programma possa essere eseguito correttamente;

• le condizioni che devono essere soddisfatte per quanta

Postcondizione:

riguarda l’output. È una buona norma utilizzare un dizionario dei dati nel

Dizionario dei dati

momento in cui si va a sviluppare un programma durante il suo ciclo di vita.

Esso consiste in una tabella con determinate proprietà:

• Identificatore;

• Tipo;

• Descrizione.

La progettazione include una serie di caratteristiche:

Progettazione

• Definizione di come il programma lavora e trasforma i dati in input in dati

di output;

• Progettazione dell’algoritmo per miglioramenti successivi. Questa teoria

si chiama e ci dice sostanzialmente che un pro-

“stepwise refinement”

gramma non necessariamente nasce già perfetto e finito, ma può avere

determinate modifiche nel corso del tempo che lo migliorino.

1

Antonio Wang - PEU-Z

• nei programmi è buona abitudine andare a

Decomposizione funzionale:

scomporre un’applicazione complessa in più singoli moduli che nel migliore

dei casi possano funzionare in maniera indipendente l’uno dall’altro. Questo

aiuta in termini di facilità di manutenzione del software.

La codifica e la verifica del programma consiste, come

Codifica e verifica

può suggerire banalmente il nome di questo paragrafo in:

• nel linguaggio di programmazione scelto;

Codifica del programma

• seguendo questi criteri:

Verifica del programma codificato

Scelta dei casi di test;

– Esecuzione del programma;

– Verifica dei risultati dei casi di test in relazione a quelli che sono i

– risultati attesi.

Algoritmi di ordinamento

Come visto anche nel corso di Programmazione I, ci sono degli algoritmi di

ordinamento di un array che sono più o meno efficienti. Rivediamoli con calma.

Si prende l’elemento minimo (o massimo) di un array e si

Selection sort

scorre attraverso l’array fino a trovarlo, poi si scambia di posto con il primo

elemento, poi si passa dal secondo elemento in poi seguendo la stessa logica e

così via facendo diminuire progressivamente la parte non ordinata dell’array.

Esempio:

[3,1,2,0]

// cerchiamo il minimo

[0,1,2,3]

// il primo elemento è ordinato, quindi si passa al secondo elemento

// il secondo elemento è il minimo, quindi si passa al terzo

// l'esecuzione del programma continuerà ma alla fine l'array è già ordinato

Insertion sort Esempio:

[3,1,2,0] // è l'array da ordinare

// Si parte dal primo elemento che è già ordinato (parzialmente)

// Si passa dunque al secondo elemento e si confronta andando sempre a ritroso

// fino a ordinarlo nella sotto-sequenza ordinata

// 1 < 3? Sì, quindi scambio

[1,3,2,0]

// Adesso passiamo al terzo elemento

// 2 < 3? Sì, scambio

[1,2,3,0]

// 2 < 1? No, quindi non scambio

[1,2,0,3] 2

Antonio Wang - PEU-Z

[1,0,2,3]

[0,1,2,3] In questo caso si confrontano delle coppie a 2 a 2 e al primo

Bubble sort

scorrimento si trova il massimo elemento dell’array, alla seconda il secondo più

grande e così via. Vediamo un esempio.

Esempio:

[3,1,2,0] // partiamo dalla prima coppia

// 1 è minore di 3 quindi swap

[1,3,2,0]

// adesso confrontiamo il secondo e il terzo elemento

// 2 è minore di 3, swap

[1,2,3,0]

// 0 è minore di 3, swap

[1,2,0,3]

// continuiamo così di nuovo

[1,2,0,3] // prima coppia invariata

[1,0,2,3] // seconda coppia swap perché 0 < 2

[1,0,2,3] // terza coppia invariata

[0,1,2,3]

Ricerca binaria in un array ordinato

In un array ordinato se volessimo trovare l’indice di uno specifico valore possiamo

utilizzare la binary search (o ricerca dicotomica).

Il suo concetto è molto semplice: prendiamo l’elemento centrale dell’array e

confrontiamo con il nostro valore, se il valore è minore allora sicuramente sarà

nella prima metà dell’array il posto che ci interessa, sennò nell’altra metà. Questa

logica viene applicata continuamente fino a quando l’elemento centrale del sotto-

array coincida con il valore che vogliamo trovare e noi terremo conto chiaramente

di quello che è l’indice.

Esempio:

// Si consideri il seguente array:

int arr[] = {1, 3, 4, 6, 7, 8, 10, 13, 14};

int arrLen = / // 9

sizeof(arr) sizeof(arr[0]);

// Prendiamo l'elemento centrale, cioè arr[9 / 2] => arr[4]

// Ipotizziamo di voler trovare l'indice del numero 4

// 4 < 7? Sì, allora consideriamo la prima metà dell'array

// cioè: [1, 3, 4, 6]

// anche qua prendiamo la metà cioè letteralmente arr[4 / 2] e confrontiamo

// 4 == arr[2] quindi l'indice è 2

3

Antonio Wang - PEU-Z

Astrazione e modularizzazione

Tendenzialmente la fase di realizzazione di un

Come si organizza il codice?

codice si divide in due componenti fondamentali:

• del codice: questa parte include la scrittura della specifica,

Progettazione

dello pseudocodice e della progettazione appunto del codice che dobbiamo

realizzare (che siano i tipi di strutture dati e le tecniche algoritmiche);

del codice: ciò significa che dividiamo in più “mod-

• Modularizzazione

uli” il codice che vogliamo scrivere per renderlo più mantenibile ed è

specialmente utile in programmi complessi.

I moduli non sono altro che pezzi di codice indipendenti che ci perme-

Moduli

ttono di poter avere dati e funzioni che possono essere riutilizzati (che è anche

il motivo principale per cui esistono i moduli). Per poter utilizzare i moduli è

necessario comprendere i concetti di:

• Astrazione;

• Information hiding.

Cos’è in parole povere il concetto di astrazione? Con astrazione

Astrazione

intendiamo letteralmente l’astrazione dal come una cosa viene implementata. In

altre parole essa ci permette di nascondere i dettagli dell’implementazione di

una determinata funzionalità dandoci solo le funzioni essenziali per utilizzarla.

La nozione, mutuata dalla psicologia, di “astrazione” permette di

concentrarsi su un problema ad un determinato livello di general-

izzazione, senza perdersi nei dettagli irrilevanti dei livelli inferiori;

l’uso dell’astrazione permette anche di lavorare con concetti e termini

che sono familiari all’ambiente di definizione del problema, senza

doverli forzatamente trasformare in strutture non altrettanto note. . .

Facciamo un esempio: dobbiamo utilizzare una libreria che ci permette di gestire

delle liste, a noi interessa solamente utilizzare le funzioni che ci fornisce la libreria,

non il come vengono gestite quelle liste ad un livello più “basso”.

Ci sono più tipi di astrazione:

Tipi di astrazione questo tipo di astrazione consiste sostanzialmente

• Astrazione funzionale:

nel nascondere i dettagli implementativi di determinate funzioni. Per

sortArray()

esempio una funzione ci permette di ordinare un array senza

il bisogno di fornirci under the hood quale algoritmo di ordinamento viene

utilizzato;

• ci permette di gestire determinate strutture dati

Astrazione sui dati:

tramite apposite funzioni senza fornirci i dettagli interni di queste strutture

dati, dato che ci fornisce appunto le funzioni per andare a fare varie

operazioni su di esse; 4

Antonio Wang - PEU-Z

• questo tipo di astrazione consiste nel nascon-

Astrazione di controllo:

dere i dettagli interni della logica decisionale. Un esempio è quando

for while,

utilizziamo i cicli e infatti non abbiamo bisogno di sapere come

funziona a basso livello la logica decisionale, bensì possiamo utilizzare il

ciclo direttamente.

L’information hiding è fondamentale quando si parla di

Information hiding

moduli, e ha determinate caratteristiche ben specifiche:

• serve a creare moduli autonomi e indipendenti tra loro;

Modularità: i codici diventano meno complessi, per-

• Riduzione della complessità:

ché si evita di dover prima di tutto implementare in un unico luogo un

determinato pezzo di codice e il “client” può utilizzare le funzioni esportate

dal modulo senza pensare alla loro implementazione rendendo tutto meno

complesso e più immediato;

• non condividendo l’implementazione

Protezione dell’implementazione:

“under the hood” del modulo ma solo determinate funzioni o strutture dati,

il client non deve preoccuparsi dell’implementazione interna, migliorando

anche la coerenza all’interno della codebase;

come detto anche prima, utilizzare i moduli

• Riutilizzabilità del codice:

aiuta a poter riutilizzare pezzi di codice che sono generalmente utilizzabili

per poter risolvere problemi di utilità generale;

• nascondere i dettagli interni aiuta a limitare la superficie

Sicurezza:

d’attacco e di conseguenza diminuire il rischio di vulnerabilità.

Ogni modulo è suddiviso in due parti principali:

Modulo

• qui ci sono le definizioni dei servizi messi a disposizione dei

Interfaccia:

clienti (il client sopracitato);

• qui c’è l’implementazione dei servizi

Sezione implementativa (body):

sopracitati.

Un modulo può importare altri moduli e può essere compilato indipendentemente

dai moduli che lo usano.

In C non esiste un costrutto specifico per andare a creare dei moduli. Tendenzial-

mente si usano dei file singoli e i rispettivi header file (cioè i file con l’estensione

.h). .h

Quindi per accedere alle risorse dobbiamo andare ad importare i file

per poter utilizzare effettivamente un modulo. Abbiamo visto questo concetto

precedentemente anche nell’esame di Programmazione I per esempio tramite

#include <stdio.h>.

l’utilizzo di

Quindi nell’header file ci sono dichiarazioni e prototipi, mentre nel file C l’effettiva

implementazione delle funzioni dichiarate all’interno dell’header file.

Secondo l’information hiding quindi poi le

Moduli e librerie di funzioni

funzioni del modulo come detto prima devono seguire determinati requisiti:

5

Antonio Wang - PEU-Z

• nessuna variabile globale;

• nessun effetto collaterale;

• funzioni di servizio nascoste.

Modulo utile

// Interfaccia del modulo utile.h

void scambia(int *x, int *y);

// dichiarazioni di altre funzioni

// Implementazione del modulo utile.c

// Commenti relativi alla progettazione e realizzazione della funzione scambia

void scambia(int *x, int *y) {

int temp = *x;

*x = *y;

*y = temp;

}

// Definizione di altre funzioni

Uso dei commenti

L’utilizzo dei commenti all’interno degli header file serve tendenzialmente

• per le descrizioni sulle specifiche delle funzioni dichiarate dall’header file;

• L’utilizzo dei commenti all’interno dei file C invece servono per la proget-

tazione delle funzioni.

I moduli possono essere compilati indipendentemente tramite

Compilazione

il consueto comando:

gcc -c <input>.c

Allo stesso tempo si possono compilare più file contemporaneamente sempre

gcc

tramite chiaramente:

gcc -c <input1>.c <input2>.c .o.

In entrambi i casi si ottengono dei file con estensione Per poterli linkare e

unire in un unico eseguibile chiaramente si può utilizzare il seguente comando:

gcc <input1>.c <input2>.c -o <executableName>

Progetto: e comando

Makefile make

Tutti gli ambienti di programmazione ci consentono di creare dei progetti. Il

Makefile

metodo in ambiente UNIX è tendenzialmente tramite e il comando

make.

Makefile

Il è costituito da specifiche del tipo:

target_file: dipendenze_da_file

comandi 6

Antonio Wang - PEU-Z make target_file

Esecuzione della specifica:

L’ordine delle specifiche chiaramente non è importante,

Alcune osservazioni

ma è buona pratica inserire come prima specifica quella per la costruzione del

programma eseguibile. In questo caso per lanciare il processo è necessario solo il

make.

comando Makefile.

Facciamo un esempio di

ordina_array: utile.o vettore.o ordina_array.o

gcc utile.o vettore.o ordina_array.o -o ordina_array

utile.o: utile.c

gcc -c utile.c

vettore.o: vettore.c

gcc -c vettore.c

ordina_array.o: ordina_array.c

gcc -c ordina_array.c ordina_array

Nel nostro esempio il primo che prova ad essere eseguito è che

utile.o, vettore.o ordina_array.o.

dipende da: e Dunque va a vedere

se sono presenti, nel caso in cui non sono presenti allora va ad eseguire

utile.o, vettore.o ordina_array.o utile.c, vettore.c

e che dipendono da

ordina_array.c

e rispettivamente. Prendiamo come esempio una lista di

Esempio di Astrazione sui dati

contatti. Se noi creassimo un sistema di gestione contatti all’utente non interessa

e non vedrà l’implementazione under the hood della gestione dei contatti o la

struttura dati utilizzata, ma solamente ciò che gli serve per interagire con essi.

Avremo tendenzialmente due strutture dati:

• Struttura contiene numero di telefono e nome del contatto;

Contact:

• Struttura potrebbe contenere il numero di contatti

ContactManager:

size, capacity

attuale la capacità massima di contatti e l’array di contatti

Contact *contacts.

Funzioni

init_manager:

• inizializza il gestore allocando dinamicamente la memoria

per un array di contatti con capacità definita;

add_contact:

• aggiunge un contatto al gestore contatti se c’è spazio libero;

get_contacts:

• permette di vedere la lista intera dei contatti;

find_contact:

• permette di cercare il contatto specifico per nome e lo

visualizza se trovato;

free_manager:

• libera la memoria dinamica allocata per i contatti.

7

Antonio Wang - PEU-Z

Astrazione dei dati

• l’utente esegue funzioni semplici come

Interfaccia semplice:

add_contact, find_contact ecc. e non ha bisogno di preoccuparsi come

i contatti vengano memorizzati internamente;

• tutta la parte della gestione

Nascosta la gestione della memoria:

della memoria, della struttura dati utilizzata non è un qualcosa che serve

all’utente. L’utente necessita solo di sapere la struttura dell’API fornita il

che va a semplificare di molto l’uso dell’utente del modulo.

Vantaggi

• l’utente non deve preoccuparsi dei dettagli di implemen-

Semplicità:

tazione, ma solo di come andare ad utilizzare le funzioni fornite;

• come conseguenza diretta al vantaggio descritto poco fa,

Modularità:

chiaramente c’è anche il fatto che se cambiasse l’implementazione interna

(se cambiassimo per esempio la struttura dati da array a lista collegata),

l’utente non dovrebbe cambiare nulla nel suo codice.

Testing dei programmi e uso dei file testare?

Alcune note sul testing Cosa significa

Testare significa verificare che il comportamento del nostro programma sia con-

forme al comportamento atteso. L’output atteso viene definito nel

oracolo,

momento in cui l’output effettivo non corrisponde all’oracolo si ha un malfun-

zionamento.

In generale non è possibile dimostrare la correttezza di un qualunque programma

e soprattutto testare un programma con tutti i dati di test. L’obiettivo quindi è

individuare classi di test, selezionare un caso di test per ogni classe ed evitare

casi di test ridondanti.

insieme dei casi di test di un programma.

Test suite: Nell’esempio di un

Nel nostro esempio di ordinamento di un array

sorting algorithm, dobbiamo tenere in considerazione alcuni aspetti:

n

• Il numero di elementi dell’array: quindi array con diversi elementi, array

n n

con lunghezza pari a 1 ed array con lunghezza pari a 0;

• La disposizione degli elementi dell’array: quindi il caso in cui l’array è già

ordinato, il caso in cui è ordinato in caso decrescente e il caso in cui non è

ordinato.

Una test suite per il nostro esempio

Nome Input Oracolo

TC1 (un solo elemento) 5 5

8

Antonio Wang - PEU-Z

Nome Input Oracolo

TC2 (input ordinato in maniera 123456789 123456789

crescente)

TC3 (input ordinato in maniera 10 9 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 10

decrescente)

TC4 (non ordinato) 5 8 2 9 10 1 4 7 3 6 1 2 3 4 5 6 7 8 9 10

12 11 11 12

Un malfunzionamento di un programma è causato da

Testing e debugging

un difetto (errore, bug). Esso può essere introdotto in fase di analisi, specifica

oppure di stesura del codi