Как рассчитать разницу между двумя наборами в C?

Question

У меня есть два массива, скажем A и B с | A | = 8 и | B | = 4. Я хочу рассчитать установленную разницу A-B. Как я могу продолжить? Обратите внимание, что в любом из наборов нет повторяющихся элементов.

Редактировать: Большое вам спасибо за несметное количество элегантных решений. Поскольку я участвую в стадии прототипирования своего проекта, на данный момент я реализовал простейшее решение, рассказанное Брайаном и Оуэном. Но я действительно ценю умное использование структур данных, как предлагалось здесь остальными, даже если я не компьютерный ученый, а инженер и никогда не изучал структуры данных как курс. Похоже, что пришло время, я действительно должен начать читать CLRS, который я откладывал на некоторое время :) Спасибо еще раз!

Answer 1

Итерация по каждому элементу А, если каждый из этих элементов не в B, а затем добавить их к новому набору C.

Answer 2

Это зависит от того, как вы хотите, чтобы представить свои наборы, но если они просто тогда вы можете использовать побитовые операторы, например D = A & ~B; даст вам заданную разницу A-B, если множества соответствуют целочисленному типу. Для больших наборов вы можете использовать массивы целочисленных типов и итерации, например.

for (i = 0; i < N; ++i) 
{ 
    D[i] = A[i] & ~B[i]; 
} 

Answer 3

сортировки массивов А и В
результате будут в C
пусть - первый эль из A
Пусть B - первый эль из B
затем:
1) в то время как < b: вставить a в C и a = следующий элемент A
2) в то время как a> b: b = следующий элемент B
3) если a = b: a = следующий элемент A и b = следующий элемент B
4) если b заканчивается: insert r Текущая из А в С и остановить
5), если идет до конца: остановка

Answer 4

Для больших наборов я предложил сортировки чисел и итерация через них путем эмуляции кода на http://www.cplusplus.com/reference/algorithm/set_difference/, который будет O (N * LogN), но поскольку размеры множества настолько малы, решение, данное Брайаном, кажется прекрасным, хотя оно теоретически медленнее в O (N^2).

Answer 5

Предполагается, что наборы хранятся в виде сортированного контейнера (как это делает std :: set).

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

Существуют варианты, которые определяют случай, когда две головы равны, и рассматривайте это специально. Примерами этого являются пересечения и союзы.

С установленной асимметричной разницей ключевым моментом является то, что для A-B, когда вы извлекаете головку B, вы отбрасываете ее. Когда вы извлекаете головку A, вы добавляете ее на вход , если голова B не равна, и в этом случае вы также извлекаете это и отбрасываете оба.

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

Ключевым моментом является то, что вы последовательно входите в входы, всегда смотря на самое нижнее оставшееся значение, так что (если входы не имеют дубликатов), вы будете сопоставлять элементы. Поэтому вы всегда знаете, является ли ваше следующее нижнее значение для обработки - это элемент из A без соответствия в B и элемент в B без совпадения в A или элемент, равный как в A, так и B.

В целом, алгоритм для заданной разности зависит от представления множества. Например, если набор представлен как бит-вектор, вышеперечисленное будет слишком сложным и медленным - вы просто пропустите векторы, выполняющие побитовые операции. Если набор представлен как хэш-таблица (как в tr1 unordered_set), это неверно, поскольку для него требуются упорядоченные входы.

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

EDIT

О сложности - с помощью этих заказанных алгоритмов объединения типа О (п) при условии, что вы можете сделать с обходами в заказе в O (N). Преобразование в список и обратно также равно O (n), так как каждый из трех шагов - это O (n) - древовидный список, разность заданий и список для дерева.

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

Преобразование списка в дерево в основном предполагает обход глубины воображаемого дерева (основанный на размере, известном с самого начала), строя его по-настоящему, когда вы идете. Например, если дерево имеет 5 узлов, вы можете сказать, что корневой узел будет узлом 3. Вы рекурсивно создаете левое поддерево с двумя узлами, затем возьмите следующий элемент из списка для этого корня, а затем рекурсивно создадите два -node прямое поддерево.

Преобразование из списка в дерево не должно быть реализовано итеративно - рекурсивный результат хорош, так как результат всегда идеально сбалансирован. Если вы не можете обработать глубину рекурсии log n, вы почти наверняка не сможете обработать полное дерево в любом случае.

Answer 6

Реализовать заданный объект в C. Вы можете сделать это, используя хеш-таблицу для базового хранилища. Это, очевидно, нетривиальное упражнение, но существует несколько решений OpenSource. Затем вам просто нужно добавить все элементы A, а затем перебрать B и удалить все элементы вашего набора.

Ключевым моментом является использование правильной структуры данных для задания.