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

一、折半查找算法的实现

折半查找也称为二分查找，它是一种高效的查找算法，适用于有序数组。算法的基本思想是：每次将待查找的元素与数组中间元素进行比较，如果相等，则查找成功；如果待查找元素小于中间元素，则在左半部分继续查找；否则在右半部分继续查找。

#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 = 6;
    int result = binarySearch(arr, n, target);
    if (result == -1) {
        printf('Target not found\n');
    } else {
        printf('Target found at index %d\n', result);
    }
    return 0;
}

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

二叉排序树是一种常用的树形数据结构，它满足以下性质：

左子树中所有节点的值都小于根节点的值
右子树中所有节点的值都大于根节点的值
左子树和右子树本身也是二叉排序树

在二叉排序树中进行查找的过程类似于折半查找，每次将待查找元素与当前节点的值进行比较，根据比较结果决定下一步查找的方向。

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

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

TreeNode *createBST(int arr[], int n) {
    if (n == 0) {
        return NULL;
    }
    TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
    root->val = arr[0];
    root->left = NULL;
    root->right = NULL;
    for (int i = 1; i < n; i++) {
        TreeNode *curr = root;
        while (1) {
            if (arr[i] < curr->val) {
                if (curr->left == NULL) {
                    TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
                    newNode->val = arr[i];
                    newNode->left = NULL;
                    newNode->right = NULL;
                    curr->left = newNode;
                    break;
                } else {
                    curr = curr->left;
                }
            } else {
                if (curr->right == NULL) {
                    TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
                    newNode->val = arr[i];
                    newNode->left = NULL;
                    newNode->right = NULL;
                    curr->right = newNode;
                    break;
                } else {
                    curr = curr->right;
                }
            }
        }
    }
    return root;
}

TreeNode *searchBST(TreeNode *root, int target) {
    while (root != NULL) {
        if (root->val == target) {
            return root;
        } else if (root->val > target) {
            root = root->left;
        } else {
            root = root->right;
        }
    }
    return NULL;
}

void inorderTraversal(TreeNode *root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf('%d ', root->val);
        inorderTraversal(root->right);
    }
}

int main() {
    int arr[] = {5, 3, 8, 2, 4, 7, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    TreeNode *root = createBST(arr, n);
    inorderTraversal(root);
    printf('\n');
    
    int target = 4;
    TreeNode *result = searchBST(root, target);
    if (result == NULL) {
        printf('Target not found\n');
    } else {
        printf('Target found\n');
    }
    
    return 0;
}

三、哈希表查找的实现

哈希表是一种通过键值对存储数据的结构，它使用哈希函数将键映射到表中的某个位置。理想情况下，哈希函数应该能够将不同的键映射到不同的位置，但由于键的范围可能远大于表的容量，所以不可避免地会出现多个键映射到同一个位置的情况，这种情况称为“冲突”。为了解决冲突，通常采用链式地址法，即在每个位置上建立一个链表，将所有映射到该位置的键值对存储在该链表中。

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

#define SIZE 10

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

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

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

void search(Node *hashTable[], char *name) {
    int index = hashFunc(name);
    Node *curr = hashTable[index];
    while (curr != NULL) {
        if (strcmp(curr->name, name) == 0) {
            printf('Name found\n');
            return;
        }
        curr = curr->next;
    }
    printf('Name not found\n');
}

int main() {
    Node *hashTable[SIZE];
    for (int i = 0; i < SIZE; i++) {
        hashTable[i] = NULL;
    }
    
    insert(hashTable, 'Alice');
    insert(hashTable, 'Bob');
    insert(hashTable, 'Charlie');
    insert(hashTable, 'David');
    
    search(hashTable, 'Bob');
    search(hashTable, 'Eve');
    
    return 0;
}

总结

本文介绍了三种常用的查找算法：折半查找、二叉排序树查找和哈希表查找。每种算法都有其优缺点，在实际应用中需要根据具体情况选择合适的算法。

折半查找适用于有序数组，效率高，但要求数据有序；二叉排序树查找适用于动态数据，效率较高，但需要额外空间存储树结构；哈希表查找适用于随机数据，效率高，但需要处理冲突问题。