📚 本仓库是面向 C/C++ 技术方向校招求职者、初学者的基础知识总结,包括语言、程序库、数据结构、算法、系统、网络、链接装载库等知识及面试经验、招聘、内推等信息。 💡 侧边目录支持方式:📚 Docsify 文档、Github + TOC
导航(TOC预览.png) 📄 保存为 PDF 方式:使用 Chrome 浏览器打开 📚
Docsify 文档 页面,缩起左侧目录-右键 - 打印 - 选择目标打印机是另存为PDF - 保存(打印预览.png) 🙏 仓库内容如有错误或改进欢迎 issue 或 pr,建议或讨论可在
#12 提出。由于本人水平有限,仓库中的知识点有来自本人原创、读书笔记、书籍、博文等,非原创均已标明出处,如有遗漏,请 issue 提出。本仓库遵循 CC BY-NC-SA 4.0(署名 - 非商业性使用 - 相同方式共享) 协议,转载请注明出处,不得用于商业目的。 (为了方便记忆可以想成)被 const 修饰(在 const
后面)的值不可改变,如下文使用例子中的 const 使用 宏定义 #define 和 const 常量
static作用
this 指针
inline 内联函数特征
使用inline 使用 // 声明1(加 inline,建议使用) inline int functionName(int first, int second,...); // 声明2(不加 inline) int functionName(int first, int second,...); // 定义 inline int functionName(int first, int second,...) {/****/}; // 类内定义,隐式内联 class A { int doA() { return 0; } // 隐式内联 } // 类外定义,需要显式内联 class A { int doA(); } inline int A::doA() { return 0; } // 需要显式内联 编译器对 inline 函数的处理步骤
优缺点优点
缺点
虚函数(virtual)可以是内联函数(inline)吗?
虚函数内联使用 #include <iostream> using namespace std; class Base { public: inline virtual void who() { cout << "I am Base\n"; } virtual ~Base() {} }; class Derived : public Base { public: inline void who() // 不写inline时隐式内联 { cout << "I am Derived\n"; } }; int main() { // 此处的虚函数 who(),是通过类(Base)的具体对象(b)来调用的,编译期间就能确定了,所以它可以是内联的,但最终是否内联取决于编译器。 Base b; b.who(); // 此处的虚函数是通过指针调用的,呈现多态性,需要在运行时期间才能确定,所以不能为内联。 Base *ptr = new Derived(); ptr->who(); // 因为Base有虚析构函数(virtual ~Base() {}),所以 delete 时,会先调用派生类(Derived)析构函数,再调用基类(Base)析构函数,防止内存泄漏。 delete ptr; ptr = nullptr; system("pause"); return 0; } volatile
assert()断言,是宏,而非函数。assert 宏的原型定义在 assert() 使用 #define NDEBUG // 加上这行,则 assert 不可用 #include <assert.h> assert( p != NULL ); // assert 不可用 sizeof()
#pragma pack(n)设定结构体、联合以及类成员变量以 n 字节方式对齐 #pragma pack(n) 使用 #pragma pack(push) // 保存对齐状态 #pragma pack(4) // 设定为 4 字节对齐 struct test { char m1; double m4; int m3; }; #pragma pack(pop) // 恢复对齐状态 位域Bit mode: 2; // mode 占 2 位 类可以将其(非静态)数据成员定义为位域(bit-field),在一个位域中含有一定数量的二进制位。当一个程序需要向其他程序或硬件设备传递二进制数据时,通常会用到位域。
extern "C"
extern "C" 使用 #ifdef __cplusplus extern "C" { #endif void *memset(void *, int, size_t); #ifdef __cplusplus } #endif struct 和 typedef structC 中// c typedef struct Student { int age; } S; 等价于 // c struct Student { int age; }; typedef struct Student S; 此时 另外还可以定义与 C++ 中由于编译器定位符号的规则(搜索规则)改变,导致不同于C语言。 一、如果在类标识符空间定义了 即表现为可以使用 // cpp struct Student { int age; }; void f( Student me ); // 正确,"struct" 关键字可省略 二、若定义了与 typedef struct Student { int age; } S; void Student() {} // 正确,定义后 "Student" 只代表此函数 //void S() {} // 错误,符号 "S" 已经被定义为一个 "struct Student" 的别名 int main() { Student(); struct Student me; // 或者 "S me"; return 0; } C++ 中 struct 和 class总的来说,struct 更适合看成是一个数据结构的实现体,class 更适合看成是一个对象的实现体。 区别
union 联合联合(union)是一种节省空间的特殊的类,一个 union 可以有多个数据成员,但是在任意时刻只有一个数据成员可以有值。当某个成员被赋值后其他成员变为未定义状态。联合有如下特点:
union 使用 #include<iostream> union UnionTest { UnionTest() : i(10) {}; int i; double d; }; static union { int i; double d; }; int main() { UnionTest u; union { int i; double d; }; std::cout << u.i << std::endl; // 输出 UnionTest 联合的 10 ::i = 20; std::cout << ::i << std::endl; // 输出全局静态匿名联合的 20 i = 30; std::cout << i << std::endl; // 输出局部匿名联合的 30 return 0; } C 实现 C++ 类C 实现 C++ 的面向对象特性(封装、继承、多态)
explicit(显式)关键字
explicit 使用 struct A { A(int) { } operator bool() const { return true; } }; struct B { explicit B(int) {} explicit operator bool() const { return true; } }; void doA(A a) {} void doB(B b) {} int main() { A a1(1); // OK:直接初始化 A a2 = 1; // OK:复制初始化 A a3{ 1 }; // OK:直接列表初始化 A a4 = { 1 }; // OK:复制列表初始化 A a5 = (A)1; // OK:允许 static_cast 的显式转换 doA(1); // OK:允许从 int 到 A 的隐式转换 if (a1); // OK:使用转换函数 A::operator bool() 的从 A 到 bool 的隐式转换 bool a6(a1); // OK:使用转换函数 A::operator bool() 的从 A 到 bool 的隐式转换 bool a7 = a1; // OK:使用转换函数 A::operator bool() 的从 A 到 bool 的隐式转换 bool a8 = static_cast<bool>(a1); // OK :static_cast 进行直接初始化 B b1(1); // OK:直接初始化 B b2 = 1; // 错误:被 explicit 修饰构造函数的对象不可以复制初始化 B b3{ 1 }; // OK:直接列表初始化 B b4 = { 1 }; // 错误:被 explicit 修饰构造函数的对象不可以复制列表初始化 B b5 = (B)1; // OK:允许 static_cast 的显式转换 doB(1); // 错误:被 explicit 修饰构造函数的对象不可以从 int 到 B 的隐式转换 if (b1); // OK:被 explicit 修饰转换函数 B::operator bool() 的对象可以从 B 到 bool 的按语境转换 bool b6(b1); // OK:被 explicit 修饰转换函数 B::operator bool() 的对象可以从 B 到 bool 的按语境转换 bool b7 = b1; // 错误:被 explicit 修饰转换函数 B::operator bool() 的对象不可以隐式转换 bool b8 = static_cast<bool>(b1); // OK:static_cast 进行直接初始化 return 0; } friend 友元类和友元函数
usingusing 声明一条 using namespace_name::name; 构造函数的 using 声明在 C++11 中,派生类能够重用其直接基类定义的构造函数。 class Derived : Base { public: using Base::Base; /* ... */ }; 如上 using 声明,对于基类的每个构造函数,编译器都生成一个与之对应(形参列表完全相同)的派生类构造函数。生成如下类型构造函数: Derived(parms) : Base(args) { } using 指示
using namespace_name name; 尽量少使用 |
容器 | 底层数据结构 | 时间复杂度 | 有无序 | 可不可重复 | 其他 |
---|---|---|---|---|---|
array | 数组 | 随机读改 O(1) | 无序 | 可重复 | 支持随机访问 |
vector | 数组 | 随机读改、尾部插入、尾部删除 O(1) 头部插入、头部删除 O(n) | 无序 | 可重复 | 支持随机访问 |
deque | 双端队列 | 头尾插入、头尾删除 O(1) | 无序 | 可重复 | 一个中央控制器 + 多个缓冲区,支持首尾快速增删,支持随机访问 |
forward_list | 单向链表 | 插入、删除 O(1) | 无序 | 可重复 | 不支持随机访问 |
list | 双向链表 | 插入、删除 O(1) | 无序 | 可重复 | 不支持随机访问 |
stack | deque / list | 顶部插入、顶部删除 O(1) | 无序 | 可重复 | deque 或 list 封闭头端开口,不用 vector 的原因应该是容量大小有限制,扩容耗时 |
queue | deque / list | 尾部插入、头部删除 O(1) | 无序 | 可重复 | deque 或 list 封闭头端开口,不用 vector 的原因应该是容量大小有限制,扩容耗时 |
priority_queue | vector + max-heap | 插入、删除 O(log2n) | 有序 | 可重复 | vector容器+heap处理规则 |
set | 红黑树 | 插入、删除、查找 O(log2n) | 有序 | 不可重复 | |
multiset | 红黑树 | 插入、删除、查找 O(log2n) | 有序 | 可重复 | |
map | 红黑树 | 插入、删除、查找 O(log2n) | 有序 | 不可重复 | |
multimap | 红黑树 | 插入、删除、查找 O(log2n) | 有序 | 可重复 | |
unordered_set | 哈希表 | 插入、删除、查找 O(1) 最差 O(n) | 无序 | 不可重复 | |
unordered_multiset | 哈希表 | 插入、删除、查找 O(1) 最差 O(n) | 无序 | 可重复 | |
unordered_map | 哈希表 | 插入、删除、查找 O(1) 最差 O(n) | 无序 | 不可重复 | |
unordered_multimap | 哈希表 | 插入、删除、查找 O(1) 最差 O(n) | 无序 | 可重复 |
STL 算法
算法 | 底层算法 | 时间复杂度 | 可不可重复 |
---|---|---|---|
find | 顺序查找 | O(n) | 可重复 |
sort | 内省排序 | O(n*log2n) | 可重复 |
〽️ 数据结构
顺序结构
顺序栈(Sequence Stack)
SqStack.cpp
顺序栈数据结构和图片
typedef struct { ElemType *elem; int top; int size; int increment; } SqStack;
队列(Sequence Queue)
队列数据结构
typedef struct { ElemType * elem; int front; int rear; int maxSize; }SqQueue;
非循环队列
非循环队列图片
SqQueue.rear++
循环队列
循环队列图片
SqQueue.rear = (SqQueue.rear + 1) % SqQueue.maxSize
顺序表(Sequence List)
SqList.cpp
顺序表数据结构和图片
typedef struct { ElemType *elem; int length; int size; int increment; } SqList;
链式结构
LinkList.cpp
LinkList_with_head.cpp
链式数据结构
typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList;
链队列(Link Queue)
链队列图片
线性表的链式表示
单链表(Link List)
单链表图片
双向链表(Du-Link-List)
双向链表图片
循环链表(Cir-Link-List)
循环链表图片
哈希表
HashTable.cpp
概念
哈希函数:H(key): K -> D , key ∈ K
构造方法
- 直接定址法
- 除留余数法
- 数字分析法
- 折叠法
- 平方取中法
冲突处理方法
- 链地址法:key 相同的用单链表链接
- 开放定址法
- 线性探测法:key 相同 -> 放到 key 的下一个位置,
Hi = (H(key) + i) % m
- 二次探测法:key 相同 -> 放到
Di = 1^2, -1^2, ..., ±(k)^2,(k<=m/2)
- 随机探测法:
H = (H(key) + 伪随机数) % m
- 线性探测法:key 相同 -> 放到 key 的下一个位置,
线性探测的哈希表数据结构
线性探测的哈希表数据结构和图片
typedef char KeyType; typedef struct { KeyType key; }RcdType; typedef struct { RcdType *rcd; int size; int count; bool *tag; }HashTable;
递归
概念
函数直接或间接地调用自身
递归与分治
- 分治法
- 问题的分解
- 问题规模的分解
- 折半查找(递归)
- 归并排序(递归)
- 快速排序(递归)
递归与迭代
- 迭代:反复利用变量旧值推出新值
- 折半查找(迭代)
- 归并排序(迭代)
广义表
头尾链表存储表示
广义表的头尾链表存储表示和图片
// 广义表的头尾链表存储表示 typedef enum {ATOM, LIST} ElemTag; // ATOM==0:原子,LIST==1:子表 typedef struct GLNode { ElemTag tag; // 公共部分,用于区分原子结点和表结点 union { // 原子结点和表结点的联合部分 AtomType atom; // atom 是原子结点的值域,AtomType 由用户定义 struct { struct GLNode *hp, *tp; } ptr; // ptr 是表结点的指针域,prt.hp 和 ptr.tp 分别指向表头和表尾 } a; } *GList, GLNode;
扩展线性链表存储表示
扩展线性链表存储表示和图片
// 广义表的扩展线性链表存储表示 typedef enum {ATOM, LIST} ElemTag; // ATOM==0:原子,LIST==1:子表 typedef struct GLNode1 { ElemTag tag; // 公共部分,用于区分原子结点和表结点 union { // 原子结点和表结点的联合部分 AtomType atom; // 原子结点的值域 struct GLNode1 *hp; // 表结点的表头指针 } a; struct GLNode1 *tp; // 相当于线性链表的 next,指向下一个元素结点 } *GList1, GLNode1;
二叉树
BinaryTree.cpp
性质
- 非空二叉树第 i 层最多 2(i-1) 个结点 (i >= 1)
- 深度为 k 的二叉树最多 2k - 1 个结点 (k >= 1)
- 度为 0 的结点数为 n0,度为 2 的结点数为 n2,则 n0 = n2 + 1
- 有 n 个结点的完全二叉树深度 k = ⌊ log2(n) ⌋ + 1
- 对于含 n 个结点的完全二叉树中编号为 i (1 <= i <= n) 的结点
- 若 i = 1,为根,否则双亲为 ⌊ i / 2 ⌋
- 若 2i > n,则 i 结点没有左孩子,否则孩子编号为 2i
- 若 2i + 1 > n,则 i 结点没有右孩子,否则孩子编号为 2i + 1
存储结构
二叉树数据结构
typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree;
顺序存储
二叉树顺序存储图片
链式存储
二叉树链式存储图片
遍历方式
- 先序遍历
- 中序遍历
- 后续遍历
- 层次遍历
分类
- 满二叉树
- 完全二叉树(堆)
- 大顶堆:根 >= 左 && 根 >= 右
- 小顶堆:根 <= 左 && 根 <= 右
- 二叉查找树(二叉排序树):左 < 根 < 右
- 平衡二叉树(AVL树):| 左子树树高 - 右子树树高 | <= 1
- 最小失衡树:平衡二叉树插入新结点导致失衡的子树:调整:
- LL型:根的左孩子右旋
- RR型:根的右孩子左旋
- LR型:根的左孩子左旋,再右旋
- RL型:右孩子的左子树,先右旋,再左旋
其他树及森林
树的存储结构
- 双亲表示法
- 双亲孩子表示法
- 孩子兄弟表示法
并查集
一种不相交的子集所构成的集合 S = {S1, S2, ..., Sn}
平衡二叉树(AVL树)
性质
- | 左子树树高 - 右子树树高 | <= 1
- 平衡二叉树必定是二叉搜索树,反之则不一定
- 最小二叉平衡树的节点的公式:
F(n)=F(n-1)+F(n-2)+1
(1 是根节点,F(n-1) 是左子树的节点数量,F(n-2) 是右子树的节点数量)
平衡二叉树图片
最小失衡树
平衡二叉树插入新结点导致失衡的子树
调整:
- LL 型:根的左孩子右旋
- RR 型:根的右孩子左旋
- LR 型:根的左孩子左旋,再右旋
- RL 型:右孩子的左子树,先右旋,再左旋
红黑树
RedBlackTree.cpp
红黑树的特征是什么?
- 节点是红色或黑色。
- 根是黑色。
- 所有叶子都是黑色(叶子是 NIL 节点)。
- 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)(新增节点的父节点必须相同)
- 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。(新增节点必须为红)
调整
- 变色
- 左旋
- 右旋
应用
- 关联数组:如 STL 中的 map、set
红黑树、B 树、B+ 树的区别?
- 红黑树的深度比较大,而 B 树和 B+ 树的深度则相对要小一些
- B+ 树则将数据都保存在叶子节点,同时通过链表的形式将他们连接在一起。
B 树(B-tree)、B+ 树(B+-tree)
B 树、B+ 树图片
特点
- 一般化的二叉查找树(binary search tree)
- “矮胖”,内部(非叶子)节点可以拥有可变数量的子节点(数量范围预先定义好)
应用
- 大部分文件系统、数据库系统都采用B树、B+树作为索引结构
区别
- B+树中只有叶子节点会带有指向记录的指针(ROWID),而B树则所有节点都带有,在内部节点出现的索引项不会再出现在叶子节点中。
- B+树中所有叶子节点都是通过指针连接在一起,而B树不会。
B树的优点
对于在内部节点的数据,可直接得到,不必根据叶子节点来定位。
B+树的优点
- 非叶子节点不会带上 ROWID,这样,一个块中可以容纳更多的索引项,一是可以降低树的高度。二是一个内部节点可以定位更多的叶子节点。
- 叶子节点之间通过指针来连接,范围扫描将十分简单,而对于B树来说,则需要在叶子节点和内部节点不停的往返移动。
B 树、B+ 树区别来自:differences-between-b-trees-and-b-trees、B树和B+树的区别
八叉树
八叉树图片
八叉树(octree),或称八元树,是一种用于描述三维空间(划分空间)的树状数据结构。八叉树的每个节点表示一个正方体的体积元素,每个节点有八个子节点,这八个子节点所表示的体积元素加在一起就等于父节点的体积。一般中心点作为节点的分叉中心。
用途
- 三维计算机图形
- 最邻近搜索
⚡️ 算法
排序
排序算法 | 平均时间复杂度 | 最差时间复杂度 | 空间复杂度 | 数据对象稳定性 |
---|---|---|---|---|
冒泡排序 | O(n2) | O(n2) | O(1) | 稳定 |
选择排序 | O(n2) | O(n2) | O(1) | 数组不稳定、链表稳定 |
插入排序 | O(n2) | O(n2) | O(1) | 稳定 |
快速排序 | O(n*log2n) | O(n2) | O(log2n) | 不稳定 |
堆排序 | O(n*log2n) | O(n*log2n) | O(1) | 不稳定 |
归并排序 | O(n*log2n) | O(n*log2n) | O(n) | 稳定 |
希尔排序 | O(n*log2n) | O(n2) | O(1) | 不稳定 |
计数排序 | O(n+m) | O(n+m) | O(n+m) | 稳定 |
桶排序 | O(n) | O(n) | O(m) | 稳定 |
基数排序 | O(k*n) | O(n2) | 稳定 |
- 均按从小到大排列
- k:代表数值中的 “数位” 个数
- n:代表数据规模
- m:代表数据的最大值减最小值
- 来自:wikipedia . 排序算法
查找
查找算法 | 平均时间复杂度 | 空间复杂度 | 查找条件 |
---|---|---|---|
顺序查找 | O(n) | O(1) | 无序或有序 |
二分查找(折半查找) | O(log2n) | O(1) | 有序 |
插值查找 | O(log2(log2n)) | O(1) | 有序 |
斐波那契查找 | O(log2n) | O(1) | 有序 |
哈希查找 | O(1) | O(n) | 无序或有序 |
二叉查找树(二叉搜索树查找) | O(log2n) | ||
红黑树 | O(log2n) | ||
2-3树 | O(log2n - log3n) | ||
B树/B+树 | O(log2n) |
图搜索算法
图搜索算法 | 数据结构 | 遍历时间复杂度 | 空间复杂度 |
---|---|---|---|
BFS广度优先搜索 | 邻接矩阵 邻接链表 | O(|v|2) O(|v|+|E|) | O(|v|2) O(|v|+|E|) |
DFS深度优先搜索 | 邻接矩阵 邻接链表 | O(|v|2) O(|v|+|E|) | O(|v|2) O(|v|+|E|) |
其他算法
算法 | 思想 | 应用 |
---|---|---|
分治法 | 把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并 | 循环赛日程安排问题、排序算法(快速排序、归并排序) |
动态规划 | 通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法,适用于有重叠子问题和最优子结构性质的问题 | 背包问题、斐波那契数列 |
贪心法 | 一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是最好或最优的算法 | 旅行推销员问题(最短路径问题)、最小生成树、哈夫曼编码 |
❓ Problems
Single Problem
- Chessboard Coverage Problem(棋盘覆盖问题)
- Knapsack Problem(背包问题)
- Neumann Neighbor Problem(冯诺依曼邻居问题)
- Round Robin Problem(循环赛日程安排问题)
- Tubing Problem(输油管道问题)
Leetcode Problems
- Github . haoel/leetcode
- Github . pezy/LeetCode
剑指 Offer
- Github . zhedahht/CodingInterviewChinese2
- Github . gatieme/CodingInterviews
Cracking the Coding Interview 程序员面试金典
- Github . careercup/ctci
- 牛客网 . 程序员面试金典
牛客网
- 牛客网 . 在线编程专题
💻 操作系统
进程与线程
对于有线程系统:
- 进程是资源分配的独立单位
- 线程是资源调度的独立单位
对于无线程系统:
- 进程是资源调度、分配的独立单位
进程之间的通信方式以及优缺点
- 管道(PIPE)
- 有名管道:一种半双工的通信方式,它允许无亲缘关系进程间的通信
- 优点:可以实现任意关系的进程间的通信
- 缺点:
- 长期存于系统中,使用不当容易出错
- 缓冲区有限
- 无名管道:一种半双工的通信方式,只能在具有亲缘关系的进程间使用(父子进程)
- 优点:简单方便
- 缺点:
- 局限于单向通信
- 只能创建在它的进程以及其有亲缘关系的进程之间
- 缓冲区有限
- 有名管道:一种半双工的通信方式,它允许无亲缘关系进程间的通信
- 信号量(Semaphore):一个计数器,可以用来控制多个线程对共享资源的访问
- 优点:可以同步进程
- 缺点:信号量有限
- 信号(Signal):一种比较复杂的通信方式,用于通知接收进程某个事件已经发生
- 消息队列(Message Queue):是消息的链表,存放在内核中并由消息队列标识符标识
- 优点:可以实现任意进程间的通信,并通过系统调用函数来实现消息发送和接收之间的同步,无需考虑同步问题,方便
- 缺点:信息的复制需要额外消耗 CPU 的时间,不适宜于信息量大或操作频繁的场合
- 共享内存(Shared Memory):映射一段能被其他进程所访问的内存,这段共享内存由一个进程创建,但多个进程都可以访问
- 优点:无须复制,快捷,信息量大
- 缺点:
- 通信是通过将共享空间缓冲区直接附加到进程的虚拟地址空间中来实现的,因此进程间的读写操作的同步问题
- 利用内存缓冲区直接交换信息,内存的实体存在于计算机中,只能同一个计算机系统中的诸多进程共享,不方便网络通信
- 套接字(Socket):可用于不同计算机间的进程通信
- 优点:
- 传输数据为字节级,传输数据可自定义,数据量小效率高
- 传输数据时间短,性能高
- 适合于客户端和服务器端之间信息实时交互
- 可以加密,数据安全性强
- 缺点:需对传输的数据进行解析,转化成应用级的数据。
- 优点:
线程之间的通信方式
- 锁机制:包括互斥锁/量(mutex)、读写锁(reader-writer lock)、自旋锁(spin lock)、条件变量(condition)
- 互斥锁/量(mutex):提供了以排他方式防止数据结构被并发修改的方法。
- 读写锁(reader-writer lock):允许多个线程同时读共享数据,而对写操作是互斥的。
- 自旋锁(spin lock)与互斥锁类似,都是为了保护共享资源。互斥锁是当资源被占用,申请者进入睡眠状态;而自旋锁则循环检测保持者是否已经释放锁。
- 条件变量(condition):可以以原子的方式阻塞进程,直到某个特定条件为真为止。对条件的测试是在互斥锁的保护下进行的。条件变量始终与互斥锁一起使用。
- 信号量机制(Semaphore)
- 无名线程信号量
- 命名线程信号量
- 信号机制(Signal):类似进程间的信号处理
- 屏障(barrier):屏障允许每个线程等待,直到所有的合作线程都达到某一点,然后从该点继续执行。
线程间的通信目的主要是用于线程同步,所以线程没有像进程通信中的用于数据交换的通信机制
进程之间的通信方式以及优缺点来源于:进程线程面试题总结
进程之间私有和共享的资源
- 私有:地址空间、堆、全局变量、栈、寄存器
- 共享:代码段,公共数据,进程目录,进程 ID
线程之间私有和共享的资源
- 私有:线程栈,寄存器,程序计数器
- 共享:堆,地址空间,全局变量,静态变量
多进程与多线程间的对比、优劣与选择
对比
对比维度 | 多进程 | 多线程 | 总结 |
---|---|---|---|
数据共享、同步 | 数据共享复杂,需要用 IPC;数据是分开的,同步简单 | 因为共享进程数据,数据共享简单,但也是因为这个原因导致同步复杂 | 各有优势 |
内存、CPU | 占用内存多,切换复杂,CPU 利用率低 | 占用内存少,切换简单,CPU 利用率高 | 线程占优 |
创建销毁、切换 | 创建销毁、切换复杂,速度慢 | 创建销毁、切换简单,速度很快 | 线程占优 |
编程、调试 | 编程简单,调试简单 | 编程复杂,调试复杂 | 进程占优 |
可靠性 | 进程间不会互相影响 | 一个线程挂掉将导致整个进程挂掉 | 进程占优 |
分布式 | 适应于多核、多机分布式;如果一台机器不够,扩展到多台机器比较简单 | 适应于多核分布式 | 进程占优 |
优劣
优劣 | 多进程 | 多线程 |
---|---|---|
优点 | 编程、调试简单,可靠性较高 | 创建、销毁、切换速度快,内存、资源占用小 |
缺点 | 创建、销毁、切换速度慢,内存、资源占用大 | 编程、调试复杂,可靠性较差 |
选择
- 需要频繁创建销毁的优先用线程
- 需要进行大量计算的优先使用线程
- 强相关的处理用线程,弱相关的处理用进程
- 可能要扩展到多机分布的用进程,多核分布的用线程
- 都满足需求的情况下,用你最熟悉、最拿手的方式
多进程与多线程间的对比、优劣与选择来自:多线程还是多进程的选择及区别
Linux 内核的同步方式
原因
在现代操作系统里,同一时间可能有多个内核执行流在执行,因此内核其实像多进程多线程编程一样也需要一些同步机制来同步各执行单元对共享数据的访问。尤其是在多处理器系统上,更需要一些同步机制来同步不同处理器上的执行单元对共享的数据的访问。
同步方式
- 原子操作
- 信号量(semaphore)
- 读写信号量(rw_semaphore)
- 自旋锁(spinlock)
- 大内核锁(BKL,Big Kernel Lock)
- 读写锁(rwlock)
- 大读者锁(brlock-Big Reader Lock)
- 读-拷贝修改(RCU,Read-Copy Update)
- 顺序锁(seqlock)
来自:Linux 内核的同步机制,第 1 部分、Linux 内核的同步机制,第 2 部分
死锁
原因
- 系统资源不足
- 资源分配不当
- 进程运行推进顺序不合适
产生条件
- 互斥
- 请求和保持
- 不剥夺
- 环路
预防
- 打破互斥条件:改造独占性资源为虚拟资源,大部分资源已无法改造。
- 打破不可抢占条件:当一进程占有一独占性资源后又申请一独占性资源而无法满足,则退出原占有的资源。
- 打破占有且申请条件:采用资源预先分配策略,即进程运行前申请全部资源,满足则运行,不然就等待,这样就不会占有且申请。
- 打破循环等待条件:实现资源有序分配策略,对所有设备实现分类编号,所有进程只能采用按序号递增的形式申请资源。
- 有序资源分配法
- 银行家算法
文件系统
- Windows:FCB 表 + FAT + 位图
- Unix:inode + 混合索引 + 成组链接
主机字节序与网络字节序
主机字节序(CPU 字节序)
概念
主机字节序又叫 CPU 字节序,其不是由操作系统决定的,而是由 CPU 指令集架构决定的。主机字节序分为两种:
- 大端字节序(Big Endian):高序字节存储在低位地址,低序字节存储在高位地址
- 小端字节序(Little Endian):高序字节存储在高位地址,低序字节存储在低位地址
存储方式
32 位整数 0x12345678
是从起始位置为 0x00
的地址开始存放,则:
内存地址 | 0x00 | 0x01 | 0x02 | 0x03 |
---|---|---|---|---|
大端 | 12 | 34 | 56 | 78 |
小端 | 78 | 56 | 34 | 12 |
大端小端图片
判断大端小端
判断大端小端
可以这样判断自己 CPU 字节序是大端还是小端:
#include <iostream> using namespace std; int main() { int i = 0x12345678; if (*((char*)&i) == 0x12) cout << "大端" << endl; else cout << "小端" << endl; return 0; }
各架构处理器的字节序
- x86(Intel、AMD)、MOS Technology 6502、Z80、VAX、PDP-11 等处理器为小端序;
- Motorola 6800、Motorola 68000、PowerPC 970、System/370、SPARC(除 V9 外)等处理器为大端序;
- ARM(默认小端序)、PowerPC(除 PowerPC 970 外)、DEC Alpha、SPARC V9、MIPS、PA-RISC 及 IA64 的字节序是可配置的。
网络字节序
网络字节顺序是 TCP/IP 中规定好的一种数据表示格式,它与具体的 CPU 类型、操作系统等无关,从而可以保证数据在不同主机之间传输时能够被正确解释。
网络字节顺序采用:大端(Big Endian)排列方式。
页面置换算法
在地址映射过程中,若在页面中发现所要访问的页面不在内存中,则产生缺页中断。当发生缺页中断时,如果操作系统内存中没有空闲页面,则操作系统必须在内存选择一个页面将其移出内存,以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。
分类
- 全局置换:在整个内存空间置换
- 局部置换:在本进程中进行置换
算法
全局:
- 工作集算法
- 缺页率置换算法
局部:
- 最佳置换算法(OPT)
- 先进先出置换算法(FIFO)
- 最近最久未使用(LRU)算法
- 时钟(Clock)置换算法
☁️ 计算机网络
本节部分知识点来自《计算机网络(第 7 版)》
计算机网络体系结构:
各层作用及协议
分层 | 作用 | 协议 |
---|---|---|
物理层 | 通过媒介传输比特,确定机械及电气规范(比特 Bit) | RJ45、CLOCK、IEEE802.3(中继器,集线器) |
数据链路层 | 将比特组装成帧和点到点的传递(帧 Frame) | PPP、FR、HDLC、VLAN、MAC(网桥,交换机) |
网络层 | 负责数据包从源到宿的传递和网际互连(包 Packet) | IP、ICMP、ARP、RARP、OSPF、IPX、RIP、IGRP(路由器) |
运输层 | 提供端到端的可靠报文传递和错误恢复( 段Segment) | TCP、UDP、SPX |
会话层 | 建立、管理和终止会话(会话协议数据单元 SPDU) | NFS、SQL、NETBIOS、RPC |
表示层 | 对数据进行翻译、加密和压缩(表示协议数据单元 PPDU) | JPEG、MPEG、ASII |
应用层 | 允许访问OSI环境的手段(应用协议数据单元 APDU) | FTP、DNS、Telnet、SMTP、HTTP、WWW、NFS |
物理层
- 传输数据的单位:比特
- 数据传输系统:源系统(源点、发送器) --> 传输系统 --> 目的系统(接收器、终点)
通道:
- 单向通道(单工通道):只有一个方向通信,没有反方向交互,如广播
- 双向交替通信(半双工通信):通信双方都可发消息,但不能同时发送或接收
- 双向同时通信(全双工通信):通信双方可以同时发送和接收信息
通道复用技术:
- 频分复用(FDM,Frequency Division Multiplexing):不同用户在不同频带,所用用户在同样时间占用不同带宽资源
- 时分复用(TDM,Time Division Multiplexing):不同用户在同一时间段的不同时间片,所有用户在不同时间占用同样的频带宽度
- 波分复用(WDM,Wavelength Division Multiplexing):光的频分复用
- 码分复用(CDM,Code Division Multiplexing):不同用户使用不同的码,可以在同样时间使用同样频带通信
数据链路层
主要信道:
- 点对点信道
- 广播信道
点对点信道
- 数据单元:帧
三个基本问题:
- 封装成帧:把网络层的 IP 数据报封装成帧,
SOH - 数据部分 - EOT
- 透明传输:不管数据部分什么字符,都能传输出去;可以通过字节填充方法解决(冲突字符前加转义字符)
- 差错检测:降低误码率(BER,Bit Error Rate),广泛使用循环冗余检测(CRC,Cyclic Redundancy Check)
点对点协议(Point-to-Point Protocol):
- 点对点协议(Point-to-Point Protocol):用户计算机和 ISP 通信时所使用的协议
广播信道
广播通信:
- 硬件地址(物理地址、MAC 地址)
- 单播(unicast)帧(一对一):收到的帧的 MAC 地址与本站的硬件地址相同
- 广播(broadcast)帧(一对全体):发送给本局域网上所有站点的帧
- 多播(multicast)帧(一对多):发送给本局域网上一部分站点的帧
网络层
- IP(Internet Protocol,网际协议)是为计算机网络相互连接进行通信而设计的协议。
- ARP(Address Resolution Protocol,地址解析协议)
- ICMP(Internet Control Message Protocol,网际控制报文协议)
- IGMP(Internet Group Management Protocol,网际组管理协议)
IP 网际协议
IP 地址分类:
IP 地址 ::= {<网络号>,<主机号>}
IP 地址类别 | 网络号 | 网络范围 | 主机号 | IP 地址范围 |
---|---|---|---|---|
A 类 | 8bit,第一位固定为 0 | 0 —— 127 | 24bit | 1.0.0.0 —— 127.255.255.255 |
B 类 | 16bit,前两位固定为 10 | 128.0 —— 191.255 | 16bit | 128.0.0.0 —— 191.255.255.255 |
C 类 | 24bit,前三位固定为 110 | 192.0.0 —— 223.255.255 | 8bit | 192.0.0.0 —— 223.255.255.255 |
D 类 | 前四位固定为 1110,后面为多播地址 | |||
E 类 | 前五位固定为 11110,后面保留为今后所用 |
IP 数据报格式:
ICMP 网际控制报文协议
ICMP 报文格式:
应用:
- PING(Packet InterNet Groper,分组网间探测)测试两个主机之间的连通性
- TTL(Time To Live,生存时间)该字段指定 IP 包被路由器丢弃之前允许通过的最大网段数量
内部网关协议
- RIP(Routing Information Protocol,路由信息协议)
- OSPF(Open Sortest Path First,开放最短路径优先)
外部网关协议
- BGP(Border Gateway Protocol,边界网关协议)
IP多播
- IGMP(Internet Group Management Protocol,网际组管理协议)
- 多播路由选择协议
VPN 和 NAT
- VPN(Virtual Private Network,虚拟专用网)
- NAT(Network Address Translation,网络地址转换)
路由表包含什么?
- 网络 ID(Network ID, Network number):就是目标地址的网络 ID。
- 子网掩码(subnet mask):用来判断 IP 所属网络
- 下一跳地址/接口(Next hop / interface):就是数据在发送到目标地址的旅途中下一站的地址。其中 interface 指向 next hop(即为下一个 route)。一个自治系统(AS, Autonomous system)中的 route 应该包含区域内所有的子网络,而默认网关(Network id:
0.0.0.0
, Netmask:0.0.0.0
)指向自治系统的出口。
根据应用和执行的不同,路由表可能含有如下附加信息:
- 花费(Cost):就是数据发送过程中通过路径所需要的花费。
- 路由的服务质量
- 路由中需要过滤的出/入连接列表
运输层
协议:
- TCP(Transmission Control Protocol,传输控制协议)
- UDP(User Datagram Protocol,用户数据报协议)
端口:
应用程序 | FTP | TELNET | SMTP | DNS | TFTP | HTTP | HTTPS | SNMP |
---|---|---|---|---|---|---|---|---|
端口号 | 21 | 23 | 25 | 53 | 69 | 80 | 443 | 161 |
TCP
- TCP(Transmission Control Protocol,传输控制协议)是一种面向连接的、可靠的、基于字节流的传输层通信协议,其传输的单位是报文段。
特征:
- 面向连接
- 只能点对点(一对一)通信
- 可靠交互
- 全双工通信
- 面向字节流
TCP 如何保证可靠传输:
- 确认和超时重传
- 数据合理分片和排序
- 流量控制
- 拥塞控制
- 数据校验
TCP 报文结构
TCP 首部
TCP:状态控制码(Code,Control Flag),占 6 比特,含义如下:
- URG:紧急比特(urgent),当
URG=1
时,表明紧急指针字段有效,代表该封包为紧急封包。它告诉系统此报文段中有紧急数据,应尽快传送(相当于高优先级的数据), 且上图中的 Urgent Pointer 字段也会被启用。 - ACK:确认比特(Acknowledge)。只有当
ACK=1
时确认号字段才有效,代表这个封包为确认封包。当ACK=0
时,确认号无效。 - PSH:(Push function)若为 1 时,代表要求对方立即传送缓冲区内的其他对应封包,而无需等缓冲满了才送。
- RST:复位比特(Reset),当
RST=1
时,表明 TCP 连接中出现严重差错(如由于主机崩溃或其他原因),必须释放连接,然后再重新建立运输连接。 - SYN:同步比特(Synchronous),SYN 置为 1,就表示这是一个连接请求或连接接受报文,通常带有 SYN 标志的封包表示『主动』要连接到对方的意思。
- FIN:终止比特(Final),用来释放一个连接。当
FIN=1
时,表明此报文段的发送端的数据已发送完毕,并要求释放运输连接。
UDP
- UDP(User Datagram Protocol,用户数据报协议)是 OSI(Open System Interconnection 开放式系统互联) 参考模型中一种无连接的传输层协议,提供面向事务的简单不可靠信息传送服务,其传输的单位是用户数据报。
特征:
- 无连接
- 尽最大努力交付
- 面向报文
- 没有拥塞控制
- 支持一对一、一对多、多对一、多对多的交互通信
- 首部开销小
UDP 报文结构
UDP 首部
TCP/UDP 图片来源于:https://github.com/JerryC8080/understand-tcp-udp
TCP 与 UDP 的区别
- TCP 面向连接,UDP 是无连接的;
- TCP 提供可靠的服务,也就是说,通过 TCP 连接传送的数据,无差错,不丢失,不重复,且按序到达;UDP 尽最大努力交付,即不保证可靠交付
- TCP 的逻辑通信信道是全双工的可靠信道;UDP 则是不可靠信道
- 每一条 TCP 连接只能是点到点的;UDP 支持一对一,一对多,多对一和多对多的交互通信
- TCP 面向字节流(可能出现黏包问题),实际上是 TCP 把数据看成一连串无结构的字节流;UDP 是面向报文的(不会出现黏包问题)
- UDP 没有拥塞控制,因此网络出现拥塞不会使源主机的发送速率降低(对实时应用很有用,如 IP 电话,实时视频会议等)
- TCP 首部开销20字节;UDP 的首部开销小,只有 8 个字节
TCP 黏包问题
原因
TCP 是一个基于字节流的传输服务(UDP 基于报文的),“流” 意味着 TCP 所传输的数据是没有边界的。所以可能会出现两个数据包黏在一起的情况。
解决
- 发送定长包。如果每个消息的大小都是一样的,那么在接收对等方只要累计接收数据,直到数据等于一个定长的数值就将它作为一个消息。
- 包头加上包体长度。包头是定长的 4 个字节,说明了包体的长度。接收对等方先接收包头长度,依据包头长度来接收包体。
- 在数据包之间设置边界,如添加特殊符号
\r\n
标记。FTP 协议正是这么做的。但问题在于如果数据正文中也含有\r\n
,则会误判为消息的边界。 - 使用更加复杂的应用层协议。
TCP 流量控制
概念
流量控制(flow control)就是让发送方的发送速率不要太快,要让接收方来得及接收。
方法
利用可变窗口进行流量控制
TCP 拥塞控制
概念
拥塞控制就是防止过多的数据注入到网络中,这样可以使网络中的路由器或链路不致过载。
方法
- 慢开始( slow-start )
- 拥塞避免( congestion avoidance )
- 快重传( fast retransmit )
- 快恢复( fast recovery )
TCP的拥塞控制图
TCP 传输连接管理
因为 TCP 三次握手建立连接、四次挥手释放连接很重要,所以附上《计算机网络(第 7 版)-谢希仁》书中对此章的详细描述:https://gitee.com/huihut/interview/raw/master/images/TCP-transport-connection-management.png
TCP 三次握手建立连接
【TCP 建立连接全过程解释】
- 客户端发送 SYN 给服务器,说明客户端请求建立连接;
- 服务端收到客户端发的 SYN,并回复 SYN+ACK 给客户端(同意建立连接);
- 客户端收到服务端的 SYN+ACK 后,回复 ACK 给服务端(表示客户端收到了服务端发的同意报文);
- 服务端收到客户端的 ACK,连接已建立,可以数据传输。
TCP 为什么要进行三次握手?
【答案一】因为信道不可靠,而 TCP 想在不可靠信道上建立可靠地传输,那么三次通信是理论上的最小值。(而 UDP 则不需建立可靠传输,因此 UDP 不需要三次握手。)
Google Groups . TCP 建立连接为什么是三次握手?{技术}{网络通信}
【答案二】因为双方都需要确认对方收到了自己发送的序列号,确认过程最少要进行三次通信。
知乎 . TCP 为什么是三次握手,而不是两次或四次?
【答案三】为了防止已失效的连接请求报文段突然又传送到了服务端,因而产生错误。
《计算机网络(第 7 版)-谢希仁》
TCP 四次挥手释放连接
【TCP 释放连接全过程解释】
- 客户端发送 FIN 给服务器,说明客户端不必发送数据给服务器了(请求释放从客户端到服务器的连接);
- 服务器接收到客户端发的 FIN,并回复 ACK 给客户端(同意释放从客户端到服务器的连接);
- 客户端收到服务端回复的 ACK,此时从客户端到服务器的连接已释放(但服务端到客户端的连接还未释放,并且客户端还可以接收数据);
- 服务端继续发送之前没发完的数据给客户端;
- 服务端发送 FIN+ACK 给客户端,说明服务端发送完了数据(请求释放从服务端到客户端的连接,就算没收到客户端的回复,过段时间也会自动释放);
- 客户端收到服务端的 FIN+ACK,并回复 ACK 给服务端(同意释放从服务端到客户端的连接);
- 服务端收到客户端的 ACK 后,释放从服务端到客户端的连接。
TCP 为什么要进行四次挥手?
【问题一】TCP 为什么要进行四次挥手? / 为什么 TCP 建立连接需要三次,而释放连接则需要四次?
【答案一】因为 TCP 是全双工模式,客户端请求关闭连接后,客户端向服务端的连接关闭(一二次挥手),服务端继续传输之前没传完的数据给客户端(数据传输),服务端向客户端的连接关闭(三四次挥手)。所以 TCP 释放连接时服务器的 ACK 和 FIN 是分开发送的(中间隔着数据传输),而 TCP 建立连接时服务器的 ACK 和 SYN 是一起发送的(第二次握手),所以 TCP 建立连接需要三次,而释放连接则需要四次。
【问题二】为什么 TCP 连接时可以 ACK 和 SYN 一起发送,而释放时则 ACK 和 FIN 分开发送呢?(ACK 和 FIN 分开是指第二次和第三次挥手)
【答案二】因为客户端请求释放时,服务器可能还有数据需要传输给客户端,因此服务端要先响应客户端 FIN 请求(服务端发送 ACK),然后数据传输,传输完成后,服务端再提出 FIN 请求(服务端发送 FIN);而连接时则没有中间的数据传输,因此连接时可以 ACK 和 SYN 一起发送。
【问题三】为什么客户端释放最后需要 TIME-WAIT 等待 2MSL 呢?
【答案三】
- 为了保证客户端发送的最后一个 ACK 报文能够到达服务端。若未成功到达,则服务端超时重传 FIN+ACK 报文段,客户端再重传 ACK,并重新计时。
- 防止已失效的连接请求报文段出现在本连接中。TIME-WAIT 持续 2MSL 可使本连接持续的时间内所产生的所有报文段都从网络中消失,这样可使下次连接中不会出现旧的连接报文段。
TCP 有限状态机
TCP 有限状态机图片
应用层
DNS
- DNS(Domain Name System,域名系统)是互联网的一项服务。它作为将域名和 IP 地址相互映射的一个分布式数据库,能够使人更方便地访问互联网。DNS 使用 TCP 和 UDP 端口 53。当前,对于每一级域名长度的限制是 63 个字符,域名总长度则不能超过 253 个字符。
域名:
域名 ::= {<三级域名>.<二级域名>.<顶级域名>}
,如:blog.huihut.com
FTP
- FTP(File Transfer Protocol,文件传输协议)是用于在网络上进行文件传输的一套标准协议,使用客户/服务器模式,使用 TCP 数据报,提供交互式访问,双向传输。
- TFTP(Trivial File Transfer Protocol,简单文件传输协议)一个小且易实现的文件传输协议,也使用客户-服务器方式,使用UDP数据报,只支持文件传输而不支持交互,没有列目录,不能对用户进行身份鉴定
TELNET
TELNET 协议是 TCP/IP 协议族中的一员,是 Internet 远程登陆服务的标准协议和主要方式。它为用户提供了在本地计算机上完成远程主机工作的能力。
HTTP(HyperText Transfer Protocol,超文本传输协议)是用于从 WWW(World Wide Web,万维网)服务器传输超文本到本地浏览器的传送协议。
SMTP(Simple Mail Transfer Protocol,简单邮件传输协议)是一组用于由源地址到目的地址传送邮件的规则,由它来控制信件的中转方式。SMTP 协议属于 TCP/IP 协议簇,它帮助每台计算机在发送或中转信件时找到下一个目的地。
Socket 建立网络通信连接至少要一对端口号(Socket)。Socket 本质是编程接口(API),对 TCP/IP 的封装,TCP/IP 也要提供可供程序员做网络开发所用的接口,这就是 Socket 编程接口。
WWW
- WWW(World Wide Web,环球信息网,万维网)是一个由许多互相链接的超文本组成的系统,通过互联网访问
URL
- URL(Uniform Resource Locator,统一资源定位符)是因特网上标准的资源的地址(Address)
标准格式:
协议类型:[//服务器地址[:端口号]][/资源层级UNIX文件路径]文件名[?查询][#片段ID]
完整格式:
协议类型:[//[访问资源需要的凭证信息@]服务器地址[:端口号]][/资源层级UNIX文件路径]文件名[?查询][#片段ID]
其中【访问凭证信息@;:端口号;?查询;#片段ID】都属于选填项
如:https://github.com/huihut/interview#cc
HTTP
HTTP(HyperText Transfer Protocol,超文本传输协议)是一种用于分布式、协作式和超媒体信息系统的应用层协议。HTTP 是万维网的数据通信的基础。
请求方法
方法 | 意义 |
---|---|
OPTIONS | 请求一些选项信息,允许客户端查看服务器的性能 |
GET | 请求指定的页面信息,并返回实体主体 |
HEAD | 类似于 get 请求,只不过返回的响应中没有具体的内容,用于获取报头 |
POST | 向指定资源提交数据进行处理请求(例如提交表单或者上传文件)。数据被包含在请求体中。POST请求可能会导致新的资源的建立和/或已有资源的修改 |
PUT | 从客户端向服务器传送的数据取代指定的文档的内容 |
DELETE | 请求服务器删除指定的页面 |
TRACE | 回显服务器收到的请求,主要用于测试或诊断 |
状态码(Status-Code)
- 1xx:表示通知信息,如请求收到了或正在进行处理
- 100 Continue:继续,客户端应继续其请求
- 101 Switching Protocols 切换协议。服务器根据客户端的请求切换协议。只能切换到更高级的协议,例如,切换到 HTTP 的新版本协议
- 2xx:表示成功,如接收或知道了
- 200 OK: 请求成功
- 3xx:表示重定向,如要完成请求还必须采取进一步的行动
- 301 Moved Permanently: 永久移动。请求的资源已被永久的移动到新 URL,返回信息会包括新的 URL,浏览器会自动定向到新 URL。今后任何新的请求都应使用新的 URL 代替
- 4xx:表示客户的差错,如请求中有错误的语法或不能完成
- 400 Bad Request: 客户端请求的语法错误,服务器无法理解
- 401 Unauthorized: 请求要求用户的身份认证
- 403 Forbidden: 服务器理解请求客户端的请求,但是拒绝执行此请求(权限不够)
- 404 Not Found: 服务器无法根据客户端的请求找到资源(网页)。通过此代码,网站设计人员可设置 “您所请求的资源无法找到” 的个性页面
- 408 Request Timeout: 服务器等待客户端发送的请求时间过长,超时
- 5xx:表示服务器的差错,如服务器失效无法完成请求
- 500 Internal Server Error: 服务器内部错误,无法完成请求
- 503 Service Unavailable: 由于超载或系统维护,服务器暂时的无法处理客户端的请求。延时的长度可包含在服务器的 Retry-After 头信息中
- 504 Gateway Timeout: 充当网关或代理的服务器,未及时从远端服务器获取请求
更多状态码:菜鸟教程 . HTTP状态码
其他协议
- SMTP(Simple Main Transfer Protocol,简单邮件传输协议)是在 Internet 传输 Email 的标准,是一个相对简单的基于文本的协议。在其之上指定了一条消息的一个或多个接收者(在大多数情况下被确认是存在的),然后消息文本会被传输。可以很简单地通过 Telnet 程序来测试一个 SMTP 服务器。SMTP 使用 TCP 端口 25。
- DHCP(Dynamic Host Configuration
Protocol,动态主机设置协议)是一个局域网的网络协议,使用 UDP 协议工作,主要有两个用途:
- 用于内部网络或网络服务供应商自动分配 IP 地址给用户
- 用于内部网络管理员作为对所有电脑作中央管理的手段
- SNMP(Simple Network Management Protocol,简单网络管理协议)构成了互联网工程工作小组(IETF,Internet Engineering Task Force)定义的 Internet 协议族的一部分。该协议能够支持网络管理系统,用以监测连接到网络上的设备是否有任何引起管理上关注的情况。
🌩 网络编程
Socket
Linux Socket 编程(不限 Linux)
Socket 中的 read()、write() 函数
ssize_t read(int fd, void *buf, size_t count); ssize_t write(int fd, const void *buf, size_t count);
read()
- read 函数是负责从 fd 中读取内容。
- 当读成功时,read 返回实际所读的字节数。
- 如果返回的值是 0 表示已经读到文件的结束了,小于 0 表示出现了错误。
- 如果错误为 EINTR 说明读是由中断引起的;如果是 ECONNREST 表示网络连接出了问题。
write()
- write 函数将 buf 中的 nbytes 字节内容写入文件描述符 fd。
- 成功时返回写的字节数。失败时返回 -1,并设置 errno 变量。
- 在网络程序中,当我们向套接字文件描述符写时有俩种可能。
- (1)write 的返回值大于 0,表示写了部分或者是全部的数据。
- (2)返回的值小于 0,此时出现了错误。
- 如果错误为 EINTR 表示在写的时候出现了中断错误;如果为 EPIPE 表示网络连接出现了问题(对方已经关闭了连接)。
Socket 中 TCP 的三次握手建立连接
我们知道 TCP 建立连接要进行 “三次握手”,即交换三个分组。大致流程如下:
- 客户端向服务器发送一个 SYN J
- 服务器向客户端响应一个 SYN K,并对 SYN J 进行确认 ACK J+1
- 客户端再想服务器发一个确认 ACK K+1
只有就完了三次握手,但是这个三次握手发生在 Socket 的那几个函数中呢?请看下图:
从图中可以看出:
- 当客户端调用 connect 时,触发了连接请求,向服务器发送了 SYN J 包,这时 connect 进入阻塞状态;
- 服务器监听到连接请求,即收到 SYN J 包,调用 accept 函数接收请求向客户端发送 SYN K ,ACK J+1,这时 accept 进入阻塞状态;
- 客户端收到服务器的 SYN K ,ACK J+1 之后,这时 connect 返回,并对 SYN K 进行确认;
- 服务器收到 ACK K+1 时,accept 返回,至此三次握手完毕,连接建立。
Socket 中 TCP 的四次握手释放连接
上面介绍了 socket 中 TCP 的三次握手建立过程,及其涉及的 socket 函数。现在我们介绍 socket 中的四次握手释放连接的过程,请看下图:
图示过程如下:
- 某个应用进程首先调用 close 主动关闭连接,这时 TCP 发送一个 FIN M;
- 另一端接收到 FIN M 之后,执行被动关闭,对这个 FIN 进行确认。它的接收也作为文件结束符传递给应用进程,因为 FIN 的接收意味着应用进程在相应的连接上再也接收不到额外数据;
- 一段时间之后,接收到文件结束符的应用进程调用 close 关闭它的 socket。这导致它的 TCP 也发送一个 FIN N;
- 接收到这个 FIN 的源发送端 TCP 对它进行确认。
这样每个方向上都有一个 FIN 和 ACK。
💾 数据库
本节部分知识点来自《数据库系统概论(第 5 版)》
基本概念
- 数据(data):描述事物的符号记录称为数据。
- 数据库(DataBase,DB):是长期存储在计算机内、有组织的、可共享的大量数据的集合,具有永久存储、有组织、可共享三个基本特点。
- 数据库管理系统(DataBase Management System,DBMS):是位于用户与操作系统之间的一层数据管理软件。
- 数据库系统(DataBase System,DBS):是有数据库、数据库管理系统(及其应用开发工具)、应用程序和数据库管理员(DataBase Administrator DBA)组成的存储、管理、处理和维护数据的系统。
- 实体(entity):客观存在并可相互区别的事物称为实体。
- 属性(attribute):实体所具有的某一特性称为属性。
- 码(key):唯一标识实体的属性集称为码。
- 实体型(entity type):用实体名及其属性名集合来抽象和刻画同类实体,称为实体型。
- 实体集(entity set):同一实体型的集合称为实体集。
- 联系(relationship):实体之间的联系通常是指不同实体集之间的联系。
- 模式(schema):模式也称逻辑模式,是数据库全体数据的逻辑结构和特征的描述,是所有用户的公共数据视图。
- 外模式(external schema):外模式也称子模式(subschema)或用户模式,它是数据库用户(包括应用程序员和最终用户)能够看见和使用的局部数据的逻辑结构和特征的描述,是数据库用户的数据视图,是与某一应用有关的数据的逻辑表示。
- 内模式(internal schema):内模式也称为存储模式(storage schema),一个数据库只有一个内模式。他是数据物理结构和存储方式的描述,是数据库在数据库内部的组织方式。
常用数据模型
- 层次模型(hierarchical model)
- 网状模型(network model)
- 关系模型(relational model)
- 关系(relation):一个关系对应通常说的一张表
- 元组(tuple):表中的一行即为一个元组
- 属性(attribute):表中的一列即为一个属性
- 码(key):表中可以唯一确定一个元组的某个属性组
- 域(domain):一组具有相同数据类型的值的集合
- 分量:元组中的一个属性值
- 关系模式:对关系的描述,一般表示为
关系名(属性1, 属性2, ..., 属性n)
- 面向对象数据模型(object oriented data model)
- 对象关系数据模型(object relational data model)
- 半结构化数据模型(semistructure data model)
常用 SQL 操作
对象类型 | 对象 | 操作类型 |
---|---|---|
数据库模式 | 模式 | CREATE SCHEMA
|
基本表 | CREATE SCHEMA ,ALTER TABLE
| |
视图 | CREATE VIEW
| |
索引 | CREATE INDEX
| |
数据 | 基本表和视图 | SELECT ,INSERT ,UPDATE ,DELETE ,REFERENCES ,ALL PRIVILEGES
|
属性列 | SELECT ,INSERT ,UPDATE ,REFERENCES ,ALL PRIVILEGES
|
SQL 语法教程:runoob . SQL 教程
关系型数据库
- 基本关系操作:查询(选择、投影、连接(等值连接、自然连接、外连接(左外连接、右外连接))、除、并、差、交、笛卡尔积等)、插入、删除、修改
- 关系模型中的三类完整性约束:实体完整性、参照完整性、用户定义的完整性
索引
- 数据库索引:顺序索引、B+ 树索引、hash 索引
- MySQL 索引背后的数据结构及算法原理
数据库完整性
- 数据库的完整性是指数据的正确性和相容性。
- 完整性:为了防止数据库中存在不符合语义(不正确)的数据。
- 安全性:为了保护数据库防止恶意破坏和非法存取。
- 触发器:是用户定义在关系表中的一类由事件驱动的特殊过程。
关系数据理论
- 数据依赖是一个关系内部属性与属性之间的一种约束关系,是通过属性间值的相等与否体现出来的数据间相关联系。
- 最重要的数据依赖:函数依赖、多值依赖。
范式
- 第一范式(1NF):属性(字段)是最小单位不可再分。
- 第二范式(2NF):满足 1NF,每个非主属性完全依赖于主键(消除 1NF 非主属性对码的部分函数依赖)。
- 第三范式(3NF):满足 2NF,任何非主属性不依赖于其他非主属性(消除 2NF 非主属性对码的传递函数依赖)。
- 鲍依斯-科得范式(BCNF):满足 3NF,任何非主属性不能对主键子集依赖(消除 3NF 主属性对码的部分和传递函数依赖)。
- 第四范式(4NF):满足 3NF,属性之间不能有非平凡且非函数依赖的多值依赖(消除 3NF 非平凡且非函数依赖的多值依赖)。
数据库恢复
- 事务:是用户定义的一个数据库操作序列,这些操作要么全做,要么全不做,是一个不可分割的工作单位。
- 事物的 ACID 特性:原子性、一致性、隔离性、持续性。
- 恢复的实现技术:建立冗余数据 -> 利用冗余数据实施数据库恢复。
- 建立冗余数据常用技术:数据转储(动态海量转储、动态增量转储、静态海量转储、静态增量转储)、登记日志文件。
并发控制
- 事务是并发控制的基本单位。
- 并发操作带来的数据不一致性包括:丢失修改、不可重复读、读 “脏” 数据。
- 并发控制主要技术:封锁、时间戳、乐观控制法、多版本并发控制等。
- 基本封锁类型:排他锁(X 锁 / 写锁)、共享锁(S 锁 / 读锁)。
- 活锁死锁:
- 活锁:事务永远处于等待状态,可通过先来先服务的策略避免。
- 死锁:事务永远不能结束
- 预防:一次封锁法、顺序封锁法;
- 诊断:超时法、等待图法;
- 解除:撤销处理死锁代价最小的事务,并释放此事务的所有的锁,使其他事务得以继续运行下去。
- 可串行化调度:多个事务的并发执行是正确的,当且仅当其结果与按某一次序串行地执行这些事务时的结果相同。可串行性时并发事务正确调度的准则。
📏 设计模式
各大设计模式例子参考:CSDN专栏 . C++ 设计模式 系列博文
设计模式工程目录
单例模式
单例模式例子
抽象工厂模式
抽象工厂模式例子
适配器模式
适配器模式例子
桥接模式
桥接模式例子
观察者模式
观察者模式例子
设计模式的六大原则
- 单一职责原则(SRP,Single Responsibility Principle)
- 里氏替换原则(LSP,Liskov Substitution Principle)
- 依赖倒置原则(DIP,Dependence Inversion Principle)
- 接口隔离原则(ISP,Interface Segregation Principle)
- 迪米特法则(LoD,Law of Demeter)
- 开放封闭原则(OCP,Open Close Principle)
⚙️ 链接装载库
本节部分知识点来自《程序员的自我修养——链接装载库》
内存、栈、堆
一般应用程序内存空间有如下区域:
- 栈:由操作系统自动分配释放,存放函数的参数值、局部变量等的值,用于维护函数调用的上下文
- 堆:一般由程序员分配释放,若程序员不释放,程序结束时可能由操作系统回收,用来容纳应用程序动态分配的内存区域
- 可执行文件映像:存储着可执行文件在内存中的映像,由装载器装载是将可执行文件的内存读取或映射到这里
- 保留区:保留区并不是一个单一的内存区域,而是对内存中受到保护而禁止访问的内存区域的总称,如通常 C 语言讲无效指针赋值为 0(NULL),因此 0 地址正常情况下不可能有效的访问数据
栈
栈保存了一个函数调用所需要的维护信息,常被称为堆栈帧(Stack Frame)或活动记录(Activate Record),一般包含以下几方面:
- 函数的返回地址和参数
- 临时变量:包括函数的非静态局部变量以及编译器自动生成的其他临时变量
- 保存上下文:包括函数调用前后需要保持不变的寄存器
堆
堆分配算法:
- 空闲链表(Free List)
- 位图(Bitmap)
- 对象池
“段错误(segment fault)” 或 “非法操作,该内存地址不能 read/write”
典型的非法指针解引用造成的错误。当指针指向一个不允许读写的内存地址,而程序却试图利用指针来读或写该地址时,会出现这个错误。
普遍原因:
- 将指针初始化为 NULL,之后没有给它一个合理的值就开始使用指针
- 没用初始化栈中的指针,指针的值一般会是随机数,之后就直接开始使用指针
编译链接
各平台文件格式
平台 | 可执行文件 | 目标文件 | 动态库/共享对象 | 静态库 |
---|---|---|---|---|
Windows | exe | obj | dll | lib |
Unix/Linux | ELF、out | o | so | a |
Mac | Mach-O | o | dylib、tbd、framework | a、framework |
编译链接过程
- 预编译(预编译器处理如
#include
、#define
等预编译指令,生成.i
或.ii
文件) - 编译(编译器进行词法分析、语法分析、语义分析、中间代码生成、目标代码生成、优化,生成
.s
文件) - 汇编(汇编器把汇编码翻译成机器码,生成
.o
文件) - 链接(连接器进行地址和空间分配、符号决议、重定位,生成
.out
文件)
现在版本 GCC 把预编译和编译合成一步,预编译编译程序 cc1、汇编器 as、连接器 ld
MSVC 编译环境,编译器 cl、连接器 link、可执行文件查看器 dumpbin
目标文件
编译器编译源代码后生成的文件叫做目标文件。目标文件从结构上讲,它是已经编译后的可执行文件格式,只是还没有经过链接的过程,其中可能有些符号或有些地址还没有被调整。
可执行文件(Windows 的
.exe
和 Linux 的ELF
)、动态链接库(Windows 的.dll
和 Linux 的.so
)、静态链接库(Windows 的.lib
和 Linux 的.a
)都是按照可执行文件格式存储(Windows 按照 PE-COFF,Linux 按照 ELF)
目标文件格式
- Windows 的 PE(Portable Executable),或称为 PE-COFF,
.obj
格式 - Linux 的 ELF(Executable Linkable Format),
.o
格式 - Intel/Microsoft 的 OMF(Object Module Format)
- Unix 的
a.out
格式 - MS-DOS 的
.COM
格式
PE 和 ELF 都是 COFF(Common File Format)的变种
目标文件存储结构
段 | 功能 |
---|---|
File Header | 文件头,描述整个文件的文件属性(包括文件是否可执行、是静态链接或动态连接及入口地址、目标硬件、目标操作系统等) |
.text section | 代码段,执行语句编译成的机器代码 |
.data section | 数据段,已初始化的全局变量和局部静态变量 |
.bss section | BSS 段(Block Started by Symbol),未初始化的全局变量和局部静态变量(因为默认值为 0,所以只是在此预留位置,不占空间) |
.rodata section | 只读数据段,存放只读数据,一般是程序里面的只读变量(如 const 修饰的变量)和字符串常量 |
.comment section | 注释信息段,存放编译器版本信息 |
.note.GNU-stack section | 堆栈提示段 |
其他段略
链接的接口————符号
在链接中,目标文件之间相互拼合实际上是目标文件之间对地址的引用,即对函数和变量的地址的引用。我们将函数和变量统称为符号(Symbol),函数名或变量名就是符号名(Symbol Name)。
如下符号表(Symbol Table):
Symbol(符号名) | Symbol Value (地址) |
---|---|
main | 0x100 |
Add | 0x123 |
... | ... |
Linux 的共享库(Shared Library)
Linux 下的共享库就是普通的 ELF 共享对象。
共享库版本更新应该保证二进制接口 ABI(Application Binary Interface)的兼容
命名
libname.so.x.y.z
- x:主版本号,不同主版本号的库之间不兼容,需要重新编译
- y:次版本号,高版本号向后兼容低版本号
- z:发布版本号,不对接口进行更改,完全兼容
路径
大部分包括 Linux 在内的开源系统遵循 FHS(File Hierarchy Standard)的标准,这标准规定了系统文件如何存放,包括各个目录结构、组织和作用。
/lib
:存放系统最关键和最基础的共享库,如动态链接器、C 语言运行库、数学库等/usr/lib
:存放非系统运行时所需要的关键性的库,主要是开发库/usr/local/lib
:存放跟操作系统本身并不十分相关的库,主要是一些第三方应用程序的库
动态链接器会在
/lib
、/usr/lib
和由/etc/ld.so.conf
配置文件指定的,目录中查找共享库
环境变量
LD_LIBRARY_PATH
:临时改变某个应用程序的共享库查找路径,而不会影响其他应用程序LD_PRELOAD
:指定预先装载的一些共享库甚至是目标文件LD_DEBUG
:打开动态链接器的调试功能
so 共享库的编写
使用 CLion 编写共享库
创建一个名为 MySharedLib 的共享库
CMakeLists.txt
cmake_minimum_required(VERSION 3.10) project(MySharedLib) set(CMAKE_CXX_STANDARD 11) add_library(MySharedLib SHARED library.cpp library.h)
library.h
#ifndef MYSHAREDLIB_LIBRARY_H #define MYSHAREDLIB_LIBRARY_H // 打印 Hello World! void hello(); // 使用可变模版参数求和 template <typename T> T sum(T t) { return t; } template <typename T, typename ...Types> T sum(T first, Types ... rest) { return first + sum<T>(rest...); } #endif
library.cpp
#include <iostream> #include "library.h" void hello() { std::cout << "Hello, World!" << std::endl; }
so 共享库的使用(被可执行项目调用)
使用 CLion 调用共享库
创建一个名为 TestSharedLib 的可执行项目
CMakeLists.txt
cmake_minimum_required(VERSION 3.10) project(TestSharedLib) # C++11 编译 set(CMAKE_CXX_STANDARD 11) # 头文件路径 set(INC_DIR /home/xx/code/clion/MySharedLib) # 库文件路径 set(LIB_DIR /home/xx/code/clion/MySharedLib/cmake-build-debug) include_directories(${INC_DIR}) link_directories(${LIB_DIR}) link_libraries(MySharedLib) add_executable(TestSharedLib main.cpp) # 链接 MySharedLib 库 target_link_libraries(TestSharedLib MySharedLib)
main.cpp
#include <iostream> #include "library.h" using std::cout; using std::endl; int main() { hello(); cout << "1 + 2 = " << sum(1,2) << endl; cout << "1 + 2 + 3 = " << sum(1,2,3) << endl; return 0; }
执行结果
Hello, World!
1 + 2 = 3
1 + 2 + 3 = 6
Windows 应用程序入口函数
- GUI(Graphical User
Interface)应用,链接器选项:
/SUBSYSTEM:WINDOWS
- CUI(Console User Interface)应用,链接器选项:
/SUBSYSTEM:CONSOLE
_tWinMain 与 _tmain 函数声明
Int WINAPI _tWinMain( HINSTANCE hInstanceExe, HINSTANCE, PTSTR pszCmdLine, int nCmdShow); int _tmain( int argc, TCHAR *argv[], TCHAR *envp[]);
应用程序类型 | 入口点函数 | 嵌入可执行文件的启动函数 |
---|---|---|
处理ANSI字符(串)的GUI应用程序 | _tWinMain(WinMain) | WinMainCRTSartup |
处理Unicode字符(串)的GUI应用程序 | _tWinMain(wWinMain) | wWinMainCRTSartup |
处理ANSI字符(串)的CUI应用程序 | _tmain(Main) | mainCRTSartup |
处理Unicode字符(串)的CUI应用程序 | _tmain(wMain) | wmainCRTSartup |
动态链接库(Dynamic-Link Library) | DllMain | _DllMainCRTStartup |
Windows 的动态链接库(Dynamic-Link Library)
部分知识点来自《Windows 核心编程(第五版)》
用处
- 扩展了应用程序的特性
- 简化了项目管理
- 有助于节省内存
- 促进了资源的共享
- 促进了本地化
- 有助于解决平台间的差异
- 可以用于特殊目的
注意
- 创建 DLL,事实上是在创建可供一个可执行模块调用的函数
- 当一个模块提供一个内存分配函数(malloc、new)的时候,它必须同时提供另一个内存释放函数(free、delete)
- 在使用 C 和 C++ 混编的时候,要使用 extern "C" 修饰符
- 一个 DLL 可以导出函数、变量(避免导出)、C++ 类(导出导入需要同编译器,否则避免导出)
- DLL 模块:cpp 文件中的 __declspec(dllexport) 写在 include 头文件之前
- 调用 DLL 的可执行模块:cpp 文件的 __declspec(dllimport) 之前不应该定义 MYLIBAPI
加载 Windows 程序的搜索顺序
- 包含可执行文件的目录
- Windows 的系统目录,可以通过 GetSystemDirectory 得到
- 16 位的系统目录,即 Windows 目录中的 System 子目录
- Windows 目录,可以通过 GetWindowsDirectory 得到
- 进程的当前目录
- PATH 环境变量中所列出的目录
DLL 入口函数
DllMain 函数
BOOL WINAPI DllMain(HINSTANCE hinstDLL, DWORD fdwReason, LPVOID lpvReserved) { switch(fdwReason) { case DLL_PROCESS_ATTACH: // 第一次将一个DLL映射到进程地址空间时调用 // The DLL is being mapped into the process' address space. break; case DLL_THREAD_ATTACH: // 当进程创建一个线程的时候,用于告诉DLL执行与线程相关的初始化(非主线程执行) // A thread is bing created. break; case DLL_THREAD_DETACH: // 系统调用 ExitThread 线程退出前,即将终止的线程通过告诉DLL执行与线程相关的清理 // A thread is exiting cleanly. break; case DLL_PROCESS_DETACH: // 将一个DLL从进程的地址空间时调用 // The DLL is being unmapped from the process' address space. break; } return (TRUE); // Used only for DLL_PROCESS_ATTACH }
载入卸载库
LoadLibrary、LoadLibraryExA、LoadPackagedLibrary、FreeLibrary、FreeLibraryAndExitThread 函数声明
// 载入库 HMODULE WINAPI LoadLibrary( _In_ LPCTSTR lpFileName ); HMODULE LoadLibraryExA( LPCSTR lpLibFileName, HANDLE hFile, DWORD dwFlags ); // 若要在通用 Windows 平台(UWP)应用中加载 Win32 DLL,需要调用 LoadPackagedLibrary,而不是 LoadLibrary 或 LoadLibraryEx HMODULE LoadPackagedLibrary( LPCWSTR lpwLibFileName, DWORD Reserved ); // 卸载库 BOOL WINAPI FreeLibrary( _In_ HMODULE hModule ); // 卸载库和退出线程 VOID WINAPI FreeLibraryAndExitThread( _In_ HMODULE hModule, _In_ DWORD dwExitCode );
显示地链接到导出符号
GetProcAddress 函数声明
FARPROC GetProcAddress( HMODULE hInstDll, PCSTR pszSymbolName // 只能接受 ANSI 字符串,不能是 Unicode );
DumpBin.exe 查看 DLL 信息
在 VS 的开发人员命令提示符
使用 DumpBin.exe
可查看 DLL 库的导出段(导出的变量、函数、类名的符号)、相对虚拟地址(RVA,relative virtual address)。如:
DUMPBIN -exports D:\mydll.dll
LoadLibrary 与 FreeLibrary 流程图
LoadLibrary 与 FreeLibrary 流程图
LoadLibrary
FreeLibrary
DLL 库的编写(导出一个 DLL 模块)
DLL 库的编写(导出一个 DLL 模块) DLL 头文件
// MyLib.h #ifdef MYLIBAPI // MYLIBAPI 应该在全部 DLL 源文件的 include "Mylib.h" 之前被定义 // 全部函数/变量正在被导出 #else // 这个头文件被一个exe源代码模块包含,意味着全部函数/变量被导入 #define MYLIBAPI extern "C" __declspec(dllimport) #endif // 这里定义任何的数据结构和符号 // 定义导出的变量(避免导出变量) MYLIBAPI int g_nResult; // 定义导出函数原型 MYLIBAPI int Add(int nLeft, int nRight);
DLL 源文件
// MyLibFile1.cpp // 包含标准Windows和C运行时头文件 #include <windows.h> // DLL源码文件导出的函数和变量 #define MYLIBAPI extern "C" __declspec(dllexport) // 包含导出的数据结构、符号、函数、变量 #include "MyLib.h" // 将此DLL源代码文件的代码放在此处 int g_nResult; int Add(int nLeft, int nRight) { g_nResult = nLeft + nRight; return g_nResult; }
DLL 库的使用(运行时动态链接 DLL)
DLL 库的使用(运行时动态链接 DLL)
// A simple program that uses LoadLibrary and // GetProcAddress to access myPuts from Myputs.dll. #include <windows.h> #include <stdio.h> typedef int (__cdecl *MYPROC)(LPWSTR); int main( void ) { HINSTANCE hinstLib; MYPROC ProcAdd; BOOL fFreeResult, fRunTimeLinkSuccess = FALSE; // Get a handle to the DLL module. hinstLib = LoadLibrary(TEXT("MyPuts.dll")); // If the handle is valid, try to get the function address. if (hinstLib != NULL) { ProcAdd = (MYPROC) GetProcAddress(hinstLib, "myPuts"); // If the function address is valid, call the function. if (NULL != ProcAdd) { fRunTimeLinkSuccess = TRUE; (ProcAdd) (L"Message sent to the DLL function\n"); } // Free the DLL module. fFreeResult = FreeLibrary(hinstLib); } // If unable to call the DLL function, use an alternative. if (! fRunTimeLinkSuccess) printf("Message printed from executable\n"); return 0; }
运行库(Runtime Library)
典型程序运行步骤
- 操作系统创建进程,把控制权交给程序的入口(往往是运行库中的某个入口函数)
- 入口函数对运行库和程序运行环境进行初始化(包括堆、I/O、线程、全局变量构造等等)。
- 入口函数初始化后,调用 main 函数,正式开始执行程序主体部分。
- main 函数执行完毕后,返回到入口函数进行清理工作(包括全局变量析构、堆销毁、关闭I/O等),然后进行系统调用结束进程。
一个程序的 I/O 指代程序与外界的交互,包括文件、管程、网络、命令行、信号等。更广义地讲,I/O 指代操作系统理解为 “文件” 的事物。
glibc 入口
_start -> __libc_start_main -> exit -> _exit
其中 main(argc, argv, __environ)
函数在 __libc_start_main
里执行。
MSVC CRT 入口
int mainCRTStartup(void)
执行如下操作:
- 初始化和 OS 版本有关的全局变量。
- 初始化堆。
- 初始化 I/O。
- 获取命令行参数和环境变量。
- 初始化 C 库的一些数据。
- 调用 main 并记录返回值。
- 检查错误并将 main 的返回值返回。
C 语言运行库(CRT)
大致包含如下功能:
- 启动与退出:包括入口函数及入口函数所依赖的其他函数等。
- 标准函数:有 C 语言标准规定的C语言标准库所拥有的函数实现。
- I/O:I/O 功能的封装和实现。
- 堆:堆的封装和实现。
- 语言实现:语言中一些特殊功能的实现。
- 调试:实现调试功能的代码。
C语言标准库(ANSI C)
包含:
- 标准输入输出(stdio.h)
- 文件操作(stdio.h)
- 字符操作(ctype.h)
- 字符串操作(string.h)
- 数学函数(math.h)
- 资源管理(stdlib.h)
- 格式转换(stdlib.h)
- 时间/日期(time.h)
- 断言(assert.h)
- 各种类型上的常数(limits.h & float.h)
- 变长参数(stdarg.h)
- 非局部跳转(setjmp.h)
📚 书籍
huihut/CS-Books:📚 Computer Science Books 计算机技术类书籍 PDF
语言
- 《C++ Primer》
- 《Effective C++》
- 《More Effective C++》
- 《深度探索 C++ 对象模型》
- 《深入理解 C++11》
- 《STL 源码剖析》
算法
- 《剑指 Offer》
- 《编程珠玑》
- 《程序员面试宝典》
系统
- 《深入理解计算机系统》
- 《Windows 核心编程》
- 《Unix 环境高级编程》
网络
- 《Unix 网络编程》
- 《TCP/IP 详解》
其他
- 《程序员的自我修养》
🔱 C/C++ 发展方向
C/C++ 发展方向甚广,包括不限于以下方向, 以下列举一些大厂校招岗位要求。
后台/服务器
【后台开发】
- 编程基本功扎实,掌握 C/C++/JAVA 等开发语言、常用算法和数据结构;
- 熟悉 TCP/UDP 网络协议及相关编程、进程间通讯编程;
- 了解 Python、Shell、Perl 等脚本语言;
- 了解 MYSQL 及 SQL 语言、编程,了解 NoSQL, key-value 存储原理;
- 全面、扎实的软件知识结构,掌握操作系统、软件工程、设计模式、数据结构、数据库系统、网络安全等专业知识;
- 了解分布式系统设计与开发、负载均衡技术,系统容灾设计,高可用系统等知识。
桌面客户端
【PC 客户端开发】
- 计算机软件相关专业本科或以上学历,热爱编程,基础扎实,理解算法和数据结构相关知识;
- 熟悉 windows 操作系统的内存管理、文件系统、进程线程调度;
- 熟悉 MFC/windows 界面实现机制,熟练使用 VC,精通 C/C++,熟练使用 STL,以及 Windows 下网络编程经验;
- 熟练掌握 Windows 客户端开发、调试,有 Windows 应用软件开发经验优先;
- 对于创新及解决具有挑战性的问题充满激情,具有良好的算法基础及系统分析能力。
图形学/游戏/VR/AR
【游戏客户端开发】
- 计算机科学/工程相关专业本科或以上学历,热爱编程,基础扎实,理解算法、数据结构、软件设计相关知识;
- 至少掌握一种游戏开发常用的编程语言,具 C++/C# 编程经验优先;
- 具游戏引擎(如 Unity、Unreal)使用经验者优先;
- 了解某方面的游戏客户端技术(如图形、音频、动画、物理、人工智能、网络同步)者优先考虑;
- 对于创新及解决具有挑战性的问题充满激情,有较强的学习能力、分析及解决问题能力,具备良好的团队合作意识;
- 具阅读英文技术文档能力;
- 热爱游戏。
测试开发
【测试开发】
- 计算机或相关专业本科及以上学历;
- 一至两年的 C/C++/Python 或其他计算机语言的编程经验;
- 具备撰写测试计划、测试用例、以及实现性能和安全等测试的能力;
- 具备实现自动化系统的能力;
- 具备定位调查产品缺陷能力、以及代码级别调试缺陷的能力;
- 工作主动积极,有责任心,具有良好的团队合作精神。
网络安全/逆向
【安全技术】
- 热爱互联网,对操作系统和网络安全有狂热的追求,专业不限;
- 熟悉漏洞挖掘、网络安全攻防技术,了解常见黑客攻击手法;
- 掌握基本开发能力,熟练使用 C/C++ 语言;
- 对数据库、操作系统、网络原理有较好掌握;
- 具有软件逆向,网络安全攻防或安全系统开发经验者优先。
嵌入式/物联网
【嵌入式应用开发】
- 有良好的编程基础,熟练掌握 C/C++ 语言;
- 掌握操作系统、数据结构等软件开发必备知识;
- 具备较强的沟通理解能力及良好的团队合作意识;
- 有 Linux/Android 系统平台的开发经验者优先。
音视频/流媒体/SDK
【音视频编解码】
- 硕士及以上学历,计算机、信号处理、数学、信息类及相关专业和方向;
- 视频编解码基础扎实,熟常用的 HEVC 或 H264,有较好的数字信号处理基础;
- 掌握 C/C++,代码能力强, 熟悉一种汇编语言尤佳;
- 较强的英文文献阅读能力;
- 学习能力强,具有团队协作精神,有较强的抗压能力。
计算机视觉/机器学习
【计算机视觉研究】
- 计算机、应用数学、模式识别、人工智能、自控、统计学、运筹学、生物信息、物理学/量子计算、神经科学、社会学/心理学等专业,图像处理、模式识别、机器学习相关研究方向,本科及以上,博士优先;
- 熟练掌握计算机视觉和图像处理相关的基本算法及应用;
- 较强的算法实现能力,熟练掌握 C/C++ 编程,熟悉 Shell/Python/Matlab 至少一种编程语言;
- 在计算机视觉、模式识别等学术会议或者期刊上发表论文、相关国际比赛获奖、及有相关专利者优先。
💯 复习刷题网站
- cplusplus
- cppreference
- runoob
- leetcode | leetcode-cn
- lintcode
- nowcoder
📝 面试题目经验
- 牛客网 . 2020秋招面经大汇总!(岗位划分)
- 牛客网 . 【备战秋招】2020届秋招备战攻略
- 牛客网 . 2019校招面经大汇总!【每日更新中】
- 牛客网 . 2019校招技术类岗位面经汇总【技术类】
- 牛客网 . 2018校招笔试真题汇总
- 牛客网 . 2017秋季校园招聘笔经面经专题汇总
- 牛客网 . 史上最全2017春招面经大合集!!
- 牛客网 . 面试题干货在此
- 知乎 . 互联网求职路上,你见过哪些写得很好、很用心的面经?最好能分享自己的面经、心路历程。
- 知乎 . 互联网公司最常见的面试算法题有哪些?
- CSDN . 全面整理的C++面试题
- CSDN . 百度研发类面试题(C++方向)
- CSDN . c++常见面试题30道
- CSDN . 腾讯2016实习生面试经验(已经拿到offer)
- cnblogs . C++面试集锦( 面试被问到的问题 )
- cnblogs . C/C++ 笔试、面试题目大汇总
- cnblogs . 常见C++面试题及基本知识点总结(一)
- segmentfault . C++常见面试问题总结
📆 招聘时间岗位
- 牛客网 . 名企校招日程
👍 内推
- Github . CyC2018/Job-Recommend:🔎 互联网内推信息(社招、校招、实习)
- Github . amusi/AI-Job-Recommend:国内公司人工智能方向(含机器学习、深度学习、计算机视觉和自然语言处理)岗位的招聘信息(含全职、实习和校招)
👬 贡献者
🍭 支持赞助
Avalive:一个面部捕捉的虚拟形象扮演软件。
📜 License
本仓库遵循 CC BY-NC-SA 4.0(署名 - 非商业性使用 - 相同方式共享) 协议,转载请注明出处,不得用于商业目的。