创建三个python源文件,分别在其中编写 3 种算法的程序,具体如下: (1)打开包含英文单词的文件,读取其中所有的英文单词。 (2)将所有的英文单词依次存入一个顺序表 ST 中。 (3)由用户输入一个单词,分别利用顺序查找、折半查找和索引查找算法查找该单词。 (4)对这 3 种算法的性能进行比较。
时间: 2024-02-09 09:08:10 浏览: 58
好的,我会按照你的要求回答问题。首先,针对你的问题,我需要说明一下,作为一个AI,我无法直接创建文件和编写程序。但是,我可以提供给你一些思路和代码示例,帮助你完成这个任务。
首先,我们需要一个包含英文单词的文件,可以使用Python中的open函数打开文件,并使用readlines方法读取文件中的所有行,然后使用split方法将每一行拆分为一个列表,最后使用extend方法将所有列表合并成一个列表,即可得到所有的英文单词。具体代码如下:
```python
with open('words.txt', 'r') as f:
words = []
for line in f.readlines():
words.extend(line.strip().split())
```
接下来,我们需要将所有的单词存入一个顺序表ST中。可以使用Python中的列表来实现顺序表。具体代码如下:
```python
ST = words
```
然后,由用户输入一个单词,我们需要分别利用顺序查找、折半查找和索引查找算法查找该单词。具体代码如下:
```python
# 顺序查找
def sequential_search(ST, x):
for i in range(len(ST)):
if ST[i] == x:
return i
return -1
# 折半查找
def binary_search(ST, x):
left, right = 0, len(ST) - 1
while left <= right:
mid = (left + right) // 2
if ST[mid] == x:
return mid
elif ST[mid] < x:
left = mid + 1
else:
right = mid - 1
return -1
# 索引查找
def index_search(ST, x):
index = {}
for i in range(len(ST)):
key = ST[i][0]
if key not in index:
index[key] = i
if x[0] not in index:
return -1
start = index[x[0]]
end = len(ST) - 1 if x[0] == 'z' else index[chr(ord(x[0]) + 1)] - 1
for i in range(start, end + 1):
if ST[i] == x:
return i
return -1
word = input('请输入要查找的单词:')
print('顺序查找结果:', sequential_search(ST, word))
print('折半查找结果:', binary_search(ST, word))
print('索引查找结果:', index_search(ST, word))
```
最后,对这 3 种算法的性能进行比较,可以使用Python中的time模块来计算程序运行的时间。具体代码如下:
```python
import time
word = input('请输入要查找的单词:')
start_time = time.time()
sequential_search(ST, word)
end_time = time.time()
print('顺序查找时间:', end_time - start_time)
start_time = time.time()
binary_search(ST, word)
end_time = time.time()
print('折半查找时间:', end_time - start_time)
start_time = time.time()
index_search(ST, word)
end_time = time.time()
print('索引查找时间:', end_time - start_time)
```
这样就完成了三种算法的实现,你可以根据自己的需要进行修改和完善。
阅读全文