给定无序序列{1,3,4,34,67,8,13,25,39,23,10,41,55,66,52,21,64,76,68,789,546,23,56,90,109,143,178,967,11,19}; 2.查找与输入的给定关键字相同的元素,使用指定的算法进行查找,若存在则输出找到的元素在序列中的位序(第一个数位序记为1)和需要进行的比较次数,不存在则输出"No",序列位序从1到n。 3.实现顺序查找和折半查找算法。c语言实现
时间: 2023-10-17 18:05:11 浏览: 168
CRNN文本识别.zip
好的,我可以为你提供C语言实现的顺序查找和折半查找算法。代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
// 顺序查找算法
int sequential_search(int nums[], int n, int key, int *num_comparisons) {
int i;
for (i = 0; i < n; i++) {
(*num_comparisons)++;
if (nums[i] == key) {
return i + 1;
}
}
return -1;
}
// 折半查找算法
int binary_search(int nums[], int n, int key, int *num_comparisons) {
int low = 0, high = n - 1, mid;
while (low <= high) {
(*num_comparisons)++;
mid = (low + high) / 2;
if (nums[mid] == key) {
return mid + 1;
} else if (nums[mid] > key) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
int main() {
int nums[] = {1, 3, 4, 34, 67, 8, 13, 25, 39, 23, 10, 41, 55, 66, 52, 21, 64, 76, 68, 789, 546, 23, 56, 90, 109, 143, 178, 967, 11, 19};
int n = sizeof(nums) / sizeof(nums[0]);
int key = 23;
int num_comparisons = 0;
// 调用顺序查找算法
int index = sequential_search(nums, n, key, &num_comparisons);
if (index == -1) {
printf("顺序查找算法:No\n");
} else {
printf("顺序查找算法:元素23在序列中的位序为%d,比较次数为%d。\n", index, num_comparisons);
}
// 调用折半查找算法
num_comparisons = 0;
int *sorted_nums = malloc(n * sizeof(int));
memcpy(sorted_nums, nums, n * sizeof(int));
qsort(sorted_nums, n, sizeof(int), cmp);
index = binary_search(sorted_nums, n, key, &num_comparisons);
free(sorted_nums);
if (index == -1) {
printf("折半查找算法:No\n");
} else {
printf("折半查找算法:元素23在序列中的位序为%d,比较次数为%d。\n", index, num_comparisons);
}
return 0;
}
```
这段代码中,我们先定义了两个函数:`sequential_search`和`binary_search`,分别对应顺序查找和折半查找算法。这两个函数都接受三个参数:一个整型数组`nums`,数组的长度`n`,以及需要查找的关键字`key`。`sequential_search`函数还有一个指向整数的指针`num_comparisons`,用于记录比较次数。这两个函数的返回值是找到的元素在序列中的位序,如果找不到则返回-1。
在`main`函数中,我们先定义了无序序列`nums`和需要查找的关键字`key`,然后分别调用了顺序查找和折半查找算法,并输出了结果。
需要注意的是,在调用折半查找算法之前,我们需要先将无序序列按照大小顺序排列,这里我们使用了C标准库中的`qsort`函数。在调用完毕之后,需要释放申请的内存。
希望这个C语言实现的例子能够帮助到你。
阅读全文