Esercitazione n. 7 - cremona.polimi.it · Esercitazione n. 7 Strutture dati dinamiche: le liste...

Esercitazione n. 7Esercitazione n. 7

Strutture dati Strutture dati dinamiche: le listedinamiche: le liste

Queste slide sono distribuite con licenza Creative Commons Attribuzione-Non commerciale-Condividi allo stesso modo 2.5 Italia

dott. Carlo Todeschini – [email protected] – Politecnico di Milano – A.A. 2010/2011

2 Esercitazioni di Fondamenti di Informatica – Politecnico di Milano sede di Cremona – A.A. 2010/2011 – Carlo Todeschini – [email protected]

C/compito: La torre di Hanoi – Nota

Il libro di testo suggerisce il seguente approccio ricorsivo:

➢ se il numero N di dischi è piccolo (per esempio 1 o 2), il problema è di soluzione immediata

➢ se si è in grado di risolvere il problema per N dischi è possibile risolverlo per N+1 dischi nel modo seguente:➢ si trasferiscono gli N dischi superiori sul piolo libero diverso

da quello su cui si vogliono trasferire tutti gli N+1 dischi applicando ricorsivamente l'algoritmo di soluzione agli N dischi superiori (si ignora il disco più grande...)

➢ si trasferisce il disco più grande sul piolo desiderato ➢ si riportano i dischi rimanenti sopra al disco più grande


C/compito: La torre di Hanoi – Codice sorgente/1

/* Questo programma realizza il gioco della torre di Hanoi (si veda l'apposito esercizio del libro di testo)*/

#include <stdio.h>#define MAX_DISCHI 9typedef unsigned short num_piolo;



typedef struct { int nd; unsigned short dischi[MAX_DISCHI];} piolo;

/* Per rappresentare il gioco si utilizza una variabile globale che mantiene le informazioni sui dischi presenti sui 3 pioli*/piolo gioco[3];



/* Questa funzione mostra graficamente la situazione dei dischi sui 3 pioli. Ogni numero stampato corrisponde alla dimensione del disco presente sul piolo*/void stampa_gioco () { int i, j, max = 0; /* Si calcola il numero massimo di dischi presenti su un piolo. Questo dato è utile perchè i pioli vengono rappresentati verticalmente ed è necessario sapere quale è il numero massimo di dischi presenti su un piolo */ for (i=0 ; i<3 ; i++) { if (gioco[i].nd > max) { max = gioco[i].nd; } }



/* Si stampa riga per riga la situazione dei dischi sui pioli, dall'alto verso il basso */ for (i=1 ; i<=max ; i++) { for (j=0 ; j<3 ; j++) { if (gioco[j].nd > max-i) { printf ("%hd ", gioco[j].dischi[max-i]); } else { printf (" "); } } printf ("\n"); }

printf ("---------\n");}



/* Funzione che aggiorna la situazione dei pioli, quando si sposta un disco da un piolo a un altro: l'ultimo disco presente sul piolo 'da' viene messo SOPRA l'ultimo disco del piolo 'a' (quindi nel primo posto libero dell'array 'dischi' corrispondente al piolo 'a'); il numero di dischi presenti sul piolo 'a' viene dunque incrementato, e il numero di dischi sul piolo 'da' viene decrementato*/void sposta_disco (num_piolo da, num_piolo a) { gioco[a-1].dischi[gioco[a-1].nd] = gioco[da-1].dischi[gioco[da-1].nd-1]; gioco[a-1].nd++; gioco[da-1].nd--;}



/* Si inizializza il gioco, mettendo 'num_dischi' dischi sul primo piolo (quello che nell'array 'gioco' ha indice 0) */void inizializza_gioco (int num_dischi){ int i; gioco[0].nd = num_dischi; gioco[1].nd = 0; gioco[2].nd = 0;

for (i=0 ; i<num_dischi ; i++) { gioco[0].dischi[i] = num_dischi-i; }}



