Lezione 21

Liste Ordinate

Liste Invasive vs Liste non Invasive.

Dato un tipo T che per generalità supponiamo sia una struttura, possiamo creare una lista di oggetti di tipo T in due modi:

  1. Nel modo "invasivo", si modifica la dichiarazione del tipo T, ed in particolare si aggiunge alla struttura un puntatore next, che punta all'elemento successivo nella lista, tale campo viene appunto aggiunto, modificando la dichiarazione della struttura originaria. Notiamo che quindi, non abbiamo più un semplice tipo T, ma piuttosto un tipo "membro di lista di T".
  2. Nel modo "non invasivo" non viene modificato il tipo T, ma viene creato un nuovo tipo che servirà a rappresentare oggetti "elemento di lista di T", oltre al tipo T originario.

Esempio, supponiamo di dover rappresentare punti in , possiamo usare una struttura


// tipo Point2d
typedef struct 2dpoint { double x,y; } Point2d;

// Versione invasiva di una lista di Point2d singolarmente linkata
typedef struct 2dpointl { 
     double x,y; 
     struct 2dpointl *next;
} ListPoint2d_invasiva;

// Versione *non invasiva* 

typedef struct l {
    Point2d point;
    struct *l next;
} ListPoint2d_noninvasiva;
 

Notiamo che nel secondo caso, non abbiamo bisogno di modificare la struttura Point2d che potrebbe essere stata già usata nel codice e che magari non vogliamo cambiare. Se invece non abbiamo vincoli di questo tipo, possiamo usare la versione invasiva che include il puntatore per realizzare la lista direttamente dentro la definizione di punto (la versione non invasiva è però matematicamente più elegante perche distingue chiaramente tra il tipo punto2d ed il tipo list_of_point2d, che sono ovviamente concetti diversi.).

Per semplicità nel seguito useremo liste invasive, quindi definiremo insieme sia i campi che rappresentano le informazioni sia i puntatori che servono a collegare gli elementi della lista.

Liste Bidirezionali, e Circolari

Dato un elemento p, il campo next di p, indica quale sia l'elemento che segue p nella lista. Notiamo che spesso è utile poter muoversi anche all'indietro, e questo è semplice da realizzare basta includere un altro campo puntatore che possiamo chiamare prev. Esempio:


// lista bidirezionale

typedef struct p { 
    double x,y;
    struct p *prev, *next;   //next punta al successivo, prev al precedente;
} LinkedPoint2d;

Una particolare versione di lista bidirezionale, detta lista circolare può essere molto utile. Tale lista soddisfa i seguenti requisiti: il successore dell'ultimo elemento è il primo elemento della lista, ed il predecessore del primo elemento è l'ultimo. In codice si ha:


// se head punta alla testa della lista
// e tail punta all'ultimo elemento della lista
// la lista è circolare se è vero:

assert(head->prev == tail && tail->next == head);

//  

Costruttori e Distruttori

La gestione delle liste deve essere fatta con un approccio bottom-up, si scrivono quindi delle funzioni elementari per implementare le operazioni di inserimento, cancellazione, ricerca degli elementi, e si usano queste per poter poi manipolare le liste.
Il costruttore di un tipo di dato, è una funziona che costruisce (con la malloc) un elemento e lo inizializza correttamente. Il distruttore invece ha la responsabilità di distruggere l'elemento.
Esempio:

// associazione tra parole e un intero, molto utile, utilizzi:
// wordstat: word e' una parola e value e' il conteggio delle occorrenze
// compilatore o interprete: word e' una variabile intera e value e' il suo valore.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct item {
   char *word;
   int value;
   struct item *next;
} LinkedWord;

// Costruttore
LinkeWord* new_word(const char* s, int v)
{
    LinkedWord *n = malloc(sizeof(LinkedWord));   // creo l'lemento
    n->word = malloc(strlen(s)+1);                // creo la stringa
    strcpy(n->word,s);     // metto a posto i campi
    n->value = v;
    n->next = NULL;
    return n;
}

// Distruttore
void delete_word(LinkedWord *p) 
{
    // prima distruggiamo la stringa poi l'lemento
    free(p->word); free(p);
}

void print_word(LinkedWord *p) 
{
   if (p==NULL) return;
   printf("(%s,%d)",p->word,p->value);
}

// uso:

int main(void)
{
    LinkedWord *a = new_word("Mario",10);
    LinkedWord *b = new_word("Paolo",20);
    LinkedWord *c = new_word("Giovanna",30);
    // notiamo che non sono ancora collegati, non abbiamo ancora pensato a gestirli come liste
    print_word(a); printf("\n");
    print_word(b); printf("\n");
    print_word(c); printf("\n");
    delete_word(a);
    delete_word(b);
    delete_word(c);
    return 0;
}

Funzioni per Inserimento, Cancellazione, Ricerca di un elemento.

Normalmente le liste vengono utilizzate manipolando un puntatore che rappresenta la testa della lista. La funzione insert può assumere varie forme a seconda dei requisiti che la lista deve soddisfare. In alcuni casi ci possono essere varie funzioni insert, ad esempio per inserire un elemento all'inizio della lista, o per appenderlo, in fondo alla lista, o se ad esempio vogliamo inserire l'elemento in un punto specifico perche la lista deve soddisfare requisiti di ordinamento.

Versione semplice, inseriamo in testa:


LinkedWord* add_head(LinkedWord *testa, const char *string, int v)
{
    LinkedWord *n = new_word(string,v);
    n->next = testa;     // va bene anche se testa == NULL
    return n;
}

Esempio (modificate il programma sopra):


// funzioni precedenti.

void print_list(LinkedWord *testa)
{
	for(LinkedWord*l=testa; l!=NULL; l=l->next) {
		print_word(l); printf("->");
	}
        printf("null\n");
}
// uso:
void destroy_list(LinkedWord *testa)
{
	LinkedWord*l = testa;
	LinkedWord *p; 
	while (l != NULL) {
                // nota bene: leggiamo p->next prima di distruggere 
		p = l->next; 
                delete_word(l); 
		// ok, l diventa p : l = l->next
                l = p;
	}
}

int main(void)
{
    LinkedWord *lista  = NULL;
	lista = add_head(lista,"Mario",10);
	lista = add_head(lista,"Paolo",20);
	lista = add_head(lista,"Giovanna",20);
	print_list(lista);
	destroy_list(lista);
    return 0;
}

Prima di occuparci di una versione generale della insert (o add) vediamo come cercare un elemento e come cancellarlo. Nel caso della find possiamo implementare l'algoritmo in forma iterativa o ricorsiva, cominciamo con la versione ricorsiva, molto semplice.

// find versione ricorsiva
LinkedWord *find_list_rec(const LinkedWord *list, const char *string)
{
    if (list == NULL) return NULL;
    if ( strcmp(list->word, string) == 0) return list;
    else return find_list_rec(list->next,string);
}
// find versione iterativa
LinkedWord *find_list_iter(const LinkedWord *list, const char *string)
{
    while (list!=NULL) 
        if (strcmp(list->word,string)==0) 
             return list; 
        else list = list->next;
}

Notiamo che le due versioni sono comunque semplici, e che la seconda versione può essere facilmente ottenuta dalla prima seguendo uno schema generale chiamato "Trasformazione della ricorsione in coda".
Tale schema può essere applicato a tutte le funzioni ricorsive che hanno un unica chiamata ricorsiva presente come ultima istruzione della funzione. Tale chiamata, implica evidentemente un esecuzione che riparte dall'inizio del corso della funzione, pertanto può essere sostituita da un while che ingloba tutto il corpo: naturalmente per essere semanticamente equivalenti, si devono gestire in modo corretto i cambiamenti di stato delle variabili: nella chiamata ricorsiva, si passa il resto della lista (l->next), e pertanto nella versione iterativa si aggiornerà list con list=list->next, notiamo che possiamo senza problemi cambiare tale variabile dentro la funzione perche, visto che il passaggio dei parametri è per valore, esso è solo una copia del parametro formale e il suo cambiamento non verrà visto dal chiamante.

Prima di vedere un possibile esempio per la ricerca, vediamo di preoccuparci anche delle cancellazioni che sono in genere una faccenda più delicata, il problema è legato al fatto che in una lista singolarmente linkata noi non possiamo "tornare indietro", quindi se cerchiamo un elemento muovendo un puntatore fin quando una certa condizione è vera, allora quel puntatore per definizione si fermerà e punterà all'elemento che ci interessa cancellare, ma per farlo dovremmo modificare l'elemento precedente che contiene proprio un suo riferimento.

