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};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 9;
    int result = binarySearch(arr, n, target);
    if (result != -1) {
        printf("目标值 %d 在有序表中的位置是 %d\n", target, result);
    } else {
        printf("目标值 %d 在有序表中未找到\n", target);
    }
    return 0;
}

以下是C语言实现二叉排序树的查找算法的代码示例：

#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;
    } else {
        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;
    } else if (val < root->val) {
        return search(root->left, val);
    } else {
        return search(root->right, val);
    }
}

int main() {
    int arr[] = {5, 3, 7, 1, 4, 6, 8};
    int n = sizeof(arr) / sizeof(arr[0]);

    TreeNode* root = NULL;
    for (int i = 0; i < n; i++) {
        root = insert(root, arr[i]);
    }

    int target = 4;
    TreeNode* result = search(root, target);
    if (result != NULL) {
        printf("目标值 %d 在二叉排序树中找到\n", target);
    } else {
        printf("目标值 %d 在二叉排序树中未找到\n", target);
    }
    return 0;
}

以下是C语言实现哈希表查找的代码示例：

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

#define SIZE 10

// 哈希表结点定义
typedef struct HashNode {
    char name[20];
    struct HashNode* next;
} 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* hashTable[], char* name) {
    int index = hash(name);
    HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
    strcpy(newNode->name, name);
    newNode->next = NULL;
    if (hashTable[index] == NULL) {
        hashTable[index] = newNode;
    } else {
        HashNode* cur = hashTable[index];
        while (cur->next != NULL) {
            cur = cur->next;
        }
        cur->next = newNode;
    }
}

// 在哈希表中查找结点
int search(HashNode* hashTable[], char* name) {
    int index = hash(name);
    HashNode* cur = hashTable[index];
    while (cur != NULL) {
        if (strcmp(cur->name, name) == 0) {
            return 1;
        }
        cur = cur->next;
    }
    return 0;
}

int main() {
    HashNode* 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[20] = "Bob";
    int result = search(hashTable, target);
    if (result) {
        printf("目标值 %s 在哈希表中找到\n", target);
    } else {
        printf("目标值 %s 在哈希表中未找到\n", target);
    }
    return 0;
}