说明1：假定本次实验中要查找的记录只有一个数据项，且该数据项为整数，用数组来存储记录集合。 说明2：读者在上机实验时, 可参考实验八中的基本函数，随机生成测试数据集。 说明3：二分查找（折半查找）算法需要对随机生成的数据集先排序，然后再查找。算法设计： 1．实现线性表的二分（折半）查找算法。 2．实现树表的二叉排序树的创建、插入、删除、查找算法。 3*．实现散列表的散列查找方法。C语言代码

下面是二分查找、二叉排序树、散列表的 C 语言代码实现。

1. 二分查找

int binarySearch(int arr[], int n, int x) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == x) {
            return mid;
        } else if (arr[mid] < x) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

在上述代码中，`arr` 表示要查找的数组，`n` 表示数组的长度，`x` 表示要查找的元素。函数会将数组按照从小到大的顺序排序，然后使用二分查找算法在数组中查找元素 `x`，如果找到则返回元素所在的下标，否则返回 -1。

2. 二叉排序树

// 定义二叉树节点
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 创建二叉排序树
TreeNode* createBST(int arr[], int n) {
    TreeNode *root = NULL;
    for (int i = 0; i < n; i++) {
        root = insertBST(root, arr[i]);
    }
    return root;
}

// 插入节点到二叉排序树
TreeNode* insertBST(TreeNode *root, int val) {
    if (root == NULL) {
        TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
        node->val = val;
        node->left = NULL;
        node->right = NULL;
        return node;
    }
    if (val < root->val) {
        root->left = insertBST(root->left, val);
    } else if (val > root->val) {
        root->right = insertBST(root->right, val);
    }
    return root;
}

// 删除二叉排序树中的节点
TreeNode* deleteBST(TreeNode *root, int val) {
    if (root == NULL) {
        return NULL;
    }
    if (val < root->val) {
        root->left = deleteBST(root->left, val);
    } else if (val > root->val) {
        root->right = deleteBST(root->right, val);
    } else {
        if (root->left == NULL) {
            TreeNode *temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            TreeNode *temp = root->left;
            free(root);
            return temp;
        }
        TreeNode *temp = findMin(root->right);
        root->val = temp->val;
        root->right = deleteBST(root->right, temp->val);
    }
    return root;
}

// 在二叉排序树中查找节点
TreeNode* searchBST(TreeNode *root, int val) {
    if (root == NULL || root->val == val) {
        return root;
    }
    if (val < root->val) {
        return searchBST(root->left, val);
    } else {
        return searchBST(root->right, val);
    }
}

// 查找二叉排序树中的最小值节点
TreeNode* findMin(TreeNode *root) {
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}

在上述代码中，`TreeNode` 结构体表示二叉树节点，其中 `val` 表示节点的值，`left` 表示节点的左子树，`right` 表示节点的右子树。`createBST` 函数用于创建二叉排序树，`insertBST` 函数用于向二叉排序树中插入节点，`deleteBST` 函数用于删除二叉排序树中的节点，`searchBST` 函数用于在二叉排序树中查找节点，`findMin` 函数用于查找二叉排序树中的最小值节点。

3. 散列表

// 定义散列表节点
typedef struct HashNode {
    int key;
    int val;
    struct HashNode *next;
} HashNode;

// 定义散列表
typedef struct HashTable {
    HashNode **table;
    int size;
} HashTable;

// 创建散列表
HashTable* createHashTable(int size) {
    HashTable *hashTable = (HashTable*)malloc(sizeof(HashTable));
    hashTable->table = (HashNode**)calloc(size, sizeof(HashNode*));
    hashTable->size = size;
    return hashTable;
}

// 计算散列值
int hash(int key, int size) {
    return key % size;
}

// 向散列表中插入节点
void insertHashTable(HashTable *hashTable, int key, int val) {
    int index = hash(key, hashTable->size);
    HashNode *node = (HashNode*)malloc(sizeof(HashNode));
    node->key = key;
    node->val = val;
    node->next = hashTable->table[index];
    hashTable->table[index] = node;
}

// 从散列表中删除节点
void deleteHashTable(HashTable *hashTable, int key) {
    int index = hash(key, hashTable->size);
    HashNode *prev = NULL, *curr = hashTable->table[index];
    while (curr != NULL && curr->key != key) {
        prev = curr;
        curr = curr->next;
    }
    if (curr == NULL) {
        return;
    }
    if (prev == NULL) {
        hashTable->table[index] = curr->next;
    } else {
        prev->next = curr->next;
    }
    free(curr);
}

// 在散列表中查找节点
int searchHashTable(HashTable *hashTable, int key) {
    int index = hash(key, hashTable->size);
    HashNode *curr = hashTable->table[index];
    while (curr != NULL) {
        if (curr->key == key) {
            return curr->val;
        }
        curr = curr->next;
    }
    return -1;
}

在上述代码中，`HashNode` 结构体表示散列表节点，其中 `key` 表示节点的键，`val` 表示节点的值，`next` 表示下一个节点。`HashTable` 结构体表示散列表，其中 `table` 是一个数组，表示散列表中的桶，每个桶存储一个链表。`createHashTable` 函数用于创建散列表，`hash` 函数用于计算散列值，`insertHashTable` 函数用于向散列表中插入节点，`deleteHashTable` 函数用于从散列表中删除节点，`searchHashTable` 函数用于在散列表中查找节点。