//折半查找 #include<iostream> #include<fstream> #include<string> #include <algorithm> using namespace std; #define MAXSIZE 10000 #define KEYSIZE 10//关键词个数 #define OK 0 #define ERROR -1 typedef string KeyType; typedef struct { KeyType key;//关键字域 int count;//词频 int index;//在关键词列表中的序号 }ElemType; typedef struct { ElemType *R;//存储空间基地址 int length;//当前长度 }SSTable; //关键词列表 KeyType key[KEYSIZE] = {"little","prince","sheep","flowers","believe","stars","one","my","he","the"}; //初始化一个空的查找表ST //ST的0号单元闲置不用 int InitSSTable(SSTable &ST) { /*-----------代码开始--------------*/ /*-----------代码结束--------------*/ return OK; }

折半查找（二分查找）是一种高效的查找算法，它要求待查找的序列必须是有序的。它的基本思想是：首先确定待查找区间的中间位置，然后将待查找关键字与中间位置关键字进行比较，如果相等则查找成功；否则根据比较结果确定下一步查找的区间，直到找到所需的关键字或者区间为空为止。

在代码中，SSTable是一个结构体，它包含了一个关键字数组和一些其他的属性，如当前长度等。InitSSTable函数的作用是初始化一个空的查找表ST，即将ST中的R指向一个新分配的空间，并将其长度初始化为0。

相关问题

#include <iostream>#include <random>#include <vector>int main() { int n = 1000; // 产生1000个随机整数 int k = 123; // 待查找的目标值 std::vector<int> data(n); // 存储随机整数的容器 // 使用随机数生成器生成n个随机整数 std::random_device rd; std::mt19937 gen(rd()); std::uniform_int_distribution<> dis(1, 1000); for (int i = 0; i < n; ++i) { data[i] = dis(gen); } // 顺序查找 clock_t start, finish; start = clock(); for (int i = 0; i < n; ++i) { if (data[i] == k) { break; } } finish = clock(); std::cout << "顺序查找所用时间：" << (double)(finish - start) / CLOCKS_PER_SEC << "s" << std::endl; // 折半查找 std::sort(data.begin(), data.end()); // 对数据进行排序 start = clock(); int left = 0, right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; if (data[mid] == k) { break; } else if (data[mid] < k) { left = mid + 1; } else { right = mid - 1; } } finish = clock(); std::cout << "折半查找所用时间：" << (double)(finish - start) / CLOCKS_PER_SEC << "s" << std::endl; return 0;}为什么返回时间都是0

这段代码的问题在于使用 clock() 函数来计时时，返回的时间单位是时钟周期（clock ticks），而不是秒。因此，当计时非常短的时候，可能会返回0。这就是为什么你的代码返回时间都是0的原因。

解决这个问题的方法是使用更精确的计时方法，例如使用 std::chrono 库中的 high_resolution_clock。具体做法是：

1. 在代码开头添加头文件 #include <chrono>
2. 将 clock_t 类型的变量 start 和 finish 改为 std::chrono::time_point<std::chrono::high_resolution_clock> 类型。
3. 在需要计时的地方使用高精度计时方法，例如 start = std::chrono::high_resolution_clock::now();
4. 计算时间差时，使用 std::chrono::duration_cast<std::chrono::duration<double>> 类型将时间差转换为秒。
5. 输出时间时，使用 std::chrono::duration<double> 类型的 count() 函数。

下面是修改后的代码示例：

#include <iostream>
#include <random>
#include <vector>
#include <chrono>

int main() {
    int n = 1000; // 产生1000个随机整数
    int k = 123; // 待查找的目标值
    std::vector<int> data(n); // 存储随机整数的容器
    // 使用随机数生成器生成n个随机整数
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(1, 1000);
    for (int i = 0; i < n; ++i) {
        data[i] = dis(gen);
    }
    // 顺序查找
    std::chrono::time_point<std::chrono::high_resolution_clock> start, finish;
    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < n; ++i) {
        if (data[i] == k) {
            break;
        }
    }
    finish = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> elapsed = finish - start;
    std::cout << "顺序查找所用时间：" << elapsed.count() << "s" << std::endl;
    // 折半查找
    std::sort(data.begin(), data.end()); // 对数据进行排序
    start = std::chrono::high_resolution_clock::now();
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (data[mid] == k) {
            break;
        } else if (data[mid] < k) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    finish = std::chrono::high_resolution_clock::now();
    elapsed = finish - start;
    std::cout << "折半查找所用时间：" << elapsed.count() << "s" << std::endl;
    return 0;
}

这样修改后，你应该可以正确地得到计时结果了。

#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; }

这是一段 C++ 代码，其中实现了顺序查找和折半查找两种查找算法。顺序查找是在无序表中按顺序逐个查找关键字，时间复杂度为 O(n)；折半查找是在有序表中将表分成两半，每次将待查找的关键字与中间位置的关键字进行比较，从而缩小查找范围，时间复杂度为 O(log n)。代码中还定义了几个测试数据和关键字，可以用于测试两种算法的性能。