【数据结构】线性探测法构造散列表及其查找 梦里梦外; 2023-08-17 15:23 58阅读 0赞 #include<iostream> using namespace std; const int LEN = 20; // Hash表长 const int INF = 0xffff; // 表空标记 const int a_length = 12; // 测试数组长度 int p = 13; // 取余质数 int HASH[LEN]; // HASH表 // 构造Hash表 void Hash(int a[], int a_length, int p) { for (int i = 0; i < LEN; i++) { HASH[i] = INF; } for (int i = 0; i < a_length; i++) { int key = a[i]; int addr = key % p; while (HASH[addr] != INF) addr++; HASH[addr] = key; } } // 查找Hash表元素 int SearchHash(int key, int p) { cout<<"Search for "<<key<<endl; int addr = key % p; cout<<"addr = "<<addr<<", HASH["<<addr<<"] = "<<HASH[addr]<<endl; if (HASH[addr] == key) return addr; int d = 0; while (HASH[addr] != key) { d++; int newAddr = (addr + d) % LEN; cout<<"addr = ("<<addr<<" + "<<d<<") % "<<LEN<<" = "<<newAddr<<", HASH["<<newAddr<<"] = "<<HASH[newAddr]<<endl; if (HASH[newAddr] == key) return addr; if (HASH[newAddr] == INF) return -1; } } // 打印Hash表 void PrintHash() { for (int i = 0; i < LEN; i++) cout<<HASH[i]<<" "; cout<<endl; } int main() { int a[a_length] = {19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79}; Hash(a, a_length, p); PrintHash(); for (int i = 0; i < 12; i++) { SearchHash(a[i], p); cout<<endl; } return 0; } // p = 13时的结果 65535 14 1 68 27 55 19 20 84 79 23 11 10 65535 65535 65535 65535 65535 65535 65535 Search for 19 addr = 6, HASH[6] = 19 Search for 14 addr = 1, HASH[1] = 14 Search for 23 addr = 10, HASH[10] = 23 Search for 1 addr = 1, HASH[1] = 14 addr = (1 + 1) % 20 = 2, HASH[2] = 1 Search for 68 addr = 3, HASH[3] = 68 Search for 20 addr = 7, HASH[7] = 20 Search for 84 addr = 6, HASH[6] = 19 addr = (6 + 1) % 20 = 7, HASH[7] = 20 addr = (6 + 2) % 20 = 8, HASH[8] = 84 Search for 27 addr = 1, HASH[1] = 14 addr = (1 + 1) % 20 = 2, HASH[2] = 1 addr = (1 + 2) % 20 = 3, HASH[3] = 68 addr = (1 + 3) % 20 = 4, HASH[4] = 27 Search for 55 addr = 3, HASH[3] = 68 addr = (3 + 1) % 20 = 4, HASH[4] = 27 addr = (3 + 2) % 20 = 5, HASH[5] = 55 Search for 11 addr = 11, HASH[11] = 11 Search for 10 addr = 10, HASH[10] = 23 addr = (10 + 1) % 20 = 11, HASH[11] = 11 addr = (10 + 2) % 20 = 12, HASH[12] = 10 Search for 79 addr = 1, HASH[1] = 14 addr = (1 + 1) % 20 = 2, HASH[2] = 1 addr = (1 + 2) % 20 = 3, HASH[3] = 68 addr = (1 + 3) % 20 = 4, HASH[4] = 27 addr = (1 + 4) % 20 = 5, HASH[5] = 55 addr = (1 + 5) % 20 = 6, HASH[6] = 19 addr = (1 + 6) % 20 = 7, HASH[7] = 20 addr = (1 + 7) % 20 = 8, HASH[8] = 84 addr = (1 + 8) % 20 = 9, HASH[9] = 79 // p = 7时的结果 14 1 23 84 11 19 68 20 27 55 10 79 65535 65535 65535 65535 65535 65535 65535 65535 Search for 19 addr = 5, HASH[5] = 19 Search for 14 addr = 0, HASH[0] = 14 Search for 23 addr = 2, HASH[2] = 23 Search for 1 addr = 1, HASH[1] = 1 Search for 68 addr = 5, HASH[5] = 19 addr = (5 + 1) % 20 = 6, HASH[6] = 68 Search for 20 addr = 6, HASH[6] = 68 addr = (6 + 1) % 20 = 7, HASH[7] = 20 Search for 84 addr = 0, HASH[0] = 14 addr = (0 + 1) % 20 = 1, HASH[1] = 1 addr = (0 + 2) % 20 = 2, HASH[2] = 23 addr = (0 + 3) % 20 = 3, HASH[3] = 84 Search for 27 addr = 6, HASH[6] = 68 addr = (6 + 1) % 20 = 7, HASH[7] = 20 addr = (6 + 2) % 20 = 8, HASH[8] = 27 Search for 55 addr = 6, HASH[6] = 68 addr = (6 + 1) % 20 = 7, HASH[7] = 20 addr = (6 + 2) % 20 = 8, HASH[8] = 27 addr = (6 + 3) % 20 = 9, HASH[9] = 55 Search for 11 addr = 4, HASH[4] = 11 Search for 10 addr = 3, HASH[3] = 84 addr = (3 + 1) % 20 = 4, HASH[4] = 11 addr = (3 + 2) % 20 = 5, HASH[5] = 19 addr = (3 + 3) % 20 = 6, HASH[6] = 68 addr = (3 + 4) % 20 = 7, HASH[7] = 20 addr = (3 + 5) % 20 = 8, HASH[8] = 27 addr = (3 + 6) % 20 = 9, HASH[9] = 55 addr = (3 + 7) % 20 = 10, HASH[10] = 10 Search for 79 addr = 2, HASH[2] = 23 addr = (2 + 1) % 20 = 3, HASH[3] = 84 addr = (2 + 2) % 20 = 4, HASH[4] = 11 addr = (2 + 3) % 20 = 5, HASH[5] = 19 addr = (2 + 4) % 20 = 6, HASH[6] = 68 addr = (2 + 5) % 20 = 7, HASH[7] = 20 addr = (2 + 6) % 20 = 8, HASH[8] = 27 addr = (2 + 7) % 20 = 9, HASH[9] = 55 addr = (2 + 8) % 20 = 10, HASH[10] = 10 addr = (2 + 9) % 20 = 11, HASH[11] = 79 // p = 11时的结果 Search for 14 addr = 3, HASH[3] = 14 Search for 23 addr = 1, HASH[1] = 23 Search for 1 addr = 1, HASH[1] = 23 addr = (1 + 1) % 20 = 2, HASH[2] = 1 Search for 68 addr = 2, HASH[2] = 1 addr = (2 + 1) % 20 = 3, HASH[3] = 14 addr = (2 + 2) % 20 = 4, HASH[4] = 68 Search for 20 addr = 9, HASH[9] = 20 Search for 84 addr = 7, HASH[7] = 84 Search for 27 addr = 5, HASH[5] = 27 Search for 55 addr = 0, HASH[0] = 55 Search for 11 addr = 0, HASH[0] = 55 addr = (0 + 1) % 20 = 1, HASH[1] = 23 addr = (0 + 2) % 20 = 2, HASH[2] = 1 addr = (0 + 3) % 20 = 3, HASH[3] = 14 addr = (0 + 4) % 20 = 4, HASH[4] = 68 addr = (0 + 5) % 20 = 5, HASH[5] = 27 addr = (0 + 6) % 20 = 6, HASH[6] = 11 Search for 10 addr = 10, HASH[10] = 10 Search for 79 addr = 2, HASH[2] = 1 addr = (2 + 1) % 20 = 3, HASH[3] = 14 addr = (2 + 2) % 20 = 4, HASH[4] = 68 addr = (2 + 3) % 20 = 5, HASH[5] = 27 addr = (2 + 4) % 20 = 6, HASH[6] = 11 addr = (2 + 5) % 20 = 7, HASH[7] = 84 addr = (2 + 6) % 20 = 8, HASH[8] = 19 addr = (2 + 7) % 20 = 9, HASH[9] = 20 addr = (2 + 8) % 20 = 10, HASH[10] = 10 addr = (2 + 9) % 20 = 11, HASH[11] = 79
还没有评论，来说两句吧...