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

本文将使用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, 3, 5, 7, 9, 11, 13, 15};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 7;
    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* 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 {
        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("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;

void insert(Node* hashTable[], char name[]) {
    int index = strlen(name) % SIZE;
    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;
    }
}

int search(Node* hashTable[], char name[]) {
    int index = strlen(name) % SIZE;
    Node* curr = hashTable[index];
    while (curr != NULL) {
        if (strcmp(curr->name, name) == 0) {
            return 1;
        }
        curr = curr->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");
    insert(hashTable, "David");
    char target[] = "Charlie";
    int result = search(hashTable, target);
    if (result == 1) {
        printf("Target found\n");
    } else {
        printf("Target not found\n");
    }
    return 0;
}

注意: 以上代码示例仅供参考，你可以根据实际需求进行修改和完善。