织梦网站响应式模板免费下载,网站开发开题报告计划进度安排,百度竞价排名黑幕,360网页游戏大全输者树
完整可编译运行代码见#xff1a;Github::Data-Structures-Algorithms-and-Applications/_31loserTree
输者树#xff1a;每一个内部节点所记录的都是比赛的输者#xff0c;晋级的节点记录在边上。本文中#xff0c;赢者是分数较低的那个#xff0c;输者是分数高…输者树
完整可编译运行代码见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
#includeiostream
#include loserTree.h
#include myExceptions.h
using namespace std;void MinimumLoserTreeTest();templateclass T
class MinimumLoserTree : public loserTreeT {
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; };//返回更大的元素下标
};templateclass T
void MinimumLoserTreeT::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);//s2^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]是最终的赢者也就是决赛的赢者}templateclass T
void MinimumLoserTreeT::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;//向上搜索}
}templateclass T
void MinimumLoserTreeT::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];//最终胜者
}templateclass T
void MinimumLoserTreeT::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_HMinimumLoserTree.cpp
/*
Project name : _30winnerTree
Last modified Date: 2023年12月19日16点48分
Last Version: V1.0
Descriptions: 最小输者树——测试函数
*/
#include MinimumLoserTree.hvoid 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];}MinimumLoserTreeint *w new MinimumLoserTreeint(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_Htemplateclass 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_HmyExceptions.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
#includeiostream
#include utilityusing 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 doesnt 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
