C语言/C++/数据结构复习

C语言：

一、常见关键字：

（1）关键字类型：
①数据类型（12个）：
char、double、float、int、long、short
②控制语句（12个）：
for、while、break、continue、if-else、case、switch
③存储类型（4个）
（2）static：定义静态变量/函数（C++中指成员函数等）
（3）const：修饰符：被其修饰的对象或变量不可被修改
（4）volatile：提醒编译器其后面定义的变量随时有可能改变

二、结构体：字节对齐

三、指针和数组

（一）指针：“地址”
（二）作用：通过它可以找到以它为地址的内存单元

C++：

一、面向对象三大特性：

封装继承多态
（一）封装：把一些属性和方法封装到一个类里
（二）继承：子类继承父类的一些属性和方法
菱形继承：两个子类继承同一个父类，且同时有另一个子类同时继承这两个子类，
使用时必须使用虚拟继承。
（三）多态：
（1）作用：
①应用程序不必为每一个派生类编写功能调用，只需要对抽象基类进行处理即可。大大提高程序的可复用性。（继承）
②派生类的功能可以被基类的方法或引用变量所调用，这叫向后兼容，可以提高可扩充性和可维护性。 （多态的真正作用）
（2）实现方法：
静态：重载 模板
动态：虚函数——本质实现

重载：函数名同，形参不同。常用来实现功能相似而数据类型不同的问题
运算符重载的相关规定：
①不能改变优先级；②不能改变结合型；③默认参数不能和重载的运算符一起使用；
④不能改变个数；⑤不能创建新的运算符；⑥运算符原含义保持不变。
模板：
①函数模板：一个对函数功能框架的描述，将根据传递的实参决定其功能，是对这个模块的定义
②模板函数：对这个函数进行实例化
虚函数：由virtual修饰的成员函数。求同存异。实现多态性。通过指向派生类的基类指针或引用，访问派生类中的同名覆盖成员函数。
纯虚函数：只有定义没有实现。包含其的类不能定义其对象。

二、STL容器

（1）vector：是一个能够存放任意类型的动态数组，能够增加和压缩数据。
#include vector<>；
（2）list：是一种序列式容器。功能与双向链表相似，具有链表的主要优点。
每个节点有三个域：前驱指针域、数据域、后继指针域。
（3）vector与list的区别：
①若需要高效随即存取，而不在乎插入和删除的效率，用vector；反之list。
②vector底层实现是数组，list是双向链表。
③vector支持随机访问，list不支持。
④vector在中间节点进行插入操作时会导致内存拷贝，list不会。
⑤vector一次性分配好内存，不够用则进行2倍扩容。list每次插入都会进行内存申请
⑥vector随机访问性能好，插入删除差；list相反。
⑦vector拥有一段连序的存储空间，list没有。

（4）stack：适配器，被设计用来操作先进后出结构的情景，元素的插入和删除只能在容器尾部实现（栈）
（5）queue：提供先进先出的适配器（队列）
（6）区别：……↑
（7）map：关联容器，提供一对一的数据处理能力，即内部存储有两个部分：key（关键字，固定键值不会改变）和value（记录该关键字的状态）
（8）set：包含已排序对象的关联容器，每个键只能对应一个元素
（9）unordered_map：内部采用hash表结构，拥有快速检索功能。
关联性：key→value
无序性：使用hash存储，内部无序
map：每个值对应一个键值
键唯一性：不存在两个元素的键一样
动态内存管理
（10）map与set的区别：

（11）map和unordered_map的区别：
内部原理：
map内部为RBTree，有自动排序功能，所以内部元素都是有序的。根据树的中序遍历可以将键值按大小遍历出来。
unordered_map内部为hash表，查找时间为O(1)，内部元素是无序的。

数据结构

一、各数据结构的优缺点和特性

（1）数组：
优：知道坐标后可以快速存取
缺：查删慢，大小固定
（2）有序数组：
优：比无需查找快
缺：存取慢
（3）栈：
优：后进先出
缺：存取慢
（4）队列：
优：先进先出
缺：存取慢
（5）链表：
优：增删快
缺：查找慢
（6）二叉树：
优：增删查都快（如果树平衡的话）
缺：删除算法复杂
（7）红黑树：
优：增删查快，树总是平衡
缺：算法复杂
（8）234树：
优：增删查快，树总是平衡。类似的树对磁盘存储有用
缺：算法复杂
（9）Hash：
优：若已知关键字则存取极快，插入快
缺：删慢，key未知则非常慢，对空间利用不充分
（10）堆：
优：增删快，对最大数据项的存取很快
缺：对其他项很慢
（11）图：（不做了解）
优：对现实世界建模
缺：有些算法慢且复杂

二、基础排序算法

（"1"为稳定，"0"为不稳定。空间中的"1"表示空间复杂度）