给定无序序列{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}; 查找与输入的给定关键字相同的元素,使用指定的算法进行查找,若存在则输出找到的元素在序列中的位序(第一个数位序记为1)和需要进行的比较次数,不存在则输出"No",序列位序从1到n,实现顺序查找和折半查找算法。c语言实现
时间: 2023-10-25 11:09:51 浏览: 77
好的,我会根据你的要求回答你的问题,以下是C语言实现顺序查找和折半查找算法的代码:
```c
#include<stdio.h>
// 顺序查找算法
int SeqSearch(int arr[], int n, int key, int *cnt)
{
int i;
for(i = 0; i < n; i++)
{
(*cnt)++;
if(arr[i] == key)
{
return i + 1; // 返回元素在序列中的位序
}
}
return -1; // 表示没有找到
}
// 折半查找算法
int BinarySearch(int arr[], int n, int key, int *cnt)
{
int low = 0;
int high = n - 1;
int mid;
while(low <= high)
{
(*cnt)++;
mid = (low + high) / 2;
if(key == arr[mid])
{
return mid + 1; // 返回元素在序列中的位序
}
else if(key < arr[mid])
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
return -1; // 表示没有找到
}
int main()
{
int arr[] = {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(arr) / sizeof(arr[0]);
int key;
int cnt = 0, ret;
printf("请输入要查找的关键字:");
scanf("%d", &key);
// 顺序查找
ret = SeqSearch(arr, n, key, &cnt);
if(ret == -1)
{
printf("No\n");
}
else
{
printf("顺序查找:元素%d在序列中的位序是%d,需要进行%d次比较\n", key, ret, cnt);
}
// 折半查找
cnt = 0;
ret = BinarySearch(arr, n, key, &cnt);
if(ret == -1)
{
printf("No\n");
}
else
{
printf("折半查找:元素%d在序列中的位序是%d,需要进行%d次比较\n", key, ret, cnt);
}
return 0;
}
```
注意,在顺序查找算法和折半查找算法中,我使用了一个指针参数`cnt`,来记录比较次数。这个指针参数的作用是,在函数中更新比较次数的计数器,最终返回的比较次数就是指针所指向的变量的值。
阅读全文