环形数组：打破数组的线性限制

为什么需要环形数组？

传统数组在头部插入/删除元素的时间复杂度是O(N)，因为需要进行数据搬移。环形数组通过巧妙的索引计算，实现了在O(1)时间内完成头尾操作。

环形数组的核心原理

环形数组在逻辑上将线性数组首尾相连，通过取模运算实现循环访问：

#include <iostream>
#include <vector>
using namespace std;

// 基础环形数组演示
void basicCycleArrayDemo() {
    vector<int> arr = {1, 2, 3, 4, 5};
    int i = 0;
    
    // 无限循环遍历，演示环形效果
    for (int count = 0; count < 10; count++) {
        cout << arr[i] << " ";
        i = (i + 1) % arr.size();  // 关键：取模运算实现环形
    }
    // 输出: 1 2 3 4 5 1 2 3 4 5
}

环形数组的指针管理

环形数组通过维护两个指针来实现高效操作：

  • start：指向第一个有效元素的索引
  • end：指向最后一个有效元素的下一个位置索引

这种左闭右开区间[start, end)的设计避免了边界处理的复杂性。

完整环形数组实现

#include <iostream>
#include <stdexcept>
#include <vector>

template<typename T>
class CycleArray {
private:
    std::vector<T> arr;
    int start;    // 指向第一个有效元素
    int end;      // 指向最后一个有效元素的下一个位置
    int count;    // 当前元素数量

    // 自动扩缩容
    void resize(int newSize) {
        std::vector<T> newArr(newSize);
        // 按顺序复制元素到新数组
        for (int i = 0; i < count; ++i) {
            newArr[i] = arr[(start + i) % arr.size()];
        }
        arr = std::move(newArr);
        start = 0;
        end = count;
    }

public:
    CycleArray() : CycleArray(1) {}
    
    explicit CycleArray(int size) 
        : arr(size), start(0), end(0), count(0) {}

    // 头部添加元素 - O(1)
    void addFirst(const T &val) {
        if (isFull()) {
            resize(arr.size() * 2);
        }
        // 关键：先左移start，再赋值
        start = (start - 1 + arr.size()) % arr.size();
        arr[start] = val;
        count++;
    }

    // 尾部添加元素 - O(1)
    void addLast(const T &val) {
        if (isFull()) {
            resize(arr.size() * 2);
        }
        // 关键：先赋值，再右移end
        arr[end] = val;
        end = (end + 1) % arr.size();
        count++;
    }

    // 头部删除元素 - O(1)
    void removeFirst() {
        if (isEmpty()) {
            throw std::runtime_error("Array is empty");
        }
        start = (start + 1) % arr.size();
        count--;
        
        // 缩容：元素数量降到容量1/4时缩容一半
        if (count > 0 && count == arr.size() / 4) {
            resize(arr.size() / 2);
        }
    }

    // 尾部删除元素 - O(1)
    void removeLast() {
        if (isEmpty()) {
            throw std::runtime_error("Array is empty");
        }
        end = (end - 1 + arr.size()) % arr.size();
        count--;
        
        if (count > 0 && count == arr.size() / 4) {
            resize(arr.size() / 2);
        }
    }

    // 随机访问 - O(1)
    T get(int index) const {
        if (index < 0 || index >= count) {
            throw std::out_of_range("Index out of range");
        }
        return arr[(start + index) % arr.size()];
    }

    // 工具方法
    bool isFull() const { return count == arr.size(); }
    bool isEmpty() const { return count == 0; }
    int size() const { return count; }
    int capacity() const { return arr.size(); }

    // 调试输出
    void display() const {
        std::cout << "Size: " << count << ", Capacity: " << arr.size() 
                  << ", Start: " << start << ", End: " << end << std::endl;
        std::cout << "Elements: [";
        for (int i = 0; i < count; i++) {
            std::cout << get(i);
            if (i < count - 1) std::cout << ", ";
        }
        std::cout << "]" << std::endl;
        
        std::cout << "Raw array: [";
        for (int i = 0; i < arr.size(); i++) {
            std::cout << arr[i];
            if (i < arr.size() - 1) std::cout << ", ";
        }
        std::cout << "]" << std::endl << std::endl;
    }
};

环形数组测试示例

