NineTSe

一、红黑树简介 红黑树的规则有 1.每个节点不是红色就是黑色2.根节点是黑色3.如果一个节点是红色，它的两个孩子节点是黑色4.每条路径都有相同数量的黑色节点5.叶子节点(Nullptr节点)是黑的 这些规则可以推导出红黑树的特性 其最长路径不超过最短路径的两倍,近似平衡没有连续的红节点左右子树的黑节点个数相同 其相较于AVL树并没有过多的旋转用较不平衡换取了性能 在实际中,红黑树的应用相较于AVL树更加常用 二、红黑树的模拟实现 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281 ...

一、模拟实现AVL树 AVL树就是高度平衡二叉搜索树所有树的左右子树高度差不超过1平衡因子 = 右子树高度 - 左子树高度 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791 ...

一、key模型搜索二叉树的模拟实现 1.非递归实现123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170#pragma once#include<iostream>using namespace std;template<clas ...

一、继承方式和访问方式 注意:友元不能继承,静态成员只会在父类创造一次 父类如果用private修饰的成员,子类无法访问protected修饰的子类可以访问,但除此之外不可访问 继承方式为private,struct为public ,一般继承方式都为public基类的成员在子类的访问方式 = ==Min(成员在基类的访问限定符,继承方式) 二、赋值兼容规则 1234567891011121314151617181920212223242526int main(){ //1.子类对象可以赋值给父类对象/指针/引用 person p; student s; p = s;//对象赋值 s = p;//不行 //子类赋值给父类,通过切割(切片)可以进行赋值 person* ptr = &s; //指针 person& ref = s; //引用 //student* sptr = &p; //父类赋值给子类,不行 student* sptr = (student*)&s; //ptr指向的本来就是子 ...

一、虚函数 1.重载,重写(覆盖),重定义(隐藏)的对比 重载: 两个函数在一个作用域,函数名相同,参数不同.重写(覆盖): 两个函数分别在基类和派生类的作用域函数名,返回类型,参数都必须相同(协变例外),两个函数必须是虚函数.重定义(隐藏): 两个函数分别在基类和派生类的作用域函数名相同,两个基类和派生类的同名函数不构成重写(覆盖)就是重定义 2.虚函数的重写 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152class person{public: void BuyTicket() //输出全为all //virtual void BuyTicket() //正确的输出 { cout << "all" << endl; }};class student : public person{public: void Buy ...

一、priority_queue简介 priority_queue也是适配出来的其与queue不同点在于能够排序,因为底层是由heap实现的,并且 12345#include<queue>#include<functionnal> //默认仿函数 greater / lesspriority_queue<int> pq; //此时输出默认顺序是降序的,大堆priority_queue<int, vector<int>, greater<int>> pq; 二、模拟实现 仿函数的使用,向上向下调整算法 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104 ...

一、适配器和迭代器 迭代器模式 是STL中的迭代器在封装后不暴露内部细节，使得上层使用时达到一种统一的方法访问适配器模式 是通过原内容封装转换出形式 stack 和 queue 通过容器适配转换出来的,不是原生实现的 二、stack stack没有迭代器 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253namespace bsy{ template<class T , class Container> //stack类模拟实现 class stack { public: void push(const T& x) { _con.push_back(x); } void pop() { _con.pop_back(); } size_t size() { return _con.size(); } bool ...

一、list要注意事项 1.迭代器失效 list没有增容销毁空间这一说,因此insert等插入不会导致失效erase也是返回下一个位置的迭代器 12345if (*it % 2 == 0) it = l.erase(it); //erase 会导致迭代器失效 //空间被erase后不能再进行操作,即++,*;else ++it; 2.splic(连接两个链表) 1234567891011121314151617list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);list<int> lt;lt.push_back(10);lt.push_back(20);lt.push_back(30);lt.push_back(40);list<int>::iterator pos = l.begin();++pos;l.splice(pos, lt); //在 l 链表中的pos位置插入lt链表Print_list(l); // ...

一、vector的注意事项 1. [] 和 at() 的越界访问 123456789101112vector<int> v1{ 1,2,3,4 };//v1[4] = 5; //越界直接结束,assert判断try{ v1.at(4) = 5; //抛异常}catch (...){ cout << "beyond" << endl; //输出beyond} 2.迭代器失效问题 简单来说就是在迭代器创建后使用了reverse,resize,insert,push_back等导致的增容导致迭代器仍然指向已经被释放的旧空间 一个应对迭代器失效的过程 12345678910111213141516171819202122232425262728293031 //删除容器中所有的偶数vector<int>::iterator it = v.begin();while (it != v.end()){ if (*it % 2 == 0)  ...

一、关于string常用的接口 1.string类对象的创建 1234567891011121314151617181920//关于string类对象的创建string s1;string s2("hello");string s3(s2); //这三个是常用且重点的,以下是了解一下string s4("hello", 2); //输出前两个字符cout << s4 << endl;string s5(s2, 2, 1); //输出s2内,第2个开始输出,输出1个字符cout << s5 << endl;string s6(s2, 2); //输出s2内,第2个开始输出,输出至结束cout << s6 << endl;string s7(s2, 2,string::npos); //输出s2内,第2个开始输出,输出至结束cout << s7 << endl;string s8(10, &# ...