位图（Bitmap）是一种数据结构，它使用位（bit）来表示信息，通常用来表示一组元素的集合。在位图中，每个位对应集合中的一个元素，如果位的值为1，则表示该元素存在或被选中；如果位的值为0，则表示该元素不存在或未被选中。位图因其高效的内存使用和快速的查找、插入、删除操作而广泛应用于各种场景。
位图的特点：
- **内存效率**：位图使用单个位来表示元素的存在或不存在，因此对于大型数据集，位图可以非常节省内存。
- **快速操作**：位图支持快速的查找、插入和删除操作，因为这些操作可以简化为位操作。
位图算法示例：
假设我们有一个班级，有30个学生，我们想用位图来跟踪哪些学生出席了课程。我们可以用一个30位的位图来表示，每位对应一个学生，1表示出席，0表示缺席。初始化位图：
```cpp
#include <vector>
#include <iostream>
const int STUDENTS = 30; // 学生数量
std::vector<bool> attendanceMap(STUDENTS, 0); // 初始化位图，所有学生默认为缺席
```标记学生出席：
```cpp
void markAttendance(int studentId) {
if (studentId >= 0 && studentId < STUDENTS) {
attendanceMap[studentId] = true; // 将对应位置为1
}
}
```检查学生是否出席：
```cpp
bool checkAttendance(int studentId) {
if (studentId >= 0 && studentId < STUDENTS) {
return attendanceMap[studentId]; // 返回该位的值
}
return false;
}
```打印出席情况：
```cpp
void printAttendance() {
for (int i = 0; i < STUDENTS; ++i) {
std::cout << (attendanceMap[i] ? "Present " : "Absent ");
}
std::cout << std::endl;
}
```主函数示例：
```cpp
int main() {
markAttendance(5); // 学生5出席
markAttendance(15); // 学生15出席
printAttendance(); // 打印所有学生的出席情况
std::cout << "Student 5 is " << (checkAttendance(5) ? "Present" : "Absent") << std::endl;
std::cout << "Student 10 is " << (checkAttendance(10) ? "Present" : "Absent") << std::endl;
return 0;
}
```位图的应用场景：
1. **内存映射**：操作系统使用位图来跟踪内存页的使用情况。
2. **图形和图像处理**：位图用于表示图像的像素，每个像素用一个或多个位来表示颜色。
3. **数据压缩**：位图可以用于表示数据的压缩信息，如霍夫曼编码树的节点存在性。
4. **集合操作**：位图可以用于实现集合的并集、交集和差集等操作。
位图是一种简单但强大的数据结构，通过使用位操作，它提供了一种高效的方式来处理大量数据。在C++中，可以使用`std::vector<bool>`或`std::bitset`来实现位图，或者使用裸机位数组来获得更底层的控制。