/* Funzione principale (ricorsiva), che realizza l'algoritmo di soluzione del gioco. Ogni volta che un disco singolo viene spostato, la situazione del gioco viene aggiornata chiamando 'sposta_disco', e il grafico rappresentante la situazione dei pioli viene visualizzato.*/void hanoi (num_piolo da, num_piolo a, num_piolo per, int num_dischi) { /* Si suppone che il numero di dischi da spostare sia almeno 1! */ if (num_dischi == 1) { printf ("\nSposta da %hd a %hd:\n", da, a); sposta_disco (da, a); stampa_gioco (); } else { hanoi (da, per, a, num_dischi-1); hanoi (da, a, per, 1); hanoi (per, a, da, num_dischi-1); }}



main(){ int num_dischi;

do { printf ("Inserire il numero di dischi con cui giocare (max %d dischi): ", MAX_DISCHI); scanf ("%d", &num_dischi);

} while (num_dischi<1 || num_dischi>MAX_DISCHI);

inizializza_gioco (num_dischi); printf ("Situazione iniziale:\n"); stampa_gioco ();

hanoi (1, 2, 3, num_dischi);

}


C/compito: La torre di Hanoi – Esecuzione/1tode@linux:/home/tode/esempi> ./es01_hanoiInserire il numero di dischi con cui giocare (max 9 dischi): 3Situazione iniziale:123---------

Sposta da 1 a 2:23 1---------

Sposta da 1 a 3:3 1 2---------

Sposta da 2 a 3: 13 2---------

Sposta da 1 a 2: 1 3 2---------

Sposta da 3 a 1:1 3 2---------

Sposta da 3 a 2: 21 3---------

Sposta da 1 a 2: 1 2 3---------


C/compito: La torre di Hanoi – Esecuzione/grafo

23 1---------

3 1 2---------

13 2---------

1 3 2---------

1 3 2---------

21 3---------

1 2 3---------

H (1, 2, 3, 3)

H (1, 3, 2, 2)

H (1, 2, 3, 1)

H (3, 2, 1, 2)

H (1, 3, 2, 1)

H (1, 2, 3, 1)

H (2, 3, 1, 1)

H (3, 2, 1, 1)

H (3, 1, 2, 1)

H (1, 2, 3, 1)


C/compito: La torre di Hanoi – Esecuzione/2tode@linux:/home/tode/esempi> ./es01_hanoiInserire il numero di dischi con cui giocare (max 9 dischi): 4Situazione iniziale:1234---------

Sposta da 1 a 3:234 1---------

Sposta da 1 a 2:34 2 1---------

Sposta da 3 a 2:3 14 2---------

Sposta da 1 a 3: 14 2 3---------

Sposta da 2 a 1:14 2 3---------

Sposta da 2 a 3:1 24 3---------

Sposta da 1 a 3: 1 24 3---------

Sposta da 1 a 2: 1 2 4 3---------

Sposta da 3 a 2: 1 2 4 3---------

Sposta da 3 a 1: 12 4 3---------

Sposta da 2 a 1:12 4 3---------

Sposta da 3 a 2:1 32 4---------

Sposta da 1 a 3: 32 4 1---------

Sposta da 1 a 2: 2 3 4 1---------

Sposta da 3 a 2: 1 2 3 4---------


C/ripasso: strutture dinamiche /1

Per allocare dinamicamente una zona di memoria

void *malloc ( size_t num );

dove size_t num è la quantità di memoria da allocare; ritorna un puntatore che punta alla memoria allocata; se non è stato possibile riservare la memoria viene ritornato NULL; spesso num viene indicato tramite l'operatore

sizeof (espressione | tipo)

La memoria deve essere deallocata esplicitamente con

void free (void *ptr);

E' necessaria l'inclusione#include <stdlib.h>



Una lista è una successione di elementi omogenei presenti in memoria. Ogni elemento è caratterizzato dal fatto che contiene l'informazione necessaria per accedere al prossimo elemento nella lista, oltre al dato vero e proprio:

elemento = informazione + puntatore

puntatoreALista ...

info punt

...

info punt

...

info

NULL

punt



puntatoreALista

La lista è vuota se puntatoreALista punta a NULL

Struttura per gli elementi dell'esempio:

struct elemento { int info; struct elemento *punt;};

...

info punt

...

info punt

...

info

NULL

punt


C/2: Operazioni con le liste – Problema

Si vuole realizzare un programma in linguaggio C in grado eseguire alcune operazioni sulle liste dinamiche:

➢ inizializzazione di una lista➢ inserimento dei valori nella lista (in testa e in coda)➢ inversione dei valori contenuti nella lista➢ stampa del contenuto di una lista➢ cancellazione di un elemento della lista (esercizio)➢ cancellazione della lista (esercizio)


C/2: Operazioni con le liste – Codice sorgente/1

/* Questo programma ha lo scopo di fare alcune operazioni sulle liste dinamiche:

- Inizializzazione di una lista - Inserimento dei valori nella lista (in testa e in coda) - Inversione dei valori contenuti nella lista - Stampa del contenuto di una lista - Cancellazione di un elemento della lista (esercizio) - Cancellazione della lista (esercizio)*/

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



/* Si definisce la struttura a lista */struct EL { int info; struct EL *next;};typedef struct EL elemLista; // si rinomina il tipo "struct

// EL" come elemListatypedef elemLista *listaDiElem; // si definisce il tipo listaDiElem

// come un puntatore al tipo elemLista// si potranno quindi definire // variabili di tipo "lista" come// listadiElem lista1, lista2;

/* Questa funzione inizializza una lista alla lista vuota. Notare che si passa la lista per indirizzo, perchè deve essere modificata per inizializzarla*/void inizializza (listaDiElem *lista){

*lista = NULL;}


C/2: Operazioni con le liste – Codice sorgente/3/* Funzione che verifica se una lista è vuota oppure no. Si passa la lista per valore, perchè non è necessario modificarla*/bool is_empty (listaDiElem lista){

if (lista == NULL) return true; else return false;}

/* Inserisce il valore 'dato' come primo elemento della lista. Non viene eseguito nessun controllo sull'esistenza o meno del valore aggiunto alla lista*/void inserisciInTesta (listaDiElem *lista , int dato){

elemLista *punt;

punt = malloc (sizeof (elemLista));punt->next = *lista;punt->info = dato;*lista = punt;

}



/* Funzione (ricorsiva) che inserisce il valore 'dato' in ultima posizione nella lista. Anche qui non viene eseguito nessun controllo sull'esistenza o meno del valore aggiunto alla lista*/void inserisciInCoda (listaDiElem *lista , int dato){

elemLista *punt;

if (is_empty (*lista)){

punt = malloc (sizeof (elemLista));punt->next = NULL;punt->info = dato;*lista = punt;

}else inserisciInCoda ( &((*lista)->next) , dato );

}



/* Funzione (ricorsiva) che stampa il contenuto di una lista*/void stampa_lista (listaDiElem lista) {

if (!is_empty(lista)){

printf ("%d -> ", lista->info);stampa_lista (lista->next);

}else printf ("NULL\n");

}


C/2: Operazioni con le liste – Codice sorgente/6/* Funzione (ricorsiva) che inverte il contenuto di una lista*/listaDiElem inverti_lista (elemLista *precedente, elemLista *corrente){

elemLista *prossimo_nodo;

// Se la lista è vuota non va invertita...if (corrente == NULL) return NULL;// metto da parte il puntatore al prossimo nodo della listaprossimo_nodo = corrente->next;// il nodo attuale va "girato", ovvero va fatto puntare al nodo // precedentecorrente->next = precedente;// controllo se sono arrivato alla fine delle listaif (prossimo_nodo == NULL)

// si, sono alla fine per cui l'elemento corrente è // l'elemento iniziale della lista invertitareturn (corrente);

else// non sono alla fine per cui invoco ricorsivamente la // funzione per invertire il prossimo nodoreturn (inverti_lista (corrente, prossimo_nodo));

}



// A -> b -> c -> d -> e -> NULL (situazione iniziale)

// NULL <- a B -> c -> d -> e -> NULL

// NULL <- a <- b C -> d -> e -> NULL

// NULL <- a <- b <- c D -> e -> NULL

// NULL <- a <- b <- c <- d E -> NULL

// NULL <- a <- b <- c <- d <- e (situazione finale)


