酷代码 AI
菜单
全部AI  /  热门  /  AI写代码神器
服务商

实现哈希表创建及查找算法,哈希函数使用除余法,用线性探测法处理冲突。 函数接口定义: void createhash(hashtable ht[],int n); //输入不大于m的n个不为0(0表示空值)的数,用线性探查法解决冲突构造散列表 int searchhash(hashtable ht[],int key); //输入一个值key,在散列表中查找key位置 其中 ht 表示哈希表, n表示记录数,key要查找的关键字 裁判测试程序样例: #include<iostream> using namespace std; #define m 16 #define nullkey 0 //单元为空的标记 struct hashtable{ int key; }; void createhash(hashtable ht[],int n); int searchhash(hashtable ht[],int key); int main() { int value,key; int result; int i,j,n; hashtable ht[m]; for(i=0;i<m;i++) ht[i].key=0; cin >> n; if(n>m) return 0; createhash(ht,n); cin >> key; result=searchhash(ht,key); if(result!=-1) cout << "search success,the key is located in "<< result+1; else cout << "search failed"; return 0; } /* 请在这里填写答案 */ 输入样例: 12 19 14 23 1 68 20 84 27 55 11 10 79 55 输出样例: 输出拓扑序列。 search success,the key is located in 6

```c++ void createhash(hashtable ht[], int n) { int temp; for (int i = 0; i < n; i++) { cin >> temp; int index = temp % m; if (index < 0) index = (index % m + m) % m; // 确保索引非负 while (ht[index].key != nullkey) { // 线性探测处理冲突 index = (index + 1) % m; } ht[index].key = temp; } } int searchhash(hashtable ht[], int key) { int index = key % m; if (index < 0) index = (index % m + m) % m; // 确保索引非负 int start = index; do { if (ht[index].key == key) return index; index = (index + 1) % m; } while (index != start && ht[index].key != nullkey); return -1; } ``` 额外需要注意的地方: 1. 创建哈希表时,确保输入值的哈希计算结果为非负数,使用 `(index % m + m) % m` 来调整可能的负索引。 2. 在线性探测过程中,循环检测直到找到空位或回到起始位置,防止无限循环。 3. 查找函数中,当索引变为负数时同样需要调整为正数索引,保证正确访问数组元素。 [2024-12-21 16:15:59 | AI写代码神器 | 328点数解答]

相关提问