[C] Qualcuno sa risolvere quest'esercizio in C?

[alebertaz]

Ecco il testo (grazie x chi mi può aiutare):

Scrivere una funzione ricorsiva occPorzFinale che, data una lista semplice di stringhe, una stringa s e un numero positivo n (> 0) calcola il numero di occorrenze della stringa nella porzione finale della lista specificata dal numero n. Il prototipo della funzione è: int occPorzFinale(Lista str l, char *s, int n, int *distFine) dove in distFine è restituita la lunghezza della lista.
Deve essere dichiarato il tipo utilizzato per definire le liste. Non si possono usare funzioni ausiliarie n´e variabili globali nè variabili static.

Esempio:
l = [Vedi, in, questi, silenzi, in, cui, le,cose]
occPorzFinale(l, in,4,&distFine) = 1
occPorzFinale(l, in,3,&distFine) = 0

Ecco il codice, senza la funzione...

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

typedef struct elem_s {
char *val;
struct elem_s * next;
} elem_str;

typedef elem_str * Lista_str;

int occPorzFinale(Lista_str l, char *s, int n, int *distFine) {}


int main() {
Lista_str a=(elem_str*)malloc(sizeof(elem_str));
Lista_str b=(elem_str*)malloc(sizeof(elem_str));
Lista_str c=(elem_str*)malloc(sizeof(elem_str));
Lista_str d=(elem_str*)malloc(sizeof(elem_str));
int distFine=0;
a->val="silenzi";
a->next=b;
b->val="in";
b->next=c;
c->val="cui";
c->next=d;
d->val="cose";
d->next=NULL;
//printf("%d",distFine);
printf("%d", occPorzFinale(a,"in",2,&distFine));
}

[wingman87]

calcola il numero di occorrenze della stringa nella porzione finale della lista specificata dal numero n.

Non ho capito questa parte, cosa intende dire?

[alebertaz]

Non ho capito questa parte, cosa intende dire?

Cioè se la lista è:
l = Vedi-> in-> questi-> silenzi-> in-> cui-> le->cose->NULL
e chiamo la funzione occPorzFinale(l, in,4,&distFine)
n quindi è =4, devo considerare solo la porzione di lista degli ultimi 4 elementi ovvero
in->cui->le->cose->NULL in cui la parola in compare.
In questo caso la funzione dà esito 1 perchè "in" viene trovato.
Se chiamo invece occPorzFinale(l, in,3,&distFine), in non viene trovato perchè non esiste nella porzione finale di lista cui->le->cose->NULL
In distFine và memorizzato invece la lunghezza della lista cioè il valore 8.

[Ziosilvio]

Scrivere una funzione ricorsiva occPorzFinale che, data una lista semplice di stringhe, una stringa s e un numero positivo n (> 0) calcola il numero di occorrenze della stringa nella porzione finale della lista specificata dal numero n. Il prototipo della funzione è: int occPorzFinale(Lista str l, char *s, int n, int *distFine) dove in distFine è restituita la lunghezza della lista.
Deve essere dichiarato il tipo utilizzato per definire le liste. Non si possono usare funzioni ausiliarie n´e variabili globali nè variabili static.
Sembra un classico esercizio da esame.
Perche' non provi a farlo tu, ci dici dove incontri difficolta', e vediamo di darti una mano? In questo modo, il lavoro rimarrebbe comunque in gran parte tu, e tu impareresti molto di piu' che facendotelo semplicemente risolvere da qualcun altro ;)

Intanto, ti faccio qualche osservazione sul codice:
Esempio:
l = [Vedi, in, questi, silenzi, in, cui, le,cose]
occPorzFinale(l, in,4,&distFine) = 1
Casomai: occPorzFinale(l,"in",4,&distFine) ;)

a->val="silenzi";
Fa' attenzione: assegnare a->val in questo modo va bene solo perche' la stringa non verra' modificata in seguito. Altrimenti, dovresti allocare strlen("silenzi")+1 char a partire da a, ed effettuare strcpy(a,"silenzi").

Il resto del codice, grosso modo, andava bene.
Per occPorzFinale, secondo me te la cavi con le funzioni di libreria dichiarate in string.h: devi solo fare un po' di attenzione.

[Furla]

