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

查找算法是计算机科学中十分重要的基础算法，用于在一个数据集中快速找到目标元素。本文介绍三种常用的查找算法，并提供C语言代码示例：

一、有序表的折半查找算法

折半查找，也称为二分查找，是一种高效的查找算法，适用于已排序的数据集。

算法步骤：

从数据集的中间元素开始比较，如果目标元素等于中间元素，则查找成功。
如果目标元素小于中间元素，则在数据集的左半部分继续查找。
如果目标元素大于中间元素，则在数据集的右半部分继续查找。
重复步骤1-3，直到找到目标元素或数据集为空。

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, 2, 3, 4, 5, 6, 7, 8, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 5;
    
    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;
}

二、二叉排序树查找

二叉排序树是一种特殊的二叉树，其每个节点的值都大于其左子树的所有节点的值，小于其右子树的所有节点的值。

算法步骤：

从根节点开始比较，如果目标元素等于根节点的值，则查找成功。
如果目标元素小于根节点的值，则在左子树中继续查找。
如果目标元素大于根节点的值，则在右子树中继续查找。
重复步骤1-3，直到找到目标元素或到达空节点。

C语言代码示例：

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

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

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

Node* insertNode(Node* 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;
}

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

int main() {
    Node* root = NULL;
    
    root = insertNode(root, 4);
    root = insertNode(root, 2);
    root = insertNode(root, 6);
    root = insertNode(root, 1);
    root = insertNode(root, 3);
    root = insertNode(root, 5);
    root = insertNode(root, 7);
    
    int target = 5;
    Node* result = searchNode(root, target);
    
    if (result == NULL) {
        printf('Target not found\n');
    }
    else {
        printf('Target found\n');
    }
    
    return 0;
}

三、哈希表查找

哈希表是一种利用哈希函数将键映射到存储桶的数据结构，可以实现快速查找、插入和删除。

算法步骤：

使用哈希函数将目标元素的键映射到哈希表中的一个存储桶。
在该存储桶中查找目标元素。
如果找到，则查找成功。否则，查找失败。

C语言代码示例：

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

#define SIZE 10

typedef struct {
    char name[20];
    int age;
} Person;

typedef struct {
    Person* data;
    int key;
    int flag;
} 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[], Person* person) {
    int key = hash(person->name);
    
    while (hashTable[key].flag == 1) {
        key = (key + 1) % SIZE;
    }
    
    hashTable[key].data = person;
    hashTable[key].key = key;
    hashTable[key].flag = 1;
}

Person* search(HashNode hashTable[], char* name) {
    int key = hash(name);
    
    while (hashTable[key].flag != 0) {
        if (strcmp(hashTable[key].data->name, name) == 0) {
            return hashTable[key].data;
        }
        
        key = (key + 1) % SIZE;
    }
    
    return NULL;
}

int main() {
    HashNode hashTable[SIZE];
    
    for (int i = 0; i < SIZE; i++) {
        hashTable[i].flag = 0;
    }
    
    Person person1 = {'Alice', 20};
    Person person2 = {'Bob', 25};
    Person person3 = {'Charlie', 30};
    
    insert(hashTable, &person1);
    insert(hashTable, &person2);
    insert(hashTable, &person3);
    
    char name[20];
    printf('Enter a name to search: ');
    scanf('%s', name);
    
    Person* result = search(hashTable, name);
    
    if (result == NULL) {
        printf('Person not found\n');
    }
    else {
        printf('Person found: %s, %d years old\n', result->name, result->age);
    }
    
    return 0;
}

总结

本文介绍了三种常用的查找算法：折半查找、二叉排序树查找和哈希表查找，并提供了C语言代码示例。每种算法都有其优缺点，应根据具体情况选择合适的算法。