[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]

Originariamente inviato da alebertaz

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]

Originariamente inviato da wingman87

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]

Originariamente inviato da alebertaz

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]

Originariamente inviato da Ziosilvio

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...

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]

Originariamente inviato da 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.

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]

Originariamente inviato da Furla

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]

Originariamente inviato da alebertaz

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
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]

Originariamente inviato da trallallero

ma il main mi auguro sia roba tua e non testo dell'esame
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]

Originariamente inviato da alebertaz

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]

Originariamente inviato da trallallero

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]

Originariamente inviato da alebertaz

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]

Originariamente inviato da Andlea

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 ?
eppure ho fatto anche il professore
mi spiace alebertaz, se si potesse con carta e penna (o lavagna e gesso) sarebbe tutto cosí semplice

[uReverendo]

Io l'ho risolto 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!!!!
ho fatto un errore!

Originariamente inviato da trallallero

   int i = 0;

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

ancora con 'sti errori

[trallallero]

Originariamente inviato da uReverendo

Io l'ho risolto 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]

Originariamente inviato da uReverendo

Io l'ho risolto 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