Lié la mise en œuvre en utilisant des noeuds factices

Question

Je travaille sur un projet où je dois union et intersecter deux ensembles. J'utilise la liste liée pour chaque ensemble avec des noeuds factices. C'est comme ça que j'initialise ma série LL de jeux

public Set() { 
top = new Node(Integer.MIN_VALUE, new Node(Integer.MAX_VALUE, null)); 
} //end Set 

Et c'est comme ça que j'insère des objets.

public void insert(int item) { 
Node prev = top; 
Node curr = top.next; 

while(curr.item < item) { 
    prev = curr; 
    curr = curr.next; 
} 
prev.next = new Node(item, curr); 
size++; 
} // insert 

Maintenant, je trouve difficile d'obtenir une union ou une intersection de deux ensembles. C'est ce que j'ai en tête pour l'intersection.

public Set intersection(Set setB) { 
Set setC = new Set(); 
//loop over both sets and if both have same value add it otherwise 
// get to the next node in both sets. 

Ma question est, suis-je logiquement correct avec l'intersection pseudocode? Mon pseudo-syndicat est risible. Quelqu'un peut-il s'il vous plaît me guider si ce problème?

Answer 1

Votre idée échouera pour cette entrée simple:

1 2 
2 3 

Votre idée:

//loop over both sets and if both have same value add it otherwise 
// get to the next node in both sets. 

• Première itération - nous avons 1 et 2, pas la même valeur, donc nous arrivons à la suivant dans les deux ensembles
• Deuxième itération - nous avons 2 et 3, pas la même valeur, donc se rendre à la prochaine
• Fin

Qu'est-ce que vous avez réellement besoin est:

• Le non-concordance, avance que la liste avec élément inférieur
• Le match ajouter à entraîner et de faire progresser à la fois (ou pour supprimer les doublons, continuer à avancer les deux tant que la même valeur est répétée)

---

Pour l'union, l'idée est très similaire:

• en cas d'incompatibilité, ajoutez le inférieur et avancer la liste qui contenait l'élément inférieur
• sur le match, ajouter et de faire progresser les deux (ou continuer à avancer à la fois comme tant que la même valeur est répétée)