C/2: Operazioni con le liste – Codice sorgente/7main (){

listaDiElem miaLista;bool uscita = false;int scelta, dato;

inizializza (&miaLista);

while (!uscita){

// Stampa menuprintf ("\n-------------------------------------------\n");printf ("1. Visualizza elementi della lista\n");printf ("2. Inserisci elemento in testa alla lista\n");printf ("3. Inserisci elemento in coda alla lista\n");printf ("4. Inverti elementi della lista\n");printf ("5. Cancella un elemento della lista\n");printf ("6. Elimina lista\n");printf ("0. Esci dal programma\n");printf ("\nScelta: ");scanf ("%d", &scelta);



switch (scelta){

case 1: // Visualizza elementi della listaprintf ("\nStampa della lista:\n");stampa_lista (miaLista);

break;case 2: // Inserisci elemento in testa alla lista

printf ("Inserire elemento (numero intero): ");scanf ("%d", &dato);inserisciInTesta (&miaLista, dato);

break;case 3: // Inserisci elemento in coda alla lista

printf ("Inserire elemento (numero intero): ");scanf ("%d", &dato);inserisciInCoda (&miaLista, dato);

break;case 4: // Inverti elementi della lista

printf ("\nInversione elementi della lista...\n");miaLista = inverti_lista (&miaLista, NULL);

break;



case 5: // Cancella un elemento della lista// da fare per esercizio...// chiedere all'utente quale elemento si desidera// cancellare...

break;case 6: // Elimina lista

// da fare per esercizio...break;case 0: // Esci dal programma

printf ("Uscita...\n");uscita = true;

break;default:

printf ("Opzione non riconosciuta...\n");break;

}}

}


C/3: Archivio a liste – Problema

Si vuole realizzare un programma in linguaggio C in grado di gestire un archivio di contatti realizzato tramite una struttura dati a lista.

Ogni contatto è definito da:➢ nome della persona➢ indirizzo➢ numero di telefono

Le operazioni possibili su questo archivio sono:➢ inizializzazione dell'archivio ➢ verifica se l'archivio è vuoto➢ inserimento ordinato di una nuova voce nell'archivio (secondo il nome

del contatto)➢ cancellazione di una voce dell'archivio➢ stampa degli elementi presenti nell'archivio


C/3: Archivio a liste – Codice sorgente/1

/* Questo programma gestisce un archivio di contatti realizzato tramite una struttura dati a lista.

Ogni contatto è definito da: - nome della persona - indirizzo - numero di telefono

Le operazioni possibili su questo archivio sono: - inizializzazione dell'archivio - verifica se l'archivio è vuoto - inserimento ordinato di una nuova voce nell'archivio (secondo il nome del contatto) - cancellazione di una voce dell'archivio - stampa degli elementi presenti nell'archivio*/

Nota: integrazioni da svolgere per esercizio



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

#include "userTypes.h"

#define MAX_L_NOME 50#define MAX_L_INDIR 70#define MAX_L_NUM_TEL 15

/* La dimensione degli array è aumentata di una unità rispetto alla lunghezza massima di nome, indirizzo e numero telefonico per fare spazio al carattere speciale '\000', utile alla libreria "string" per sapere dove finisce la stringa di caratteri*/typedef struct { char nome [MAX_L_NOME+1]; char indir [MAX_L_INDIR+1]; char n_tel [MAX_L_NUM_TEL+1];} ElementoArchivio;



/* Si definisce la struttura a lista */struct EL { ElementoArchivio e; struct EL *next;};typedef struct EL ElemLista; // si rinomina il tipo "struct

// EL" come ElemListatypedef ElemLista *ArchivioALista;

// si definisce il tipo ArchivioALista // come un puntatore al tipo ElemLista// si potranno quindi definire // variabili di tipo "lista" come// ArchivioALista lista1, lista2;



/* Questa funzione inizializza una lista alla lista vuota. Notare che si passa la lista per indirizzo, perchè deve essere modificata per inizializzarla*/void init_arch (ArchivioALista *arch) { *arch = NULL;}

/* Funzione che verifica se una lista è vuota oppure no. Si passa la lista per valore, perchè non è necessario modificarla*/bool is_empty (ArchivioALista arch) { if (arch == NULL) return true; else return false;}



/* Funzione che restituisce la testa di una lista e ritorna 2 parametri: il valore dell'elemento (se la lista non è vuota), e un valore di tipo bool che indica se l'operazione è riuscita oppure no. Essendo i parametri in uscita 2, uno viene restituito, l'altro viene passato per indirizzo, perchè deve poter essere caricato con il valore necessario.*/bool head (ArchivioALista arch, ElementoArchivio *testa) { /* Se la lista è vuota si ritorna "false" senza modificare il parametro "testa" */ if (is_empty(arch)) return false;

*testa = arch->e; return true;}


