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

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

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

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

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

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

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

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

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

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

EDIT

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

Tree-to-list в основном выполняет обход в глубину, деконструируя дерево по мере продвижения. Есть трюк, позволяющий сделать этот процесс итеративным: хранить "стек" в частично обработанных узлах - изменение указателя на левого ребенка в указатель на родителя непосредственно перед тем, как вы перейдете к левому ребенку. Это хорошая идея, если дерево может быть большим и несбалансированным.

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

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

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

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

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

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

сортировка массивов A и B
результат будет на C
let a - первый элемент A
пусть b - первый элемент B
затем:
1) пока a 2) пока a> b: b = следующий элемент B
3) если a = b: a = следующий элемент A и b = следующий элемент B
4) если b доходит до конца: вставьте остаток A в C и остановитесь
5) если a доходит до конца: стоп