[C] Funzione ricorsiva per l'unione di stringhe

[Deidan]

Salve a tutti avrei un piccolo problema. In pratica mi è stato chiesto di realizzare una funzione ricorsiva la quale ha in input due stringhe, che rappresentano due insiemi A e B di caratteri, e restituisce in output una terza stringa che contiene l'unione degli insiemi A e B, per esempio se stringa1 = "afr" e stringa2 = “abdr” allora stringa3 = “abdfr” . Non ho molta pratica con la ricorsione e quindi non so bene come implementarla. Ci sarebbe qualcuno che può aiutarmi? Grazie mille in anticipo.

[Laikius91]

Non ci è permesso aiutarti in toto..

Prova a ragionare su un foglio di carta su come realizzare la funzione:

analizzi la stringa più corta;

1) se è terminata ritorni una stringa risultato non modificata;
2) se non è terminata e il primo carattere è presente nell'altra stringa, copi il carattere nella stringa risultato;
3) se no riduci la ricerca incrementando la stringa che stai analizzando!

[Deidan]

Io avevo pensato a questa soluzione, solo che non so come implementarla ricorsivamente:

1) Confronto ciascun elemento della stringa più lunga con tutti gli elementi della stringa più corta. Se trovo l'elemento interrompo la ricerca e lo copio nella stringa risultato. Altrimenti continuo la ricerca e se non trovo nessun elemento della stringa corta corrispondente all'elemento della stringa lunga che sto analizzando, allora lo copio nella stringa risultato.

2) Una volta completata la stringa lunga, passo alla stringa corta e confronto ciascun elemento della corta con tutti gli elementi della stringa risultato. Se trovo l'elemento della corta nella stringa risultato allora non copio nulla, altrimenti copio il carattere della stringa corta nella stringa risultato.

[Laikius91]

Scusami, mi sa che avevo letto troppo in fretta la consegna

Il tuo ragionamento è giusto comunque, devi solo capire come renderlo ricorsivo, ricordati che occorre sempre una condizione di terminazione, ossia un caso banale al quale ricondurti con le altre istruzioni

Magari prova a buttare giù qualcosa e posta il risultato!

[Laikius91]

Originariamente inviato da Deidan
Salve a tutti avrei un piccolo problema. In pratica mi è stato chiesto di realizzare una funzione ricorsiva la quale ha in input due stringhe, che rappresentano due insiemi A e B di caratteri, e restituisce in output una terza stringa che contiene l'unione degli insiemi A e B, per esempio se stringa1 = "afr" e stringa2 = “abdr” allora stringa3 = “abdfr” . Non ho molta pratica con la ricorsione e quindi non so bene come implementarla. Ci sarebbe qualcuno che può aiutarmi? Grazie mille in anticipo.

Piccolo chiarimento, le stringhe passate alla funzione sono ordinate? O è una coincidenza che nel tuo esempio sia cosi?

[Deidan]

No è una coincidenza dell'esempio, non serve che siano ordinate

[Laikius91]

Ok perfetto... Ma c'è un po' di ambiguità nella richiesta, cioè è un unione particolare... Mi spiego meglio:
dall'esempio sembra che nella stringa risultato debbano esserci i caratteri contenuti nelle due stringhe passate NON ripetuti; se una delle due stringhe al suo interno ha delle ripetizioni queste vanno ignorate?

Ad esempio: se vengono passate le stringhe "aghkja" e "aaabbb", la stringa risultato deve essere "abghkj"?

[Deidan]

Le stringhe rappresentano degli insiemi di caratteri, quindi si suppone che non ci siano elementi ripetuti.

[ramy89]

La mia idea è di usare una variabile statica che rappresenta la stringa che alla fine andrà restituita,questa stringa all' inizio sarà vuota,poi man mano che scandisci le stringhe se ne trovi uno nuovo lo allochi,fai il controllo carattere per carattere,alla fine del controllo se la stringa non è finita (guardi se c'è il terminatore) passi alla stessa funzione il carattere successivo.Poi se e solo se entrambe le due stringhe sono finite ritorni l' array di char,statico e che viene allocato di un carattere in più solo se il carattere non è già presente.
Spero che è chiaro,prova a farla semmai se è sbagliata ci diamo un' occhiata.

[Laikius91]

Originariamente inviato da ramy89
La mia idea è di usare una variabile statica che rappresenta la stringa che alla fine andrà restituita,questa stringa all' inizio sarà vuota,poi man mano che scandisci le stringhe se ne trovi uno nuovo lo allochi,fai il controllo carattere per carattere,alla fine del controllo se la stringa non è finita (guardi se c'è il terminatore) passi alla stessa funzione il carattere successivo.Poi se e solo se entrambe le due stringhe sono finite ritorni l' array di char,statico e che viene allocato di un carattere in più solo se il carattere non è già presente.
Spero che è chiaro,prova a farla semmai se è sbagliata ci diamo un' occhiata.

Interessante sai?
Per comodità, la stringa risultato si potrebbe già allocare della somma delle lunghezze delle altre due (ossia il caso peggiore in cui le due stinghe contegano caratteri tutti diversi)...
Il problema è stabilire i casi banali di terminazione dell'algoritmo... Cioè, se una delle due stringhe termina prima dell'altra come bisogna comportarsi?