C/3: Archivio a liste – Codice sorgente/6/* Si noti come in questo caso sia stata passata la lista per valore e non per indirizzo, perchè non deve essere modificata.

Si faccia attenzione, perchè nel caso delle lista il discorso "passaggio per valore/passaggio per indirizzo" si fa molto labile...

In realtà quello che si passa per valore in questo caso è solo il PUNTATORE al primo elemento della lista. Notare che COMUNQUE SI PASSA UN PUNTATORE! La differenza tra il caso precedente in "init_arch" e questo è che prima si passava un PUNTATORE DI PUNTATORE, in questo caso un puntatore semplice, ma sempre di puntatore si tratta. In realtà si potrebbe modificare la lista, perchè una lista non viene mai realmente passata "per valore". Si potrebbe per esempio andare a modificare il contenuto del primo elemento della lista, perchè "arch" contiene proprio un puntatore ad esso. E poichè nel primo elemento di una lista è contenuto il PUNTATORE al secondo elemento della lista (nel campo "next" in questo caso), si potrebbe anche andare a modificare il contenuto del secondo elemento, e così via.

Attenzione quindi quando si lavora con le liste! Se non si pone la dovuta attenzione nella gestione dei puntatori si rischia di ottenere effetti indesiderati!*/



/* Questa funzione restituisce una LISTA che corrisponde alla lista passata in input meno il primo elemento. Se la lista passata in ingresso è vuota viene ritornato "false", altrimenti "true". Ancora una volta si devono ritornare 2 parametri, quindi è necessario ricorrere al passaggio di parametri per indirizzo. In questo caso si passa per indirizzo la lista nella quale verrà memorizzata la coda.*/bool tail (ArchivioALista arch, ArchivioALista *coda) { /* Se la lista è vuota si ritorna "false" senza andare a modificare il parametro "coda" */ if (is_empty(arch)) return false;

*coda = arch->next; return true;



/* Notare come in realtà non si esegua una copia della lista "arch", ma ci si limiti a restituire il puntatore al secondo elemento della lista. Questo significa che alla fine di questa funzione tramite "arch" e "(*coda)" si può accedere agli STESSI elementi! Ancora una volta, occorre fare molta attenzione nella gestione delle liste altrimenti si rischia di incappare in effetti collaterali difficili anche da riconoscere. */}



/* Questa funzione inserisce una nuova voce in un archivio, seguendo l'ordine alfabetico dei nomi, purchè non esista già nell'archivio un elemento associato allo stesso nome. La funzione ritorna "true" se l'inserimento viene effettuato con successo, altrimenti "false".

Questa è una funzione ricorsiva, con i seguenti passi:

Passo base: se la lista è vuota o se il primo elemento della lista è MAGGIORE di quello da inserire (il campo "nome" del primo elemento della lista precede il campo "nome" del nuovo contatto da inserire in ordine lessicografico) si inserisce il nuovo contatto come primo elemento della lista; se il primo elemento della lista ha lo stesso nome del nuovo elemento, non si modifica la lista e si ritorna "false".

Passo ricorsivo: se il nuovo contatto viene dopo il primo elemento della lista, lo si inserisce nella sottolista che inizia dal secondo elemento della lista.*/