void testCycleArray() {
    CycleArray<int> arr(3);
    
    cout << "=== 环形数组测试 ===" << endl;
    
    cout << "1. 头部插入测试:" << endl;
    arr.addFirst(3);
    arr.addFirst(2);
    arr.addFirst(1);
    arr.display();
    
    cout << "2. 尾部插入触发扩容:" << endl;
    arr.addLast(4);  // 触发扩容
    arr.display();
    
    cout << "3. 混合操作:" << endl;
    arr.addFirst(0);
    arr.addLast(5);
    arr.display();
    
    cout << "4. 删除操作:" << endl;
    arr.removeFirst();
    arr.removeLast();
    arr.display();
    
    cout << "5. 随机访问测试:" << endl;
    for (int i = 0; i < arr.size(); i++) {
        cout << "arr[" << i << "] = " << arr.get(i) << endl;
    }
}

位图：极致的空间效率

为什么需要位图？

在算法中，我们经常需要记录大量布尔状态：

// 传统布尔数组 - 每个元素占用1字节(8bit)
bool visited[1000];  
visited[10] = true;  // 浪费了7/8的空间！

位图通过每个比特位存储一个布尔值，将空间效率提升8倍！

位图的核心原理

位图使用整数数组作为底层存储，通过位运算精确控制每个比特位：

// 计算第k个比特位的位置：
int wordIndex = k / 64;    // 在哪个long元素中
int bitOffset = k % 64;    // 在long中的哪个比特位

// 设置第k位为1：
words[wordIndex] |= (1ULL << bitOffset);

// 检查第k位：
bool isSet = (words[wordIndex] & (1ULL << bitOffset)) != 0;

完整位图实现

#include <iostream>
#include <vector>
#include <stdexcept>
using namespace std;

class BitSet {
private:
    vector<unsigned long long> words;
    int size;  // 位图能够表示的最大索引+1

public:
    BitSet(int size) : size(size) {
        // 计算需要的long long数量
        int arraySize = (size + 63) / 64;  // 向上取整
        words.resize(arraySize, 0);
    }

    // 设置指定位为1
    void set(int bitIndex) {
        checkIndex(bitIndex);
        int wordIndex = bitIndex >> 6;  // 等价于 bitIndex / 64
        int bitOffset = bitIndex & 63;  // 等价于 bitIndex % 64
        words[wordIndex] |= (1ULL << bitOffset);
    }

    // 清除指定位（设为0）
    void clear(int bitIndex) {
        checkIndex(bitIndex);
        int wordIndex = bitIndex >> 6;
        int bitOffset = bitIndex & 63;
        words[wordIndex] &= ~(1ULL << bitOffset);
    }

    // 获取指定位的值
    bool get(int bitIndex) const {
        checkIndex(bitIndex);
        int wordIndex = bitIndex >> 6;
        int bitOffset = bitIndex & 63;
        return (words[wordIndex] & (1ULL << bitOffset)) != 0;
    }

    // 位图大小
    int getSize() const { return size; }

    // 统计设置为1的位数（Population Count）
    int count() const {
        int total = 0;
        for (unsigned long long word : words) {
            // 使用内置函数或手动计算
            total += __builtin_popcountll(word);
        }
        return total;
    }

    // 位图交集
    BitSet intersection(const BitSet& other) const {
        if (size != other.size) {
            throw invalid_argument("BitSet sizes must match");
        }
        BitSet result(size);
        for (int i = 0; i < words.size(); i++) {
            result.words[i] = words[i] & other.words[i];
        }
        return result;
    }

    // 位图并集
    BitSet unionWith(const BitSet& other) const {
        if (size != other.size) {
            throw invalid_argument("BitSet sizes must match");
        }
        BitSet result(size);
        for (int i = 0; i < words.size(); i++) {
            result.words[i] = words[i] | other.words[i];
        }
        return result;
    }

    // 调试输出
    void display() const {
        cout << "BitSet (size=" << size << ", count=" << count() << "): ";
        for (int i = 0; i < min(size, 100); i++) {  // 只显示前100位
            cout << (get(i) ? '1' : '0');
            if ((i + 1) % 8 == 0) cout << " ";  // 每8位加空格
        }
        if (size > 100) cout << "...";
        cout << endl;
    }

private:
    void checkIndex(int bitIndex) const {
        if (bitIndex < 0 || bitIndex >= size) {
            throw out_of_range("Bit index out of range: " + to_string(bitIndex));
        }
    }
};

位运算优化技巧

// 传统运算 vs 位运算优化
int wordIndex = bitIndex / 64;      // 传统除法
int wordIndex = bitIndex >> 6;      // 优化：右移6位 (2^6=64)

int bitOffset = bitIndex % 64;      // 传统取模  
int bitOffset = bitIndex & 63;      // 优化：与运算 (64-1=63)

位图测试示例

