ESERCITAZIONI di Programmazione II, n. 1 § Ricorsione su vettori, stringhe e liste semplici. Nota Bene: nei programmi qui sotto si è prediletta la chiarezza all'eleganza. (A) semplici ricorsioni su stringhe __________________________________ i) Stampa al contrario una serie di parole /* una funzione che legge n parole dallo std input e le stampa sullo std output in ordine inverso */ void invertiFrase( int n ){ char parola[SIZE]; if (n <= 1){ scanf("%s", parola); printf("%s ", parola); } else{ scanf("%s", parola); invertiFrase(n-1); printf("%s ", parola); } } ii) Trova e stampa le maiuscole in una stringa /* una funzione che riceve una stringa e produce la stringa contenente le maiuscole della stringa data in ordine di occorrenza */ char * trovaMaiuscole( char *maiuscole, const char *stringa){ char tempMaiuscole[SIZE]; if (stringa[0]=='\0') maiuscole[0] = '\0'; else if (isupper(stringa[0])) sprintf(maiuscole, "%c%s", stringa[0], trovaMaiuscole(tempMaiuscole, &stringa[1])); else trovaMaiuscole(maiuscole, &stringa[1]); return maiuscole; } iii) Conta le occorrenze di un carattere in una stringa. /* una funzione che prende in input un carattere e una stringa e conta il numero di occorrenze del carattere nella stringa */ int contaOccorrenze(char k, const char *stringa){ int risultato; if (stringa[0]== '\0') risultato = 0; else if (k == stringa[0]) risultato = 1 + contaOccorrenze(k, &stringa[1]); else risultato = contaOccorrenze(k, &stringa[1]); reutrn risultato; } iv) Decide se una stringa è palindroma. /* una funzione che prende in input una stringa e la sua dimensione e decide se la stringa è palindroma o no */ int Palind(char *stringa, int n){ if (n <= 1) return 1; if (stringa[0]==stringa[n-1]) return Palind(&stringa[1], n-2); else return 0; } (B) Insiemi con stringhe. ________________________ Implementiamo le relazioni e operazioni insiemistiche di base usando le stringhe. Ci limitiamo ad insiemi di caratteri, che rappresentiamo come stringhe di caratteri senza ripetizioni. Definiamo procedure di decisione per le seguenti relazioni: - S è l'insieme vuoto? - a appartiene a S? - S è un sottinsieme di T? Definiamo funzioni per le seguenti operazioni insiemistiche: - Unione: A *unione* B è l'insieme degli elementi che stanno in A o in B - Intersezione: A *intersezione* B è l'insieme degli elementi che stanno in A e in B - Differenza: A *meno* B è l'insieme egli elementi che stanno in A e non stanno in B i) Insieme Vuoto: un insieme è vuoto se l'unico carattere che contiene è \0. int Vuoto(const char *insieme){ return (!insieme)} ii) Appartenenza: il carattere x è elemento dell'insieme S? Una specifica ricorsive della seguente relazione è come segue. Base: S è vuoto --> NO Passo: S non vuoto. Caso 1: x è il primo elemento di S --> YES Caso 2: x non è il primo elemento di S --> (x appartiene a S-{primo elemento})? int Appartiene(char elt, const char *ins){ if (Vuoto(ins)) return 0; else if (ins[0]==elt) return 1; else return Appartiene(elt, &ins[1]); } iii) Insieme: un insieme è una lista senza ripetizioni. Base: S è vuoto --> YES Passo: S non vuoto. Caso 1: il primo elemento di S appartiene anche a S-{primo elemento di S} --> NO Caso 2: --> YES int Insieme(const char *ins){ if (Vuoto(ins)) return 1; else if (Appartiene(ins[0], &ins[1])) return 0; else return 1; } iv) Sottinsieme: A è un sottinsieme di B se (per ogni a)[a apprtiene ad A --> a apprtiene a B]. Base: A è vuoto --> YES Passo: A non vuoto. Caso 1: il primo elemento di A non appartiene a B --> NO Caso 2: il primo elemento di A appartiene a B --> (A-{primo elemento di A} è sottinsieme di B)? int Sott(const char *insA, const char *insB){ if (Vuoto(insA)) return 1; else if (Appartiene(insA[0],insB)) return Sott(&insA[1], insB); else return 0; } v) Unione: l'insieme unione di due insiemi A e B è denotato con A U B e definito come l'unico insieme che contiene tutti e soli gli elementi che stanno in A o in B. char *Un(char *risultato, const char *setA, const char *setB){ char temp[SIZE]; if (Vuoto(setA)){ strcpy(risultato,setB); } else if (App(setA[0],setB)){ Un(risultato, &setA[1], setB); } else{ sprintf(risultato,"%c%s", setA[0], Un(temp,&setA[1],setB)); } return risultato; } vi) Intersezione: esercizio. vii) Differenza: esercizio. (C) Ricorsione su Liste. _______________________ --- C1) Liste Ordinate: consideriamo il caso speciale delle liste ordinate, i.e. delle liste i cui elementi sono interi ordinati in ordine strettamente crescente (dunque senza ripetizioni). i) Inserimento in una lista ordinata: una funzione che prende in input una lista ordinata L e un intero k e restituisce la lista ordinata ottenuta inserendo k in L (rispettando l'ordine). lista *InsInOrd(lista *L, int k){ lista *L_out; if (L == NULL){ L_out=(lista *)malloc(sizeof(lista)); L_out->dato = k; L_out->nxt = NULL; } else if (L->info >= k){ L_out=(lista *)malloc(sizeof(lista)); L_out->dato = k; L_out->nxt = L; } else { L_out = L; L_out->nxt = InsInOrd(L->nxt,k); } return L_out; } ii) Cancellare un elemento k da una lista ordinata L. lista *CancInOrd(lista *L, int k){ lista *temp, *L_out; if (L==NULL){ L_out=NULL; } else if (L->dato==k){ temp = L; L_out = L->nxt; free(temp); } else if (L->dato > k){ L_out = L; } else { L_out = L; L_out->nxt=CancInOrd(L->nxt,k); } return L_out; } iii) Fondere due liste ordinate: prende due liste ordinate e ritorna la lista composta dagli elementi di L1 e dagli elementi di L2 in ordine. lista *fondi(lista *L1, lista *L2){ lista *L; if ((L1 == NULL) && (L2 == NULL)){ L = NULL;} else if (L1 == NULL){ L = L2; } else if (L2 == NULL){ L = L1; } else if (L1->dato < L2->dato){ lista *L = (lista *)malloc(sizeof(lista)); L->dato = L_1->dato; L->nxt = fondi(L_1->nxt,L2); } else if (L1->dato > L2->dato){ lista *L = (lista *)malloc(sizeof(lista)); L->dato = L2->dato; L->nxt = fondi(L1,L2->nxt); } else { lista *L = (lista *)malloc(sizeof(lista)); L->dato = L1->dato; L->nxt = fondi(L1->nxt,L2->nxt); } return L; } iv) Intersezione di liste ordinate. lista *IntOrd(lista *L1, lista *L2){ lista *L; if ((L1==NULL)||(L2==NULL)){ return NULL;} else if (L1->dato < L2->dato){ return IntOrd(L1->nxt,L2); } else if (L1->dato > L2->dato){ return IntOrd(L1,L2->nxt); } else{ L = (lista *)malloc(sizeof(lista)); L->dato = L1->dato; L->nxt = IntOrd(L1->nxt,L2->nxt); return L; } } v) Differenza di liste ordinate. lista *DiffOrd(lista *L1, lista *L2){ lista *L; if (L1==NULL){ return NULL;} else if ((L2==NULL)||(L1->dato < L2->dato)){ L = (lista *)malloc(sizeof(lista)); L->dato = L1->dato; L->nxt = DiffOrd(L1->nxt,L2); return L; } else if (L1->dato > L2->dato){ return DiffOrd(L1, L2->nxt); } else{ return DiffOrd(L1->nxt,L2->nxt);} } --- C2) Relazioni tra liste non ordinate. i) Prefisso: una lista L1 è un prefisso di una lista L2 se (usando la notazione dei linguaggi formali) vale L2 = L1*. Scriviamo una funzione che decide la relazione di prefisso. int prefisso(lista *L1, lista *L2){ if (L1 == NULL) return 1; else if (L2 == NULL) return 0; else if (L->dato==L2->dato){ return prefisso(L1->nxt,L2->nxt); } else return 0; } ii) Sottostringa: una lista L1 con elementi (a1, ..., am) è una sottostringa di una lista L2 con elementi (b1, ..., bn) se e soltanto se esistono indici i_1 < ... < i_m in {1, ..., n} tali che a1 = bi_1, a2 = bi_2, ..., am = bi_m. Scriviamo una funzione che decide la relazione di sottostringa. Per convenzione diciamo che la stringa vuota è sottostringa di qualunque stringa. int sottostringa(lista *L1, lista *L2){ if (L1 == NULL) return 1; else if (L2 == NULL) return 0; return ((L1->dato==L2->dato)&& sottostringa(L1->nxt,L2->nxt)) || sottostringa(L1,L2->nxt); } iii) Suffisso: una lista L1 è un suffisso di una lista L2 se e soltanto se L2 = *L1. Scriviamo una funzione che decide la relazione di suffisso. Usiamo una funzione ausiliaria con una variabile ausiliaria. int postfisso(lista *L1, lista *L2){ return postfisso_aux(L1, L2, L1); } int postfisso_aux(lista *L1, lista *L2, lista *L){ if ((L==NULL) && (L2 == NULL)) return 1; if ((L==NULL) || (L2 == NULL)) return 0; return ((L->dato == L2->dato) &&(postfisso_aux(L1, L2->next, L->next))) || postfisso_aux(L1, L2->next, L1); } iv) Infisso: una lista L1 è un infisso di una lista L2 se e soltanto se L2 = *L1*. Scrivere una funzione ricorsiva che decide la relazione infisso. Esercizio. v) Ordinamento lessicografico. L'ordinamento lessicografico LEX tra due liste di stessa lunghezza L1 = a1, ..., an e L2 = b1,..., bn, è definito come segue: L1 <_LEX L2 se e soltanto esiste un indice i <= n tale che ai < bi. Scrivere una funzione ricorsiva che decide LEX. Esercizio.