Soluzione: se si fanno molte cancellazioni, allora conviene usare liste doppiamente linkate, cosi da poter accedere da ogni punto della lista, sia al successivo che al precedente. oppure nel nostro caso, possiamo tenere un puntatore ausiliario che punta sempre all'elemento precedente rispetto a quello che stiamo analizzando, ecco il codice:


LinkedWord *delete_list(LinkedWord *list, const char *s)
{
	LinkedWord *cur  = list, *p  = NULL;
    // cerca s tenendo un riferimento all'elemento precedente	
    while (cur != NULL && strcmp(cur->word,s)!=0) {
		p=cur; cur=cur->next;
	}
	if (cur == NULL)
		return list;   // siamo alla fine s non e' nella lista
	if (p == NULL)     // siamo all'inizio aggiorna la testa
	    list = list->next;
	else
		p->next = cur->next;  // siamo in mezzo
	delete_word(cur);      // se cur!=NULL
	return list;
}

Usiamo la funzione sopra:

int main(void)
{
    LinkedWord *lista  = NULL;
    lista = add_head(lista,"Mario",10);
    lista = add_head(lista,"Giovanna",40);
    lista = add_head(lista,"Paolo",20);
    lista = add_head(lista,"Giovanna",30);

    print_list(lista);
    printf("Search:--------------\n");
    print_word(find_list_rec(lista,"Paolo")); printf("\n");
	
    // troviamo la prima e la seconda occorrenza
    LinkedWord *g = find_list_rec(lista,"Giovanna");
    print_word(g); printf("\n");
    print_word(find_list_rec(g->next,"Giovanna")); printf("\n");
    print_word(find_list_iter(lista,"Mario")); printf("\n");

    printf("Delete:----------------\n");
	
    lista = delete_list(lista,""); print_list(lista);
    lista = delete_list(lista,"Paolo"); print_list(lista);
    lista = delete_list(lista,"Mario"); print_list(lista);
    lista = delete_list(lista,"Giovanna"); print_list(lista);
    lista = delete_list(lista,"Giovanna"); print_list(lista);

    destroy_list(lista);
    return 0;
}

La funzione insert costruita sopra inserisce un elemento solo in testa alla lista, esistono invece due varianti molto importanti, una variante costruisce insert in modo che la lista sia ordinata (su un qualche campo, in modo crescente o decrescente) un altra variante inserisce l'elemento in coda.

Nel caso ad esempio del programma che conta le parole, consideriamo che lo schema del programma principale richiede di cercare una parola e eventualmente aggungerla o modificare il numero di occorrenze, per ogni parola letta, la ricerca quindi deve essere comunque fatta ed è la parte dispendiosa del programma. Potremmo ottimizzare il caso medio se le parole sono tenute ordinate per numero di occorrenze in modo descrescente, il ragionamento è: se una parola è frequente (il numero di occorrenze è alto) allora la probabilità che appaia ancora sarà maggiore rispetto alle altre, quindi se la lista è ordinata in modo decrescente per numero di occorrenze le parole che cerco più spesso saranno nella parte iniziale della lista e saranno trovate con un numero minore di confronti (ci aspettiamo che "Alice" sia prima, nel libro che parla delle sue avventure).

Un esempio di inserimento ordinato è il seguente:

LinkedWord *add_ordered(LinkedWord* list, const char *s, int v)
{
	LinkedWord *p = NULL, *l = list;
	LinkedWord *n = new_word(s,v);	
	for (; l!=NULL && l->value >= v; p=l,l=l->next) ;
	if (p == NULL) {
		n->next = list; return n;
	}
	p->next = n;
	n->next = l;
	return list;
}

LinkedWord *add_ordered_rec(LinkedWord *list, const char *s, int v)
{
	// caso base cambia la testa
	if (list == NULL || v > list->value) {
		LinkedWord *n = new_word(s,v);
		n->next = list;
		return n;
	}
        // recurse
        list->next = add_ordered_rec(list->next,s,v);
	return list;
}

potete provare la funzione sopra, cambiando nel programma precedente add_head con add_ordered. La versione ricorsiva è in questi casi, più elegante e comprensibile.

Se si vuole inserire un elemento in coda, (append) e si gestisce la lista con un puntatore al primo elemento come fatto finora, l'unica soluzione è scorrere la lista fino all'ultimo elemento e poi aggiungere il nuovo elemento. Questo ovviamente costa tanto quanto la lunghezza della lista, quindi, nel caso in cui l'inserimento in coda avviene con alta frequenza, può essere conveniente mantenere oltre al puntatore alla testa, anche un puntatore alla coda, e magari visto che ci siamo anche il numero di elementi presenti nella lista. Esempio:


typedef struct listinfo {
    LinkedWord *testa,*coda;
    int len;
} ListInfo;

// aggiunge un elemento in coda
void list_append(ListInfo *l, const char* s, int v)
{
    LinkedWord *n = new_word(s,v);
    if (l->coda == NULL) l->coda = l->testa = n; else l->coda->next = n;
    l->len++;
}

int main(void)
{
    ListInfo parole = { 0 };
    list_append(&parole,"Ciao",10);
    print_list(parole.testa);
    return 0;   
}

Notate che in quest'ultimo caso, la struttura viene passata per riferimento (usando un puntatore), e viene direttamente cambiata dentro le funzioni che la modificano, queste ultime avranno quindi dominio void.

In questa pagina potete trovare una versione del programma che calcola le statistiche delle occorrenze di parole, che usa delle liste (non ordinate), provate a modificarlo in modo da usare una lista ordinata, come sopra, in senso decrescente rispetto al numero di occorrenze (le parole più frequenti saranno quindi le prime), e verificate se c'è un miglioramento nei tempi di esecuzione.

Lezione 19-20

File Binari

  • Differenze tra file di testo e file binari.
  • funzioni per letture scrittura: fwrite fread
  • file binari strutturati, funzioni per movimento: fseek, ftell, rewind
  • utilizzo per memorizzare dati in formato binario: esempio, vettori, matrici.
  • utilizzo per creare piccoli database: vedere anche libro.

Memoria Dinamica

  • Differenza tra stack e heap: guardate velocemente la figura in basso nell'articolo seguente (articolo), poi leggete giusto l'inizio di (questo).
  • API: malloc, calloc, free, realloc.
  • malloc, tipo di ritorno come puntatore non tipato (void *), cast implicito in C99, (ma non in C++) quindi meglio farlo.
    int *p = (int *) malloc(sizeof(int));
  • se la malloc restituisce NULL la memoria fisica è esaurita, (difficile con i sistemi di memoria dinamica moderni, ma non controllare significa costruire codice non robusto: consiglio creare una funzione xmalloc che controlla subito dopo aver fatto la malloc se il puntatore è NULL), cosi si evita di controllare sempre.
  • Attenzione la memoria restituita NON è inizializzata, se la si vuole inizializzata (a zero) usare calloc.
  • realloc è come una free+malloc ma cerca di creare il nuovo blocco allungando o restringendo il blocco esistente per mantenere località.
  • Utilizzo:
    • Allocazione dinamica di vettori. Importante caso particolare di questo: allocazione dinamica di stringhe. Utilizzo tipico, funzione strdup:
      char * strdup(const char * s)
      {
        size_t len = 1+strlen(s);
        char *p = malloc(len);
      
        return p ? memcpy(p, s, len) : NULL;
      }
    • Allocazione dinamica di matrici: esempio.
    • Strutture dati dinamiche: liste singolarmente linkate, liste doppiamente linkate, liste bidirezionali.

Lezione 18

Programma del corso completato. Mancano solo due argomenti: file binari (funzioni fread/fwrite e fseek/ftell/frewind), e gestione dinamica della memoria (malloc,free,realloc), con introduzione alle strutture dati dinamiche (liste, code, pile, alberi).

Programma WordCount (Conteggio di Parole da File). Sotto sono riportati i link con i sorgenti del programma che verrà implementato in varie versioni. L'ordine di lettura non è quello di presentazione a causa di variazioni relative al diverso anno accademico. Si consiglia quindi di studiarli in questo ordine:

  • Versione 1.0 schema del programma generale, in un unico file, operazioni del dizionario abbozzate (programmazione top-down). Lezione 15
  • Versione 2.0 versione con vettore statico (dopo la versione con liste), uso di file separati per il dizionario e per il programma, dizionario come ADT (Tipo di dato Astratto).
  • Versione 3.0 che tratteremo la prossima volta, introduzione alle strutture lineari dinamiche (liste). (Codice nella lezione 16 sotto, primo sorgente).

Importante: Si consiglia di leggere e studiare gli esempi e gli esercizi svolti presenti nel sito web, relativi agli anni precedenti.

 

Lezione 15: Strutture

Lezione 16: Liste, Code reengineering.

Lezione 17