dunque, se ho capito il problema, la funzione dovrebbe semplicemente vedere con un blocco if se l'ultimo elemento corrisponde alla stringa cercata, per poi richiamare se stessa, operando sulla lista di distFine - 1 elementi (ovvero controllando l'elemento precedente), e fermandosi quando si è autorichiamata n volte.

non so il c, ti faccio un algoritmo generico "visualbasiccheggiante":

occPorzFinale(Lista_str l, char *s, int n, int *distFine)
if n = 0 then
return 0
else
. if l(*distFine) = *s then
... return occPorzFinale(l, s, n - 1, int distFine - 1) + 1
. else
... return occPorzFinale(l, s, n - 1, distFine - 1) + 0
. endif
endif

[alebertaz]

Sembra un classico esercizio da esame.
Perche' non provi a farlo tu, ci dici dove incontri difficolta', e vediamo di darti una mano? In questo modo, il lavoro rimarrebbe comunque in gran parte tu, e tu impareresti molto di piu' che facendotelo semplicemente risolvere da qualcun altro ;)

Esatto, è un esercizio d'esame... :p

Questà è la mia bozza di funzione...ovviamente non funziona...sapete darmi una mano?

int occPorzFinale(Lista_str l, char *s, int n, int *distFine) {
if (!l) return 0;
if ((*distFine)<n) {
*distFine=*distFine+1;
if (strcmp(l->val, s)==0)
return 1;
else
return 0;
}
return 0+occPorzFinale(l->next,s,n,distFine);
}

Intanto, ti faccio qualche osservazione sul codice:

Casomai: occPorzFinale(l,"in",4,&distFine) ;)

si ho notato, effettivamente è un errore del testo...


Fa' attenzione: assegnare a->val in questo modo va bene solo perche' la stringa non verra' modificata in seguito. Altrimenti, dovresti allocare strlen("silenzi")+1 char a partire da a, ed effettuare strcpy(a,"silenzi").


li ho assegnati in questo modo perchè la lista andava solamente visitata

Il resto del codice, grosso modo, andava bene.
Per occPorzFinale, secondo me te la cavi con le funzioni di libreria dichiarate in string.h: devi solo fare un po' di attenzione.

và usato infatti strcmp per confrontare l'uguaglianza fra due stringhe

[alebertaz]

dunque, se ho capito il problema, la funzione dovrebbe semplicemente vedere con un blocco if se l'ultimo elemento corrisponde alla stringa cercata, per poi richiamare se stessa, operando sulla lista di distFine - 1 elementi (ovvero controllando l'elemento precedente), e fermandosi quando si è autorichiamata n volte.


esatto


if l(*distFine) = *s then

distFine credo che inizialmente valga 0, quindi aumenta man mano che la funzione scorre la lista...

[Furla]

dove in distFine è restituita la lunghezza della lista.

:)

ah, ovviamente per l(distFine) io intendo il distFine-esimo elemento della lista, se l'index parte da 0 dovremo usare l(distFine - 1) ;)

[alebertaz]

:)

ah, ovviamente per l(distfine) intendo il distFine-esimo elemento della lista, se l'index parte da 0 dovremo usare l(distfine - 1) ;)

è la funzione che deve calcolare distFine, che inizialmente vale 0

[trallallero]

int main() {
Lista_str a=(elem_str*)malloc(sizeof(elem_str));
Lista_str b=(elem_str*)malloc(sizeof(elem_str));
Lista_str c=(elem_str*)malloc(sizeof(elem_str));
Lista_str d=(elem_str*)malloc(sizeof(elem_str));
int distFine=0;
a->val="silenzi";
a->next=b;
b->val="in";
b->next=c;
c->val="cui";
c->next=d;
d->val="cose";
d->next=NULL;
//printf("%d",distFine);
printf("%d", occPorzFinale(a,"in",2,&distFine));
}
ma il main mi auguro sia roba tua e non testo dell'esame :eek:
vabbé, in ogni caso se dice lista devi fare una lista.
Tu invece fai n elementi a,b,c ... e poi passi solo "a" alla funzione
io farei:

elem_str list[] =
{
{ "pippo", NULL },
{ "pluto", NULL },
{ "pape" , NULL },
{ "papi" , NULL },
{ "papin", NULL },
{ "papi" , NULL },
{ "" , NULL }
};

