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

查找算法是计算机科学中非常基础和重要的算法之一。本文将介绍三种常用的查找算法：折半查找、二叉排序树查找和哈希表查找，并使用C语言实现这三种算法。

一、折半查找算法

折半查找算法适用于有序数组。其基本思想是：将目标值与数组中间元素进行比较，如果相等则查找成功；否则根据比较结果缩小查找范围，继续在数组的左半部分或右半部分进行查找，直到找到目标值或查找范围为空。

以下是使用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, 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('找到了，索引为：%d ', result); } else { printf('没找到 '); } return 0;}

二、二叉排序树查找

二叉排序树是一种特殊的二叉树，其每个节点的值都比其左子树上的所有节点的值大，比其右子树上的所有节点的值小。利用二叉排序树的这种性质，可以实现高效的查找操作。

以下是使用C语言实现二叉排序树查找的代码：c#include <stdio.h>#include <stdlib.h>

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

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

TreeNode* insert(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;}

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

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

int target = 6;    TreeNode* result = search(root, target);    if (result != NULL) {        printf('找到了，值为：%d

', result->val); } else { printf('没找到 '); } return 0;}

三、哈希表查找

哈希表是一种利用哈希函数将关键字映射到存储位置的数据结构。通过哈希函数，可以将查找操作的时间复杂度降低到O(1)。

以下是使用C语言实现哈希表查找的代码：c#include <stdio.h>#include <stdlib.h>#include <string.h>

#define HASH_SIZE 100

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

Node* hashTable[HASH_SIZE];

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

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

Node* search(char* name) { int index = hash(name); Node* cur = hashTable[index]; while (cur != NULL) { if (strcmp(cur->name, name) == 0) { return cur; } cur = cur->next; } return NULL;}

int main() { memset(hashTable, 0, sizeof(hashTable));

insert('Tom');    insert('Jerry');    insert('Alice');    insert('Bob');

char target[] = 'Alice';    Node* result = search(target);    if (result != NULL) {        printf('找到了，姓名为：%s

', result->name); } else { printf('没找到 '); } return 0;}

总结

本文介绍了三种常用的查找算法：折半查找、二叉排序树查找和哈希表查找，并使用C语言实现了这三种算法。不同的查找算法适用于不同的场景，需要根据具体的应用场景选择合适的查找算法。