비트 맵 데이터 구조

2000 단어 데이터 구조
비트 맵 데이터 구 조 는 유한 정의 역 내의 조밀 한 밀집 을 묘사 하 는데 그 중의 모든 요 소 는 최대 한 번 나타 나 고 다른 데이터 가 이 요소 와 관련 이 없다.메모리 공간 이 제 한 된 조건 에서 같은 메모리 에서 비트 맵 데이터 구 조 는 다른 데이터 형식 으로 저장 하 는 것 보다 훨씬 많은 데 이 터 를 저장 할 수 있 고 시간 에 도 좋 은 선택 이다.
비트 맵 데이터 구 조 는 각 비트 로 하나의 수 를 저장 하고 여러 비트 로 하나의 기본 데이터 형식 을 구성 하 며 여러 개의 같은 데이터 형식 으로 하나의 배열 을 형성한다. 예 를 들 어 int 는 네 개의 바이트, 32 비트 가 있 고 32 개의 수 를 각각 0 ~ 31, int [2] 로 저장 할 수 있 으 며 모두 64 개의 비트 가 있 으 며 0 ~ 63 사이 의 수 를 저장 하고 순서대로 유추 할 수 있다. 물론 데이터 유형 은 int 와 국한 되 지 않 고 다른 것 일 수도 있다.비트 맵 데이터 구 조 는 필요 한 공간 이 적 고 공간 을 크게 이용 할 수 있다 는 장점 을 알 수 있다.
다음은 비트 맵 데이터 구조의 구체 적 인 실현 절차 이다.
//      

#include
#include 
#define SIZE 5        //     ,      ,    
void init(int *bm);   //   
void Setbit(int *bm,int n);  //   n ,    n
void Clearbit(int *bm,int n);// n   ,    n
int Testbit(const int *bm,int n); //  n    

//   
void init(int *bm)
{
	int i;
	for(i = 0;i < SIZE;i++)
		bm[i] = 0;
}
//   n 
//n>>5   n/32;   n           
//n&0x1F   n%32,      , n
//  35;35>>5 = 1,35&0x1F = 3 35       1     3 
void Setbit(int *bm,int n)
{
	if(n <0 || n > SIZE*32)
		printf("%d    ,  0       !
",n); bm[n>>5] |= (1< SIZE*32) printf("%d , 0 !
",n); bm[n>>5] &= (~(1< SIZE*32) printf("%d , 0 !
",n); return bm[n>>5] & (1<

사실은 내 려 오 면서 비트 맵 의 실현 은 상대 적 으로 어렵 지 않다. 심지어 다른 데이터 구조 에 비해 비교적 간단 하 다. 그 중에서 비트 연산 은 주로 운행 속 도 를 가속 화 하 는 것 이다. 그 실현 이 간단 하기 때문에 우 리 는 매크로 를 통 해 실현 할 수 있다.그러나 비트 맵 데이터 구조 에 도 한계 가 있 습 니 다. 앞에서 언급 한 바 와 같이 데 이 터 는 중복 되 지 않 아야 합 니 다. 또한 데이터 의 크기 는 사용 하 는 배열 (또는 다른) 의 크기 (비트 의 개수) 보다 작 아야 합 니 다. 정렬 된 요 소 를 읽 을 때 배열 을 스 캔 해 야 하기 때문에 한 자리 로 스 캔 을 해 야 합 니 다. 데이터 가 비교적 크 지만 개수 가 적 을 때.얻 는 것 보다 잃 는 것 이 더 많 을 지도 모른다.
                                                                                                           ——잘못된 부분 이 있 으 면 지적 을 환영 합 니 다. 문제 가 있 으 면 메 시 지 를 남 겨 주세요.

좋은 웹페이지 즐겨찾기