《数据结构、算法与应用C++语言描述》- 最小输者树模板的C++实现

2023-12-19 20:04
文章标签 算法 语言 模板 c++ 实现 应用 数据结构 最小 描述 输者

本文主要是介绍《数据结构、算法与应用C++语言描述》- 最小输者树模板的C++实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

输者树

完整可编译运行代码见：Github::Data-Structures-Algorithms-and-Applications/_31loserTree

输者树：每一个内部节点所记录的都是比赛的输者，晋级的节点记录在边上。本文中，赢者是分数较低的那个，输者是分数高的那个。教材的举例是这样的。

在这里插入图片描述

更好理解的解释是，参考地址。

  • a与b比赛，输者是b，赢者是a，将b放到内部节点，将a放到边上
  • c与d比赛，输者是d，赢者是c，将d放到内部节点，将c放到边上
  • e与f比赛，输者是e，赢者是f，将e放到内部节点，将f放到边上
  • g与h比赛，输者是h，赢者是g，将h放到内部节点，将g放到边上
  • a与c比赛，输者是c，赢者是a，将c放到内部节点，将a放到边上
  • f与g比赛，输者是g，赢者是f，将g放到内部节点，将f放到边上
  • a与f比赛，输者是a，赢者是f，将a放到内部节点，将f放到边上
  • 将最终赢者放到数组的第0个元素

在loserTree的模板实现中，可以使用一个数组来存储输者、另一个数组存储赢者。

在这里插入图片描述

输者树比赢者树的优势

当改变的元素是上一场比赛的最终赢家的话，内部节点存储了所有该赢家的输者。在重新组织比赛时，只需要与父亲节点进行比较，而不需要获取到父亲节点的另外一个节点，然后与其比较，可以减少访存的时间。

输者树的实现

main.cpp

/*
Project name :			_30winnerTree
Last modified Date:		2023年12月19日16点48分
Last Version:			V1.0
Descriptions:			最小输者树——main函数
*/
#include "MinimumLoserTree.h"
int main(){MinimumLoserTreeTest();return 0;
}

MinimumLoserTree.h

