Comment calculer la différence entre deux ensembles en C?

Trier les tableaux A et B de
le résultat sera en C
laissez A - le premier elem d'un
Soit B - le premier elem de Puis:
1) Pendant que A 2) Pendant que A> B: B = Next elem de 3) Si A = B: A = Elem Suivant de A et B = Elem Suivant de B
4) Si B va à la fin: insérez le reste de A dans C et arrêtez de
5) Si un mot se termine: arrêtez

Pour les ensembles plus importants, je vous suggère de trier les chiffres et de les utiliser en émulant le code sur http://www.cplusplus.com/reference/algorithm/set_difefence/ qui serait O (n * logn), mais puisque les tailles de jeu sont si petites, la solution donnée par Brian semble bien même si elle est bien théoriquement plus lent à O (n ^ 2).

Les éléments suivants supposent que les ensembles sont stockés sous forme de conteneur trié (comme STD :: Set Set).

Il existe un algorithme commun pour la fusion de deux listes ordonnées pour produire un tiers. L'idée est que lorsque vous regardez les têtes des deux listes, vous pouvez déterminer quel est l'extrait inférieur, et l'ajoutez à la queue de la sortie, puis répétez.

Il y a des variantes qui détectent le cas où les deux têtes sont égales et le traitent spécialement. Définir des intersections et des syndicats sont des exemples de cela.

Avec une différence asymétrique définie, le point clé est que pour A-B, lorsque vous extrayez la tête de B, vous le jetez. Lorsque vous extrayez la tête de A, vous l'ajoutez à l'entrée sauf si la tête de B est égale, auquel cas vous extrayez-le aussi et jetez les deux.

Bien que cette approche soit conçue pour les structures de données d'accès séquentielles (et le stockage de bande, etc.), il est parfois très utile de faire la même chose pour une structure de données d'accès aléatoire tant qu'il est raisonnablement efficace d'y accéder séquentiellement. Et vous n'avez pas nécessairement d'extraire des choses pour réel - vous pouvez faire la copie et la pas.

Le point clé est que vous traversez les entrées séquentiellement, en examinant toujours la valeur restante la plus basse, de sorte que (si les entrées n'ont pas de duplicate), vous ferez les éléments correspondants. Vous savez donc toujours si votre prochaine valeur la plus basse à gérer est un élément d'un sans correspondance en B et l'élément de B sans correspondance dans A, ou un élément égal à la fois A et B.

Plus généralement, l'algorithme de la différence définie dépend de la représentation de l'ensemble. Par exemple, si l'ensemble est représenté sous la forme d'un vecteur bit, ce qui précède serait surcommode et lent - vous venez de boucler à travers les vecteurs faisant des opérations sur le bitwise. Si l'ensemble est représenté sous forme de hashtable (comme dans le TR1 Unommked_sed_set), ce qui précède est incorrect car il nécessite des entrées commandées.

Si vous avez votre propre code d'arbre binaire que vous utilisez pour les ensembles, une bonne option consiste à convertir les deux arbres en listes liées, à utiliser sur les listes, puis à convertir la liste résultante à un arbre parfaitement équilibré. La différence relative à la liste liée est très simple et les deux conversions sont réutilisables pour d'autres opérations similaires.

Modifier

sur la complexité - à l'aide de ces algorithmes commandés en forme de fusion est O (n) à condition que vous puissiez effectuer les traverser dans l'ordre dans O (n). La conversion d'une liste et de son dos est également O (n) car chacune des trois étapes est O (n) - arborescente, différence et liste-liste.

Tree-to-List fait essentiellement une travertielle de profondeur, déconstruisant l'arbre comme ça va. Il y a une astuce pour faire de cette itératif, stocker la "pile" dans les nœuds à manipulation partielle - changer un pointeur à gauche dans un point de parent juste avant de passer à l'enfant gauche. C'est une bonne idée si l'arbre peut être grand et déséquilibré.

Conversion d'une liste en un arbre implique essentiellement une première traversée d'un arborescence imaginaire (basée sur la taille, connue du début) le construisant pour le réel comme vous allez. Si un arbre a 5 nœuds, par exemple, vous pouvez dire que la racine sera nœud 3. Vous recursez pour créer un sous-arbre à deux nœuds à gauche, puis saisissez l'élément suivant de la liste pour cette racine, puis recueille pour construire une deux -Node sous-arbre à droite.

La conversion de liste à arborescence ne doit pas nécessairement être mise en œuvre itérative - la récursive est une amende, car le résultat est toujours parfaitement équilibré. Si vous ne pouvez pas gérer la profondeur de la restauration du journal N, vous ne pouvez certainement pas gérer l'arbre complet de toute façon.