Как удалить повторяющиеся строки из массива в C?

Question

У меня есть массив строк в C и целое число, указывающее, сколько строк в массиве.

char *strarray[MAX]; 
int strcount; 

В этом массиве, самый высокий показатель (где 10 выше, чем 0) добавляется самый последний элемент и самый низкий показатель добавлен самый дальний элемент. Порядок элементов в массиве имеет значение.

Мне нужен быстрый способ проверить массив для дубликатов, удалить все, кроме самого высокого индекса, дубликата и свернуть массив.

Например:

strarray[0] = "Line 1"; 
strarray[1] = "Line 2"; 
strarray[2] = "Line 3"; 
strarray[3] = "Line 2"; 
strarray[4] = "Line 4"; 

станет:

strarray[0] = "Line 1"; 
strarray[1] = "Line 3"; 
strarray[2] = "Line 2"; 
strarray[3] = "Line 4"; 

Индекс 1 из исходного массива был удален и индексы 2, 3, и 4 скользил вниз, чтобы заполнить этот пробел.

У меня есть идея, как это сделать. Он непроверен, и я в настоящее время пытаюсь его кодировать, но только из моего слабого понимания, я уверен, что это ужасный алгоритм.

Алгоритм, представленный ниже, будет запускаться каждый раз, когда новая строка будет добавлена ​​в strarray.

Для интереса, показывая, что я пытаюсь, я буду включать предлагаемый мой алгоритм ниже:

1. Поиска всей strarray для матча ул
2. Если не подходит, ничего не делать
3. Если матч найден , поставить ул в strarray
4. Теперь у нас есть strarray с максами входа 1 дубликата
5. Добавить высокий индекс strarray строки низкого индекса временных массива строк
6. Продолжить вниз в strarray и проверить каждый элемент
7. Если дубликат найден, пропустите его
8. Если нет, добавьте его к следующему самому высокому индексу временного массива строк
9. Reverse массив строк временного и скопировать strarray

Еще раз, это не проверено (я сейчас его реализую). Я просто надеюсь, что у кого-то будет намного лучшее решение.

Порядок элементов важен, и код должен использовать язык C (а не C++). Самые низкие дубликаты индексов должны быть удалены и сохранен один самый высокий индекс.

Спасибо!

Answer 1

Типичная эффективность уникальная функция заключается в следующем:

1. Сортировка данного массива.
2. Убедитесь, что последовательных прогонов одного и того же элемента настроены так, что остается только один.

Я считаю, что вы можете использовать qsort в сочетании с strcmp для выполнения первой части; но написать эффективный remove будет все на вас.

К сожалению, у меня нет конкретных идей; это вид серой области для меня, потому что я обычно с помощью C++, где это было бы просто:

std::vector<std::string> src; 
std::sort(src.begin(), src.end()); 
src.remove(std::unique(src.begin(), src.end()), src.end); 

Я знаю, что вы не можете использовать C++, но реализация должна быть по существу то же самое.

Потому что вам нужно, чтобы сохранить первоначальный заказ, вы можете иметь что-то вроде:

typedef struct 
{ 
    int originalPosition; 
    char * string; 
} tempUniqueEntry; 

Do первого сорта относительно string, удалить уникальные наборы элементов на отсортированном множестве, то прибегают относительно originalPosition. Таким образом, вы все равно получаете O (n lg n) производительность, но вы не теряете первоначальный порядок.

EDIT2: Простой C Пример реализации std::unique:

tempUniqueEntry* unique (tempUniqueEntry * first, tempUniqueEntry * last) 
{ 
    tempUniqueEntry *result=first; 
    while (++first != last) 
    { 
    if (strcmp(result->string,first->string)) 
     *(++result)=*first; 
    } 
    return ++result; 
} 

Answer 2

Вы можете контролировать вход, как это происходит в массив? Если это так, просто сделать что-то вроде этого:

int addToArray(const char * toadd, char * strarray[], int strcount) 
{ 
    const int toaddlen = strlen(toadd); 

    // Add new string to end. 
    // Remember to add one for the \0 terminator. 
    strarray[strcount] = malloc(sizeof(char) * (toaddlen + 1)); 
    strncpy(strarray[strcount], toadd, toaddlen + 1); 

    // Search for a duplicate. 
    // Note that we are cutting the new array short by one. 
    for(int i = 0; i < strcount; ++i) 
    { 
     if (strncmp(strarray[i], toaddlen + 1) == 0) 
     { 
      // Found duplicate. 
      // Remove it and compact. 
      // Note use of new array size here. 
      free(strarray[i]); 
      for(int k = i + 1; k < strcount + 1; ++k) 
       strarray[i] = strarray[k]; 

      strarray[strcount] = null; 
      return strcount; 
     } 
    } 

    // No duplicate found. 
    return (strcount + 1); 
} 

Вы всегда можете использовать вышеуказанную функцию зацикливание по элементам существующего массива, создание нового массива без дубликатов.

PS: Если вы делаете этот тип операции много, вы должны отойти от массива в качестве своей структуры хранения и вместо этого использовать связанный список. Они намного эффективнее для удаления элементов из другого места, кроме конца.

Answer 3

Я не совсем понимаю, предлагаемый ваш алгоритм (я не понимаю, что значит добавить строку индекса на шаге 5), но то, что я хотел бы сделать это:

unsigned int i; 
for (i = n; i > 0; i--) 
{ 
    unsigned int j; 

    if (strarray[i - 1] == NULL) 
    { 
     continue; 
    } 

    for (j = i - 1; j > 0; j--) 
    { 
     if (strcmp(strarray[i - 1], strarray[j - 1]) == 0) 
     { 
      strarray[j - 1] = NULL; 
     } 
    } 
} 

Тогда вы просто нужно отфильтровать нулевые указатели из вашего массива (который я оставлю как упражнение).

Другой подход состоял бы в том, чтобы итератировать назад по массиву и вставить каждый элемент в (сбалансированное) двоичное дерево поиска по мере продвижения. Если элемент уже находится в дереве двоичного поиска, отметьте элемент массива (например, установите элемент массива на NULL) и перейдите к нему. Когда вы обработали весь массив, отфильтруйте отмеченные элементы, как и раньше. Это будет немного больше накладных расходов и будет потреблять больше места, но его время работы будет O (n log n) вместо O (n^2).

Answer 4

Сортировка массива с помощью алгоритма, как qsort (man 3 qsort в терминале, чтобы увидеть, как она должна быть использована), а затем использовать функцию strcmp для сравнения строк и найти дубликаты

Если вы хотите его поддерживать первоначальный заказ вы можете использовать алгоритм сложности O (N^2), вложенный два for, первый каждый раз выбирает элемент для сравнения с другим, а второй для будет использоваться для сканирования остальной части массива, чтобы найти, является ли выбранный элемент дублировать.