编写程序,实现静态查找表的查找:(1) 按关键字从小到大顺序输入一组记录构造查找表;(2) 给定一个关键字值,对所构造的查找表分别进行顺序查找和折半查找,输出查找的结果以及查找过程中“比较”操作的执行次数。输入格式:第一行的整数表示要建立的查找表的长度n;n 行数据,每行数据的两个整数之间以空格分隔,分别表示第i条记录的关键字域和其他域。最后一行的数据表示要查找的记录的关键字值。输出格式:查找结果,两行数据,第一行表示用顺序查找的查找结果,两个数据分别表示是否找到和比较次数;第二行表示用折半查找的查找结果,两个数据分别表示是否找到和比较次数。
时间: 2024-03-25 07:38:42 浏览: 94
静态查找表算法
好的,我知道了你的要求。下面是 Python 代码实现:
```python
# 顺序查找
def sequential_search(key, table):
count = 0 # 记录比较次数
for i in range(len(table)):
count += 1
if key == table[i][0]:
return True, count
return False, count
# 折半查找
def binary_search(key, table):
count = 0 # 记录比较次数
low, high = 0, len(table) - 1
while low <= high:
mid = (low + high) // 2
count += 1
if key == table[mid][0]:
return True, count
elif key < table[mid][0]:
high = mid - 1
else:
low = mid + 1
return False, count
# 主函数
if __name__ == '__main__':
n = int(input("请输入查找表的长度n:"))
table = []
for i in range(n):
key, value = map(int, input().split())
table.append((key, value))
key = int(input("请输入要查找的关键字值:"))
# 排序
table.sort()
# 顺序查找
sequential_found, sequential_count = sequential_search(key, table)
# 折半查找
binary_found, binary_count = binary_search(key, table)
# 输出结果
print("用顺序查找的查找结果:", sequential_found, sequential_count)
print("用折半查找的查找结果:", binary_found, binary_count)
```
注意,这里假设输入的数据没有错误,例如输入的长度n与实际输入的记录数一致,输入的记录按照关键字从小到大排序等。如果要增加容错处理,需要在代码中添加相应的判断。
阅读全文