在C中查找字符串数组中的唯一元素

Question

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 def abe abc def deg输入唯一的输入:应找到abc def abe deg.

Answer 1

您可以使用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 );
  }

Answer 2

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

如果我这样做的话,每个唯一字符串第一次出现的索引应该是唯一的[0..n-1].