.给定无序序列{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 12:05:19 浏览: 33
好的,以下是实现顺序查找和折半查找算法的完整 C++ 代码:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 顺序查找算法
pair<int, int> sequentialSearch(vector<int>& lst, int key) {
for (int i = 0; i < lst.size(); i++) {
if (lst[i] == key) {
return {i+1, i+1};
}
}
return {"No", 0};
}
// 折半查找算法
pair<int, int> binarySearch(vector<int>& lst, int key) {
sort(lst.begin(), lst.end()); // 折半查找前要先将序列排序
int left = 0, right = lst.size()-1, count = 0;
while (left <= right) {
int mid = (left+right) / 2;
if (lst[mid] == key) {
return {mid+1, count+1};
} else if (lst[mid] > key) {
right = mid - 1;
} else {
left = mid + 1;
}
count++;
}
return {"No", count};
}
int main() {
vector<int> lst = {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 key = 23;
// 顺序查找
cout << "输入关键字:" << key << endl;
auto result1 = sequentialSearch(lst, key);
if (result1.first == "No") {
cout << "顺序查找结果:" << result1.first << endl;
} else {
cout << "顺序查找结果:元素" << key << "位于序列的第" << result1.first << "位,进行了" << result1.second << "次比较" << endl;
}
// 折半查找
cout << "输入关键字:" << key << endl;
auto result2 = binarySearch(lst, key);
if (result2.first == "No") {
cout << "折半查找结果:" << result2.first << endl;
} else {
cout << "折半查找结果:元素" << key << "位于序列的第" << result2.first << "位,进行了" << result2.second << "次比较" << endl;
}
return 0;
}
```
注意,为了方便输出,我将结果改成了 pair 类型,第一个元素表示查找到的元素在序列中的位序,第二个元素表示需要进行的比较次数。同时,顺序查找和折半查找的实现方式也略有不同。