data stractures and algorithm analysis in c++
作为本书笔记. 大概一天1.5章
第一章
本书主要的介绍方式是基于对象的, 也就是说使用了对象的一些特征, 但是不是面向对象的, 面向对象主要的特征是继承和多态, 所谓继承就是把一些类似的类归到一个抽象类上, 定义一个统一的接口, 所谓多态, 就是在实现的时候可以根据具体情况对父类的方法进行覆盖, 即父可以是子, 但子不一定是父, 这点最重要.
一个主要的内容是对一个程序, 如何估计其运行时间, 找到瓶颈, 进行优化.
数学
一个需要注意的是
$$log1=0,log2=1,log1024=10,log1048576=20$$
$$\sum_{i=0}^N2^i=2^{N+1}-1$$
$$\sum_{i=0}{N}A^i=\frac{A^{N+1}-1}{A-1}$$
当$0<A<1$
$$\sum_{i=0}^{N}A^i\leq\frac{1}{1-A}$$
调和数
$$\sum_{i=1}^{N}\frac{1}{i}=H_N$$
近似为
$$log_eN$$, 在$N\rightarrow\infty$时, 两者的差距就是欧拉常数$y=0.577$
$$\sum_{i=1}^{N}i^k=\frac{N^{k+1}}{|k+1|}$$
递归
- 基准条件
- 向基准逼近
- 假设能运行
- 同样的计算不要重复
c++类
类定义中存在private和public, 注意没有定义的时候是默认private.使用这种方法进行信息隐藏, 也就是封装.
在函数后面添加:进行初始化列表. 如const成员只能这样初始化.
可以使用()和{}进行初始化.
explicit避免强制类型转换.
在函数后面添加const表示函数是一个访问函数, 对数据不进行修改.(这只在对象里使用, 所谓访问函数和修改函数, 关键在于会不会修改对象的状态)
接口与实现的分离, 可以在头文件中定义一个类的接口, 但是不用具体实现, 在.cpp文件中定义实现, 使用::表达类作用于来定义函数.
注意头文件中一般都有#ifndef xxx_H #endif
防止重复加载头文件. 实际上xxx_H只是一个标志头文件有没有加载成功的表示符, 防止重复加载. 在实现文件中#include 头文件, 定义实现. 之后再实际main函数中就只用在#include 头文件就可以了. 注意对于系统的一般使用<>, 对于自己的头文件使用””
注意在实现接口的时候特征必须完全匹配. 所谓特征(signature)就是访问还是修改函数这个特征.
一般使用vector来代替数组, 最主要的原因是vector是一个类, 我们可以保存有用的信息如数组的大小以及对它进行一些方便的操作. 同时内置的字符串就是一个数组, 因此==不能对其进行比较. 形成类后就可以使用== <=等进行比较.
初始化
- vector
da(12) - vector
da{12,3,124121,123}
for(auto x:da)
xx
for(auto &x:da)
x++
注意这里:就相当于python的 in.
c++细节
指针作为存储地址的变量.
incell m;
表示为指针.
动态创建 xx = new xx();
new进行创建的都是指针, 但是使用构造函数得到的是对象.
注意new出来的对象在堆里面, 如果不delete的话会一直占用内存, 造成内存泄漏.
直接操作指针对象的内容用->, 提取对象用*, 取地址用&
左值和右值
含有标识符的就是左值, 而”sdas”就是右值, 作为临时量, 传递后就消失, 因此赋值的时候是直接移动, 而左值的赋值是复制, 因此有复制开销.
- & 左值引用
- &&右值引用
引用的作用在于避免复制.
& 放在表达式中间 const vector
- 对于小的不被函数改变的对象, 用传值
- 大的不被函数改变的, 可以传常量引用
- 对于可以被改变的对象, 直接传引用就ok
在函数定义的时候写&&就可以进行右值重载.
std::swap和std::move
使用std::move把一个左值变成右值, 就可以减少复制开销.
五大函数
- 拷贝构造, 使用同类型对象对新类型进行初始化, 称为构造, 如果是左值, 就是拷贝构造, 右值就是移动构造, vector
aa{aab}; - 移动构造
- 拷贝赋值, 是针对=符号的, 要定义如 IntCell & operator= (const IntCell & rhs);
- 移动赋值 IntCell & operator= (IntCell && rhs);可以利用&&来分辨是左值还是右值
- 析构函数, 对于对象运行越出范围或者delete操作, 调用, 大部分情况下都是作为释放掉对象使用的资源. ~IntCell(), 使用~开头.
模板
模板实际上就是参数化类型, 用来进行泛型
如函数模板和类模板. 在开头加个template就可以了.
注意inline函数就对于个别经常调用的小函数使用的, 实际上就是一个#define 但是不同的是像一个函数一样进行类型检验, 展开.
泛型算法通过iterator进行操作, 进一步抽象类型.
算法分析
这一章主要讲算法分析, 分析了大$O$, $\Omega$的意义, 并引出对数算法的效率问题, 作为一个例子, 最大子序列问题
int maxSumSeq(const vector & vec)
{
int thisSum = 0, maxSum = 0;
for(auto i;vec)
{
thisSum += i;
if (thisSum > maxSum)
maxSum = thisSum;
else if (thisSum < 0)
thisSum = 0;
}
return maxSum;
}
GCD
long long gcd(long long m, long long n){
if (n == 0)
return m;
return gcd(n, m%n);
}