C语言实现三种查找算法：有序表折半查找、二叉排序树查找、哈希表查找

前言

本文将介绍如何使用C语言编写三种常见的查找算法：有序表折半查找、二叉排序树查找、哈希表查找。每种算法都将提供详细的代码示例和调试步骤，帮助您理解和掌握。

一、有序表折半查找算法

1. 算法描述

折半查找算法，也称为二分查找算法，是一种高效的查找算法，适用于已排序的数据集。其基本思想是：

• 将目标值与数组中间元素进行比较。
• 如果目标值等于中间元素，则返回中间元素的索引。
• 如果目标值小于中间元素，则在数组左半部分继续查找。
• 如果目标值大于中间元素，则在数组右半部分继续查找。
• 重复以上步骤，直到找到目标值或确定目标值不存在于数组中。

2. 代码实现

#include <stdio.h>

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

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 5;
    
    int result = binarySearch(arr, n, target);
    if (result != -1) {
        printf('找到了，索引位置为：%d\n', result);
    } else {
        printf('未找到\n');
    }
    
    return 0;
}

3. 调试步骤

• 编译并运行代码，观察输出结果是否符合预期。
• 修改 target 的值，测试不同的查找目标。
• 尝试在数组中添加或删除元素，观察算法的正确性。

二、二叉排序树查找

1. 算法描述

二叉排序树是一种特殊的二叉树，其每个节点都满足以下性质：

• 左子树所有节点的值均小于根节点的值。
• 右子树所有节点的值均大于根节点的值。
• 左右子树也都是二叉排序树。

二叉排序树查找算法的思想是：

• 从根节点开始查找。
• 如果目标值等于根节点的值，则返回根节点。
• 如果目标值小于根节点的值，则在左子树中递归查找。
• 如果目标值大于根节点的值，则在右子树中递归查找。
• 如果查找过程中遇到空节点，则说明目标值不存在于树中。

2. 代码实现

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode *insert(TreeNode *root, int val) {
    if (root == NULL) {
        TreeNode *newNode = (TreeNode *) malloc(sizeof(TreeNode));
        newNode->val = val;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }
    
    if (val < root->val) {
        root->left = insert(root->left, val);
    } else if (val > root->val) {
        root->right = insert(root->right, val);
    }
    
    return root;
}

TreeNode *search(TreeNode *root, int val) {
    if (root == NULL || root->val == val) {
        return root;
    }
    
    if (val < root->val) {
        return search(root->left, val);
    } else {
        return search(root->right, val);
    }
}

int main() {
    int nums[] = {5, 3, 7, 2, 4, 6, 8};
    int n = sizeof(nums) / sizeof(nums[0]);
    TreeNode *root = NULL;
    
    for (int i = 0; i < n; i++) {
        root = insert(root, nums[i]);
    }
    
    int target = 4;
    TreeNode *result = search(root, target);
    
    if (result != NULL) {
        printf('找到了\n');
    } else {
        printf('未找到\n');
    }
    
    return 0;
}

3. 调试步骤

• 编译并运行代码，观察输出结果是否符合预期。
• 修改 target 的值，测试不同的查找目标。
• 尝试在二叉排序树中添加或删除节点，观察算法的正确性。

三、哈希表查找

1. 算法描述

哈希表是一种根据关键字直接访问内存存储位置的数据结构。它通过哈希函数将关键字映射到数组的某个位置，然后将对应的数据存储在该位置。

哈希表查找算法的步骤如下：

• 使用哈希函数计算关键字的哈希值。
• 根据哈希值定位到数组的对应位置。
• 如果该位置存储的数据与关键字匹配，则查找成功。
• 否则，发生冲突，需要使用某种冲突解决策略查找关键字。

2. 代码实现

#include <stdio.h>
#include <string.h>

#define SIZE 10

typedef struct {
    char name[20];
} Person;

typedef struct {
    Person data;
    int flag;
} HashNode;

int hash(char *name) {
    int sum = 0;
    for (int i = 0; i < strlen(name); i++) {
        sum += name[i];
    }
    return sum % SIZE;
}

void insert(HashNode table[], Person person) {
    int index = hash(person.name);
    while (table[index].flag != 0) {
        index = (index + 1) % SIZE;
    }
    table[index].data = person;
    table[index].flag = 1;
}

int search(HashNode table[], char *name, Person *result) {
    int index = hash(name);
    int count = 0;
    while (table[index].flag != 0 && count < SIZE) {
        if (strcmp(table[index].data.name, name) == 0) {
            *result = table[index].data;
            return 1;
        }
        index = (index + 1) % SIZE;
        count++;
    }
    return 0;
}

int main() {
    HashNode table[SIZE];
    memset(table, 0, sizeof(table));
    
    Person person1 = {'张三'};
    Person person2 = {'李四'};
    Person person3 = {'王五'};
    
    insert(table, person1);
    insert(table, person2);
    insert(table, person3);
    
    char name[] = '李四';
    Person result;
    if (search(table, name, &result)) {
        printf('找到了，姓名：%s\n', result.name);
    } else {
        printf('未找到\n');
    }
    
    return 0;
}

3. 调试步骤

• 编译并运行代码，观察输出结果是否符合预期。
• 修改 name 的值，测试不同的查找目标。
• 尝试在哈希表中添加或删除元素，观察算法的正确性。

四、总结

本文介绍了三种常见的查找算法：有序表折半查找、二叉排序树查找、哈希表查找。每种算法都有其优缺点，选择合适的算法取决于具体的应用场景。