0001 class Bitmap { //位图Bitmap类 0002 private: 0003 unsigned char* M; 0004 Rank N, _sz; //位图空间M[],N*sizeof(char)*8个比特中含_sz个有效位 0005 protected: 0006 void init( Rank n ) 0007 { M = new unsigned char[N = ( n + 7 ) / 8]; memset( M, 0, N ); _sz = 0; } 0008 public: 0009 Bitmap( Rank n = 8 ) { init( n ); } //按指定容量创建位图(为测试暂时选用较小的默认值) 0010 Bitmap( char* file, Rank n = 8 ) { //按指定或默认规模,从指定文件中读取位图 0011 init( n ); 0012 FILE* fp = fopen( file, "r" ); fread( M, sizeof( char ), N, fp ); fclose( fp ); 0013 for ( Rank k = 0, _sz = 0; k < n; k++ ) _sz += test(k); 0014 } 0015 ~Bitmap() { delete[] M; M = NULL; _sz = 0; } //析构时释放位图空间 0016 0017 Rank size() { return _sz; } 0018 void reset() { memset( M, 0, N ); _sz = 0; } 0019 void set ( Rank k ) { if ( test(k) ) return; expand( k ); _sz++; M[k >> 3] |= ( 0x80 >> ( k & 0x07 ) ); } 0020 void clear ( Rank k ) { if (!test(k) ) return; expand( k ); _sz--; M[k >> 3] &= ~ ( 0x80 >> ( k & 0x07 ) ); } 0021 bool test ( Rank k ) { expand( k ); return M[k >> 3] & ( 0x80 >> ( k & 0x07 ) ); } 0022 0023 void dump( char* file ) //将位图整体导出至指定的文件,以便对此后的新位图批量初始化 0024 { FILE* fp = fopen( file, "w" ); fwrite( M, sizeof ( char ), N, fp ); fclose( fp ); } 0025 char* bits2string( Rank n ) { //将前n位转换为字符串—— 0026 expand( n - 1 ); //此时可能被访问的最高位为bitmap[n - 1] 0027 char* s = new char[n + 1]; s[n] = '\0'; //字符串所占空间,由上层调用者负责释放 0028 for ( Rank i = 0; i < n; i++ ) s[i] = test( i ) ? '1' : '0'; 0029 return s; //返回字符串位置 0030 } 0031 void expand( Rank k ) { //若被访问的Bitmap[k]已出界,则需扩容 0032 if ( k < 8 * N ) return; //仍在界内,无需扩容 0033 Rank oldN = N; unsigned char* oldM = M; 0034 init( 2 * k ); //与向量类似,加倍策略 0035 memcpy_s( M, N, oldM, oldN ); 0036 delete[] oldM; //原数据转移至新空间 0037 } 0038 };