构造散列表

yangzhixiaohuli

设散列表a[18]，散列函数是hask(k)=k%17，用开放地址法解决冲突h
i
​
=(h
0
​
+d
i
​
)%m。冲突时，使用增量序列d
i
​
=5i。计算输入序列(值>=0)对应的散列地址值。（输入个数不会超过15个）

输入格式:
第一行为输入个数；

第二行为对应的输入值，用空格隔开。

输出格式:
按输入顺序输出其散列地址。每行对应一个值及其散列地址，中间用空格隔开（即pos前后均有一个空格）

输入样例:
5
141 73 95 112 56
输出样例:
141 pos: 5
73 pos: 10
95 pos: 15
112 pos: 2
56 pos: 7

这题用C语言或者C++怎么做

FishC

以下是使用C++编写的程序代码，以开放地址法解决散列表的冲突问题：

1. #include <iostream>
   
2. #include <vector>
   
3. using namespace std;
   
4. 
   
5. // 定义散列表的大小
   
6. const int TABLE_SIZE = 17;
   
7. 
   
8. // 定义散列函数
   
9. int hashFunction(int k) {
   
10.     return k % TABLE_SIZE;
    
11. }
    
12. 
    
13. // 查找插入位置
    
14. int findPosition(vector<int>& table, int key) {
    
15.     int hashValue = hashFunction(key);
    
16.     int i = 0;
    
17.     while (table[(hashValue + 5 * i) % TABLE_SIZE] != -1) {
    
18.         i++;
    
19.     }
    
20.     return (hashValue + 5 * i) % TABLE_SIZE;
    
21. }
    
22. 
    
23. int main() {
    
24.     int n;  // 输入个数
    
25.     cin >> n;
    
26. 
    
27.     vector<int> table(TABLE_SIZE, -1);  // 初始化散列表
    
28. 
    
29.     for (int i = 0; i < n; ++i) {
    
30.         int value;
    
31.         cin >> value;
    
32. 
    
33.         int pos = findPosition(table, value);
    
34.         table[pos] = value;  // 插入值
    
35. 
    
36.         cout << value << " pos: " << pos << endl;
    
37.     }
    
38. 
    
39.     return 0;
    
40. }

复制代码

**说明：**

1. **hashFunction**: 计算给定键的初始散列值。  
2. **findPosition**: 利用增量序列 \(d_i = 5i\) 计算并查找适合插入的空位置。  
3. **main函数**: 通过输入获取数据并利用以上函数找出适合的位置，然后输出值和位置。  

将以上代码复制并在C++编译器中执行即可获得对应的输出结果。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。