In der Informatik ist ein Satz eine abstrakte Datenstruktur, die bestimmte Werte, ohne jede besondere Ordnung und keine wiederholten Werte versorgen kann. Es ist eine Computerdurchführung des mathematischen Konzepts eines begrenzten Satzes. Verschieden von den meisten anderen Sammlungstypen, anstatt ein spezifisches Element von einem Satz wiederzubekommen, prüft man normalerweise einen Wert für die Mitgliedschaft in einem Satz.

Einige Satz-Datenstrukturen werden für statische oder eingefrorene Sätze entworfen, die sich nicht ändern, nachdem sie gebaut werden. Statische Sätze erlauben nur Anfragenoperationen auf ihren Elementen — wie Überprüfung, ob ein gegebener Wert im Satz oder dem Aufzählen der Werte in einer willkürlichen Ordnung ist. Andere Varianten, genannt dynamische oder veränderliche Sätze, erlauben auch die Einfügung und/oder das Auswischen von Elementen vom Satz.

Eine abstrakte Datenstruktur ist eine Sammlung oder Anhäufung von Daten. Die Daten können booleans, Zahlen, Charaktere oder andere Datenstrukturen sein. Wenn man die Struktur als nachgegeben betrachtet, indem man paketiert oder mit einem Inhaltsverzeichnis versieht, gibt es vier grundlegende Datenstrukturen:

1. unpaketiert, mit einem Inhaltsverzeichnis unersehen: Bündel
2. paketiert, mit einem Inhaltsverzeichnis unersehen: Satz
3. unpaketiert, mit einem Inhaltsverzeichnis versehen: Schnur (Folge)
4. paketiert, mit einem Inhaltsverzeichnis versehen: Liste (Reihe)

In dieser Ansicht ist der Inhalt eines Satzes ein Bündel, und isolierte Datensachen sind elementare Bündel (Elemente). Wohingegen Sätze Elemente enthalten, bestehen Bündel aus Elementen.

Weitere Strukturierung kann durch das Betrachten der Vielfältigkeit von Elementen erreicht werden (Sätze werden Mehrsätze, Bündel werden Hyperbündel), oder ihre Gleichartigkeit (ist eine Aufzeichnung eine Reihe von Feldern, nicht notwendigerweise der ganze derselbe Typ).

Durchführungen

Ein Satz kann auf viele Weisen durchgeführt werden. Zum Beispiel kann man eine Liste verwenden, die Ordnung der Elemente ignorierend und darauf achtend, wiederholte Werte zu vermeiden. Sätze werden häufig mit verschiedenen Geschmäcken nach Bäumen, Versuchen oder Hash-Tabellen durchgeführt.

Ein Satz kann gesehen, und als eine (teilweise) assoziative Reihe durchgeführt werden, in der der Wert jedes Schlüsselwert-Paares den Einheitstyp hat.

Typ-Theorie

In der Typ-Theorie werden Sätze allgemein mit ihrer Anzeigefunktion identifiziert: Entsprechend kann eine Reihe von Werten des Typs durch angezeigt werden oder. (Subtypen und Teilmengen können durch Verbesserungstypen modelliert werden, und Quotient-Sätze können durch setoids ersetzt werden.) Die charakteristische Funktion F eines Satzes S wird als definiert:

1, & \mbox {wenn} x \in S \\

0, & \mbox {wenn} x \not \in S

\end {Fälle }\</Mathematik>

In der Theorie können viele andere abstrakte Datenstrukturen als Satz-Strukturen mit zusätzlichen Operationen und/oder zusätzlichen den Standardoperationen auferlegten Axiomen angesehen werden. Zum Beispiel kann ein abstrakter Haufen als eine Satz-Struktur mit einer Operation angesehen werden, die das Element des kleinsten Werts zurückgibt.

Operationen

Mit dem Satz theoretische Kernoperationen

Man kann die Operationen der Algebra von Sätzen definieren:

• : gibt die Vereinigung von Sätzen S und T zurück.
• : gibt die Kreuzung von Sätzen S und T zurück.
• : gibt den Unterschied von Sätzen S und T zurück.
• : ein Prädikat, das prüft, ob der Satz S eine Teilmenge des Satzes T ist.

