网站建设及推广服务的合同范本做网站用什么配置的笔记本

当前位置： 首页 > news >正文

网站建设及推广服务的合同范本,做网站用什么配置的笔记本,wordpress showposts,百度推广怎么收费标准目录 一. 如何使用一颗红黑树同时实现map和set 二. 红黑树的节点插入操作 三. 红黑树迭代器的实现 3.1 begin()和end() 3.2 operator和operator– 3.3 红黑树迭代器实现完整版代码 四. map和set的封装 附录#xff1a;用红黑树封装map和set完整版代码

1. RBTree.h文件…目录 一. 如何使用一颗红黑树同时实现map和set 二. 红黑树的节点插入操作 三. 红黑树迭代器的实现 3.1 begin()和end() 3.2 operator和operator– 3.3 红黑树迭代器实现完整版代码 四. map和set的封装 附录用红黑树封装map和set完整版代码
2. RBTree.h文件
3. map.h文件 3. set.h文件 一. 如何使用一颗红黑树同时实现map和set 我们知道map和set的底层都是通过红黑树来实现的它们的不同在于map存储的是一键值对键值对的第一个数据用于搜索树的比较第二个数据用于与之配对而set则只有一个数据。需要采用模板泛型编程的方法来定义红黑树节点并在map和set中给定红黑树类模板不同的模板参数类型 图1.1 红黑树节点、红黑树类模板与map和set类模板之间的关系 观察图1.1我们可以总结出RBTreeNode、RBTree、map和set类模板之间的如下规则 红黑树节点只有一个模板参数set有一个模板参数其本身就是节点的数据类型map有两个模板参数分别为创建键值对的first和second数据类型。在map中RBTreeNode中的模板参数类型为pair键值对由于map中要取出键值对的first比较创建搜索树而直接用或对pair比较不符合要求因此定义仿函数KeyOfV来获取用于比较的数据。 二. 红黑树的节点插入操作 用于对map和set封装的红黑树的查找操作与普通红黑树一致唯一的不同在于需要创建KeyOfV类的对象并使用仿函数进行比较。如果希望与库中的insert更加贴合则应返还键值对pairiterator, bool类型数据。 具体的红黑树的插入实现流程可参考博文C数据结构手撕红黑树_【Shine】光芒的博客-CSDN博客 代码2.1红黑树节点插入 std::pairiterator, bool insert(const T date){//插入第一个节点if (_root nullptr){_root new Node(date);_root-_col BLACK; //根节点为黑色return std::make_pair(_root, true);}KeyOfT kov; //用于筛选比较数据的类对象//寻找节点插入的位置Node* parent nullptr; Node* cur _root;while (cur){//如果cur节点的key值大于插入键值对的key向左子树查找if (kov(cur-_date) kov(date)){parent cur;cur cur-_left;}else if(kov(cur-_date) kov(date)) //如果cur节点的key值小于插入键值对的key向左子树查找{parent cur;cur cur-_right;}else //相等表明节点已存在插入失败{return std::make_pair(cur, false);}}//判断新节点是parent的左节点还是右节点链接//默认新插入的节点为红色cur new Node(date);Node* newNode cur;cur-_col RED;cur-_parent parent;if (kov(parent-_date) kov(date)){parent-_left cur;}else{parent-_right cur;}//如果parent节点不为空且为红色那么红黑树的结构在插入节点后被破坏需要调整while (parent parent-_col RED){Node* grandParent parent-_parent; //祖父节点assert(grandParent);assert(grandParent-_col BLACK); //断言检查如果祖父节点为空或为黑色那么红黑树结构在节点插入之前就存在问题if (parent grandParent-_left) //插入在祖父节点的左子树{Node* uncle grandParent-_right;//情况一cur为红parent为红grandFather为黑uncle为红if (uncle uncle-_col RED){//将parent节点和uncle节点变为黑grandFather节点变为红然后继续向上调整parent-_col BLACK;uncle-_col BLACK;grandParent-_col RED;cur grandParent;parent cur-_parent;} else //情况二、三cur为红parent为红grandFather为黑uncle不存在或为黑{if (parent-_left cur){//情况二 – 进行右单旋 变色(parent变黑,grandFather变红)// g// p u//cRotateR(grandParent);parent-_col BLACK;grandParent-_col RED;}else{//情况三 – 进行左右双旋 变色cur节点变为黑grandFater节点变为红// g// p u// u RotateLR(grandParent);cur-_col BLACK;grandParent-_col RED;}break;}}else //parent grandParent-_right{Node* uncle grandParent-_left; //叔叔节点//情况一cur为红parent为红grandFather为黑uncle为红if (uncle uncle-_col RED){//将parent节点和uncle节点变为黑grandFather节点变为红然后继续向上调整parent-_col BLACK;uncle-_col BLACK;grandParent-_col RED;cur grandParent;parent cur-_parent;}else{//情况二、三cur为红parent为红grandFather为黑uncle不存在或为黑if (parent-_right cur){//情况二 – 进行右单旋 变色(parent变黑,grandFather变红)// g// u p// cRotateL(grandParent);parent-_col BLACK;grandParent-_col RED;}else{//情况三 – 进行右左双旋 变色cur节点变为黑grandFater节点变为红// g// u p// cRotateRL(grandParent);cur-_col BLACK;grandParent-_col RED;}break;}}}_root-_col BLACK; //根节点为黑色return std::make_pair(newNode, true);} 三. 红黑树迭代器的实现 我们要额外封装一个类struct  __RBTree_iterator_来实现红黑树迭代器这个类有三个模板参数T、Ref、Ptr这样做的目的是定义一份迭代器类模板就可以实现普通迭代器和const迭代器。 typedef __RBTree_iterator_T, T, T* iterator;   //红黑树迭代器 3.1 begin()和end() STL标准规定迭代器区间begin()和end()为左闭右开区间而对红黑树遍历获取的数据为升序序列因此begin()应该为左下角位置处的节点end()应该为哨兵卫的头结点_head。这里从便于理解和实现的角度出发将_head设为nullptr即end()返回空指针。 图3.1 红黑树的begin()和end() 代码3.1begin和end //获取begin()位置 – 最左侧节点iterator begin(){Node* left _root;while (left left-_left){left left-_left;}return iterator(left);}iterator end(){return iterator(nullptr);} 3.2 operator和operator– operator就是查找中序遍历的下一个节点可分为两种情况讨论 如果节点的右子树不为空则为右子树最左侧的节点。如果节点的右子树为空则向上查找孩子不是父亲的右子节点的那个节点。 图3.2 operator的两种情况 operator–与operator正好相反为找中序遍历的前一个节点亦可分两种情况讨论 如果节点的左子树不为空则为左子树最右侧的节点。如果节点的左子树为空则向上查找孩子不是父亲的左子节点的那个节点。 图3.3 operator–的两种情况 代码3.2operator和operator– typedef RBTreeNodeT Node; //红黑树节点typedef __RBTree_iterator_T, Ref, Ptr Self; //运算符重载函数Self operator(){if (_node-_right ! nullptr){//找右子树的最左侧节点Node* left _node-_right;while (left-_left){left left-_left;}_node left;}else{//找孩子节点为左孩子节点的位置或者父亲节点为空Node* parent _node-_parent;Node* cur _node;while (parent parent-_right cur){cur cur-_parent;parent parent-_parent;}_node parent;}return this;}//–运算符重载函数Self operator–(){if (_node-_left ! nullptr){Node right _node-_left;while (right-_right){right right-_right;}_node right;}else{Node* parent _node-_parent;Node* cur _node;while (parent parent-_left cur){cur cur-_parent;parent parent-_parent;}_node parent;}return this;} 3.3 红黑树迭代器实现完整版代码 //红黑树迭代器模板 templateclass T, class Ref, class Ptr struct __RBTreeiterator {typedef RBTreeNodeT Node; //红黑树节点typedef __RBTree_iterator_T, Ref, Ptr Self;Node _node;//构造函数__RBTreeiterator(Node* node): _node(node){ }//解引用函数Ref operator(){return _node-_date;}//成员访问操作符-重载Ptr operator-(){return _node-_date;}bool operator(const Self it) const{return _node it._node;}bool operator!(const Self it) const{return _node ! it._node;}//运算符重载函数Self operator(){if (_node-_right ! nullptr){//找右子树的最左侧节点Node left _node-_right;while (left-_left){left left-_left;}_node left;}else{//找孩子节点为左孩子节点的位置或者父亲节点为空Node* parent _node-_parent;Node* cur _node;while (parent parent-_right cur){cur cur-_parent;parent parent-_parent;}_node parent;}return this;}//–运算符重载函数Self operator–(){if (_node-_left ! nullptr){Node right _node-_left;while (right-_right){right right-_right;}_node right;}else{Node* parent _node-_parent;Node* cur _node;while (parent parent-_left cur){cur cur-_parent;parent parent-_parent;}_node parent;}return *this;} }; 四. map和set的封装 map和set底层都是通过红黑树来实现的只需在map和set中定义一颗红黑树的自定义类型变量然后调用红黑树的接口函数即可。 这里需要特别注意的是map中的operator[]函数其实现为先调用insert函数insert函数返回一个键值对first为插入的节点或Key与插入节点相等位置的迭代器second为bool类型变量用来表示是否有新节点成功插入。函数只需返回insert返回的键值对的second的引用即可。 注意用于提取Key的仿函数要在map和set中分别定义。 代码4.1map的封装 namespace zhang {template class K, class Vclass map{struct KeyOfV{const K operator()(const std::pairK,V val){return val.first;}};public:typedef typename RBTreeK, std::pairK, V, KeyOfV::iterator iterator;std::pairiterator, bool insert(const std::pairK, V kv){return _t.insert(kv);}iterator begin(){return _t.begin();}iterator end(){return _t.end();}V operator{std::pairiterator, bool ret insert(std::make_pair(key, V()));return ret.first-second;}private:RBTreeK, std::pairK,V, KeyOfV _t; //红黑树}; } 代码4.2set的模拟实现 namespace zhang {template class Kclass set{struct KeyOfV{const K operator()(const K val){return val;}};public:typedef typename RBTreeK, K, KeyOfV::iterator iterator;std::pairiterator, bool insert(const K key){return _t.insert(key);}iterator begin(){return _t.begin();}iterator end(){return _t.end();}K operator{std::pairiterator, bool ret insert(key);return *ret.first;}private:RBTreeK, K, KeyOfV _t; //红黑树}; }附录用红黑树封装map和set完整版代码
4. RBTree.h文件 #includeiostream #includeassert.h//枚举常量 – 红色、黑色 enum Color {RED,BLACK };//定义红黑树节点 templateclass T struct RBTreeNode {RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;T _date; //数据值set为单个值map为键值对pairColor _col; //节点颜色RBTreeNode(const T date) //节点构造函数: _left(nullptr), _right(nullptr), _parent(nullptr), _date(date), _col(RED){ } };//红黑树迭代器模板 templateclass T, class Ref, class Ptr struct __RBTreeiterator {typedef RBTreeNodeT Node; //红黑树节点typedef RBTree_iterator_T, Ref, Ptr Self;Node* _node;//构造函数RBTreeiterator(Node* node): _node(node){ }//解引用函数Ref operator(){return _node-_date;}//成员访问操作符-重载Ptr operator-(){return _node-_date;}bool operator(const Self it) const{return _node it._node;}bool operator!(const Self it) const{return _node ! it._node;}//运算符重载函数Self operator(){if (_node-_right ! nullptr){//找右子树的最左侧节点Node left _node-_right;while (left-_left){left left-_left;}_node left;}else{//找孩子节点为左孩子节点的位置或者父亲节点为空Node* parent _node-_parent;Node* cur _node;while (parent parent-_right cur){cur cur-_parent;parent parent-_parent;}_node parent;}return this;}//–运算符重载函数Self operator–(){if (_node-_left ! nullptr){Node right _node-_left;while (right-_right){right right-_right;}_node right;}else{Node* parent _node-_parent;Node* cur _node;while (parent parent-_left cur){cur cur-_parent;parent parent-_parent;}_node parent;}return this;} };//红黑树类模板 templateclass K, class T, class KeyOfT class RBTree {typedef RBTreeNodeT Node; //类型重定义红黑树节点public:typedef __RBTree_iterator_T, T, T iterator; //迭代器std::pairiterator, bool insert(const T date){//插入第一个节点if (_root nullptr){_root new Node(date);_root-_col BLACK; //根节点为黑色return std::make_pair(_root, true);}KeyOfT kov; //用于筛选比较数据的类对象//寻找节点插入的位置Node* parent nullptr; Node* cur _root;while (cur){//如果cur节点的key值大于插入键值对的key向左子树查找if (kov(cur-_date) kov(date)){parent cur;cur cur-_left;}else if(kov(cur-_date) kov(date)) //如果cur节点的key值小于插入键值对的key向左子树查找{parent cur;cur cur-_right;}else //相等表明节点已存在插入失败{return std::make_pair(cur, false);}}//判断新节点是parent的左节点还是右节点链接//默认新插入的节点为红色cur new Node(date);Node* newNode cur;cur-_col RED;cur-_parent parent;if (kov(parent-_date) kov(date)){parent-_left cur;}else{parent-_right cur;}//如果parent节点不为空且为红色那么红黑树的结构在插入节点后被破坏需要调整while (parent parent-_col RED){Node* grandParent parent-_parent; //祖父节点assert(grandParent);assert(grandParent-_col BLACK); //断言检查如果祖父节点为空或为黑色那么红黑树结构在节点插入之前就存在问题if (parent grandParent-_left) //插入在祖父节点的左子树{Node* uncle grandParent-_right;//情况一cur为红parent为红grandFather为黑uncle为红if (uncle uncle-_col RED){//将parent节点和uncle节点变为黑grandFather节点变为红然后继续向上调整parent-_col BLACK;uncle-_col BLACK;grandParent-_col RED;cur grandParent;parent cur-_parent;} else //情况二、三cur为红parent为红grandFather为黑uncle不存在或为黑{if (parent-_left cur){//情况二 – 进行右单旋 变色(parent变黑,grandFather变红)// g// p u//cRotateR(grandParent);parent-_col BLACK;grandParent-_col RED;}else{//情况三 – 进行左右双旋 变色cur节点变为黑grandFater节点变为红// g// p u// u RotateLR(grandParent);cur-_col BLACK;grandParent-_col RED;}break;}}else //parent grandParent-_right{Node* uncle grandParent-_left; //叔叔节点//情况一cur为红parent为红grandFather为黑uncle为红if (uncle uncle-_col RED){//将parent节点和uncle节点变为黑grandFather节点变为红然后继续向上调整parent-_col BLACK;uncle-_col BLACK;grandParent-_col RED;cur grandParent;parent cur-_parent;}else{//情况二、三cur为红parent为红grandFather为黑uncle不存在或为黑if (parent-_right cur){//情况二 – 进行右单旋 变色(parent变黑,grandFather变红)// g// u p// cRotateL(grandParent);parent-_col BLACK;grandParent-_col RED;}else{//情况三 – 进行右左双旋 变色cur节点变为黑grandFater节点变为红// g// u p// cRotateRL(grandParent);cur-_col BLACK;grandParent-_col RED;}break;}}}_root-_col BLACK; //根节点为黑色return std::make_pair(newNode, true);}//中序遍历函数void InOrder(){_InOrder(_root);std::cout std::endl;}//红黑树检验函数bool IsRBTree(){//空树是合法的红黑树if (_root nullptr){return true;}//检查根节点颜色if (_root-_col RED){std::cout 根节点颜色不是黑色 std::endl;}int baseBlackNum 0; //基准黑色节点个数//以最左侧路径为基准计算黑色节点个数每条路径黑色节点数目都应该相同Node* cur _root;while (cur){if (cur-_col BLACK){baseBlackNum;}cur cur-_left;}bool blackNumTrue PrevCheck(_root, 0, baseBlackNum); //检查每条路径黑色节点数目是否相同bool colorTrue CheckColor(_root); //检查是否存在连续红色节点return blackNumTrue colorTrue;}//获取begin()位置 – 最左侧节点iterator begin(){Node* left _root;while (left left-_left){left left-_left;}return iterator(left);}iterator end(){return iterator(nullptr);}private:bool CheckColor(Node* root){if (root nullptr){return true;}//如果本节点为红色且父亲节点也为红色证明存在连续红色节点结构错误if (root-_col RED root-_parent root-_parent-_col RED){std::cout 存在连续的红色节点 std::endl;return false;}return CheckColor(root-_left) CheckColor(root-_right);}bool PrevCheck(Node* root, int blackNum, int baseBlackNum){if (root nullptr){if (blackNum ! baseBlackNum){std::cout 每条路径上黑色节点的数目不同 std::endl;return false;}else{return true;}}if (root-_col BLACK){blackNum;}return PrevCheck(root-_left, blackNum, baseBlackNum) PrevCheck(root-_right, blackNum, baseBlackNum);}void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);std::cout root-_kv.first ;_InOrder(root-_right);}void RotateR(Node* parent) //右单旋函数{Node* pNode parent-_parent; Node* pL parent-_left; //左子节点Node* pLR pL-_right; //左子节点的右子节点//将pLR节点托管给parent节点的左子节点parent-_left pLR;if (pLR ! nullptr){pLR-_parent parent;}//将父亲节点托管给pL节点的右子节点pL-_right parent; parent-_parent pL;//此时这颗进行旋转的子树的根节点变为了pLpL要与pNode节点连接if (parent _root){_root pL;pL-_parent nullptr;}else{pL-_parent pNode;if (pNode-_left parent){pNode-_left pL;}else{pNode-_right pL;}}}void RotateL(Node* parent) //左单旋函数{Node* pNode parent-_parent;Node* pR parent-_right; //右子节点Node* pRL pR-_left; //右子节点的左子节点//将pLR节点托管给parent节点的右子节点parent-_right pRL;if (pRL ! nullptr){pRL-_parent parent;}//将parent节点托管给pR的左子节点pR-_left parent;parent-_parent pR;if (_root parent){_root pR;_root-_parent nullptr;}else{pR-_parent pNode;if (pNode-_left parent){pNode-_left pR;}else{pNode-_right pR;}}}void RotateLR(Node* parent) //左右双旋函数{RotateL(parent-_left);RotateR(parent);}void RotateRL(Node* parent) //右左双旋函数{RotateR(parent-_right);RotateL(parent);}private:Node* _root nullptr; };
5. map.h文件 #include RBTree.hnamespace zhang {template class K, class Vclass map{struct KeyOfV{const K operator()(const std::pairK,V val){return val.first;}};public:typedef typename RBTreeK, std::pairK, V, KeyOfV::iterator iterator;std::pairiterator, bool insert(const std::pairK, V kv){return _t.insert(kv);}iterator begin(){return _t.begin();}iterator end(){return _t.end();}V operator{std::pairiterator, bool ret insert(std::make_pair(key, V()));return ret.first-second;}private:RBTreeK, std::pairK,V, KeyOfV _t; //红黑树}; } 3. set.h文件 namespace zhang {template class Kclass set{struct KeyOfV{const K operator()(const K val){return val;}};public:typedef typename RBTreeK, K, KeyOfV::iterator iterator;std::pairiterator, bool insert(const K key){return _t.insert(key);}iterator begin(){return _t.begin();}iterator end(){return _t.end();}K operator{std::pairiterator, bool ret insert(key);return *ret.first;}private:RBTreeK, K, KeyOfV _t; //红黑树}; }