0%

位图

每一个比特位来表示当前比特位对应的数据是否存在,存在为1,不存在为0

整数数组:

  1. 整数位置:n/32
  2. 整数位置中具体的bit位置:n%32
  • 右移相当于除,右移n位 == 数字➗2^n^

位图实现:哈希表

  1. 实现:整数数组
  2. 数据单元是bit位
  3. 节省空间,一个字节可以存放8个整数的二值信息(存在与否),不存放数据本身
  4. 操作效率高,通过哈希映射获取位置,通过位运算执行操作, 时间效率O(1)
  5. 位置映射:
    1. 获取整数位置,n / 32
    2. 获取整数的比特位:n % 32
  6. 位图需要的空间大小和数据的范围有关,和数据本身大小没有关系
  7. 适合的场景:数据不重复,信息简单
阅读全文 »

二叉搜索树

  • 若左子树非空,则左子树上所有节点的值都小于根节点的值
  • 若右子树非空,则右子树上所有节点的值都小根节点的值
  • 左右子树也是二叉搜索树

上述条件反之亦可

阅读全文 »

多态的概念、定义以及实现

多种形态,当不同的对象去执行同一种行为时,产生的不同表现形态

构成条件:在不同的继承关系的类对象,去调用同一函数,产生了不同的行为

  1. 继承关系
  2. 必须通过基类的指针或者引用调用的虚函数,一般都是用父类指针/引用指向父类以及子类实体,即都为切片行为
  3. 被调用的函数必须是虚函数,且派生类必须对基类的虚函数进行重写
阅读全文 »

继承概念

类级别的代码复用

  1. 继承方式:public、protected、private
  2. protectde访问权限/private访问权限:
    • protected —-> 在当前类和子类中可见,在其他地方不可见
    • private —-> 在当前类中可见,在其他地方不可见
  3. 父类成员在子类中的访问权限:min { 成员在父类中的原始访问权限,继承方式 }
  4. 一般都是public继承,protected/private继承很少使用/几乎不用
  5. 默认继承方式:
    • class定义的类默认继承方式是private
    • struct定义的类默认继承方式public
阅读全文 »

stack的基本使用

1
2
3
4
5
6
7
8
9
10
11
#include<stack>
stack<int> st;
st.push(1);
st.push(2);
st.push(3);
while(!st.empty())
{
cout << st.top() << " ";
st.pop();
}
cout << endl;
阅读全文 »

list的基本使用

本质为双向带头循环列表

  1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。
  2. list的底层是双向带头循环链表,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。
  3. 与其他的序列式容器相比(array,vector,deque),list通常在任意位置进行插入、移除元素的执行效率更好。
  4. 与其他序列式容器相比,list和forward_list最大的缺陷是不支持任意位置的随机访问,比如:要访问list的第6个元素,必须从已知的位置(比如头部或者尾部)迭代到该位置,在这段位置上迭代需要线性的时间开销;list还需要一些额外的空间,以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)
阅读全文 »

vector的基本使用

1
2
3
4
5
6
7
8
9
10
vector<int> v;
vector<char> v2;
vector<string> v3;

vector<int> v4(10, 5);//10个5

string s2 = "0123456789";
vector<char> v5(s2.begin(), s2.end());

vector<char> v6(v5);
阅读全文 »

string类基本使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <string>

void test()
{
string str;//""
string str2("123");//"123"
string str3 = "abc";//"abc"
string str4("0123456789", 5);//"01234"
string cpy(str3);//"abc"

string str5(str4, 2, 2);//"23" 从str4的第2个位置拿两个字符创建一个字符串
string str6(10, a);//"aaaaaaaaaa"

str6 = str5;//操作符重载
str6 = "321";
str6 = "xyz";
}
阅读全文 »

泛型编程

编写与类型无关的代码

1
template <typename / class 泛型参数1, typename / class 泛型参数2 ...... >

告诉编译器一个模板,让编译器根据不同的类型利用该模板生成代码

阅读全文 »

C/C++内存分布

  1. 栈:非静态局部变量,函数参数,返回值等,栈是向下增长的
  2. 内存映射段:装载一个共享的动态内存库
  3. 堆:用于程序运行时动态内存分配,可以向上增长
  4. 数据段:存储全局变量和静态数据
  5. 代码段:可执行的代码、只读常量
阅读全文 »