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

查找算法是计算机科学中十分重要的基础算法，本文将介绍三种常用的查找算法，并使用C语言实现。

一、折半查找算法

折半查找算法，也称二分查找，适用于有序数组，其基本思想是：将目标值与数组中间元素比较，如果相等则返回中间元素索引；否则根据比较结果缩小查找范围，直到找到目标值或查找范围为空。

代码实现：

#include <stdio.h>

int binarySearch(int arr[], int n, int target) {
    int left = 0;
    int right = n - 1;
    
    while (left <= right) {
        int mid = (left + right) / 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, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 9;
    
    int result = binarySearch(arr, n, target);
    
    if (result != -1) {
        printf('找到了，索引为%d\n', result);
    }
    else {
        printf('没有找到\n');
    }
    
    return 0;
}

二、二叉排序树查找算法

二叉排序树是一种特殊的二叉树，其每个节点都满足：左子树所有节点的值都小于该节点的值，右子树所有节点的值都大于该节点的值。

代码实现：

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

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

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

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

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

三、哈希表查找算法

哈希表利用哈希函数将键映射到数组的特定位置进行存储，从而实现快速查找。理想情况下，哈希表查找的时间复杂度可以达到O(1)。

代码实现：

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

#define SIZE 10

typedef struct Node {
    char name[20];
    struct Node* next;
} Node;

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

void insert(Node* hashtable[], char* name) {
    int index = hash(name);
    
    Node* newNode = (Node*)malloc(sizeof(Node));
    strcpy(newNode->name, name);
    newNode->next = NULL;
    
    if (hashtable[index] == NULL) {
        hashtable[index] = newNode;
    }
    else {
        Node* temp = hashtable[index];
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

int search(Node* hashtable[], char* name) {
    int index = hash(name);
    
    Node* temp = hashtable[index];
    while (temp != NULL) {
        if (strcmp(temp->name, name) == 0) {
            return 1;
        }
        temp = temp->next;
    }
    
    return 0;
}

int main() {
    Node* hashtable[SIZE];
    for (int i = 0; i < SIZE; i++) {
        hashtable[i] = NULL;
    }
    
    insert(hashtable, 'Alice');
    insert(hashtable, 'Bob');
    insert(hashtable, 'Charlie');
    
    char* name = 'Bob';
    int result = search(hashtable, name);
    
    if (result == 1) {
        printf('找到了\n');
    }
    else {
        printf('没有找到\n');
    }
    
    return 0;
}

总结

本文介绍了三种常见的查找算法：折半查找、二叉排序树查找以及哈希表查找，并提供了C语言代码实现。每种算法都有其适用场景，选择合适的算法可以提高程序的效率。