Как удалить повторяющиеся строки из массива в 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 смещены внизчтобы заполнить пробел.

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

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

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

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

Выполните первую сортировку по 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

Я не совсем понимаю предложенный вами алгоритм (я не понимаю, что значит добавить строку в индекс на шаге 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 3

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

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 4

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

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