用c语言1.有A和B两个数组,A数组中存储500个2000以内的随机整数,B数组中存储10个2000以内的随机整数,完成以下操作: (1)用顺序查找算法显示B数组中每个元素在A数组中的位置,并返回该算法所用时间; (2)用折半查找算法显示B数组中每个元素在A数组中的位置,并返回该算法所用时间;
时间: 2024-03-26 21:35:48 浏览: 16
好的,下面是使用C语言实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// 定义顺序查找函数,返回元素在数组中的位置,如果未找到则返回-1
int sequential_search(int arr[], int len, int target) {
for (int i = 0; i < len; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
// 定义折半查找函数,返回元素在数组中的位置,如果未找到则返回-1
int binary_search(int arr[], int len, int target) {
int low = 0;
int high = len - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
int main() {
// 生成A和B数组
int A[500], B[10];
srand(time(NULL));
for (int i = 0; i < 500; i++) {
A[i] = rand() % 2000 + 1;
}
for (int i = 0; i < 10; i++) {
B[i] = rand() % 2000 + 1;
}
// 顺序查找
clock_t start_time = clock(); // 记录开始时间
for (int i = 0; i < 10; i++) {
int index = sequential_search(A, 500, B[i]);
printf("B[%d]在A中的位置为:%d\n", i, index);
}
clock_t end_time = clock(); // 记录结束时间
printf("顺序查找所用时间为:%lf秒\n", (double)(end_time - start_time) / CLOCKS_PER_SEC);
// 折半查找
qsort(A, 500, sizeof(int), compare); // 对A数组进行排序
start_time = clock(); // 记录开始时间
for (int i = 0; i < 10; i++) {
int index = binary_search(A, 500, B[i]);
printf("B[%d]在A中的位置为:%d\n", i, index);
}
end_time = clock(); // 记录结束时间
printf("折半查找所用时间为:%lf秒\n", (double)(end_time - start_time) / CLOCKS_PER_SEC);
return 0;
}
```
代码中,我们先定义了顺序查找函数`sequential_search`和折半查找函数`binary_search`,分别用于在数组中查找目标元素。然后,我们生成了A和B两个数组,使用`rand()`函数生成随机整数,并使用`clock()`函数记录时间。接下来,我们使用顺序查找和折半查找分别在A数组中查找B数组中的元素,并输出其位置。最后,我们使用`CLOCKS_PER_SEC`计算出每秒的时钟数,并计算出顺序查找和折半查找所用的时间。
需要注意的是,在使用折半查找前,我们需要先对A数组进行排序。因此,我们使用了标准库函数`qsort()`来对A数组进行排序,需要定义一个`compare()`函数作为比较规则。
希望这个答案能够解决您的问题。