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.实现顺序查找和折半查找算法(c语言)。
时间: 2023-10-21 22:05:19 浏览: 89
67.Python之访问set共2页.pdf.zip
好的,您的问题已经收到了。以下是我的回答:
首先,针对您的问题2,我需要先解释一下顺序查找和折半查找算法的原理。
顺序查找算法:
顺序查找也称为线性查找,它是最简单、最基本的查找算法。顺序查找的思路就是从第一个元素开始,一直查找到最后一个元素,直到找到与给定关键字相同的元素为止。顺序查找的优点在于不需要对序列进行任何预处理,但是在最坏情况下,需要比较n次才能找到目标元素。
折半查找算法:
折半查找也称为二分查找,它是一种效率较高的查找算法。折半查找的思路是将序列分成两部分,如果目标元素小于序列的中间元素,则在左半部分继续查找;反之,在右半部分继续查找。每次查找都可以将待查找的序列长度缩小一半。折半查找的优点在于查找速度快,但是要求序列必须是有序的。
接下来,针对您的问题3,我提供以下C语言代码实现:
顺序查找算法:
```c
#include <stdio.h>
int seq_search(int a[], int n, int key, int* count) {
int i;
for (i = 0; i < n; i++) {
(*count)++;
if (a[i] == key)
return i + 1;
}
return -1;
}
int main() {
int a[] = {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(a) / sizeof(a[0]);
int key = 34;
int count = 0;
int pos = seq_search(a, n, key, &count);
if (pos != -1) {
printf("元素 %d 在序列中的位序为 %d,比较次数为 %d\n", key, pos, count);
}
else {
printf("元素 %d 不存在于序列中\n", key);
}
return 0;
}
```
折半查找算法:
```c
#include <stdio.h>
int bin_search(int a[], int n, int key, int* count) {
int low = 0, high = n - 1, mid;
while (low <= high) {
(*count)++;
mid = (low + high) / 2;
if (a[mid] == key)
return mid + 1;
else if (a[mid] > key)
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
int main() {
int a[] = {1, 3, 4, 8, 10, 13, 21, 23, 23, 25, 34, 39, 41, 52, 55, 56, 64, 66, 67, 68, 76, 90, 109, 143, 178, 546, 789, 967};
int n = sizeof(a) / sizeof(a[0]);
int key = 34;
int count = 0;
int pos = bin_search(a, n, key, &count);
if (pos != -1) {
printf("元素 %d 在序列中的位序为 %d,比较次数为 %d\n", key, pos, count);
}
else {
printf("元素 %d 不存在于序列中\n", key);
}
return 0;
}
```
以上是我的回答,希望能够帮助到您。
阅读全文