Calcolabilità

  • Revisione della lezione precedente, sistemi di transizione, algoritmo, nozioni di calcolabilità
  • Problema della Fermata.
  • Complessità Computazionale, misura di tempo come tempo impiegato dall'istanza peggiore di dimensione .

Linguaggio C

  • Strutture. Definizione e dichiarazioni del tipo struttura.
  • Dichiarazione di variabili di tipo struttura, esempi.
  • Operatore "." per accedere ai campi di una struttura a partire da una variabili.
  • Semantica delle variabili struttura per "valore", uso dell'assegnamento tra variabili, passaggio delle strutture per valore.
  • Uso della typedef per semplificare e abbreviare i nomi dei tipi.
  • Tipi di dato misti, vettori di strutture, strutture che contengono altre strutture o vettori, strutture che contengono puntatori.
  • Puntatori a strutture, uso dell'operatore freccia ->

Esercizi:

  • Scrivete un programma C che implementa un piccolo CAD 2d. Il programma presenta un interfaccia in stile "linea di comando" con una serie di comandi a disposizione:
    • help    (stampa un elenco di tutti i comandi e per ogni comando gli argomenti e la descrizione di cosa fa).
    • load project   (carica il file "project.cad", dove avete salvato una descrizione dei vostri dati, nota: project.dat è solo un esempio di un nome generico)
    • save, saveas project   (salva il progetto corrente sul file con il nome associato al progetto (save) o con il nome specificato "project.cad")
    • clear all         (cancella tutte le primitive definite nel progetto, si torna ad uno stato iniziale).
    • new project   (crea un nuovo progetto, implica che il nome del progetto sarà project)
    • point (x,y)     (crea un punto alle coordinate (x,y))
    • line (x1,y1) (x2,y2)  (crea il segmento passante da (x1,y1) a (x2,y2))
    • rect (x1,y1) (x2,y2)  (crea il rettangolo con vertice inferiore sinisto in (x1,y1) e vertice superiore destro in (x2,y2) con i lati paralleli agli assi cartesiani).
    • square (x1,y1) l        (crea un quadrato di lato l, con vertice inferiore sinistro in (x1,y1)).
    • list                           (elenca tutte le primitive inserite nel progetto e per ogni primitiva stampa i suoi attributi e un numero che la identifica univocamente).
    • scale (sx,sy) id         (modifica la primitiva di identificatore id, scalandone le dimensioni del fattore sx,sy, si applica a tutte le primitive tranne che ai punti).
    • translate (tx,ty) id      (sposta la primitiva di (tx,ty)).
    • rotate (ax,ay) id        (ruota rispetto al suo centro la primitiva di un angolo ax rispetto all'asse x e ay rispetto all'asse y) attenzione, per poter
      ruotare correttamente rispetto al centro, si dovrà prima traslare nel centro degli assi la primitiva, poi svolgere la rotazione e
      infine ritraslare la primitiva nella posizione originale.
  • Provate a definire le strutture dati associate ad un social network. Quali strutture definite, quali informazioni serve memorizzare?

Lezione 16

Nozioni di Calcolabilità

  • Materiale didattico delle note, disponibili nella pagina del programma.
  • Definizione Formale di Linguaggio. Appartenenza a Linguaggi come "Problemi Decisionali", Problemi di Calcolo di una funzione come problema decisionale: per una opportuna funzione di codifica, se allora calcolare è equivalente a decidere se data la coppia si ha . Ad esempio:
    • Se il problema è decidere se un intero è primo, avremo come input un intero cioè , e come linguaggio: PRIMES = è primo .
    • Se il problema è la soluzione di un sistema lineare, , allora, esiste una codifica , tale che è il linguaggio delle stringhe binarie che rappresentano le soluzioni del sistema. Il problema di trovare una soluzione del sistema, è equivalente al problema decisionale che data una stringa qualunque di {0,1} decide se essa appartiene a .
  • Algoritmi come sistemi di transizione terminanti, esempio di modello di calcolo (come sistema di transizione): Macchine di Turing.
  • Esistenza della macchina di Turing Universale: programmi come "codifiche" di una Macchina di Turing, per il nastro della macchina universale.
  • Macchina Universale come Interprete del formalismo delle macchine di Turing.
  • Esistenza di problemi non calcolabili (secondo Turing): problema della fermata.
  • Esistenza di problemi non calcolabili: dimostrazione per cardinalità, cioè, l'insieme di tutte le macchine di Turing è numerabile. Mentre le funzioni dai naturali ai naturali hanno la cardinalità del continuo.

