Tìm các phần tử duy nhất trong một mảng chuỗi trong C

Question

C làm phiền tôi với việc xử lý chuỗi. Tôi có một giả như thế này trong tâm trí tôi:

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

Nhưng khi tôi mã này kết quả là xấu (tôi xử lý tất cả những thứ nhớ, những điều nhỏ nhặt, vv) Vấn đề là trong vòng lặp thứ hai rõ ràng là:. D . Nhưng tôi không thể nghĩ ra bất kỳ giải pháp nào. Làm cách nào để tìm chuỗi duy nhất trong một mảng.

Ví dụ nhập: abc def abe abc def deg được nhập số duy nhất: abc def abe deg sẽ được tìm thấy.

Answer 1

Bạn có thể sử dụng qsort để buộc các bản sao cạnh nhau. Sau khi sắp xếp, bạn chỉ cần so sánh các mục liền kề để tìm các bản sao. Kết quả là O (N log N) thay vì (tôi nghĩ) O (N^2).

Đây là giờ ăn trưa phiên bản 15 phút không có kiểm tra lỗi:

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

nó có thể là thử nghiệm của bạn là if (strcmp (điều này, đó)) mà sẽ thành công nếu hai là khác nhau? ! strcmp có lẽ là những gì bạn muốn ở đó.

Answer 3

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

Chỉ mục lần xuất hiện đầu tiên của mỗi chuỗi duy nhất phải là duy nhất [0..n-1] nếu tôi làm điều đó đúng.

Answer 4

Tại sao bạn bắt đầu vòng lặp thứ hai từ 1?

Bạn nên bắt đầu từ i + 1. tức là

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

Giống như nếu danh sách là

abc 
def 
abc 
abc 
lop 

sau đó

khi tôi == 4

tmp = "lop"

nhưng sau đó thứ hai bắt đầu vòng lặp mà là từ 1 đến 19. Điều này có nghĩa là nó cũng sẽ nhận được giá trị là 4 ở một giai đoạn và sau đó là

dữ liệu [4], là "lop", sẽ giống như tmp. Vì vậy, mặc dù "lop" là duy nhất nhưng nó sẽ được gắn cờ lặp đi lặp lại.

Hy vọng nó hữu ích.

Answer 5

Suy nghĩ thêm một chút về vấn đề của bạn - những gì bạn thực sự muốn làm là xem các chuỗi PREVIOUS để xem bạn đã xem nó chưa. Vì vậy, đối với mỗi chuỗi n, hãy so sánh với chuỗi 0 đến 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