dove "" segna la fine della lista.
poi setto i puntatori next della lista:

int i = 0;

while(1)
if (strlen( list[i].val) )
list[i].next = &list[++i];
else break;

[alebertaz]

ma il main mi auguro sia roba tua e non testo dell'esame :eek:
vabbé, in ogni caso se dice lista devi fare una lista.
Tu invece fai n elementi a,b,c ... e poi passi solo "a" alla funzione
io farei:

elem_str list[] =
{
{ "pippo", NULL },
{ "pluto", NULL },
{ "pape" , NULL },
{ "papi" , NULL },
{ "papin", NULL },
{ "papi" , NULL },
{ "" , NULL }
};

dove "" segna la fine della lista.
poi setto i puntatori next della lista:

int i = 0;

while(1)
if (strlen( list[i].val) )
list[i].next = &list[++i];
else break;


si, il main l'ho fatto io per fare un pò di prove...

la lista deve essere implementata usando questa struttura dati senza indicizzazione:

typedef struct elem_s {
char *val;
struct elem_s * next;
} elem_str;

typedef elem_str * Lista_str;

[trallallero]

la lista deve essere implementata usando questa struttura dati senza indicizzazione:
e dove sta scritto ? non hai mandato tutta la traccia allora ?
comunque una lista é intesa come 1 oggetto contenente una serie di valori.
Tu invece stai facendo n liste contenenti 1 valore.
se fai tante liste "a","b","c","d","e",... e poi
chiami la funzione passando solo "a" come fa la funzione
a sapere cosa c'é dentro "b","c", ... ?

[alebertaz]

e dove sta scritto ? non hai mandato tutta la traccia allora ?
comunque una lista é intesa come 1 oggetto contenente una serie di valori.
Tu invece stai facendo n liste contenenti 1 valore.
se fai tante liste "a","b","c","d","e",... e poi
chiami la funzione passando solo "a" come fa la funzione
a sapere cosa c'é dentro "b","c", ... ?

la struttura lista contiene una stringa e il puntatore ad un altro oggetto lista
a e b sono due oggetti lista elem_str.
La lista composta da a e b può essere scritta così:
Lista_str lista=a;

Per scorrere tutta la lista:
while (lista) {
//fai qualcosa
lista=lista->next;
}

...

[Andlea]

la struttura lista contiene una stringa e il puntatore ad un altro oggetto lista
a e b sono due oggetti lista elem_str.
La lista composta da a e b può essere scritta così:
Lista_str lista=a;

Quello che trallallero vuol dire è che tu hai dichiarato due liste distinte, legate tra loro
quando vuoi aggiungere un elemento ad una linked list, devi allocare memoria per un ELEMENTO, non per una lista di elementi come fai tu. Dopo aver allocato l'elemento ed averlo definito, ne passi l'indirizzo al puntatore next.
Per inserire l'elemento successivo farai un lista=lista->next; avendo cura di mantenere una variabile con il puntatore alla radice della lista
In definitiva la struttura tipo sarà UN puntatore all'elemento corrente della lista, UN puntatore alla radice della lista, UN puntatore all'elem_str che verrà allocato ad ogni inserimento

[trallallero]

Quello che trallallero vuol dire è che tu hai dichiarato due liste distinte, legate tra loro
quando vuoi aggiungere un elemento ad una linked list, devi allocare memoria per un ELEMENTO, non per una lista di elementi come fai tu. Dopo aver allocato l'elemento ed averlo definito, ne passi l'indirizzo al puntatore next.
Per inserire l'elemento successivo farai un lista=lista->next; avendo cura di mantenere una variabile con il puntatore alla radice della lista
In definitiva la struttura tipo sarà UN puntatore all'elemento corrente della lista, UN puntatore alla radice della lista, UN puntatore all'elem_str che verrà allocato ad ogni inserimento
forse ho dato per scontato qualcosa ? :eek:
eppure ho fatto anche il professore :muro:
mi spiace alebertaz, se si potesse con carta e penna (o lavagna e gesso) sarebbe tutto cosí semplice :)

[uReverendo]

Io l'ho risolto :D ragionando in questo modo:

- Prima di tutto ho trovato il modo di contare il numero di elementi nella lista;
- Poi ho cercato di contare le occorrenze della stringa nella lista;
- Infine ho preso solo le occorrenze nelle n posizioni finali.
Mettendo tutto insieme ecco cosa mi è uscito:

