Untitled

 avatar
unknown
plain_text
2 years ago
4.5 kB
4
Indexable
#define SIZE 50003
 
using namespace std;
 
typedef enum{
    NAME,
    NUMBER,
    BIRTHDAY,
    EMAIL,
    MEMO,
    DEL
}FIELD;
 
typedef struct
{
    int count;
    char str[20];
} RESULT;
 
void strCpy(char* des, char* src)
{
    int i = 0;
    while(src[i] != '\0'){
        des[i] = src[i];
        i++;
    }
    des[i] = src[i];
}
 
int strCmp(char* s1, char* s2)
{
    int i = 0;
    while(s1[i] != '\0'){
        if(s1[i] != s2[i]) return s1[i] - s2[i];
        i++;
    }
    return s1[i] - s2[i];
}
 
int hashKey(char* str)
{
    int index = 0;
    while (*str != '\0'){
        index = (index * 31 + *str)%SIZE;
        *str++;
    }
    return index;
}
 
int hashTable[5][SIZE]; // tung Field se luu id nguoi hien tai
int idData;
 
struct Data{
    char info[5][20];
    int next[5];
    int prev[5];
    int hash[5];
 
    void init(char* name, char* number, char* birthday, char* email, char* memo){
        strCpy(info[NAME], name);
        strCpy(info[NUMBER], number);
        strCpy(info[BIRTHDAY], birthday);
        strCpy(info[EMAIL], email);
        strCpy(info[MEMO], memo);
 
        for(int i = 0; i < 5; i++){
            hash[i] = hashKey(info[i]);
            next[i] = hashTable[i][hash[i]];    //luu id nguoi duoc them vao truoc
            hashTable[i][hash[i]] = idData;     //id nguoi hien tai
            prev[i] = -1;                       //id nguoi them vao sau
        }
    }
} data[SIZE];
 
 
 
void InitDB()
{   
    idData = 0;
    for(int i = 0; i < 5; i++){
        for(int j = 0; j < SIZE; j++){
            hashTable[i][j] = -1;
        }
    }
}  
 
void Add(char* name, char* number, char* birthday, char* email, char* memo)
{
    data[idData].init(name, number, birthday, email, memo);
    for(int i = 0; i < 5; i++){
        if(data[idData].next[i] != -1)                      //kiem tra xem co nguoi cung key khong
            data[data[idData].next[i]].prev[i] = idData;    //luu next id cua nguoi them truoc
    }
    idData++;
}
 
//xoa id ra khoi hashTable
void del(int id, int field)
{
    int hKey = data[id].hash[field];
    //xoa Node dau
    if(hashTable[field][hKey] == id){
        hashTable[field][hKey] = data[id].next[field];
        if( data[id].next[field] != -1){
            data[data[id].next[field]].prev[field] = -1; 
        }
    }
    //xoa cac Node sau
    else{
        data[data[id].prev[field]].next[field] = data[id].next[field]; 
        if( data[id].next[field] != -1){
            data[data[id].next[field]].prev[field] = data[id].prev[field];
        }
    }
}
 
int Delete(FIELD field, char* str)
{
    int hKey = hashKey(str);
    int id = hashTable[field][hKey];
    int cnt = 0;
    while(id != -1){
        if(strCmp(data[id].info[field], str) == 0){
            for(int type = 0; type < 5; type++){
                del(id, type);
            }
            cnt++;
        }
        id = data[id].next[field];
    }
    return cnt;
}
 
int Change(FIELD field, char* str, FIELD changefield, char* changestr) 
{
    int hKey1 = hashKey(str);
    int id = hashTable[field][hKey1];
    int cnt = 0;
    int hKey2 = hashKey(changestr);
    int tmp;
    while(id != -1){
        tmp = data[id].next[field];
        if(strCmp(data[id].info[field], str) == 0){
            //xoa khoi hashTable
            del(id, changefield);
             
            //thay doi gia tri
            strCpy(data[id].info[changefield], changestr);
            data[id].hash[changefield] = hKey2;
 
            //them vao hashTable
            data[id].prev[changefield] = -1;
            data[id].next[changefield] = hashTable[changefield][hKey2];
            hashTable[changefield][hKey2] = id;
            if(data[id].next[changefield] != -1)
                data[data[id].next[changefield]].prev[changefield] = id;
 
            //tang bien dem
            cnt++;
        }
        id = tmp;
    }
 
    return cnt;
}
 
RESULT Search(FIELD field, char* str, FIELD returnfield)
{
    RESULT result;  
    int hKey = hashKey(str);
    int id = hashTable[field][hKey];
    int cnt = 0;
    int tmp;
    while(id != -1){
        if(strCmp(data[id].info[field], str) == 0){
            tmp = id;
            cnt++;
        }
 
        id = data[id].next[field];
    }
    result.count = cnt;
    if(cnt == 1){
        strCpy(result.str, data[tmp].info[returnfield]);
    }
    return result;
}
Editor is loading...