2010-05-10 32 views
5

C mi disturba con la gestione delle stringhe. Ho un pseudocodice come questo nella mia mente:Trovare elementi univoci in un array di stringhe in C

char *data[20]; 

char *tmp; int i,j; 

for(i=0;i<20;i++) { 
    tmp = data[i]; 
    for(j=1;j<20;j++) 
    { 
    if(strcmp(tmp,data[j])) 
     //then except the uniqueness, store them in elsewhere 
    } 
} 

Ma quando ho codificato questo i risultati sono stati male (ho gestito tutta la roba di memoria, piccole cose, ecc) Il problema è nel secondo ciclo, ovviamente:. D . Ma non posso pensare a nessuna soluzione. Come trovo le stringhe uniche in una matrice.

Immissione di esempio: abc def abc ab deg immesso univoci: abc def ab deg deg dovrebbe essere trovato.

+0

L'ordinamento iniziale dell'array consente di ottenere modi lunghi. Quindi basta scorrere le stringhe e se la stringa corrente differisce dalla stringa precedente, è unica e puoi memorizzarla altrove. – WhirlWind

+0

il problema è che ho bisogno delle posizioni esatte. Sai come in questo: ingresso: abc def abe abc def deg entrato quelle uniche: abc def abe deg se ho risolto la matrice mi metterò quelle uniche come quella: abc def Abe deg Questo non è quello che ho voglio che abbia bisogno anche dei luoghi. – LuckySlevin

+4

Quindi creare una matrice di puntatori o una matrice di indici di matrice nell'array iniziale che si ordina, invece di ordinare l'array iniziale. – WhirlWind

risposta

6

È possibile utilizzare qsort per forzare i duplicati uno accanto all'altro. Una volta ordinati, devi solo confrontare le voci adiacenti per trovare i duplicati. Il risultato è O (N log N) piuttosto che (credo) O (N^2).

Ecco la versione di pranzo 15 minuti senza alcun controllo di errore:

typedef struct { 
    int origpos; 
    char *value; 
    } SORT; 

    int qcmp(const void *x, const void *y) { 
    int res = strcmp(((SORT*)x)->value, ((SORT*)y)->value); 
    if (res != 0) 
     return res; 
    else 
     // they are equal - use original position as tie breaker 
     return (((SORT*)x)->origpos - ((SORT*)y)->origpos); 
    } 

    int main(int argc, char* argv[]) 
    { 
    SORT *sorted; 
    char **orig; 
    int i; 
    int num = argc - 1; 

    orig = malloc(sizeof(char*) * (num)); 
    sorted = malloc(sizeof(SORT) * (num)); 

    for (i = 0; i < num; i++) { 
     orig[i] = argv[i + 1]; 
     sorted[i].value = argv[i + 1]; 
     sorted[i].origpos = i; 
     } 

    qsort(sorted, num, sizeof(SORT), qcmp); 

    // remove the dups (sorting left relative position same for dups) 
    for (i = 0; i < num - 1; i++) { 
     if (!strcmp(sorted[i].value, sorted[i+1].value)) 
      // clear the duplicate entry however you see fit 
      orig[sorted[i+1].origpos] = NULL; // or free it if dynamic mem 
     } 

    // print them without dups in original order 
    for (i = 0; i < num; i++) 
     if (orig[i]) 
      printf("%s ", orig[i]); 

    free(orig); 
    free(sorted); 
    } 
+0

lo so. Non voglio un array ordinato e fare il lavoro. Ho bisogno di questi con luoghi che conosci. Sai come in questo: input: abc def abc def deg introdotti quelli unici: abc def abe deg se ho ordinato la matrice otterrò quelli unici come quello: abc abe def deg Questo non è quello che voglio ho bisogno delle posizioni anche. – LuckySlevin

+1

Non credo che Mark lo sapesse, in realtà, dal momento che non ne hai parlato nella tua domanda. – WhirlWind

+0

Ecco perché sto chiedendo questo :). Conosco già l'ordinamento e il controllo degli elementi adiacenti. Ma questo non risolve il mio problema. – LuckySlevin

0

Potrebbe essere che il test è se (strcmp (questo, quello)), che avrà successo se i due sono diversi? ! strcmp è probabilmente quello che vuoi lì.

+0

no provato anche in questo modo. grazie duro. – LuckySlevin

5
char *data[20]; 
int i, j, n, unique[20]; 

n = 0; 
for (i = 0; i < 20; ++i) 
{ 
    for (j = 0; j < n; ++j) 
    { 
     if (!strcmp(data[i], data[unique[j]])) 
      break; 
    } 

    if (j == n) 
     unique[n++] = i; 
} 

Gli indici della prima occorrenza di ciascuna stringa unica dovrebbero essere in unico [0..n-1] se ho fatto questo diritto.

+0

che sembra davvero interessante, ci proverò. – LuckySlevin

2

Perché si avvia il secondo ciclo da 1?

Si dovrebbe avviarlo da i + 1. cioè

for(j=i+1;j<20;j++) 

Come se l'elenco è

abc 
def 
abc 
abc 
lop 

poi

quando i == 4

tmp = "LOP"

ma poi inizia la seconda ciclo che è da 1 a 19. Ciò significa che otterrà un valore di 4 anche in una fase, e quindi

data [4], che è "lop", sarà uguale a tmp. Quindi anche se "lop" è univoco ma verrà contrassegnato come ripetuto.

Spero che sia stato utile.

+2

Questo non è sicuramente il problema principale. Still O (n^2) –

+0

@Terry: grazie –

+1

Questo dipende molto dalla tua definizione di "problema principale". Questa risposta ha identificato un problema di correttezza, che è più grave di un problema di prestazioni. – caf

1

Pensa un po 'di più al tuo problema: quello che vuoi veramente è guardare le stringhe PRECEDENTI per vedere se l'hai già visto. Pertanto, per ogni stringa n, confrontarla con le stringhe 0 tramite n-1.

print element 0 (it is unique) 
for i = 1 to n 
    unique = 1 
    for j = 0 to i-1 (compare this element to the ones preceding it) 
    if element[i] == element[j] 
     unique = 0 
     break from loop 
    if unique, print element i 
Problemi correlati