编写算法建立线性表或二叉排序树并完成相应查找算法： 1. 先依次输入元素为简单类型（int、char）或自定义结构体类型（如订单信息或学生信息或员工信息）的数个数据元素建立顺序存储的线性表，然后①以该线性表为查找表进行顺序查找；②用冒泡排序对该线性表按某个关键字值进行排序，在排序之后的线性表之上进行折半查找。

以下是使用 C++ 实现的线性表和二叉排序树，并完成相应的查找算法：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 定义订单信息结构体
struct Order {
    int id;
    string name;
    double price;
};

// 定义学生信息结构体
struct Student {
    int id;
    string name;
    int age;
    double score;
};

// 定义员工信息结构体
struct Employee {
    int id;
    string name;
    string department;
    double salary;
};

// 定义简单类型元素的线性表类
template <typename T>
class LinearList {
public:
    // 构造函数
    LinearList() {
        size = 0;
        capacity = 10;
        data = new T[capacity];
    }

    // 析构函数
    ~LinearList() {
        delete[] data;
    }

    // 在线性表尾部插入元素
    void push_back(T element) {
        if (size == capacity) {
            capacity *= 2;
            T* new_data = new T[capacity];
            for (int i = 0; i < size; i++) {
                new_data[i] = data[i];
            }
            delete[] data;
            data = new_data;
        }
        data[size++] = element;
    }

    // 顺序查找元素
    int sequential_search(T element) {
        for (int i = 0; i < size; i++) {
            if (data[i] == element) {
                return i;
            }
        }
        return -1;  // 没有找到
    }

    // 冒泡排序
    void bubble_sort() {
        for (int i = 0; i < size - 1; i++) {
            for (int j = 0; j < size - i - 1; j++) {
                if (data[j] > data[j + 1]) {
                    swap(data[j], data[j + 1]);
                }
            }
        }
    }

    // 折半查找元素
    int binary_search(T element) {
        int left = 0, right = size - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (data[mid] == element) {
                return mid;
            } else if (data[mid] < element) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;  // 没有找到
    }

    // 打印线性表元素
    void print() {
        for (int i = 0; i < size; i++) {
            cout << data[i] << " ";
        }
        cout << endl;
    }

private:
    T* data;  // 数据存储区
    int size;  // 当前元素个数
    int capacity;  // 容量
};

// 定义二叉排序树节点类
template <typename T>
class BSTNode {
public:
    T data;  // 数据
    BSTNode<T>* left;  // 左子树指针
    BSTNode<T>* right;  // 右子树指针

    // 构造函数
    BSTNode(T data) {
        this->data = data;
        left = nullptr;
        right = nullptr;
    }
};

// 定义二叉排序树类
template <typename T>
class BinarySearchTree {
public:
    // 构造函数
    BinarySearchTree() {
        root = nullptr;
    }

    // 析构函数
    ~BinarySearchTree() {
        destroy(root);
    }

    // 在二叉排序树中插入元素
    void insert(T data) {
        insert_helper(root, data);
    }

    // 中序遍历二叉排序树，输出排序后的结果
    void inorder_traversal() {
        inorder_traversal_helper(root);
        cout << endl;
    }

    // 折半查找元素
    int binary_search(T element) {
        return binary_search_helper(root, element);
    }

private:
    BSTNode<T>* root;  // 根节点

    // 销毁二叉排序树
    void destroy(BSTNode<T>* node) {
        if (node != nullptr) {
            destroy(node->left);
            destroy(node->right);
            delete node;
        }
    }

    // 插入元素辅助函数
    void insert_helper(BSTNode<T>*& node, T data) {
        if (node == nullptr) {
            node = new BSTNode<T>(data);
        } else {
            if (data < node->data) {
                insert_helper(node->left, data);
            } else {
                insert_helper(node->right, data);
            }
        }
    }

    // 中序遍历二叉排序树辅助函数
    void inorder_traversal_helper(BSTNode<T>* node) {
        if (node != nullptr) {
            inorder_traversal_helper(node->left);
            cout << node->data << " ";
            inorder_traversal_helper(node->right);
        }
    }

    // 折半查找元素辅助函数
    int binary_search_helper(BSTNode<T>* node, T element) {
        if (node == nullptr) {
            return -1;  // 没有找到
        } else {
            if (node->data == element) {
                return 0;
            } else if (node->data < element) {
                int result = binary_search_helper(node->right, element);
                return result == -1 ? -1 : result + 1 + binary_search_helper(node->left, element);
            } else {
                int result = binary_search_helper(node->left, element);
                return result == -1 ? -1 : result + 1 + binary_search_helper(node->right, element);
            }
        }
    }
};

int main() {
    // 测试简单类型元素的线性表
    LinearList<int> list1;
    list1.push_back(5);
    list1.push_back(2);
    list1.push_back(4);
    list1.push_back(6);
    list1.push_back(1);
    list1.push_back(3);
    list1.print();
    cout << "Sequential search: " << list1.sequential_search(4) << endl;
    list1.bubble_sort();
    list1.print();
    cout << "Binary search: " << list1.binary_search(4) << endl;

    // 测试自定义结构体类型的线性表
    LinearList<Order> list2;
    list2.push_back({1, "book", 29.99});
    list2.push_back({2, "pen", 3.99});
    list2.push_back({3, "bag", 59.99});
    list2.push_back({4, "notebook", 9.99});
    list2.print();
    cout << "Sequential search: " << list2.sequential_search({3, "bag", 59.99}) << endl;
    list2.bubble_sort();
    list2.print();
    cout << "Binary search: " << list2.binary_search({3, "bag", 59.99}) << endl;

    // 测试二叉排序树
    BinarySearchTree<int> bst;
    bst.insert(5);
    bst.insert(2);
    bst.insert(4);
    bst.insert(6);
    bst.insert(1);
    bst.insert(3);
    bst.inorder_traversal();
    cout << "Binary search: " << bst.binary_search(4) << endl;

    return 0;
}

需要注意的是，在二叉排序树中进行折半查找时，要统计节点的左子树和右子树中小于或等于或大于查找元素的节点个数，具体实现可以参考上面的代码。