设每个记录有下列数据项:电话号码、用户名、住址。从键盘输入各记录,以用户名为关键字建立哈希表,哈希函数用除留取余数法构造,采用线性探测法解决冲突。可以插入、查找、删除并显示给定用户名的记录, 显示哈希表,哈希表保存到文件中。测试数据:取某个单位电话号码簿中的30 个记录。
时间: 2024-02-01 18:16:00 浏览: 78
好的,这个问题需要编写一个哈希表的程序来实现。以下是 Python 代码示例:
```python
class Record:
def __init__(self, phone_number, user_name, address):
self.phone_number = phone_number
self.user_name = user_name
self.address = address
class HashTable:
def __init__(self, size):
self.size = size
self.table = [None] * size
def hash_function(self, user_name):
return sum([ord(c) for c in user_name]) % self.size
def insert(self, record):
index = self.hash_function(record.user_name)
while self.table[index] is not None:
if self.table[index].user_name == record.user_name:
return
index = (index + 1) % self.size
self.table[index] = record
def search(self, user_name):
index = self.hash_function(user_name)
while self.table[index] is not None:
if self.table[index].user_name == user_name:
return self.table[index]
index = (index + 1) % self.size
return None
def delete(self, user_name):
index = self.hash_function(user_name)
while self.table[index] is not None:
if self.table[index].user_name == user_name:
self.table[index] = None
return
index = (index + 1) % self.size
def display(self):
for i in range(self.size):
if self.table[i] is not None:
print(f"{i}: {self.table[i].phone_number}, {self.table[i].user_name}, {self.table[i].address}")
def save_to_file(self, file_name):
with open(file_name, "w") as f:
for i in range(self.size):
if self.table[i] is not None:
f.write(f"{self.table[i].phone_number},{self.table[i].user_name},{self.table[i].address}\n")
```
上述代码中,`Record` 类表示一个记录,包含电话号码、用户名和住址三个数据项。`HashTable` 类表示哈希表,包含一个大小和一个数组 `table`。`table` 数组中的每个元素要么为 `None`,要么为一个 `Record` 对象。`HashTable` 类提供了插入、查找、删除、显示和保存到文件等功能。其中,`hash_function` 方法用于根据用户名计算哈希值,采用的是除留取余数法。如果哈希值对应的位置已经有元素了,就采用线性探测法解决冲突,即向后查找空位置。`display` 方法用于显示哈希表中的所有元素,`save_to_file` 方法用于将哈希表保存到文件中。
下面是一个简单的测试代码,可以读入 30 个记录并插入哈希表中,然后进行一些查询和删除操作:
```python
if __name__ == "__main__":
table = HashTable(50)
with open("data.txt", "r") as f:
for line in f:
data = line.strip().split(",")
record = Record(data[0], data[1], data[2])
table.insert(record)
table.display()
while True:
user_name = input("Enter user name: ")
if user_name == "quit":
break
record = table.search(user_name)
if record is None:
print("Record not found.")
else:
print(f"Phone number: {record.phone_number}")
print(f"Address: {record.address}")
action = input("Do you want to delete this record? (y/n) ")
if action.lower() == "y":
table.delete(user_name)
table.display()
table.save_to_file("output.txt")
```
上述代码从文件 `data.txt` 中读入 30 个记录,并插入到哈希表中。然后进入一个循环,等待用户输入用户名。如果用户名存在于哈希表中,就显示电话号码和住址,并询问用户是否要删除该记录。如果用户输入了 "y",就将该记录从哈希表中删除。最后,显示哈希表中的所有元素,并将哈希表保存到文件 `output.txt` 中。
阅读全文