#include <iostream> #include <algorithm> using namespace std; // 顺序查找 int sequential_search(int* list, int size, int key) { int count = 0; for (int i = 0; i < size; i++) { count++; if (list[i] == key) { cout << "找到元素在 " << i+1 << ".比较次数:" << count << endl; return i; } } cout << "找不到元素。比较次数: " << count << endl; return -1; } // 折半查找 int binary_search(int* list, int left, int right, int key) { int count = 0; while (left <= right) { count++; int mid = (left + right) / 2; if (list[mid] == key) { cout << "找到元素在 " << mid+1 << ".比较次数:" << count << endl; return mid; } else if (list[mid] < key) { left = mid + 1; } else { right = mid - 1; } } cout << "找不到元素。比较次数: " << count << endl; return -1; } int main() { // 测试数据 int list1[] = {3, 6, 2, 10, 1, 8, 5, 7, 4, 9}; int list2[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int list3[] = {6, 14, 20, 25, 39, 59, 67, 78, 89, 96, 123}; int key1 = 5, key2 = 9, key3 = 9, key4 = 96, key5 = 97; // 顺序查找无序表 cout << "1\n"; sequential_search(list1, sizeof(list1)/sizeof(int), key1); // 顺序查找有序表 cout << "2\n"; sequential_search(list2, sizeof(list2)/sizeof(int), key2); // 折半查找有序表 cout << "3\n"; binary_search(list3, 0, sizeof(list3)/sizeof(int)-1, key3); // 顺序查找无序表 cout << "4\n"; sequential_search(list3, sizeof(list3)/sizeof(int), key4); sequential_search(list3, sizeof(list3)/sizeof(int), key5); // 折半查找有序表 cout << "5\n"; binary_search(list3, 0, sizeof(list3)/sizeof(int)-1, key4); binary_search(list3, 0, sizeof(list3)/sizeof(int)-1, key5); return 0; }
时间: 2024-04-20 10:27:12 浏览: 18
这是一段 C++ 代码,其中实现了顺序查找和折半查找两种查找算法。顺序查找是在无序表中按顺序逐个查找关键字,时间复杂度为 O(n);折半查找是在有序表中将表分成两半,每次将待查找的关键字与中间位置的关键字进行比较,从而缩小查找范围,时间复杂度为 O(log n)。代码中还定义了几个测试数据和关键字,可以用于测试两种算法的性能。
相关问题
#include <iostream> #include<algorithm> #include<cmath> #include <queue> using namespace std;
#include <iostream>:这是C++标准库中的头文件,用于输入输出流操作,包括cin、cout等。
#include<algorithm>:这是C++标准库中的头文件,用于提供各种算法操作,如排序、查找等。
#include<cmath>:这是C++标准库中的头文件,用于提供数学函数操作,如绝对值、平方根等。
#include <queue>:这是C++标准库中的头文件,用于提供队列操作,包括入队、出队等。
using namespace std;:这是C++的命名空间声明,表示使用std命名空间,可以直接使用std中的函数和对象。
#include <iostream> #include <queue> #include <string> using namespace std;对代码进行注释
代码注释如下:
```c++
#include <iostream> // 引入输入输出流库
#include <queue> // 引入队列库
#include <string> // 引入字符串库
using namespace std; // 使用 std 命名空间
// 主函数
int main() {
queue<string> q; // 定义一个字符串队列 q
// 往队列中添加元素
q.push("apple");
q.push("banana");
q.push("orange");
// 输出队列头部元素
cout << q.front() << endl; // 输出:apple
// 弹出队列头部元素
q.pop();
// 输出队列头部元素
cout << q.front() << endl; // 输出:banana
// 输出队列中元素的个数
cout << "The size of the queue is " << q.size() << endl; // 输出:The size of the queue is 2
return 0; // 返回 0 表示程序正常结束
}
```