bool inser_per_nome (ArchivioALista *arch, ElementoArchivio el) { ElemLista *pt_new_el;

/* Passo base (1) */ if (is_empty (*arch)) { /* La funzione "malloc" alloca in memoria una quantità di celle specificata dal suo argomento, e restituisce l'indirizzo della prima di queste celle. "sizeof(arg)" corrisponde al numero di celle occupate dal tipo passatole come parametro. */ pt_new_el = malloc (sizeof (ElemLista)); pt_new_el->e = el; pt_new_el->next = NULL; *arch = pt_new_el; return true; }



/* Passo base (2). Se già esiste nell'archivio una voce associata allo stesso nome, la funzione ritorna "false" senza fare nulla. "strcmp" è una funzione della libreria "string", la quale prende in ingresso due array di caratteri (la cui fine DEVE essere segnalata tramite il carattere '\000'), e restituisce 0 se il contenuto dei due array è uguale, un valore <0 se il primo array precede il secondo in ordine lessicografico (che è l'ordinamento usato per le stringhe), ed uno >0 se è il secondo a precedere il primo. */

if (strcmp ((*arch)->e.nome, el.nome) == 0) { return false; }



/* Passo base (3). Se il primo elemento nell'archivio è maggiore di quello da inserire, il nuovo elemento viene inserito al primo posto */ if (strcmp ((*arch)->e.nome, el.nome) > 0) { pt_new_el = malloc (sizeof (ElemLista)); pt_new_el->e = el; /* Questa volta il nuovo elemento deve puntare, nel campo "next", al prossimo elemento della nuova lista, che è il primo della vecchia */ pt_new_el->next = *arch;

/* L'istruzione che segue garantisce che l'elemento della lista da cui si era partiti punti ora al nuovo elemento inserito, garantendo continuità alla lista stessa */ *arch = pt_new_el;

return true;

}



else { /* Passo ricorsivo. Nel caso in cui il primo elemento è minore di quello da inserire, si chiama ricorsivamente la funzione sulla parte di lista che inizia dal secondo elemento */ return inser_per_nome (&((*arch)->next), el); }}



/* Questa funzione prende in input il nome associato ad una voce dell'archivio da cancellare e l'archivio stesso, e cancella la voce (se esiste). Se l'operazione di cancellazione ha successo, la funzione ritorna "true", altrimenti "false". Si noti che l'archivio viene passato per indirizzo, perchè deve essere modificato se la voce da cancellare viene trovata.

La funzione utilizza un algoritmo RICORSIVO per la cancellazione: se la lista è vuota, non è stato trovato l'elemento da cancellare e si ritorna "false"; se l'elemento da cancellare è il primo della lista, viene tolto dalla lista, altrimenti si effettua l'operazione di cancellazione sulla sottolista che comincia dal secondo elemento.*/



bool canc_voce (ArchivioALista *arch, char *nome) { ElemLista *temp;

if (is_empty(*arch)) { return false; }


C/3: Archivio a liste – Codice sorgente/16 if (strcmp ((*arch)->e.nome, nome) == 0) { temp = (*arch)->next; free (*arch); *arch = temp; /* L'istruzione "free" è fondamentale, oppure si avrà il problema del "garbage" (spazzatura), cioè celle di memoria a cui nessuno fa più riferimento e che rimangono occupate.

Si consiglia comunque di fare attenzione nell'utilizzo della "free", perchè si rischia il problema duale del "garbage", ovvero le "dangling references" (riferimenti penzolanti). Infatti, è possibile che a una cella di memoria allocata con una "malloc" puntino più puntatori, non uno solo. Se si esegue una "free" di memoria quando ci sono ancora puntatori che puntano a quella memoria, questi puntatori dopo la "free" punteranno a della memoria non più allocata (si dice per semplicità che non puntano più a nulla di valido), creando così delle "dangling reference". */ return true;



} else { return canc_voce (&((*arch)->next), nome); /* Chiamata ricorsiva della funzione "canc_voce": se l'elemento da cancellare non è il primo nella lista, si effettua l'operazione di cancellazione sulla sottolista che comincia a partire dal prossimo elemento nella lista (che si provvede a passare per indirizzo con la '&') */ }}



/* Funzione (ricorsiva) che stampa il contenuto di una lista */void stampa_arch (ArchivioALista arch) { if (!is_empty(arch)) { printf ("\nNome: %s\n", arch->e.nome); printf ("Indirizzo: %s\n", arch->e.indir); printf ("N. Telefono: %s\n", arch->e.n_tel);

stampa_arch (arch->next); }}



