Verwendung richtlinienbasierter Datenstrukturen für die Rückwärtszählung

Wir werden den Code im C++-Compiler unter Verwendung von G++-Header-Dateien kompilieren. g++ ist ein Linux-basierter Header zum Kompilieren von Code für richtlinienbasierte Datenstrukturen in C++. Richtlinienbasierte Datenstrukturen sind Strukturen, die für hohe Leistung und Flexibilität in Ihrem Code verwendet werden. Da diese Datenstrukturen sehr umfangreich sind, können wir sie für viele Funktionen verwenden, z. B. zum Durchsuchen des Index nach einem Element, zum Einfügen eines Elements an einer Indexposition, zum Entfernen eines Elements aus einem Indexbereich usw.

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

Nehmen wir ein Beispiel für das umgekehrte Zählen -

Angenommen, die interne Durchquerung zum Aufbau des Baums ist 1,2,3,4,5. Wenn wir sie umkehren, wird die Form des Baums zu 5,4,3,2,1.

Nehmen wir die folgende Baumstruktur als Eingabe

 < 5, 4, 3, 2, 1 >

Die angegebene Länge des Strukturbaums beträgt 4. Nun betrachten wir die folgenden Schritte, um den Prozess der Inversion zu verstehen.

Schritt 1 – Elemente beginnen mit index[0], der 5 ist, und werden mit jedem Element gepaart, bis index [4], der 1 ist. Die Gesamtzahl zwischen Index 0 und 4 beträgt also 4.

(5…4), (5…3), (5…2), (5…1)

Schritt 2 – Elemente beginnen bei index[1], also 4, , und werden mit jedem Element bis index[4], also 1, gepaart. Daher beträgt die Gesamtzahl zwischen den Indizes 1 bis 4 3.

(4…3), (4…2), (4…1)

Schritt 3 – Elemente beginnen mit index[2], der 3 ist, und werden mit jedem Element gepaart, bis index [4], der 1 ist. Die Gesamtzahl zwischen Index 2 und 4 beträgt also 2.

(3…2), (3…1)

Schritt 4 – Elemente beginnen bei index[3], also 2, und werden mit jedem Element bis index[4], also 1, gepaart. Daher beträgt die Gesamtzahl zwischen Index 3 und 4 1.

(2…1)

Auf diese Weise können wir die Umkehrung eines gegebenen Konstruktionsbaums schreiben. Daher beträgt die Gesamtzahl der Umkehrungen von count(4+3+2+1) 10.

In diesem Artikel werden wir richtlinienbasierte Datenstrukturen verwenden, um das Problem der Inversionszählung zu lösen.

Grammatik

Die folgende Syntax wird im Programm verwendet -

vector <data_type> vector_variable_name

Parameter

data_type – Datentyp zur Verwendung für Vektoren.

vector_variable_name – Variablenname zur Verwendung für Vektoren.

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

Parameter

typedef – Dies ist ein reserviertes Schlüsselwort, das in C++-Programmen verwendet wird.

int – Datentyp des eingefügten Array-Elements.

null_type – Dies ist eine Zuordnungsstrategie und wird als Sammlung verwendet. Wenn wir eine Karte erstellen möchten, muss der zweite Parameter der Kartentyp sein.

less - Vergleich zwischen zwei Funktionen.

rb_tree_tag – Baumtyp für rot-schwarze Bäume basierend auf Einfügen und Löschen.

tree_order_statistics_node_update − Dies basiert auf der Header-Datei „tree_policy.hpp“, die verschiedene Operationen zum Aktualisieren des Baumcontainers von Knotenvarianten enthält. Daher werden wir die Knoten im Unterbaum im Auge behalten.

pbds – Variablennamen für richtlinienbasierte Datenstrukturen.

order_of_key()

Algorithmus

• Wir werden die Header-Dateien iostream und vector verwenden, um das Programm zu starten. Dann werden wir Header-File-Policy-basierte Datenstrukturen (pbds) erwähnen, die auf g++ basieren.

• Wir werden den erforderlichen Namespace basierend auf der Datenstruktur gemäß der GNU-Richtlinie verwenden, die „Verwendung des Namespace __gnu_pbds“ lautet. Es wird das Format des Baums gemäß pbds initialisieren, d. h. ‘typedef tree, rb_tree_tag, tree_order_statistics_node_update> pbds;Durch diese Verwendung behalten wir den Überblick über die Knoten im Unterbaum.

• Wir definieren eine Funktionsdefinition des doppelt langen Datentyps ‘inversion_Cnt‘, die einen Parameter einer Vektor-Ganzzahl annimmt und die Adresse des Array-Elements speichert.

• Wir speichern „0“ in der Variablen „cnt“, um die umgekehrte Zählung der gesamten Paare zu verarbeiten.

• Das Objekt mit dem Namen pb wird dann mit einer richtlinienbasierten Variablen ‘pbds‘ initialisiert, um das Einfügen und Sortieren von Array-Elementen zu steuern.

• Verwenden Sie nach der Initialisierung der Variablen eine for-Schleife, um die Array-Elemente zu durchlaufen. Dieses Array-Element wird gemäß den folgenden zwei Anweisungen umgekehrt -

• cnt += i-pb.order_of_key(arr[i]); – Durch Berechnung von <5,4>,< 等对值来返回第二个参数中的最小值5,3>, <5,2>, <5,1>, <4,3>, <4,2> usw.

• pb.insert(arr[i]); – Durch die Verwendung der vordefinierten Funktion insert() fügen wir die Inversion des Array-Elements, also arr[i], hinzu.

• Wir starten die Hauptfunktion und deklarieren die Vektor-Array-Eingabe.

• Dann verwenden wir die Variable ‘count‘, um die Funktion ‘inversion_Cnt‘ aufzurufen.

• Schließlich gibt die Variable ‘count‘ die Gesamtzahl der Inversionen im Array an.

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

In diesem Programm verwenden wir strategische Datenstrukturen, um die Umkehrung einer Zahl zu berechnen.

#include 
#include 
// *******g++ header file*********
#include 
#include 

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
double long inversion_Cnt( vector& arr) {
   double long cnt = 0;
   pbds pb;
   for(int i = 0; i < arr.size(); i++) {
      cnt += i-pb.order_of_key(arr[i]); 
      pb.insert(arr[i]); // add the array element 
   }
   return cnt;
}
int main() {
   vector arr = {5, 4, 3, 2, 1}; // The inversion of following input array is <5,4>, <5,3>, <5,2>, <5,1>, <4,3>, <4,2>, <4,1>, <3,2>, <3,1>, <2,1>
   double long count = inversion_Cnt(arr);
   cout<<"Total number of inversion count using Policy based data structure is : "<
Nach dem Login kopieren

输出

Total number of inversion count using Policy based data structure is : 10

结论

我们通过执行基于反转计数的程序来探索 Linux 头文件 (g++) 的概念。众所周知，C++程序用于操作系统，它有一个跟踪器来记录系统的每一个信息。与此程序相同，我们看到子树如何跟踪其每个节点。

Das obige ist der detaillierte Inhalt vonVerwendung richtlinienbasierter Datenstrukturen für die Rückwärtszählung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!