Share
Setul este un tip de colecție care implementează algoritmii de bază algebrici, inclusiv unirea, intersecția, diferența și diferența simetrică. Fiecare dintre aceste algoritmi va fi explicat în detaliu în secțiunile respective.
Conceptual, seturile sunt colecții de obiecte care au adesea o anumită caracteristică. De exemplu, este posibil să avem un set care să conțină numere întregi pozitive:
[2, 4, 6, 8, 10, ...]
Și un set care conține numere întregi pozitive:
[1, 3, 5, 7, 9, ...]
Aceste două seturi nu au valori comune. Acum, luați în considerare un al treilea set care reprezintă toți factorii din numărul 100:
[1, 2, 4, 5, 10, 20, 25, 50, 100]
Având în vedere aceste seturi, putem răspunde acum la întrebarea "Ce factori din 100 sunt ciudați?", Analizând setul de numere întregi și setul de factori de 100 și văzând care valori există în ambele seturi. Dar am putea răspunde la întrebări precum: "Ce numere impare nu sunt factori de 100?" Sau "Ce cifre pozitive, chiar și ciudate, nu sunt factori de 100?"
Acest lucru nu pare foarte util, dar asta pentru că exemplul este oarecum contrivit. Imaginați-vă dacă seturile au fost fiecare angajat al unei companii și al fiecărui angajat care a absolvit antrenamentul anual obligatoriu.
Am putea răspunde cu ușurință la întrebarea "Ce angajați nu au terminat formarea obligatorie?"
Putem continua să adăugăm seturi suplimentare și să începem să răspundem la întrebări foarte complexe, cum ar fi: "Ce angajați cu normă întreagă din echipa de vânzări cărora li sa eliberat un card de credit corporativ nu au participat la formarea obligatorie privind noul proces de raportare a cheltuielilor?"
A stabilit clasa implementează IEnumerable interfață și acceptă un argument generic care ar trebui să fie un argument IComparable tip (testarea pentru egalitate este necesară pentru funcționarea algoritmilor setați).
Membrii setului vor fi prezenți într-un .NET Listă dar în practică seturile sunt adesea conținute în structuri de copaci, cum ar fi un arbore binar de căutare. Această alegere a containerului de bază afectează complexitatea diverselor algoritmi. De exemplu, folosind Listă, Conține are o complexitate de O (n), în timp ce folosirea unui arbore ar duce la O (log n) în medie.
Pe lângă metodele pe care le vom implementa, A stabilit include un constructor implicit și unul care acceptă un constructor IEnumerable de elemente pentru a popula setul cu.
clasa publica Set: IEnumerable unde T: IComparable private readonly List _items = new List (); set public () set public (elemente iterabile) AddRange (elemente); void public Add (element T); public void AddRange (numere de numar I); bool public Eliminare (element T); bool public Contine (element T); public int Count get; public Set Union (Setați altul); intersecție set public (setare altul); Setarea diferenței publice (setați altul); public Setati simetric Diferenta (setati altul); public IEnumerator GetEnumerator (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator ();
| Comportament | Adaugă articolul la set. Dacă elementul există deja în set, este aruncat un InvalidOperationException. |
| Performanţă | Pe) |
La implementarea Adăuga algoritmul, trebuie luată o decizie: setul permite trimiterea de elemente duplicate sau nu? De exemplu, având în vedere următorul set:
[1, 2, 3, 4]
Dacă apelantul încearcă să adauge valoarea a treia, setul devine:
[1, 2, 3, 3, 4]
Deși acest lucru ar putea fi acceptabil în anumite contexte, nu este vorba de comportamentul pe care îl vom implementa. Imaginați-vă un set care conține toți studenții la un colegiu local. Nu ar fi logic să permiteți aceluiași student să fie adăugat la set de două ori. De fapt, încercarea de a face acest lucru este probabil o eroare (și va fi tratată ca atare în această implementare).
Notă: Adăugarea folosește Conține Metodă
Accentsconagua
public void Adăugați (element T) if (Conține (element)) arunca noul InvalidOperationException ("Elementul există deja în set"); _items.Add (element); | Comportament | Adaugă elemente multiple în set. Dacă există vreun membru al enumeratorului de intrare în set sau dacă există elemente duplicate în enumeratorul de intrare, va fi aruncat un InvalidOperationException. |
| Performanţă | O (mn), unde m este numărul de elemente din enumerarea de intrare și n este numărul de elemente aflate în prezent în set. |
public void AddRange (elementele de numărare) foreach (element T în articole) Add (item);
| Comportament | Elimină valoarea specificată din set dacă este găsită, returnând true. Dacă setul nu conține valoarea specificată, este returnat mesajul false. |
| Performanţă | Pe) |
bool public Ștergeți (element T) return _items.Remove (item);
| Comportament | Returnează true dacă setul conține valoarea specificată. În caz contrar, se întoarce false. |
| Performanţă | Pe) |
bool public Contine (element T) return _items.Contains (item);
| Comportament | Returnează numărul de elemente din set sau 0 dacă setul este gol. |
| Performanţă | O (1) |
public int Număr get return _items.Count;
| Comportament | Returnează un enumerator pentru toate elementele din set. |
| Performanţă | O (1) pentru a reveni la enumerator. Enumerând toate elementele are o complexitate de O (n). |
public IEnumerator GetEnumerator () returnați _items.GetEnumerator (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () returnați _items.GetEnumerator ();
| Comportament | Returnează un nou set care este rezultatul funcționării sindicale a setului curent și a intrării. |
| Performanţă | O (mn), unde m și n reprezintă numărul de elemente din seturile furnizate și respectiv din cele actuale. |
Unirea a două seturi este un set care conține toate elementele distincte care există în ambele seturi.
De exemplu, având două seturi (fiecare reprezentată în roșu):
Două seturi de intrări înaintea operației sindicale Când se efectuează operația sindicală, setul de ieșire conține toate elementele din ambele seturi. Dacă există elemente care există în ambele seturi, numai o singură copie a fiecărui element este adăugată setului de rezultate.
Rezultatul setat după operația de unire (elementele returnate sunt galbene) Un exemplu mai concret poate fi văzut atunci când ne unim împreună mai multe seturi de întregi:
[1, 2, 3, 4] uniune [3, 4, 5, 6] = [1, 2, 3, 4, 5, 6]
public Set Union (Setați altul) Set result = Set nou (_items); foreach (element T în alt._items) if (! conține (element)) result.Add (item); retur;
| Comportament | Returnează un nou set care este rezultatul operației de intersecție a seturilor curente și de intrare. |
| Performanţă | O (mn), unde m și n reprezintă numărul de elemente din seturile furnizate și respectiv din cele actuale. |
Intersecția este punctul în care două seturi "intersectează", de exemplu, membrii lor comuni. Folosind diagrama Venn din exemplul union, intersecția celor două seturi este prezentată aici:
Intersecția celor două seturi de intrări este afișată în galben Sau, folosind seturi de numere întregi:
[1, 2, 3, 4] intersecta [3, 4, 5, 6] = [3, 4]
public Setare intersecție (Setați altul) Set result = new Set (); foreach (element T în _items) if (other._items.Contains (item)) result.Add (element); retur;
| Comportament | Returnează un nou set care este rezultatul funcționării diferenței dintre seturile de curent și de intrare. |
| Performanţă | O (mn), unde m și n reprezintă numărul de elemente din seturile furnizate și respectiv din cele actuale. |
Diferența sau setarea diferenței dintre două seturi sunt elementele care există în primul set (setul al cărui Diferență se numește metoda), dar nu există în al doilea set (parametrul metodei). Diagrama Venn pentru această metodă este prezentată aici cu setul returnat în galben:
Diferența stabilită între două seturi Sau, folosind seturi de numere întregi:
[1, 2, 3, 4] diferență [3, 4, 5, 6] = [1, 2]
public Set Difference (Setați altul) Set result = Set nou (_items); foreach (elementul T în alte ._items) result.Remove (item); rezultatul retur;
| Comportament | Returnează un nou set care este rezultatul funcționării diferențelor simetrice a seturilor curente și de intrare. |
| Performanţă | O (mn), unde m și n reprezintă numărul de elemente din seturile furnizate și respectiv din cele actuale. |
Diferența simetrică a două seturi este un set a cărui membri sunt acele elemente care există doar în unul sau celălalt set. Diagrama Venn pentru această metodă este prezentată aici cu setul returnat în galben
Diferența simetrică a două seturi Sau, folosind seturi întregi:
[1, 2, 3, 4] diferența simetrică [3, 4, 5, 6] = [1, 2, 5, 6]
S-ar putea să fi observat că acesta este exact opusul operației de intersecție. Având în vedere acest lucru, să vedem ce ar fi nevoie pentru a găsi diferența simetrică folosind doar algoritmii setați pe care i-am analizat deja.
Să mergem prin ceea ce vrem.
Vrem un set care să conțină toate elementele din ambele seturi, cu excepția celor care există în ambele. Sau a spus altfel, vrem unirea celor două seturi, cu excepția intersecției celor două seturi. Vrem diferența stabilită între unire și intersecția celor două seturi.
Pas cu pas, arată astfel:
[1, 2, 3, 4] uniune [3, 4, 5, 6] = [1, 2, 3, 4, 5, 6]
[1, 2, 3, 4] intersecție [3, 4, 5, 6] = [3, 4]
[1, 2, 3, 4, 5, 6] set diferență [3, 4] = [1, 2, 5, 6]
Care rezultă setul rezultat dorit: ([1, 2, 5, 6]).
public Set SimetricDiferență (Setați altul) Set union = Union (altul); Setați intersecția = intersecția (alta); retur uniune.Diferență (intersecție);
S-ar putea să te întrebi de ce nu am adăugat IsSubset metodă. Acest tip de metodă este utilizat în mod obișnuit pentru a determina dacă un set este conținut în întregime într-un alt set. De exemplu, am putea să știm dacă:
[1, 2, 3] este submulțimea [0, 1, 2, 3, 4, 5] = Adevărat
Întrucât:
[1, 2, 3] este submulțimea [0, 1, 2] = fals
Motivul pentru care nu am detaliat un IsSubset metoda este că poate fi efectuată folosind mijloacele existente. De exemplu:
[1, 2, 3] diferență [0, 1, 2, 3, 4, 5] = []
Un set de rezultate goale arată că întregul prim set a fost conținut în al doilea set, deci știm că primul set este un subset complet al celui de-al doilea set. Un alt exemplu, folosind intersecția:
[1, 2, 3] intersecție [0, 1, 2, 3, 4, 5] = [1, 2, 3]
Dacă setul de ieșire are același număr de elemente ca setul de intrări, știm că setul de intrare este un subset al celui de-al doilea set.
Într-o clasă de scop general, având un IsSubset metoda ar putea fi utilă (și ar putea fi implementată mai optim); totuși, am vrut să subliniez că acest lucru nu este neapărat un comportament nou, ci mai degrabă un alt mod de a gândi despre operațiunile existente.
