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

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

本文使用 C 语言分别实现了三种常见的查找算法：折半查找、二叉排序树查找和哈希表查找。通过实例代码演示如何创建有序表、二叉排序树和哈希表，并进行相应的查找操作，并附带详细注释，帮助读者理解实现原理。

一、折半查找算法的 C 语言实现

#include <stdio.h>

int binarySearch(int arr[], int low, int high, int target) {
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = 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 index = binarySearch(arr, 0, n - 1, target);
    if (index != -1) {
        printf('Target found at index %d\n', index);
    } else {
        printf('Target not found\n');
    }
    return 0;
}

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

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

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

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

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

struct TreeNode* search(struct 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 arr[] = {5, 3, 7, 2, 4, 6, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    struct TreeNode* root = NULL;
    for (int i = 0; i < n; i++) {
        root = insert(root, arr[i]);
    }
    int target = 6;
    struct TreeNode* result = search(root, target);
    if (result != NULL) {
        printf('Target found\n');
    } else {
        printf('Target not found\n');
    }
    return 0;
}

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

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

#define TABLE_SIZE 10

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

struct HashTable {
    struct Node* table[TABLE_SIZE];
};

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

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

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

int main() {
    struct HashTable ht;
    for (int i = 0; i < TABLE_SIZE; i++) {
        ht.table[i] = NULL;
    }
    insert(&ht, 'Alice');
    insert(&ht, 'Bob');
    insert(&ht, 'Charlie');
    char* target = 'Bob';
    if (search(&ht, target)) {
        printf('Target found\n');
    } else {
        printf('Target not found\n');
    }
    return 0;
}

以上代码分别实现了有序表的折半查找算法、二叉排序树的查找算法和哈希表查找算法。你可以根据需要调整具体的数据和查找目标进行调试。