Encontrar elementos únicos en una matriz de cadenas en C

C me molesta con su manejo de cadenas. Tengo un pseudocódigo como esto en mi mente:Encontrar elementos únicos en una matriz de cadenas en 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 
    } 
}

Pero cuando codifiqué esto, los resultados fueron malos (que manejé todo el material de memoria, pequeñas cosas, etc.) El problema está en el segundo bucle, obviamente:. D . Pero no puedo pensar en ninguna solución. ¿Cómo encuentro cadenas únicas en una matriz?

Ejemplo de entrada: abc def abe abc def deg ingresado únicos: abc def abe deg se debe encontrar.

Fuente

2010-05-10 LuckySlevin

La ordenación de la matriz primero le llevará un largo camino. A continuación, simplemente itere sobre las cadenas, y si la cadena actual difiere de la cadena anterior, es única y puede almacenarla en otro lugar. – WhirlWind

el problema es que necesito las ubicaciones exactas. Usted sabe como en esto: entrada: abc def abe abc def deg ingresado únicos: abc def abe deg si ordeno la matriz obtendré unos únicos así: abc abe def deg Esto no es lo que quiero también necesito las ubicaciones. – LuckySlevin

A continuación, cree una matriz de punteros o una matriz de índices de matriz en la matriz inicial que ordene, en lugar de ordenar la matriz inicial. – WhirlWind

Puede usar qsort para forzar los duplicados uno al lado del otro. Una vez ordenado, solo necesita comparar las entradas adyacentes para encontrar duplicados. El resultado es O (N log N) en lugar de (creo) O (N^2).

Aquí está la versión de la hora del almuerzo de 15 minutos con ninguna comprobación de errores:

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); 
    }

Fuente

2010-05-10 16:44:14

lo sé. No quiero una matriz ordenada y hacer el trabajo. Necesito estos con ubicaciones que conoces. Ya sabes como en esto: entrada: abc def abe abc def deg ingresado únicos: abc def abe deg si clasifico la matriz obtendré unos únicos así: abc abe def deg Esto no es lo que quiero, necesito las ubicaciones también. – LuckySlevin

No creo que Mark lo supiera, en realidad, ya que no lo mencionó en su pregunta. – WhirlWind

Es por eso que estoy preguntando esto :). Ya sé ordenar y verificar elementos adyacentes. Pero eso no soluciona mi problema. – LuckySlevin

Podría ser que la prueba es si (strcmp (esto, eso)), que tendrá éxito si los dos son diferentes? ! strcmp es probablemente lo que quieres allí.

Fuente

2010-05-10 16:44:52

no lo intenté también. Gracias duro. – LuckySlevin

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; 
}

Los índices de la primera aparición de cada cadena única debe estar en singular [0..n-1] si lo hacía la derecha.

Fuente

2010-05-10 16:57:57 kolbyjack

que parece realmente interesante, intentaré esto. – LuckySlevin

¿Por qué estás comenzando el segundo ciclo desde 1?

Debería iniciarlo en i + 1. es decir

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

Al igual que si la lista es

abc 
def 
abc 
abc 
lop

entonces

cuando i == 4

tmp = "LOP"

pero entonces el segundo comience el bucle que es de 1 a 19. Esto significa que obtendrá un valor de 4 también en una etapa, y luego

datos [4], que es "lop", será lo mismo que tmp. Entonces, aunque "lop" es único, se marcará como repetido.

Espero que haya sido útil.

Fuente

2010-05-10 17:10:10

Eso definitivamente no es el problema principal. Todavía O (n^2) –

@Terry: gracias –

Eso realmente depende de su definición de "problema principal". Esta respuesta ha identificado un problema de corrección, que es más grave que un problema de rendimiento. – caf

Piense un poco más sobre su problema: lo que realmente quiere hacer es mirar las cuerdas ANTERIORES para ver si ya lo ha visto. Por lo tanto, para cada cadena n, compárela con las cadenas 0 hasta 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

Fuente

2010-05-15 16:37:26 tomlogic

Encontrar elementos únicos en una matriz de cadenas en C

Respuesta

Cuestiones relacionadas