Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Eliminare degli elementi da un array di caratteri e ricompattarlo..
Forum - C/C++ - Eliminare degli elementi da un array di caratteri e ricompattarlo..

Pagine: [ 1 2 ] Precedente | Prossimo
Avatar
comtel (Member)
Pro


Messaggi: 145
Iscritto: 08/04/2011

Segnala al moderatore
Postato alle 20:36
Lunedì, 27/08/2018
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.

Questo è il codice:

Codice sorgente - presumibilmente C++

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. char * string_del(char *, char *);
  6.  
  7. int main(int argc, char *argv[]) {
  8.         char *string = "acacrsssdstgfdfgdacacddf", *chr = "ac";
  9.         string_del(string, chr);
  10. }
  11.  
  12. char * string_del(char *string, char *chr) {
  13.         int fs_pos, sc_pos, i = 0, j = 0, *pos_array;
  14.         pos_array = (int *)calloc(0, sizeof(int));
  15.        
  16.         for(i = 0; *(string + i) != '\0'; i++) {
  17.                 if(strncmp(string + i, chr, strlen(chr)) == 0) {
  18.                         if((sc_pos + 1) == i) {
  19.                                 sc_pos = i + strlen(chr) - 1;
  20.                                 *(pos_array + j) = sc_pos;
  21.                                 j++;  
  22.                         } else {
  23.                                 fs_pos = i;
  24.                                 sc_pos = i + strlen(chr) - 1;
  25.                                
  26.                                 if(realloc(pos_array, (j)*2 + 1) != NULL) {
  27.                                         *(pos_array + j) = fs_pos;
  28.                                         *(pos_array + j + 1) = sc_pos;
  29.                                         j++;  
  30.                                 }
  31.                         }
  32.                 }
  33.         } printf("\n");
  34.  
  35.         for(i = 0; i < j; i += 2) {
  36.                 int size = *(pos_array + i + 1) - *(pos_array + i);
  37.                 char dest = *(string + *(pos_array + i));
  38.                 char src = *(string + *(pos_array + i + 1));
  39.                
  40.                 printf("DEST: %c\tSRC: %c\tSIZE: %d\n", dest, src, size);
  41.  
  42.                 // In questa sezione del codice dovrei eseguire l'eliminazione e lo spostamento degli elementi.
  43.         }
  44. }


PM Quote
Avatar
AldoBaldo (Member)
Guru


Messaggi: 699
Iscritto: 08/01/2015

Segnala al moderatore
Postato alle 1:46
Martedì, 28/08/2018
Se lo scopo è ridurre gli spostamenti di memoria io risolverei così:

Codice sorgente - presumibilmente VB.NET

  1. #include <stdio.h>
  2. #include <string.h>
  3.  
  4. //==============================================================================
  5. // Funzione strrem, "string remove"
  6. //
  7. //     char *strrem( char *str, const char *rem );
  8. //
  9. // Questa funzione si occupa di eliminare tutte le occorrenze della stringa rem
  10. // dalla stringa str. L'eliminazione avviene "sul posto", in modo distruttivo
  11. // (in uscita, str risulta modificata; il contenuto originale e' perso).
  12. //
  13. //     str     str: stringa; un puntatore a char che punta ad una stringa C
  14. //             valida (zero terminated); dopo l'elaborazione, il contenuto della
  15. //             stringa puo' risultare modificato senza possibilita' di recupero
  16. //
  17. //     rem     rem: remove; un puntatore a const char che punta ad una stringa C
  18. //             valida (zero terminated); la stringa puntata da rem non viene mai
  19. //             modificata
  20. //
  21. // Valore di ritorno: lo stesso puntatore a char passato in str.
  22. //
  23. // Note:
  24. // Non avviene alcuna elaborazione se 1) str o rem sono NULL o se 2) la
  25. // lunghezza della stringa puntata da rem supera quella della stringa puntata da
  26. // str. Richiede l'inclusione del file string.h.
  27. //==============================================================================
  28.  
  29. char *strrem( char *str, const char *rem ) {
  30.     if( str && rem ) {
  31.         size_t lStr = strlen( str );
  32.         size_t lRem = strlen( rem );
  33.  
  34.         if( lRem <= lStr ) {
  35.             char *pStr = strstr(str,rem);
  36.             const char *pRem = str;
  37.  
  38.             // in str, sostituisce con '\0'
  39.             // le sottostringhe da eliminare
  40.             while( pStr ) {
  41.                 memset( pStr, 0, lRem );
  42.                 pStr += lRem;
  43.                 pStr = strstr( pStr, rem );
  44.             }
  45.  
  46.             // "compatta" la stringa eliminando
  47.             // gli '\0' immessi in precedenza
  48.             for( pStr=str, pRem=str; pRem-str<lStr; ++pRem )
  49.                 if( *pRem ) *pStr++ = *pRem; else pRem += lRem-1;
  50.  
  51.             *pStr = '\0'; // termina la stringa
  52.         }
  53.     }
  54.  
  55.     return str; // restituisce l'indirizzo ricevuto in str
  56. }
  57.  
  58. // Esempio d'uso
  59.  
  60. int main() {
  61.     char str[] = "acacsssdstgfdfgdacacddf";
  62.     const char rem[] = "ac"; // da sottrarre
  63.     printf( "%s - %s", str, rem );
  64.     printf( " = %s\n\n", strrem(str,rem) );
  65. }


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.
PM Quote
Avatar
comtel (Member)
Pro


