相较于预处理阶段使用的头文件，库文件相对来说就更复杂。链接器是程序编译流程中的关键组件，负责将编译器生成的目标文件、动态库、静态库文件组合为可执行文件或动态库。由于操作系统生态的差异，Windows和Linux的链接器在职责实现、库文件查找机制上存在显著区别。本文将从链接器核心职责出发，详细对比两者的链接过程及库文件（尤其是系统调用库和C库）的查找逻辑。

1.Windows,Linux的字符编码方式

• UTF-8：Linux统一
• GBK：Windows应用层软件、文本文件、ying'yong'ceng程序内部文本数据等默认字符编码方式
• UTF-16：Windows内核（包括Win32 API）。

源码文件以什么方式编码，编译后得到的可执行文件里的常量字符串就以什么方式编码。

2.git的使用

1.推送之前必须要拉取远程仓库。这是为了不错过远程项目的最新变化。
2.提交(commit)一定要在visual studio中完成否则git commit .会把整个项目都暂存破坏了只上传源码的gitignore规则。在VS中提交完成后，使用git push origin master推送。

C++ STL中的栈与队列：核心原理与实战应用指南

在C++标准模板库（STL）中，stack（栈）和queue（队列）是两个重要的容器适配器，它们通过封装底层容器（默认使用deque）实现了特定的数据操作逻辑。本文将深入探讨它们的设计原理、常用操作及典型应用场景，帮助开发者快速掌握其核心用法。

一、栈（stack）：后进先出的数据管理
核心特性与初始化

栈遵循后进先出（LIFO）原则，仅允许在栈顶进行插入和删除操作。其底层通常基于deque或list容器实现。

include <stack>

std::stack<int> s;  // 默认基于deque的整型栈

常用操作及示例

方法         功能描述 示例代码

push(x) 将元素x压入栈顶 s.push(10);
pop() 移除栈顶元素（不返回值） s.pop();
top() 返回栈顶元素的引用（需非空检查） int val = s.top();
empty() 判断栈是否为空（返回布尔值） if (s.empty()) {...}
size() 返回栈中元素数量 int cnt = s.size();

操作示例：遍历栈并输出所有元素

