README.md

C/C++基础知识

知识列表

零散知识点

• int i = i;是合法的，是先进行的变量定义然后进行的赋值
• printf参数的计算是从右到左的，因此需要注意++和--的问题
• 通过x&(x-1)可以判断x中1的个数，通过x|(x+1)可以判断x中0的个数
• 交换a,b可以使用a = a ^ b; b = a ^ b; a = a ^ b;注意，如果ab指向同一个地址的时候会出错，因此需要判断一下
• 一个数两次异或同一个数之后又变回原数
• C与C++编译器对函数的命名不一致，因此可以通过extern “C”来解决名字匹配问题
• mutable修饰的成员变量可以在const类型的成员函数中修改
• 32位系统中，sizeof指针得到的都是值恒为4， sizeof数组名得到是数组的大小， 另外注意的是将数组名作为形参时数组名会退化为指针
• 定义const常量时必须初始化，比如 const int a = 6；
• define与--i一起使用时容易出错
• const类型和引用类型必须通过参数列表进行初始化
• 只有const static 类型的整形的成员变量才可以在类中初始化
• 静态的数据成员必须初始化，并且在类外初始化，并且初始化的时候是没有static关键字的，为什么这样呢，因为static成员变量在类中是声明而不是定义，而类外的才算定义
• 初始化列表的初始化顺序时根据成员变量的声明顺序来执行的
• 析构函数时可以定义为内联的
• 构造函数可以抛异常，析构函数不可以抛异常（如果析构函数捕获了自己抛出的异常则另当别论）
• 阻止一个类实例化有两种方式：设置为纯虚函数；将构造函数声明为private
• 一个类如果想使用static_cast<char *>实现强制类型转换，则类中需要实现转换函数，声明为operation char*()，无参数，无返回类型，以转换目标类型为函数名，其函数定义中需要返回转换结果
• typeid返回的时type_info常量对象的引用
• 非静态成员函数操作符（带1个参数）时是二元运算符，非成员函数操作符（带2个参数）时是二元运算符
• assert是宏定义不是函数，主要目的是保证在debug和release版本程序的内存和代码结构不变
• inline需要放在函数的定义前边，缺省参数是放在声明里的
• string a = c;调用的拷贝构造函数； a = c调用的是赋值运算符函数
• 派生类的构造函数应该在其初始化列表中调用基类的构造函数
• 编写派生类的赋值函数时注意不要忘记对基类的数据成员进行重新赋值，可以通过Base::operator=(other)方式，因为不能直接操作积累的私有数据成员
• 静态链表中指针表示的是下一元素在数组中的位置

常用关键字

const与define的区别

const有数据类型，编译器可以进行类型检查，同时支持调试

nullptr与NULL的区别

C/C++中关于NULL的定义为： 注：nullptr为C++11特性

#ifdef __cplusplus #define NULL 0 #else #define NULL ((void *)0) #endif

C++中是不可以将void*隐形转化为其他类型的指针的，所以定义为0，但是因为0是整数，所以在函数重载时可能会出现问题。

static

• static可以修饰全局变量，局部变量，函数，成员变量，成员函数。
• static修饰函数和全局变量可以限制函数和变量在当前文件内有效
• 静态的数据成员必须初始化，并且在类外初始化，并且初始化的时候是没有static关键字的，为什么这样呢，因为static成员变量在类中是声明而不是定义，而类外的才算定义。
• const static 类型的整形的成员变量才可以在类中初始化

extern

extern可以修饰变量，也可以实现C与C++的混用，参见 "C++项目中的extern "C" {}"

malloc/free与new/delete的区别

• new/delete会调用构造函数和析构函数
• new/delete为运算符，而malloc/free为函数

this

• this是不同对象共享相同成员函数的保证
• this指针的本质是一个函数参数，只是被编译器隐藏了，因此不占用对象的空间
• 静态成员函数不可以使用this指针

inline

