Нахождение уникальных элементов в массиве строк в C

Question

Нахождение уникальных элементов в массиве строк в C

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

Но когда я кодировал это, результаты были плохи. (Я обработал весь материал памяти, небольшие вещи и т.д.), проблема находится во втором цикле, очевидно, :D. Но я не могу думать никакое решение. Как я нахожу уникальные строки в массиве.

Пример ввел: определение abc abe градус определения abc ввело уникальные: определение abc abe градус должно быть найдено.

5

c arrays string strcmp

задан sbi 10 May 2010 в 16:52

5 ответов

Другие вопросы по тегам:

c arrays string strcmp

Похожие вопросы:

score 5 · Answer 1

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

Индексы первого вхождения каждой уникальной строки должны быть в unique[0..n-1], если я сделал это правильно.

score 6 · Answer 2

Вы можете использовать qsort, чтобы заставить дубликаты находиться рядом друг с другом. После сортировки для поиска дубликатов достаточно сравнить соседние записи. Результат - O(N log N), а не (я думаю) O(N^2).

Вот 15-минутная обеденная версия без проверки ошибок:

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

score 0 · Answer 3

Может быть, ваш тест if (strcmp (this, that)) будет успешным, если эти два значения различны? !strcmp - это, вероятно, то, что вам нужно.

score 2 · Answer 4

Почему вы начинаете второй цикл с 1?

Вы должны начать его с i+1. Т.е.

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

Например, если список

abc
def
abc
abc
lop

то

when i==4

tmp="lop"

но потом начинается второй цикл, который с 1 по 19. Это означает, что на каком-то этапе он тоже получит значение 4, и тогда

data[4], которое является "lop", будет таким же, как tmp. Таким образом, хотя "lop" уникален, он будет помечен как повторяющийся.

Надеюсь, это было полезно.

score 1 · Answer 5

Подумайте немного о своей проблеме - на самом деле вам нужно посмотреть на ПРЕДЫДУЩИЕ строки, чтобы увидеть, видели ли вы это уже. Итак, для каждой строки n сравните ее со строками от 0 до 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