/*
Project name :			_30winnerTree
Last modified Date:		2023年12月19日16点48分
Last Version:			V1.0
Descriptions:			最小输者树——模板类
*/#ifndef _31LOSERTREE_MINIMUMLOSERTREE_H
#define _31LOSERTREE_MINIMUMLOSERTREE_H
#include<iostream>
#include "loserTree.h"
#include "myExceptions.h"
using namespace std;void MinimumLoserTreeTest();template<class T>
class MinimumLoserTree : public loserTree<T> {
public:/*构造函数*/explicit MinimumLoserTree(T *thePlayer = nullptr, int theNumberOfPlayers = 0) {tree = nullptr;advance = nullptr;initialize(thePlayer, theNumberOfPlayers);}/*析构函数*/~MinimumLoserTree() {delete[] tree;delete[] advance;}void initialize(T *thePlayer, int theNumberOfPlayers);//初始化[[nodiscard]] int getTheWinner() const { return tree[0]; };//输出当前的赢者void rePlay(int thePlayer, T newvalue);//重构void output() const;
private:int numberOfPlayers{};int *tree;// 记录内部结点，tree[0]是最终的赢者下标，不使用二叉树结点，因为父子关系都是通过计算得出int *advance;// 记录比赛晋级的成员T *player;//参与比赛的元素int lowExt{};//最底层外部结点的个数,2*(n-s)int offset{};//2*s-1void play(int, int, int);int winner(int x, int y) { return player[x] <= player[y] ? x : y; };//返回更小的元素下标int loser(int x, int y) { return player[x] <= player[y] ? y : x; };//返回更大的元素下标
};template<class T>
void MinimumLoserTree<T>::initialize(T *thePlayer, int theNumberOfPlayers) {int n = theNumberOfPlayers;if (n < 2) {throw illegalParameterValue("must have at least 2 players");}player = thePlayer;numberOfPlayers = n;// 删除原来初始化的内存空间，初始化新的内存空间delete[] tree;delete[] advance;tree = new int[n + 1];advance = new int[n + 1];// 计算sint s;for (s = 1; 2 * s <= n - 1; s += s);//s=2^log(n-1)-1（常数优化速度更快），s是最底层最左端的内部结点lowExt = 2 * (n - s);offset = 2 * s - 1;for (int i = 2; i <= lowExt; i += 2)//最下面一层开始比赛play((i + offset) / 2, i - 1, i);//父结点计算公式第一条int temp = 0;if (n % 2 == 1) {//如果有奇数个结点，一定会存在特殊情况，需要内部节点和外部节点的比赛play(n / 2, advance[n - 1], lowExt + 1);temp = lowExt + 3;} else temp = lowExt + 2;//偶数个结点，直接处理次下层for (int i = temp; i <= n; i += 2)//经过这个循环，所有的外部结点都处理完毕play((i - lowExt + n - 1) / 2, i - 1, i);tree[0] = advance[1];//tree[0]是最终的赢者，也就是决赛的赢者}template<class T>
void MinimumLoserTree<T>::play(int p, int leftChild, int rightChild) {// tree结点存储相对较大的值，也就是这场比赛的输者tree[p] = loser(leftChild, rightChild);// advance结点存储相对较小的值，也就是这场比赛的晋级者advance[p] = winner(leftChild, rightChild);// 如果p是右孩子while (p % 2 == 1 && p > 1) {tree[p / 2] = loser(advance[p - 1], advance[p]);advance[p / 2] = winner(advance[p - 1], advance[p]);p /= 2;//向上搜索}
}template<class T>
void MinimumLoserTree<T>::rePlay(int thePlayer, T newvalue) {int n = numberOfPlayers;if (thePlayer <= 0 || thePlayer > n) {throw illegalParameterValue("Player index is illegal");}player[thePlayer] = newvalue;int matchNode,//将要比赛的场次leftChild,//比赛结点的左孩子rightChild;//比赛结点的右孩子if (thePlayer <= lowExt) {//如果要比赛的结点在最下层matchNode = (offset + thePlayer) / 2;leftChild = 2 * matchNode - offset;rightChild = leftChild + 1;} else {//要比赛的结点在次下层matchNode = (thePlayer - lowExt + n - 1) / 2;if (2 * matchNode == n - 1) {//特殊情况，比赛的一方是晋级leftChild = advance[2 * matchNode];rightChild = thePlayer;} else {leftChild = 2 * matchNode - n + 1 + lowExt;//这个操作是因为上面matchNode计算中/2取整了rightChild = leftChild + 1;}}//到目前位置，我们已经确定了要比赛的场次以及比赛的选手//下面进行比赛重构，也就是和赢者树最大的不同，分两种情况if (thePlayer == tree[0]) {//当你要重构的点是上一场比赛的赢家的话，过程比赢者树要简化，简化之后只需要和父亲比较，不需要和兄弟比较for (; matchNode >= 1; matchNode /= 2) {int oldLoserNode = tree[matchNode];//上一场比赛的输者tree[matchNode] = loser(oldLoserNode, thePlayer);advance[matchNode] = winner(oldLoserNode, thePlayer);thePlayer = advance[matchNode];}} else {//其他情况重构和赢者树相同tree[matchNode] = loser(leftChild, rightChild);advance[matchNode] = winner(leftChild, rightChild);if (matchNode == n - 1 && n % 2 == 1) {//特殊情况// 特殊在matchNode/2后，左孩子是内部节点，右孩子是外部节点matchNode /= 2;tree[matchNode] = loser(advance[n - 1], lowExt + 1);advance[matchNode] = winner(advance[n - 1], lowExt + 1);}matchNode /= 2;for (; matchNode >= 1; matchNode /= 2) {tree[matchNode] = loser(advance[matchNode * 2], advance[matchNode * 2 + 1]);advance[matchNode] = winner(advance[matchNode * 2], advance[matchNode * 2 + 1]);}}tree[0] = advance[1];//最终胜者
}template<class T>
void MinimumLoserTree<T>::output() const
{cout << "number of players = " << numberOfPlayers<< " lowExt = " << lowExt<< " offset = " << offset << endl;cout << "complete loser tree pointers are" << endl;for (int i = 1; i < numberOfPlayers; i++)cout << tree[i] << ' ';cout << endl;
}#endif //_31LOSERTREE_MINIMUMLOSERTREE_H

MinimumLoserTree.cpp

/*
Project name :			_30winnerTree
Last modified Date:		2023年12月19日16点48分
Last Version:			V1.0
Descriptions:			最小输者树——测试函数
*/
#include "MinimumLoserTree.h"void MinimumLoserTreeTest(){int n;cout << "Enter number of players, >= 2" << endl;cin >> n;if (n < 2){cout << "Bad input" << endl;exit(1);}int *thePlayer = new int[n + 1];cout << "Enter player values" << endl;for (int i = 1; i <= n; i++){cin >> thePlayer[i];}MinimumLoserTree<int> *w =new MinimumLoserTree<int>(thePlayer, n);cout << "The loser tree is" << endl;w->output();w->rePlay(2, 0);cout << "Changed player 2 to zero, new tree is" << endl;w->output();w->rePlay(3, -1);cout << "Changed player 3 to -1, new tree is" << endl;w->output();w->rePlay(7, 2);cout << "Changed player 7 to 2, new tree is" << endl;w->output();delete [] thePlayer;delete w;
}