• inline具备宏定义代码的效率
• inline会进行类型检查和自动类型转换，因此更加安全
• inline函数可以是成员函数，this对象会被放在合适的地方，因此可以自由的操作类的成员数据
• inline是一种实现的关键字，因此需要放在函数的定义前边
• 定义在类声明中的成员函数将自动的成为内联函数

友元函数

• 友元函数是能够访问类中的私有成员的非成员函数
• 友元是一种定义在类外部的普通函数或类，但它需要在类体内进行说明
• 友元的正确使用能提高程序的运行效率，但同时也破坏了类的封装性和数据的隐藏性，导致程序可维护性变差
• 友元关系不具对称性，不能被继承

流运算符为什么需要声明为友元函数？

如果是重载双目操作符（即为类的成员函数），就只要设置一个参数作为右侧运算量，而左侧运算量就是对象本身，而 >>或<<左侧运算量是cin或cout，而不是对象本身，这与实际使用习惯不符，而且无法链式使用>>和<<, 所以需要定义为友元函数。

智能指针的实现与原理

智能指针是一个类，这个类的构造函数中传入一个普通指针，析构函数中释放传入的指针。智能指针的类都是栈上的对象，所以当函数（或程序）结束时会自动被释放。 基于引用计数的智能指针的实现，需要实现构造，析构，拷贝构造，=操作符重载，重载*-和>操作符。

1. std::auto_ptr，有很多问题。 不支持复制（拷贝构造函数）和赋值（operator =），但复制或赋值的时候不会提示出错。因为不能被复制，所以不能被放入容器中
2. C++11引入的unique_ptr， 也不支持复制和赋值，但比auto_ptr好，直接赋值会编译出错。实在想赋值的话，需要使用：std::move
3. C++11或boost的shared_ptr，基于引用计数的智能指针。可随意赋值，直到内存的引用计数为0的时候这个内存会被释放

树

• 平衡树一定是二叉搜索树
• 堆是一棵完全二叉树
• 堆删除堆顶元素是将最后一个叶子节点放到根节点，然后依次下沉
• 构建堆时是从最后一个非叶子节点开始判断的
• 前序遍历一棵树恰好等价于前序遍历该树对应的二叉树； 后序遍历树恰好等价于中序遍历该树对应的二叉树。
• 前序遍历森林等同于前序遍历该森林对应的二叉树； 后序遍历森林等同于中序遍历该森林对应的二叉树
• 树转化为二叉树： **加线：**所有兄弟节点之间加线; **去线：**保留树中每个结点与它第一个孩子的连
• 森林转化为二叉树：把每棵树转换为二叉树，第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来
• 在树中，结点有几个分叉，度就是几，树中结点数 = 总分叉数 +1
• 一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边
• 度为2的节点数为a，叶子节点为b，则b=a+1
• 完全二叉树的高度h=log(n) + 1
• 完全二叉树的叶子节点个数为（n+1)/2向下取整
• 二叉树的叶子节点n0与度为2的节点内n2的关系为n0=n2+1

图

• 十字链表之于有向图，邻接表之于无向图
• 注意邻接表和邻接矩阵的区别
• 由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。
  1. 选择一个入度为0的顶点并输出之；
  2. 从网中删除此顶点及所有出边。
• 关键路径（临界路径）：在AOE网络中从源点到汇点（结束顶点）的最长路径
• AOV网，即顶点活动网，不会成环
• 如果图中任意两个顶点之间都连通，则称该图为连通图，否则，称该图为非连通图，则其中的极大连通子图称为连通分量，这里所谓的极大是指子图中包含的顶点个数极大
• 在有向图中，若图中任意两个顶点vi和vj都连通，则称为强连通图。
• 有向图的最大强连通子图称为该有向图的强连通分量。强连通图只有一个强连通分量，即本身，非强连通图有多个强连通分量。任何连通图的连通分量只有一个，即为其本身