在阅读英文文章时,经常会遇到不认识的单词,通常需要查询这些英文单词。现给定一份包含英文单词的文件,文件中的单词按照从“a”到“z”的顺序排列,由用户输入一个待查找的单词,请分别使用顺序查找、折半查找和索引查找算法来进行该单词的查找。 创建三个python源文件,分别在其中编写 3 种算法的程序,具体如下: (1)打开包含英文单词的文件,读取其中所有的英文单词。 (2)将所有的英文单词依次存入一个顺序表 ST 中。 (3)由用户输入一个单词,分别利用顺序查找、折半查找和索引查找算法查找该单词。 (4)对这 3 种算法的性能进行比较
时间: 2024-02-09 16:13:06 浏览: 121
对于这个问题,我可以为您提供一些思路和代码示例,但由于我是一个语言模型 AI,不能直接创建文件,所以您需要手动创建这 3 个 python 源文件。
首先是顺序查找的程序,代码如下:
```python
# 顺序查找算法
def sequential_search(word, words):
for i in range(len(words)):
if word == words[i]:
return i
return -1
# 读取文件中的单词
with open("words.txt", "r") as f:
words = f.read().split()
# 用户输入要查找的单词
word = input("请输入要查找的单词:")
# 进行顺序查找
index = sequential_search(word, words)
# 输出查找结果
if index == -1:
print("未找到该单词!")
else:
print("该单词在文件中的位置为:", index)
```
接下来是折半查找的程序,代码如下:
```python
# 折半查找算法
def binary_search(word, words):
low = 0
high = len(words) - 1
while low <= high:
mid = (low + high) // 2
if word == words[mid]:
return mid
elif word < words[mid]:
high = mid - 1
else:
low = mid + 1
return -1
# 读取文件中的单词
with open("words.txt", "r") as f:
words = f.read().split()
# 用户输入要查找的单词
word = input("请输入要查找的单词:")
# 进行折半查找
index = binary_search(word, words)
# 输出查找结果
if index == -1:
print("未找到该单词!")
else:
print("该单词在文件中的位置为:", index)
```
最后是索引查找的程序,代码如下:
```python
# 索引查找算法
def index_search(word, words, index):
for i in range(len(index)-1):
if word >= index[i] and word < index[i+1]:
for j in range(i*10, (i+1)*10):
if word == words[j]:
return j
return -1
for i in range((len(words)//10)*10, len(words)):
if word == words[i]:
return i
return -1
# 读取文件中的单词
with open("words.txt", "r") as f:
words = f.read().split()
# 构建索引
index = []
for i in range(0, len(words), 10):
index.append(words[i])
# 用户输入要查找的单词
word = input("请输入要查找的单词:")
# 进行索引查找
index = index_search(word, words, index)
# 输出查找结果
if index == -1:
print("未找到该单词!")
else:
print("该单词在文件中的位置为:", index)
```
至于三种算法的性能比较,可以通过计算它们的时间复杂度来得到。顺序查找的时间复杂度是 O(n),折半查找的时间复杂度是 O(log n),索引查找的时间复杂度是 O(n/m + m),其中 m 是索引的大小。因此,在单词数量较少的情况下,顺序查找可能更快;在单词数量较大的情况下,折半查找和索引查找可能更快。
阅读全文