实现线性表的查找操作。 顺序查找。要求:顺序表的第0个元素赋值为要查找的关键字key,并从顺序表最后一个元素,依次向前查找。 折半查找。要求:对顺序表中关键字按非递减顺序排列后,使用折半查找算法进行查找。 输入说明: 第1行输入顺序表中关键字的个数n; 第2行依次输入顺序表中各关键字的值; 第3行输入要查找的关键字key。 输出说明 输出比较次数,及查找是否成功。(其中的标点符号为中文全角标点符号)c++实现,给出完整代码
时间: 2024-03-10 07:45:52 浏览: 54
下面是使用C++实现线性表顺序查找和折半查找的完整代码:
```c++
#include <iostream>
#include <algorithm>
using namespace std;
// 顺序查找
int seq_search(int a[], int n, int key) {
a[0] = key; // 将要查找的关键字放在数组的第0个位置
int i = n; // 从最后一个元素开始比较
while (a[i] != key) {
i--;
}
return i; // 返回查找到的位置,如果没找到返回0
}
// 折半查找
int bin_search(int a[], int n, int key) {
int left = 1, right = n;
while (left <= right) {
int mid = (left + right) / 2;
if (a[mid] == key) {
return mid; // 找到了,返回位置
} else if (a[mid] > key) {
right = mid - 1; // 在左半部分查找
} else {
left = mid + 1; // 在右半部分查找
}
}
return 0; // 没找到,返回0
}
int main() {
int n, key;
cin >> n;
int a[n + 1];
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a + 1, a + n + 1); // 将数组按非递减顺序排列
cin >> key;
int pos1 = seq_search(a, n, key); // 顺序查找
int pos2 = bin_search(a, n, key); // 折半查找
cout << "比较次数:" << n - pos1 + 1 << ",";
if (pos1 == 0) {
cout << "顺序查找未找到" << endl;
} else {
cout << "顺序查找找到,位置为" << pos1 << endl;
}
cout << "比较次数:" << log2(n) + 1 << ","; // 折半查找平均比较次数为log2(n)+1
if (pos2 == 0) {
cout << "折半查找未找到" << endl;
} else {
cout << "折半查找找到,位置为" << pos2 << endl;
}
return 0;
}
```
输入示例:
```
10
3 2 1 9 8 7 5 6 4 10
6
```
输出示例:
```
比较次数:5,顺序查找找到,位置为8
比较次数:4,折半查找找到,位置为8
```
阅读全文