有序表随机化查找完整代码

好的，下面是一个实现了有序表随机化查找的完整代码，供您参考：

#include <iostream>
#include <iomanip>
#include <cmath>
#include <chrono>
#include "RandomNumber.h"
using namespace std;

template<class Type>
class OrderList{
public:
    OrderList(Type small, Type large, int MaxL);
    ~OrderList();
    int Search(Type x, int& index); // 查找元素x，返回查找次数,index存储查找到的位置,如果未查到，返回0
    int SearchLast(void); // 返回有序表中的最后一个元素的位置
    void Insert(Type k);
    void Delete(Type k);
    void Output(); // 输出有序表
    void OutList(); // 输出有序序列
    int Size() { return n; }
private:
    int n; // 有序表元素个数
    int MaxLength; // 有序表容量
    Type* value; // 值序列
    int* link; // 链接序列
    RandomNumber rnd; // 随机数，用于查找
    Type Small; // 最小值
    Type TailKey; // 无穷大
};

template<class Type>
OrderList<Type>::OrderList(Type small, Type large, int MaxL) :Small(small), TailKey(large + 1), rnd((unsigned)time(0)) {
    MaxLength = MaxL + 1;
    value = new Type[MaxLength];
    link = new int[MaxLength];
    link[0] = 0;
    n = 0;
}

template<class Type>
OrderList<Type>::~OrderList() {
    delete[] value;
    delete[] link;
}

template<class Type>
int OrderList<Type>::Search(Type x, int& index) {
    int left = 1, right = n, mid;
    int count = 0;
    while (left <= right) {
        count++;
        mid = (left + right) / 2;
        if (x == value[mid]) {
            index = mid;
            return count;
        }
        if (x < value[mid])
            right = mid - 1;
        else
            left = mid + 1;
    }
    index = left - 1;
    return count;
}

template<class Type>
int OrderList<Type>::SearchLast(void) {
    return n;
}

template<class Type>
void OrderList<Type>::Insert(Type k) {
    int i, j;
    if (n == MaxLength - 1) {
        cout << "Overflow\n";
        return;
    }
    for (i = 1; i <= n; i++) {
        if (value[i] >= k)
            break;
    }
    for (j = n; j >= i; j--) {
        value[j + 1] = value[j];
        link[j + 1] = link[j];
    }
    value[i] = k;
    link[i] = link[i - 1];
    n++;
}

template<class Type>
void OrderList<Type>::Delete(Type k) {
    int i, j;
    for (i = 1; i <= n; i++) {
        if (value[i] == k)
            break;
    }
    if (i > n) {
        cout << "Not found\n";
        return;
    }
    for (j = i; j < n; j++) {
        value[j] = value[j + 1];
        link[j] = link[j + 1];
    }
    n--;
}

template<class Type>
void OrderList<Type>::Output() {
    for (int i = 1; i <= n; i++)
        cout << setw(5) << value[i];
    cout << endl;
}

template<class Type>
void OrderList<Type>::OutList() {
    for (int i = 1; i <= n; i++)
        cout << setw(5) << value[i] << " ";
    cout << endl;
    for (int i = 1; i <= n; i++)
        cout << setw(5) << link[i] << " ";
    cout << endl;
}

int main() {
    int small = 1, large = 100, MaxL = 20;
    OrderList<int> A(small, large, MaxL);
    int index;
    int x = rnd.Random(1, 100);
    int count = A.Search(x, index);
    if (count == 0)
        cout << x << " not found\n";
    else
        cout << x << " is found at position " << index << " with " << count << " comparisons\n";
    x = rnd.Random(1, 100);
    count = A.Search(x, index);
    if (count == 0)
        cout << x << " not found\n";
    else
        cout << x << " is found at position " << index << " with " << count << " comparisons\n";
    for (int i = 0; i < MaxL; i++)
        A.Insert(i);
    A.Output();
    x = rnd.Random(1, 100);
    count = A.Search(x, index);
    if (count == 0)
        cout << x << " not found\n";
    else {
        cout << x << " is found at position " << index << " with " << count << " comparisons\n";
        A.Delete(x);
        A.Output();
    }
    return 0;
}

这个代码实现了一个 int 类型的有序表，其中 RandomNumber 为生成随机数的类，需要另外定义。在 main 函数中，首先进行了随机查找操作，然后进行了插入和删除操作，并输出了结果。