C++位运算与字符串操作技巧：STL库用法与算法基础

文档中包含了C++中位运算的基本方法、字符串操作的相关函数以及STL中优先队列的使用技巧，同时还涉及了数据结构的基础知识。" 知识点一: C++位运算方法 在C++中，位运算是一种直接对整数的二进制位进行操作的方法，具有非常高的效率。以下是C++中主要的位运算符及其功能： 1. 按位与（AND）运算符 '&' - 功能：只有当两个二进制位都为1时，结果才为1。 - 示例：a & b 2. 按位或（OR）运算符 '|' - 功能：只要有一个二进制位为1，结果就为1。 - 示例：a | b 3. 按位异或（XOR）运算符 'ˆ' - 功能：只有当两个二进制位不同时，结果才为1（即一个为0，一个为1）。 - 示例：a ˆ b 4. 按位取反（NOT）运算符 '˜' - 功能：将所有的二进制位翻转，1变为0，0变为1。 - 示例：˜a 5. 左移运算符（Left Shift）'<<' - 功能：将二进制位向左移动指定的位数，在右侧填充0。 - 示例：a << n，相当于a乘以2的n次方。 6. 右移运算符（Right Shift）'>>' - 功能：将二进制位向右移动指定的位数，对于无符号整型，左侧填充0；对于有符号整型，则依据符号位填充（即算术右移）。 - 示例：a >> n，相当于a整除2的n次方。 技巧和常见用途： - 检查奇偶性：使用 a & 1 来检查整数a是奇数还是偶数。 - 交换两个数：使用异或运算可以实现不借助临时变量的交换，如：a = a ^ b; b = a ^ b; a = a ^ b; - 位掩码操作：利用位运算可以创建或检查位掩码，例如在“生命游戏”中，可以利用位运算控制细胞的生死状态。 知识点二: 字符串操作 C++中的字符串操作是程序设计中常用的基础操作，主要包含以下函数： 1. string.find(string a, pos) - 功能：查找子字符串a，从指定位置pos开始，默认为0，未找到返回string.npos。 2. string.length() - 功能：返回字符串的长度。 3. string.substr(int start, int length) - 功能：返回从指定位置start开始，长度为length的子字符串。 4. string.resize(int) - 功能：调整字符串的大小，常用于与scanf等函数配合使用，以便存储输入的数据。 5. to_string(int) - 功能：将整数转换为字符串。 知识点三: STL优先队列 STL中的优先队列是一种容器适配器，其行为类似于队列，但元素的添加和删除基于优先级。优先队列默认使用最大堆实现，因此最大的元素总是位于队列的前面。以下为优先队列的使用方法： 1. 定义优先队列： - 默认情况下，优先队列是最大堆，即优先级最高的是最大的元素。 ```cpp #include <queue> std::priority_queue<int> pq; ``` 2. 自定义优先队列比较方式： - 可以通过提供自定义比较函数或类来自定义优先级的顺序。 ```cpp #include <queue> bool myCompare(int a, int b) { return a > b; // 小顶堆 } std::priority_queue<int, std::vector<int>, decltype(myCompare)*> pq(myCompare); ``` 3. 优先队列操作： - push()：添加元素到优先队列。 - pop()：移除优先队列中优先级最高的元素。 - top() 或 front()：获取优先队列中优先级最高的元素。 知识点四: 数据结构基础 数据结构是存储、组织数据的方式，以便于数据的操作。常见的数据结构包括数组、链表、栈、队列、树、图等。在机试或编程竞赛中，理解并熟练使用这些数据结构是解决问题的基础。 1. 数组：线性存储结构，通过索引快速访问元素，但在插入和删除操作中效率较低。 2. 链表：由节点组成，每个节点包含数据部分和指向下一个节点的指针。链表便于插入和删除，但访问元素速度较慢。 3. 栈（Stack）：后进先出（LIFO）的数据结构，只有栈顶元素可被访问。 4. 队列（Queue）：先进先出（FIFO）的数据结构，允许在队尾插入元素，在队首移除元素。 5. 树（Tree）：非线性数据结构，由节点和边组成，其中有一个节点称为根节点，没有父节点的节点称为叶节点。 6. 图（Graph）：由顶点（节点）和边组成的非线性数据结构，用于表示元素间的复杂关系。 通过掌握以上知识点，可以为进行高效且复杂的算法设计和问题解决打下坚实的基础，尤其是在需要使用C++语言和STL库的场景中。