Ich möchte ein Set in C implementieren. Ist es in Ordnung, eine verknüpfte Liste zu verwenden, wenn Sie das SET erstellen, oder sollte ich einen anderen Ansatz verwenden?
Wie implementieren Sie normalerweise Ihren eigenen Satz (falls erforderlich).
HINWEIS: Wenn ich den Linked-List-Ansatz verwende, werde ich wahrscheinlich die folgenden Komplexitäten für Set my operations haben:
O (n * m) scheint vor allem bei großen Datenmengen etwas zu groß zu sein ... Gibt es eine Möglichkeit, mein Set effizienter zu implementieren?
Mengen werden normalerweise entweder als rot-schwarze Bäume implementiert (die erfordern, dass die Elemente eine Gesamtreihenfolge haben) oder als automatisch skalierende Hashtabelle (die eine Hash-Funktion erfordert).
Letzteres wird normalerweise implementiert, indem die Größe der Hashtabelle verdoppelt wird und alle Elemente erneut eingefügt werden, wenn ein bestimmter Kapazitätsschwellenwert (75% funktioniert) überschritten wird. Dies bedeutet, dass einzelne Einfügeoperationen O (n) sein können, aber wenn sie über viele Operationen hinweg amortisiert sind, ist es tatsächlich O (1).
std::set wird oft als rot-schwarzer Baum implementiert: Ссылка
Dieser Ansatz wird Ihnen eine viel bessere Komplexität bei allen aufgeführten Operationen geben.
Da Sie bereits eine verkettete Liste implementiert haben, ist die Skip-Liste am einfachsten. Wenn Sie ausgewogene Bäume verwenden möchten, ist meiner Meinung nach ein Treap am einfachsten. Dies sind randomisierte Datenstrukturen, aber im Allgemeinen sind sie genauso effizient wie ihre deterministischen Gegenstücke, wenn nicht mehr (und eine Skip-Liste kann deterministisch gemacht werden).
Tags und Links c data-structures