一、数据结构及算法（快排、归并、堆排等）
十大排序算法 数据结构(c/c++版)-严蔚敏 数据结构与算法(思维导图）
E:\学习\4.数据结构(C语言版)].严蔚敏_吴伟民.扫描版.pdf
数据结构分为8类有:数组、栈、队列、链表、树、散列表、堆、图
1.快速排序（Quick Sort）
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
算法描述
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
从数列中挑出一个元素，称为 “基准”（pivot）；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
2.归并排序
是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
3.希尔排序缩小增量排序
希尔排序是把记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止
二、C/C++内存管理
c/c++内存分布
【说明】
- 栈又叫堆栈，非静态局部变量/函数参数/返回值等等，栈是向下增长的;栈是由操作系统自动管理的。
- 内存映射段是高效的I/O映射方式，用于装载一个共享的动态内存库。用户可使用系统接口创建共享共享内存，做进程间通信。（Linux课程如果没学到这块，现在只需要了解一下）
- 堆用于程序运行时动态内存分配，堆是可以上增长的；堆是由程序员管理，先入后出。
- 数据段–存储全局数据和静态数据。
- 代码段–可执行的代码/只读常量。
2.1 栈&堆
栈区：
栈区开辟的数据由编译器自动释放
堆区：
由程序员分配释放,若程序员不释放,程序结束时由操作系统回收
主要的区别由以下几点：
1、管理方式不同；
2、空间大小不同；
3、能否产生碎片不同；
4、生长方向不同；
5、分配方式不同；
6、分配效率不同；
管理方式：对于栈来讲，是由编译器自动管理，无需我们手工控制；对于堆来说，释放工作由程序员控制，容易产生memory leak。
空间大小：一般来讲在32位系统下，堆内存可以达到4G的空间，从这个角度来看堆内存几乎是没有什么限制的。但是对于栈来讲，一般都是有一定的空间大小的，例如，在VC6下面，默认的栈空间大小是1M（好像是，记不清楚了）。当然，我们可以修改：
碎片问题：对于堆来讲，频繁的new/delete势必会造成内存空间的不连续，从而造成大量的碎片，使程序效率降低。对于栈来讲，则不会存在这个问题，因为栈是先进后出的队列，他们是如此的一一对应，以至于永远都不可能有一个内存块从栈中间弹出，在他弹出之前，在他上面的后进的栈内容已经被弹出，详细的可以参考数据结构，这里我们就不再一一讨论了。
生长方向：对于堆来讲，生长方向是向上的，也就是向着内存地址增加的方向；对于栈来讲，它的生长方向是向下的，是向着内存地址减小的方向增长。
分配方式：堆都是动态分配的，没有静态分配的堆。栈有2种分配方式：静态分配和动态分配。静态分配是编译器完成的，比如局部变量的分配。动态分配由alloca函数进行分配，但是栈的动态分配和堆是不同的，他的动态分配是由编译器进行释放，无需我们手工实现。
分配效率：栈是机器系统提供的数据结构，计算机会在底层对栈提供支持：分配专门的寄存器存放栈的地址，压栈出栈都有专门的指令执行，这就决定了栈的效率比较高。堆则是C/C++函数库提供的，它的机制是很复杂的，例如为了分配一块内存，库函数会按照一定的算法（具体的算法可以参考数据结构/操作系统）在堆内存中搜索可用的足够大小的空间，如果没有足够大小的空间（可能是由于内存碎片太多），就有可能调用系统功能去增加程序数据段的内存空间，这样就有机会分到足够大小的内存，然后进行返回。显然，堆的效率比栈要低得多。
从这里我们可以看到，堆和栈相比，由于大量new/delete的使用，容易造成大量的内存碎片；由于没有专门的系统支持，效率很低；由于可能引发用户态和核心态的切换，内存的申请，代价变得更加昂贵。所以栈在程序中是应用最广泛的，就算是函数的调用也利用栈去完成，函数调用过程中的参数，返回地址，EBP和局部变量都采用栈的方式存放。所以，我们推荐大家尽量用栈，而不是用堆。
无论是堆还是栈，都要防止越界现象的发生（除非你是故意使其越界），因为越界的结果要么是程序崩溃，要么是摧毁程序的堆、栈结构，产生以想不到的结果
2.2 malloc/calloc/realloc区别总结
malloc底层原理实现
相同点：
1.都是从堆上申请空间
2.都需要对返回值判空
3.都需要用户free释放
4.返回值类型相同（void*）
5.都需要类型转化
6.底层实现上是一样的，都需要开辟多余的空间，用来维护申请的空间
不同点：
1.函数名字不同和参数类型不同。
2.calloc会对申请空间初始化，并且初始化为0，而其他两个不会。
3.malloc申请的空间必须使用memset初始化
4.realloc是对已经存在的空间进行调整，当第一个参数传入NULL的时候和malloc一样
调整分为两种情况：
a:调整的空间比原有空间大：
1.大了一点：多出来的空间小于下面空闲的空间；
做法：
1.直接延伸申请空间
2.返回原空间首地址**
2.大了很多：多出来的空间，大于下面空闲空间
做法：
1.重新开辟新空间
2.将旧空间的内容拷贝到新空间中
3.释放旧空间
4.返回新空间的首地址
b.调整的空间比原有空间小：
做法：
1.将原空间缩小
2 .返回旧空间首地址
2.3 malloc/free和new/delete的区别
共同点是：都是从堆上申请空间，并且需要用户手动释放。
不同的地方是：
- malloc和free是函数，new和delete是运算符
- malloc申请的空间不会初始化，new可以初始化
- malloc申请空间时，需要手动计算空间大小并传递，new只需在其后跟上空间的类型即可
- malloc的返回值为void*, 在使用时必须强转，new不需要，因为new后跟的是空间的类型
- malloc申请空间失败时，返回的是NULL，因此使用时必须判空，new不需要，但是new需要捕获异常
- 申请自定义类型对象时，malloc/free只会开辟空间，不会调用构造函数与析构函数，而new在申请空间后会调用构造函数完成对象的初始化，delete在释放空间前会调用析构函数完成空间中资源的清理
new既是关键字，也可以作为运算符，作为运算符时，可以作为 operator new函数重载。
delete会调用对象的析构函数,和new对应free只会释放内存，new调用构造函数。malloc与free是C++/C语言的标准库函数，new/delete是C++的运算符。它们都可用于申请动态内存和释放内存。
2.4 内存泄漏
1.内存泄漏：内存泄漏指因为疏忽或错误造成程序未能释放已经不再使用的内存的情况。内存泄漏并不是指内存在物理上的消失，而是应用程序分配某段内存后，因为设计错误，失去了对该段内存的控制，因而 造成了内存的浪费
危害：长期运行的程序出现内存泄漏，影响很大，如操作系统、后台服务等等，出现内存泄漏会导致响应越来越慢，最终卡死。
2.内存泄漏的分类
堆内存泄露（Heap leak）：
堆内存指的是程序执行中依据须要分配通过malloc / calloc / realloc / new等从堆中分配的一块内存，用完后必须通过调用相应的 free或者delete 删掉。假设程序的设计错误导致这部分内存没有被释放，那么以后这部分空间将无法再被使用，就会产生Heap Leak
系统资源泄露：
指程序使用系统分配的资源，比方套接字、文件描述符、管道等没有使用对应的函数释放掉，导致系统资源的浪费，严重可导致系统效能减少，系统执行不稳定
3 如何避免内存泄漏
事前预防——智能指针
事后查错——泄露检测工具
2.5 malloc内存分配原理
malloc基本的实现原理就是维护一个内存空闲链表，当申请内存空间时，搜索内存空闲链表，找到适配的空闲内存空间，然后将空间分割成两个内存块，一个变成分配块，一个变成新的空闲块。如果没有搜索到，那么就会用sbrk()才推进brk指针来申请内存空间。
搜索空闲块最常见的算法有：首次适配，下一次适配，最佳适配。
首次适配：第一次找到足够大的内存块就分配，这种方法会产生很多的内存碎片。
下一次适配：也就是说等第二次找到足够大的内存块就分配，这样会产生比较少的内存碎片。
最佳适配：对堆进行彻底的搜索，从头开始，遍历所有块，使用数据区大小大于size且差值最小的块作为此次分配的块。
2.6 如何一次在堆上申请4G的内存？
// 将程序编译成x64的进程，运行下面的程序试试？
#include
using namespace std;
int main()
{
void* p = new char[0xfffffffful];
cout << “new:” << p << endl;
return 0;
}
三、智能指针
C++11中引入了智能指针的概念，方便管理堆内存。动态的分配内存。
智能指针的作用是防止忘记调用delete释放内存和程序异常的进入catch块忘记释放内存。
智能指针是一个类，这个类的构造函数中传入一个普通指针，析构函数中释放传入的指针。智能指针的类都是栈上的对象，所以当函数（或程序）结束时会自动被释放
3.1 RAII思想
定义一个类来封装资源的分配与释放，构造函数中完成资源的分配及初始化；
析构函数中完成资源的清理，可以保证资源的正确初始化和释放
如果对象是用声明的方式在栈上创建局部对象，那么RAII机制就会正常工作，当离开作用域对象会自动销毁而调用析构函数释放资源。
3.2 最常用的智能指针：
1）std::auto_ptr，有很多问题。 不支持复制（拷贝构造函数）和赋值（operator =），但复制或赋值的时候不会提示出错。因为不能被复制，所以不能被放入容器中。
2) C++11引入的unique_ptr， 也不支持复制和赋值，但比auto_ptr好，直接赋值会编译出错。实在想赋值的话，需要使用：std::move。
3) C++11或boost的shared_ptr，是通过引用计数的方式来实现多个shared_ptr对象之间共享资源。可随意赋值，直到内存的引用计数为0的时候这个内存会被释放。多个指针可以同时指向一个对象，当最后一个shared_ptr离开作用域时，内存才会自动释放。
shared_ptr循环引用导致内存泄露。weak_ptr专门用于辅助shared_ptr来解决引用计数的问题。当shared_ptr内部要监视其他的shared_ptr对象时，类型就采用weak_ptr。这种weak_ptr在指向被监视的shared_ptr后，并不会使被监视的引用计数增加，且当被监视的对象析构后就自动失效。
4）C++11或boost的weak_ptr，弱引用。 引用计数有一个问题就是互相引用形成环，这样两个指针指向的内存都无法释放。需要手动打破循环引用或使用weak_ptr。顾名思义，weak_ptr是一个弱引用，只引用，不计数。如果一块内存被shared_ptr和weak_ptr同时引用，当所有shared_ptr析构了之后，不管还有没有weak_ptr引用该内存，内存也会被释放。所以weak_ptr不保证它指向的内存一定是有效的，在使用之前需要检查weak_ptr是否为空指针。
3.3 智能指针的实现
1.构造函数中计数初始化为1；2.拷贝构造函数中计数值加1；3.赋值运算符中，左边的对象引用计数减一，右边的对象引用计数加一；4.析构函数中引用计数减一；5.在赋值运算符和析构函数中，如果减一后为0，则调用delete释放对象。
智能指针是线程安全的吗？
对于unique_ptr，由于只是在当前代码块范围内有效。所以不涉及线程安全的问题。
对于shared_ptr，多个对象要同时共用一个引用计数变量，所以会存在线程安全的问题，但是标准库实现的时候考虑到了这一点，使用了基于原子操作（CAS）的方式来保证shared_ptr能够高效，原子的操作引用计数。
四、STL-Vector&List
C++ STL标准库（内含大量示例） 学了C++中STL STL用法超详细
1.迭代器（Iterator）是指针（pointer）的泛化
2.Vector ：
vector可理解为变长数组，基于倍增思想。当以已申请vector长度为m时，若实际长度n=m,则申请长度为2m的数组，将内容转移至新地址上，并释放旧空间；删除元素时，若n<=m/4,则释放一半空间。vector容器能像数组一样随机访问第i个数a[i]，但不支持随机插入。一种随机访问的数组类型，提供了对数组元素进行快速随机访问以及在序列尾部进行快速的插入和删除操作的功能。可以再需要的时候修改其自身的大小。
3.List：
List类表示可通过索引访问的对象的强类型列表，提供用于对列表进行搜索、排序和操作的方法。一种不支持随机访问（支持双向）的数组类型，插入和删除所花费的时间是固定的，与位置无关
list和vector有什么区别？
vector和数组类似，它拥有一段连续的内存空间，并且起始地址不变，因此它能非常好的支持随机存取（即使用[]操作符访问其中的元素），但由于它的内存空间是连续的，所以在中间进行插入和删除会造成内存块的拷贝（复杂度是O(n)），另外，当该数组后的内存空间不够时，需要重新申请一块足够大的内存并进行内存的拷贝。这些都大大影响了vector的效率。
list是由数据结构中的双向链表实现的，因此它的内存空间可以是不连续的。因此只能通过指针来进行数据的访问，这个特点使得它的随机存取变的非常没有效率，需要遍历中间的元素，搜索复杂度O(n)，因此它没有提供[]操作符的重载。但由于链表的特点，它可以以很好的效率支持任意地方的删除和插入。
unordered_map:
unordered_map内部实现了一个哈希表.
4.map
提供的是一种键值对容器，里面的数据都是成对出现的
Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据 处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。这里说下map内部数据的组织，map内部自建一颗红黑树(一 种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的。
重温数据结构：深入理解红黑树
五、设计模式
23 种设计模式详解 十种常用的设计模式
5.1、单例模式（懒汉式、饿汉式）
一个类仅有一个实例，减少内存开销，尤其是类频繁的创建与销毁。
单例模式的要点有三个：一是某个类只能有一个实例；二是它必须自行创建这个实例；三是它必须自行向整个系统提供这个实例
- 饿汉式(线程不安全,不支持多线程)
- 懒汉式(线程安全,支持多线程)：双重锁机制实现线程安全。第一次调用才初始化，避免内存浪费。
5.2、工厂模式
spring IOC就是使用了工厂模式，对象的创建都交给一个工厂去创建。
5.3、代理模式
代理对象可以在客户端和目标对象之间起到中介作用
一）静态代理
实现方式：
a） 为真实类和代理类提供的公共接口或抽象类。（租房）
b） 真实类，具体实现逻辑，实现或继承a。（房主向外租房）
c） 代理类，实现或继承a，有对b的引用，调用真实类的具体实现。（中介）
d） 客户端，调用代理类实现对真实类的调用。（租客租房）
二）动态代理
实现方式：
a） 公共的接口（必须是接口，因为Proxy类的newproxyinstance方法的第二参数必须是个接口类型的Class）
b） 多个真实类，具体实现的业务逻辑。
c） 代理类，实现InvocationHandler接口，提供Object成员变量，和Set方法，便于客户端切换。
d） 客户端，获得代理类的实例，为object实例赋值，调用Proxy.newproxyinstance方法在程序运行时生成继承公共接口的实例，调用相应方法，此时方法的执行由代理类实现的Invoke方法接管。
jdk动态代理使用的局限性：
通过反射类Proxy和InvocationHandler回调接口实现的jdk动态代理，要求委托类必须实现一个接口，但事实上并不是所有类都有接口，对于没有实现接口的类，便无法使用该方方式实现动态代理。
5.4、迭代器模式
提供一种方法访问一个容器对象中各个元素，而又不暴露该对象的内部细节。其别名为游标。对于对象集合的遍历，还是比较麻烦的，对于数组或者有序列表，我们尚可以通过游标来取得。
单例模式和静态类的区别
1.单例模式指的是在应用***整个生命周期内只能存在一个实例。***单例模式是一种被广泛使用的设计模式。他有很多好处，能够避免实例对象的重复创建，减少创建实例的系统开销，节省内存。
静态类就是一个类里面都是静态方法和静态field，构造器被private修饰，因此不能被实例化。
2.单例模式的灵活性更高，方法可以被override，因为静态类都是静态方法，所以不能被override；
3.静态类比单例类更快，因为静态的绑定是在编译期进行的。***如果你要维护状态信息，或者访问资源时，应该选用单例模式。
六、extern
extern置于变量或函数前，用于标示变量或函数的定义在别的文件中，提示编译器遇到此变量和函数时在其他模块中寻找其定义。它只要有两个作用：
当它与“C”一起连用的时候，如：extern “C” void fun(int a,int b);则告诉编译器在编译fun这个函数时候按着C的规矩去翻译，而不是C++的（这与C++的重载有关，C++语言支持函数重载，C语言不支持函数重载，函数被C++编译器编译后在库中的名字与C语言的不同）
当extern不与“C”在一起修饰变量或函数时，如：extern int g_Int；它的作用就是声明函数或全局变量的作用范围的关键字，其声明的函数和变量可以在本模块或其他模块中使用。记住它是一个声明不是定义!也就是说B模块(编译单元)要是引用模块(编译单元)A中定义的全局变量或函数时，它只要包含A模块的头文件即可,在编译阶段，模块B虽然找不到该函数或变量，但它不会报错，它会在连接时从模块A生成的目标代码中找到此函数。
七、static
修饰局部变量
static修饰局部变量时，存储在静态区的数据生命周期与程序相同，在main函数之前初始化，在程序退出时销毁。
修饰全局变量
被static修饰的全局变量只能被该包含该定义的文件访问（即改变了作用域）。
修饰函数
static修饰函数使得函数只能在包含该函数定义的文件中被调用。对于静态函数，声明和定义需要放在同一个文件夹中。
修饰成员变量
用static修饰类的数据成员使其成为类的全局变量，会被类的所有对象共享，包括派生类的对象，所有的对象都只维持同一个实例。 可以通过对象名直接访问公有静态成员变量；
修饰成员函数
用static修饰成员函数，使这个类只存在这一份函数，所有对象共享该函数，不含this指针，因而只能访问类的static成员变量。可以通过类名直接调用公有静态成员函数。
八、volatile
用来修饰变量的，表明某个变量的值可能会随时被外部改变，因此这些变量的存取不能被缓存到寄存器，每次使用需要重新读取。
这个关键字声明的变量，编译器对访问该变量的代码就不再进行优化，从而可以提供对特殊地址的稳定访问。
当要求使用 volatile 声明的变量的值的时候，系统总是重新从它所在的内存读取数据，即使它前面的指令刚刚从该处读取过数据。而且读取的数据立刻被保存。
九、const VS #define
const对象只能访问const成员函数,而非const对象可以访问任意的成员函数,包括const成员函数.即对于class A，有const A a；那么a只能访问A的const成员函数。而对于：A b；b可以访问任何成员函数。
const和#define区别
（1）const和#define都可以定义常量，但是const用途更广。
（2）const 常量有数据类型，而宏常量没有数据类型。编译器可以对前者进行类型安全检查。而对后者只进行字符替换，没有类型安全检查，并且在字符替换可能会产生意料不到的错误。
（3） 有些集成化的调试工具可以对const 常量进行调试，但是不能对宏常量进行调试。
十、指针vs引用 数组VS 链表
10.1 指针vs引用
相同点：
1). 都是地址的概念；
2). 都是“指向”一块内存。指针指向一块内存，它的内容是所指内存的地址；而引用则是某块内存的别名；
3). 引用在内部实现其实是借助指针来实现的，一些场合下引用可以替代指针，比如作为函数形参。
不同点：
1). 指针是一个实体，而引用(看起来，这点很重要)仅是个别名；
2). 引用只能在定义时被初始化一次，之后不可变；指针可变；引用“从一而终”，指针可以“见异思迁”；
3). 引用不能为空，指针可以为空；
4). “sizeof 引用”得到的是所指向的变量(对象)的大小，而“sizeof 指针”得到的是指针本身的大小；
5). 指针和引用的自增(++)运算意义不一样；
6). 引用是类型安全的，而指针不是 (引用比指针多了类型检查)
7). 引用具有更好的可读性和实用性。
10.2 数组VS 链表
数组的特点
1.在内存中，数组是一块连续的区域；
2.数组需要预留空间，在使用前要先申请占内存的大小，可能会浪费内存空间；
3.插入数据和删除数据效率低，插入数据时，这个位置后面的数据在内存中都要向后移。删除数据时，这个数据后面的数据都要往前移动；
4.查找速度快；
5.随机访问性强。
链表的特点
1.在内存中可以存在任何地方，不要求连续。
2.每一个数据都保存了下一个数据的内存地址，通过这个地址找到下一个数据。
3.增加数据和删除数据很容易。
4.查找数据时效率低，因为不具有随机访问性，所以访问某个位置的数据都要从第一个数据开始访问，然后根据第一个数据保存的下一个数据的地址找到第二个数据，以此类推。
5.不指定大小，扩展方便。链表大小不用定义，数据随意增删。
十一、封装、继承、多态
11.1封装
封装是实现面向对象程序设计的第一步，封装就是将数据或函数等集合在一个个的单元中（我们称之为类）。
封装的意义在于保护或者防止代码（数据）被我们无意中破坏。
从封装的角度看，public， private 和 protected 属性的特点如下。
不管那种属性，内类都是可以访问的
public 是一种暴露的手段，比如暴露接口，类的对象可以访问
private 是一种隐藏的手段，类的对象不能访问
protected 成员：
和 public 一样可以被子类继承
和 private 一样不能在类外被直接调用
11.2继承
继承主要实现重用代码，节省开发时间。
子类可以继承父类的一些东西。
a.**公有继承(public)**公有继承的特点是基类的公有成员和保护成员作为派生类的成员时，它们都保持原有的状态（基类的私有成员仍然是私有的，不能被这个派生类的子类所访问）。
b.**私有继承(private)**私有继承的特点是基类的公有成员和保护成员都作为派生类的私有成员（并且不能被这个派生类的子类所访问）。
c.**保护继承(protected)**保护继承的特点是基类的所有公有成员和保护成员都成为派生类的保护成员（并且只能被它的派生类成员函数或友元访问，基类的私有成员仍然是私有的）。
这里特别提一下虚继承。虚继承是解决C++多重继承问题（其一，浪费存储空间；第二，存在二义性问题）的一种手段。比如菱形继承，典型的应用就是 iostream, 其继承于 istream 和 ostream，而 istream 和 ostream 又继承于 ios。
继承的实现方式？
继承概念的实现方式有三类：实现继承、接口继承和可视继承。
- 实现继承是指使用基类的属性和方法而无需额外编码的能力；
- 接口继承是指仅使用属性和方法的名称、但是子类必须提供实现的能力；
- 可视继承是指子窗体（类）使用基窗体（类）的外观和实现代码的能力。
11.3多态 虚函数
什么是多态？
允许将子类类型的指针赋值给父类类型的指针。
多态性可以简单地概括为“一个接口，多种方法”，程序在运行时才决定调用的函数 。C++多态性主要是通过虚函数实现的，虚函数允许子类重写override(注意和overload的区别，overload是重载，是允许同名函数的表现，这些函数参数列表/类型不同）多态与非多态的实质区别就是函数地址是早绑定还是晚绑定。
11.4 重载VS覆盖
重载：是编写函数名相同，参数列表不同的函数。重载和多态无关！
覆盖也叫重写，重写的函数必须有一致的参数表和返回值。
重写：和多态真正相关。当子类重新定义了父类的虚函数后，父类指针根据赋给它的不同的子类指针，动态的调用属于子类的该函数，这样的函数调用在编译期间是无法确定的（调用的子类的虚函数的地址无法给出）。因此，这样的函数地址是在运行期绑定的（晚绑定）。
什么情况下用重载，什么情况下用覆盖？
派生类重写基类的虚函数用覆盖。实现同一功能有不同参数列表的函数用重载。他们是怎么实现的？重载是在编译阶段就知道要调用的函数地址，属于早绑定，是静态的；覆盖要在运行时绑定函数地址，属于晚绑定，是动态的。
a、编译时多态性：通过重载函数实现 （静态多态）
b、 运行时多态性：通过虚函数实现（动态多态）
（纯虚函数是不被实现的）纯虚函数目的在于，使派生类仅仅只是继承函数的接口。
纯虚函数用来规范派生类的行为，即接口。
纯虚函数是为了实现一个接口，起到一个规范的作用，规范继承这个类的程序员必须实现这个函数。
十二、虚函数表：
虚函数实现机制：
可以定义一个基类的指针, 其指向一个继承类, 当通过基类的指针去调用函数时, 可以在运行时决定该调用基类的函数还是继承类的函数.
虚函数表是针对类的还是针对对象的？同一个类的两个对象的虚函数表是怎么维护的？
编译器为每一个类维护一个虚函数表（本质是一个函数指针数组，数组里面存放了一系列函数地址 ），每个对象的首地址保存着该虚函数表的指针，同一个类的不同对象实际上指向同一张虚函数表。调用形式：*(this指针+调整量)虚函数在vftable内的偏移
在类内部添加一个虚拟函数表指针，该指针指向一个虚拟函数表，该虚拟函数表包含了所有的虚拟函数的入口地址，每个类的虚拟函数表都不一样，在运行阶段可以循此脉络找到自己的函数入口。纯虚函数相当于占位符， 先在虚函数表中占一个位置由派生类实现后再把真正的函数指针填进去。除此之外和普通的虚函数没什么区别。
多态是由虚函数实现的，而虚函数主要是通过虚函数表（V-Table）来实现的。
如果一个类中包含虚函数（virtual修饰的函数），那么这个类就会包含一张虚函数表，虚函数表存储的每一项是一个虚函数的地址。如下图：
这个类的每一个对象都会包含一个虚指针（虚指针存在于对象实例地址的最前面，保证虚函数表有最高的性能），这个虚指针指向虚函数表。
注：对象不包含虚函数表，只有虚指针，类才包含虚函数表，派生类会生成一个兼容基类的虚函数表。
十三、深拷贝&浅拷贝
最根本的区别在于是否真正获取了一个对象的复制实体，而不是引用。
浅拷贝：
只是拷贝了基本类型的数据，而引用类型数据，复制后也是会发生引用，我们把这种拷贝叫做“（浅复制）浅拷贝”，换句话说，浅复制仅仅是指向被复制的内存地址，如果原地址中对象被改变了，那么浅复制出来的对象也会相应改变。
深拷贝：
在计算机中开辟了一块新的内存地址用于存放复制的对象。
1). 没有任何构造函数时，编译器会自动生成默认构造函数，也就是无参构造函数；当类没有拷贝构造函数时，会生成默认拷贝构造函数。
2). 深拷贝是指拷贝后对象的逻辑状态相同，而浅拷贝是指拷贝后对象的物理状态相同；默认拷贝构造函数属于浅拷贝。
3). 当系统中有成员指代了系统中的资源时，需要深拷贝。比如指向了动态内存空间，打开了外存中的文件或者使用了系统中的网络接口等。如果不进行深拷贝，比如动态内存空间，可能会出现多次被释放的问题。是否需要定义拷贝构造函数的原则是，是类是否有成员调用了系统资源，如果定义拷贝构造函数，一定是定义深拷贝，否则没有意义。
析构函数
对于栈对象或者全局对象，调用顺序与构造函数的调用顺序刚好相反，也即后构造的先析构。对于堆对象，析构顺序与delete的顺序相关。
13.1虚析构函数的作用
基类采用虚析构函数可以防止内存泄漏。比如下面的代码中，如果基类 A 中不是虚析构函数，则 B 的析构函数不会被调用，因此会造成内存泄漏。
但并不是要把所有类的析构函数都写成虚函数。因为当类里面有虚函数的时候，编译器会给类添加一个虚函数表，里面来存放虚函数指针，这样就会增加类的存储空间。所以，只有当一个类被用来作为基类的时候，才把析构函数写成虚函数。
13.2拷贝构造函数
对于 class A，它的拷贝构造函数如下：
A::A(const A &a){}
- 为什么必须是当前类的引用呢？
循环调用。如果拷贝构造函数的参数不是当前类的引用，而是当前类的对象，那么在调用拷贝构造函数时，会将另外一个对象直接传递给形参，这本身就是一次拷贝，会再次调用拷贝构造函数，然后又将一个对象直接传递给了形参，将继续调用拷贝构造函数……这个过程会一直持续下去，没有尽头，陷入死循环。
只有当参数是当前类的引用时，才不会导致再次调用拷贝构造函数，这不仅是逻辑上的要求，也是 C++ 语法的要求。
- 为什么是 const 引用呢？
拷贝构造函数的目的是用其它对象的数据来初始化当前对象，并没有期望更改其它对象的数据，添加 const 限制后，这个含义更加明确了。
另外一个原因是，添加 const 限制后，可以将 const 对象和非 const 对象传递给形参了，因为非 const 类型可以转换为 const 类型。如果没有 const 限制，就不能将 const 对象传递给形参，因为 const 类型不能转换为非 const 类型，这就意味着，不能使用 const 对象来初始化当前对象了。
十四、强制类型转换
static_cast <T*> (content) 静态转换.在编译期间处理，可以实现C++中内置基本数据类型之间的相互转换。如果涉及到类的话，static_cast只能在有相互联系的类型中进行相互转换,不一定包含虚函数。
a. 用于基本类型间的转换
b. 不能用于基本类型指针间的转换
c. 用于有继承关系类对象间的转换和类指针间的转换
dynamic_cast<T*>(content) 动态类型转换;也是向下安全转型;是在运行的时候执行;基类中一定要有虚函数，否则编译不通过。在类层次间进行上行转换时（如派生类指针转为基类指针），dynamic_cast和static_cast的效果是一样的。在进行下行转换时（如基类指针转为派生类指针），dynamic_cast具有类型检查的功能，比static_cast更安全。
a. 用于有继承关系的类指针间的转换
b. 用于有交叉关系的类指针间的转换
c. 具有类型检查的功能
d. 需要虚函数的支持
const_cast<T*>(content) 去常转换;编译时执行;
a. 用于指针间的类型转换
b. 用于整数和指针间的类型转换
reinterpret_cast<T*>(content) 重解释类型转换;
a. 用于去掉变量的const属性
b. 转换的目标类型必须是指针或者引用
在C++中，普通类型可以通过类型转换构造函数转换为类类型，那么类可以转换为普通类型吗？答案是肯定的。但是在工程应用中一般不用类型转换函数，因为无法抑制隐式的调用类型转换函数（类型转换构造函数可以通过explicit来抑制其被隐式的调用），而隐式调用经常是bug的来源。实际工程中替代的方式是定义一个普通函数，通过显式的调用来达到类型转换的目的。
十五、c语言vs c++
C语言是结构化的编程语言，它是面向过程的，而C++是面向对象的。 C++是C的超集;
封装：将数据和函数等集合在一个单元中（即类）。被封装的类通常称为抽象数据类型。封装的意义在于保护或者防止代码（数据）被我们无意中破坏。
继承：继承主要实现重用代码，节省开发时间。它可以使用现有类的所有功能，并在无需重新编写原来的类的情况下对这些功能进行扩展。
多态：同一操作作用于不同的对象，可以有不同的解释，产生不同的执行结果。在运行时，可以通过指向派生类的基类指针，来调用实现派生类中的方法。有编译时多态和运行时多态。
十六、左值引用和右值引用
左值引用就是我们通常所说的引用，如下所示。左值引用通常可以看作是变量的别名。
右值引用是 C++11 新增的特性，右值引用用来绑定到右值，绑定到右值以后本来会被销毁的右值的生存期会延长至与绑定到它的右值引用的生存期。
在汇编层面右值引用做的事情和常引用是相同的，即产生临时量来存储常量。但是，唯一 一点的区别是，右值引用可以进行读写操作，而常引用只能进行读操作。
十七、C++ Socket编程步骤
三种：流式套接字（SOCK_STREAM），数据报套接字（SOCK_DGRAM），原始套接字（SOCK_RAW）；基于TCP的socket编程是采用的流式套接字、
服务器端编程的步骤：
1：加载套接字库，创建套接字(WSAStartup()/socket())；
2：绑定套接字到一个IP地址和一个端口上(bind())；
3：将套接字设置为监听模式等待连接请求(listen())；
4：请求到来后，接受连接请求，返回一个新的对应于此次连接的套接(accept())；
5：用返回的套接字和客户端进行通信(send()/recv())；
6：返回，等待另一连接请求；
7：关闭套接字，关闭加载的套接字库(closesocket()/WSACleanup())。
客户端编程的步骤：
1：加载套接字库，创建套接字(WSAStartup()/socket())；
2：向服务器发出连接请求(connect())；
3：和服务器端进行通信(send()/recv())；
4：关闭套接字，关闭加载的套接字库(closesocket()/WSACleanup())。
十八、程序编译的过程：预处理、编译、汇编和链接 Linux环境下的GCC工具链详解
程序编译的过程中就是将用户的文本形式的源代码(c/c++)转化成计算机可以直接执行的机器代码的过程。主要经过四个过程：预处理、编译、汇编和链接
从C语言源码到可执行程序一般要经过以下的处理步骤：
- 预处理
在这一阶段，源码中的所有预处理语句得到处理，例如 #include语句所包含的文件内容替换掉语句本身所有已定义的宏被展开 根据#ifdef，#if等语句的条件是否成立取舍相应的部分,预处理之后源码中不再包含任何预处理语句。
GCC预处理阶段可以生成.i的文件，通过选项-E可以使编译器在预处理结束时就停止编译。例如：gcc -E -o hello.i hello.c - 编译
这一阶段，编译器对源码进行词法分析、语法分析、优化等操作，最后生成汇编代码。这是整个过程中最重要的一步，因此也常把整个过程称为编译。
可以通过选项-S使GCC在进行完编译后停止，生成.s的汇编程序。例如：
gcc -S -o hello.s hello.c - 汇编
这一阶段使用汇编器对汇编代码进行处理，生成机器语言代码，保存在后缀为.o的目标文件中。目标文件已经是最终程序的某一部分了，只是在链接之前还不能执行。可以通过-c选项生成目标文件gcc -c -o hello.o hello.c - 链接
经过汇编以后的机器代码还不能直接运行。为了使操作系统能够正确加载可执行文件，文件中必须包含固定格式的信息头，还必须与系统提供的启动代码链接起来才能正常运行，这些工作都是由链接器来完成的.
十九、宏 VS 内联函数（inline）
1). 首先宏是C中引入的一种预处理功能；
2). 内联（inline）函数是C++中引用的一个新的关键字；C++中推荐使用内联函数来替代宏代码片段；
3). 内联函数将函数体直接扩展到调用内联函数的地方，这样减少了参数压栈，跳转，返回等过程；
4). 由于内联发生在编译阶段，所以内联相较宏，是有参数检查和返回值检查的，因此使用起来更为安全；
5). 需要注意的是， inline会向编译期提出内联请求，但是是否内联由编译期决定（当然可以通过设置编译器，强制使用内联）；
6). 由于内联是一种优化方式，在某些情况下，即使没有显示的声明内联，比如定义在class内部的方法，编译器也可能将其作为内联函数。
7). 内联函数不能过于复杂，最初C++限定不能有任何形式的循环，不能有过多的条件判断，不能对函数进行取地址操作等，但是现在的编译器几乎没有什么限制，基本都可以实现内联。
用内联函数取代宏的优点：
内联函数在运行时可调试，而宏定义不可以;
编译器会对内联函数的参数类型做安全检查或自动类型转换（同普通函数），而宏定
义则不会；
内联函数可以访问类的成员变量，宏定义则不能
在类中声明同时定义的成员函数，自动转化为内联函数。
内联函数和普通函数相比可以加快程序运行的速度，因为不需要中断调用，在编译的时候内联函数可以直接被镶嵌到目标代码中。
内联函数要做参数类型检查，这是内联函数跟宏相比的优势。
inline是指嵌入代码，就是在调用函数的地方不是跳转，而是把代码直接写到那里去。对于短小的代码来说，inline可以带来一定的效率提升，而且和C时代的宏函数相比，inline 更安全可靠。可是这个是以增加空间消耗为代价的。至于是否需要inline函数就需要根据你的实际情况取舍了。
宏是在代码处不加任何验证的简单替代，而内联函数是将代码直接插入调用处，而减少了普通函数调用时的资源消耗。
宏不是函数，只是在编译前（编译预处理阶段）将程序中有关字符串替换成宏体。
inline函数是函数，但在编译中不单独产生代码，而是将有关代码嵌入到调用处。
二十、i++和++i的区别
理论上++i更快，实际与编译器优化有关，通常几乎无差别。
//i++实现代码为：
int operator++(int)
{
int temp = *this;
++*this;
return temp;
}//返回一个int型的对象本身
// ++i实现代码为：
int& operator++()
{
*this += 1;
return *this;
}//返回一个int型的对象引用
i++和++i的考点比较多，简单来说，就是i++返回的是i的值，而++i返回的是i+1的值。也就是++i是一个确定的值，是一个可修改的左值，如下使用：
cout << ++(++(++i)) << endl;
cout << ++ ++i << endl;
可以不停的嵌套++i。
这里有很多的经典笔试题，一起来观摩下：
int main()
{
int i = 1;
printf("%d,%d\n", ++i, ++i); //3,3
printf("%d,%d\n", ++i, i++); //5,3
printf("%d,%d\n", i++, i++); //6,5
printf("%d,%d\n", i++, ++i); //8,9
system(“pause”);
return 0;
}
首先是函数的参数入栈顺序从右向左入栈的，计算顺序也是从右往左计算的，不过都是计算完以后再进行的压栈操作：
对于第1个printf，首先执行++i，返回值是i，这时i的值是2，再次执行++i，返回值是i，得到i=3，将i压入栈中，此时i为3，也就是压入3，3；
对于第2个printf，首先执行i++，返回值是原来的i，也就是3，再执行++i，返回值是i，依次将3，5压入栈中得到输出结果
对于第3个printf，首先执行i++，返回值是5，再执行i++返回值是6，依次将5，6压入栈中得到输出结果
对于第4个printf，首先执行++i，返回i，此时i为8，再执行i++，返回值是8，此时i为9，依次将i，8也就是9，8压入栈中，得到输出结果。
上面的分析也是基于VS搞的，不过准确来说函数多个参数的计算顺序是未定义的(the order of evaluation of function arguments are undefined)。笔试题目的运行结果随不同的编译器而异。
二十一、PostMessage与SendMessage的区别
在做基于窗口的Windows程序的时候，我们避免不了要向窗口发送消息，有两种方式，一种是PostMessage，另外一种是SendMessage。区别如下：
1、PostMessage会将消息压入窗口所在线程的消息队列，然后返回；而SendMessage则不经过消息队列，SendMessage可认为是直接调用了该窗口的窗口过程，因此在我们需要获得消息处理后的返回值的时候，就要用到SendMessage。
2、在多线程应用中，PostMessage的用法还是一样，但SendMessage则不同了。如果在线程A中向线程B所创建的一个窗口hWndB发送消息SendMessage（hWndB，WM_MSG，0，0），那么系统将会立即将执行权从线程A切换到线程B，然后在线程B中调用hWndB的窗口过程来处理消息，并且在处理完该消息后，执行权仍然在B手中！这个时候，线程A则暂停在SendMessage处，等待下次线程A获得执行权后才继续执行，并且仍然可以获得消息处理的结果（返回值）。一般，为了避免死锁，在B中对WM_MSG做出处理之前，要加上：
if(InSendMessage())
RelpyMessage(lResult)；
即判断：如果该消息是发自另外一个线程，则立即 RelpyMessage，回复消息，参数lResult即是返回值。而如果是在同一个线程内，则InSendMessage()将会返回FALSE。
二十二、struct & union struct VS class
定义：
结构体struct：把不同类型的数据组合成一个整体，自定义类型。
共同体union：使几个不同类型的变量共同占用一段内存。
地址：
struct和union都有内存对齐，结构体的内存布局依赖于CPU、操作系统、编译器及编译时的对齐选项。
结构体struct：不同之处，stuct里每个成员都有自己独立的地址。sizeof(struct)是内存对齐后所有成员长度的加和。
共同体union：当共同体中存入新的数据后，原有的成员就失去了作用，新的数据被写到union的地址中。sizeof(union)是最长的数据成员的长度。
struct和union都是由多个不同的数据类型成员组成, 但在任何同一时刻, union中只存放了一个被选中的成员, 而struct的所有成员都存在。在struct中，各成员都占有自己的内存空间，它们是同时存在的。一个struct变量的总长度等于所有成员长度之和。在Union中，所有成员不能同时占用它的内存空间，它们不能同时存在。Union变量的长度等于最长的成员的长度。对于union的不同成员赋值, 将会对其它成员重写, 原来成员的值就不存在了, 而对于struct的不同成员赋值是互不影响的。
struct VS class：
两种情况：
1.C的struct与C++的class的区别：struct只是作为一种复杂数据类型定义，不能用于面向对象编程。
2.C++中的struct和class的区别：对于成员访问权限以及继承方式，class中默认的是private的，而struct中则是public的。 class还可以用于表示模板类型，struct则不行。
二十四、select、poll和epoll的区别
select，poll，epoll本质上都是同步I/O，因为他们都需要在读写事件就绪后自己负责进行读写，也就是说这个读写过程是阻塞的，而异步I/O则无需自己负责进行读写，异步I/O的实现会负责把数据从内核拷贝到用户空间。
- Select：select本质上是通过设置或者检查存放fd标志位的数据结构来进行下一步处理。对socket进行扫描时是线性扫描，即采用轮询的方法，效率较低。
2.poll：无最大连接数的限制，原因是它是基于链表来存储的。
3.epoll有EPOLLLT和EPOLLET两种触发模式，LT是默认的模式，ET是“高速”模式。LT模式下，只要这个fd还有数据可读，每次 epoll_wait都会返回它的事件，提醒用户程序去操作，而在ET（边缘触发）模式中，它只会提示一次，直到下次再有数据流入之前都不会再提示了，无 论fd中是否还有数据可读。所以在ET模式下，read一个fd的时候一定要把它的buffer读光，也就是说一直读到read的返回值小于请求值，或者 遇到EAGAIN错误。还有一个特点是，epoll使用“事件”的就绪通知方式，通过epoll_ctl注册fd，一旦该fd就绪，内核就会采用类似callback的回调机制来激活该fd，epoll_wait便可以收到通知。
总结：
1、表面上看epoll的性能最好，但是在连接数少并且连接都十分活跃的情况下，select和poll的性能可能比epoll好，毕竟epoll的通知机制需要很多函数回调。
2、select低效是因为每次它都需要轮询。低效也是相对的。
二十五、线程vs进程
1．线程
线程是指进程内的一个执行单元,也是进程内的可调度实体.
2 与进程的区别:
(1)调度：线程作为调度和分配的基本单位，进程作为拥有资源的基本单位
(2)并发性：不仅进程之间可以并发执行，同一个进程的多个线程之间也可并发执行
(3)拥有资源：进程是拥有资源的一个独立单位，线程不拥有系统资源，但可以访问进程拥有的的资源
(4)系统开销：在创建或撤消进程时，由于系统都要为之分配和回收资源，导致系统的开销明显大于创建或撤消线程时的开销。
①一个线程只能属于一个进程，一个进程可以有多个线程；
②系统资源分配给进程，同一进程的所有线程共享该进程的所有资源；
③真正在处理机上运行的是线程；
④不同进程的线程间利用消息通信的方式实现同步。
区别
①调度：线程是系统调度和分配的基本单位，进程是作为拥有系统资源的基本单位；
②并发性：进程之间可以并发执行，同一进程的多个线程时间亦可以并发执行；
③拥有资源：进程是拥有资源的独立单位，线程不拥有资源，但可以访问隶属于进程的资源；
④系统开销：创建和撤销进程的开销更大；进程拥有独立的地址空间，一个进程的崩溃不会影响其他进程；线程拥有自己的堆栈和局部变量，没有独立的地址空间，因此进程里的一个线程崩溃会导致其他线程均崩溃。
线程池：基本思想还是一种对象池的思想，开辟一块内存空间，里面存放了众多(未死亡)的线程，池中线程执行调度由池管理器来处理。当有线程任务时，从池中取一个，执行完成后线程对象归池，这样可以避免反复创建线程对象所带来的性能开销，节省了系统的资源。
二十六、进程间通信
C++ 进程间通信 进程间通信——共享内存
进程间
①管道( pipe )：
管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。
②有名管道 (namedpipe) ：
有名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信。
③信号量(semophore ) ：
信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。
④消息队列( messagequeue ) ：
消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
⑤信号 (sinal ) ：
信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。
⑥共享内存(shared memory ) ：
共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号两，配合使用，来实现进程间的同步和通信。
⑦套接字(socket ) ：
套接口也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同设备及其间的进程通信。
线程间
①锁机制：包括互斥锁、条件变量、读写锁
互斥锁提供了以排他方式防止数据结构被并发修改的方法。
读写锁允许多个线程同时读共享数据，而对写操作是互斥的。
条件变量可以以原子的方式阻塞进程，直到某个特定条件为真为止。对条件的测试是在互斥锁的保护下进行的。条件变量始终与互斥锁一起使用。
②信号量机制(Semaphore)：包括无名线程信号量和命名线程信号量
③信号机制(Signal)：类似进程间的信号处理，线程间的通信目的主要是用于线程同步，所以线程没有像进程通信中的用于数据交换的通信机制。
二十七、OSI七层模型 tcp/UDP http/https
计算机网络 计算机网络-面试题 TCP/IP协议 TCP与UDP
从低到高分别是：物理层、数据链路层、网络层、传输层、会话层、表示层和应用层。
应用层：为操作系统或网络应用程序提供访问网络服务的接口。
应用层任务是通过应用进程间的交互来完成特定网络应用。
应用层协议的代表包括：FTP、HTTP、SMTP等。
运输层：负责向两个主机中进程之间的通信提供服务。运输层还要处理端到端的差错检测(与数据链路层不同)、拥塞控制、流量控制等问题。
运输层协议的代表包括：TCP（面向连接、可靠数据传输服务，数据传输单位是报文段）、UDP（无连接。尽最大努力的数据传输服务，数据传输单位是用户数据报）等。
OSI下3层的主要任务是数据通信，上3层的任务是数据处理。而传输层（Transport Layer）是OSI模型的第4层。因此该层是通信子网和资源子网的接口和桥梁，起到承上启下的作用。协议 和 端口号 是在传输层定义的。
该层的主要任务是：定义了一些传输数据的协议和端口号（如HTTP的端口80等），TCP（传输控制协议，传输效率低，可靠性强，可以用于传输可靠性要求高，数据量大的数据），UDP（用户数据报协议，与TCP特性恰恰相反，用于传输可靠性要求不高，数据量小的数据，如QQ聊天数据就是通过这种方式传输的）。 主要是从下层接收的数据进行分段和传输，到达目的地址后再进行重组。常常把这一层数据叫做报文段。
网络层：负责对子网间的数据包进行路由选择，为分组交换网上的不同主机提供通信服务。
网络层协议的代表包括：IP、ICMP、IGMP等。
数据链路层：数据的封装成帧、数据的透明传输、数据的差错检测。
数据链路层协议的代表包括：PPP、帧中继等。
物理层：通过传输介质发送和接收二进制比特流。
属于物理层定义的典型规范如RJ-45等。
27.1 TCP & UDP
1、TCP面向连接（如打电话要先拨号建立连接）;UDP是无连接的，即发送数据之前不需要建立连接
2、TCP提供可靠的服务。也就是说，通过TCP连接传送的数据，无差错，不丢失，不重复，且按序到达;UDP尽最大努力交付，即不保证可靠交付
3、TCP面向字节流，实际上是TCP把数据看成一连串无结构的字节流;UDP是面向报文的
UDP没有拥塞控制，因此网络出现拥塞不会使源主机的发送速率降低（对实时应用很有用，如IP电话，实时视频会议等）
4、每一条TCP连接只能是点到点的;UDP支持一对一，一对多，多对一和多对多的交互通信
5、TCP首部开销20字节;UDP的首部开销小，只有8个字节
6、TCP的逻辑通信信道是全双工的可靠信道，UDP则是不可靠信道
27.2 http、https的区别
http是超文本传输协议，信息是明文传输，https则是具有安全性的ssl加密传输协议。
http和https使用的是完全不同的连接方式，用的端口也不一样，前者是80，后者是443。
http的连接很简单，是无状态的；HTTPS协议是由SSL+HTTP协议构建的可进行加密传输、身份认证的网络协议，比http协议安全。
27.3 tcp/ip的三次握手
第一次握手：Client将标志位SYN置为1（表示要发起一个连接），随机产生一个值seq=J，并将该数据包发送给Server，Client进入SYN_SENT状态，等待Server确认。
第二次握手：Server收到数据包后由标志位SYN=1知道Client请求建立连接，Server将标志位SYN和ACK都置为1，ack=J+1，随机产生一个值seq=K，并将该数据包发送给Client以确认连接请求，Server进入SYN_RCVD状态。
第三次握手：Client收到确认后，检查ack是否为J+1，ACK是否为1，如果正确则将标志位ACK置为1，ack=K+1，并将该数据包发送给Server，Server检查ack是否为K+1，ACK是否为1，如果正确则连接建立成功，Client和Server进入ESTABLISHED状态，完成三次握手，随后Client与Server之间可以开始传输数据了。
为什么是三次握手不是两次不是四次
三次握手的最主要目的是确认双方都有收发数据的能力。三次握手完成两个重要的功能，既要双方做好发送数据的准备工作(双方都知道彼此已准备好)，也要允许双方就初始序列号进行协商，这个序列号在握手过程中被发送和确认。
第一次： A发给B。证明A有发消息的能力。
第二次： B收到并发消息给A。证明B有收消息，并且有发消息的能力。
第三次： A收到B消息。证明A有收消息的能力。
二次握手达不到目的，四次多余。
27.4 tcp/ip的四次挥手
第一次挥手：首先，客户端发送一个FIN，用来关闭客户端到服务器的数据传送，然后等待服务器的确认。其中终止标志位FIN=1，序列号seq=u。
第二次挥手：服务器收到这个FIN，它发送一个ACK，确认ack为收到的序号加一。
第三次挥手：关闭服务器到客户端的连接，发送一个FIN给客户端。
第四次挥手：客户端收到FIN后，并发回一个ACK报文确认，并将确认序号seq设置为收到序号加一。首先进行关闭的一方将执行主动关闭，而另一方执行被动关闭。
为什么是四次挥手
双方关闭连接要经过双方都同意。所以，首先是客服端给服务器发送FIN，要求关闭连接，服务器收到后会发送一个ACK进行确认。服务器然后再发送一个FIN，客户端发送ACK确认，并进入TIME_WAIT状态。等待2MSL后自动关闭
二十八、Linux面试题 Linux命令总结 ARM-Linux嵌入式系统启动流程 启动脚本编写
基本命令
ps （process status：进程状态，类似于windows的任务管理器）
ping （用于检测与目标的连通性）语法：ping ip地址
free 命令 （显示系统内存）
ARM-Linux嵌入式系统启动流程
1、第一阶段启动ROM-Code；
2、第二阶段启动x-loader
3、第三阶段启动任务u-boot
4、启动内核kernel
5、加载根文件系统
二十九、MFC框架
MFC简介以及基础使用 C++的图像界面学习（MFC）
Windows编程模型
一个应用程序的功能是：创建一个窗口，然后响应键盘或者鼠标消息。
WinMain函数的定义
创建窗口
消息循环
窗口过程
MFC简介
MFC是微软基础类库，以C++类的形式封装了Windows API，并且包含一个应用程序框架。类中包含了大量的windows句柄封装类和很多windows的组件和内建控件的封装类。MFC把Windows SDK API函数包装成了几百个类，MFC给Windows系统提供面向对象的接口，支持可重用性、自包含性以及OPP原则。
三十、c++11新特性
C++11常用新特性
1. nullptr
nullptr 出现的目的是为了替代 NULL。
2. 类型推导
C++11 引入了 auto 和 decltype 这两个关键字实现了类型推导，让编译器来操心变量的类型。
3. 构造函数
委托构造
C++11 引入了委托构造的概念，这使得构造函数可以在同一个类中一个构造函数调用另一个构造函数，从而达到简化代码的目的.
4.Lambda 表达式
Lambda 表达式，实际上就是提供了一个类似匿名函数的特性，而匿名函数则是在需要一个函数，但是又不想费力去命名一个函数的情况下去使用的。
5.新增容器
std::array
std::array 保存在栈内存中，相比堆内存中的 std::vector，我们能够灵活的访问这里面的元素，从而获得更高的性能。
三十一、算法题
1.实现strcpy.
char* MyStrCpy( char *pDest, const char *pSrc )
{
if( nullptr == pDest || nullptr == pSrc )
{
return nullptr;
}
if( pDest == pSrc )
{
return pDest;
}
char *pIter = pDest;
while( ( *pIter++=*pSrc++ ) !=’\0’ );
return pDest;
}
2.strcmp
int strcmp(const char* str1, const char*str2){
assert(str1 != NULL&&str2 != NULL);
while (*str1&&*str1 == *str2){
str1++;
str2++;
}
if (*(unsigned char*)str1 < *(unsigned char*)str2){return -1;
}
else if (*(unsigned char*)str1 > *(unsigned char*)str2){return 1;
}
else{return 0;
}
}
3.strcat
char strcat(char strDest, const charstrSrc){
assert(strDest != NULL&&strSrc != NULL);
char address = strDest;
while (*strDest != ‘\0’) strDest++;
while (*strSrc != '\0'){*strDest = *strSrc;strDest++;strSrc++;
}
*strDest = '\0';//
return address;
}
4.memcpy
void * memcpy ( void * destination, const void * source, size_t num );
自己动手实现memcpy()时就需要考虑地址重叠的情况。
#include
#include
using namespace std;
void* mymemcpy(void* dst, const void* src, size_t n){
if (dst == NULL || src == NULL) return NULL;
char* pdst;
char* psrc;
if (src >= dst || (char*)dst >= (char*)src + n - 1){pdst = (char*)dst;psrc = (char*)src;while (n--){*pdst++ = *psrc++;}
}
else{pdst = (char*)dst+ n - 1;psrc = (char*)src+ n - 1;while (n--){*pdst-- = *psrc--;}
}return dst;
}
int main(){
char buf[100] = "abcdefghijk";
memcpy(buf+2, buf, 5);
//mymemcpy(buf + 2, buf, 5);
printf("%s\n", buf + 2);return 0;
}
5.不使用第三个变量交换两个数的值
void SwapA( int &A, int &B )
{
if( A == B )
{
return;
}
A = A + B;
B = A - B;
A = A - B;
}
void SwapB( unsigned int &A, unsigned int &B )
{
if( A == B )
{
return;
}
A = A ^ B;
B = A ^ B;
A = A ^ B;
}
6.C语言中字符串转数字的方法是什么( atoi )，请实现它
int Myatoi( const char *pString )
{
assert( nullptr != pString );
const int Len = strlen( pString );
int Value = 0;
int Times = 1;
for( int i = Len -1; i >= 0; --i, Times = 10 )
{
Value += ( pString[ i ] - ‘0’ ) * Times;
}
return Value;
}
7.实现一个将字符串逆序的方法
char MyInverted( char *pDest )
{
assert( nullptr != pDest );
const int Len = strlen( pDest );
char T = 0;
for( int i = 0; i < Len / 2; ++i )
{
T = pDest[ i ];
pDest[ i ] = pDest[ Len - i - 1 ];
pDest[ Len - i -1 ] = T;
}
return pDest;
}
8.实现一个将字符串中所有字母转换为大写的方法
char* MyUpper( char *pDest )
{
assert( nullptr != pDest );
for( char *i = pDest; *i != ‘\0’; ++i )
{
if( *i < ‘a’ || *i > ‘z’ )
{
continue;
}
*i -= ‘a’ - ‘A’;
}
return pDest;
}
9.已知一个数组已经降序排序请用二分查字法找到其中的某个元素找到返回索引否则返回-1
int BinarySearch( int *pArray, int Count, int Value )
{
assert( nullptr != pArray );
int Left = 0;
int Right = Count -1;
int Mid = 0;
while( Left <= Right )
{
Mid = ( Left + Right ) / 2;
if( Value < pArray[ Mid ] )
{
Right = Mid - 1;
}
else if( Value > pArray[ Mid ] )
{
Left = Mid + 1;
}
else
{
return Mid;
}
}
return -1;
}
struct Node
{
Node *mpNext;
int mData;
};
10.删除链表中值为Value的所有元素( [Head]->[node1]->[node2]->…[noden] )
void DeleteFromList( Node *pHead, int Value )
{
Node *pPrev = pHead;
Node *pNext = pHead->mpNext;
while( nullptr != pNext )
{
if( pNext->mData != Value )
{
pPrev = pNext;
pNext = pNext->mpNext;
}
else
{
pPrev->mpNext = pNext->mpNext;
delete pNext;
pNext = pPrev->mpNext;
}
}
}
11.在链表Index位置插入新的值为Value的元素
void InsertFromList( Node *pHead, int Index, int Value )
{
Node *pIter = pHead;
for( int i = 0; i < Index && nullptr != pIter; ++i, pIter = pIter->mpNext );
assert( nullptr != pIter );
Node *pNew = new Node;
pNew->mData = Value;
pNew->mpNext = pIter->mpNext;
pIter->mpNext = pNew;
}
12.将链表逆序
Node* InvertedFromList( Node *pHead )
{
//A->B->C
Node *pPrev = pHead; //A
Node *pNext = pHead->mpNext; //B
Node *pNextNext = nullptr; //C
while( nullptr != pNext )
{
pNextNext = pNext->mpNext; //C = B->C
pNext->mpNext = pPrev; //B->A
pPrev = pNext; //A = B pNext = pNextNext; //B = C } pHead->mpNext = nullptr;//C->B->A->null return pPrev; //return C( new head )
}
13.判断X年X月X日是这年的第几天
int GetDay( int Year, int Month, int Day )
{
int MonthDays[ 13 ] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
if( ( Year % 4 == 0 && Year % 100 != 0 ) || ( Year % 400 == 0 ) ) { ++MonthDays[ 2 ]; } int Days = 0;
for( int i = 1; i < Month; ++i ) { Days += MonthDays[ i ]; } Days += Day; return Days;
}
14.求斐波拉契数列第N项
int GetFibonacci1( int N )
{
if( 1 == N || 2 == N )
{
return 1;
}
if( 3 == N )
{
return 2;
}
int A = 2;
int B = 3;
int C = 5;
for( int i = 0; i < N - 4; ++i )
{
C = A + B;
A = B;
B = C;
}
return C;
}
15.递归求斐波拉契数列数列第N项
int GetFibonacci2( int N )
{
if( 1 == N || 2 == N )
{
return 1;
}
return GetFibonacci2( N - 1 ) + GetFibonacci2( N - 2 );
}
16.实现一个产生[N-M]区间数字的随机方法
int GetRandomRange( int N, int M )
{
if( N == M )
{
return N;
}
if( N > M )
{
N = N + M;
M = N - M;
N = N - M;
}
return N + ( rand() % ( M - N + 1 ) );
}
17.实现一个产生[0~1]之间的随机浮点数
double GetRandomRange()
{
return rand() / static_cast< double >( RAND_MAX );
}
18.实现一个打印出1-1000之间的所有素数的方法
void PrintfPrime()
{
//1不是素数
//2是最小非奇数素数
//直接从3开始
printf( “2\n” );
bool b = false;
for( int i = 3; i <= 1000; ++i )
{
b = true;
for( int j = 2; j <= i / 2; ++j )
{
if( i % j == 0 )
{
b = false;
break;
}
}
if( b )
{
printf( “%d\n”, i );
}
}
}
19.请用栈实现队列
int QueuePop( std::stack< int > &StackA )
{
std::stack< int > StackB;
while( false == StackA.empty() )
{
StackB.push( StackA.top() );
StackA.pop();
}
const int top = StackB.top();
StackB.pop(); while( false == StackB.empty() )
{ StackA.push( StackB.top() ); StackB.pop(); }
return top;
}
20.已知X班X成绩0-100分编写一个方法实现0-59打印不合格,60-69打印合格,70-79打印良好,80-100打印优秀
2 //不能使用if,:?,switch
void PrintScore( int Score )
{
assert( Score >= 0 && Score <= 100 );
const char pString[] =
{
“不合格”,
“不合格”,
“不合格”,
“不合格”,
“不合格”,
“不合格”,
“合格”,
“良好”,
“优秀”,
“优秀”,
“优秀”,
};
printf( “%s\n”, pString[ Score / 10 ] );
}
C语言中数字转字符串的方法是什么？(itoa)请实现他
char Myitoa( char *pDest, int val, int radix )
{
assert( NULL != pDest );
assert( radix > 1 );
const bool IsMinu = val < 0;
char buffer[ 16 ] = {};
int count = 0;
do
{ buffer[ count++ ] = abs(val) % radix; val /= radix; } while( val ); if( IsMinu )
{ pDest[ 0 ] = '-'; for( int i = 0; i < count; ++i ) { pDest[ i + 1 ] = '0' + buffer[ count - i - 1 ]; } pDest[ count + 1 ] = '\0'; } else { for( int i = 0; i < count; ++i ) { pDest[ i ] = '0' + buffer[ count - i - 1 ]; } pDest[ count ] = '\0'; } return pDest;
}
21.如何判断链表是否有环
bool IsLoop( Node *pHead )
{
//[H->A->B->C->A]
assert( NULL != pHead );
Node *pNext = pHead->mpNext;
Node *pNextNext = pHead->mpNext;
while( NULL != pNext && NULL != pNextNext->mpNext )
{
pNext = pNext->mpNext;//[ B、C、A ]
pNextNext = pNextNext->mpNext->mpNext;//[C、B、A]
if( pNext == pNextNext )
{
return true;
}
}
return false;
}
22.统计出一个字符串每种字母出现的次数要求时间复杂度为O(n)
void CountLetter( const char *pSrc )
{
int count[ 256 ] = {};
for( ; *pSrc !=’\0’; ++pSrc )
{
const char &c = *pSrc;
if( ( c < ‘A’ || c > ‘z’) && ( c < ‘a’ || c > ‘z’ ) )
{
continue;
}
++count[ c ];
}
}
23.选择排序的思想是什么？( 每次找到最大或最小的值放在数组的低位上 )请实现它
void SelectSort( int *pArray, int count )
{
for( int i = 0; i < count; ++i )
{
//默认低位元素最小
int MinValue = pArray[ i ];
//默认保存低位元素的索引
int MinIndex = i;
//除开第一个元素找是否还有比它还小的元素( 升序 )
for( int j = i + 1; j < count; ++j )
{
//发现找到比它还小的元素重新赋值和保存索引
if( pArray[ j ] < MinValue )
{
MinValue = pArray[ j ];
MinIndex = j;
}
}
//将找到最小元素放在数组低位上面
const int Temp = pArray[ i ];
pArray[ i ] = MinValue;
pArray[ MinIndex ] = Temp;
}
}
24.冒泡排序的思想是什么?(升序排序中越小的数往低位走，越大的数往高位走,每次与相邻元素比较导致的特点)请实现它
void BubbleSort( int *pArray, int count )
{
//eg.[6][8][8][0][9][1]
//i = 0,j < 5 [6][8][0][8][1][9]
//i = 1,j < 4 [6][0][8][1][8][9]
//i = 2,j < 3 [0][6][1][8][8][9]
//i = 3,j < 2 [0][1][6][8][8][9]
//到此为止已经排序OK了
//i = 4,j < 1 [0][1][6][8][8][9] //i = 5,j < 0 [0][1][6][8][8][9] for( int i = 0; i < count; ++i ) { for( int j = 0; j < count - i - 1; ++j ) { if( pArray[ j ] > pArray[ j + 1 ] ) { const int Temp = pArray[ j ]; pArray[ j ] = pArray[ j + 1 ]; pArray[ j + 1 ] = Temp; } } }
}
25.已知两个数组有序实现一个方法将他们合并任然有序
void MergeSort( int *pMerge, int *p1, int p1len, int *p2, int p2len )
{
assert( nullptr != pMerge && nullptr != p1 && nullptr != p2 );
int i = 0; int j = 0; int k = 0; while( i < p1len && j < p2len ) { if( p1[ i ] < p2[ j ] ) { pMerge[ k ] = p1[ i ]; ++k; ++i; } else { pMerge[ k ] = p2[ j ]; ++k; ++j; } } while( i < p1len )
{ pMerge[ k ] = p1[ i ]; ++k; ++i; } while( j < p2len ) { pMerge[ k ] = p2[ j ]; ++k; ++j; }
}
26.实现一个算法找到数组中第二大的数
int FindSec( int *p, int len )
{
assert( nullptr != p );
int maxv = p[ 0 ];
int secv = p[ 0 ];
for( int i = 1; i < len; ++i )
{
if( maxv < p[ i ] )
{
secv = maxv;
maxv = p[ i ];
}
}
return secv;
}
