数据布局哈希表-(开放地点法+二次探测法解决哈希冲突)(创建+删除+插入)+(C ...

1. #include<stdio.h>
2. #include<stdlib.h>
3. #include<stdbool.h>
4. #define M 20
5. #define NULLDEL -1
6. #define DELDEY -2
8. typedef struct
9. {
10.         int key;
11.         int count;
12. }HashTable;
14. //创建和插入
15. void Insert(HashTable ha[], int m, int p, int key)
16. {
17.         int i, HO, HI;
18.         HO = key % p;
19.         if (ha[HO].key == NULLDEL || ha[HO].key == DELDEY)
20.         {
21.                 ha[HO].key = key;
22.                 ha[HO].count = 1;
23.         }
24.         else
25.         {
26.                 i = 1;
27.                 do
28.                 {
29.                         HI = (HO + i * i) % m;
30.                         i++;
31.                 } while (ha[HI].key != NULLDEL && ha[HI].key != DELDEY);
32.                 ha[HI].key = key;
33.                 ha[HI].count = i;
34.         }
35. }
36. void Create(HashTable ha[],int m,int n1,int p,int keys[])
37. {
38.         int i;
39.         for (i = 0; i < m; i++)
40.         {
41.                 ha[i].key = NULLDEL;
42.                 ha[i].count = 0;
43.         }
44.         for (i = 0; i < n1; i++)
45.         {
46.                 Insert(ha, m, p, keys[i]);
47.         }
48.         printf("二次探测法哈希表如下:\n");
49.         for (i = 0; i < m; i++)
50.         {
51.                 printf("%d  查找次数 %d 次\n", ha[i].key,ha[i].count);
52.         }
53. }
54. //查找
55. int Search(HashTable ha[], int m, int p, int key)
56. {
57.         int HO, HI;
58.         HO = key % p;
59.         if (ha[HO].key == NULLDEL)
60.         {
61.                 ha[HO].count = 1;
62.                 return -1;
63.         }
64.         else if (ha[HO].key == key)
65.         {
66.                 ha[HO].count = 1;
67.                 return HO;
68.         }
69.         else
70.         {
71.                 ha[HO].count = 1;
72.                 for (int i = 0; i < m; i++)
73.                 {
74.                         HI = (HO + i * i) % m;//HO还是那个HO，这里变的是HI和i的值
75.                         if (ha[HI].key == NULLDEL)
76.                         {
77.                                 ha->count = ha[HO].count + i;//哈希冲突的次数
78.                                 return -1;
79.                         }
80.                         else if (ha[HI].key == key)
81.                         {
82.                                 ha->count = ha[HO].count + i;
83.                                 return HI;
84.                         }
85.                 }
86.         }
87. }
88. //删除哈希值
89. bool deleteNode(HashTable ha[], int m, int p, int key)
90. {
91.         int HO,i = 1;
92.         HO = key % p;
93.         while (ha[HO].key != NULLDEL && ha[HO].key != key)
94.         {
95.                 HO = (HO + i * i);
96.                 i++;
97.         }
98.         if (ha[HO].key == key)
99.         {
100.                 ha[HO].key = DELDEY;
101.                 return true;
102.         }
103.         else
104.         {
105.                 return false;
106.         }
107. }
108. int main()
109. {
110.         HashTable ha[M];
111.         int keys[] = { 19,14,23,1,68,20,84,27,55,11,10,79 };
112.         int n1 = sizeof(keys) / sizeof(keys[0]);
113.         int p = 13;
114.         Create(ha, M, n1, p, keys);
116.         int key = 79;
117.         int result = Search(ha, M, p, key);
118.         if (result!=-1)
119.         {
120.                 printf("找到 %d 位置在 %d 哈希冲突 %d 次\n", key, result, ha->count);
121.         }
122.         else {
123.                 printf("找不到 %d 哈希冲突 %d 次\n", key, ha->count);
124.         }
125.        
126.         key = 23;
127.         deleteNode(ha, M, p, key);
128.         printf("删除 %d 元素后遍历如下:\n", key);
129.         for (int i = 0; i < M; i++)
130.         {
131.                 if (ha[i].key != NULLDEL && ha[i].key != DELDEY)
132.                 {
133.                         printf(" %d ", ha[i].key);
134.                 }
135.                 else {
136.                         printf(" * ");
137.                 }
138.         }
139.         return 0;
140. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。