在上一篇文章中，我们已经掌握了静态库和动态库的制作与使用。完成链接。但是，如果只掌握这些命令，我们还不能真正理解链接器和操作系统到底完成了什么。为什么分别编译的两个.o文件能够调用彼此的函数？链接器如何知道某个函数的机器指令位于哪里？为什么.o.so和可执行文件都可以采用 ELF 格式？程序尚未运行时，为什么 ELF 文件中已经存在虚拟地址？操作系统执行execve()时，究竟怎样把 ELF 文件

在上一篇 Linux 基础 IO 中，我们已经学习了文件描述符fdopen()read()write()close()和重定向。操作系统会找到对应的文件，并且返回一个文件描述符。读取文件内容。操作系统为什么能够根据文件名找到文件？文件内容存储在磁盘的什么位置？文件的权限、大小、时间等属性保存在哪里？为什么文件描述符和 inode 不是一回事？为什么 Linux 可以将多个磁盘分区统一组织在根目录下

在前面的 Linux 进程控制学习中，我们已经通过 、 和实现了一个简易 Shell。目前，我们的 MiniShell 已经能够完成：例如：但是，如果尝试执行：我们之前的程序就无法正确处理。真正的 Shell 会将写入 ，而不是显示在终端上。这便引出了一个重要问题：程序默认向显示器输出数据，操作系统究竟怎样把这些数据转移到文件中？要回答这个问题，我们首先需要理解 Linux 文件 IO 的底层机制

进程是程序的一次执行实例。Linux 使用描述和管理进程。每个进程都有自己的 PID、地址空间和执行上下文。操作系统通过调度器决定进程什么时候运行。进程可能处于运行、睡眠、停止和僵尸等状态。进程是谁创建出来的？执行完以后又由谁负责回收？如果一个进程想运行另外一个程序，应该怎么办？ls -lShell 会运行ls程序，等待执行结果，再重新显示命令提示符。Shell进程| fork()v创建子进程|

fork();getpid();getppid();一堆Linux命令几个系统调用操作系统如何管理正在运行的程序？冯诺依曼体系↓计算机硬件↓操作系统管理硬件↓操作系统管理程序↓描述进程↓↓组织进程↓调度、切换、创建、退出用户↓应用程序↓C/C++库↓系统调用接口↓│ 操作系统内核 │↓ ↓ ↓CPU 内存 外设也就是常见定义：进程是程序的一次执行实例。或者：进程是正在执行的程序。这两个说法都可以帮

在学习红黑树之前，我们首先需要知道它到底解决了什么问题。4/ \2 6/ \ / \1 3 5 7log₂NO(logN)但是普通二叉搜索树并不会主动维护自己的结构。12345O(N)O(N)所以我们需要一种能够自动控制高度的二叉搜索树。AVL 树是一种解决方法，而红黑树则是另一种非常经典的解决方案。红黑树并不像 AVL 树那样严格要求左右子树高度差不超过 1，而是通过一些颜色规则间接约束树的高度

红黑树为什么能够保持近似平衡？插入以后为什么需要变色和旋转？这一篇正式进入代码实现。1. 红黑树结点2. 左旋与右旋3. BST 插入4. 红黑树插入修复5. Find 查找6. 红黑树合法性验证红黑树的代码虽然看起来比较长，但真正复杂的部分其实只有插入修复。第一阶段：BST 插入第二阶段：新结点染红第三阶段：如果父结点为红，修复红红冲突→ 变色→ 向上继续→ 判断 LL / RR / LR /

左子树中的关键字小于根右子树中的关键字大于根左右子树仍然是二叉搜索树借助这个规则，我们可以根据关键字大小决定向左还是向右查找。但是，普通二叉搜索树有一个明显的问题：它只规定了关键字之间的大小关系，却没有限制树的形状。查找7O(log N)O(N)AVL 树就是为了解决这个问题而出现的。普通二叉搜索树↓树高决定操作效率↓限制左右子树高度差↓引入平衡因子↓按照 BST 规则插入↓沿祖先路径更新平衡因子

按照 BST 规则插入↓沿祖先路径更新平衡因子↓平衡因子为 0：停止平衡因子为 ±1：继续平衡因子为 ±2：旋转真正实现 AVL 树时，难点主要集中在旋转。二叉搜索树的大小关系左孩子指针右孩子指针父指针整棵树的根指针局部子树与上一层的连接结点的平衡因子右单旋左单旋左右双旋右左双旋最后给出一套可以直接在 Linux 环境中编译运行的完整 C++ 实现。假设失衡结点为parent说明 parent 左

在学习普通二叉树时，我们主要关注的是树的结构，以及前序、中序、后序、层序等遍历方式。但普通二叉树有一个问题：结点之间没有统一的大小关系。假设现在要在一棵普通二叉树中查找数字13，除了把整棵树遍历一遍，我们通常没有更好的办法。因为站在某个结点上时，并不知道目标应该在左子树还是右子树。较小的数据放在左边较大的数据放在右边正是这条看起来很简单的规则，让树具备了定向查找、插入和删除的能力。这时树的方向会与