数据结构实验七 查找
- 格式：pdf
- 大小：67.28 KB
- 文档页数：7
数据结构实验七 查找
数据结构实验七 查找
一、实验目的
本实验旨在通过实际操作和编程实现不同查找算法，并对其进行性能比较。
二、实验内容
1.线性查找算法
2.二分查找算法
3.插值查找算法
4.哈希查找算法
三、线性查找算法
线性查找算法是最简单的查找算法之一，它的基本思想是从第一个元素开始逐个比较，直到找到目标元素或遍历完整个数组。
1.算法步骤：
●从数组的第一个元素开始遍历，比较当前元素与目标元素是否相等。
●如果相等，则查找成功，返回当前元素的索引。 ●如果不相等，继续遍历下一个元素，重复上述步骤，直到遍历完整个数组。
●如果遍历完数组仍未找到目标元素，则查找失败，返回.1.
2.算法示例代码（Python）：
```
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return .1
```
四、二分查找算法
二分查找算法适用于有序数组，它通过每次将目标值与数组的中间元素进行比较，并根据比较结果缩小搜索范围。
1.算法步骤：
●初始化左边界为数组的第一个元素的索引，右边界为数组的最后一个元素的索引。 ●在每一次循环中，找到数组中间元素的索引（mid）。
●将目标值与中间元素进行比较：
●如果相等，则查找成功，返回中间元素的索引。
●如果目标值大于中间元素，则说明目标值在中间元素的右侧，将左边界更新为mid + 1.
●如果目标值小于中间元素，则说明目标值在中间元素的左侧，将右边界更新为mid ●1.
●重复上述步骤，直到左边界大于右边界，表示查找失败。
2.算法示例代码（Python）：
```
def binary_search(arr, target):
left = 0
right = len(arr) ●1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid elif arr[mid] < target:
left = mid + 1
else:
right = mid ●1
return .1
```
五、插值查找算法
插值查找算法是对二分查找算法的改进，它通过根据目标值在数组中的分布情况，更准确地预测目标值的位置，从而提高查找效率。
1.算法步骤：
●计算插值公式：
●pos = left + (right ●left) (target ●arr[left]) / (arr[right] ●arr[left])
●如果目标值等于arr[pos]，则查找成功，返回pos。
●如果目标值小于arr[pos]，则说明目标值在左侧，更新right为pos ●1. ●如果目标值大于arr[pos]，则说明目标值在右侧，更新left为pos + 1.
●重复上述步骤，直到查找成功或左边界大于右边界，表示查找失败。
2.算法示例代码（Python）：
```
def interpolation_search(arr, target):
left = 0
right = len(arr) ●1
while left <= right and arr[left] <= target <= arr[right]:
pos = left + (right ●left) (target ●arr[left]) // (arr[right] ●arr[left])
if arr[pos] == target:
return pos
elif arr[pos] < target:
left = pos + 1
else: right = pos ●1
return .1
```
六、哈希查找算法
哈希查找算法利用哈希函数将目标值映射到数组的索引，从而快速找到目标值。
1.算法步骤：
●建立哈希表，将数组中的元素进行哈希计算，并将结果存储在对应的索引位置。
●通过哈希函数计算目标值的索引。
●在目标值的索引位置进行查找，如果找到目标值，则查找成功。
●如果目标值的索引位置为空或不等于目标值，说明目标值不存在。
2.算法示例代码（Python）：
```
def hash_search(arr, target):
hash_table = [None] len(arr) for i in range(len(arr)):
index = arr[i] % len(arr)
while hash_table[index] is not None:
index = (index + 1) % len(arr)
hash_table[index] = arr[i]
index = target % len(arr)
while hash_table[index] is not None:
if hash_table[index] == target:
return index
index = (index + 1) % len(arr)
return .1
```
七、附件
本文档不涉及任何附件。
八、法律名词及注释
本文档不涉及任何法律名词及注释。
