在阅读英文文章时,经常会遇到不认识的单词,通常需要查询这些英文单词。现给定一份包含英文单词的文件,文件中的单词按照从“a”到“z”的顺序排列,由用户输入一个待查找的单词,请分别使用顺序查找、折半查找和索引查找算法来进行该单词的查找。 创建三个python源文件,分别在其中编写 3 种算法的程序,具体如下: (1)打开包含英文单词的文件,读取其中所有的英文单词。 (2)将所有的英文单词依次存入一个顺序表 ST 中。 (3)由用户输入一个单词,分别利用顺序查找、折半查找和索引查找算法查找该单词。 (4)对这 3 种算法的性能进行比较。
时间: 2024-02-09 09:12:52 浏览: 27
好的,我明白了。这是三个算法的 Python 实现。首先是顺序查找,它的时间复杂度是 O(n)。
```python
def sequential_search(word_list, target):
for i in range(len(word_list)):
if word_list[i] == target:
return i
return -1
```
然后是折半查找,它的时间复杂度是 O(log n)。
```python
def binary_search(word_list, target):
low = 0
high = len(word_list) - 1
while low <= high:
mid = (low + high) // 2
if word_list[mid] == target:
return mid
elif word_list[mid] > target:
high = mid - 1
else:
low = mid + 1
return -1
```
最后是索引查找,它的时间复杂度是 O(1)。
```python
import string
def index_search(word_list, target):
index = {}
for i in range(len(word_list)):
first_letter = word_list[i][0]
if first_letter not in index:
index[first_letter] = i
if target[0] not in index:
return -1
start = index[target[0]]
for i in range(start, len(word_list)):
if word_list[i] == target:
return i
elif word_list[i][0] != target[0]:
return -1
return -1
```
我们可以在主函数中使用这些函数来测试算法的性能。
```python
import time
def main():
with open('words.txt', 'r') as f:
word_list = f.read().split('\n')
word_list = [word.lower() for word in word_list]
target = input('Enter a word to search: ').lower()
start_time = time.time()
index = sequential_search(word_list, target)
end_time = time.time()
print('Sequential search: ', end_time - start_time, 'seconds')
if index == -1:
print('Word not found')
else:
print('Word found at index', index)
start_time = time.time()
index = binary_search(word_list, target)
end_time = time.time()
print('Binary search: ', end_time - start_time, 'seconds')
if index == -1:
print('Word not found')
else:
print('Word found at index', index)
start_time = time.time()
index = index_search(word_list, target)
end_time = time.time()
print('Index search: ', end_time - start_time, 'seconds')
if index == -1:
print('Word not found')
else:
print('Word found at index', index)
if __name__ == '__main__':
main()
```
这样就可以测试三种算法的性能了。顺序查找对于较小的数据集来说很有效,但对于大型数据集来说会很慢。折半查找在大型数据集上的表现要比顺序查找好得多,但它要求数据集是有序的。索引查找需要花费额外的时间来构建索引,但一旦索引建立完成,查找就可以在常数时间内完成。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![py](https://img-home.csdnimg.cn/images/20210720083646.png)
![ppt](https://img-home.csdnimg.cn/images/20210720083527.png)