Untitled

 avatar
unknown
plain_text
2 years ago
5.8 kB
4
Indexable
#define HASH 1997
  
typedef enum
{
    NAME,
    NUMBER,
    BIRTHDAY,
    EMAIL,
    MEMO
} FIELD;
  
typedef struct
{
    int count;
    char str[20];
} RESULT;
  
int hashF(char *name) {
    int h = 0;
    int i = 0;
    while (name[i] != '\0') {
        h = h * 31 + name[i];
        i++;
    }
    if (h < 0) h = -h;
    return h;
}
  
void copy(char* src, char dest[])
{
    int i = 0;
    while (src[i] != '\0') { dest[i] = src[i]; i++; }
    dest[i] = src[i];
}
  
int compare(char a[], char b[])
{
    int i;
    for (i = 0; a[i] != '\0'; ++i) if (a[i] != b[i]) return a[i] - b[i];
    return a[i] - b[i];
}
  
int hashTable[5][HASH];
int ci;
struct Contact {
    char value[5][20];
    int h[5];
    int next[5];
    int pre[5];
  
    void init(char *n, char *num, char *birth, char *e, char *m) {
        copy(n, value[0]);
        copy(num, value[1]);
        copy(birth, value[2]);
        copy(e, value[3]);
        copy(m, value[4]);
  
        for (int i = 0; i < 5; i++) {
            h[i] = hashF(value[i]);
            next[i] = hashTable[i][h[i]%HASH];
            hashTable[i][h[i]%HASH] = ci;
            pre[i] = -1;
        }
    }
} contacts[50002];
  
void InitDB() {
    ci = 0;
    for (int i = 0; i < HASH; i++) {
        for (int j = 0; j < 5; j++) hashTable[j][i] = -1;
    }
}
  
void Add(char* name, char* number, char* birthday, char* email, char* memo){
    contacts[ci].init(name, number, birthday, email, memo);
    for (int i = 0; i < 5; i++) {
        if (contacts[ci].next[i] != -1) contacts[contacts[ci].next[i]].pre[i] = ci;
    }
    ci++;
}
  
int find(int type, char *str) {
    int hv = hashF(str)%HASH;
    int i = hashTable[type][hv];
    while (i != -1) {
        if (compare(str, contacts[i].value[type]) == 0) {
            return i;
        }
        i = contacts[i].next[type];
    }
  
    return -1;
}
  
void del(int id) {
    int h;
    for (int type = 0; type < 5; type++) {
        h = contacts[id].h[type]%HASH;
        if (hashTable[type][h] == id) {
            hashTable[type][h] = contacts[id].next[type];
            if (contacts[id].next[type] != -1) contacts[contacts[id].next[type]].pre[type] = -1;
        } else {
            contacts[contacts[id].pre[type]].next[type] = contacts[id].next[type];
            if (contacts[id].next[type] != -1) contacts[contacts[id].next[type]].pre[type] = contacts[id].pre[type];
        }
    }
}
  
int Delete(FIELD field, char* str) {
    int hv = hashF(str)%HASH;
    int i = hashTable[field][hv];
    int cnt = 0;
    while (i != -1) {
        if (compare(str, contacts[i].value[field]) == 0) {
            del(i);
            cnt++;
        }
        i = contacts[i].next[field];
    }
    return cnt;
}
  
int Change(FIELD field, char* str, FIELD changefield, char* changestr){
    int hv = hashF(str)%HASH;
    int i = hashTable[field][hv];
    int cnt = 0;
    int hv2 = hashF(changestr);
    int tmp;
    while (i != -1) {
        tmp = contacts[i].next[field];
        if (compare(str, contacts[i].value[field]) == 0) {
            // remove from hash table
            hv = contacts[i].h[changefield];
            if (i == hashTable[changefield][hv%HASH]) {
                hashTable[changefield][hv%HASH] = contacts[i].next[changefield];
                if (contacts[i].next[changefield] != -1) contacts[contacts[i].next[changefield]].pre[changefield] = -1;
            } else {
                if (contacts[i].next[changefield] != -1) contacts[contacts[i].next[changefield]].pre[changefield] = contacts[i].pre[changefield];
                contacts[contacts[i].pre[changefield]].next[changefield] = contacts[i].next[changefield];
            }
  
            // change value
            copy(changestr, contacts[i].value[changefield]);
            contacts[i].h[changefield] = hv2;
  
            // add to hash table
            contacts[i].pre[changefield] = -1;
            contacts[i].next[changefield] = hashTable[changefield][hv2%HASH];
            hashTable[changefield][hv2%HASH] = i;
            if (contacts[i].next[changefield] != -1) contacts[contacts[i].next[changefield]].pre[changefield] = i;
  
            cnt++;
        }
        i = tmp;
    }
    return cnt;
}
  
RESULT result;
  
RESULT Search(FIELD field, char* str, FIELD returnfield) {
    int hv = hashF(str)%HASH;
    int i = hashTable[field][hv];
    int cnt = 0;
    int res;
    while (i != -1) {
        if (compare(str, contacts[i].value[field]) == 0) {
            res = i;
            cnt++;
        }
        i = contacts[i].next[field];
    }
  
    result.count = cnt;
    if (cnt == 1) {
        copy(contacts[res].value[returnfield], result.str);
    }
      
    return result;
}
Editor is loading...