/* Questa funzione legge da input i dati relativi a una voce dell'archivio e ritorna una struttura opportunamente inizializzata. Se l'utente non inserisce un nome valido, la funzione ritorna "false", altrimenti "true"*/bool leggi_dati_voce (ElementoArchivio *el) { ElementoArchivio new_voce;

printf ("Inserire nome (max %d caratteri, <ENTER> per terminare): ", MAX_L_NOME); gets (new_voce.nome);

/* Invece della funzione "scanf" per leggere una stringa di caratteri da standard input si utilizza la funzione "gets". Questo perchè la "scanf" non permette di avere spazi all'interno della stringa, mentre la "gets" sì. La segnatura della "gets" è: char *gets(char *)

Si noti che comunque non interessa mantenere il puntatore che viene restituito, e quindi è possibile ignorarlo senza assegnarlo ad alcuna variabile */



/* Se l'utente come nome ha inserito la stringa vuota si esce dalla funzione ritornando "false". La stringa vuota può essere rappresentata con una coppia di doppie virgolette: "" */ if (strcmp (new_voce.nome, "") == 0) { return false; }

printf ("Inserire indirizzo (max %d caratteri): ", MAX_L_INDIR); gets (new_voce.indir); printf ("Inserire num. telefonico (max %d caratteri): ", MAX_L_NUM_TEL); gets (new_voce.n_tel);

*el = new_voce; return true;}



main() { ElementoArchivio el; ArchivioALista arch, coda; char nome_da_canc[MAX_L_NOME]; char c; bool fine;

init_arch (&arch); while (leggi_dati_voce (&el)) { inser_per_nome (&arch, el); /* Notare come la funzione "inser_per_nome" restituisca un valore "bool" che però non interessa, quindi viene ignorato senza assegnarlo ad una variabile (comportamento perfettamente lecito) */ printf ("\n"); }



printf ("Contenuto archivio:\n"); stampa_arch (arch); printf ("**********************\n");

if (head (arch, &el)) { printf ("\nNome prima voce: %s\n", el.nome); }

printf ("**********************\n"); if (tail (arch, &coda)) { printf ("\nContenuto coda:\n"); stampa_arch (coda); }



printf ("**********************\n"); printf ("\nNome elemento da cancellare: "); gets (nome_da_canc); canc_voce (&arch, nome_da_canc);

printf ("Nuovo contenuto archivio:\n"); stampa_arch (arch); printf ("**********************\n");

printf ("Nuovo contenuto coda:\n"); stampa_arch (coda); printf ("**********************\n");



/* Notare che se l'elemento che è stato cancellato non è il primo nella lista (cioè appartiene anche alla "coda"), con l'operazione di "canc_voce" si va a modificare il contenuto sia della lista "arch" che della lista "coda"! Questo perchè in realtà gli elementi della lista "coda" sono anche comuni alla lista "arch", per cui se ne viene modificato (o cancellato) uno in "arch" (purchè non sia il primo), la modifica si ripercuote sulla lista "coda".

Notare ancora che se l'elemento da cancellare è il SECONDO di "arch" (cioè la testa della lista "coda"), la "free" che viene effettuata da "canc_voce" libera la memoria a cui punta "coda", la quale, dopo la "canc_voce", punta nel vuoto (dangling reference), e il comportamento del programma può risultare imprevedibile. */

}



/* Funzione che prende un archivio passatole come argomento, e ne scarica i contenuti in un file (binario) il cui nome le è passato come secondo argomento. La funzione in sè non è ricorsiva, si limita ad aprire (e chiudere) il file binario, e si appoggia a un'altra funzione (questa ricorsiva), che prende un archivio e il descrittore di un file già aperto, e scrive i contenuti dell'archivio nel file.*/bool scarica_arch (ArchivioALista arch, char nome_file[]) { FILE *file_arch;

bool scarica_lista_in_file (ArchivioALista a, FILE *f);

Nota: inizio delle funzioni da integrare nel programma per esercizio



file_arch = fopen (nome_file, "wb"); if (file_arch == NULL) { return false; } else { if (scarica_lista_in_file (arch, file_arch)) { fclose (file_arch); return true; } else { fclose (file_arch); return false; } }}



/* Funzione ricorsiva che prende una archivio implementato a lista, il descrittore di un file (che deve essere già aperto), scrive il primo elemento della lista, quindi si invoca ricorsivamente sulla sottolista che inizia dal secondo elemento. */bool scarica_lista_in_file (ArchivioALista a, FILE *f) { if (f == NULL) { return false; } else if (a == NULL) { return true; } else { if (fwrite(&(a->e), sizeof (ElementoArchivio), 1, f)) { return scarica_lista_in_file (a->next, f); } else { return false; } }}


