Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Buonasera a tutti, il mio problema è il seguente, e ci sto un poco sbattendo la testa: Avendo due stringhe, allora si devono trovare le occorrenze della prima stringa nella seconda (ovviamente la seconda è più grande della prima) e le si devono eliminare col minor numero di spostamenti di memoria possibile.
La soluzione che ho pensato è la seguente: in un primo momento trovo tutte le occorrenze nella stringa e salvo le posizione della corrispondenza in un array di interi. Se la stringa da cercare si ripete due volte in modo consecutivo nella stringa allora l'ultima posizione salvata nell'array delle posizioni viene aggiornata, in modo che quando verrà eseguito lo spostamento di memoria per compattare l'array, non dovrà eseguirlo due volte, ma solo una volta per quella specifica area (non so se ho lasciato intendere). Il punto è proprio questo, ho individuato le aree da eliminare, ed ho anche l'array delle posizioni, ma non riesco a compattare l'array eliminando quelle aree specifiche.
returnstr; // restituisce l'indirizzo ricevuto in str
}
// Esempio d'uso
int main(){
char str[]="acacsssdstgfdfgdacacddf";
const char rem[]="ac"; // da sottrarre
printf("%s - %s", str, rem);
printf(" = %s\n\n", strrem(str,rem));
}
Ultima modifica effettuata da AldoBaldo il 28/08/2018 alle 9:20
ATTENZIONE! Sono un hobbista e l'affidabilità delle mie conoscenze informatiche è molto limitata. Non prendere come esempio il codice che scrivo, perché non ho alcuna formazione accademica e rischieresti di apprendere pratiche controproducenti.
Innanzitutto ti ringrazio per la risposta e il tempo speso per elaborare questa soluzione. Avevo pensato anche io di risolverlo con questo metodo, ossia di sostituire le occorrenze con degli "0" o "-" e poi andare ad eliminarle successivamente, cosa che però non mi è riuscita in quanto non sono riuscito a sostituire i caratteri nella stringa come hai fatto tu utilizzando la funzione memset().
Ho studiato la tua soluzione e la gran parte del codice l'ho capito, e l'ho rielaborato nel mio codice (cosi da capirlo ancora meglio).
Quello che non ho capito però è questo punto:
Codice sorgente - presumibilmente C/C++
// "compatta" la stringa eliminando
// gli '\0' immessi in precedenza
for( pStr=str, pRem=str; pRem-str<lStr; ++pRem )
if( *pRem ) *pStr++ = *pRem; else pRem += lRem-1;
*pStr = '\0'; // termina la stringa
L'intestazione del ciclo FOR l'ho capita, ma quella del controllo no.
Ultima modifica effettuata da comtel il 28/08/2018 alle 12:31
Avete la funzione di libreria strstr, il numero di caratteri residui è lunghezza_stringa - (lunghezza_sotto stringa * numero_verificato_match) il numero massimo di match lo sapete a priori, potete mettere gli inizi di stringa in un array e poi copiare la stringa.
Comunque il numero minimo di copie in memoria è il numero di caratteri da non rimuovere....
Ci son due coccodrilli... anzi, no, due puntatori che tengono traccia l'uno (pStr) dell'avanzamento del punto nel quale vengono copiati i caratteri da tenere, l'altro (pRem) dell'avanzamento del punto dal quale vengono prelevati i caratteri da copiare (tutti tranne gli '\0').
Inizialmente entrambi i puntatori combaciano con l'indirizzo d'inizio della stringa dalla quale rimuovere la sottostringa. Il ciclo procede fino a che la differenza tra il puntatore "di prelievo" e quello "di destinazione" è minore della lunghezza della stringa str, ovvero fino a che si arriva in fondo alla stringa stessa.
Il puntatore pRem NORMALMENTE avanza di una posizione ad ogni ciclo (++pRem), MA quando incontra uno '\0' ("else", ovvero !(*pRem)) avanza quanto basta per superare d'un botto l'intera serie degli '\0' immessi da una delle chiamate a memset(), cioè di lRem caratteri. E' vero che trovi scritto lRem-1, però bisogna tenere presente che dopo essere stato "spinto in avanti" di lRem-1 posizioni, pRem viene "spinto in avanti" di un'ulteriore posizione per via del ++pRem tra le parentesi del for.
In altre parole, più schematicamente...
Codice sorgente - presumibilmente C/C++
finche' non e' finita la stringa str
se *pRem non è '\0'
copia *pRem in *pStr
entrambi i puntatori avanzano di una posizione
altrimenti (se *pRem e' '\0')
non viene copiato nulla
pStr resta dov'e'
pRem avanza di lRem posizioni
Secondo me è più conveniente rispetto alla soluzione con l'array di int per conservare le posizioni delle parti da eliminare, anche perché in questo modo non serve allocare/deallocare memoria, e si evita la possibilità degli errori potenzialmente correlati all'uso della memoria dinamica.
Non sono in grado di esprimere valutazioni ragionate (non ho le competenze necessarie), ma "a spanne" mi sa anche che col metodo che ho usato io si risparmiano un po' di "risorse".
ATTENZIONE! Sono un hobbista e l'affidabilità delle mie conoscenze informatiche è molto limitata. Non prendere come esempio il codice che scrivo, perché non ho alcuna formazione accademica e rischieresti di apprendere pratiche controproducenti.
Ci son due coccodrilli... anzi, no, due puntatori che tengono traccia l'uno (pStr) dell'avanzamento del punto nel quale vengono copiati i caratteri da tenere, l'altro (pRem) dell'avanzamento del punto dal quale vengono prelevati i caratteri da copiare (tutti tranne gli '\0').
Inizialmente entrambi i puntatori combaciano con l'indirizzo d'inizio della stringa dalla quale rimuovere la sottostringa. Il ciclo procede fino a che la differenza tra il puntatore "di prelievo" e quello "di destinazione" è minore della lunghezza della stringa str, ovvero fino a che si arriva in fondo alla stringa stessa.
Il puntatore pRem NORMALMENTE avanza di una posizione ad ogni ciclo (++pRem), MA quando incontra uno '\0' ("else", ovvero !(*pRem)) avanza quanto basta per superare d'un botto l'intera serie degli '\0' immessi da una delle chiamate a memset(), cioè di lRem caratteri. E' vero che trovi scritto lRem-1, però bisogna tenere presente che dopo essere stato "spinto in avanti" di lRem-1 posizioni, pRem viene "spinto in avanti" di un'ulteriore posizione per via del ++pRem tra le parentesi del for.
In altre parole, più schematicamente...
Codice sorgente - presumibilmente C/C++
finche' non e' finita la stringa str
se *pRem non è '\0'
copia *pRem in *pStr
entrambi i puntatori avanzano di una posizione
altrimenti (se *pRem e' '\0')
non viene copiato nulla
pStr resta dov'e'
pRem avanza di lRem posizioni
Secondo me è più conveniente rispetto alla soluzione con l'array di int per conservare le posizioni delle parti da eliminare, anche perché in questo modo non serve allocare/deallocare memoria, e si evita la possibilità degli errori potenzialmente correlati all'uso della memoria dinamica.
Non sono in grado di esprimere valutazioni ragionate (non ho le competenze necessarie), ma "a spanne" mi sa anche che col metodo che ho usato io si risparmiano un po' di "risorse".
Nemmeno io ho ancora del tutto le competenze necessarie, ma secondo me è una buona soluzione. Davvero. Grazie mille per l'ulteriore spiegazione, cercherò di integrarla nella mia soluzione !
Mi accorgo or ora che usare quel memset() è uno "spreco", nel senso che basta "segnare" con '\0' il solo primo carattere di ogni sottostringa da eliminare trovata. Non so quanto possa migliorare l'efficienza, però sprecare non è mai una bella cosa, come regola di vita.
//"compatta" la stringa eliminando le sottostringhe
// segnalate dagli '\0' immessi in precedenza
for( pStr=str, pRem=str; pRem-str<lStr; ++pRem )
if(*pRem )*pStr++=*pRem; else pRem += lRem-1;
*pStr ='\0'; // termina la stringa
}
}
returnstr; // restituisce l'indirizzo ricevuto in str
}
// Esempio d'uso
int main(){
char str[]="acacsssdstgfdfgdacacddf";
const char rem[]="ac"; // da sottrarre
printf("%s - %s", str, rem);
printf(" = %s\n\n", strrem(str,rem));
}
ATTENZIONE! Sono un hobbista e l'affidabilità delle mie conoscenze informatiche è molto limitata. Non prendere come esempio il codice che scrivo, perché non ho alcuna formazione accademica e rischieresti di apprendere pratiche controproducenti.
Mi accorgo or ora che usare quel memset() è uno "spreco", nel senso che basta "segnare" con '\0' il solo primo carattere di ogni sottostringa da eliminare trovata. Non so quanto possa migliorare l'efficienza, però sprecare non è mai una bella cosa, come regola di vita.
Perdonatemi se riapro la discussione con questa ulteriore domanda, ma con quella soluzione proposta non si evitano gli spostamenti di memoria eccessivi. Del tipo che andiamo a sostituire le occorrenze sella sottostringa nella stringa principale, e poi quando si va a compattare la stringa principale, la andiamo a compattare passo passo, cosi che l'ultima porzione di memoria verrà spostata N volte quante sono le occorrenze trovate. Correggetemi se sto sbagliando.