Statische Sätze

Typische Operationen, die durch eine statische Satz-Struktur S zur Verfügung gestellt werden können, sind:

• : Kontrollen, ob der Wert x im Satz S ist.
• : Kontrollen, ob der Satz S leer ist.

• oder: Gibt die Zahl der Elemente in S zurück.
• : gibt eine Funktion zurück, die einen mehr Wert von S bei jedem Anruf in einer willkürlichen Ordnung zurückgibt.
• : gibt eine Liste zurück, die die Elemente von S in einer willkürlichen Ordnung enthält.
• : schafft eine Satz-Struktur mit Werten x, x, …, x.
• : schafft eine neue Satz-Struktur, die alle Elemente der gegebenen Sammlung oder alle durch den gegebenen iterator zurückgegebenen Elemente enthält.

Dynamische Sätze

Dynamische Satz-Strukturen tragen normalerweise bei:

• : schafft eine neue, am Anfang leere Satz-Struktur.
• : schafft eine neue Satz-Struktur, die am Anfang leer, aber zum Halten bis zu n Elementen fähig ist.
• : trägt das Element x zu S bei, wenn es bereits nicht da ist.
• : entfernt das Element x von S, wenn es da ist.
• : gibt die maximale Zahl von Werten zurück, die S halten kann.

Einige Satz-Strukturen können nur einige dieser Operationen erlauben. Die Kosten jeder Operation werden von der Durchführung, und vielleicht auch auf den besonderen Werten abhängen, die im Satz und der Ordnung versorgt sind, in die sie eingefügt werden.

Zusätzliche Operationen

Es gibt viele andere Operationen, die (im Prinzip) in Bezug auf das obengenannte definiert werden können wie:

• : gibt ein willkürliches Element von S zurück, es von S löschend.
• : gibt den Satz von verschiedenen Werten zurück, die sich aus Verwendung der Funktion F zu jedem Element von S ergeben.
• : gibt die Teilmenge zurück, die alle Elemente von S enthält, die ein gegebenes Prädikat P befriedigen.
• : gibt den Wert nach dem Bewerben um jedes Element e S zurück.
• : löschen Sie alle Elemente von S.
• : Kontrollen, ob die zwei gegebenen Sätze gleich sind (d. h. enthalten alle und nur dieselben Elemente).
• : gibt einen Kuddelmuddel-Wert für den statischen Satz S solch dass wenn dann zurück

Andere Operationen können für Sätze mit Elementen eines speziellen Typs definiert werden:

• : gibt die Summe aller Elemente von S für eine Definition "der Summe" zurück. Zum Beispiel, über ganze Zahlen oder reals, kann es als definiert werden.
• : gibt das Element von S zurück, der im Wert an x (durch einige metrisch) am nächsten ist.

Durchführungen

Sätze können mit verschiedenen Datenstrukturen durchgeführt werden, die verschiedene Umtausche der Zeit und Raums für verschiedene Operationen zur Verfügung stellen. Einige Durchführungen werden entworfen, um die Leistungsfähigkeit sehr spezialisierter Operationen, solcher als zu verbessern, oder. Durchführungen, die als "allgemeiner Gebrauch" normalerweise beschrieben sind, mühen sich, und Operationen zu optimieren.

Sätze werden ebenso als assoziative Reihe, nämlich, ein selbstbalancierender binärer Suchbaum für sortierte Sätze allgemein durchgeführt (der O hat (loggen Sie n), für die meisten Operationen), oder eine Hash-Tabelle für unsortierte Sätze (der O (1) durchschnittlicher Fall, aber O (n) Grenzfall, für die meisten Operationen hat). Eine sortierte geradlinige Hash-Tabelle kann verwendet werden, um deterministisch bestellte Sätze zur Verfügung zu stellen.