std::stack<int> s;
s.push(1); s.push(2); s.push(3);
while (!s.empty()) {
    std::cout << s.top() << " ";  // 输出：3 2 1
    s.pop();

典型应用场景

括号匹配：通过栈结构检测表达式中的括号嵌套是否正确

深度优先搜索（DFS）：递归算法中隐式使用栈管理访问路径

撤销操作：文本编辑器中按顺序记录操作步骤

二、队列（queue）：先进先出的任务调度
核心特性与初始化

队列遵循先进先出（FIFO）原则，元素在队尾插入，队首删除。底层同样基于deque或list实现。

include <queue>

std::queue<std::string> q;  // 字符串队列

常用操作及示例

方法         功能描述 示例代码

push(x) 将元素x插入队尾 q.push("task1");
pop() 移除队首元素（不返回值） q.pop();
front() 返回队首元素的引用（需非空检查） auto task = q.front();
back() 返回队尾元素的引用 auto last = q.back();
empty() 判断队列是否空 if (q.empty()) {...}
size() 返回队列元素数量 int len = q.size();

操作示例：处理任务队列

std::queue<int> q;
q.push(10); q.push(20); q.push(30);
while (!q.empty()) {
    std::cout << q.front() << " ";  // 输出：10 20 30
    q.pop();

典型应用场景

广度优先搜索（BFS）：按层次遍历树或图结构

消息队列：异步处理系统中的任务缓冲

打印任务调度：保证文档按提交顺序打印

三、进阶扩展：优先队列（priority_queue）
优先队列是队列的变种，元素按优先级排序（默认最大堆）。常用于任务调度系统：
include

// 小顶堆示例
std::priority_queue<int, std::vector, std::greater> pq;
pq.push(3); pq.push(1); pq.push(4);
pq.top(); // 返回1（当前最小元素）

一、插入排序

1.直接插入排序与折半插入排序。

　　1.1步骤：
　　　(1)对于第i个元素，先用临时变量保存之，然后在1 ~ i-1的有序序列中找到其该插入的位置k。
　　　(2)将k到i-1的所有元素后移一位，导致k被腾出。
　　　(3)将临时变量保存的i号元素赋值到k位置。
　　*对于折半插入排序，因为i前必有序，找插入位置可使用折半查找。注意mid与临时变量相等时（即序列有重复元素），让low = mid + 1而非直接结束，最后将low ~ i-1或high+1 ~ i-1的元素往后移动一位腾出位置供插入。k=low。这样做是为了保证稳定性。考虑abcccdec，最后一个c为待插入前面的元素，mid=4与临时变量匹配就认为找到了k的话，在5的位置还有一个c就会被移动，就不稳定。
　　*对于直接插入排序，步骤(1)的找位置与步骤(2)同时进行。
　　*时间复杂度为O(n^2)。空间复杂度为O(1)。稳定。

2.希尔排序/缩小增量排序

　　2.1思想：
　　　以逐渐减小为1的增量（步长）划分子表，一个增量d可以把原序列化为d个子表，对每个子表插入排序即可。增量为1就是直接插入排序了。
　　*时间复杂度不明。空间复杂度为O(1)。不稳定。

二、交换排序

1.冒泡排序

　　*对于求冒泡的趟数的，把每一趟结束的序列写出来不要偷懒。最后千万别忘了得到一个排完序的序列之后实际上程序还要再跑一趟从而发现没有进行任何交换才会结束。
　　*时间复杂度为O(n^2)。空间复杂度为O(1)。稳定。

2.快速排序

　　*思想：移走首元素留下空位，比首元素（枢轴pivot）小的移到前面空位从而在后面产生空位，大的移到后面空位从而在前面产生空位，两者交替，最终空的就是存放首元素的位置。
　　*画二叉排序树的心算方法：把序列写出来，把首元素（枢轴pivot）写到序列下面，序列与其下的pivot充当一个结点。左手手指为low指针，右手笔为high指针，分别指向序列首尾。先low不动，high从当前位置的前一位开始判断是否比pivot小，不是则写入到该结点右分支的最左，high往左移动并继续判断，直到找到并写入到该结点左分支的最右或high与low相等则表明该结点成功生成子结点了。若结束原因非后者，则此次是保持high不变，low从其后一位开始移动直到low指向的大于pivot从而写入到high的位置或low与high相等。两者如此交替重复几轮终会导致low=high。此时两个子结点就生成完毕。然后对两个子结点的序列进行同样的操作。（详见王道p351第10题）
　　*时间复杂度：最好时树高logn，树的每一层low与high都对整个序列一个个的遍历，为n。故最好时间复杂度O(nlogn)。最坏树是单支树，O(n^2)。快速排序发生最好的情况的概率更大，故平均时间复杂度O(nlogn)。
　　*空间复杂度：即同时处于栈段的函数栈的个数，即树的树高，因此最好O(logn)最坏O(n)，平均O(logn)。
　　*定下一个序列的枢轴最终所在的位置需要比较的次数就是该序列长度-1。因为所有的比较无非就是枢轴元素与其他所有元素的比较。

三、选择排序

1.简单选择排序

　　*思想：每次从无序序列中选出最大/最小的元素交换到有序序列前/后一位。

2.堆排序

　　*堆即顺序存储的，根与其两个孩子有大小关系的完全二叉树。若堆有n个元素，则非叶结点的数量为⌊n/2⌋个。
　　*堆分为大根堆与小根堆。
　　步骤：
　　a.先将序列建堆。方法是序列前⌊n/2⌋个元素调用HeadAdjust函数。该函数针对传入其的根结点，暂存根结点并产生k与i双指针，其中k永远是i的双亲。在一个i每次乘2（指向其左孩子）的循环中，先比较左右孩子孰大孰小以确定i是否+1成为k的右孩子，在比较i与k孰大孰小决定是否让i移动到k的位置上，若无需移动则表明当前k结点为根的树符合堆的定义了，否则接下来k=i调整其子树成为堆。
　　b.建立n-1次的循环。这里与选择排序一致，因为堆顶一定是最大/小的元素，省去了选择排序遍历的麻烦。但每次将堆顶元素交换到后面都要调用HeadAdjust函数调整前面。
　　*建堆时间复杂度O(n)，堆排序时间复杂度O(nlogn)，总体O(nlogn)，空间复杂度O(1)。不稳定。
　　*堆的插入操作：新结点放序列末尾，然后向上调整。时间复杂度O(logn)。
　　*堆的删除操作：删除结点，以序列末尾元素代替。然后向下调整。时间复杂度O(logn)。
　　*题目若要求堆排序、堆插入或堆删除的比较次数，对每个结点，先比较其两个子结点的大小，选出有资格与该结点比较的子结点与该结点比较。子结点若不为叶结点则继续往下记录比较次数。
　　*题目若要求堆排序、堆插入或堆删除的交换次数，对每个结点，若其子结点移动到该结点的位置就算“交换”，即使实际代码中子结点并没有被该结点赋值。

四、归并排序

　　1.思想（以排成从小到大的序列为例）：
　　*全局建立一个辅助数组B，长度与序列长度相同。（因为首位弃用故长度为元素个数+1）
　　*函数Merge:传入待排序数组A，以及low,high,mid。左半部分数组为A[low~mid]，右半部分数组为A[mid+1~high]，两个子数组都有序。将所有这些元素通通移动到B中同下标的位置。然后设置三指针i,j,k。i为B中左半部分数组的移动索引，j为B中右半部分数组的移动索引，k为A的移动索引。循环比较B[i]与B[j]，谁小谁移到B[k]（相等则先把左子数列中的移到A保证稳定性），A[i]移走i++，A[j]移走j++，k不管谁移走都要加1。最终因为i与j的任何一个出界退出循环。最后再将没有移动完的B的子数组移动到A剩余位置。
　　*函数MergeSort:利用递归，递归结束条件是传入该层递归函数的low与high相等，否则产生变量mid=(low+high)/2，以low到mid调用他自己，再以mid+1到high调用他自己。最后调用Merge将low到high中的序列排有序。

2.排序趟数取决于树高，O(logn)，每趟O(n)，时间复杂度O(nlogn)，空间复杂度O(n)，稳定。

五、基数排序

　　1.思想：从关键字本身的信息出发，设关键字为r进制，位数为d位，个数为n个。设置r个队列，将最低位，放进相应队列（分配），再将各个队列的关键字保持先后顺序的拿出来存进链表（收集），再到下一位直至最高位。从高位出发到低位亦可行。
　　2.共d趟，每趟分配O(n)，收集O(r)，时间复杂度O(d(n+r))，空间复杂度O(r)。