开放寻址法的几种实现

2009-03-24 16:15

const int m = 701;//与2^n不太接近的素数

const int m2 = 2917;//与2^n不太接近的素数

int list[m];
int iter;
 
void init();

int h(int key);
int h2(int key);
int get_key(char c);
 
void init(){
     for(int i=0;i<m;i++)
         list[i] = -1;
}
int h(int key){
    return key%m;
}
   
int h2(int key){
    return key%m2;
}
   
int get_key(char c){
    return (int)c<<4;
}
 
双重探查：
void insert(char c);
int search(char c);
 
void insert(char c){
     int i,t,t2;
    
     t = h(get_key(c) );
     t2 = h2(get_key(c) );
     for(i=0;i<m;i++){
         if(list[t]==-1){
            list[t] = c;
            break;
         }
         t = (t+t2)%m;
        
     }
}
   
int search(char c){
    int r,i,t,t2;
    
    r = -1;
    t = h(get_key(c) );
    t2 = h(get_key(c) );
    for(i=0;i<m;i++){
        //test

        iter++;
        //test

        if(list[t]==c){
           r = t;
           break;
        }
        t=(t+t2)%m;
    }
    
    return r;
}
线性探查：
void insert(char c);
int search(char c);
 
void init(){
     for(int i=0;i<m;i++)
         list[i] = -1;
}
int h(int key){
    return key%m;
}
   
int get_key(char c){
    return (int)c<<4;
}
void insert(char c){
     int i,t;
    
     t = h(get_key(c) );
     for(i=0;i<m;i++){
         if(list[t]==-1){
            list[t] = c;
            break;
         }
         t = (t+1)%m;
        
     }
}
   
int search(char c){
    int r,i,t;
    
    r = -1;
    t = h(get_key(c) );
    for(i=0;i<m;i++){
        //test

        iter++;
        //test

        if(list[t]==c){
           r = t;
           break;
        }
        t=(t+1)%m;
    }
    
    return r;
}
二次探查：
void insert(char c);
int search(char c);
 
void init(){
     for(int i=0;i<m;i++)
         list[i] = -1;
}
int h(int key){
    return key%m;
}
   
int get_key(char c){
    return (int)c<<4;
}
void insert(char c){
     int i,t;
    
     t = h(get_key(c) );
     for(i=0;i<m;i++){
         if(list[t]==-1){
            list[t] = c;
            break;
         }
         t = (t+i)%m;
        
     }
}
   
int search(char c){
    int r,i,t;
    
    r = -1;
    t = h(get_key(c) );
    for(i=0;i<m;i++){
        //test

        iter++;
        //test

        if(list[t]==c){
           r = t;
           break;
        }
        t=(t+i)%m;
    }
    
    return r;
}