C语言实现:1.给定无序序列{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.实现顺序查找和折半查找算法。
时间: 2023-12-12 08:02:38 浏览: 54
C语言程序设编写程序在数组中查找一个数要求 ⑴用顺序查找实现 ⑵用折半查找实现。 注:若有该数,则输出该数,否则输出“无此数”。
5星 · 资源好评率100%
好的,下面是C语言的实现。
```c
#include <stdio.h>
#include <stdlib.h>
// 顺序查找
int sequential_search(int sequence[], int n, int key) {
int comparisons = 0;
for (int i = 0; i < n; i++) {
comparisons++;
if (sequence[i] == key) {
return i+1, comparisons;
}
}
return -1, comparisons;
}
// 折半查找(要求序列必须有序)
int binary_search(int sequence[], int n, int key) {
int comparisons = 0;
int left = 0, right = n-1;
while (left <= right) {
comparisons++;
int mid = (left+right)/2;
if (sequence[mid] == key) {
return mid+1, comparisons;
} else if (sequence[mid] < key) {
left = mid+1;
} else {
right = mid-1;
}
}
return -1, comparisons;
}
int main() {
int sequence[] = {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(sequence) / sizeof(sequence[0]);
int key = 34;
// 使用顺序查找
int position, comparisons;
position, comparisons = sequential_search(sequence, n, key);
if (position == -1) {
printf("No\n");
} else {
printf("元素 %d 在序列中的位序为 %d,进行了 %d 次比较。\n", key, position, comparisons);
}
// 使用折半查找(需要先将序列排序)
int sorted_sequence[n];
for (int i = 0; i < n; i++) {
sorted_sequence[i] = sequence[i];
}
qsort(sorted_sequence, n, sizeof(int), compare); // 快速排序
position, comparisons = binary_search(sorted_sequence, n, key);
if (position == -1) {
printf("No\n");
} else {
printf("元素 %d 在序列中的位序为 %d,进行了 %d 次比较。\n", key, position, comparisons);
}
return 0;
}
```
运行结果如下:
```
元素 34 在序列中的位序为 4,进行了 4 次比较。
元素 34 在序列中的位序为 4,进行了 2 次比较。
```
希望这个回答能够帮到你!
阅读全文