Scrivere una funzione che prende come parametro una lista di caratteri che formano una sequenza di parole, separate da spazi (la lista contiene solo lettere e spazi), e restituisce la lista formata dalle lettere iniziali di ogni parola, nell'ordine in cui le parole appaiono nella lista.
Se per esempio la lista di partenza contiene la sequenza di caratteri frase che non vuole dire niente allora la lista che deve venire restituita è fcnvdn. Il programma driver, che legge una lista da file e chiama la funzione CreaListaAcronimo da realizzare è gen02-driver.c. La seguente lista dà alcuni file che si possono usare per testare il programma: lischar1.txt, lischar2.txt (lista vuota), lischar3.txt, lischar4.txt, lischar5.txt, lischar6.txt, lischar7.txt, lischar8.txt,
Il testo dell'esercizio si può rifrasare come segue: data una lista, costruire una seconda lista che contiene solo alcune lettere della prima. In particolare, la seconda lista contiene una lettera della prima solo se questa è la lettera iniziale di una parola.
Possiamo quindi dire che si tratta di selezionare le lettere della prima lista che sono lettere iniziali di una parola; queste lettere vanno messe nella seconda lista. Per fare questo è ovviamente necessario verificare, per ogni elemento della prima lista, se soddisfa la condizione di essere inizio di una parola, nel qual caso la lettera va messa nella seconda lista.
per ogni elemento della prima lista
se e' l'inizio di una parola
allora mettilo nella seconda lista
La prima linea, ossia la frase per ogni elemento della prima lista si traduce in C in una scansione della lista, e non presenta nessuna difficoltà.
Veniamo ora invece alla traduzione della frase se e' l'inizio di una parola. Occorre rendere questa frase meno ambigua, ossia va prima trasformata in modo che specifichi in modo esatto come si fa a capire se una lettera è l'inizio di una parola.
Possiamo però sfruttare l'assunzione che la lista contiene solo lettere e spazi. Questo significa che la lista contiene delle sequenza di lettere intervallate da uno o più spazi, e le sequenze di lettere sono appunto le parole. Questo significa che una parola inizia quando:
Il secondo punto si può ulteriormente semplificare notando che la parola in effetti inizia quando uno spazio è seguito da una lettera. Quindi, un elemento della prima lista è l'inizio di una parola se è il primo carattere della lista ed è una lettera, oppure se è preceduto da un carattere.
Il primo punto è facile da verificare: basta controllare se il primo elemento della lista è una lettera, e quindi si può anche fare fuori dal ciclo di scansione della prima lista.
if(l==NULL)
return NULL;
if(l->val!=' ') {
s=malloc(sizeof(struct NodoLista));
s->val=l->val;
s->next=NULL;
}
/* scansione della lista */
Verificare se un elemento è preceduto da uno spazio è invece più difficile. Infatti, una volta che ci troviamo a scandire un carattere, non abbiamo un modo facile di vedere qual'è l'elemento che lo precede (la cosa è invece banale nel caso dei vettori, in cui basta diminuire di uno l'indice).
Sono però possibili due soluzioni. La prima è quella di memorizzare l'elemento corrente prima di avanzare il puntatore: questo elemento risulta quindi il precedente nel successivo corpo del ciclo di scansione. Il secondo modo consiste nel modificare ulteriormente la definizione di inizio di parola; infatti, possiamo dire che una parola inizia quando uno spazio è seguito da una lettera, e che la lettera (quindi, l'elemento successivo) è l'iniziale della parola.
Iniziamo quindi ad analizzare la prima soluzione. L'idea è la seguente: se ho finito di analizzare un elemento della lista l->val e sto per passare al successivo facendo l=l->val, allora l'elemento che ora è quello corrente dopo questa istruzione diventa l'elemento precedente. D'altra parte, non posso più accedere ad esso, dal momento che il puntatore l è stato portato avanti. Occorre quindi memorizzare l'elemento prima che il puntatore vada avanti. Per fare questo, posso utilizzare una variabile di tipo carattere. In breve, se abbiamo la sequenza di istruzioni:
c=l->val; l=l->next;
Allora c è un elemento della lista, mentre alla fine l punta all'elemento successivo. In altre parole, c è l'elemento precedente a quello puntato da l.
La soluzione, a questo punto, &ovvia: si fa una scansione della lista, memorizzando nella variabile c il valore dell'elemento precedente. Ad ogni elemeno della lista, si vede se l'elemento è una lettera, e se il precedente è uno spazio. In questo caso, si aggiunge il carattere corrente alla lista.
c=l->val;
l=l->next;
while(l!=NULL) {
if(l->val!=' ' && c==' ')
/* inserisci l->val nella lista s */
c=l->val;
l=l->next;
}
Si faccia attenzione alle prime due istruzioni: dal momento la scelta se inserire o meno un elemento dipende dall'elemento e dall'elemento precedente, è necessario che la scansione venga fatta solo su elementi per i quali esiste un elemento precedente. Infatti, inseriamo un elemento in lista solo se è una lettera e il precedente è uno spazio, e questo confrono ha senso solo se l'elemento corrente ha un precedente da confrontare con lo spazio.
A prima vista la cosa non crea problemi: tutti gli elementi della lista hanno un precedente? Questo è vero per quasi tutti gli elementi della lista, o meglio, tutti tranne il primo, che non ha un elemento precedente. Quindi, dato che la scansione va fatta solo su elementi che hanno un elemento precedente, occorre iniziare la scansione a partire dal secondo elemento della lista. Questo spiega l'istruzione l=l->next; che precede l'intero ciclo. Prima ancora viene effettuato l'assegnamento c=l->val che memorizza il primo elemento in c, in modo tale che, alla prima esecuzione del ciclo contenga correttamente il valore dell'elemento precedente.
Quello che manca, a questo punto, è l'inserimento del carattere nella lista risultato. In questo caso, vogliamo che le lettere iniziali delle parole vangano inserite nello stesso ordine in cui le lettere stesse sono state incontrate durante la scansione della lista.
Supponiamo quindi che la lista che è stata passata come parametro sia appunto frase che non vuole dire niente, e vediamo in che modo le lettere vanno inserite. Il primo carattere della lista è l, per cui viene messo nella lista risultato prima ancora di iniziare il ciclo di scansione. A questo punto la lista r contiene un solo elemento, la lettera f.
Quando la scansione arriva alla lettera c, da cui inizia la seconda parole, abbiamo quindi il carattere c da inserire, e la lista è composta dalla sola lettera f. Dova va messa la c? In questo caso f è l'iniziale della prima parola, mentre c è l'iniziale della seconda. Quindi la c va messa dopo la lettera f.
La lista che risulta è quindi fc. Continuiamo quindi la scansione, e arriviamo alla n da cui inizia la parola non. Ora, questa è la terza parola, per cui la lettera va messa dopo le altre due. Quando si arriva alla quarta parola vuol, la v iniziale va messa in quarta posizione, ossia dopo le altre. Lo stesso vale per la quinta lettera ecc.
In generale, possiamo dire semplicemente che, quando si arriva a una nuova lettera da inserire, questa va messa dopo quelle che sono state trovate fino a quel momento. Quindi, l'inserimento da fare è quello in coda alla lista.
TipoLista CreaListaAcronimo(TipoLista l) {
TipoLista a;
char c;
if(l==NULL)
return NULL;
a=NULL;
if(l->val!=' ')
InserisciCodaLista(&a, l->val);
c=l->val;
l=l->next;
while(l!=NULL) {
if(c==' ' && l->val!=' ')
InserisciCodaLista(&a, l->val);
c=l->val;
l=l->next;
}
return a;
}
La funzione di inserimento in coda si può sia in modo iterativo che in modo ricorsivo. Entrambi i metodi sono stati visti a lezione, e si trovano anche sul libro. Di seguito, ecco il link all'inserimento in coda iterativo. La versione ricorsiva è simile alla cancellazione dell'ultimo elemento ricorsiva.
Consideriamo ora il secondo metodo di soluzione a cui si è accennato, ossia quello di fare la scansione controllando se il carattere corrente sia uno spazio mentre il successivo è una lettera.
In questo caso, la scansione va iniziata dal primo elemento della lista. Può anche darsi il caso che il primo carattere della lista sia uno spazio, seguito da una lettera; in questo caso, occorre fare il controllo anche sul primo elemento della lista, dato che il controllo infatti dice che il successivo elemento è l'inizio di una parola.
Il ciclo consiste quindi in una scansione della lista, in cui ad ogni passo si controlla se l->val è uno spazio mentre l->next->val è una lettera. Se entrambe le condizioni sono vere, il carattere da inserire in lista è il successivo, ossia l->next->val.
Si noti che, ad ogni passo, si fa un accesso all'elemento puntato da l->next. È quindi necessario fare in modo che questo puntatore non sia mai NULL. In altre parole, l'ultimo confronto significativo è quello che viene fatto con il penultimo e l'ultimo elemento. Infatti, se si trova che il penultimo è uno spazio e l'ultimo è una lettera, mettiamo l'ultimo in lista. Altrimenti, abbiamo esaurito la lista, e non ci sono altre possibilità di passare da uno spazio a una lettera.
Tutto questo ci dice che il ciclo di scansione, in questo caso, inizia dal primo elemento della lista (e non dal secondo come nel caso precedente), e termina con il penultimo elemento (e non con l'ultimo).
Anche in questo caso occorre fare prima il controllo sul primo elemento della lista (se è una lettera va messo in lista), e anche in questo caso l'inserimento in lista va fatto in coda. La funzione risultante è quindi la seguente.
TipoLista CreaListaAcronimo(TipoLista l) {
TipoLista a;
if(l==NULL)
return NULL;
a=NULL;
if(l->val!=' ')
InserisciCodaLista(&a, l->val);
while(l->next!=NULL) {
if(l->val==' ' && l->next->val!=' ')
InserisciCodaLista(&a, l->next->val);
l=l->next;
}
return a;
}
Esistono delle varianti di queste due soluzioni. Per esempio, la prima soluzione funziona ugualmente se non si effettua il controllo sul primo elemento, ma si pone inizialmente c=' ' e poi si fa la scansione a partire dal primo elemento della lista, invece che dal secondo. In questo modo, se il primo elemento è una lettera, alla prima esecuzione del ciclo risulta vero sia che c è uno spazio, sia che l'elemento corrente è una lettera, e quindi il primo elemento viene correttamente inserito in lista.
È poi possibile sostutire l'inserimento in coda con l'inserimento in testa. Questo però genera una lista in cui l'ordine delle lettere è invertito. Per ottenere l'ordine giusto, occorre quindi invertire la lista prima di ritornarla. La funzione di inversione di una lista si trova sul libro.
Una ultima soluzione comporta l'inserimento in coda alla lista, ma senza usare una funzione separata, ma mantenendo un puntatore all'ultimo elemento della lista che si sta costruendo. Questa soluzione è quella più complessa, ed è quindi quella che più facilmente può portare a errori.