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