7-43 字符串关键字的散列映射 (25分)--散列，平方探测法

 1 #include <iostream>
 2 #include <string>
 3 #include <cstring>
 4 using namespace std;
 5 int main()
 6 {
 7     char a[501][10];//存储字符串
 8     int pos[501];//字符串存放的位置
 9     int exist[1100];//用来标志表中某个位置是否被占用，数组要开大，P是>=N的最小素数
10     int N, P;
11     cin >> N >> P;
12     for (int i = 0; i < P; i++)exist[i] = -1;//没有被占用时设为-1
13     for (int i = 0; i < N; i++)
14     {
15         cin >> a[i];
16         int flag = 0;
17         for (int c = 0; c < i; c++)
18         {
19             if (!strcmp(a[i], a[c]))//检测是否有重复的关键字
20             {
21                 pos[i] = pos[c];
22                 flag = 1;
23                 break;
24             }
25         }
26         if (flag == 0)//如果没有重复的关键字
27         {
28             int k = -1;
29             while (a[i][++k] != '');
30             if (k < 3)//判断字符是否小于三个
31             {
32                 if (k == 2)k -= 2;
33                 else if (k == 1)k -= 1;
34             }
35             else
36             {
37                 k -= 3;
38             }
39             unsigned long int hash_value = 0;//开始散列
40             while (a[i][k] != '')
41             {
42                 hash_value = (hash_value << 5) + (int)(a[i][k++] - 'A');
43             }
44             int x = hash_value % P;
45             int tempx = x;
46             int j = 1;
47             while (exist[x] != -1)//平方探测法处理冲突
48             {
49                 x = tempx;
50                 x = (x + j * j);
51                 while (x >= P)x -= P;
52                 if (exist[x] != -1)
53                 {
54                     x = tempx;
55                     x = (x - j * j);
56                     while (x < 0)x += P;
57                 }
58                 j++;
59             }
60             pos[i] = x;
61             exist[x] = 1;
62         }
63     }
64     for (int i = 0; i < N; i++)
65     {
66         cout << pos[i];
67         if (i != N - 1)cout << ' ';
68     }
69     return 0;
70 }