使用基於策略的資料結構進行逆序計數

我們將使用 g 頭檔在 C 編譯器中編譯程式碼。 g 是一個基於Linux的頭文件，用於在C 中編譯基於策略的資料結構的程式碼。基於策略的資料結構是用於程式碼的高效能和靈活性的結構。由於這些資料結構非常豐富，我們可以將它們用於許多功能，例如搜尋元素的索引、將元素插入索引位置、從索引範圍中刪除元素等。

Example

的中文翻譯為：

範例

讓我們舉一個反轉計數的例子 -

假設建構樹的內部遍歷是1,2,3,4,5，當我們遍歷以反轉它時，樹的形式變成5,4,3,2 ,1.

讓我們將以下樹結構作為輸入

 < 5, 4, 3, 2, 1 >

給定的結構樹長度為4。現在我們將考慮以下步驟來理解反轉的過程。

步驟1 - 元素以index[0] 開頭，即5， 並與每個元素配對，直到index [4] 即1。因此索引 0 到 4 之間的總計數為 4。

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

第二步驟 - 元素從index[1] 開始，即4， 並與每個元素配對，直到index[4 ] 即1。因此，索引 1 到 4 之間的總計數為 3。

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

步驟3 - 元素以index[2] 開頭，即3， 並與每個元素配對，直到index [4] 即1。因此索引 2 到 4 之間的總計數為 2。

(3…2), (3…1)

第4步 - 元素從index[3] 開始，即2，並與每個元素配對，直到index[4 ]，即1。因此，索引3到4之間的總計數為 1。

(2…1)

這樣我們可以寫給定建構樹的反轉。因此，count(4 3 2 1)的總反轉數為10。

在本文中，我們將使用基於策略的資料結構來解決反轉計數問題。

文法

程式中使用以下語法 -

vector <data_type> vector_variable_name

參數

data_type - 用於向量的資料類型。

vector_variable_name − 用於向量的變數名稱。

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

參數

typedef - 這是 C 程式中使用的保留關鍵字。

int − 插入陣列項目的資料型態。

null_type - 這是一個映射策略並作為一個集合使用。如果我們想要映射，那麼第二個參數必須是映射類型。

less - 兩個函數之間的比較。

rb_tree_tag - 用於基於插入和刪除的紅黑樹的樹類型。

tree_order_statistics_node_update − 這是基於頭檔‘tree_policy.hpp’的，該檔案包含了用於更新節點變體的樹形容器的各種操作。因此，我們將追蹤子樹中的節點。

pbds - 基於策略的資料結構的變數名稱。

order_of_key()

演算法

• 我們將使用頭檔iostream和vector啟動程式。 然後我們將提到基於g 的頭檔基於策略的資料結構（pbds）。

• 我們將根據GNU的策略基於資料結構使用必要的命名空間，即‘using namespace __gnu_pbds’。 它將根據pbds初始化樹的格式，即'typedef tree, rb_tree_tag, tree_order_statistics_node_update> pbds;#透過使用這些，我們將追蹤子樹中的節點追蹤子樹中的節點;

  # 。

• 我們正在定義一個雙長資料類型的函數定義‘inversion_Cnt’

  ，它接受一個向量整數的參數並儲存陣列元素的位址。

• 我們將‘0’儲存到變數‘cnt’中，以便處理總對的逆序計數。

• 然後將名為pb的物件初始化為基於策略的變數‘pbds’

  ，以便對陣列元素的插入和排序進行操作。

• 在初始化變數之後，使用for

  迴圈來迭代數組元素。這個陣列元素將根據以下兩個語句進行反轉運算 -

• cnt = i-pb.order_of_key(arr[i]);<5,4> - 透過計算< 等对值来返回第二个参数中的最小值5,3>,<5,2>、<5,1>、<4,3>、<4,2>、

  等。

• pb.insert(arr[i]);

  - 透過使用預定義函數 insert()，我們加入陣列元素的反轉，即 arr[i]。

• 我們開始主函數，並宣告向量陣列 input。

• 然後我們使用變數‘count’呼叫函數‘inversion_Cnt’

  。

• 最後，‘count’

  變數給出了陣列中反轉的總計數。

Example

的中文翻譯為：

範例

在這個程式中，我們將使用策略性的資料結構來計算數字的逆序數。 ###

#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 : "<
登入後複製

输出

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

结论

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

以上是使用基於策略的資料結構進行逆序計數的詳細內容。更多資訊請關注PHP中文網其他相關文章！