创建三个python源文件,分别在其中编写 3 种算法的程序,具体如下: (1)打开包含英文单词的文件,读取其中所有的英文单词。 (2)将所有的英文单词依次存入一个顺序表 ST 中。 (3)由用户输入一个单词,分别利用顺序查找、折半查找和索引查找算法查找该单词。 (4)对这 3 种算法的性能进行比较。
时间: 2024-02-09 14:08:09 浏览: 57
我用Python写的一些算法
5星 · 资源好评率100%
好的,我明白了你的问题。这是一个编程题目,需要编写三个Python程序,分别实现三种不同的查找算法:顺序查找、折半查找和索引查找,并比较它们的性能。以下是我的回答:
首先,我们需要创建三个Python源文件,命名为sequential_search.py、binary_search.py和index_search.py。
其中,sequential_search.py文件中的代码如下:
```python
def sequential_search(word, word_list):
for i, w in enumerate(word_list):
if w == word:
return i
return -1
```
binary_search.py文件中的代码如下:
```python
def binary_search(word, word_list):
left, right = 0, len(word_list) - 1
while left <= right:
mid = (left + right) // 2
if word_list[mid] == word:
return mid
elif word_list[mid] < word:
left = mid + 1
else:
right = mid - 1
return -1
```
index_search.py文件中的代码如下:
```python
def index_search(word, word_list, index_list):
for i in range(len(index_list)):
if i == len(index_list) - 1 or word < index_list[i + 1]:
for j in range(index_list[i], index_list[i + 1]):
if word_list[j] == word:
return j
break
return -1
```
这三个文件分别实现了顺序查找、折半查找和索引查找三种算法。其中,sequential_search()函数使用顺序查找算法,在word_list中查找word;binary_search()函数使用折半查找算法,在已经排好序的word_list中查找word;index_search()函数使用索引查找算法,在使用索引index_list的word_list中查找word。
接下来,我们需要在一个主程序中调用这三个函数来进行单词查找,并比较它们的性能。主程序的代码如下:
```python
import sys
import time
# 打开包含英文单词的文件,读取其中所有的英文单词
with open(sys.argv[1], 'r') as f:
word_list = f.read().splitlines()
# 将所有的英文单词依次存入一个顺序表 ST 中
ST = sorted(word_list)
# 构建索引表
n = len(ST)
m = 1000
index_list = [i * (n // m) for i in range(m)] + [n]
# 由用户输入一个单词
word = input("请输入一个单词:")
# 分别利用顺序查找、折半查找和索引查找三种算法在 ST 中查找该单词,并计算运行时间
start_time = time.time()
sequential_res = sequential_search(word, ST)
sequential_time = time.time() - start_time
start_time = time.time()
binary_res = binary_search(word, ST)
binary_time = time.time() - start_time
start_time = time.time()
index_res = index_search(word, ST, index_list)
index_time = time.time() - start_time
# 输出查找结果和运行时间
if sequential_res != -1:
print("顺序查找:单词 %s 在列表中的位置是 %d,耗时 %.6f 秒" % (word, sequential_res, sequential_time))
else:
print("顺序查找:单词 %s 不在列表中,耗时 %.6f 秒" % (word, sequential_time))
if binary_res != -1:
print("折半查找:单词 %s 在列表中的位置是 %d,耗时 %.6f 秒" % (word, binary_res, binary_time))
else:
print("折半查找:单词 %s 不在列表中,耗时 %.6f 秒" % (word, binary_time))
if index_res != -1:
print("索引查找:单词 %s 在列表中的位置是 %d,耗时 %.6f 秒" % (word, index_res, index_time))
else:
print("索引查找:单词 %s 不在列表中,耗时 %.6f 秒" % (word, index_time))
```
这段程序首先打开包含英文单词的文件,并读取其中所有的英文单词。然后,将所有的英文单词依次存入一个顺序表ST中,并对ST进行排序。接着,程序构建索引表index_list,并等待用户输入一个单词。最后,程序分别使用顺序查找、折半查找和索引查找三种算法在ST中查找该单词,并计算运行时间。程序输出查找结果和运行时间。
运行程序时,需要将包含英文单词的文件名作为命令行参数传递给程序。例如,假设单词列表保存在words.txt文件中,可以使用以下命令运行程序:
```
python main.py words.txt
```
希望这个回答能够对你有所帮助!
阅读全文