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

查找算法是计算机科学中十分重要的基础算法，本文将介绍三种经典的查找算法：折半查找、二叉排序树查找以及哈希表查找，并给出相应的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 - 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 = 6;
    int result = binarySearch(arr, n, target);
    if (result != -1) {
        printf('Found at index %d\n', result);
    } else {
        printf('Not found\n');
    }
    return 0;
}

二、二叉排序树查找算法的C语言实现

二叉排序树是一种特殊的二叉树，其每个节点的左子树所有节点的值均小于该节点的值，右子树所有节点的值均大于该节点的值。查找时，从根节点开始比较，根据比较结果选择左子树或右子树继续查找，直到找到目标节点或到达叶子节点。

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

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

TreeNode* createNode(int data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

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

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

int main() {
    TreeNode* root = NULL;
    root = insertNode(root, 8);
    insertNode(root, 3);
    insertNode(root, 10);
    insertNode(root, 1);
    insertNode(root, 6);
    insertNode(root, 14);
    insertNode(root, 4);
    insertNode(root, 7);
    insertNode(root, 13);

    int target = 6;
    TreeNode* result = searchNode(root, target);
    if (result != NULL) {
        printf('Found\n');
    } else {
        printf('Not found\n');
    }

    return 0;
}

三、哈希表查找的C语言实现

哈希表利用哈希函数将关键字映射到数组的某个位置，然后将数据存储在该位置。查找时，通过哈希函数计算关键字的哈希值，直接访问数组对应位置即可。哈希表查找效率高，但需要解决哈希冲突问题。

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

#define TABLE_SIZE 10

typedef struct HashNode {
    char name[50];
    struct HashNode* next;
} HashNode;

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

void insertNode(HashNode* hashTable[], char* name) {
    int index = hashFunction(name);
    HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
    strcpy(newNode->name, name);
    newNode->next = NULL;

    if (hashTable[index] == NULL) {
        hashTable[index] = newNode;
    } else {
        HashNode* current = hashTable[index];
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newNode;
    }
}

int searchNode(HashNode* hashTable[], char* name) {
    int index = hashFunction(name);
    HashNode* current = hashTable[index];
    while (current != NULL) {
        if (strcmp(current->name, name) == 0) {
            return 1;
        }
        current = current->next;
    }
    return 0;
}

int main() {
    HashNode* hashTable[TABLE_SIZE];
    for (int i = 0; i < TABLE_SIZE; i++) {
        hashTable[i] = NULL;
    }

    insertNode(hashTable, 'Alice');
    insertNode(hashTable, 'Bob');
    insertNode(hashTable, 'Charlie');
    insertNode(hashTable, 'David');
    insertNode(hashTable, 'Eva');

    char* target = 'Charlie';
    int result = searchNode(hashTable, target);
    if (result) {
        printf('Found\n');
    } else {
        printf('Not found\n');
    }

    return 0;
}

总结

本文介绍了三种常见的查找算法及其C语言实现，并提供了代码示例。在实际应用中，需要根据具体情况选择合适的查找算法，以获得最佳的性能。