Riferimenti:

  • Dimostrazione diagonale.
  • libro: Per una trattazione più approfondita si rimandano gli studenti a leggere il libro disponibile online. In particolare:
    • Nella sezione 1.1.6 per la dimostrazione diagonale (ma tutto il primo Capitolo sarebbe un buon ripasso/studio di concetti di base). Sezione 1.3 per la definizione di linguaggio formale, fino a 1.3.3 (facoltativo se vi piace l'algebra). Sezione 1.3.4 per la cardinalità dei linguaggi.
    • Alla fine del Capitolo 2, Definizione 2.10, 2.11.
    • Quindi nel Capitolo 5, definizione ed esempi di macchina di Turing, in particolare l'esempio con il grafo che modella la funzione di transizione vi farà capire meglio come in pratica sono fatte le MdT.
    • Sezione 5.1.2 computazione: Definizione 5.6 e 5.7, verificate che queste definizioni dicono sostanzialmente qualcosa di simile a quello che nelle note è definito un sistema di transizione e un algoritmo.
    • Sezione 5.2 e 5.3 calcolabilità di funzioni.
    • Per il problema della fermata è preferibile: un video molto simpatico.

Lezione 15

Capitolo Stringhe.

  • Stringhe costanti come puntatori. Le stringhe costanti sono di sola lettura, modificarle è un errore a runtime.
  • Stringhe non constanti, vettori di caratteri terminate da zero, inizializzazione, lettura con scanf, stampa con printf.
  • Funzioni di libreria: strlen, strcpy, strcat, strcmp. e tante altre: vedere libro.
  • Vettori di stringhe costanti, argomenti della linea di comando, parametri della main: argc, argv.
  • Introduzione al concetto di tipo di dato astratto. Applicazione: FILE.
  • Operazioni sui file, apertura ( fopen ), chiusura ( fclose ). Operazioni su file di testo: fprintf, fscanf, fgetc, fgets.

Esempio visti a Laboratorio:

Stringhe costanti, uso di vettori di stringhe costanti, parametri da linea di comando

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#include <string.h>

/* La funzione main, accetta due parametri:
   argc e' un intero, che specifica la lunghezza del vettore di stringhe argv.
   argv e' un vettore di stringhe costanti. nota: argv[0] e' sempre presente ed
   e' uguale al nome (e percorso) del file eseguibile associato al programma. */

int main(int argc, char *argv[])
{
    char *p = "Ciao ragazzi\n";

    // p e' una stringa costante, il compilatore alloca la memoria per noi, ma in sola lettura.

    printf("%s - quarto carattere: ",p); // posso leggere
    putchar(p[3]);   
    putchar('\n');

    // p[3] = 'x';   // non posso scrivere: se decommento questo, il programma si pianta a runtime.
    // morale -> non provate mai a modificare una stringa costante ad esempio gli elementi di argv.
    // stampiamo tutti gli argomenti:
    
    for (int i=0; i<argc; i++)
        printf("argomento %d: %s\n",i,argv[i]);

    return 0;
}

Varie funzioni di libreria, e file. Cosa fa questo programma?
Scrivete il codice, e salvatelo come numeri.c
Compilatelo e provate ad eseguirlo su un file di testo che potete creare voi
con notepad++, ad esempio su un file "testo.txt" che contiene:

"Ciao ragazzi, finora 10 + 100 fa 110,
ma oggi decido che 2 + 2 = 5."

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#include <string.h>
#include <ctype.h>

#define LINELEN 1024

void stampalo(FILE *f)
{
    char line[LINELEN]; 
    char num[LINELEN];
    
    // fgets == NULL se non leggo nulla (file finito).

    while (fgets(line,LINELEN,f) != NULL)
    {
        // ok, line contiene una linea di testo.
        // cerco la prima cifra:
        int i = 0;
        while (i<LINELEN && line[i]!='\0' && !isdigit(line[i])) i++;
     
        if (i == LINELEN) continue;   // finito, leggo la riga successiva.
 
        int j = 0, c = 0;
        while (j<LINELEN && (c = line[i++])!='\0' && isdigit(c)) num[j++] = c;
        num[j] = '\0';   // la stringa va terminata con lo zero se no..cavoli amari.
        if (j>0) printf("%s\n",num);
    }
}

int main(int argc, char *argv[])
{
    // argomento main: nome di un file.
    
    if (argc < 2) {
        fprintf(stderr,"Uso: wordstat [nomefile]\n");
        exit(1);
    }
    char *nome = argv[1];
    FILE* input = fopen(nome,"r");  // apro in lettura
    if (input == NULL) {
        fprintf(stderr,"Errore: non riesco ad aprire il file %s\n",nome);
        exit(1);
    }

    stampalo(input);

    fclose(input);
    return 0;
}

Fun with Python:

scrivete il seguente programma, e salvatelo come "webread.py", nella stessa cartella del programma C fatto sopra.

import urllib.request
import sys

if len(sys.argv) < 2:
    print("leggiweb: url")
url = sys.argv[1]
html = ""
with urllib.request.urlopen(url) as response:
    html = response.read()
print(html)

adesso eseguite:

python3 webread.py http://www.repubblica.it > giornale.html

e subito dopo:

numeri.exe giornale.html

il risultato estrarrà tutti i numeri presenti nel codice html della pagina frontale (home) di repubblica.it
(compresi tutti quelli presenti nel codice javascript presente, quindi ..molti).
Se avete problemi nell'eseguire python3 da console, potete 1) aprire una console python e poi spostarvi dentro la cartella giusta, oppure come spiegato, inserire nel path della console corrente, la cartella che contiene l'eseguibile dell'interprete python:
cercate python.exe o python3.exe nella cartella dell'installazione di python, ed una volta trovata tale cartella, inserite:

 set PATH=percorsocartella;%PATH%

se per caso ci sono spazi all'interno del percorso è necessario fare:

 set "PATH=percorsocartella;%PATH%"

e verificate se python3 viene eseguito, questo vale per ogni programma.

Esercizi

Esercizio 1: scrivere un programma "calc" che riceve da linea di comando sempre e solo due valori floating point con in mezzo un operatore "+" "-" etc. ad esempio

calc 2.4 + 3

Il programma legge gli argomenti, converte i numeri in modo appropriato, calcola il valore dell'operazione e stampa il risultato. Che problemi si pongono? cosa accade ad esempio se non inserisco gli spazi tra gli argomenti? "3+4.2".

Esercizio 2: Scrivere un piccolo "interprete" di espressioni, chiamiamolo minipython l'interprete esegue un ciclo in cui:
1. stampa il prompt " > "
2. legge una stringa che l'utente inserisce terminata con <enter>, la stringa è un espressione come sopra. accettate questa volta espressioni con spazi o senza ad esempio "2+3" o "3.14 * 2" o "3   +   4   -   8", consiglio: leggete la stringa con fgets(comando,LEN,stdin); poi elaborate carattere per carattere della stringa comando con un while. Usate le funzioni di libreria in ctypes.h per capire se il carattere è una cifra, e usate una stringa secondaria per separare i vari "pezzi" che chiameremo "token" (biscottini). Il primo passo quindi consiste nel riuscire a scomporre e stampare l'epressione sopra come I(2) OP(+) F(3) dove (I,F,OP) è un modo per far capire che quello che ho riconosciuto la parte della stringa corrispondente e l'ho convertita nel tipo adeguato (intero, float, operatore). Una volta fatto questo, potete banalmente fare uno switch sull'op per calcolare il valore dell'espressione ed eseguirla al punto sotto. Preoccupatevi solo di espressioni del tipo "numero op numero op numero op numero op numero", tipo "3 + 4.5 + 1 - 8 * 3" senza preoccuparvi di come gestire le precedenze tra gli operatori, quindi per voi "3 + 4 * 2" sarà uguale a "14" e non come dovrebbe "11".
3. esegue l'espressione e stampa il risultato, e ritorna al punto 1.

Esercizio 3: scaricare "alice dal paese delle meraviglie" da Liber Liber, come file txt, scompattate se zippato, e scrivete un programma che riceve come argomento dalla linea di comando il nome del file con dentro alice, e stampa sul terminale un elenco delle parole presenti nel file senza i segni di interpunzione (virgole, punti, etc), non vi preoccupate se i caratteri accentati non sono gestiti correttamente.

Lezione 14

Puntatori

  • Definizione
  • Dichiarazione
  • Utilizzo degli operatori & *
  • Perche i puntatori?
    1. Passaggio dei parametri per riferimento
    2. Aritimetica dei puntatori e vettori (vedi sotto)
    3. Gestione della memoria da parte del programmatore, heap e memoria dinamica (prossimamente)
    4. Passaggio di oggetti di grossa dimensione (strutture) per riferimento per evitare copie (prossimamente).

Puntatori e Vettori

 

Lezione 13

Esercizi Iterazione su vettore:

  • Intervallo di Somma Massima (versione ).
  • Ottimizzazione versione , idea: non calcolare le somme da zero.
  • Ottimizzazione versione lineare. idea: gli estremi dell'intervallo rispettano specifiche relazioni.

Esercizi Ricorsione:

  • Calcolo del Coefficiente Binomiale . Perche la versione con i fattoriali non è ideale.
  • Versione Ricorsiva del Coefficiente Binomiale.
  • Problemi con la ricorsione, valutazioni ripetute della stessa espressione, soluzione:
  • Triangolo di Tartaglia: versione "programmazione dinamica = ricorsione + memorizzazione" della relazione ricorsiva.

Esercizi:

  1. Completare l'esercizio sulla somma massima nel vettore.
  2. Data una matrice dove esiste un indice di colonna tale che se e se , e date le coordinate di un elemento di M, start = $(p,q)$, riempire la sottomatrice composta dagli elementi di M con valore uguale a quello in M[p][q] con il valore 0.
  3. Data una stringa (vettore di caratteri terminato con '\0'), che contiene un espressione composta da parentesi tonde, scrivere una funzione ricorsiva che verifica se tale espressione ha le parentesi bilanciate e se è ben-formata (le parentesi aperte appaiono sempre prima della corrispondente chiusa).

Lezione 12

Algoritmi di Ordinamento cenni introduttivi:

  • Bubble Sort, Shell Sort.
  • Selection Sort: for all i, si seleziona il minimo in [i,N)  e lo si mette in v[i]
  • Insertion Sort: for all i, si estrae (la carta/il valore) v[i] e lo si mette nella sua corretta posizione nel sottovettore v[0..i-1] spostando verso destra fin quando necessario.

Implementazone in C:

#include <stdio.h>
#include <stdlib.h>

#define N 100

void insertion_sort(int v[N], int size)
{
    for (int i=1; i<size; i++)
    {
        int t = v[i];
        int j = i-1;
        while (j>=0 && v[j] > t) { v[j+1] = v[j]; j--; }
        v[j+1] = t;
    }
}

void vprint(int v[N], int size)
{
    for (int i=0; i<size; i++) {
        printf("%2d ",v[i]);
        if ((i+1) % 20 == 0)
            printf("\n");
    }
}

int main(void)
{
    int v[N];
    
    for (int i=0; i<N; i++)
        v[i] = rand() % 30 + 1;
    vprint(v,N);
    insertion_sort(v,N);
    printf("--------------------\n");
    vprint(v,N);
    return 0;
}

Ricorsione:

  • Funzioni Ricorsive, regole di visibilità
  • Funzioni Ricorsive come sostituto all'iterazione (Turing Equivalenza)
  • Ricorsione e Iterazione infinita: necessità del caso base.
  • Alcuni esempi:  fattoriale, fibonacci, mcd, potenza

Esercizi: scrivere tutte le funzioni sopra in modo ricorsivo.

  • Ordinamento Ricorsivo: merge / mergesort

 

Lezione 11

Esercizi su Vettori:

  • Ricerca di un elemento in un vettore, codice della ricerca lineare:
/*
 input: un vettore v di al massimo N elementi
        un intero x
        un intero n <=N.
 output:  k in [0,n) tale che v[k] = x 
         -1 se x non appartiene a v
*/
int linear_search(int v[N], int n, int x)
{
    for (int i=0; i<n; i++)
        if (v[i] == x) return i;
    return -1;
}

Algoritmo di ricerca binaria, o dicotomica (o metodo di bisezione):

/*
 input: un vettore v di al massimo N elementi
        v e' ordinato in modo crescente
        un intero x
        due interi low, hi, con low < hi <=N.
 output:  k in [low,hi) tale che v[k] = x 
         -1 se x non appartiene a v
*/
int binary_search(int v[N], int low, int hi, int x)
{
    if (x < v[low] || x > v[hi]) return -1;
    while (low < hi) {
        int mid = (low + hi)/2;
        // printf("debug: search in [%d,%d,%d)\n",low,mid,hi);
        if (v[mid] == x) return mid;
        else if (x > v[mid]) low = mid+1;
        else if (x < v[mid]) hi = mid;
    }
    return -1;
}