用c++编写代码:1.定义长度为n的查找表,m个待查找数据,定义二叉树排序树的结点结构。2.初始化随机数发生器,产生n个随机数构成的查找表并用简单选择排序。3.创建顺序查找、折半查找、创建二叉排序树、二叉排序树查找,取得当前系统时间函数。4.调用顺序查找、折半查找、二叉排序树查找函数,输出在长度为n的查找表中,查找m个数据耗费的总时间。
时间: 2023-12-03 14:46:20 浏览: 88
以下是实现上述要求的C++代码:
```c++
#include <iostream>
#include <ctime>
using namespace std;
// 定义二叉排序树结点结构
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int v): val(v), left(nullptr), right(nullptr) {}
};
// 初始化查找表
void init(int arr[], int n) {
srand(time(nullptr));
for (int i = 0; i < n; i++) {
arr[i] = rand() % 100;
}
}
// 简单选择排序
void selectSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
int minIndex = i;
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr[i], arr[minIndex]);
}
}
// 顺序查找
int sequentialSearch(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
// 折半查找
int binarySearch(int arr[], int n, int target) {
int left = 0, right = n-1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
// 创建二叉排序树
void insert(TreeNode *&root, int val) {
if (root == nullptr) {
root = new TreeNode(val);
return;
}
if (val < root->val) {
insert(root->left, val);
} else {
insert(root->right, val);
}
}
// 二叉排序树查找
bool searchBST(TreeNode *root, int target) {
if (root == nullptr) {
return false;
}
if (root->val == target) {
return true;
} else if (root->val < target) {
return searchBST(root->right, target);
} else {
return searchBST(root->left, target);
}
}
int main() {
int n = 10; // 查找表长度
int m = 5; // 待查找数据个数
int arr[n];
init(arr, n);
selectSort(arr, n);
TreeNode *root = nullptr;
for (int i = 0; i < n; i++) {
insert(root, arr[i]);
}
int targets[m] = {10, 20, 30, 40, 50};
time_t start, end;
// 顺序查找
start = clock();
for (int i = 0; i < m; i++) {
sequentialSearch(arr, n, targets[i]);
}
end = clock();
cout << "Sequential search time: " << (double)(end-start)/CLOCKS_PER_SEC << "s" << endl;
// 折半查找
start = clock();
for (int i = 0; i < m; i++) {
binarySearch(arr, n, targets[i]);
}
end = clock();
cout << "Binary search time: " << (double)(end-start)/CLOCKS_PER_SEC << "s" << endl;
// 二叉排序树查找
start = clock();
for (int i = 0; i < m; i++) {
searchBST(root, targets[i]);
}
end = clock();
cout << "BST search time: " << (double)(end-start)/CLOCKS_PER_SEC << "s" << endl;
return 0;
}
```
这个程序会输出三个查找方法在查找5个数据时的耗时。可以根据需要修改变量n和m的值,增加或减少查找表长度和待查找数据个数。
阅读全文