C – Wie implementiert man die Set-Datenstruktur?

Gibt es eine knifflige Möglichkeit, eine festgelegte Datenstruktur (eine Sammlung eindeutiger Werte) in C zu implementieren? Alle Elemente in einem Satz sind vom gleichen Typ und es gibt einen riesigen RAM-Speicher.

Wie ich weiß, kann es für ganze Zahlen sehr schnell und einfach mit wertindizierten Arrays gemacht werden. Aber ich hätte gerne einen sehr allgemeinen Set-Datentyp. Und es wäre schön, wenn ein Set sich selbst enthalten könnte.

Es gibt mehrere Möglichkeiten der Umsetzung set (and map)-Funktionalität, zum Beispiel:

• baumbasierter Ansatz (Ordered Traversal)
• Hash-basierter Ansatz (unordered traversal)

Seit Sie haben wertindizierte Arrays erwähntversuchen wir den Hash-basierten Ansatz which baut natürlich auf der wertindizierten Array-Technik auf.

Hüten Sie sich vor der Vorteile und Nachteile von hashbasierten vs. baumbasierten Ansätzen.

Sie können eine entwerfen Hash-Set (ein Sonderfall von Hash-Tabellen) von Zeigern auf hashbar PODs, mit Verkettungintern dargestellt als ein Array fester Größe von Buckets von Hashwertewo:

• alle Hashwerte in einem Bucket denselben Hashwert haben
• ein Bucket kann als implementiert werden Dynamisches Array oder verknüpfte Liste von Hashables
• a hashbar‘s Hash-Wert wird verwendet, um in das Array von Buckets zu indizieren (Hashwert-indiziertes Array)
• eine oder mehrere der Hashwerte im Hash-Set enthalten sein könnte (ein Zeiger auf) ein anderes Hash-Set oder sogar auf das Hash-Set selbst (d. h Selbsteinschluss ist möglich)

Mit großen Speichermengen, die Ihnen zur Verfügung stehen, können Sie Ihr Bucket-Array großzügig dimensionieren und in Kombination mit einer guten Hash-Methode die Wahrscheinlichkeit drastisch reduzieren Kollisionwodurch eine praktisch konstante Leistung erreicht wird.

Du müsstest implementieren:

• das Hash-Funktion für den Typ, der gehasht wird
• eine Gleichheitsfunktion für den Typ, der verwendet wird, um zu testen, ob zwei Hash-Werte gleich sind oder nicht
• das Hash-Set contains/insert/remove Funktionalität.

Sie können auch verwenden offene Adressierung als Alternative zur Wartung und Verwaltung von Buckets.

Mengen werden normalerweise als eine Variante von a implementiert binärer Baum. Rote schwarze Bäume haben eine gute Worst-Case-Performance.

Diese können auch zum Bauen verwendet werden Karte um Schlüssel/Wert-Lookups zu ermöglichen.

Dieser Ansatz erfordert eine gewisse Ordnung der Elemente der Menge und der Schlüsselwerte in einer Karte.

Ich bin mir nicht sicher, wie Sie einen Satz verwalten würden, der sich möglicherweise selbst enthalten könnte, indem Sie Binärbäume verwenden, wenn Sie die Satzmitgliedschaft auf wohldefinierte Typen in C beschränken … Vergleiche zwischen solchen Konstrukten könnten problematisch sein. Sie könnten es jedoch problemlos in C++ tun.

Wenn die maximale Anzahl von Elementen in der Menge (die Kardinalität des zugrunde liegenden Datentyps) klein genug ist, sollten Sie erwägen, ein einfaches altes Array von Bits (oder wie auch immer Sie es in Ihrer bevorzugten Sprache nennen) zu verwenden.

Dann haben Sie eine einfache Prüfung der Zugehörigkeit zu einer Menge: Bit n ist 1, wenn Element n in der Menge ist. Sie könnten sogar „gewöhnliche“ Mitglieder von 1 an zählen und Bit 0 nur dann gleich 1 machen, wenn die Menge sich selbst enthält.

Dieser Ansatz wird wahrscheinlich irgendeine andere Datenstruktur (oder Funktion) erfordern, um vom Mitgliedsdatentyp in die Position im Bitarray (und zurück) zu übersetzen, aber er macht grundlegende Mengenoperationen (Vereinigung, Schnittmenge, Zugehörigkeitstest, Differenz, Einfügen, Entfernen, Komplement) sehr sehr einfach. Und es ist nur für relativ kleine Mengen geeignet, Sie würden es nicht für Mengen von 32-Bit-Ganzzahlen verwenden wollen, nehme ich nicht an.

Der Weg, um Generizität in C zu erreichen, ist by void *, Sie werden also sowieso Zeiger verwenden, und Zeiger auf verschiedene Objekte sind eindeutig. Das bedeutet, dass Sie eine Hash-Map oder einen Binärbaum benötigen, der Zeiger enthält, und dies funktioniert für alle Datenobjekte.

Der Nachteil dabei ist, dass Sie Rvalues ​​nicht unabhängig eingeben können. Sie können keine Menge haben, die den Wert 5 enthält; Sie müssen einer Variablen 5 zuweisen, was bedeutet, dass sie nicht mit einer zufälligen 5 übereinstimmt. Sie könnten sie als eingeben (void *) 5und aus praktischen Gründen funktioniert dies wahrscheinlich mit kleinen ganzen Zahlen, aber wenn Ihre ganzen Zahlen groß genug werden können, um mit Zeigern zu konkurrieren, ist die Wahrscheinlichkeit eines Fehlschlagens sehr gering.

Dies funktioniert auch nicht mit Zeichenfolgenwerten. Gegeben char a[] = "Hello, World!"; char b[] = "Hello, World!";würde eine Reihe von Zeigern finden a und b anders sein. Wahrscheinlich möchten Sie die Werte hashen, aber wenn Sie sich Sorgen über Hash-Kollisionen machen, sollten Sie die Zeichenfolge in der Menge speichern und a strncmp() um die gespeicherte Zeichenfolge mit der Sondierungszeichenfolge zu vergleichen.

(Es gibt ähnliche Probleme mit Gleitkommazahlen, aber der Versuch, Gleitkommazahlen in Mengen darzustellen, ist von vornherein eine schlechte Idee.)

Daher möchten Sie wahrscheinlich einen Tag-Wert, ein Tag für jede Art von Objekt, eines für Integer-Werte und eines für String-Werte und möglicherweise mehr für verschiedene Arten von Werten. Es ist kompliziert, aber machbar.