Andere populäre Methoden schließen Reihe ein. Insbesondere eine Teilmenge der ganzen Zahlen 1.. n kann effizient durchgeführt werden, weil ein N-Bit Reihe gebissen hat, die auch sehr effiziente Vereinigung und Kreuzungsoperationen unterstützen. Eine Blüte-Karte führt einen Satz probabilistically mit einer sehr kompakten Darstellung durch, aber eine kleine Chance von falschem positives auf Abfragen riskierend.

Die Boolean gehen unter Operationen können in Bezug auf elementarere Operationen durchgeführt werden (und), aber Spezialalgorithmen können niedrigere asymptotische Zeitgrenzen nachgeben. Wenn Sätze als sortierte Listen zum Beispiel durchgeführt werden, wird der naive Algorithmus dafür Code nehmen, der zur Länge M von S Zeiten die Länge n T proportional ist; wohingegen eine Variante des Listenmischen-Algorithmus den zu m+n rechtzeitig proportionalen Job tun wird. Außerdem, dort werden Satz-Datenstrukturen spezialisiert (wie die Vereinigung - finden Datenstruktur), die für ein oder mehr von diesen Operationen, auf Kosten anderer optimiert werden.

Sprachunterstützung

Eine der frühsten Sprachen, um Sätze zu unterstützen, war Pascal; viele Sprachen schließen es jetzt, ob auf der Kernsprache oder in einer Standardbibliothek ein.

• Java bietet die Schnittstelle an, um Sätze (mit der Klasse zu unterstützen, die es mit einer Hash-Tabelle durchführt), und die Subschnittstelle, um sortierte Sätze (mit der Klasse zu unterstützen, die es mit einem binären Suchbaum durchführt).
• Das Fundament-Fachwerk des Apfels (ein Teil von Kakao) stellt die Objektiven-C Klassen zur Verfügung, und. CoreFoundation APIs stellen die Typen CFSet und CFMutableSet für den Gebrauch in C zur Verfügung.
• Pythonschlange hat eingebaut und Typen da 2.4, und seit der Pythonschlange 3.0 und 2.7, nichtleere Satz-Druckfehler von Unterstützungen mit einer Syntax der krausen Klammer z.B:.
• Das.NET Fachwerk stellt das allgemeine und die Klassen zur Verfügung, die die allgemeine Schnittstelle durchführen.
• Die Standardbibliothek des Rubins schließt ein Modul ein, das enthält und Klassen, die Sätze mit Hash-Tabellen, der letzten erlaubenden Wiederholung in der sortierten Ordnung durchführen.
• Die Standardbibliothek von OCAML enthält ein Modul, das eine funktionelle Satz-Datenstruktur mit binären Suchbäumen durchführt.
• Die GHC Durchführung von Haskell stellt ein Modul zur Verfügung, das eine funktionelle Satz-Datenstruktur mit binären Suchbäumen durchführt.
• Das Tcl Tcllib Paket stellt ein Satz-Modul zur Verfügung, das eine auf TCL-Listen gestützte Satz-Datenstruktur durchführt.

Wie bemerkt, in der vorherigen Abteilung auf Sprachen, die Sätze nicht direkt unterstützen, aber wirklich assoziative Reihe unterstützen, kann mit Sätzen mit der assoziativen Reihe, durch das Verwenden der Elemente als Schlüssel und das Verwenden eines Scheinwerts als die Werte wettgeeifert werden, die ignoriert werden.

In C ++

In C ++ stellt Standard Template Library (STL) die Schablone-Klasse zur Verfügung, die einen sortierten Satz mit einem binären Suchbaum durchführt; der STL von SGI stellt auch die Schablone-Klasse zur Verfügung, die einen Satz mit einer Hash-Tabelle durchführt.

In Sätzen sind die Elemente selbst die Schlüssel im Gegensatz zu sequenced Behältern, wo auf Elemente mit ihrem (relativ oder absolut) Position zugegriffen wird. Satz-Elemente müssen eine strenge schwache Einrichtung haben.

Einige der Mitglied-Funktionen in C ++ und ihre Beschreibung werden im Tisch unten gegeben:

Schablone-Rahmen