loserTree.h

/*
Project name :			_30winnerTree
Last modified Date:		2023年12月19日16点48分
Last Version:			V1.0
Descriptions:			最小输者树——虚基类
*/#ifndef _31LOSERTREE_LOSERTREE_H
#define _31LOSERTREE_LOSERTREE_Htemplate<class T>
class loserTree {
public:virtual ~loserTree() {}virtual void initialize(T *thePlayer, int number) = 0;virtual int getTheWinner() const = 0;virtual void rePlay(int thePLayer, T newvalue) = 0;
};#endif //_31LOSERTREE_LOSERTREE_H

myExceptions.h

/*
Project name :			_30winnerTree
Last modified Date:		2023年12月18日16点28分
Last Version:			V1.0
Descriptions:			异常汇总
*/
#pragma once
#ifndef _MYEXCEPTIONS_H_
#define _MYEXCEPTIONS_H_
#include <string>
#include<iostream>
#include <utility>using namespace std;// illegal parameter value
class illegalParameterValue : public std::exception
{
public:explicit illegalParameterValue(string theMessage = "Illegal parameter value"){message = std::move(theMessage);}void outputMessage() {cout << message << endl;}
private:string message;
};// illegal input data
class illegalInputData : public std::exception
{
public:explicit illegalInputData(string theMessage = "Illegal data input"){message = std::move(theMessage);}void outputMessage() {cout << message << endl;}
private:string message;
};// illegal index
class illegalIndex : public std::exception
{
public:explicit illegalIndex(string theMessage = "Illegal index"){message = std::move(theMessage);}void outputMessage() {cout << message << endl;}
private:string message;
};// matrix index out of bounds
class matrixIndexOutOfBounds : public std::exception
{
public:explicit matrixIndexOutOfBounds(string theMessage = "Matrix index out of bounds"){message = std::move(theMessage);}void outputMessage() {cout << message << endl;}
private:string message;
};// matrix size mismatch
class matrixSizeMismatch : public std::exception
{
public:explicit matrixSizeMismatch(string theMessage ="The size of the two matrics doesn't match"){message = std::move(theMessage);}void outputMessage() {cout << message << endl;}
private:string message;
};// stack is empty
class stackEmpty : public std::exception
{
public:explicit stackEmpty(string theMessage ="Invalid operation on empty stack"){message = std::move(theMessage);}void outputMessage() {cout << message << endl;}
private:string message;
};// queue is empty
class queueEmpty : public std::exception
{
public:explicit queueEmpty(string theMessage ="Invalid operation on empty queue"){message = std::move(theMessage);}void outputMessage() {cout << message << endl;}
private:string message;
};// hash table is full
class hashTableFull : public std::exception
{
public:explicit hashTableFull(string theMessage ="The hash table is full"){message = std::move(theMessage);}void outputMessage() {cout << message << endl;}
private:string message;
};// edge weight undefined
class undefinedEdgeWeight : public std::exception
{
public:explicit undefinedEdgeWeight(string theMessage ="No edge weights defined"){message = std::move(theMessage);}void outputMessage() {cout << message << endl;}
private:string message;
};// method undefined
class undefinedMethod : public std::exception
{
public:explicit undefinedMethod(string theMessage ="This method is undefined"){message = std::move(theMessage);}void outputMessage() {cout << message << endl;}
private:string message;
};
#endif

运行结果

