Eine der Arten von Datenstrukturen, die die direkte Verkörperung mathematischer Einheiten in der Informatik sind, sind Mengen. Operationen mit ihnen liegen nicht selten verschiedenen Algorithmen zugrunde. Verschiedene Programmiersprachen haben ihre eigenen Mittel zur Beschreibung von Mengen.
Notwendig
- - Entwicklungsumgebung;
- - Übersetzer aus der gewählten Programmiersprache.
Anweisungen
Schritt 1
Beschreiben Sie das Set mit der Programmiersprache, falls verfügbar. In der Pascal-Sprache gibt es beispielsweise ein Set-Konstrukt, mit dem Sie die entsprechenden Typen deklarieren können. Das Volumen solcher Sets sollte zwar 256 Elemente nicht überschreiten. Ein Beispiel für Set-Typ-Deklarationen könnte wie folgt aussehen:
Typ
AZLetters = Satz von 'A'.. 'Z';
AllLetters = Zeichensatz;
Variablen und Konstanten von Typen, die Mengen sind, werden auf die übliche Weise deklariert. In diesem Fall können Set-Literale zur Initialisierung verwendet werden. Beispielsweise:
const
LettersSet1: AZLetters = ['A', 'B', 'C'];
Schritt 2
Verwenden Sie die Fähigkeiten von Standardbibliotheken oder -modulen, um Mengen zu beschreiben. Die C++-Vorlagenbibliothek, die mit dem Compiler mitgeliefert werden sollte, enthält also eine Vorlage für die set-Containerklasse, die die Funktionalität von Mengen implementiert:
Vorlage <
Klassenschlüssel, Klassenmerkmale = weniger, Klasse Allocator = Allocator
Klassensatz
Wie Sie der Auflistung entnehmen können, sind die Argumente der Set-Vorlage: der Datentyp der Elemente des Sets, der Typ des funktionalen Objekts, um die Reihenfolge der Elemente im Set zu bestimmen, und der Typ des Speicherzuordners. In diesem Fall ist nur das erste Argument erforderlich (wie bei den anderen beiden werden standardmäßig das binäre Standardprädikat less und der Standardzuordner verwendet).
Schritt 3
Wenden Sie gegebenenfalls Klassen oder Klassenvorlagen an, die bei der Entwicklung von Frameworks verwendet werden, die die Funktionalität der Arbeit mit Mengen implementieren. Ein Beispiel für ein solches Werkzeug ist die QSet-Vorlagenklasse des QtCore-Moduls der Qt-Bibliothek. Seine Fähigkeiten ähneln denen des im vorherigen Schritt beschriebenen STL-Set-Containers.
Schritt 4
Beschreiben Sie die Menge mit Ihren eigenen Implementierungsmethoden. Verwenden Sie Bit-Flags, die in Arrays fester Länge gespeichert sind, für Gruppen von Elementen einfacher Typen und kleiner Größe. Implementieren Sie eine Set-Container-Klasse für komplexe Datentypen. Als Grundlage können Sie die Funktionalität assoziativer oder hashing assoziativer Arrays nehmen. Es kann wiederum auf der Basis von selbstausgleichenden binären Suchbäumen (zum Beispiel Rot-Schwarz-Bäumen) aufgebaut werden.