Messaggi: 145
Iscritto: 08/04/2011

Segnala al moderatore
Postato alle 12:28
Martedì, 28/08/2018
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++

  1. // "compatta" la stringa eliminando
  2. // gli '\0' immessi in precedenza
  3.            
  4. for( pStr=str, pRem=str; pRem-str<lStr; ++pRem )
  5.   if( *pRem ) *pStr++ = *pRem; else pRem += lRem-1;
  6.  
  7. *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
PM Quote
Avatar
TheDarkJuster (Member)
Guru^2


Messaggi: 1620
Iscritto: 27/09/2013

Segnala al moderatore
Postato alle 12:49
Martedì, 28/08/2018
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....

PM Quote
Avatar
AldoBaldo (Member)
Guru


Messaggi: 699
Iscritto: 08/01/2015

Segnala al moderatore
Postato alle 22:11
Martedì, 28/08/2018
for( pStr=str, pRem=str; pRem-str<lStr; ++pRem )
  if( *pRem ) *pStr++ = *pRem; else pRem += lRem-1;

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

  1. finche' non e' finita la stringa str
  2.     se *pRem non è '\0'
  3.         copia *pRem in *pStr
  4.         entrambi i puntatori avanzano di una posizione
  5.     altrimenti (se *pRem e' '\0')
  6.         non viene copiato nulla
  7.         pStr resta dov'e'
  8.         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.
PM Quote
Avatar
comtel (Member)
Pro


Messaggi: 145
Iscritto: 08/04/2011

Segnala al moderatore
Postato alle 17:58
Mercoledì, 29/08/2018
Testo quotato

Postato originariamente da AldoBaldo:

for( pStr=str, pRem=str; pRem-str<lStr; ++pRem )
  if( *pRem ) *pStr++ = *pRem; else pRem += lRem-1;

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

  1. finche' non e' finita la stringa str
  2.     se *pRem non è '\0'
  3.         copia *pRem in *pStr
  4.         entrambi i puntatori avanzano di una posizione
  5.     altrimenti (se *pRem e' '\0')
  6.         non viene copiato nulla
  7.         pStr resta dov'e'
  8.         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 !

PM Quote
Avatar
AldoBaldo (Member)
Guru


Messaggi: 699
Iscritto: 08/01/2015

Segnala al moderatore
Postato alle 14:25
Giovedì, 30/08/2018
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. :nono:

Codice sorgente - presumibilmente VB.NET

  1. #include <stdio.h>
  2. #include <string.h>
  3.  
  4. //==============================================================================
  5. // Funzione strrem, "string remove"
  6. //
  7. //     char *strrem( char *str, const char *rem );
  8. //
  9. // Questa funzione si occupa di eliminare tutte le occorrenze della stringa rem
  10. // dalla stringa str. L'eliminazione avviene "sul posto", in modo distruttivo
  11. // (in uscita, str risulta modificata; il contenuto originale e' perso).
  12. //
  13. //     str     str: stringa; un puntatore a char che punta ad una stringa C
  14. //             valida (zero terminated); dopo l'elaborazione, il contenuto della
  15. //             stringa puo' risultare modificato senza possibilita' di recupero
  16. //
  17. //     rem     rem: remove; un puntatore a const char che punta ad una stringa C
  18. //             valida (zero terminated); la stringa puntata da rem non viene mai
  19. //             modificata
  20. //
  21. // Valore di ritorno: lo stesso puntatore a char passato in str.
  22. //
  23. // Note:
  24. // Non avviene alcuna elaborazione se 1) str o rem sono NULL o se 2) la
  25. // lunghezza della stringa puntata da rem supera quella della stringa puntata da
  26. // str. Richiede l'inclusione del file string.h.
  27. //==============================================================================
  28.  
  29. char *strrem( char *str, const char *rem ) {
  30.     if( str && rem ) {
  31.         size_t lStr = strlen( str );
  32.         size_t lRem = strlen( rem );
  33.  
  34.         if( lRem <= lStr ) {
  35.             char *pStr = strstr(str,rem);
  36.             const char *pRem = str;
  37.  
  38.             // in str, sostituisce con '\0' l'inizio
  39.             // di ogni sottostringa da eliminare
  40.             while( pStr ) {
  41.                 *pStr = '\0';
  42.                 pStr += lRem;
  43.                 pStr = strstr( pStr, rem );
  44.             }
  45.  
  46.             // "compatta" la stringa eliminando le sottostringhe
  47.             // segnalate dagli '\0' immessi in precedenza
  48.             for( pStr=str, pRem=str; pRem-str<lStr; ++pRem )
  49.                 if( *pRem ) *pStr++ = *pRem; else pRem += lRem-1;
  50.  
  51.             *pStr = '\0'; // termina la stringa
  52.         }
  53.     }
  54.  
  55.     return str; // restituisce l'indirizzo ricevuto in str
  56. }
  57.  
  58. // Esempio d'uso
  59.  
  60. int main() {
  61.     char str[] = "acacsssdstgfdfgdacacddf";
  62.     const char rem[] = "ac"; // da sottrarre
  63.     printf( "%s - %s", str, rem );
  64.     printf( " = %s\n\n", strrem(str,rem) );
  65. }



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.
PM Quote
Avatar
comtel (Member)
Pro


Messaggi: 145
Iscritto: 08/04/2011

Segnala al moderatore
Postato alle 13:53
Sabato, 01/09/2018
Testo quotato

Postato originariamente da AldoBaldo:

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

Codice sorgente - presumibilmente VB.NET

  1. #include <stdio.h>
  2. #include <string.h>
  3.  
  4. //==============================================================================
  5. // Funzione strrem, "string remove"
  6. //
  7. //     char *strrem( char *str, const char *rem );
  8. //
  9. // Questa funzione si occupa di eliminare tutte le occorrenze della stringa rem
  10. // dalla stringa str. L'eliminazione avviene "sul posto", in modo distruttivo
  11. // (in uscita, str risulta modificata; il contenuto originale e' perso).
  12. //
  13. //     str     str: stringa; un puntatore a char che punta ad una stringa C
  14. //             valida (zero terminated); dopo l'elaborazione, il contenuto della
  15. //             stringa puo' risultare modificato senza possibilita' di recupero
  16. //
  17. //     rem     rem: remove; un puntatore a const char che punta ad una stringa C
  18. //             valida (zero terminated); la stringa puntata da rem non viene mai
  19. //             modificata
  20. //
  21. // Valore di ritorno: lo stesso puntatore a char passato in str.
  22. //
  23. // Note:
  24. // Non avviene alcuna elaborazione se 1) str o rem sono NULL o se 2) la
  25. // lunghezza della stringa puntata da rem supera quella della stringa puntata da
  26. // str. Richiede l'inclusione del file string.h.
  27. //==============================================================================
  28.  
  29. char *strrem( char *str, const char *rem ) {
  30.     if( str && rem ) {
  31.         size_t lStr = strlen( str );
  32.         size_t lRem = strlen( rem );
  33.  
  34.         if( lRem <= lStr ) {
  35.             char *pStr = strstr(str,rem);
  36.             const char *pRem = str;
  37.  
  38.             // in str, sostituisce con '\0' l'inizio
  39.             // di ogni sottostringa da eliminare
  40.             while( pStr ) {
  41.                 *pStr = '\0';
  42.                 pStr += lRem;
  43.                 pStr = strstr( pStr, rem );
  44.             }
  45.  
  46.             // "compatta" la stringa eliminando le sottostringhe
  47.             // segnalate dagli '\0' immessi in precedenza
  48.             for( pStr=str, pRem=str; pRem-str<lStr; ++pRem )
  49.                 if( *pRem ) *pStr++ = *pRem; else pRem += lRem-1;
  50.  
  51.             *pStr = '\0'; // termina la stringa
  52.         }
  53.     }
  54.  
  55.     return str; // restituisce l'indirizzo ricevuto in str
  56. }
  57.  
  58. // Esempio d'uso
  59.  
  60. int main() {
  61.     char str[] = "acacsssdstgfdfgdacacddf";
  62.     const char rem[] = "ac"; // da sottrarre
  63.     printf( "%s - %s", str, rem );
  64.     printf( " = %s\n\n", strrem(str,rem) );
  65. }




TI ringrazio tantissimo per la risposta e l'aiuto !

PM Quote
Avatar
comtel (Member)
Pro


Messaggi: 145
Iscritto: 08/04/2011

Segnala al moderatore
Postato alle 13:04
Domenica, 02/09/2018
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.

PM Quote
Pagine: [ 1 2 ] Precedente | Prossimo