设每个记录有下列数据项:电话号码、用户名、住址。从键盘输入各记录,以用户名为关键字建立哈希表,哈希函数用除留取余数法构造,采用线性探测法解决冲突。可以插入、查找、删除并显示给定用户名的记录,并计算查找长度, 哈希表保存到文件中。
时间: 2024-02-01 21:14:59 浏览: 67
Hash表存储数据,用再散列来解决地址冲突问题,计算平均查找长度,还可以通过Key值查找对应的value
以下是基于Python语言的实现,涉及到文件操作以及哈希表的基本操作。
```python
import os
# 定义哈希表类
class HashTable:
def __init__(self):
self.size = 11 # 哈希表的大小
self.slots = [None] * self.size # 哈希表的槽数
self.data = [None] * self.size # 哈希表的数据
# 哈希函数
def hashfunction(self, key, size):
return key % size
# 插入操作
def insert(self, key, data):
hashvalue = self.hashfunction(key, len(self.slots))
if self.slots[hashvalue] == None: # 如果当前位置为空,直接插入
self.slots[hashvalue] = key
self.data[hashvalue] = data
else: # 否则进行线性探测
nextslot = self.rehash(hashvalue, len(self.slots))
while self.slots[nextslot] != None and self.slots[nextslot] != key:
nextslot = self.rehash(nextslot, len(self.slots))
if self.slots[nextslot] == None: # 如果找到了空位置,插入
self.slots[nextslot] = key
self.data[nextslot] = data
else: # 否则覆盖原有数据
self.data[nextslot] = data
# 查找操作
def get(self, key):
startslot = self.hashfunction(key, len(self.slots))
data = None
stop = False
found = False
position = startslot
while self.slots[position] != None and not found and not stop:
if self.slots[position] == key:
found = True
data = self.data[position]
else:
position = self.rehash(position, len(self.slots))
if position == startslot:
stop = True
return data
# 删除操作
def delete(self, key):
startslot = self.hashfunction(key, len(self.slots))
stop = False
found = False
position = startslot
while self.slots[position] != None and not found and not stop:
if self.slots[position] == key:
found = True
self.slots[position] = None
self.data[position] = None
else:
position = self.rehash(position, len(self.slots))
if position == startslot:
stop = True
# 哈希表的扩容操作
def rehash(self, oldhash, size):
return (oldhash + 1) % size
# 显示哈希表中的记录
def show(self):
for i in range(len(self.slots)):
if self.slots[i] != None:
print("用户名:", self.slots[i], ",住址:", self.data[i])
# 将哈希表保存到文件中
def save(self):
with open("hashtable.txt", "w") as f:
for i in range(len(self.slots)):
if self.slots[i] != None:
f.write(str(self.slots[i]) + " " + str(self.data[i]) + "\n")
```
接下来就可以进行测试了:
```python
if __name__ == '__main__':
# 创建哈希表
hashtable = HashTable()
# 从文件中读取记录
if os.path.exists("hashtable.txt"):
with open("hashtable.txt", "r") as f:
for line in f.readlines():
key, data = line.strip().split()
hashtable.insert(int(key), data)
# 插入新记录
key = int(input("请输入电话号码:"))
data = input("请输入用户名和住址,用空格分隔:")
hashtable.insert(key, data)
# 显示指定用户名的记录
username = input("请输入要查找的用户名:")
data = hashtable.get(int(username))
if data != None:
print("该用户的住址为:", data)
else:
print("未找到该用户!")
# 删除指定用户名的记录
username = input("请输入要删除的用户名:")
hashtable.delete(int(username))
# 显示哈希表中的所有记录
hashtable.show()
# 将哈希表保存到文件中
hashtable.save()
```
需要注意的是,我们在程序开始时从文件中读取记录,并在程序结束时将哈希表保存到文件中。这样可以实现数据的持久化,下次运行程序时可以继续使用之前保存的数据。
阅读全文