C++散列查找实验（开散列）

Question

遇到一个算法类的问题，求助各位大佬帮我看看怎么做

• 请设计一个整型开散列表，散列函数为除留余数法，其中散列表的长度、除留余数法的模和关键码的个数由键盘输入，再根据输入由键盘输入所有的关键码。分别对三个待查值在散列表中进行查找，输出查找结果采用头插法。

• 输入描述
  各个命令以及相关数据的输入格式如下：
  第一行输入闭散列表的长度n
  第二行输入除留余数法的模m
  第三行输入关键码的个数num
  第四行输入num个整型关键码
  第五行输入三个待查整型值

• 输出描述
  输出三行，每行格式为：
  如果找到待查值，输出找到待查值的位置，先输出待查值在散列表指针数组中的下标，
  再输出待查值在关键码链表中的位置，从1开始，如果没找到，输出“none”，并把待查值
  插入到开散列表中

• 输入样例
  11 11 9
  2 6 8 9 13 17 10 12 20
  11 13 9

• 输出样例
  none
  2 1
  9 2

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

首先，我们需要设计一个整型的开散列表，使用除留余数法作为散列函数。接下来按照输入描述依次输入列表的长度n，除留余数法的模m，关键码的个数num，以及num个整型关键码。然后输入三个待查整型值。 接下来，我们需要对三个待查值在散列表中进行查找，输出查找结果采用头插法。 下面是Python代码示例：

# 定义除留余数法的散列函数
def hash_func(key, n, m):
    return key % m % n
# 头插法插入元素
def insert_head(table, idx, key):
    table[idx].insert(0, key)
# 查找元素
def search(table, key, n, m):
    idx = hash_func(key, n, m)
    if key in table[idx]:
        return idx, table[idx].index(key) + 1
    else:
        insert_head(table, idx, key)
        return "none"
# 从键盘输入相关数据
n = int(input())
m = int(input())
num = int(input())
keys = list(map(int, input().split()))
search_keys = list(map(int, input().split()))
# 初始化散列表
table = [[] for _ in range(n)]
# 插入关键码
for key in keys:
    idx = hash_func(key, n, m)
    insert_head(table, idx, key)
# 查找待查值
for key in search_keys:
    result = search(table, key, n, m)
    if result == "none":
        print("none")
    else:
        print(result[0], result[1])

这段代码实现了根据输入数据构建一个开散列表，然后对三个待查值进行搜索，并输出相应的结果。