一些概念与技巧

  1. 两个数的乘积除以它们的最大公约数等于最小公倍数。

  2. 比较两浮点数是否相等:fabs(x) < 0.000001

  3. 浮点型常数的表示方法:1.2L 表示 double 型,1.2f 表示 float 型。默认为 double 型。

  4. 浮点数强制转换成整型会向下取整,但格式化输出会四舍五入。

关于 typedef

1
2
3
4
5
typedef struct LNode
{
ElemType data;
struct LNode *next;
} LNode, *LinkList;

相当于

1
2
3
4
5
6
7
struct LNode
{
ElemType data;
struct LNode *next;
};
typedef struct LNode Lnode;
typedef struct Lnode* LinkList;

变量与类型

枚举类型

  1. 枚举类型相当于同时定义多个常量。

  2. 枚举类型定义的每个常量都是 int 型。

  3. 定义枚举类型时,常有一个 num 记录个数,这个 num 可以用来定义数组,这是个小套路。

寄存器变量

  1. 定义寄存器变量:register 数据类型 变量名

  2. 因寄存器大小的限制,能定义的寄存器变量非常少,且只能定义 int, char指针

  3. 若寄存器的空间不够,寄存器变量会自动转换为普通变量。

共用体

  1. 共用体中的成员变量占用同一片空间,以占用空间最大的成员变量为准分配空间大小。

  2. 作用:可以将每个内存单元中的值输出,在文件部分有用。

  3. 共用体的地址与它的成员的地址是同一个地址。

  4. 共用体变量不能整体赋值,也不能赋初值。

  5. 不能把共用体变量作为函数的参数进行传递,但可以使用指向共用体变量的指针作为参数。

引用

  1. 引用是 const 类型,初始化后不能改变引用的值。它必须在定义时初始化。没有空引用

  2. 引用一般作为函数形参和函数返回值使用。

  3. 由于函数返回引用返回的是一个内存空间的名,所以可以将函数调用作为函数的左值,如:Max(x, y) = z;

  4. 指针也可以有引用,定义方法:

    1
    2
    int *p = NULL;
    int *&q = p; // 注意是先 * 后 &

