Untitled
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...