Есть ли простой способ удалить элементы из массива?

Question

У меня есть два списка.

char *name[] = {"RGS", "O", "NRGY", "SIG", "BML-O", "BHI", "KSU", "ORN"}; 
char *name_to_remove[] = {"RGS", "O", "NRGY"}; 

Есть ли эффективный способ взять список предметов и удалить его из другого списка? Я внедрил свою собственную версию, но считаю ее довольно неэффективной. Он в основном делает копию списка имен, а затем использует цикл вложенных циклов, который проходит через дублированное имя & name_to_remove списки и отмечает любой элемент, который повторяет «удалить». Наконец, я просматриваю список и копирую все элементы, кроме тех, у которых есть значения «remove». Это ужасно уродливо, и я подозреваю, что это неэффективно. Проблема, с которой у меня возникают проблемы (не рассматривали ее раньше), я не уверен, возможно ли удалить элемент из массива, если массив является фиксированным размером в памяти, поэтому я первоначально попытался изменить значения, а затем добавьте значения в новый массив (тот же размер, что и оригинал - размер массива элементов, которые я хочу удалить).

Я не вижу лучшего способа сделать это, memcmp казался многообещающим, потому что он может сравнивать два списка, но я не мог понять, как он подходит. Я знаю, C не Python, но вот как я это делаю чисто в питоне:

for item in name_to_remove: 
    name_copy.remove(item) 

может быть, под сценой, команда питона делает столько петель, как я делаю, но я думал, что спросить.

Answer 1

Ответ на этот вопрос заключается в использовании соответствующей структуры данных. Список Python определенно не реализован как простой массив C строк (просто потому, что вы можете хранить объекты разных типов в списке Python). Таким образом, структура данных, которую вы ищете, вероятно, либо linked list, либо hash table.

Answer 2

вы можете создать хэш-карту, затем пропустить один массив и проверить через mapOfRemovableWords.contains(words[i]) и использовать это, чтобы решить, следует ли скопировать элемент в новый массив (или сам по себе).

Вы также можете отсортировать оба массива, а затем пропустить их в одно и то же время. Используйте тот факт, что если вы находитесь в положении, когда слово больше, чем текущее слово в другом списке, то оно не входит в другой список. Вы повторяете одно, а затем решаете, нужно ли повторять другую, и повторяйте, пока вы полностью не перейдете к обоим.

Answer 3

Я предполагаю, что версия python не намного эффективнее, чем ваш код.

Это, конечно, может улучшить вашу реализацию. Помните, что массив C - это всего лишь блок памяти с кучей указателей на начало строк. Поскольку вы не создаете новые строки, вы всегда можете повторно использовать указатели строк.

Концептуально перейди по массиву, установив указатель на нуль, если значение находится в списке для удаления. Затем используйте malloc() для создания нового массива соответствующего размера. Переверните старый массив, скопировав ненулевые указатели на новый массив.

Таким образом, у вас есть 2 итерации цикла и один malloc.

Answer 4

Его в основном делает копию списка имен, а затем с помощью вложенного цикла, который проходит через оба дублированного имя & списки name_to_remove и отмечает любой элемент, который повторяется на «удалить». Наконец, я просматриваю список и копирую все элементы, кроме тех, у которых есть значения «remove».

Вместо того, чтобы что-либо маркировка, вы можете просто скопировать любой предмет, который вы найдете в name что в name_to_remove не и сохранить его в новом массиве, а затем мусор старого name массива.

Answer 5

Если вы выберете первый массив во время компиляции, то его размер будет фиксированным, и я верю, что впоследствии не удастся восстановить любую из памяти путем «удаления» выбранных элементов. Я бы предложил либо реализовать связанный список, который вы можете динамически распределить, а затем free() частей всякий раз, когда вы хотите удалить элемент, или, еще лучше, более эффективную структуру данных, такую ​​как двоичное дерево поиска.

Answer 6

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

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

#define ARR_SIZE(array) sizeof(array)/sizeof(const char *) 

int compare (const void * a, const void * b) { 
    return strcmp(*((const char**)a), *((const char**)b)); 
} 

int main(void) { 
    const char *name[] = {"RGS", "O", "NRGY", "SIG", "BML-O", "BHI", "KSU", "ORN"}; 
    const char *name_to_remove[] = {"RGS", "O", "NRGY"}; 
    int i = 0, j = 0; 
    qsort(name, ARR_SIZE(name), sizeof(const char*), compare); 
    qsort(name_to_remove, ARR_SIZE(name_to_remove), sizeof(const char*), compare); 
    while (i != ARR_SIZE(name) && j != ARR_SIZE(name_to_remove)) { 
      int diff = strcmp(name[i], name_to_remove[j]); 
      if (diff == 0) { 
        name[i] = NULL; 
        i++; 
        j++; 
      } else if (diff < 0) { 
        i++; 
      } else { 
        j++; 
      } 
    } 
    for (i = 0 ; i != ARR_SIZE(name) ; i++) 
      if (name[i]) 
        printf("%s\n", name[i]); 
    return 0; 
}