int occPorzFinale(Lista_str l, char *s, int n, int *distFine)
{

int c = 0; // Conta le occorrenze della stringa
int intPosCorr; // Salva la posizione corrente nella lista

// Controlla che la lista non sia finita
if(l != NULL)
{
// Aggiorna il numero di elementi della lista
(*distFine)++;
// Salva il numero di elementi
intPosCorr = (*distFine);
// Chiama nuovamente la funzione
c = occPorzFinale(l->next, s, n, distFine);
// distFine ora contiene il numero totale di elementi
// c contiene le occorrenze trovate finora

// Controlla che la stringa nella posizione corrente della lista sia uguale
// a quella cercata e controlla anche che essa si trovi negli ultimi n elementi
// della lista
if( (strcmp(l->val, s) == 0) && ((*distFine)-intPosCorr+1 <= n) )
// Un'altra occorrenze trovata!!!
c++;
}

// Restituisce le occorrenze trovate finora
return c;
}

[trallallero]

AAAAAAAAAAAAAAAAAAAAAAH!!!! :eekk:
ho fatto un errore!



int i = 0;

while(1)
if (strlen( list[i].val) )
list[i].next = &list[++i];
else break;

:muro: ancora con 'sti errori :muro:

[trallallero]

Io l'ho risolto :D ragionando in questo modo:

- Prima di tutto ho trovato il modo di contare il numero di elementi nella lista;
- Poi ho cercato di contare le occorrenze della stringa nella lista;
- Infine ho preso solo le occorrenze nelle n posizioni finali.
Mettendo tutto insieme ecco cosa mi è uscito:

int occPorzFinale(Lista_str l, char *s, int n, int *distFine)
{

int c = 0; // Conta le occorrenze della stringa
int intPosCorr; // Salva la posizione corrente nella lista

// Controlla che la lista non sia finita
if(l != NULL)
{
// Aggiorna il numero di elementi della lista
(*distFine)++;
// Salva il numero di elementi
intPosCorr = (*distFine);
// Chiama nuovamente la funzione
c = occPorzFinale(l->next, s, n, distFine);
// distFine ora contiene il numero totale di elementi
// c contiene le occorrenze trovate finora

// Controlla che la stringa nella posizione corrente della lista sia uguale
// a quella cercata e controlla anche che essa si trovi negli ultimi n elementi
// della lista
if( (strcmp(l->val, s) == 0) && ((*distFine)-intPosCorr+1 <= n) )
// Un'altra occorrenze trovata!!!
c++;
}

// Restituisce le occorrenze trovate finora
return c;
}
ottima soluzione :)
ma per farla funzionare correttamente la riga in neretto é:

if( (strcmp(l->val, s) == 0) && ((*distFine)-intPosCorr >= n) )

[alebertaz]

Io l'ho risolto :D ragionando in questo modo:

- Prima di tutto ho trovato il modo di contare il numero di elementi nella lista;
- Poi ho cercato di contare le occorrenze della stringa nella lista;
- Infine ho preso solo le occorrenze nelle n posizioni finali.
Mettendo tutto insieme ecco cosa mi è uscito:

int occPorzFinale(Lista_str l, char *s, int n, int *distFine)
{

int c = 0; // Conta le occorrenze della stringa
int intPosCorr; // Salva la posizione corrente nella lista

// Controlla che la lista non sia finita
if(l != NULL)
{
// Aggiorna il numero di elementi della lista
(*distFine)++;
// Salva il numero di elementi
intPosCorr = (*distFine);
// Chiama nuovamente la funzione
c = occPorzFinale(l->next, s, n, distFine);
// distFine ora contiene il numero totale di elementi
// c contiene le occorrenze trovate finora

// Controlla che la stringa nella posizione corrente della lista sia uguale
// a quella cercata e controlla anche che essa si trovi negli ultimi n elementi
// della lista
if( (strcmp(l->val, s) == 0) && ((*distFine)-intPosCorr+1 <= n) )
// Un'altra occorrenze trovata!!!
c++;
}

// Restituisce le occorrenze trovate finora
return c;
}


Ottimo esordio nel forum uReverendo ;)
Domani con calma controllo
Grazie a tutti per l'aiuto :)