void testBitSet() {
    cout << "=== 位图测试 ===" << endl;
    
    BitSet bitSet(100);
    
    // 设置一些位
    bitSet.set(10);
    bitSet.set(20);
    bitSet.set(30);
    bitSet.set(95);  // 测试边界
    
    cout << "初始位图:" << endl;
    bitSet.display();
    
    cout << "\n测试获取操作:" << endl;
    cout << "bitSet.get(10): " << bitSet.get(10) << endl;  // 1
    cout << "bitSet.get(15): " << bitSet.get(15) << endl;  // 0
    
    cout << "\n测试清除操作:" << endl;
    bitSet.clear(20);
    cout << "清除第20位后:" << endl;
    bitSet.display();
    
    cout << "\n测试集合操作:" << endl;
    BitSet other(100);
    other.set(10);
    other.set(25);
    other.set(35);
    
    BitSet intersection = bitSet.intersection(other);
    cout << "交集:" << endl;
    intersection.display();
    
    // 内存使用对比
    cout << "\n=== 内存使用对比 ===" << endl;
    int elementCount = 1000000;  // 100万元素
    
    // 布尔数组内存使用
    size_t boolArrayMemory = elementCount * sizeof(bool);  // 约1MB
    
    // 位图内存使用  
    size_t bitSetMemory = (elementCount + 63) / 64 * sizeof(unsigned long long);  // 约125KB
    
    cout << "100万元素的布尔数组: " << boolArrayMemory / 1024 << " KB" << endl;
    cout << "100万元素的位图: " << bitSetMemory / 1024 << " KB" << endl;
    cout << "空间节省: " << (1 - (double)bitSetMemory / boolArrayMemory) * 100 << "%" << endl;
}

实际应用场景

环形数组的应用

  1. 循环缓冲区：音频处理、网络数据包缓冲
  2. 队列实现：固定大小的循环队列
  3. 滑动窗口：实时数据流处理
  4. 游戏开发：循环动画帧、环形物品栏
// 基于环形数组的固定大小队列
template<typename T>
class CircularQueue {
private:
    CycleArray<T> array;
    
public:
    CircularQueue(int capacity) : array(capacity) {}
    
    void enqueue(T value) { array.addLast(value); }
    T dequeue() { 
        T value = array.get(0);
        array.removeFirst();
        return value;
    }
    bool isFull() { return array.isFull(); }
    bool isEmpty() { return array.isEmpty(); }
};

位图的应用

  1. 大规模布尔状态记录：网页爬虫的已访问URL记录
  2. 集合运算：快速求交集、并集
  3. 权限系统：每个比特位代表一个权限
  4. 布隆过滤器：概率性数据结构的基础
  5. 内存管理：操作系统中的空闲内存块管理
// 使用位图实现简单的权限系统
class PermissionSystem {
private:
    BitSet permissions;
    
public:
    enum Permission {
        READ = 0,
        WRITE = 1, 
        EXECUTE = 2,
        DELETE = 3,
        // ... 更多权限
    };
    
    PermissionSystem() : permissions(64) {}  // 支持64种权限
    
    void grantPermission(int userId, Permission perm) {
        permissions.set(userId * 8 + perm);
    }
    
    bool checkPermission(int userId, Permission perm) {
        return permissions.get(userId * 8 + perm);
    }
};

性能对比分析

时间复杂度对比

操作 普通数组 环形数组 位图
头部插入 O(N) O(1) -
尾部插入 O(1)
随机访问 O(1)
布尔状态设置 -
集合运算 O(N/64)

空间复杂度对比

对于N个布尔值：

  • 布尔数组：N字节
  • 位图：N/8字节（节省87.5%空间）

总结

环形数组和位图都是通过巧妙的设计在特定场景下提供极致性能的数据结构：

环形数组的核心价值：

  • 在O(1)时间内完成头尾操作
  • 逻辑上的环形结构，物理上的连续存储
  • 适合需要频繁头尾操作的场景

位图的核心价值：

  • 极致的空间效率，8倍于布尔数组
  • 快速的位级操作和集合运算
  • 适合大规模布尔状态记录

这两种数据结构体现了算法设计中重要的思想：

  • 空间换时间（环形数组的索引计算）
  • 时间换空间（位图的压缩存储）
  • 抽象与封装（隐藏复杂实现，提供简洁接口）

掌握这些底层数据结构不仅有助于解决具体的算法问题，更能培养深入思考系统优化的能力。在实际开发中，当遇到性能瓶颈时，考虑使用这些高效数据结构往往能带来显著的改进。

  1. 评测队列
  2. 服务状态
  3. 兼容模式
  4. 主题
  2. 豫ICP备2025149381号
  3. Powered by Hydro v5.0.0-beta.12 Community