首页 > 后端开发 > C++ > 使用基于策略的数据结构进行逆序计数

使用基于策略的数据结构进行逆序计数

王林
发布: 2023-09-02 23:45:06
转载
810 人浏览过

使用基于策略的数据结构进行逆序计数

我们将使用 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()
登录后复制

算法

  • 我们将使用头文件iostreamvector启动程序。然后我们将提到基于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中文网其他相关文章!

相关标签:
来源:tutorialspoint.com
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板