"C:\Users\15495\Documents\Jasmine\prj\_Algorithm\Data Structures, Algorithms and Applications in C++\_31loserTree\cmake-build-debug\_31loserTree.exe"
Enter number of players, >= 2
8
Enter player values
4
6
5
9
8
2
3
7
The loser tree is
number of players  = 8 lowExt = 8 offset = 7
complete winner tree pointers are
1 3 7 2 4 5 8
Changed player 2 to zero, new tree is
number of players  = 8 lowExt = 8 offset = 7
complete winner tree pointers are
6 3 7 1 4 5 8
Changed player 3 to -1, new tree is
number of players  = 8 lowExt = 8 offset = 7
complete winner tree pointers are
6 2 7 1 4 5 8
Changed player 7 to 2, new tree is
number of players  = 8 lowExt = 8 offset = 7
complete winner tree pointers are
6 2 7 1 4 5 8Process finished with exit code 0

这篇关于《数据结构、算法与应用C++语言描述》- 最小输者树模板的C++实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/513532。

相关文章

通俗易懂的Java常见限流算法具体实现

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》：本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1
阅读更多...
MySQL8.0设置redo缓存大小的实现

MySQL8.0设置redo缓存大小的实现

《MySQL8.0设置redo缓存大小的实现》本文主要在MySQL8.0.30及之后版本中使用innodb_redo_log_capacity参数在线更改redo缓存文件大小,下面就来介绍一下,具有一... mysql 8.0.30及之后版本可以使用innodb_redo_log_capacity参数来更改
阅读更多...
C++使用栈实现括号匹配的代码详解

C++使用栈实现括号匹配的代码详解

《C++使用栈实现括号匹配的代码详解》在编程中,括号匹配是一个常见问题,尤其是在处理数学表达式、编译器解析等任务时,栈是一种非常适合处理此类问题的数据结构,能够精确地管理括号的匹配问题,本文将通过C+... 目录引言问题描述代码讲解代码解析栈的状态表示测试总结引言在编程中，括号匹配是一个常见问题，尤其是在
阅读更多...
Java实现检查多个时间段是否有重合

Java实现检查多个时间段是否有重合

《Java实现检查多个时间段是否有重合》这篇文章主要为大家详细介绍了如何使用Java实现检查多个时间段是否有重合,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录流程概述步骤详解China编程步骤1：定义时间段类步骤2：添加时间段步骤3：检查时间段是否有重合步骤4：输出结果示例代码结语作
阅读更多...
使用C++实现链表元素的反转

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定
阅读更多...
Java覆盖第三方jar包中的某一个类的实现方法

Java覆盖第三方jar包中的某一个类的实现方法

《Java覆盖第三方jar包中的某一个类的实现方法》在我们日常的开发中,经常需要使用第三方的jar包,有时候我们会发现第三方的jar包中的某一个类有问题,或者我们需要定制化修改其中的逻辑,那么应该如何... 目录一、需求描述二、示例描述三、操作步骤四、验证结果五、实现原理一、需求描述需求描述如下：需要在
阅读更多...
如何使用Java实现请求deepseek

如何使用Java实现请求deepseek

《如何使用Java实现请求deepseek》这篇文章主要为大家详细介绍了如何使用Java实现请求deepseek功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1.deepseek的api创建2.Java实现请求deepseek2.1 pom文件2.2 json转化文件2.2
阅读更多...
python使用fastapi实现多语言国际化的操作指南

python使用fastapi实现多语言国际化的操作指南

《python使用fastapi实现多语言国际化的操作指南》本文介绍了使用Python和FastAPI实现多语言国际化的操作指南,包括多语言架构技术栈、翻译管理、前端本地化、语言切换机制以及常见陷阱和... 目录多语言国际化实现指南项目多语言架构技术栈目录结构翻译工作流1. 翻译数据存储2. 翻译生成脚本
阅读更多...
C++初始化数组的几种常见方法(简单易懂)

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化（推荐方式）1.2、初始化部分列表1.3、使用std::
阅读更多...
C++ Primer 多维数组的使用

C++ Primer 多维数组的使用

《C++Primer多维数组的使用》本文主要介绍了多维数组在C++语言中的定义、初始化、下标引用以及使用范围for语句处理多维数组的方法,具有一定的参考价值,感兴趣的可以了解一下... 目录多维数组多维数组的初始化多维数组的下标引用使用范围for语句处理多维数组指针和多维数组多维数组严格来说,C++语言没
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2