Appunti di Informatica

Si trovano facilmente esempi di frasi palindrome (anche se spesso il signicato delle frasi stesse fa capire

come siano state scritte solo per il gusto di trovare una stringa che soddisfasse la caratteristica), e con questo

programma si potrà vericare una qualsiasi stringa.

Idea per lo svolgimento i j

Si acquisisce la stringa. Nota la sua lunghezza, con due variabili e che scorrono in sensi inversi la parola

(una parte da sinistra, l'altra da destra) si verica l'uguaglianza tra i vari caratteri.

Codice

# include <stdio.h>

# include <string.h>

int main()

{ 10

char stringa[N+1];

int i, j;

int l,ok=0;

/* Acquisizione stringhe (va scritto un printf altrimenti quando si fa girare il programma

non si capisce cosa si deve fare) */

gets(stringa);

l=strlen(stringa);

for(i=0, j=l; stringa[i]!='\0' && !ok; i++, j--)

if (stringa[i]!=stringa[j])

ok=1;

if (ok)

printf(\n Non sono palindrome. \n);

}

Errori comuni

Questo problema è parente stretto di quello sugli anagrammi anche nella tipologia di errori: pressochè nessuno.

Lo scoglio risiede, ancora una volta, nell'impostazione dell'esercizio.

Gestione di le

In questa sezione non si risolveranno veri e propri esercizi, perchè i meccanismi per la risoluzione sono gli

stessi visti nora. L'unica dierenza è la presenza di uno o più le da gestire: le richieste sono, generalmente,

l'acquisizione di dati dal le e la scrittura di dati su un altro le.

Ci si soermerà più (con esempi di codice per capire il linguaggio che sta dietro alla gestione dei le) su

come manipolare un le, e non su come risolvere l'esercizio: se viene chiesto di acquisire un array da le e poi

trovarne il massimo, la dicoltà - una volta vista l'acquisizione da le - sta nel trovare il massimo dell'array.

Che però è un problema che è già stato arontato nell'apposita sezione.

Istruzioni per l'uso

Quando si manipola un le, ci sono poche regole, ma è bene averle tutte ben chiare:

FILE *fp

• Il le è identicato da un puntatore del tipo . Va sempre dichiarato quando si gestiscono le.

• Bisogna vericare se il le può essere aperto o se ci sono errori (ad esempio, il le in questione non

esiste). Per far questo si scrive la riga

if(fp=fopen(nomefile,?))

? r w

dove a si sostituisce se il le va aperto in modalità di lettura (per acquisire dati) o se si vuole

entrare in modalità scrittura (per salvare dati su le). fclose(fp)

• Dopo averlo aperto (se ci si è riusciti), bisogna sempre chiudere il le mediante . E non

è una questione di buona educazione: se non si chiude il le, i dati in esso presenti possono essere

sovrascritti, con conseguenze facilmente immaginabili.

• A proposito di sovrascrittura, sarebbe utile vericare che un le aperto in scrittura non esista già o che

sia vuoto, altrimenti si perderanno tutte le informazioni precedentemente contenute.

fprintf fscanf

• Per scrivere su le o acquisire dati si usano le funzioni e . Si comportano esattamente

le pointer

printf scanf

come e , con l'unica eccezione che va dichiarato il su cui si opera.

Ad esempio:

fprintf(fp,Hello world!); 11

• Quando non è noto a priori il numero di elementi da acquisire da le (guarda caso è una situazione che si

while

verica spesso), si usa un ciclo in cui la condizione di uscita è rappresentata dal raggiungimento

feof

della ne del le, identicabile dalla funzione (found end of le). La sintassi sarà:

while (!(feof(fp)))

Typedef e struct

Le typedef sono un'arma potentissima nelle mani dei programmatori: permettono infatti di denire nuovi

int char float

tipi, oltre ai tipi base , , , per costruire strutture dati più complesse.

typedef

Anche nel caso di esercizi con si arontano gli stessi problemi già visti con strutture più semplici.

Tuttavia, a dierenza di quanto accade con i le, i problemi sono più articolati perchè spesso si deve risalire

typedef

ad un campo interno alla (ad esempio, si vuole risalire al nome di uno Studente e questi è denito

da Nome, Cognome, NumeroMatricola).

La nozione fondamentale: accedere ad un campo in una typedef

typedef .

Per accedere ad un campo interno ad una si usa l'operatore (punto), come di seguito presentato:

/* Definita la seguente typedef: */

typedef struct Studente

{

char nome[30];

char cognome[30];

int matricola;

} Studente;

/* Data una variabile di tipo Studente */

Studente stud;

/* Per accedere al numero di matricola dello studente si scrive: */

stud.matricola;

typedef

Molto spesso le deniscono degli array. Ad esempio, nel nostro caso potrebbe trattarsi di una

classe di 30 studenti, e avremmo semplicemente

Studente stud[30];

e dovremo comportarci come se stessimo lavorando con un array normale.

Esercizi con strutture dati

Liste

Le liste sono lo strumento per eccellenza nella programmazione in C, e si dice che si arrivi a comprenderle

dopo una lunga meditazione, necessaria a causa della loro natura sfuggente. Meditazione a parte, le liste

sono davvero un valido strumento: è però necessario saperle adoperare bene per poterne sfruttare appieno le

potenzialità.

Fondamentalmente permettono l'allocazione dinamica di memoria: a dierenza di un array, che se viene

denito come array[20] può contenere al massimo 20 elementi, la lista non ha dimensioni (a parte la memoria

del computer, ovvio) e può essere modicata dinamicamente, aggiungendo o togliendo elementi anche durante

il programma stesso. typedef

Si basano su una ricorsiva, in cui all'interno della denizione del tipo si descrive un puntatore -

lista per gestione di

*next

generalmente chiamato - dello stesso tipo della lista. Un esempio su tutti è la

numeri interi

, di seguito riportata perchè molto frequente nella risoluzione degli esercizi:

typedef struct nodo

{

int valore;

struct nodo *next;

} nodo; 12

Maneggiare una lista può procurare grandi vantaggi in fase di programmazione, e altrettanto grandi

sciagure se usata male: mi pare dunque giusto riportare, come già fatto in alcune sezioni precedenti, un

elenco di operazioni base che si possono eettuare con le liste.

Istruzioni per l'uso

Con le liste si può gestire molto economicamente (in termini di memoria) un qualsiasi processo; è però

necessario ricordare alcune nozioni fondamentali:

• Le liste lavorano con i puntatori, bisogna dunque stare attenti quando si fanno gli assegnamenti.

• Per scorrere una lista, identicata dalla presenza di una testa, è necessaria una variabile temporanea:

testa

essa va inizializzata a perchè altrimenti non si riesce a costruire la lista.

• Per accedere ad un elemento di una lista, pur essendo il tipo denito da una typedef, non si usa

l'operatore punto ma la freccia. Ad esempio: temp freccia valore.

• La variabile temporanea occupa la memoria esattamente necessaria all'acquisizione del dato: perchè

malloc

questo sia possibile, si deve ricorrere alla funzione , che viene denita come di seguito:

if(temp=(nodo*)malloc(sizeof(nodo))) temp sizeof

dove si denisce anche il tipo di appartenenza per la variabile , e si usa la funzione - che

calcola da sè la dimensione del tipo indicato - per allocare il corretto numero di bit in memoria.

• Con una lista si possono eettuare due operazioni fondamentali: inserimento di un elemento e cancel-

lazione di un elemento. Queste vengono di seguito riportate come algoritmi generali per la loro grande

importanza.

Inserimento in testa

Come nei problemi con array, spesso (praticamente sempre, a dire il vero) viene richiesto di acquisire un

dato, che poi andrà collocato in memoria. Le liste, però, non hanno un indice - come gli array - per il

semplice motivo che la quantità di elementi contenuti non è denita a priori: esse operano mediante una

variabile temporanea che scorre ogni singolo elemento della lista. Avendo la lista una testa, il procedimento

che permette di inserire nuovi valori consiste nell'inserire il valore acquisito, memorizzato di volta in volta

testa

nella variabile temporanea, prima della testa e di aggiornarne il valore per fare in modo che punti

sempre al primo elemento. L'algoritmo per l'inserimento è il seguente:

/* Inserimento in testa */

/* Questa parte di programma contiene l'algoritmo per l'inserimento in testa di un numero

intero */ /* Dopo aver definito il tipo adatto per la lista... */

nodo *temp,*testa=0;

int num;

temp=testa;

if(temp=(nodo*)malloc(sizeof(nodo)))

{

temp->valore=num;

temp->next=testa;

testa=temp;

}

else

printf("\n Errore allocazione memoria. \n");

13

Cancellazione di un elemento

Un grande vantaggio delle liste rispetto ai più statici array è quello di poter cancellare elementi. Per far

questo, però, è necessario usare due diverse variabili temporanee che si inseguano: entrambe scorrono la

lista, sfalsate tra di loro di una posizione. In questo modo quando la variabile più avanti nello scorrimento

identica il valore da eliminare, l'altra punta direttamente all'elemento successivo alla prima: si crea così una

free

nuova lista priva dell'elemento richiesto. Per completare l'opera si ricorre poi alla funzione per liberare

dalla memoria lo spazio occupato dalla variabile temporanea (che ora non punta più a nulla) e ottimizzare

la gestione dello spazio in memoria sul computer. L'algoritmo per la cancellazione (che consiste di due casi:

o l'elemento da eliminare è il primo della lista, o va cercato scorrendo tutta la lista) è il seguente:

/* Cancellazione di un elemento */

/* Questa parte di programma contiene l'algoritmo per la cancellazione di un elemento */

/* Dopo aver definito il tipo adatto per la lista... */

nodo *temp, *temp1, *testa=0;

int num;

int trovato=0; /* Per scorrere la lista fino a quando non si trova l'elemento desiderato

*/ temp=testa;

if(temp=(nodo*)malloc(sizeof(nodo)))

{

if(testa->valore == valore) /* L'elemento da cancellare e' il primo della lista */

{

temp=testa;

testa=testa->next;

free(temp);

}

else

{

temp=testa->next;

temp1=testa;

trovato=0;

while(! trovato && temp) /* Si scorre la lista fino a trovare l'elemento */

{

if(temp->valore == valore)

trovato=1;

else

{

temp=temp->next;

temp1=temp1->next;

}

}

if(trovato)

{

temp1->next=temp->next;

free(temp);

}

}

}

else

printf("\n Errore allocazione memoria. \n");