位图结构

蔚落 2023-07-10 00:54 2阅读 0赞

### 文章目录 ###

*   *   *  简介
         *  实现原理
         *  位运算的实现
         *  实现

### 简介 ###

*  位图结构实现是参考\[邓俊辉\]数据结构习题解析第三版
    
     *  位图是一种特殊的序列结构，可以动态表示一组无符号整数构成的集合。其长度无限，且其中每个元素的取值都是布尔值(初始false)
        
         *  bool test(int k) 整数k是否存在
         *  void set(int k) 整数k放入集合
         *  void clear(int k) 删除整数k
 *  本文用来记录和学习

### 实现原理 ###

*  利用存储char的向量实现
    
     *  整数k对应的序是 k >> 3 (char一个字节8比特位)
     *  余数(k && 0x07) n 由当前元素的第n个元素置为1来表示

### 位运算的实现 ###

*  余数部分设计到位运算下面解释下具体的过程
    
     *  余数范围是\[0，7\]，k & 0000 0111 可以等到
     *  0x07 (2进制)00000111 7(10进制)
     *  (0x80 >> (k & 0x07)) 将余数位对应的比特位置为掩码
        
         *  0x80 (二进制)10000000 (10进制) 128
     *  M\[k>> 3\] |= (0x80 >> (k & 0x07)); 当前字节中余数对应的比特位一定是1

### 实现 ###

class Bitmap {
    private:
        char *M; // 比特图所存放的空间
        int N; // 容量为N*sizeof(char)*8 容量
    protected:
        void init(int n) {
            // 全入除法(ceil) 向量的容量
            N = (n + 7) / 8;
    
            // 初始化向量
            M = new char[N];
    
            //
            memset(M, 0, N);
        }
    
    public:
        // 构造函数
        Bitmap(int n = 8) { init(n); }
    
        // 按照指定规模,从指定文件中读取Bitmap
        Bitmap(char *file, int n = 8) {
            // 初始化
            init(n);
    
            // 读取文件
            FILE *fp = fopen(file, "r");
            fread(M, sizeof(char), N, fp);
            fclose(fp);
        }
    
        // 析构释放比特图空间
        ~Bitmap() {
            delete[] M;
            M = NULL;
        }
    
        //将位图整体导出至指定空间
        void dump(char *file) {
            FILE *fp = fopen(file, "w");
            fwrite(M, sizeof(char), N, fp);
            fclose(fp);
        }
    
        // 将第k位设置为true(将整数k加入当前集合)
        void set(int k) {
            // 查看是否扩容
            expand(k);
    
            // 在向量中的序
            int index = k >> 3;
    				
            M[index] |= (0x80 >> (k & 0x07));
        }
    
    // 将第k位设置为false(将整数k加入当前集合)
        void clear(int k) {
            // 扩容
            expand(k);
    
            int index = k >> 3;
            M[index] &= ~(0x80 >> (k & 0x07));
        }
    
        // 测试k是不是存在
        bool test(int k) {
            expand(k);
            int index = k >> 3;
    
            return M[index] & (0x80 >> (k & 0x07));
        }
    
        // 扩容
        void expand(int k) {
            // 还在界内
            if (k < 8 * N) {
                return;
            }
    
            int oldN = N;
            char *oldM = M;
    
            // 加倍扩容
            init(2 * k);
    
            // 复制
            memcpy(M, oldM, oldN);
        }
    
        // 将前n位转换成字符串 （n是指比特位）
        char *bits2string(int n) {
            // 从0开始, 所以需要检查下n-1是否超过了容量
            expand(n - 1);
    
            char *str = new char[n + 1];
            str[n] = '\0';
    
            for (int i = 0; i < n; ++i) {
                str[i] = test(i) ? '1' : '0';
            }
    
            return str;
        }
    };