输出

  1. 特殊格式输出需要添加头文件 iomanip

  2. 输出小数:

    1
    2
    3
    4
    5
    include <iomanip>

    int a = 1;
    cout.setf(ios::fixed);
    cout << setprecision(3) << a;` // output: 1.000

    cout.setf(ios::fixed) 用来设置补零,如果要取消补零:cout.unsetf(ios::fixed)

    设置小数位数:setprecision(n)n 为小数的位数,setprecision(n) 对其后都有效。

  3. 补零输出整数:用 setfill() 设置整数前填充的字符(如 0),对其后都有效;setw() 设置整数宽度,只对其后一个数字有效

    1
    2
    int a = 1;
    cout << setfill('0') << setw(3) << a; output: 0001
  4. coutcerr 的区别:

    • cout:经过流的输出,可以重定向,因此可以用于文件的输出操作。

    • cerr:直接输出到屏幕上。

函数

递归函数

  1. 分为 直接调用间接调用

  2. 计算机是通过栈来实行递归的,函数的递归调用其实就是压栈和出栈的过程。

  3. 使用递归解决问题时,最主要的是怎样把问题变为递归,然后就是确定递归出口(用 if 表达式),不用想的太复杂。

指向函数的指针

  1. 函数名既是函数的名字,又是函数的入口地址。

  2. 定义方法:数据类型 (*指针名)(函数形参列表),数据类型和形参列表规定了指针能指向的函数的类型,如 int (*p)(double x)p 只能指向返回类型是 int、形参只有一个且是 double 型的函数。

  3. 通过函数指针调用函数的方法:p(形参),只是把函数名改成了指针名,因为指针 p 中保存的就是函数的入口地址,即函数名。

  4. 使用函数指针可以达到将函数传参的目的,即实参是一个函数名,形参是函数指针。

  5. 利用指向函数的指针可以实现动态绑定。

main 函数的参数与返回值

C++ 标准规定 main 函数有两种定义方式:

1
2
3
4
int main(void) // void 可省略

int main(int argc, char *argv[]) // argc(arguments count), argv(arguments vector)
// argc 是命令行参数个数,argv 是一个字符指针数组,保存命令行参数。

返回值main 函数是由操作系统调用的,因此,main 函数的返回值也由操作系统接收。main 函数会把最终的执行状态以整数的方式传递给操作系统。返回值如果是 0,就表示程序执行过程一切顺利;任何非 0 的返回值,都表示程序执行时出现了某种问题。

类和对象

类和对象的定义

  1. 默认情况下,在类体中定义的成员函数若符合内敛函数的要求,即使没有写 inline,编译器也会自动将其当做内联函数处理(隐式内敛)。

  2. class Time { int h, m, s; void Settime(……) }; 此时 sizeof(Time)的值为 12,没有把 Settime 函数算进去,因为逻辑上该成员函数属于类 Time,但从存储空间上来说,成员函数不属于包含它的类。

  3. 可以只声明一个类而不定义它:class 类名;,这个声明叫做前向声明,声明一个类后,不能用这个类创建对象,因为编译器并不知道这个类有哪些成员,无法给对象分配存储空间。但可以定义指向该类型的指针引用,或者用于声明以该类型为形参类型或返回值类型的函数(不是定义,同理,是因为编译器无法给函数分配空间)。

  4. 声明而没有定义的类没有类体,叫做不完全类

  5. 当定义一个类时,在类体中用该类定义一个对象,这样的写法是错误的,因为这个类还没有定义完(没有遇到分号),还是个不完全类,不完全类无法定义对象。

关于作用域

  1. 若类的定义放在一个函数中,则这个类只能在这个函数中被使用。

  2. 若在全局作用域内定义了一个类,在局部作用域内定义了一个同名的类,它俩不冲突,因为它们的作用域不同。

  3. C++ 规定,在局部作用域定义的类,成员函数的定义必须放在类体中,不能放到类外。

  4. 一般类是对整个程序服务的,所以很少在局部作用域中定义类。

  5. class 也可以嵌套定义,即在 class 中再定义一个 class,此时被嵌套定义的 class 由于作用域的限制,不能在类外部使用。

  6. 在类里面也可以定义 structenum 等等,也可以用 typedef 为一个数据类型声明一个新名字,但由于作用域的限制,定义的 structenum 等,还有 typedef 声明的新名字都只能在该类中使用。

构造函数与析构函数

构造函数也可以在类外定义,但构造函数初始化列表只能在定义中出现,不能在声明中出现。

初始化列表对数据成员的初始化的次序是数据成员声明的次序,所以一般按成员声明次序编写初始化列表次序。尽可能避免使用成员初始化其他成员。

派生类的构造函数,继承来的数据成员只能在 初始化列表中调用基类构造函数初始化 或者 在函数体中初始化,不能在初始化列表中单独初始化。

默认构造函数

  • 一个类只能有一个默认构造函数。

  • 若自定义了构造函数(不管是否为默认构造函数),系统都不会提供默认构造函数。

  • 派生类的构造函数会默认调用基类的默认构造函数,如果基类没有默认构造函数,需要程序员显式调用其他构造函数。

拷贝构造函数

  • 对象数组的初始化:如果没有初始化,则会调用默认构造函数初始化,如果像平常数组一样,用大括号初始化了,则调用的是复制构造函数初始化。

  • 若没有给组合类和派生类定义拷贝构造函数,系统自动定义的拷贝构造函数会调用基类的 拷贝构造函数,而如果自己定义了拷贝构造函数,则这个拷贝构造函数默认调用的是基类的默认构造函数,若想调用基类的拷贝构造函数,需要显示调用。

隐式类类型转换(转换构造函数)

  1. 构造函数初始化是它的显式功能,如果一个构造函数只有一个形参,那么它还有一个隐式功能,即隐式类类型转换,此时这个构造函数可以叫做转换构造函数。

  2. 转换构造函数的一个形参必须是被转换数据的类型,且一般要加一个 const 限定。

  3. 转换构造函数的使用:类名(指定数据类型的数据对象),作用是将括号里的数据转换为该类类型(是临时转换)。

  4. 在转换构造函数前加关键词 explicit,声明它是显式的,即禁止它的隐式功能。

  5. explicit 只能放在类里面,不能放在类外。

  6. 一般的,如果不进行隐式类类型转换,都要将单形参的构造函数设置为 explicit,避免错误。

  7. 一般不使用隐式类类型转换,若真想转换,可以自己定义一个转换函数进行显式的转换,而不用构造函数隐式转换。

构造函数与析构函数的调用顺序

构造函数:基类的构造函数 –> 成员对象的构造函数 –> 本类的构造函数

析构函数:本类的析构函数 –> 成员对象的析构函数 –> 基类的析构函数

返回对象和返回引用的区别

返回对象:创建临时对象,调用拷贝构造函数将返回值拷贝给临时对象。如果要将返回值赋值给某个对象,调用拷贝构造函数或赋值操作符重载函数将临时对象赋值给赋值号左值。

返回引用:不创建临时对象,直接给返回值起一个别名。如果要将返回值赋值给某个对象,调用拷贝构造函数或赋值操作符重载函数将该对象赋值给赋值号左值。

:如果要返回的对象是在当前函数体里定义的,则只能返回对象,不能返回引用,因为该对象在函数执行完成后会被释放。

继承方式的调整

除了基类的 private 成员,其他成员被继承到派生类后,也可在派生类中对其访问控制属性进行调整。

在派生类中,用作用域限定符和基类成员名对派生类的成员的访问控制属性进行调整。

调整方法:

1
2
public: Base::x;        //将从 Base 类中继承过来的 x 的属性调整为 public。
private: Base::Show; //将从 Base 类中继承过来的 Show 函数 的属性调整为 private。

关于类的静态成员

  1. 如果基类中定义了静态数据成员,无论以何种继承方式派生出派生类,派生类与基类共享该静态数据成员。即所有基类和派生类的所有对象的该数据成员共享同一片内存空间。同样,基类定义了静态成员函数,那么基类和派生类共享该静态成员函数。

  2. 静态成员函数可以重载。

  3. 调用静态成员不用定义对象,用对象调用,可以直接用过作用域限定符调用,因为静态成员是类属性。

  4. 静态成员函数没有隐含的 this 指针。

虚函数实现动态绑定

  1. 当子类公有继承父类后(即子类成为父类的子类型),可以让父类指针或引用指向子类(不能用子类指针或引用指向父类)。

  2. 用父类指针或引用调用父类与子类的同型构函数时,不管父类指针或引用指向的是父类对象还是子类对象,调用的都是父类的函数。

  3. 将父类与子类的同型构函数声明为虚函数(virtual)后,用父类指针或引用调用父类和子类的同型构函数,该指针指向哪个类的对象,就调用哪个类的函数。(即用虚函数实现动态绑定)

  4. 虚函数实现动态绑定的深入理解:TODO

虚基类和虚继承(解决重复继承)

1
2
3
4
5
6
7
class grandfather{
public:
int x;
};
class father :public grandfather {};
class mother :public grandfather {};
class son :public father, public mother{};

此时 son 类中就会有两个 int x;,当调用这个 x 时程序会因出现歧义而编译错误。

1
2
class father :virtual public grandfather{};
class mother :virtual public grandfather{};

grandfather 类定义为 father 类和 mother 类的虚基类(或者可以说 father 类和 mother 类虚继承 grandfather 类),可以避免重复继承。

操作符重载

  1. 操作符重载包括:

    • 单目运算符重载

    • 双目运算符重载

    • 特殊运算符重载

  2. 不能重载的运算符:

    • .(成员选择符)

    • .*(间接成员选择符)

    • ::(域解析符)

    • ?:(条件运算符)

    • sizeof(数据占内存大小)

  3. 对于重载后的操作符,其操作数至少有一个是类、结构、枚举类型或它们的指针。

  4. 操作符重载的一些要求:

    • 只能重载已有的操作符,不可自己创造。

    • 重载后优先级和结合性不变。

    • 单目运算符只能重载成单目,双目运算符只能重载成双目。

    • 遵循已有操作符的语义,不要重载成语义完全不同的运算符。

  5. 运算符重载有两种方式:重载成类的成员函数(有些情况不适用),或重载成全局函数(需声明为友元)。

  6. 单目运算符重载:默认为前置用法,若要重载后置用法,可再定义一个带 int 型参数的重载函数,这样,后置用法将采用这个函数,int 型参数仅仅是为了区分,因为单目运算符只有一个操作数。这个 int 型参数不用定义变量名。

  7. 对于 ==!= 这种具有相反意义的操作符,可以在重载 == 后,利用 == 去重载 !=,这样,当它们的含义需要改变的时候,只需要修改 == 即可,!= 的含义也会随之变化。

  8. 特殊操作符的重载:

    • =:只能在类体中重载,不能重载为全局函数。

    • 转移赋值操作符:TODO

    • [](下标操作符):参数是两个,参数一[参数二]

    • newdelete 运算符:TODO

    • ()(函数调用运算符):可以使对象被当做函数来使用。参数个数随意,没有限制。一般用于只有一个操作的对象(函数对象)。调用方式:对象名(参数列表)。具体作用:TODO

    • ->(类成员访问运算符):第一个操作数是指针,第二个操作数是指针所指向的对象的成员。而重载后,第一个操作数是一个对象,这个对象不但含有一个指针,可以通过该指针调用所指向的对象的成员,而且它还可以含有其他数据和函数成员,这样,这个指针就变成了“智能指针”,它不再是一个只能存储地址的指针,而是一个拥有属性的“指针”。可以利用这些属性干一些事,如计算对一个对象的访问次数。虽然有两个参数,但在类体中定义时不用写参数,即第二个参数不用写,因为第二个参数的类型多种多样,没法写。详细内容:TODO

    • 类型转换操作符:实现隐式类类型转换。TODO

模板

声明为模板:template <class T1, class T2>,要分开写,和函数形参列表一样。

模板分为函数模板和类模板。

  1. 函数模板

    实例化的两种方法:

    • 系统自动实例化

    • show<int>();

  2. 类模板

    每个在类外定义的函数都要写 template <class T>,且在所属类名后加 <T>,如:

    1
    template <class T> void Point<T>::show(){}

    如果类外定义的函数,其参数或返回值类型是该类,也加 <T>

    类模板没有隐式实例化,必须显式实例化,如:point<double> p;,也可以 point<point<double>> p;

    一个普通类可以派生类模板,类模板也可以派生类模板。

  3. 类模板与函数模板的关系:

    一个类,只要其中有一个函数是函数模板,那么这个类就是类模板。

    类模板中的所有函数都是函数模板。

algorithm 中函数的使用

比较规则的指定

  1. 自定义比较函数 Compare,定义方式见下面 sort 快排中的示例。

  2. 使用 functional 头文件提供的 lessgreater 函数指定比较规则,使用方式见下面 priority_queue 中的示例。

这两种方式不仅适用于 sort 函数,还适用于 STL 中数据结构自带的排序函数。

sort 快排

1
2
3
4
5
bool Compare(T a, T b) { return a < b; }
/* 自定义比较函数,sort 会根据该比较函数来排序,比如现在就是从小到大排序(如果是 return a > b; 会从大到小排序)。T 表示任意类型,如果 T 不是基本数据类型而是自定义类型,还要自己制定排序规则 */

sort(start_address, end_address, Compare);
/* 调用 sort 函数进行排序,前两个参数是 数组第一个元素地址 与 数组最后一个元素的后一个元素的地址,第三个参数是 自定义的比较函数的函数名。 */

堆操作

  1. make_heap():建堆

    1
    2
    3
    /* 从 vector 建堆 */
    vector<int> vec{0, 1, 2, 3, 4, 5};
    make_heap(vec.begin(), vec.end()) /* 此处两个参数必须是迭代器,所以需要调用 vec 的函数。可以自定义比较函数或使用 less/greater 作为第三个参数,指定比较规则 */
  2. push_heap():将 vector 重新调整成堆(并没有添加元素的功能)

    1
    2
    3
    4
    5
    vector<int> vec{0, 1, 2, 3, 4, 5};
    vec.push_back(6); /* 先为 vec 添加一个元素 */
    push_heap(vec.begin(), vec.end()) /* 再用 push_heap 函数将 vec 重新调整成堆 */

    /* push_heap 参数与 make_heap 一样,前两个必须是迭代器,而且也可以自定义比较函数来指定比较规则。 */
  3. pop_heap():将堆顶元素与堆底元素交换,并将其他元素重新调整成堆。参数与前两个函数相同。

  4. sort_heap():堆排序。参数与前两个函数相同。

  5. is_heap(): 判断是否为堆。参数与前两个函数相同。

C++ 模板库的使用

STL list

  1. list 进行迭代操作需要定义迭代器:

    1
    list<T>::iterator iter;

    使用迭代器操作链表与使用指针操作数组很相似。

  2. list 的遍历:

    1
    2
    3
    4
    5
    list<T> linklist;
    list<T>::iterator iter;
    for (iter = linklist.begin(); iter != linklist.end(); iter++) {
    cout << *iter; // 迭代器会模拟指针的用法
    }

STL vector

  1. 底层用数组实现,初始大小为 0,加入元素后变为 1,以后每次加入元素时,如果越界,大小翻一倍。

  2. vector 也有迭代器,遍历时可以直接将 vector 对象 当做数组遍历,也可以使用迭代器遍历,但使用迭代器更好。

  3. vector 对象的定义:

    1
    2
    3
    vector<T> vec; /* 定义一个向量 */
    vector<T> vec(10); /* 定义一个大小为 10 并已被初始化的向量 */
    vector<T> vec{1, 2, 3, 4, 5}; /* 定义一个向量,并用大括号内的值初始化 */
  4. vector 中关于大小的函数:

    函数 功能
    size() 返回当前已被使用的空间的大小
    capacity() 返回当前 vector 对象的容量
    max_size() 返回该 vector 对象最大能达到的容量(4611686018427387903)

priority_queue(优先队列)

  1. 创建:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    #include <queue> /* priority_queue 包含在头文件 queue 中 */

    /* 创建一个优先队列,其数据结构为 大顶堆,优先级高的元素优先出队。*/
    priority_queue<T, vector<T>, less<T> > pQ;

    /* 创建一个优先队列,其数据结构为 小顶堆,优先级低的元素优先出队。*/
    priority_queue<T, vector<T>, greater<T> > pQ;

    /* 如果要创建一个数据结构是 大顶堆 的优先队列,让优先级高的元素优先出队,也可以这样写以简化书写 */
    priority_queue<T> pQ;

    /* 如果 T 是自定义类型,需要重载 < 或 > 运算符 */
  2. 常用操作:

    函数 功能
    push(element) 将元素入队(将元素放到堆底)
    pop() 优先级最高的元素出队(堆顶元素出队)
    top() 取优先级最高的元素(取堆顶元素)

TODO

  • 匿名函数

  • 转移构造函数

  • 类之间的聚集关系