设计一个算法,输出在顺序表{8,14,6,9,10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,100,94,88,96,87}中采用分块查找法查找(每块的块长为5,共有5块)关键字46的过程
时间: 2024-05-20 07:12:12 浏览: 17
分块查找法是一种在有序表中进行查找的算法,它将有序表分成若干块,每块内部是有序的,块与块之间是无序的。在查找时,先确定要查找的元素在哪个块内,然后在该块内采用顺序查找或折半查找的方法进行查找。
在本题中,顺序表有 24 个元素,每块的块长为 5,共有 5 块。我们可以将顺序表按照块长进行分块,得到以下各块:
块0:{8,14,6,9,10}
块1:{22,34,18,19,31}
块2:{40,38,54,66,46}
块3:{71,78,68,80,85}
块4:{100,94,88,96,87}
首先需要确定要查找的元素 46 位于第几块。由于每块内部是有序的,块与块之间是无序的,因此可以通过比较块内最后一个元素和要查找的元素的大小来确定要查找的元素在哪个块内。在本题中,要查找的元素 46 大于块 1 最后一个元素 31,小于块 2 最后一个元素 46,因此要查找的元素位于块 2。
接下来,在块 2 内部采用顺序查找或折半查找的方法进行查找。由于块内只有 5 个元素,可以直接采用顺序查找的方法。在块 2 中查找 46,需要进行 5 次比较才能找到。
因此,采用分块查找法查找关键字 46 的过程如下:
1. 根据块长将顺序表分成 5 块。
2. 确定要查找的元素 46 位于第 2 块。
3. 在第 2 块内部采用顺序查找的方法,比较 5 次后找到了关键字 46。
相关问题
写出代码;输出在顺序表(8,14,6,9,10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,100,94,88,96,87)中采用分块查找方法查找(每块块长为5,共有5块)关键字46的过程
分块查找方法的核心是将待查找的元素集合分成若干个块,每个块内部元素无序,但是块与块之间按照一定的顺序排列。这样可以在块内部采用顺序查找,块与块之间则采用二分查找或者其他高效的查找算法。下面是采用Python语言实现分块查找算法的代码:
```python
def block_search(arr, target):
block_size = 5
n = len(arr)
block_num = (n + block_size - 1) // block_size
# 计算每个块的边界
block_boundaries = [i * block_size for i in range(block_num)]
block_boundaries.append(n)
# 二分查找每个块的起始位置
block_starts = []
for i in range(block_num):
start = block_boundaries[i]
end = block_boundaries[i+1]
if start == end:
break
mid = (start + end) // 2
while mid > 0 and arr[mid-1] == arr[mid]:
mid -= 1
block_starts.append(mid)
# 在块内部采用顺序查找
for i in range(block_num):
if block_starts[i] == n:
break
start = block_boundaries[i]
end = block_boundaries[i+1]
if target < arr[start] or target > arr[end-1]:
continue
for j in range(start, end):
if arr[j] == target:
return j
return -1
arr = [8, 14, 6, 9, 10, 22, 34, 18, 19, 31, 40, 38, 54, 66, 46, 71, 78, 68, 80, 85, 100, 94, 88, 96, 87]
target = 46
index = block_search(arr, target)
if index != -1:
print("找到了,索引为:", index)
else:
print("没找到!")
```
输出结果为:
```
找到了,索引为: 14
```
说明在顺序表中采用分块查找方法查找关键字46的过程中,先将整个序列分成了5个块,每个块的长度为5,然后在块内部采用顺序查找,在第3个块(包含元素46)中查找到了目标元素,其在整个序列中的索引为14。
顺序表实验内容 1 初始化并建立顺序表。 (开辟的存储空间大小为8) 2.给定的线性表为L=(12,25,7,42,19,38)元素由键盘输入。 甲 3 编写顺序表输出算法。 4.依次插入3、21、15、99四个数,分别插入在第1、8、4和12位置,每插入一次都要输出一次 顺序表。 5.删除第1,第9和第12个位置上的元素,每删除一个元素都要输出一次顺序表。 6.编写一个排序算法,对线性表中元素从小到大排列。 7 向有序表分别插入20和50插入后表仍然有序。(修改开辟的存储空间大小为15)
实验步骤:
1. 初始化并建立顺序表,开辟的存储空间大小为8。
2. 从键盘输入元素,建立线性表。将输入的元素依次存储到顺序表中。
3. 编写顺序表输出算法。遍历顺序表,输出每个元素的值。
4. 依次插入3、21、15、99四个数,分别插入在第1、8、4和12位置,每插入一次都要输出一次顺序表。先遍历顺序表找到插入位置,然后将后面的元素依次后移,最后将要插入的元素插入到空出来的位置。插入后输出顺序表。
5. 删除第1、第9和第12个位置上的元素,每删除一个元素都要输出一次顺序表。先遍历顺序表找到要删除的位置,然后将后面的元素依次前移,最后将最后一个元素删除。删除后输出顺序表。
6. 编写一个排序算法,对线性表中元素从小到大排列。使用冒泡排序算法,每次比较相邻的两个元素,如果前面的元素大于后面的元素,就交换它们的位置。重复执行,直到排序完成。
7. 向有序表分别插入20和50插入后表仍然有序。(修改开辟的存储空间大小为15)。先判断表是否已满,如果已满则重新开辟空间。然后遍历有序表,找到插入位置。将后面的元素依次后移,最后将要插入的元素插入到空出来的位置。插入后输出有序表。
注意事项:
1. 在编写程序时,要注意数组下标的起始值是0,而不是1。
2. 在插入或删除元素时,要注意顺序表的长度变化,以及是否需要重新开辟空间。
3. 在排序时,要注意判断表的长度是否为0或1,以免出现数组越界的情况。
4. 在输出顺序表或有序表时,要注意格式的美观和清晰。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.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)