C/3: Archivio a liste – Codice sorgente/28/* Funzione che crea un archivio, leggendone i contenuti da un file (binario), tipicamente uno creato dalla funzione precedente */bool carica_da_file (ArchivioALista *a, char nome_file[]){ FILE *f; ElementoArchivio e;

f = fopen (nome_file, "rb"); if (f == NULL) { return false; }

init_arch (a);

while (fread (&e, sizeof (ElementoArchivio), 1, f) == 1) { inser_per_nome (a, e); } if (feof(f)) { fclose (f); return true; } else { fclose (f); return false; }}


C/approfondimento: parametri a linea di comando

E' possibile passare dei parametri al momento del lancio di un programma, a linea di comando:

tode@benfuter:~$ programma_eseguibile par_1 par_2 par_3

questi vengono gestiti tramite i parametri passati al main:

int argc = contiene il numero di parametri passati, nome del programma compreso (nell'esempio argc = 4)

char *argv[] = array di puntatori a char che puntano alle stringhe dei parametri passati

argv

programma_eseguibile

par_1

par_2

par_3


C/4: cerca in file /1

/* Questo programma riceve due parametri in input da linea di comando.

In particolare riceve il path assoluto di un file di testo da caricare e una parola da ricercare all'interno del file. Il programma stampa a STDOUT le righe in cui la parola è stata trovata e il relativo numero di riga.

*/

#include <stdio.h>#include <string.h>#include "userTypes.h"

#define MAX_LUNGH_RIGA 1024

void elimina_newline (char *str);



main ( int argc , char *argv[] ){

FILE *file_da_controllare;int contatore_righe;char riga_da_controllare[MAX_LUNGH_RIGA+2];

if ( argc == 3 ){

printf ( "File da caricare: %s\n" , argv[1] );printf ( "Parola da cercare: %s\n" , argv[2] );/* Si tenga presente che i parametri sono sempre considerati delle stringhe (anche se l'utente intende passare un numero...)

*/



/* Si cerca di aprire in sola lettura il file da analizzare */file_da_controllare = fopen ( argv[1] , "r" );if ( file_da_controllare != NULL ){

/* Ok: il file è stato aperto e quindi se ne legge riga per riga il contenuto alla ricerca della parola */contatore_righe = 1;while ( ! feof ( file_da_controllare ) ){

/* Si legge una riga dal file sorgente */if ( fgets ( riga_da_controllare , MAX_LUNGH_RIGA+1 ,

file_da_controllare ) != NULL ){

/* Si toglie l'eventuale '\n' alla fine della riga */elimina_newline ( riga_da_controllare );



/* Si controlla se l'argomento passato a linea di comando è contenuto almeno una volta nella riga letta utilizzando la funzione di libreria strstr: char *strstr (const char *full_string,

const char *sub_string);*/if ( strstr ( riga_da_controllare , argv[2] ) != NULL ){

/* La stringa è stata trovata! */printf ( "R: %5d | %s\n" , contatore_righe ,

riga_da_controllare );}else{

/* Stringa non trovata... */printf ( "R: %5d | STRINGA NON TROVATA\n" ,

contatore_righe );}contatore_righe++;

}}

}


C/4: cerca in file /5else{

/* Errore: impossibile aprire il file di input */printf ("\nSi è verificato un errore durante l'apertura del

file \"%s\"\n\n" , argv[1] );}

}else{

/* Errore: parametri di input errati */printf ( "\nUtilizzo: %s path_assoluto_del_file parola_da_cercare\n\n"

, argv[0] );}

}

/* Funzione utile per togliere il carattere di 'a capo' da una stringa */void elimina_newline ( char *str ){

int lstr = strlen (str);

if (str[lstr-1] == '\n')str[lstr-1] = '\000';

}


C/domanda: è tutto qui?

Programma

CLI

UI

GUI

CGI(Internet...)


C on-line: CGI-BIN

Pagina scritta in linguaggio HTML: contiene una form che invoca una programma CGI remoto

Il programma CGI remoto (scritto in C) riceve i dati dalla pagina precedente ed elabora una risposta (a sua volta una pagina HTML, creata “al volo”)

Esercitazione n. 7 - cremona.polimi.it · Esercitazione n. 7 Strutture dati dinamiche: le liste...

Documents

Transcript of Esercitazione n. 7 - cremona.polimi.it · Esercitazione n. 7 Strutture dati dinamiche: le liste...