Hier und sind in Satz-Behältern definierte Mitglied-Typen. Erstens, Wert, der zu verwenden ist, um eingefügtes Element zu initialisieren. Dann hat sich die Position des ersten Elements für die Operation verglichen. Es gibt wirklich die Position nicht, wo Element eingefügt werden soll, aber gerade eine Anzeige der möglichen Einfügungsposition im Behälter, um effiziente Einfügungsoperation zu machen. Typ Template kann jeder Typ des Eingangs iterator sein. Iterators geben eine Reihe von Elementen und Kopien von diesen in der Reihe [zuerst an, letzt) werden in den Satz eingefügt.

Mehrsatz

Eine Schwankung des Satzes ist der Mehrsatz oder die Tasche, die dasselbe als eine Satz-Datenstruktur ist, aber wiederholte ("gleiche") Werte (Duplikate) erlaubt. Der Satz aller Taschen über den Typ T wird durch die Ausdruck-Tasche T gegeben. Es ist für Gegenstände in der Informatik möglich, "gleich" unter etwas Gleichwertigkeitsbeziehung, aber noch verschieden unter einer anderen Beziehung betrachtet zu werden. Einige Typen von Mehrsatz-Durchführungen werden verschiedene gleiche Gegenstände als getrennte Sachen in der Datenstruktur versorgen; während andere es unten zu einer Version (die erste gestoßen) zusammenbrechen und eine positive Zählung der ganzen Zahl der Vielfältigkeit des Elements behalten werden.

• C ++ 's Standardschablone-Bibliothek stellt die Klasse für den sortierten Mehrsatz zur Verfügung, und der STL von SGI stellt die Klasse zur Verfügung, die einen Mehrsatz mit einer Hash-Tabelle durchführt.
• Für Java stellen Drittbibliotheken Mehrsatz-Funktionalität zur Verfügung:
• Apachen-Unterhaus-Sammlungen stellen und Schnittstellen, mit dem Einführen von Klassen wie zur Verfügung und.
• Google Sammlungen stellen die Schnittstelle, mit dem Einführen von Klassen wie zur Verfügung und.
• Apfel stellt die Klasse als ein Teil von Kakao, und und Typen als ein Teil von CoreFoundation zur Verfügung.
• Die Standardbibliothek der Pythonschlange schließt ein, der einem Mehrsatz ähnlich ist.

Wo eine Mehrsatz-Datenstruktur nicht verfügbar ist, soll ein workaround einen regelmäßigen Satz verwenden, aber das Gleichheitsprädikat seiner Sachen überreiten, um immer "nicht gleich" auf verschiedenen Gegenständen zurückzukehren (jedoch, solcher wird noch immer nicht im Stande sein, vielfache Ereignisse desselben Gegenstands zu versorgen), oder eine assoziative Reihe verwendet, die die Werte zu ihrer Vielfältigkeit der ganzen Zahl kartografisch darstellt (das wird nicht im Stande sein, zwischen gleichen Elementen überhaupt zu unterscheiden).

Typische Operationen auf Taschen:

• Tasche-Mitgliedschaft - Wenn B: Tasche T und x: T dann ist das Prädikat x in B wahr, wenn, und nur wenn x in B mindestens einmal erscheint.
• Subtaschen - Wenn B, B: Tasche T dann ist das Prädikat B  B wahr, wenn jedes Element, das in B vorkommt, in B nicht mehr häufig vorkommt, als es in B vorkommt.
• Das Aufzählen von Taschen - Wenn B: Tasche T und x: T dann kommt die Zahl von Zeiten x in B vor (eine natürliche Zahl) wird durch den Ausdruck B # x gegeben.
• Das Schuppen von Taschen - Wenn B: Tasche T und n: N dann n  ist B eine Tasche, die dieselben Elemente wie B enthält, außer dass jedes Element, das M Zeiten mit B vorkommt, n * M Zeiten mit n  B vorkommt.
• Tasche-Vereinigung - Wenn B, B: Tasche T dann B  B ist eine Tasche, die gerade jene Werte enthält, die entweder in B oder in B vorkommen, außer dass die Zahl von Zeiten ein Wert x kommt in B  B vor (B#x) + (B#x) gleich ist.

Siehe auch

• Blüte-Filter
• Zusammenhangloser Satz